Develop with pleasure!

福岡でCloudとかBlockchainとか。

Bulletproofsを利用したrange proofの仕組み

techmedia-think.hatenablog.com

↑でBulletproofsの基本となる内積の証明の仕組みについて書いたので、今回はこれがCTやMimblewimbleなどで必要とされるrange proofにどう適用されるのか見ていく。

range proofとは?

CTと同様Mimblewimbleなどでもコインの量を秘匿するのに以下のような楕円曲線を利用したPedersen Commitmentが採用されている。

C = xG + aH

xはBlinding Factor(MWでは秘密鍵に該当)で、aがコインの量。コインの量をこのようなコミットメントCにすることで、外部からaの値を分からなくしている。具体的な仕組みが知りたい場合は、以前撮影したMWのGBEC動画を参照↓

goblockchain.network

このようなPedersen Commitmentを使ってコインの量を秘匿する場合には、コインの量aが決められた正の範囲(0〜264など)にありマイナスやオーバーフローをしていないことを証明する(マイナスやオーバーフローしているとコインのインフレーション(生成)が可能になる)range proofが必要になる。

CTの初期の提案では、このrange proofにBorromean Ring Signatureを使用するものになっていた。ただしこの証明のサイズの大きさ(数百バイトのTxに対してrange proofのサイズが2.xKBなど)がCT導入のハードルとなっていた。この問題を解消するために提案されたのがBulletproofだ。

Bulletproofを利用したrange proof

Bulletproofを利用したrange proofプロトコルを表す図が↓

f:id:techmedia-think:20200108100156p:plain

ぱっと見ても???なので、具体的にどういうことをやっているのか見ていこう。

range proofの内積表現

図の左上にあるように、range proofで証明したいのはある値vが0 ≦ v < 2nの範囲内にあること。例えばn = 4で、v = 5の場合、5が0〜24-1の範囲内にあることを証明する。

証明者は最初にランダムな値γを選択し、値vへのコミットメントを作成する(CTやMWのアウトプットに相当)。

 {V = γ\tilde{B} + vB}

vがある範囲内にあることを証明する場合、図の左上の2番めの枠のようにvは以下の2つのベクトルの内積として表現することができる。

  • vのビット表現 {a_L \in {0, 1}^{n}}。v = 5の場合は {a_L = (0, 1, 0, 1)}というベクトル
  • 2nのベクトル。つまり {(2^{n-1}, 2^{n-2}, ..., 2^{0})}というベクトル

この2つのベクトルの内積は、 {<a_L, 2^{n}> = v}になる。(n = 4で、v = 5の場合、 {2^{3}・0 + 2^{2}・1 + 2^{1}・0 + 2^{0}・1 = 5}

このような内積を使った表現をした場合、証明するステートメントは↓

  1. 2つのベクトルの内積が値vであること( {<a_L, 2^{n}> = v})。
  2.  {a_L}のベクトルの各値が0か1であること。 {a_L}の各要素から1を引いたベクトルを {a_R = a_L - 1}とすると、この2つのベクトルの各要素を乗算した結果のベクトルの要素は全て0になること {a_L \circ a_R = 0^{n}}。また、 {(a_L - 1) - a_R = 0}

これが図の左上の部分。

ステートメントの結合とBlinding Factorを使った内積のブラインド

続いて、↑の1と2のステートメントをチャレンジスカラーを使って結合し、Blinding Factorを追加する。

  • まずその前に、証明者が {a_L}を直接公開しては意味がないので(値を公表することになる)、range proofを作成する証明者は、↑の実質vの値を指す  {a_L}へのコミットするVector Commitmentを作成する。このVector Commitment Aはランダムな値αを選択し、 {A = α\tilde{B} + a_LG + a_RH}を計算することで作られる。
  • さらに、2つのブラインドベクトル {s_L, s_R}を選択し、同様にランダムな値pを選択して {s_L, s_R}へコミットするVector Commitment  {S = p\tilde{B} + s_LG + s_RH}を計算する。
  • 証明者は、検証者にこのAとSを送信する。
  • AとSを受け取った検証者はチャレンジとしてランダムな値yzを選択し、証明者に送る。

この検証者が選択したyを使って、 内積<0n, yn> = 0であるため、上記の1と2のステートメントは暗黙的に以下のように表現できる。

  •  {<a_L, 2^{n}> = v}
  •  {<a_L - 1 - a_R, y^{n}> = 0}
  •  {<a_L, a_R \circ y^{n}> = 0}

さらに検証者が選択したzを使って、上記3つのステートメントを1つのステートメントに結合できる↓

 {z^{2}v = z^{2}<a_L, 2^{n}> + z<a_L - 1 - a_R, y^{n}> + <a_L, a_R \circ y^{n}>}

このステートメントをより単純な項を持つように分割し、再配置する↓

 {z^{2}v =  z^{2}<a_L, 2^{n}> + z<a_L, y^{n}> - z<a_R, y^{n}> - z<1, y^{n}> + <a_L, a_R \circ y^{n}>}  {z^{2}v + z<1, y^{n}> = z^{2}<a_L, 2^{n}> + z<a_L, y^{n}> -z<1, a_R \circ y^{n}> +<a_L, a_R \circ y^{n}> }  {z^{2}v + z<1, y^{n}> = <a_L, z^{2}2^{n}> + <a_L, zy^{n}> + <-z1, a_R \circ y^{n}> +<a_L, a_R \circ y^{n}>}  {z^{2}v + z<1, y^{n}> = <a_L, z^{2}2^{n} + zy^{n} + a_R \circ y^{n}> + <-z1, a_R \circ y^{n}>}

右辺を結合するため、両辺に {<-z1, z^{2}2^{n} + zy^{n}>}を加算し、単純化すると↓

 {z^{2}v + z<1, y^{n}> - <z1, z^{2}2^{n} + zy^{n}> = <a_L, z^{2}2^{n} + zy^{n} + a_R \circ y^{n}> + <-z1, z^{2}2^{n} + zy^{n} + a_R \circ y^{n}>}  {z^{2}v + (z - z^{2})<1, y^{n}> - z^{3}<1, 2^{n}> = <a_L - z1, z^{2}2^{n} + zy^{n} + a_R \circ y^{n}>}

そこから内積以外の秘密の値でない項を以下のように定義すると↓

 {δ(y, z) = (z - z^{2})<1, y^{n}> - z^{3}<1, 2^{n}>)}

(この値は検証者が提供したyとzを使って簡単に計算できる。)これを適用した最終的なステートメントは、

 {z^{2}v + δ(y, z) = <a_L - z1, y^{n} \circ (a_R + z1) + z^{2}2^{n}>}

となる。この式の右辺の内積は、左の要素に {a_L}を持ち、右の要素に {a_R}を持つ。そしてこの式の各パーツを以下のように定義する。

  •  {l(x) = a_L - z1}
  •  {r(x) = y^{n} \circ (a_R + z1) + z^{2}2^{n}}
  •  {z^{2}v + δ(y, z) = <l(x), r(x)>}

