2018-09-09

ブロックヘッダのバージョンについてソフトフォークのデプロイ以外の汎用利用を提案するBIP-320

BIP Bitcoin

Bitcoinのブロックヘッダにはバージョンを表すnVersionフィールドが存在する。現在このnVersionフィールドは、コンセンサスに影響するような新しい機能をソフトフォークで導入する際に、ソフトフォークの準備ができたことを各マイナーがシグナリングするのに使われている。（と言っても、Segwit以降新たなソフトフォークの計画はまだ発表されてないけど）

BIP-9で定義されたこの仕様は、nVersionフィールドをビット列として解釈し、ソフトフォークの対応状況をその各bitを使ってシグナリングしている。詳細な仕様ついては↓参照。

techmedia-think.hatenablog.com

BIP-9のversion bitsによるシグナリングにより、異なるソフトフォークを29個同時にデプロイできるようになっているが、実際にそんな数のソフトフォークを並行デプロイするようなことはこれまで無かったし、今後も考えにくい。

そこで、このブロックヘッダのnVersionフィールドをソフトフォークのデプロイ以外にも使用できるようにしようというのがBtcDrakによって提案されたBIP-320↓

https://github.com/bitcoin/bips/blob/master/bip-0320.mediawiki

簡単に説明すると、ブロックヘッダのnVersionフィールドは4バイト（32 bit）あるが、そのうち16 bitを汎用的な目的のために確保し、BIP-9のversion bitsの解釈から取り除こうという提案。16 bitを任意に利用できるようにすることで、マイニング効率の向上などに繋げようと。

一時期話題にあがったAsicBoostだが、covert型とovert型の内、Segwitのデプロイによりcovert型は実質不可能になったが（Bitcoin Cashでは可能）、overt型の方はバージョンローリングをする方式なので、ちょうどこのBIPの内容に当てはまる。AsicBoostの特許は、その所有者がブロックチェーンの防衛特許ライセンス↓

bitcoinmagazine.com

に加入したことで、BDPLに参加するメンバーはその特許が利用可能になっていることから、そのあたりの絡みもあっての提案なのかもね。まぁ実際に現段階でそういう使い方をされていることもあるので、適用には問題ないと思う（あと、そもそも29個並行デプロイとかないし）。

以下、BIP-320の定義内容。

動機

マイナーはnVersionフィールドのいくつかのbitを、様々な用途に使用したいと考えている。しかし現在は、マイナーによってアクティベートされるソフトフォークの調整に使用しているため、これらのbitをソフトフォーク以外のシグナリング目的で使用すると、フルノードが未知のソフトフォークだと認識して誤った警告を生成する。nVersionフィールドのbitを汎用的な使用のために確保することで、ノードソフトウェアがそれらのbitを無視するようにアップグレードすることができ、誤った警告を生成することもなくなる。汎用的な使用のために16 bitを確保しても、まだ13個のソフトフォークの並行デプロイが可能であり十分だ。

使用例

以下はnVersionフィールドの一部のbitを使用できるようにすることで得られる利益の一例だ。このリストは網羅的ではない。

Bitcoinのマイニングハードウェアは現在200ms未満で32 bitのnonceフィールドを使い切る。このためコントローラは多くの帯域幅とCPU時間を消費して新しいジョブを非常に頻繁に各マイニングチップに配布する必要がある。これはより多くのbitをローリングすることで大幅に削減できる。同じくブロックヘッダにあるnTimeの多くのbitをローリングするという方法もあるが、タイムスタンプをより長い時間に渡って歪める可能性があるので理想的ではない。

バージョンローリングをするAsicBoostでは、4方向の衝突を計算するのにnVersionフィールドから2 bit必要だ。任意の2 bitが使用できると、マイニング装置はStratumの「version-rolling」拡張を使ってどのbitがマイニングプールで使用されるか交渉することができる。

仕様

13から始まり28（0x1fffe000を含む）で終わるブロックヘッダのnVersionフィールドの16 bitを汎用的な使用のために確保され、BIP-8およびBIP-9の仕様からは削除される。nVersion bitに0xe0001fffのマスクを適用し、ソフトフォークのシグナリングおよびソフトフォークの警告に対してbit 13〜28を無視する。

参照実装

github.com

後方互換性

アップグレードされていないノードは、この提案で確保されるbitをソフトフォークのシグナリングとして解釈し、さらに未知のソフトフォークの警告システムをアクティブにすることがある。

この提案を実装するのにソフトフォークは必要としない。

これが記載されている時点で、このBIPで確保しようとしている16 bitのいずれも既知のソフトフォークで確保されてはおらず、ハッシュレートの少なくない割合がすでにそれらのbitを使用していることを考慮すると、将来のソフトフォークでアクティベーションのシグナリングにこれらのbitを使用すべきではない。

2018-09-04

SchnorrベースのScriptlessな「Multi-Hop Locks」の実現方法

Bitcoin Scriptless Scripts Schnorr Payment Channel Lightning network Cryptography

techmedia-think.hatenablog.com

と書いたので、残ったSchnorrベースのMulti-Hop Locksについても書いておく。
（Multi-Hop Locksのコンセプトについては最初の記事参照）

SchnorrベースのMulti-Hop Locksは署名アルゴリズム自体がSchnorrとECDSAで違うだけで、基本的な構成はECDSAの時と同じだ。

鍵生成フェーズ

各ユーザー ${U_i}$ が持つ秘密鍵を ${x_i}$ とし、対応する公開鍵を ${P_i = x_iG}$ とする。

決済の経路間のユーザー＝ペイメントチャネルを直接開いているユーザーは、相手と鍵生成プロトコルを使用して二者間の公開鍵を計算する。例えば ${Ui, U_{i+1}}$ は、それぞれ公開鍵 ${P_i, P_{i+1}}$ を持っているが、Schnorrの公開鍵の集約特性を利用し、両者の公開鍵を加算した共有鍵 ${P = P_i + P_{i+1}}$ を算出する。

通常、Schnorr署名では上記の共有鍵Pにロックされたコインは、

${U_i}$ が ${s_i = k_i + H(P, R, m)x_i}$
${U_{i+1}}$ が ${s_{i+1} = k_{i+1} + H(P, R, m)x_{i+1}}$

をそれぞれ計算し、 ${s_i + s_{i+1}}$ を計算した ${(R, s)}$ がPに対する有効な署名となる。

送信者から中間者、受信者の3人の場合、それぞれ ${x_0, x_1, x_2}$ の秘密鍵を持っている場合、

${U_0}$ （送信者）と ${U_1}$ （中間者）の共有鍵は ${P_0 = x_0G + x_1G}$
${U_1}$ （中間者）と ${U_2}$ （受信者）の共有鍵は ${P_1 = x_1G + x_2G}$

となる。

セットアップフェーズ

