Develop with pleasure!

福岡でCloudとかBlockchainとか。

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で構成される。

Bitcoinの新しいテストネットワーク「Signet」の仕様を定義したBIP-325

Bitcoin関連のテストを行うのに便利なtestnetだが、ブロックの生成間隔がまばら(30分くらい生成されなかったり、数秒で連続してブロックが生成されたり)だったり、巨大な再編成が起こったりとあまり安定していない。そのためテストになかなか使いづらくなっていた。このような問題を解消するため新しいタイプのテストネットワークがBIP-325として提案された↓

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

Signetでは既存のProof of Workの検証に加えて、ネットワーク起動時に予め設定するチャレンジと呼ばれるscriptPubkeyに対する有効な解答(scriptSig)が提供されるか検証するようになっている。ざっくり言うとPoAタイプのテストネット。

具体的には、ノード起動時に

$ ./bitcoind -signet_blockscript=<scriptPubkey(hexフォーマット)>

のように-signet_blockscriptオプションを使ってチャレンジのscriptPubkeyを指定する。これはP2PKHであってもいいし、k-of-nのマルチシグなどであってもいい。またこのブロックスクリプトによってSignetジェネシスブロックのデータも異なる。詳細はこちら

-signet_blockscriptオプションで起動されたチェーンは、ブロックをマイニングする際に有効なPoWの他、そのブロックのコインベーストランザクションのwitness commitment内にscriptPubkeyに対して有効な解答(scriptSig)を含める必要がある。有効なscriptSigが無い場合無効なブロックと判定される。この時、scriptSig内の署名および署名検証の際に使われるメッセージダイジェストは、ブロックから生成される(詳細は以下BIP参照)。

そのため、-signet_blockscriptに対応する有効な解答が作れるメンバー=対応する秘密鍵を保持し署名を付与できるメンバーしかブロックが作れなくなる。つまり予め決められたこれらのメンバーによりそのsignetのブロックは作られていくことになる。

以下、BIPの内容↓(仕組みの概要は書かれてるけど、Bitcoin Wikiの方がカスタムSignetの立て方など具体的に書いてて参考になるかも。)

2020/05/08時点の内容で更新

概要

複数の独立した参加者が関与する長期的なテストシナリオのため、ブロックの進行に対してProof of Workに加えて署名が使用される新しいタイプのテストネットワークにより、優れた調整と堅牢性を実現する。

動機

Testnetは実際のお金を危険に晒すこと無く新しいことを試すのに最適な場所だが、信頼性が低いことで有名だ。巨大なブロックの再編成や、マイニング中のブロック間に長いギャップが生じたり、また急に連続してブロックが作成されるバーストは、特に長期間に渡ってソフトウェアを実行する複数の独立した参加者が関与するソフトウェアの現実的なテストが実際に実行不可能となることを意味する。

新しいタイプのテストネットワークは、取引所などの組織による結合テストや、eltooやサイドチェーンペグなど次世代のLayer2プロトコルのテストにより適しいてる。目標は完全に信頼できることではなく、むしろ予測可能な非信頼性の量を持つことである。テストネットワークがmainnetと同じように動作する(つまり数千のブロックの再編成などはない)のと同時に、6ブロックの再編成などの予想される稀なイベントをトリガーしやすくする必要がある。Regtestはブロックの作成にコストがかからないため、複数の独立した参加者が関係する長期的シナリオには適していないため、どの参加者もテストネットワークを完全に制御できる。

仕様

新しいタイプのネットワーク「Signet」はチャレンジ(scriptPubkey)と呼ばれる追加のコンセンサスパラメータを受け取る。このチャレンジは単純なpubkey(P2PKHスタイル)、k-of-nのマルチシグもしくはその他の必要なスクリプトにすることができる。

コインベーストランザクションのwitness commitmentは、2つ目のコミットメント(署名/解答)を含むよう拡張される:

1-4 bytes - 以下の (x + 4) byteをプッシュする
4 bytes - Signetヘッダー (0xecc7daa2)
x bytes - 解答 (sigScript)

4バイトのSignetヘッダーで始まらないプッシュ操作は無視される。4バイトのSignetヘッダーを持つ複数のプッシュ操作は、最初のエントリーを除いて無視される。