ただこの段階ではl(x)とr(x)はブラインドされていない。つまり、このステートメントを証明する際にl(x)とr(x)の情報をそのまま送るとvの値が検証者に分かってしまうので、↑で選択したブラインドファクター {s_L, s_R}を使用して、l(x)とr(x)を以下のようなブラインド多項式にする。

  •  {l(x) = a_L + s_Lx - z1} = l_0 + l_1x
  •  {r(x) = y^{n} \circ (a_R + s_Rx + z1) + z^{2}2^{n} = r_0 + r_1x}

 {a_L, a_R}がそれぞれ {a_L + s_Lx, a_R + s_Rx}に置き換わっただけ。 {l_0 + l_1x} {r_0 + r_1x}はxの多項式として表現した場合の式で、 {l_0, r_0}はxの多項式の次数0の項を、 {l_1, r_1}は次数1の項をそれぞれ表している。ここでブラインドファクター {s_L, s_R}に対してのみxが乗算されているため、 {l_0, r_0}がブラインドされていない内積の左右の要素となる。つまり、

 {<l_0, r_0> = z^{2}v + δ(y, z)}

である。このような式変形をすると以下のような多項式表現ができる↓

 {t(x) = <l(x), r(x)> = t_0 + t_1x + t_2x^{2}}

この多項式の各項( {t_0, t_1, t_2})はKaratsuba法を使うと以下のように表現できる↓

  •  {t_0 = <l_0, r_0>}
  •  {t_2 = <l_1, r_1>}
  •  {t_1 = <l_0 + l_1, r_0 + r_1> - t_0 - t_2}

ここで {t_0 =  <l_0, r_0> = <a_L - z1, y^{n} \circ (a_R + z1) + z^{2}2^{n}>}であるので、証明者が検証者にアンブラインドした内積の式が成立することを証明するためには、t(x)の定数項 {t_0} {z^{2}v + δ(y, z)}であることと、t(x)が正しい多項式であることを証明すればいい。

ここまでが図の真ん中上部の緑の枠の部分(長かった。。)。

 {t_0}の正しさの証明

続いて、↑の {t_0 = z^{2}v + δ(y, z)}であることを証明する。

まず証明者はt(x)の係数へのコミットメントを作成し、チャレンジポイントxを使って多項式を評価することで、コミットメントが正しいt(x)へのコミットメントであることを検証者に証明する。

vに対するコミットメントVは既に作ってあり、それが {t_0}へのコミットメントにもなるので、新たに {t_1, t_2}へのコミットメント {T_1, T_2}を作成し、検証者に送信する。この時 {V, T_1, T_2}には以下の関係がある。

t(x)をPedersen Commitmentにマッピングするのに、点Bを使用してまず値へのコミットメントを作る。

 {t(x)B = z^{2}vB +δ(y, z)B + xt_1B + x^{2}t_2B }

続いて、別の点 {\tilde{B}}を使ってブラインドファクターとなる部分を作る。

 {\tilde{t}(x)\tilde{B} = z^{2}\tilde{v}\tilde{B} + 0\tilde{B} + x\tilde{t_1}\tilde{B} + x^{2}\tilde{t_2}\tilde{B}}

ここで {\tilde{v}, \tilde{t_1}, \tilde{t_2}}はそれぞれ {v, t_1, t_2}のブラインドファクター。そして {t(x)B} {\tilde{t}(x)\tilde{B}}を加算してt(x)のPedersen Commitmentが作成できる↓

 {t(x)B + \tilde{t}(x)\tilde{B} = z^{2}V + δ(y, z)B + xT_1 + x^{2}T_2}

なので検証者に送る {V, T_1, T_2}はブラインドファクターを含んでいる。

検証者にt(x)が {t(x) = z^{2}v + δ(y, z) + t_1x + t_2x^{2}}であることを納得させるために、証明者は {t(x), \tilde{t}(x)}を検証者に開示する。そして検証者は、以下が成立するか検証する。

 {t(x)B + \tilde{t}(x)\tilde{B} = z^{2}V +  δ(y, z)B + xT_1 + x^{2}T_2}

上記が成立すると、検証者は {t_0} = z^{2}v + δ(y, z)であることを納得する。

これが図の右上の部分。

t(x)が正しい多項式であることの証明

続いてt(x)が正しい多項式であること、つまりt(x) = <l(x), r(x)>であることを証明する。

証明者は既に、↑ですでに {a_L, a_R, s_L, s_R}へのコミットメント {A = α\tilde{B} + a_LG + a_RH} {S = p\tilde{B} + s_LG + s_RH}を検証者と共有している。そしてAは以下のように表現できる。

 {A = <a_L, G> + <a_R, H> + α\tilde{B} = <a_L, G> + <y^{n} \circ a_R, y^{-n} \circ H> + α\tilde{B}}