LNで支払いを行う送信者は受信者までの数分（n）、ランダムに値をサンプリング（ ${y_0, ...., y_n}$ ）する。
続いて1〜nについて ${Y_i = Y_{i-1} + y_iG}$ を計算する。なお、 ${Y_0} = y_0G$ 。
送信者は受信者までの各ユーザーに対して３つのアイテムを送信する。送信者から中間者、受信者の3人の場合、それぞれに送られるデータは
- ${U_0}$ （送信者）には ${(n/a, Y_0, y_0)}$
- ${U_1}$ （中間者）には ${(Y_0, Y_1, y_1)}$
- ${U_2}$ （受信者）には ${(Y_1, Y_2, y_2)}$
最後に受信者にのみ追加で、全てのサンプリング値を加算した（ ${y_0 + y_1 + y_2}$ ）オープン鍵を送る。

この部分は、ECDSAと全く同じ。

ロックフェーズ

ECDSAとは署名アルゴリズムが異なるので署名の構成方法は異なるが、基本的には ${Y_i}$ をRに含めることで、Rの構成にシークレットを含めるという仕掛けは変わらない。

ロックフェーズは ${U_i, U_{i+1}}$ 間で始まる。まず両者はECDSA署名に必要なランダムなnonceについて合意する。それぞれランダムに ${r_i, r_{i+1}}$ を選択し、それぞれ ${r_i G}$ 、 ${r_{i+1}G}$ を計算する。それぞれ計算した点を明らかにし、自分のnonceと組み合わせて共通の ${R_{i} = r_iG + r_{i+1}G + Y_i}$ を計算する。

ここで ${Y_i}$ を加算しているのがポイントだ。

ECDSAと違ってSchnorr署名は署名アルゴリズム自体が署名の集約をサポートしているため、まず以下のように ${Y_i}$ がなかった場合に有効な署名を計算する。

${U_i}$ は ${s_i = r_i + H(P, R, m)x_i}$ を計算
${U_{i+1}}$ は ${s_{i+1} = r_{i+1} + H(P, R, m)x_{i+1}}$ を計算

${s_i + s_{i+1}}$ を計算すると、