チャレンジ内に含まれる全ての署名操作はSHA256d(modifiedBlockHash)、つまり以下のデータのダブルSHA256ダイジェストをsighashとして使用する:

サイズ 名前
Int32 4 nVersion
Uint256 32 hashPrevBlock
Uint256 32 modifiedMerkleRoot
Uint32 4 nTime
Uint32 4 nBits

modifiedMerkleRootハッシュは、コインベースのwitness commitmentに上記Signetの拡張が含まれない状態のブロックトランザクションのマークルルートを生成することで取得できる。これは、ブロックのマークルルートがSignet commitment内のマークルルートと異なることを意味する。これは署名されるメッセージ(この場合ブロック)に署名を含めることはできないためだ。署名とは別にブロック生成(マイニング)を簡単にするために、ブロックのnonce値はSignetの署名がコミットしないブロックの他の唯一のコンポーネントだ。Proof of Workを回していくのに、拡張用nonceは使用できない。これはそれを行うと署名が無効になるためだ。代わりに同じ(もしくは更新された)ブロックに再署名することで、Proof of Workの新しい計算スペースが得られる。

上記のコミットメントが見つかった場合、その解答が有効であれば、ブロックは完全に検証されたとみなされる。この検証はwitness commitmentの検証の前後に直接行うのを推奨する(両者の検証で必要なデータはほぼ同じであるため)。

ジェネシスブロックとメッセージスタート

全てのsignetネットワークにおいてジェネシスブロックは同じだが、メッセージスタートはシングルプッシュで定義されるチャレンジスクリプトのDouble-SHA256の先頭4バイト(以下参照)。

ジェネシスブロック

  • Time stamp: 1534313275
  • Nonce: 100123
  • Difficulty: 1e2adc28

この結果、ジェネシスブロックのハッシュは0000032d7f67af9ec7b7152aea0fe7c95b9804ff973265e252f245e0ae61799dで、ブロックのHex値は、

0100000000000000000000000000000000000000000000000000000000000000000000003ba3edfd7a7b12b27ac72c3e67768f617fc81bc3888a51323a9fb8aa4b1e5e4a3bc3735b28dc2a1e1b8701000101000000010000000000000000000000000000000000000000000000000000000000000000ffffffff4d04ffff001d0104455468652054696d65732030332f4a616e2f32303039204368616e63656c6c6f72206f6e206272696e6b206f66207365636f6e64206261696c6f757420666f722062616e6b73ffffffff0100f2052a01000000434104678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5fac00000000

メッセージスタート

メッセージスタートはシングルプッシュで定義されるチャレンジスクリプトのDouble-SHA256の先頭4バイトとして定義される(つまりチャレンジスクリプトの長さがプレフィックスになる)。

  • チャレンジスクリプト = 512103ad5e0edad18cb1f0fc0d28a3d4f1f3e445640337489abb10404f2d1e086be43051ae
  • Sha256d(長さ || チャレンジスクリプト) = sha256d(25512103ad...51ae) = 7ec653a59b1912f9db10da2c461ed827d48f9404d5ef0346a6c94aadd4203646
  • 先頭4バイト = the message start = 7ec653a5

互換性

この仕様は、既存のソフトウェアがすぐにSignetを使用できるという意味で後方互換性がある。

Signet用のネットワークパラメータ(マジックナンバーなど)を追加するだけで、クライアントは変更を加えることなく任意のsignetネットワークに接続して使用できる。ブロックヘッダーには有効なproof of workがあるため、クライアンはブロックが「おそらく」有効であることを簡単に確認できる。

ただし、特定のsignetネットワークでクライアントが受け入れたブロックは誰でもマイニングができる。ただし、これらのブロックには必要な署名が含まれていないため、完全な検証を行うノードはすぐにそのブロックを拒否する。そのため、クライアントはコインベーストランザクション内のブロックの署名を検証するか、信頼できるピアに接続する必要がある。

他のソフトウェアは本番環境で使用しないブロックの署名検証コードを追加する必要はない。これはネットワークが可能な限りmainnetのように動作することが目標である非実稼働のテスト目的に適している。

参照実装

https://github.com/bitcoin/bitcoin/pull/16411