ここで、 {H' = y^{-n} \circ H}とするとl(x)とGの内積

 {<l(x), G> = <a_L, G> + x<s_L, G> + <-z1, G>}

となり、r(x)とH'の内積

 {<r(x), H'> = <a_R, H> + x<s_R, H> + <zy^{n} + z^{2}2^{n}, H'>}

となる。l(x), r(x)とコミットメントA、Sを関連付けるには、 {e\tilde{B} = α\tilde{B} + xp\tilde{B}}を使って以下を計算すると、↓

 {<l(x), G> + <r(x), H'> + e\tilde{B} =}

 {<a_L, G> + <a_R, H> + α\tilde{B} + x<s_L, G> +  x<s_R, H> + xp\tilde{B} + <-z1, G> + <zy^{n} + z^{2}2^{n}, H'>}

となり、これは

 {<l(x), G> + <r(x), H'> + e\tilde{B} = A + xS + <zy^{n} + z^{2}2^{n}, H'> - <z1, G> }

つまり

 {<l(x), G> + <r(x), H'> = -e\tilde{B} + A + xS + <zy^{n} + z^{2}2^{n}, H'> - <z1, G> }

になる。これが合成ブラインドファクターeを持つl(x)とr(x)へのVector Pedersen Commitmentとなる。ここまでが図の右下の部分。証明者が検証者にeを送ることでこのコミットメント {P = <l(x), G> + <r(x), H'>}を計算することができる。

↑の式は要素の数nのベクトルになるので、内積の証明と同様、ベクトルの要素が1つのスカラー値になるまで圧縮する。ここが図の中央の部分。

そして {P = <l(x), G> + <r(x), H'>}とt(x) = <l(x), r(x)>の関係が成立するかどうかを検証するために、Pとt(x)を入力して冒頭のBulleptproofsの内積の証明を利用する。この関係性が証明できれば結果的にrange proofの証明になる。

Bulletproofsにおける内積の証明

Bulletproofsは2017年にBünzらが発表したゼロ知識証明システムの一種で、Trusted Setupを必要とせず、プルーフが非常に短く、その集約が可能であるという特性を持っている。最初はConfidential Transactionの秘匿した値がある範囲内にあることを証明するrange proofを効率的に実現するために提案されが、range proofに限らず、一般的な算術回路向けの非対話型ゼロ知識証明プロトコルとしても提案されている。

Bulletproofsがどのような仕組みでrange proofや算術回路で動作するのか見ていく前に、Bulletproofsのベースとなる内積の証明の仕組みについて理解する。

内積の証明

Bulletproofsの重要な構成要素の1つは、2つの異なるベクトルを持つPedersen Commitmentに対してベクトルの内積を計算するアルゴリズムにある。

よくConfidential TransactionやMimblewimbleで出てくる楕円曲線Pedersen Commitmentは

C = rG + aH

という形式のコミットメントで、rがブラインドファクター、aが秘匿するコインの量として使われる。

raスカラー値だが、Bulletproofsの内積の証明では、これを拡張し、2つのベクトル {\textbf{a} = (a_0, a_1, ..., a_n)},  {\textbf{b} = (b_0, b_1, ..., b_n)}について

  •  {c = \langle \textbf{a}, \textbf{b} \rangle}
  •  {P = \langle \textbf{a}, \textbf{G} \rangle + \langle \textbf{b}, \textbf{H} \rangle}

という関係が成立するベクトルa, bの知識を知っていることをa, bを明かすことなく検証者に確信させる(太字はスカラーではなく、G,Hを含めベクトルの表記で、 {\langle \rangle}は2つのベクトルの内積の表記)。

まず↑の2つのステートメントを、GとHとは異なるジェネレータBを利用したQ = wBを使って1つの式にする。このwは検証者がランダムに選択する。cの両辺にQを乗算すると、

  •  {cQ = \langle \textbf{a}, \textbf{b} \rangle Q}

これをPの式に加算すると、

  •  {P + cQ = \langle \textbf{a}, \textbf{G} \rangle + \langle \textbf{b}, \textbf{H} \rangle +  \langle \textbf{a}, \textbf{b} \rangle Q}

シンプルにするため、P' = P + cQとすると、

  •  {P' = \langle \textbf{a}, \textbf{G} \rangle + \langle \textbf{b}, \textbf{H} \rangle +  \langle \textbf{a}, \textbf{b} \rangle Q}

というふうにシンプルにでき、このステートメントが成立することを証明する。

証明のプロセス

まず最初にベクトルを圧縮する。a, b, G, Hの要素の数をnとすると、以下の手順をk = log(n)回繰り返し、サイズを1にする。

ランダムな値xを選択し、ベクトルa, bを左右半分に分割し、半分に分割したベクトルにxおよび {x^{-1}}を乗算し、加算することでベクトルのサイズを半分にする。

f:id:techmedia-think:20200110164524j:plain

そしてa', b'に対応する新しいc'

 {c' = \langle \textbf{a'}, \textbf{b'} \rangle = \langle \textbf{a}_{lo} \cdot x + \textbf{a}_{hi} \cdot x^{-1}, \textbf{b}_{lo} \cdot x^{-1} + \textbf{b}_{hi} \cdot x \rangle}

となる。そして、c'は以下のようにも表現できる。

 {c' = \langle \textbf{a}_{lo}, \textbf{b}_{lo} \rangle + \langle \textbf{a}_{hi}, \textbf{b}_{hi} \rangle + x^{2} \cdot \langle \textbf{a}_{lo}, \textbf{b}_{hi} \rangle + x^{-2} \cdot \langle \textbf{a}_{hi}, \textbf{b}_{lo} \rangle}

ここで、 {L = \langle \textbf{a}_{lo}, \textbf{b}_{hi} \rangle} {R = \langle \textbf{a}_{hi}, \textbf{b}_{lo} \rangle}とすると、↑の式は1つまえのcを使って以下のように表現できる。

 {c' = c + x^{2} \cdot L + x^{-2} \cdot R}

各ラウンドのLとRを検証者に送り、k回ラウンドを繰り返すとベクトルa, bの要素の数は最終的に1つになるので、スカラー値となったa', b', c'を証明者に送ると、3つの値と各ラウンドのL, Rを使って逆の計算をすることでcの値を計算できる。この仕組がポイントの1つで、圧縮とその逆の計算を簡単にするためcで説明したが、実際は後述するようにP'を使った計算になる。

↑の圧縮はa, bだけでなくG, Hも同様に圧縮していく。結果、各ベクトルの次の状態は以下のように表現できる。

  •  {\textbf{a}^{k-1} = \textbf{a}_{lo} \cdot x_k + x^{-1}_k \cdot \textbf{a}_{h_i}}
  •  {\textbf{b}^{k-1} = \textbf{b}_{lo} \cdot x_k^{-1} + x_k \cdot \textbf{b}_{h_i}}
  •  {\textbf{G}^{k-1} = \textbf{G}_{lo} \cdot x_k^{-1} + x_k \cdot \textbf{G}_{h_i}}
  •  {\textbf{H}^{k-1} = \textbf{H}_{lo} \cdot x_k + x^{-1}_k \cdot \textbf{H}_{h_i}}

そしてステートメントP'についても以下のようになる。

 {P'_{k-1} = \langle \textbf{a}^{(k-1)}, \textbf{G}^{(k-1)} \rangle + \langle \textbf{b}^{(k-1)}, \textbf{H}^{(k-1)} \rangle + \langle \textbf{a}^{(k-1)}, \textbf{b}^{(k-1)} \rangle \cdot Q}

展開すると

 {P'_{k-1} = \langle \textbf{a}_{lo} \cdot x_k + x^{-1}_k \cdot \textbf{a}_{h_i},  \textbf{G}_{lo} \cdot x_k^{-1} + x_k \cdot \textbf{G}_{h_i} \rangle + }  {\langle \textbf{b}_{lo} \cdot x_k^{-1} + x_k \cdot \textbf{b}_{h_i}, \textbf{H}_{lo} \cdot x_k + x^{-1}_k \cdot \textbf{H}_{h_i} \rangle + }  {\langle \textbf{a}_{lo} \cdot x_k + x^{-1}_k \cdot \textbf{a}_{h_i}, \textbf{b}_{lo} \cdot x_k^{-1} + x_k \cdot \textbf{b}_{h_i} \rangle \cdot Q}

となるが、これは↑のcc'の関係と同じ変換を利用して、以下のように変換できる。

  •  {P'_{k-1} = P'_k + x_{k}^{2} \cdot L_k + x_{k}^{-2} \cdot R_k}
  •  {L_k = \langle \textbf{a}_{lo}, \textbf{G}_{hi} \rangle + \langle \textbf{b}_{hi}, \textbf{H}_{lo} \rangle + \langle \textbf{a}_{lo}, \textbf{b}_{hi} \rangle \cdot Q}
  •  {R_k = \langle \textbf{a}_{hi}, \textbf{G}_{lo} \rangle + \langle \textbf{b}_{lo}, \textbf{H}_{hi} \rangle + \langle \textbf{a}_{hi}, \textbf{b}_{lo} \rangle \cdot Q}

各ベクトルの要素数が1になるまで圧縮を繰り返すとP'は最終的に

 {P'_{0} = a^{(0)}_0G^{(0)} + b^{(0)}_0H^{(0)} + a^{(0)}_0b^{(0)}_0Q}

で、これは各ラウンドのLとRとxの値を使うと以下の式になる。

 {P'_{0} = P'_{k} + \sum^{k}_{j=1}(L_{j}x^{2}_j + x^{-2}_{j}R_{j})}

P'を元のPに置き換えると式は以下のように変形できる。

 {P + cwB = a^{(0)}_0G^{(0)} + b^{(0)}_0H^{(0)} + a^{(0)}_0b^{(0)}_0wB - \sum^{k}_{j=1}(L_{j}x^{2}_j + x^{-2}_{j}R_{j})}

ここまでの要素が揃うと以下の検証ができる。

  • 検証者は証明者から受け取った {P'_0}の構成要素であるスカラー {a^{(0)}_0, b^{(0)}_0}と各ラウンドのL, Rを使って、圧縮ラウンドの逆の計算をすることで算出した値が元のP'と合致するか検証し、合致すればスカラー {a^{(0)}_0, b^{(0)}_0}が正しいことを検証できる。
  • 検証者は {a^{(0)}_0, b^{(0)}_0}と各ラウンドのL, Rを使って↑のP + cwBの等式が成立するか直接検証することができる。 {a^{(0)}_0, b^{(0)}_0}がPを構成する式とcwBでcの式の両方に展開されるので、これをもって、Pとcの関係性の証明になる。

この検証をすることで、検証者はステートメント  {P' = \langle \textbf{a}, \textbf{G} \rangle + \langle \textbf{b}, \textbf{H} \rangle +  \langle \textbf{a}, \textbf{b} \rangle Q}が成立することをベクトルa, bの値を知ることなく確認することができる。これがBulletproofsの内積の証明の仕組み。

ちなみに↑は証明者と検証者による対話が必要な形で記載しているが、これはFiat-Shamir変換により非対話型にすることができる。

このBulletproofsによる内積の証明ができると何が嬉しいの?と思うかもしれないが、これを冒頭で言ったようにCTやMimblewimbleで使われるrange proofの証明に利用できる。ある値が0〜2nの範囲内にあるというステートメント内積で表現できるからだ。具体的なプロトコルについてはまた別の記事で解説したい。

チェーン上で異なるコンセンサスの実行を可能にする拡張方法「Extension Block」

最近、LitecoinがMimblewimbleを導入するLIP(Litecoin版BIP)が提案された↓

Litecoinは元々Bitcoinアルトコインであるため、根本的にブロックチェーンの構造が異なるMimblewimbleを導入するのはBitcoin同様難しい。そこでLitecoinがMimblewimbleを導入するために採った方法がExtension Blockという拡張方法だ。

Auxiliary Block

Extension Blockのアイディアはもともと、2013年にJohnson Lauがハードフォークを必要とせずブロックサイズを増やす方法として提案したものだ↓

https://bitcointalk.org/index.php?topic=283746.0

提案された1MBのブロックサイズを増やすAuxiliary Blockの仕組みは、

  1. 各ブロック毎にメインのブロックとは別にAuxiliary Blockが作成される。Auxiliary Blockヘッダーを持たないブロック。
  2. OP_NOP1をOP_AUXとして再定義する。
  3. 誰かがBitcoin<serialized script> OP_AUXというscriptPubkey宛に送金するまでAuxiliary Blockは空のまま。この形式のscriptPubkeyが現れると、Auxiliary Blockにコインベースのようなトランザクションが作成され、ロックされたBitcoinが送られる。Auxiliary Blockのマークルルートはメインブロックのコインベースに含まれる。アップグレードされたノードはBitcoinがメインチェーンから補助チェーンに正しく転送されているかどうか確認する。(なお、OP_AUXトランザクションを含まないブロックではAuxiliary Blockは作られない。つまりAuxiliary Blockのチェーンは形成されない)
  4. 補助チェーンでもメインチェーンと同様Bitcoinの送金ができ、マイナーもメインチェーンと同じ仕組みを使って手数料を徴収することもできる。唯一の違いは、補助チェーンにはコイン生成の報酬が無いということ。メインチェーン側で<serialized script> OP_AUXにコインを送金した場合のみ、補助チェーン上でコインが生成される。
  5. 補助チェーンからメインチェーンにコインを戻す場合は、補助チェーンのコインを<serialized script y> OP_AUX OP_RETURN形式のscriptPubkeyに送金する。マイナーはこの送金を検知し、メインチェーン上でOP_AUXのUTXOをランダムに選択し、同じコインの量だけメインチェーン内の<deserialized script>宛に送金する。

というもの。この仕組みでは以下の後方互換性が担保される:

  • 旧ノードには補助ブロックのデータが表示されないので、補助ブロックのサイズは自由に決められる。
  • OP_AUXのアウトプットは旧ノードにとって誰もが使用可能なanyone can spendなUTXOとしてみられるので、旧ノードはそのまま動作可能。
  • 上記のルールに従わずOP_AUX UTXOのコインを盗もうとしても大多数のマイナーにより上記がアクティベートされていれば、その行為は拒否される。
  • 旧ノードは作成するブロックにOP_AUXトランザクションを含めたり引き換えたりしない限り、引き続き有効なブロックをマイニングできる。

この仕組みを利用すると、ブロックサイズに限らず本来ハードフォークを必要とする変更も、ソフトフォークで実現することができる。

そしてExtension Blockとして2017年1月に実際にBitcoinへのソフトフォークとして提案されたのが↓

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-January/013490.html

LitecoinのExtension Block

Litecoinでは、LIP-0002としてMimblewimbleをLitecoinに導入するためにExtension Blockを導入する提案が出ている。この提案は、OP_AUXのようなopcodeを追加するのではなく、2017年にBitcoinで提案された内容の用に、新しいwitness versionを使った導入になる。

Peg-in

標準チェーンのコインをExtention Blockのチェーンに移動する場合、ユーザーはPeg-inトランザクションを作成する。Peg-inトランザクションは、EB側のブロックチェーンに送金したいコインを新しいwitness program宛に送金するトランザクション

新しいwitness programにコインを送金するPeg-inトランザクションが作られると、そのPeg-inトランザクションが含まれるブロックに対応するEB側のブロックにおいて、同量のコインを持つコインベーストランザクションが作られる。witness programの値はEB側のコインベーストランザクションの送金先へのコミットメントになる(Mimblewimbleの場合、witness programはEB側のコインベーストランザクションにセットされるカーネルコミットメントを指定するっぽい)。なお、対応するEBのブロックに対応すコインベーストランザクションが存在しない場合、標準チェーン上のPeg-inトランザクションは無効とみなされる。

Peg-inトランザクションにより標準チェーンからEB側のチェーンにコインが移動するので、標準チェーンでは当然移動したコインはEB側から戻ってくるまでロックされなければならない。そのため、Peg-inトランザクションで作成されたUTXOは、マイナーにより収集され、同一ブロック内に作成されるインフレーショントランザクション(後述)で使用される。

Peg-out

Peg-inとは逆にEBのチェーンから標準チェーンにコインを移動する際にはEBチェーン上でPeg-outトランザクションを作成する。Peg-outトランザクションは標準チェーン上で同量のコインの送金先であるLitecoinアドレスへコミットする。

Peg-outにより標準チェーン上で利用可能になったコインは、標準トランザクションのコインベーストランザクションのコインと同様、使用できるまで一定期間ロックされる。これはチェーンの再編成に対応するため。

インテグレーショントランザクション

標準チェーン上でEBへのPeg-in、EBからのPeg-outを処理するために作られるのがインテグレーショントランザクション。インテグレーショントランザクションはマイナーによってブロック毎に1つ作成されるトランザクションで、ブロック内の最後のトランザクションとして配置される。

インテグレーショントランザクションは、X+1個のインプットとY+1個のアウトプットを持つ。Xはブロック内のPeg-inトランザクションの数で、Yはブロック内のPeg-outトランザクションの数。

  • インプット
    • 最初のインプットは前のブロックExtAddr UTXO(後述)。
    • X個のインプットはブロック内のPeg-inトランザクションのUTXOを集めたもの。基本的に対応するEB内に同じ数のコインベーストランザクションが作られる。これらのコインは新しくEB側のチェーンに移動するコインであるため、標準チェーン上では他で使用されないようこのトランザクションでインプットとして使用される。
  • アウトプット
    • 最初のアウトプットは、このブロックにおけるEB側のコインの合計量を持つExtAddrアウトプット。インプットには前のブロックのExtAddrとこのブロックでEB側に移動したコインの合計があるので、そこからこのブロックでEB側から標準チェーンに戻ってきたコイン(このアウトプットの後に続くPeg-out分のコイン)を差し引いた量がこのブロック時点でのEB側のコインの総量になり、その総量を全てこのExtAddrにロックすることになる。
    • Y個のアウトプットは、EB側のチェーンから標準チェーンに移動してくるコインのアウトプット。このアウトプットはEB側のPeg-outトランザクションでコミットされたLitecoinアドレス宛のアウトプットになり、対応するEB側のブロック内のPeg-outトランザクションの数と同じだけのアウトプットが作成される。
ExtAddr

ExtAddrは、EB側のチェーンに移動したコインを標準チェーン側でロックしておくためのアドレスで、以下のフォーマットのscriptPubkeyになる。

ExtVer <eb_commitment>

ExtVerの値はおそらくEB毎に異なるものと思われる(例えば今回一緒に提案されているLIP-0003のMimblewimbleのEBでは「ExtVer」の値は0x09とされている)。

witness programの部分は2〜40バイトのeb_commitment。このデータは対応するEBのブロックへのコミットメントになる。LIP-0003だと、EBのブロック内のトランザクションカーネルとそのブロック時点のUTXOセットのデータから作られるコミットメントになる。

基本的に1ブロックあたりそのインテグレーショントランザクション内で1つのExtAddrが作られ、そこにEBに移動したコインの総量がロックされることになる。

EBに対応してしない旧ノードから見ると↑のscriptPubkeyは誰もが使用可能なアウトプットと認識される。

手数料

EB側の手数料は基本的にインテグレーショントランザクションの手数料として標準チェーン側で徴収される。

所感

以上が、Extension Blockを利用した拡張方法。

  • Extension Block側のチェーンの仕様は自由に決められるので(EBのブロックサイズも自由に決められるし、トランザクション構造もまったく異なる仕組みが利用できる)、既存のコンセンサスにとらわれない拡張が可能なのは大きい。
  • サイドチェーンライクでもあるけど、サイドチェーンと違って
    • Peg-in/outが単一のチェーンのコンセンサスとして担保されており、この点は重要。
    • EB側のブロック生成の手数料報酬も標準チェーンのコインとして入手できる。
  • 一方、サイドチェーンと違って単一チェーンのフルノードとしての検証コストは増える。これはフルノードの分散化への影響があるのと、経済的な観点からマイナーによる導入の支持がどうなるか?という別の課題が生まれる。EB側のチェーンの報酬は手数料収入だけなので、標準チェーンとEB側のチェーンで手数料レートが変わる可能性も考えられる。

ちなみに、↑のExtAddrを利用してブロック単位で別のコインを管理する手法は、似たようなアプローチが以前、Confidential TransactionをBitcoinにソフトフォークで導入する際にも使われており↓、設計方法の1つとして他にも利用できそう。

techmedia-think.hatenablog.com

Bitcoinにアカウント機能を導入するLayer 2プロトコル「easypaysy」

BitcoinはUTXOモデルのブロックチェーンで、コインはアカウント単位ではなくUTXO単位(アドレス単位)に管理される。また、プライバシーの観点から支払い毎に異なるアドレスを使用することを推奨している。このような支払いは、コインの送金先のリンク性のハードルを上げることになるが、そのような知識を必要とする支払いはユーザーに複雑なUXを強いることになる。

これに対し、Bitcoinの支払いにおいても、各ユーザーが一意のアカウントを作成でき、各支払いもそのアカウントに対して行えるようにしようというのがLayer 2プロトコルとして提案されたeasypaysyプロトコルだ。ホワイトペーパーは↓

https://www.easypaysy.org/assets/easypaysy_white_paper.pdf

easypaysy プロトコル

easypaysyはBitcoinにアカウントベースの支払いを可能にするLayer 2プロトコルだ。実際の支払いは今まで通り支払い毎に新しいアドレス宛に送金するトランザクションが作られる訳だが、ユーザーはそのような事を意識することなく、ウォレットで毎回相手のアカウントを指定することでそのようなトランザクションを作成し、送金の受取側もそのような送金を検知するための仕組みをサポートするようになっている。

アカウントの作成

easypaysyを使った支払いをするためには、まずeasypaysyのアカウントIDを作成する必要がある。このアカウントはメールアドレスや銀行口座のようにユーザーを識別するためのIDで、アカウントベースの支払いをする際のIDとなる。このアカウントは以下の3つの情報を持つ。

  • Identity key
    メッセージへの署名や、送金者と受取人の間で暗号化されたメッセージを交換するのに使われる公開鍵。
  • Value key
    非対話型の支払いをする際に送金先の鍵の導出に使われる公開鍵。
  • ランデブー記述子
    アカウントの所有者が受け入れる支払いのタイプと、送金者がアカウントと通信する際に使用することができるプロトコルとその方法を定義したJSONドキュメント。

easypaysyアカウントを作成するには、上記3つの情報を持つトランザクションを作成し、ブロックチェーンに記録する。具体的にどういうトランザクションを作成するかというと、

① まずIdentity keyとValue keyの2つの公開鍵を使って2-of-2のマルチシグを構成する。

2 <Identity key> <Value key> 2 OP_CHECKMULTISIG

これをP2SHアドレスに変換し、そのP2SHアドレス宛にコインを送金する。

② ↑のトランザクションがブロックに格納されたら、続いて、そのUTXOをインプットにした以下のトランザクションを作成する。

  • Input
    1. Identity keyとValu keyのマルチシグのUTXO
  • Output
    1. Identity keyとValu keyのマルチシグのUTXO(つまりインプットと同じP2SHアドレス)
    2. OP_RETURN <ランデブー記述子>

①で作成したP2SHがインプットにあるため、そのscriptSigを確認するとIdentity keyとValue keyの値が分かる。また、OP_RETURNを使ってランデブー記述子のデータを格納する。

このトランザクションブロックチェーンに記録されると、アカウントに必要な3つの情報がブロックチェーンに記録されることになる。

②のトランザクションブロックチェーンに格納され100承認されるとeasypaysyアカウントがアクティベートされる。

アカウントID

↑のようにeasypaysyアカウントがアクティベートされるとアカウントIDができる。easypaysyアカウントのIDはブロックチェーンに記録された②のトランザクションのデータから以下の形式で表現される。

btc@<ブロック高>.<ブロック内のトランザクションのindex>/checksum

ブロック高は②のトランザクションが格納されたブロックのブロック高で、.の後にそのブロック内に②のトランザクションが入っている位置が続く。

チェックサムの計算

チェックサムは以下のアルゴリズムで計算される。

  1. ②のトランザクションが格納されたブロックのハッシュとマークルルートおよび②のWTXIDを結合し、そのハッシュ値を計算する。tx_digest = sha256(block chash || merkle root || wtxid)
  2. 32バイトのtx_digestを8バイトずつの4つのデータに分割する。
    • tx_digest_0 = tx_digest[0..7]
    • tx_digest_1 = tx_digest[8..15]
    • tx_digest_2 = tx_digest[16..23]
    • tx_digest_3 = tx_digest[24..31]
  3. 各tx_digest_xを1000で割ったあまりを計算する。
    • checksum_chunk_0 = tx_digest_0 % 1000
    • checksum_chunk_1 = tx_digest_1 % 1000
    • checksum_chunk_2 = tx_digest_2 % 1000
    • checksum_chunk_3 = tx_digest_3 % 1000

こうして計算した4つのチャンクがチェックサムデータになる。つまりチェックサムの値は、000-000-000-000から999-999-999-999の乱数とみなすことができる。

アカウントIDの表現方法

アカウントIDを表現する方法は3つある。

Canonical ID

Canonical IDは↑のアカウントIDの各データをそのまま10進数で表現する方法。

例えばブロック高が#543847のブロックの636番目トランザクションの場合のCanonical IDは、btc@543847.636/577-218-376-867

チェックサムは必ずしも4つすべて表記する必要はなく、btc@543847.636/577と省略してもいい。

Mnemonic ID

Mnemonic IDは↑のアカウントIDの各データをBIP-39のニーモニックワードを使って表現する方法。

↑のCanonical IDをMnemonic IDで表現するとbtc@cancel-mind.exhibit/motion-custom-fun-sugarとなる。

Domain ID

3つめのDomain IDは、DNSを利用した表現方法で、チェックサムが付いたアカウントIDを自身のドメインのTXTレコードに挿入するというもの。DNSに対してクエリするとそのドメインに対応するアカウントIDを返すという仕組み。

ランデブー記述子

アカウント情報の1つであるランデブー記述子は、アカウントの所有者が受け入れる支払いのタイプと、送金者がアカウントと通信する際に使用することができるプロトコルとその方法を定義するもので、②のトランザクションアウトプットでOP_RETURNを利用して記録される。

実際に定義されるのは以下のようなJSONデータになる。

{
 "Document_name": "EASYPAYSY_RENDEZVOUS_DESCRIPTOR",
 "Version": "0",
 "Accepted_payments": [
   "TYPE_1_RENDEZVOUS",
   "TYPE_2_IOC_OVERT"
 ],
 "Mail": "fiber.burden.erupt@gmail.com",
 "Bitmessage": "BM-2cTZhb···NnZTjC69ke9BieU"
}
  • Document_name: easypaysyドキュメントを識別する文字列の固定のリテラル
  • Version: ランデブー記述子のバージョン
  • Accepted_payments: アカウント所有者受け入れる支払いのリスト。現在可能なのは以下の4種類で、アカウントは少なくともこのペイメントタイプの1つを受け入れる必要がある。

Bitcoinの標準トランザクションのルールとして、OP_RETURNで登録可能なデータは80バイト以内であることという制限があるため、↑のJSONをそのまま記録しようとするとサイズオーバーになる。そこでeasypaysyでは、最適化された辞書ベースの圧縮アルゴリズムを使ってJSON形式のランデブー記述子をシリアライズして記録する。この圧縮アルゴリズムを使用すると↑のサンプルは7バイトになると。

支払いタイプ

easypaysyでは以下の4種類の支払いタイプをサポートしている。

TYPE_0_UNSAFE_FIXED

TYPE_0の支払いタイプは、各支払いにおいて常に同じアドレス、具体的にはValue keyに関連付けられたアドレスを使用する必要がある。これはプライバシーの欠如にもなるため基本的に推奨されていない。

TYPE_1_RENDEZVOUS

TYPE_1は、対話型の支払いで、支払いの都度、受取人と対話して支払先のアドレスを導出する。この支払いタイプを使用する場合、ランデブー記述子に定義された連絡プロトコルhttps, メール、Bitmessage、MQTT)とそのエンドポイントに従って、支払人が受取人に連絡し、支払先のアドレスを受け取る。この時、受取人は支払先のアドレスと一緒に受取人のeasypaysyアカウントのIdentity keyでアドレスに署名した署名データも一緒に返す。この署名データから、そのアドレスが確かに受取人によって承認されたアドレスであることを証明できるため、受取人による送金の否認防止につながる。

TYPE_2_IOC_OVERT, TYPE_3_IOC_COVERT

TYPE_2とTYPE_3は両方とも非対話型の支払い。IOCはInversion Of Controlの略で制御の反転、つまり支払いプロセスの制御を反転させ、各支払の宛先アドレスを選択するのは受取人ではなく支払人であるということを意味する。このためTYPE_1と違って、支払いの都度、受取人と対話する必要はなく、ランデブー記述子にも連絡プロトコルを定義する必要はない。

ボブからアリス(Value key = A = a * G)へeasypaysyアカウントを使った非対話型の支払いをする手順は以下の通り。※ アリスのeasypaysyアカウントはすでにチェーン上に公開されているとする。

  1. ボブは支払いに使用するキーペア:B = b * Gを作成する。
  2. ボブは以下の方法でnを計算し、それを秘密鍵とした公開鍵Nを計算する。
    • n = sha256(b * A) = sha256(b * a * G)
    • N = n * G
  3. ボブは別の公開鍵Cを以下の方法で計算する。
    • C = A + N (ボブはアリスのeasysypaysyアカウントからアリスのValue key = Aを知っている)
    • C = c * G = (a + n) * G (この時点でボブはaを知らないのでcを計算できず、アリスもnを知らないのでcを計算できない)
  4. ボブはCから送金先アドレスを導出し、最低2つのアウトプットを持つ支払いトランザクションを作成する。このアウトプットの1つはC宛の支払いで、もう1つはOP_RETURNアウトプットでBのデータが含まれる。このトランザクションをブロードキャストし、アリスにWTXIDを通知する(TXIDでもいいような?)。
  5. アリスはボブから通知を受け取るか、トランザクションを監視し、4のトランザクションについて以下を行う。
    1. OP_RETURN からBを取得する。
    2. nおよびc, Cを計算する。
      • n = sha256(a * B)
      • c = a + n
      • C = c * G
  6. アリスは4のトランザクションアウトプットにC宛の送金があるか確認する。アリスはそのコインを使用するために必要な秘密鍵cをこの時点知っているので、このコインはアリスのものになる。(ボブはaを知らないのでCのコインは使えない)

また、一度支払いをしてしまえば、その後の支払いではOP_RETURNに含めるBのデータを(支払い回数をiとした場合 i || bなどで)決定論的に導出すれば、OP_RETURNアウトプットを含める必要はなくなる。

なお、OVERTとCOVERTの違いは、OP_RETURNで公開鍵を伝える際にそのプレフィックスEP(hexだと4550)を付与するかどうかという点だけ。OVERTの場合、EPが付くのでそのトランザクションIOC支払いであることが明確になり、スキャンする側の負荷が軽減する。一方COVERTの場合プレフィックスが付かないため第三者のオブザーバーがいたとしてもIOC支払いであることを確実に判断するのが困難になる。

IOC支払いの否認防止性

IOC支払いの場合、非対話型のため実際にCのコインをアリスがアンロックできることを明示的に証明することができない。対話型の場合、受信側のアドレスへの署名データがあるため、その署名データによって否認防止性が担保できる。そのため、IOC支払いの場合、公平な第三者に支払いに使ったbの値を開示することで、それがアリスの鍵から導出可能であることを証明することができる。

通信の暗号化

支払人と受取人の間の全ての通信はECIESプロトコルを使って暗号化される。このセキュリティプロトコルはアカウントのIdentity keyを使ったECDH鍵交換を利用した共有AES鍵を使って行われる。

※ 実際にIdentity keyが使わるのは最初の通信のみで、後はメッセージ内のEncrypt_answer_with_public_keyで指定した一時鍵が使われる。

アカウントの更新

アクティベートされたアカウント情報(ランデブー記述子)はいつでも更新することができる。②のマルチシグのUTXOを使用するトランザクションを作成し、そのトランザクションアウトプットに更新したランデブー記述子を定義する(もう1つのトランザクションアウトプットは同じマルチシグのP2SH)。

アカウントの削除

アカウントを削除する場合は、アカウントのマルチシグのUTXOを、全く異なるアドレス宛に送金するだけ。

所感

  • 非対話で支払先のアドレスを導出するプロトコルは今までもステルスアドレスや、BIP-47のペイメントコードなどで提案されてきたけど、これらと違って基点となるアカウント情報もブロックチェーンで管理するというのが新しい試み。
  • Layer 2プロトコルを設計する際にランデブー記述子のようなメタデータをOP_RETURNに登録することはよくあるが、80バイト制限もあるので、OP_RETURNにはエンドポイントのみ記録して、実際の定義値はそのエンドポイントで公開するというアプローチが多い。ただその場合、エンドポイントが公開しているデータが不変であるという確証はないので、不変性を担保するのであればデータはブロックチェーン上に記録された方がいい。そういう意味で、easypaysyは専用の圧縮アルゴリズムを使って直接メタデータを記録するアプローチを取ってる。JSONである必要があるかは疑問だけど。
  • BitcoinのUXを改善するためにUTXOやそれに付随するアドレスの仕組みをできるだけエンドユーザーに意識させない方が望ましい。そういった意味ではアカウントベースの見せ方の方が向いてそう。
  • ↑の解説以外にもプル型の定期支払いの仕組みやスケーリングのための仕組みがホワイトペーパーには定義されている。

Bitcoinネットワークのトポロジーを推定するTxProbe

Scaling Bitcoin 2019復習シリーズ第三弾は、「TxProbe: Discovering Bitcoin's Network Topology Using Orphan Transactions」

TxProbeは、Bitcoinネットワークのネットワークトポロジーを推定するための方法。ここで推定するBitcoinネットワークは基本的にパブリックに到達可能なノードで構成されるネットワークで、NATやファイアウォールの背後にあり到達不可能のノードや、インバウンド接続を受け入れないノード(軽量ノードなど)は対象外となる。

Bitcoin Coreはデフォルトで8つのアウトバウンド接続を作成する。この時選択される接続先のピアはランダムに選択されるが、/16 (ipv4)ネットワークセグメントが重複しない形で選ばれる。またこの他にインバウンド接続を受け入れる。

到達可能なノードについては、Bitnodesなどのサイトで確認できる。Bitnodesでは、getaddr/addrメッセージを利用して入手したノードに実際にアクセスするクローラーを利用して到達可能なノードを検出している。ただし、こうやって得られるのは到達可能なノードの情報のみと、それらのノードがどのようなネットワークトポロジーを形成しているかは分からない。

このノード間のエッジを推定しネットワークトポロジーを推定するための手法がTxProbeだ。

オーファントランザクションと二重使用トランザクションの扱い

TxProbeの調査方法は、Bitcoin Coreのオーファントランザクションと二重使用トランザクションのハンドリング方法に依存している。

トランザクションのハンドリング

ノードがトランザクションを受信し、検証するとそのトランザクションはメモリプールに格納され、接続中のピアに伝播される。ノードは直ぐに接続中のピアにトランザクションを送るのではなく、まずinvメッセージを使ってトランザクションの存在を通知する。そして、送信先のピアが該当トランザクションを持っていない場合getdataメッセージでトランザクションデータ自体を要求する。既に該当トランザクションを持っている場合はgetdataメッセージは送られない。

オーファントランザクションのハンドリング

オーファントランザクションのハンドリングは通常のトランザクションのハンドリングとは異なる。オーファントランザクションはそのインプットが参照するUTXOのトランザクションがまだそのノードに届いていないので、オーファントランザクションを受信してもそのトランザクションが有効なトランザクションかどうか検証することができない。そのためノードはMapOrphanTransactionsとして知られるメモリプールとは別のオーファンプールに格納される。またトランザクションの検証が出来ていないためこのオーファントランザクションが接続中のピアにリレーされることもない。

二重使用トランザクションのハンドリング

二重使用トランザクションは単純に同じコイン(UTXO)を使用する2つめのトランザクションで、このトランザクションを受信したノードは、最初のトランザクションのみを受け入れ、2つめの二重使用トランザクションは受け入れない。

基本的なネットワーク・トポロジーの推定手法

上記のトランザクションのハンドリング方法を利用すると、次のようにしてネットワーク・トポロジーの推定ができる。

まず以下の3つのトランザクションを作成する。

BitcoinBitcoinベースのアルトコインのネットワークのテストや監視、測定を行えるツールであるCoinscope*1を使用し、アリスとボブ2つのノードと接続するネットワークを仮定する。

f:id:techmedia-think:20191115134054p:plain
アリスとボブのノード間のエッジが存在する場合

Coinscopeで、

  • アリスのノードには {tx_P}を送信する。
  • ボブのノードには {tx_F}を送信する。

これが同時に到着すると仮定した場合、アリスはボブに {tx_P}をボブはアリスに {tx_F}をリレーしようとするが、お互いにとって通知されたトランザクションは二重使用トランザクションであるため、両者とも受けとったトランザクションを拒否する。

その後アリスに {tx_M}を送信する。 {tx_M}を受け取ったアリスは、それをボブにリレーする。この時点でアリスとボブのメモリプールとオーファンプールの状態は以下のようになる。

アリス ボブ
メモリプール  {tx_P},  {tx_M}  {tx_F}
オーファンプール  {tx_M}

アリスとボブのノード間にエッジが存在する場合、上記のようにボブのノードのオーファンプールには {tx_M}が存在している状態になる。このエッジが存在するかどうかの確認はCoinscopeが、ボブのノードに対して {tx_M}を通知するinvメッセージを送信した際のボブのノードの反応で判断できる。ボブとアリスの間にエッジが存在すれば、ボブは {tx_M}をオーファンプールに持っているので、invに対してgetdataを要求することはない。逆にアリスとボブのノード間にエッジが無ければ、ボブは {tx_M}について知らないので、Coinscopeのinvに対してgetdataを要求する。

以下はアリスとボブの間にエッジが存在しないパターンの構成:

f:id:techmedia-think:20191115135805p:plain
アリスとボブのノード間のエッジが存在しない場合

で、アリスとボブのメモリプールとオーファンプールの状態は↓

アリス ボブ
メモリプール  {tx_P},  {tx_M}  {tx_F}
オーファンプール

と簡単にエッジ検出できそうに思えるが、これはあくまでノード数が2つの場合に機能するが、ノード数が増えると破綻する。例えばアリスとボブの間にキャロルのノードが加わった場合に、Coinscopeがアリスに {tx_P}を送った際、 {tx_P}をアリスがキャロルにリレーするのを止められないので、ノードが増えると上記の手法はワークしない。

TxProveのトポロジー推定手法

上記の基本的な推定手法を、多くのノードが存在する状況で行えるようにするためには、TxProveでは、invBlockと呼ばれる手法を利用する。invBlockというのは、トランザクションを通知する際にinvで通知し、その要求がgetdataで来た際にトランザクションの送信を2分間ほど保留することでトランザクションの伝播を防ぐ手法(2分以上経過すると別のノードに問い合わせる)。

例えば、アリス、キャロル、ボブのネットワークを考える。

f:id:techmedia-think:20191115185556p:plain
invBlockの動作

まず、Coinscopeが全ノードに対して、 {tx_P}invを送信する。すると3ノードともそのトランザクションを要求するgetdataで返信するが、このうちアリスの要求に対してのみtxメッセージで {tx_P}を送る。すると {tx_P}を受信したアリスがキャロルに対して {tx_P}invを送信してもキャロルはすでにCoinscopeから最初に {tx_P}invを受け取っているので、アリスのinvには応答せず2分間待機している。続いて {tx_F}をボブに送信すると、ボブはそれをキャロルにリレーする。また {tx_M}をアリスに送信すると、それはキャロルにリレーされるが、キャロルは {tx_P}を持っていないので {tx_M}をオーファンとして扱い、各ノードの状態は以下のようになる。

アリス キャロル ボブ
メモリプール  {tx_P},  {tx_M}  {tx_F}  {tx_F}
オーファンプール  {tx_M}

上記のようにinvBlockの仕組みを利用することで、対象トランザクションを特定のノードに固定することができるので、この仕組みを利用して以下の手順でトポロジーを計測する。

  1. ターゲットノードを選択
  2. ターゲットノード用に親、マーカー、フラッドトランザクションを作成する。
  3. invBLockを実行する。
  4. ターゲットノード以外の全ての接続ノードにフラッドを送信し、フラッドを伝播させる。
  5. 親をターゲットに送信する。
  6. マーカーをターゲットに送信する。
  7. マーカーが伝播する。
  8. ターゲットを除くすべてのノードにマーカーを要求する。

ネットワーク内の全てのノードに対して↑を実行する。

TxProbeのコスト

mainnet(約1万のノード)でTxProbeを実行するコスト見積もりは以下のようになっている。

  • 時間: 8.25時間
  • 手数料 = (5 sat/byteとした場合) 573210〜764280 satoshi($20〜$30)

実際にmainnetでは検証されておらず、testnetで40回ほど検証が施行され、グラフ分析した結果が↓のような結果だったみたい。観測されたネットワークにはノードが733個で、6090個のエッジがあり、平均して16.6の接続数となっている。

f:id:techmedia-think:20191115191811p:plain
testnetのノードの接続数の分布

f:id:techmedia-think:20191115191849p:plain
testnetのノードグラフ

サークルの大きさは接続数の多さを表現しており、色がコミュニティを表している。ランダムグラフよりも高いコミュニティ構造を持ったグラフになっている。testnetとmainnetではインセンティブも違うのでこの傾向がmainnetにもそのまま当てはまるということはないだろうが、実際にmainnetでどのようなネットワークトポロジーが形成されているかは観測してみないと分からない。この辺、誰かmainnetで計測したりしないかなー。

なお、TxProbeは↑のようなBitcoin Coreのトランザクションのハンドリング方法に依存した仕組みなので、トランザクションの伝播方法が変わるといずれそのままでは使えなくなってしまうだろう。

*1:他のノードに接続し、接続を維持するBitcoinのネットワークプロトコルをしゃべるConnectorと、Connectorに対して要求を送る(あるノードに接続したり、メッセージを送信したりなど)Clientで構成される。