${s' = r_i + r_{i+1} + H(P, R, m)(x_i + x_{i+1})}$

になるが、このままでは ${Y_i}$ の離散対数の情報がないので、 ${R_i}$ に対応した署名としては無効だ。

これを有効な ${R_i}$ に対応した有効な署名にするためには、s'に対して ${Y_i}$ の離散対数 ${y_i}$ を加算する必要がある。

ECDSAの場合と同様各 ${Y_i}$ の離散対数が、受信者→送信者の経路で順にアンロックするトリガーとなる。

送信者から中間者、受信者の3人の場合、送信者から中間者、受信者の3人の場合、それぞれ ${r_0,r_1,r_2}$ のnonceを選択した状態で、それぞれの間で作成されるRと署名データは以下のようになる。

${U_0}$ （送信者）と ${U_1}$ （中間者）

${R_0 = r_0G + r_1G + Y_0}$ $\biggl( R_0, s' = r_0 + r_1 + H(P, R, m)(x_0 + x_1)\biggr)$

${Y_0 = y_0G}$ であることから、この署名に対して必要な ${Y_0}$ の離散対数は ${y_0}$ 。

${U_1}$ （中間者）と ${U_2}$ （受信者）

${R_1 = r_1G + r_2G + Y_1}$ $\biggl( R_1, s' = r_1 + r_2 + H(P, R, m)(x_1 + x_2)\biggl)$

${Y_1 = Y_0 + y_1G}$ であることから、この署名に対して必要な ${Y_1}$ の離散対数は ${y_0 + y_1}$ 。

リリースフェーズ

リリースフェーズでは、ロックフェーズでロックされたコインを入手するのに各チャネルでアンロック条件となっている離散対数を明らかにする。

送信者から中間者、受信者の3人の場合、受信者はオープン鍵 ${y_0 + y_1 + y_2}$ と ${y_2}$ を持っているため、中間者からコインを貰う際の署名に使った ${Y_1}$ の離散対数をオープン鍵から ${y_2}$ を引くことで算出できる。この離散対数を中間者に対し明らかにすることで、コインを入手する。

中間者は ${y_0 + y_1}$ の離散対数を知ったので、そこから予め知っている ${y_1}$ の値を引けば、 ${Y_0}$ の離散対数 ${y_0}$ を算出でき、これを使って送信者から資金を入手する署名を完成させることができる。

途中の参加者が離散対数を相手に伝えることがなく、トランザクションをブロードキャストした場合も、ブロードキャストされたトランザクションで使われている署名値sを使ってs - s'を計算することで、自身がコインの入手に必要な離散対数を手に入れることができる。

といった形で、Schnorrの場合もECDSAと同様、署名のR値に受信者→送信者の順にアンロック要素が明らかになる離散対数のロック条件をしのばせることで、Scriptlessな「Multi-Hop Locks」を構成しているのが分かる。

2018-09-03

ECDSAベースのScriptlessな「Multi-Hop Locks」の実現方法

Bitcoin Scaling Bitcoin Scriptless Scripts Payment Channel Lightning network ECDSA Cryptography

Scaling Bitcoin 2018のセッションの１つでもある、LNなどで利用されているペイメントチャネルネットワークの新しいプリミティブである「Multi-Hop Locks」について、以前一方向準同型関数を使った実装方法について書いたが↓

techmedia-think.hatenablog.com

Multi-Hop Locksには、一方向準同型関数を使用する方法以外に、

SchnorrベースのScriptless Scripts
ECDSAベースのScriptless Scripts

で実現する方法が定義されている。

今回は、現在のBitcoinでも利用可能なECDSAを使ったScriptless Scriptベースの実現方法についてみてみる。（ホワイトペーパーの内容を適当に脳内補間してるので誤解している可能性あり）

鍵生成フェーズ

各ユーザー ${U_i}$ が持つ秘密鍵を ${x_i}$ とし、対応する公開鍵を ${P_i = x_iG}$ とする。

決済の経路間のユーザー＝ペイメントチャネルを直接開いているユーザーは、相手と鍵生成プロトコルを使用して二者間の公開鍵を計算する。例えば ${Ui, U_{i+1}}$ は、 ${U_i}$ は ${x_i P_{i+1}}$ を計算し、 ${U_{i+1}}$ は ${x_{i+1} P_i}$ を計算することで共通の公開鍵 ${P_{(i, i+1)}}$ を計算することができる。この公開鍵に対応する秘密鍵は、2人の秘密鍵を乗算した ${x_i \cdot x_{i+1}}$ である。

ここで導出した共有鍵にコインをロックすることは、アンロックに2人の秘密の情報を必要とするという意味で、2-of-2のマルチシグへのコインのロックと同等のこととなる。

送信者から中間者、受信者の3人の場合、それぞれ ${x_0, x_1, x_2}$ の秘密鍵を持っている場合、

${U_0}$ （送信者）と ${U_1}$ （中間者）の共有鍵は ${P_0 = (x_0 \cdot x_1)G}$
${U_1}$ （中間者）と ${U_2}$ （受信者）の共有鍵は ${P_1 = (x_1 \cdot x_2)G}$

※ 簡易的に同じ記載にしてるけど、中間者の ${x_1}$ は相手によって違う鍵になると思われる。

セットアップフェーズ

LNで支払いを行う送信者は受信者までの数分（n）、ランダムに値をサンプリング（ ${y_0, ...., y_n}$ ）する。
続いて1〜nについて ${Y_i = Y_{i-1} + y_iG}$ を計算する。なお、 ${Y_0} = y_0G$ 。
送信者は受信者までの各ユーザーに対して３つのアイテムを送信する。送信者から中間者、受信者の3人の場合、それぞれに送られるデータは
- ${U_0}$ （送信者）には ${(n/a, Y_0, y_0)}$
- ${U_1}$ （中間者）には ${(Y_0, Y_1, y_1)}$
- ${U_2}$ （受信者）には ${(Y_1, Y_2, y_2)}$
最後に受信者にのみ追加で、全てのサンプリング値を加算した（ ${y_0 + y_1 + y_2}$ ）オープン鍵を送る。

ロックフェーズ

ロックフェーズは ${U_i, U_{i+1}}$ 間で始まる。まず両者はECDSA署名に必要なランダムなnonceについて合意する。それぞれランダムに ${r_i, r_{i+1}}$ を選択し、それぞれ ${r_i Y_i}$ 、 ${r_{i+1} Y_i}$ を計算する。それぞれ計算した点を明らかにし、自分のnonceと組み合わせて共通の ${R_{i} = (r_i \cdot r_{i+1})Y_i}$ を計算する。

ここでRの計算に両者のnonceをGではなく、Yに乗算しているのがポイントになる。

まずは ${Y_i}$ を無視して、二者の共有鍵に対する署名をLindellのプロトコルを使って計算する↓

techmedia-think.hatenablog.com

${Y_i}$ を無視したその署名データは

$\biggl( r_x, s' = \frac{r_x(x_{i-1} \cdot x_i) + H(m)}{r_{i-1} \cdot r_i} \biggr)$

となる。当然この署名データには ${Y_i}$ が考慮されていないので、有効な署名ではない。有効な署名にするためには ${Y_i}$ の離散対数 ${y_i}$ を使って、 ${s' \cdot y_i^{-1}}$ を計算すると、

$\biggl( r_x, s = \frac{r_x(x_{i-1} \cdot x_i) + H(m)}{r_{i-1} \cdot r_i \cdot y_i} \biggr)$

と有効な署名が作成できる。

この ${Y_i}$ の離散対数の知識が、受信者→送信者への経路でコインの入手と共に明らかになるデータになる。

つまり、2者間の共有鍵にロックされた資金の内、ペイメントチャネルのマルチホップ決済の送金分のコインを相手に送金するトランザクションを作成するが、そのトランザクションの署名で使用するRには、セットアップフェーズで送信者から配布された ${Y_i}$ が含まれ、この署名を有効なものにするためには、 ${Y_i}$ の離散対数の知識が必要になる。この離散対数が従来のLNのHTLCで扱われるシークレットの代替となる。

送信者から中間者、受信者の3人の場合、送信者から中間者、受信者の3人の場合、それぞれ ${r_0, r_1, r_2}$ のnonceを選択した状態で、それぞれの間で作成されるRと署名データは以下のようになる。

${U_0}$ （送信者）と ${U_1}$ （中間者）

${R_0 = (r_0 \cdot r_1)Y_0}$ $\biggl( r_x, s' = \frac{r_x(x_{0} \cdot x_1) + H(m)}{r_{0} \cdot r_1} \biggr)$

${Y_0 = y_0G}$ であることから、この署名に対して必要な ${Y_0}$ の離散対数は ${y_0}$ 。

${U_1}$ （中間者）と ${U_2}$ （受信者）

${R_1 = (r_1 \cdot r_2)Y_1}$ $\biggl( r_x, s' = \frac{r_x(x_{1} \cdot x_2) + H(m)}{r_{1} \cdot r_2} \biggr)$

${Y_1 = Y_0 + y_1G}$ であることから、この署名に対して必要な ${Y_1}$ の離散対数は ${y_0 + y_1}$ 。

リリースフェーズ

リリースフェーズでは、ロックフェーズでロックされたコインを入手するのに各チャネルでアンロック条件となっている離散対数を明らかにする。

途中の参加者が離散対数を相手に伝えることがなく、トランザクションをブロードキャストした場合も、ブロードキャストされたトランザクションで使われている署名値sを使ってs'・s^-1を計算することで、自身がコインの入手に必要な離散対数を手に入れることができる。

注意点としては、ECDSAの署名(r, s)のsは-s mod q した場合でも有効で、これを許可すると成立しなくなるので、sは ${\frac{q-1}{2}}$ 以下であるというLOW_Sルールが前提となる。よく考えたら、sが変更されていた場合、もう１つのsの候補を計算すればいいだけなので、問題はなかった。

上記の方法を使えば、既存のBitcoinですぐにScriptlessなMulti-Hop LocksのLNコントラクトを実装することができるっぽい。ECDSA + Scriptlessということだったので、楕円曲線の操作がベースになるとは思ったけど、nonceのRを利用するのね。

2018-08-23

Schnorr署名と検証可能な秘密分散法を利用したm-of-nのマルチシグスキーム

Bitcoin Cryptography 秘密分散

SchnorrのBIPドラフト↓

https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki

に応用例の１つとして記載されているのが、Scnorr署名とペダーセンの検証可能な秘密分散法を利用してm-of-nのマルチシグを構成するというもので、参照論文↓

https://t.co/jMhQnovLcb

をざっと読んで、どう構成なのか見てみる。

前提技術

まず、前提となる暗号技術として、以下のシャミアの閾値法、ペダーセンの検証可能な秘密分散法などについておさえとく。

以下、楕円曲線の離散対数問題を利用するため、qを巨大な素数とし、GとHを楕円曲線Eの位数qのサブグループのジェネレータ、h()を一方向ハッシュ関数とする。

シャミアの(t, n)閾値法

ベースとなるプリミティブの１つが(t, n)閾値法。これはディーラーがある秘密のシークレットをn個のシェア*1に分割し、このシェアをt個集めるともとのシークレットを復元することができるというシャミアの秘密分散法で実現できる。

秘密分散のシェアの作成

秘密のシークレットをs、閾値をtとした場合、ディーラーがn人のパーティに配布する各シェアは、f(0) = s を満たすt-1の次数を持つランダムな多項式

${f(x) = s + a_1x + a_2x^2 + ... + a_{t-1}x^{t-1} \mod p}$

から作られる。

例えば閾値t = 3、シークレットs = 5とした場合の多項式は

f(x) = 5 + ax + bx²

のような式になる。aとbの係数は何でもいいので

f(x) = 5 + 3x + 5x²

とかでも良い、重要なのはf(0) = シークレット値となるt-1次の多項式を決めること。

多項式が決まったら、n人のパーティに配布するシェアをその多項式から生成する。

例えば5人のパーティなら

${x_1 = f(1) = 13 = (1, 13)}$
${x_2 = f(2) = 31 = (2. 31)}$
${x_3 = f(3) = 59 = (3, 59)}$
${x_4 = f(4) = 97 = (4, 97)}$
${x_5 = f(5) = 145 = (5, 145)}$

が各ユーザーに配布するシェアのペアになる。

シェアからシークレットを復元

↑のように分割したシェアの内、t個が揃うとラグランジュの補間公式 ${f(x) = \sum_{i=1}^{t}y_i \frac{f_i(x)}{f_i(x_i)}}$ を使って多項式を復元できる。

上記ではt = 3なのでラグランジュの補間公式は、

${f(x) = y_1\frac{(x-x_2)(x-x_3)}{(x_1-x_2)(x_1-x_3)} + y_2 \frac{(x-x_1)(x-x_3)}{(x_2-x_1)(x_2-x_3)} + y_3 \frac{(x-x_1)(x-x_2)}{(x_3 - x_1)(x_3 - x_2)}}$

を使って計算すればいい。例えば、(1, 13)、（3, 59）、(4, 97)をそれぞれ↑の式に当てはめると

f(x) = 5 + 3x + 5x²

が算出できる。こうやって復元した多項式からシークレットsの値が何か分かる。

ペダーセンの検証可能な秘密分散法

シャミアの秘密分散法によりシークレットを各ユーザーに分割して渡すことができるが、この場合、各ユーザーに配布されるシェアは本当にシークレットから生成されたものかどうかは、シェアを生成したディーラーを信頼する必要がある。もしディーラーが不正をして誤った値のシェアを配布した場合、t個のシェアを集めても本当のシークレットを復元することはできない。

この問題を解消するのがペダーセンの検証可能な秘密分散法（Verifiable Secret Sharing Scheme＝VSS）。

VSSは以下のように動作する。

ディーラーによるシェアの作成

ディーラーはシークレットsとは別にランダムな整数s'を選択する。
sとs'について、それぞれ別の多項式をランダムに選択する。
${f(x) = s + a_{1}x' + a_{2}x^{2} + ... + a_{t-1}x^{t-1}}$
${f'(x) = s' + b_1x' + b_2x'^2 + ... + b_{t-1}x'^{t-1}}$
多項式f(x)とf(x')を使ってn個のシェアを計算し、シェアのペア ${(s_i, s'_i)}$ を安全な経路で各パーティに送る。
シェアとは別にコミットメント ${C_j = a_jG + b_jH}$ を計算し、ブロードキャストする（jは0≦ j ≦ t-1）。

例えば選択した多項式が以下の場合

f(x) = 5 + 3x + 5x²
f'(x) = 3 + 2x + 7x²

上記手順3でディーラーが各パーティ（n=4）に作成するシェアのペアは↓

(f(1), f'(1)) = (13, 12)
(f(2), f'(2)) = (31, 35)
(f(3), f'(3)) = (59, 72)
(f(4), f'(4)) = (97, 123)

手順4で作成するコミットメントは↓

${C_0 = 5G + 3H}$
${C_1 = 3G + 2H}$
${C_2 = 5G + 7H}$

になる。

各ユーザーの検証

各ユーザーは、個別に受信したペア ${(s_i, s'_i)}$ とブロードキャストされたコミットメントを使って、

${s_iG + s'_iH = \sum_{j=0}^{t-1} \, i^j \, C_j}$

が成立するか検証して、成立すれば自身のシェアは正しいシェアであることが分かる。

例えば、(f(1), f'(1)) = (13, 12)を受け取ったユーザーは、

${13G + 12H = C_0 + C_1 + C_2 = 5G + 3H + 3G + 2H + 5G + 7H}$

が成立するか検証し、(f(2), f'(2)) = (31, 35)を受け取ったユーザーは、

${31G + 35H = C_0 + 2C_1 + 4C_2 = 5G + 3H + 6G + 4H + 20G + 28H}$

が成立するか検証する。

シークレットを含む ${C_0 = 5G + 3H}$ が公開されるが、シークレットの値は ${C_0}$ からは分からない。

これが成立しない場合、受け取ったシェアは不正なシェアになる。

このように公開されたコミットメントと自身が受け取ったシェアを使って、そのシェアが確かにシークレットから生成されたものであるか検証できるようにするのがVSS。

ランダムシークレットの生成

上記の秘密分散法ではいずれも信頼できるディーラーがシークレットを生成し、シェアを作成、配布していたが、これをディーラー抜きで行う。要は、各ユーザーから集めた情報を元にシークレットを生成する。

各ユーザーは以下の手順を実行する。

各ユーザー ${U_i}$ はランダムに値 ${r_i, r'_i}$ を選択する。
※ 参加者数がnの場合、各ユーザーの ${r_i}$ を合算した ${\sum_{i=1}^{n}r_i}$ がシークレットになり、このシークレットを復元する際に使う多項式は、以下の2で各ユーザーが作成した多項式の和で構成される。
続いて各ユーザーはそれぞれ以下の２つの多項式を生成する。
- ${f_i(x) = a_{i0} + a_{i1}x + a_{i2}x^{2} + ... + a_{i t-1}x^{t-1}}$
- ${f'_i(x) = b_{i0} + b_{i1}x + b_{i2}x^{2} + ... + b_{i t-1}x^{t-1}}$
  この時、多項式のシークレット値はそれぞれ ${a_0 = r_i}$ 、 ${b_0 = r'_i}$ とする。
続いて各ユーザーは、 ${0 ≦ m ≦ t-1}$ のコミットメント ${C_{im} = a_{im}G + b_{im}H}$ を計算し公開する。
続いて各ユーザーは、 ${1 ≦ j ≦ n}$ で ${s_{ij} = f_i(j)}$ と、 ${s'_{ij} = f'_i(j)}$ を計算し、計算した値をユーザー ${U_j}$ に送る。
${(s_{ij}, s'_{ij})}$ を受け取ったユーザー ${U_j}$ はそのシェアが正しいか、送信者が公開しているコミットメントを使い ${s_{ij}G + s'_{ij}H = \sum_{m=0}^{t-1} \, j^{m} \, C_{im}}$ で検証する。この１つ１つのシェアの検証に↑のVSSが使われる。
続いて各ユーザーは ${A_{ik} = a_{ik}G}$ を算出し、ブロードキャストする（kは、 ${0 ≦ k ≦ t-1}$ ）。
各ユーザーは、他のユーザーによってブロードキャストされた値が正しい値か、 ${s_{ij}G = \sum_{k=0}^{t-1} \, j^{k} \, A_{ik}}$ が成立するか検証する。

各ユーザーがランラムに選択したシークレットに対する公開鍵は、最後に各ユーザーが公開した ${a_{ik}G}$ のリストの内、全ユーザーの ${a_{i0}G}$ を合算した ${Pub = \sum_{i=1}^{n}a_{i0}G}$ になる。

このプロトコルを実行することで、各ユーザーが生成したランダム値 ${r_i}$ を合算した値を秘密鍵とした際に、それに対応する公開鍵を共有することができる。このプロトコルでは各ユーザーは ${r_i}$ を直接公開しないし、シェアを集めて復元もしていないので実際の秘密鍵rは知られていない。

計算例

実際に↑のプロトコルに沿って計算してみよう。数が多いと大変なので、今回は2-of-3にする。

まず、各ユーザーはそれぞれシークレットを選択し（アリス：３、ボブ：７、キャロル：２）、そのシークレットを使った多項式を以下のように決める。

アリスの多項式
- fa(x) = 3 + 4x
- fa'(x) = 5 + 2x
ボブの多項式
- fb(x) = 7 + x
- fb'(x) = 3 + 5x
キャロルの多項式
- fc(x) = 2 + 7x
- fc'(x) = 8 + 9x

続いて、各ユーザーは多項式の定数項を使ってコミットメントを計算し公開する。

アリスが公開するコミットメント
- Ca0 = 3G + 5H
- Ca1 = 4G + 2H
ボブが公開するコミットメント
- Cb0 = 7G + 3H
- Cb1 = G + 5H
キャロルが公開するコミットメント
- Cc0 = 2G + 8H
- Cc1 = 7G + 9H

続いて、各ユーザーはそれぞれの多項式を利用してf(x)とf'(x)のシェアを計算して、別のユーザーに送る。

アリスが提供するシェア
- (s11, s'11) = (7, 7)
- (s12, s'12) = (11, 9)
ボブが提供するシェア
- (s21, s'21) = (8, 8)
- (s22, s'22) = (9, 13)
キャロルが提供するシェア
- (s31, s'31) = (9, 17)
- (s32, s'32) = (16, 26)

シェアを送られたユーザーはそのシェアが正しい値か送信元が公開したコミットメントを使って ${s_{ij}G + s'_{ij}H = \sum_{m=0}^{t-1} \, j^{m} \, C_{im}}$ を検証する。例えば、アリスが(s12, s'12)=（11, 9）をキャロルに送った場合、キャロルは以下を検証する。

11G + 9H = Ca0 + 2Ca1 = （3G + 5H） + 2(4G + 2H) = 3G + 5H + 8G + 4H = 11G + 9H

続いて、各ユーザーの多項式f(x)の定数項を楕円曲線のベースポイントに乗算して公開鍵を計算し、ブロードキャストする。

アリスが公開する公開鍵
- A10 = 3G
- A11 = 4G
ボブが公開する公開鍵
- A20 = 7G
- A21 = G
キャロルが公開する公開鍵
- A30 = 2G
- A31 = 7G

他のユーザーがブロードキャストした公開鍵が正しいか、送信元から受け取ったシェアを使って ${s_{ij}G = \sum_{k=0}^{t-1} \, j^{k} \, A_{ik}}$ を検証する。例えばキャロルがブロードキャストした公開鍵が正しいかボブが検証する場合は以下を検証する（ボブはキャロルからシェア（16, 26）を受け取っている）。

16G = 2G + 2(7G) = 2G + 14G

各ユーザーがブロードキャストした全ての公開鍵の検証が成功すると、各ユーザーが公開したAi0の公開鍵を加算した点がマルチシグの公開鍵になる。

A10 + A20 + A30 = 3G + 7G + 2G = 12G

これは各ユーザーがランダムに生成したシークレット（アリス：３、ボブ：７、キャロル：２）の共有シークレットに対応した公開鍵となる。

Schnorr署名

残りはSchnorr署名。これはシンプルで、楕円曲線を使う場合（ジェネレータをG、秘密鍵をx、公開鍵をP=xG、署名対象のメッセージをmとする）、その署名は以下のように計算される。

ランダム値kを選択。
R = kGを計算。
s = k + h(P, R, m)x を計算する。
(R, s)がmに対する署名

署名の検証は、sG = R + h(P, R, m)Pが成立するか検証する。

(t, n)閾値署名方式

前提が長かったけど、本題に入る。Schnorr署名を利用したm-of-nのマルチシグスキーム。

実際のSchnorrベースの（t, n）閾値署名は以下の鍵生成プロトコルと署名発行プロトコルで構成される。

鍵生成プロトコル

鍵生成プロトコルでは、↑のランダムシークレット生成のプロトコルを利用して、マルチシグの参加者は、協力して公開鍵と秘密鍵のシェアを生成する。これによりランダムな共有シークレットができる。

このプロトコルの結果、

共有される秘密鍵をx
各ユーザーが持つ秘密鍵 ${r_i}$ のシェアを ${α_i}$
各ユーザーが公開する自身の多項式の定数を使って計算した各点を ${a_{im}G}$ （0 ≦ m ≦ t-1）
公開鍵を ${P = \sum_{i=1}^{n}a_{i0}G}$

とする。

ここで生成した公開鍵宛にコインを送ること＝t-of-nのマルチシグへコインを送ることになる。

署名発行プロトコル

署名対象のメッセージmに対して、鍵生成プロトコルで生成したt-of-nのマルチシグの公開鍵Pに対して有効なSchnorr署名を生成する。この時、協力するユーザーがt人未満の場合は署名は作成できない。

手順１

まず、署名生成にあたって上記のSchnorr署名のプロトコルにあるように、ランダムな値eとその点R = eGが必要となるが、これも鍵生成プロトコルで使用したのと同じランダムシークレット生成のプロトコルを利用して生成することになる。

ランダムシークレット生成のプロトコルを実行した結果を

共有される秘密鍵をe
各ユーザーが持つ秘密鍵eのシェアを ${β_i}$
各ユーザーが公開する自身の多項式の定数を使って計算した各点を ${b_{im}G}$ （0 ≦ m ≦ t-1）
公開鍵を ${R = \sum_{i=1}^{n}b_{i0}G}$

とする。

これで署名に使用するランダムな点R = eGが共有される。

手順２

続いて各ユーザーは、eの計算に使用したシークレットの各シェア ${β_{i}}$ と、共有シークレットを構成するシークレットの各シェア ${α_{i}}$ を使って以下を計算し、公開する。

${\gamma_i = β_i + h(P, R, m)α_i}$

手順3

続いて以下が成立するか検証する。

${\gamma_k G = R + \sum_{j=1}^{t-1} c_{j}k^{j} G + h(P, R, m) \bigl( P + \sum_{j=1}^{t-1} b_jk^{j} G \bigr)}$

※ cは署名に使うランダムな点Rを導出する際の多項式の定数項、bは共有シークレットを導出する際の多項式の定数項で、これらはランダムシークレットの生成プロトコル手順６で公開している。

手順４

手順３が問題なければ、検証が成功したユーザーが提供したデータのうち任意のt個の値を使って、Schnorr署名のsを計算する。

算出するSchnorr署名 s = e + h(P, R, m)xは、共有シークレットの多項式f(x)と、署名用のランダムなシークレットの多項式f'(x)が求まれば、

s = f'(0) + h(P, R, m) f(0) = e + (P, R, m)x

が求まるので、t個の ${γ_k}$ を集めて、ラグランジュの補間公式を使えば、Schnorrの署名値sに必要なデータを復元できる。

計算例

実際に計算してみる。↑のランダムシークレット生成の計算例で使った各ユーザーの２つの多項式を、シークレットの多項式と署名に使うランダムなシークレットの多項式とする。

まず各ユーザーはシークレットと署名用のシークレットを使って以下のγを計算し、公開する。

アリスが公開する
- γ11 = 7 + h(P, R, m)7
- γ12 = 9 + h(P, R, m)11
ボブが公開する
- γ21 = 8 + h(P, R, m)8
- γ22 = 13+ h(P, R, m)9
キャロルが公開する
- γ31 = 17 + h(P, R, m)9
- γ32 = 26 + h(P, R, m)16

公開された値が正しいか手順３の検証を行う。

例えばγ2Gを計算する場合、γ2Gは各ユーザーが公開したγ2を集約して

γ２ = 9 + h(P, R, m)11 + 13+ h(P, R, m)9 + 26 + h(P, R, m)16 = 48 + h(P, R, m)36
γ2G = （48 + h(P, R, m)36）G

となる。これに対して、

${R + \sum_{j=1}^{2-1} c_{j}2^{j} G + h(P, R, m) \bigl( P + \sum_{j=1}^{2-1} b_j2^{j} G \bigr)}$

を計算すると

16G + 2(2 + 5 + 9)G + h(P, R, m)(12G + 2(4 + 1 + 7)G) = 16G + 32G + h(P, R, m)(12G + 24G)
= （48 + h(P, R, m)36）G

となり、γ2Gと一致することが分かる。

最後に署名の作成。手順2で各ユーザーが公開したγの値を使って署名に必要なデータを計算する。γ1とγ2はそれぞれ

γ1 = 7 + h(P, R, m)7 + 8 + h(P, R, m)8 + 17 + h(P, R, m)9
= 32 + h(P, R, m) 24

γ2 = 9 + h(P, R, m)11 + 13+ h(P, R, m)9 + 26 + h(P, R, m)16
= 48 + h(P, R, m) 36

となるので、これをラグランジュの補間公式に当てはめる。今回は閾値は2なので

${f(x) = y_1 \frac{x - x_2}{x_1 - x_2} + y_2 \frac{x - x_1}{x_2 - x_1}}$

を適用すればいいので、(1, γ1)、（2, γ2）を適用すると

${f(x) = (32 + h(P, R, m) 24) \frac{x - 2}{1-2} + (48 + h(P, R, m) 36) \frac{x - 1}{2 - 1}}$ ${f(x) = (16 + 12 h(P, R, m))x + 16 + 12 h(P, R, m)}$

となり、f(0) = 16 + 12 h(P, R, m)。

共有シークレットxは12、署名に使用するeは16であることから、これがそのままSchnorrの署名値sとなる。

というのが論文で紹介されてたm-of-nのマルチシグスキーム。長かった。。

という風に、Schnorr署名単体では閾値署名を生成する特性はないが、秘密分散と組み合わせてm-of-nの閾値署名を生成することができる。ただ、参加者同士での対話や検証が多いので、実装しようとすると結構面倒ではある。。

Bitcoin向けのSchnorrのm-of-nのマルチシグの実現方法としては、こういった暗号技術のみを使用する方法以外にも、↓みたいに公開鍵の組み合わせでマークルツリーを構成してn-of-mのマルチシグを評価するアイディアなんかも紹介されている。

medium.com

*1:シークレットを分割してできた各断片

2018-08-16

Bitcoinのトランザクション伝播時の匿名性を強化するDandelionについて定義したBIP-156

Bitcoin BIP

Bitcoin Coreなどのノードがトランザクションをリレーする際、ノードは接続中のピアに対して一斉にトランザクションを送信する訳ではなく、接続中の各ピア毎に指数関数的な遅延時間をもって各ピアにトランザクションを送信するようになっている。これによりトランザクションを作成したノードを判定しにくくし、プライバシーを向上させるのが狙いだ。

ただBitcoinネットワークのノード数は10,000ノードくらいなので、安価に大量のスパイノードを配置して、送信されるトランザクションメッセージの対称性を観測することで、トランザクションをブロードキャストしたソースノードを推論することができるとして、もっとプライバシーを向上させようと、新しくDandelionというトランザクション伝播プロトコルがBIP-156として提案された↓

https://github.com/bitcoin/bips/blob/master/bip-0156.mediawiki

なお、Bitcoin CoreではDandelionの採用とは別に、各ネットワークブロック（IPブロック）毎にランダムな遅延時間を設定することで、分析コストを上げてよりプライバシーを向上させようという提案がマージされ↓、0.17.0で導入される見込みなので、CoreでDandelionが採用されるかどうかは未定。

github.com

具体的なDandelionのBIPの仕様について見てみる↓

概要

Bitcoinのトランザクション拡散プロトコルは、匿名性を奪う攻撃に対して脆弱だ。Dandelionはこれらの攻撃に対して正式な匿名性保証を提供するトランザクションルーティングメカニズムだ。Dandelionを使わずにノードがトランザクションを生成すると、ノードは接指数関数的な遅延をさせつつ接続中のピアに個別にトランザクションを送信する。Diffusionとして知られるこのアプローチは、ネットワーク内の敵対者がトランザクションをIPアドレスにリンクすることを可能にする。

Dandelionは拡散前にランダムに選択されたパスを介してトランザクションを送信することで、この種の攻撃を緩和する。トランザクションは「stemフェーズ」中にこのパスに沿って移動し、その後の「fluffフェーズ」で拡散される（stem=幹、fluff=綿毛なのでDandelion＝たんぽぽ）。このルーティング・プロトコルは追加の暗号メカニズムを導入することなく、最適な匿名性保証を提供する。

動機

Bitcoinのトランザクション拡散は、匿名性を奪う攻撃に対して脆弱だ。トランザクションはピア毎に個別に指数関数的な遅延をもって送信されるため、メッセージは統計的に対称な方法でネットワーク全体に広がる。このパターンはスパイノードと結託してトランザクションソースを推論することを可能にする。この対称性を破ることで攻撃を防ぐ。しかし、我々は対称性の破壊が適切に行われない場合、ネットワークトポロジーの知識を持つ敵がより効果的な指紋攻撃を開始できることが分かった。

P2Pグラフにアクセスできるボットネット型の敵を考えてみよう。BitcoinのP2Pネットワークに匹敵するサイズのボットネットは一般的に安価で、これらの敵はプローブメッセージでネットワーク構造を知ることができる。このような敵は、各ノード毎に10以下のトランザクションを観察した後、ネットワーク全体の完全な非匿名化を達成できることが分かった。

Dandelionは、Bitcoinネットワークの正式な匿名性の保証を提供する実用的で軽量なプライバシーソリューションだ。他のプライバシーソリューションは個々のユーザーを保護することを目的としているが、Dandelionは敵対者がネットワーク全体を非匿名化することを制限することで、匿名性を保護する。

Dandelionはどのように動作するのか？

Dandelionはトランザクションをネットワークに拡散する前に、「anonymityフェーズ」を介してトランザクションを送信することでユーザーのプライバシーを強化する。高レベルでは、

拡散の対称性の破壊
同じパスに沿って異なるソースからのメッセージを転送することによりトランザクションをミキシング

することで、プライバシーを強化する。

Dandelionのルーティングは３つのフェーズで概念化される。最初にプライバシーグラフが構築される。実際に、このプライバシーグラフは完全に分散された方法で構築され、既存のBitcoinのP2Pネットワークのサブグラフになる。次に、stemフェーズ中にこのプライバシーグラフに沿ってトランザクションが転送される。最後にメッセージはfluffフェーズで、拡散の典型的な方法でネットワークにブロードキャストされる。

分散型でプライバシーグラフを選択するために、各ノードはそのアウトバウンドピアのサブセットをDandelionの宛先に選択する。インバウンドの接続を介してこのノードに届くDandelionトランザクション（stemフェーズ中のトランザクション）は、これらDandelionの宛先に転送される。

理想的な設定では、ハミルトン閉路がほぼ最適なプライバシー保証を提供することが分かった。しかし分散型のBitcoinのP2Pネットワークを介してトラストレスな方法でハミルトン閉路を構築するのは不可能だ。そのため、各ノードはアウトバウンドピアのリストから置換することなく、ランダムに一様に2つのDandelionの宛先を選択することを推奨する。我々のテストでは、この方法が堅牢性の向上と同等のプライバシーを提供することが分かった。

stemフェーズのルーティングの際、プライバシーを保護するためにどのようにルーティングするかという問題がある。例えば2つのDandelionトランザクションが異なるインバウンドピアからノードに届いた場合、どのDandelionの宛先にこれらのトランザクションを送信すべきだろうか？我々はいくつかの選択肢が他の選択肢よりずっと優れていることに気づいた。

各Dandelionのトランザクションが、ランダムに一様に選択されたDandelionの宛先に転送される場合を考えてみよう。このアプローチの結果、指紋攻撃が発生し、ネットワークレベルのボットネット攻撃者がノードあたり10件未満のトランザクションを観察した後、P2Pネットワークの完全な非匿名化を達成できるようになる。

指紋攻撃の間に、グラフ構造の知識を持つボットネット形式の敵対者は最初にトランザクションの伝搬をシミュレートする。このオフラインステップにより、敵対者は各ネットワークノードの指紋を生成することができる。オンライン攻撃中、敵対者はスパイノードでトランザクションを収集し、これらの観測結果をシミュレートした指紋と一致させる。我々のシミュレーションでは、この攻撃がネットワーク全体の匿名化を壊滅させると示されている。

この問題を回避するには、インバウンドエッジ毎のルーティングを推奨する。各インバウンドピアには、特定のDandelionの宛先が割り当てられる。このピアを介して届いたDandelionトランザクションは同じDandelionの宛先に転送される。インバウンドエッジ毎のルーティングは攻撃者が有用な指紋を構築する能力をブロックすることで、攻撃を破る。指紋はルーティングの決定が各ノードでトランザクション毎に独立して行われる際に発生する。この場合、同じノードからの2つのトランザクションは通常ネットワークの異なる経路をとる。重要なのは、指紋と一致するような複数、単一のデータポイントが得られることだ。

Dandelionでは、同じノードからの２つのトランザクションは同じネットワーク経路を取るようにし、Figure 3の左端に敵対者を限定する。言い換えると、敵対者の知識は、複数のトランザクション経路の豊富なプロファイルではなく、1つの観察されたメッセージに限定される。Dandelionはまた拡散の対称性を破壊し、トランザクションソースの推測を困難にする。

トランザクションはDandelionのstemフェーズでランダム数ホップした後、ルーティングのfluffフェーズに移行する。トランザクションは既存の拡散プロセスを通じてネットワークに共有される。実際には、fluffの仕組みは各ノードでコインフリップの重み付けで強制される。ランダム値がある閾値を下回る場合、Dandelionトランザクションは典型的なトランザクションに変換される。我々のテストでは、あるノードを離れる際、特定のDandelionトランザクションがfluffフェーズに入る確率を10%と選択した。この値はstemの経路長とトランザクション拡散のレイテンシーとの間で良好なバランスを取る。

Dandelionの予測精度保証は集団レベルのメトリックだが、期待リコール保証は個人レベルのメトリックとして解釈できる。期待リコールは、敵対者が単一のトランザクションを所与のソースに関連付ける確率に相当する。これらの保証は確率的だ。彼らは、ノードが他のノードによって覆い隠されたシナリオ、またはISPのような敵対者によってノードが具体的にターゲットにされているシナリオに対処していない。非匿名化のターゲットとされるのを心配する個人は、Torを使用する必要がある。

高いレベルでは、DandelionはBitcoinのプライバシーの課題を意識していないようなユーザーを含む、一般の人々のための匿名性の注入のようなものだ。Torを使っていないユーザーにも、採用が増えると大きなメリットがもたらされる。Dandelionの早期採用者は、プライバシー上の利益を得ている。隣接するノード群がDandelionをサポートしない最悪の場合、トランザクションはDiffusion前に1ホップを作成する。ルーティングにのみ基づくソリューションは、オリジナルのDandelionペーパーに示されている精度とリコールに関する基本的な下限のため、完全に匿名にすることはできない。Dandelionはそのようなソリューションの中で最適な匿名性保証を提供する。

仕様

Dandelionは以下のいくつかの機能で定義される。

Dandelionトランザクションサポート
Dandelionルーティングデータとロジック
定期的なDandelionルートシャッフル
メモリプールロジック
fluffメカニズム
トランザクションの停止
Dandelionトランザクションロジック

仕様の詳細について以下にまとめる。

Dandelionトランザクションサポート

stemフェーズ中、トランザクションはDandelionトランザクションとなる。Dandelionトランザクションがfluffフェーズに入ると、トランザクションはBitcoinの通常のトランザクションとなる。Dandelionトランザクションと通常のBitcoinトランザクションとの違いは、NetMsgTypeのみ。

stemフェーズのDandelionトランザクションは通常のBitcoinトランザクションと区別できなければならない。

Dandelionルーティングデータとロジック

stemフェーズ中のDandelionのルーティングでは、インバウンドピア、アウトバウンドピア、Dandelion宛先、Dandelionルートという4つの概念がある。インバウンドピアはピアが接続を開始してから現在接続されている全てのピアで構成される。アウトバウンドピアは、このノードによって現在接続されている全てのピアで構成される。Dandelionの宛先はアウトバウンドピアのサブセットである。Dandelion宛先の数は、DANDELION_MAX_DESTINATIONSパラメータによって制限される。参照実装ではこの値は2に設定されている。我々のテストでは、この値がプライバシーと堅牢性の両方を提供することを示している（パラメータのトレードオフに関する詳細は参考文献を参照）。Dandelionルートは、Dandelion宛先へのインバウンドピアのマップだ。各インバウンドピアはDandelion宛先にマッピングされている。

Dandelionノードは、プライバシーグラフから分割することなく異なるDANDELION_MAX_DESTINATIONSパラメータを選択できることに注意すること。Dandelionルートのインバウンド接続をアウトバウンド接続にマッピングする際は、次のルーティングロジックを実装する。最初に、アウトバウンドピアのセットからDandelionの宛先のセットを選択する。このDandelionの宛先のセットのサイズは、DANDELION_MAX_DESTINATIONS以下である。インバウンド接続毎に、最小数のルートを持つDandelion宛先のサブセットを最初に識別する。例えば、Dandelion宛先の一部がゼロルートに属し、他の全てのDandelion宛先は１以上のルートに属する。このサブセットの中から一様にランダムに１つのDandelion宛先を選択する。インバウンド接続からこのDandelion宛先へのDandelionルートを確立する。

あるDandelionルートエポックでは、２つの個別のDandelion宛先を、アウトバウンド接続のセットから一様にランダムに選択する必要がある。特定のインバウンド接続から受信した全てのDandelionトランザクションは、同じDandelion宛先に送信する必要がある。特定のインバウンド接続に対してDandelion宛先を選択する際は、最小のインバウンド接続がそれらにマップされているDandelion宛先のセットから一様にランダムに選択しなければならない。

定期的なDandelionルートシャッフル

Dandelionルートのマップは、平均10分毎にクリアされ再構築される。我々は敵がプライバシーグラフを学習するのを困難にするため、経験的に10分という時間を選択した。Dandelionノードは、プライバシーグラフを分割することなく、異なる平均シャッフル時間を選択できることを注意すること。embargoes

Dandelionルートは、ランダムな間隔でクリアし再構築しなければならない。Dandelionルートは平均１０分毎にクリアして再構築する必要がある。

メモリプールロジック

Dandelionトランザクションは、一般的なトランザクションとは区別される。ただメモリプールは変更されない。stempoolと呼ばれるCTxMemPoolの別のインスタンスが、Dandelionトランザクションに使用される。適切なトランザクション伝播を保証するため、情報がmempoolからstempoolへ流れる。Dandelionトランザクションが通常のトランザクションに流入しない限り、情報がstempoolからmempoolに流れることはない。

Dandelionトランザクションが届くと、そのトランザクションはstempoolに追加され、mempoolに追加されてはならない。一般的なトランザクションが届くと、そのトランザクションはmempoolに追加され、stempoolにも追加されなければならない。Dandelionトランザクションがfluffに入ると、そのトランザクションはmempoolに追加しなければならない。

fluffメカニズム

DandelionルートにDandelionトランザクションを中継すると、Dandelionトランザクションは10%の確率で通常のBitcoinトランザクションになり、Diffusionで中継される。我々のテストでは、この値はstemのパス長とトランザクション拡散レイテンシー間で良好なバランスを保っている。Dandelionノードは、プライバシーグラフを分割することなく異なる確率を選択できることに注意すること。

ノードがDandelionトランザクションの送信を準備する際、偏ったコインフリップをしなければならない。コインフリップの結果がDandelionトランザクションの場合、ノードはトランザクションを適切なDandelion宛先に送信する必要がある。結果がDandelionトランザクションでない場合は、Dandelionトランザクションを通常のBitcoinトランザクションに変換する必要がある。Dandelionトランザクションは10%の確率で通常のBitcoinトランザクションに変換されるはずだ。

トランザクションの停止

stemフェーズ中、トランザクションは単一のパスに沿って中継される。このパスの任意のノードがDandelionトランザクションを受信してオフラインになると、そのトランザクションの伝播は停止する。堅牢性を高めるため、Dandelionトランザクションを転送する全てのノードは受信時にタイマーを初期化する。タイマーが終了するまでにDandelionトランザクションがメモリプールに現れない場合、トランザクションはfluffフェーズに入り、Diffusionで転送される。

Dandelionトランザクションを受信すると、ノードは将来のランダムな時間を停止タイマーとしてセットしなければならない。Dandelionトランザクションが通常のBitcoinトランザクションとして届いた場合、ノードはタイマーをキャンセルする必要がある。Dandelionトランザクションがタイマーが切れる前に通常のBitcoinとして観測されたら、ノードはDandelionをfluffで処理する。

Dandelionトランザクションロジック

以下のケースは、Dandelionトランザクションを参照するネットワークパケットを受信した際のノード振る舞いを定義している。

Dandelion TxのINVを受信した場合
ピアがインバウンドで、そのピアからDandelionトランザクションを受信していない場合、GETDATAで応答する。
Dandelion TxのGETDATAを受信した場合
ピアがインバウンドではなく、Dandelionトランザクションがこのピアに配信されている場合、Dandelionトランザクションで応答する。
Dandelion Txを受信した場合
ピアがインバウンドの場合、Dandelion Txを適切なDandelion宛先に中継する。

実装

参照実装は以下から入手可能。

github.com

全ての機能は以下のURLの単一のコミットに圧縮されている。

https://github.com/dandelion-org/bitcoin/tree/dandelion

互換性

DandelionはBitcoinの既存バージョンと競合しない。DandelionをサポートするBitcoinノードは、古いソフトウェアバージョンを実行するBitcoinノードと同様に見える。DandelionをサポートするBitcoinノードは、プローブメッセージを介して機能サポートを識別することができる。明らかに古いノードはDandelionルーティングの互換性はない。DandelionをサポートするBitcoinノードでも、接続先にDandelionをサポートするピアがない場合、Dandelionトランザクションの停止により、自然とDandelionサポートのないBitcoinノードの動作になる。

動機

使用例

仕様

参照実装

後方互換性

鍵生成フェーズ

セットアップフェーズ

ロックフェーズ

（送信者）と（中間者）

（中間者）と（受信者）

リリースフェーズ

鍵生成フェーズ

セットアップフェーズ

ロックフェーズ

（送信者）と（中間者）

（中間者）と（受信者）

リリースフェーズ

前提技術

シャミアの(t, n)閾値法

秘密分散のシェアの作成

シェアからシークレットを復元

ペダーセンの検証可能な秘密分散法

ディーラーによるシェアの作成

各ユーザーの検証

ランダムシークレットの生成

計算例

Schnorr署名

(t, n)閾値署名方式

鍵生成プロトコル

署名発行プロトコル

手順１

手順２

手順3

手順４

計算例

概要

動機

Dandelionはどのように動作するのか？

仕様

Dandelionトランザクションサポート

Dandelionルーティングデータとロジック

定期的なDandelionルートシャッフル

メモリプールロジック

fluffメカニズム

トランザクションの停止

Dandelionトランザクションロジック

実装

互換性

${U_0}$ （送信者）と ${U_1}$ （中間者）

${U_1}$ （中間者）と ${U_2}$ （受信者）

${U_0}$ （送信者）と ${U_1}$ （中間者）

${U_1}$ （中間者）と ${U_2}$ （受信者）