Develop with pleasure!

福岡でCloudとかBlockchainとか。

Compact Blockとは異なる方法でブロックアナウンス時のトランザクションの重複を解消するプロトコル「Graphene」

昨年スタンフォードで開催されたScaling Bitcoin 2017のBrian N. Levineのセッションで発表されてたのが効率的なブロック伝播のためのプロトコルGraphene↓

www.youtube.com

時間が空いたけど、どういうプロトコルなのかホワイトペーパーを読んでみた↓(珍しく短めのペーパーで読みやすい)。

http://forensics.cs.umass.edu/graphene/graphene-short.pdf

コンセプトはBIP-152のCompact Blockと同じだ。新しいブロックをアナウンスする際に、既存のblockメッセージを使って伝播すると、そのペイロードにはブロックに含まれる全トランザクションが入ってる。ただ、ブロックに入っている(コインベースを除く)ほとんどのトランザクションは、既にほとんどのピアがメモリプール内に持っているものなので、blockメッセージのペイロードとして受け取ると二重にトランザクションのデータを受け取ることになり無駄が生じる。

BIP-152として現在のBitcoin Coreで実装されているCompact Blockでは、blockメッセージを使わずに、ブロックヘッダと短縮したTXID(6バイト)のリストを使ってブロックを通知し、受信側のピアが自身のメモリプール内に持っていないトランザクションがあればそれを要求する方法を取り、既に持っているトランザクションデータについては送られてこないようにしている。詳細は↓

techmedia-think.hatenablog.com

Grapheneもこのトランザクションの重複を解消するためのプロトコルで、Compact Blockの場合はブロック内のトランザクションリストの短縮TXIDを使用してブロックに入っているトランザクションの情報を相手のピアに伝えるという方法を取っているが、Grapheneでは代わりにBloom FilterとIBLT(Invertible bloom lookup tables)を利用している。具体的には以下のステップで新しいブロックをアナウンスする。

  1. 新しいブロックの送信者はそのブロックの存在をinvメッセージを使って受信側のピアに伝える(このプロセスは今までと変わらない)。
  2. 受信側のピアはinvのブロックハッシュを確認し、自分がまだ受け取っていないブロックなら、相手にそのブロックを要求する。
  3. 送信側のピアは、ブロック内の全トランザクションのTXIDを要素にしてBloom FilterとIBLT I 作成し、ブロックヘッダと合わせて受信側ピアに送信する。
  4. 受信側のピアはメモリプール内の全トランザクションのTXIDを受信したBloom Filterにかけ、ブロックに含まれている可能性があるTXIDをピックアップし、ピックアップしたTXIDを使って受信者のIBLT I' を作成する。
  5. 受信側のピアは生成した I' と送信者から受け取った Iの差分を計算し、ブロックに含まれるTXIDをデコードする。

※ IBLTは、key-valueペアの挿大、削除、検索、リストアップをサポートしている確率的なデータ構造で、Bloom Filterと同様Bitcoin特有の技術ではない。

両者が作成するIBLTの各セルは以下の値を持っている。

  • count(2バイト)
  • hash値(4バイト)
  • value(TXIDのラスト5バイト)

Bloom Filterには偽陽性があるため、フィルタにかけた結果合致する可能性があると判断されたTXIDも実はブロックに含まれていない可能性がある。このためBloom Filter単体ではブロックに含まれているトランザクションを確定することはできず、あくまで可能性があるトランザクションのリストをピックアップするだけ。IBLTは差分を取れるので、Bloom Filterを使って受信側が作ったIBLTと送信者が作成したIBLTの差分を取ることで、Bloom Filterでピックアップしたトランザクションリストの中から実際のブロックには含まれていないものを除外したリストを作成できるという仕組みっぽい。

Compact Blockとは異なりBloom FilterとIBLTにより確率的にブロックに含まれるトランザクションリストを判断するのがGrapheneの仕組みみで、その際Compact Blockの短縮TXIDよりも小さいデータサイズで済むと。

ただ基本的に実現していることはCompact Blockと同様、トランザクションの二重伝播の無駄をなくすということなので、Graphene単体でビッグブロックを劇的にスケールするような仕組みではない。Compact Blockの短縮TXIDよりもデータ効率は良いが、そのデータサイズも2000トランザクション持つブロック当たり、7,8KBぐらいの差なのでそこ単体を追求してもパフォーマンスの劇的な改善は見込めない。ただ、ブロックサイズが増えるとCompact Blockの場合、短縮TXIDのデータはリニアに増えるけど、Grapheneの場合はBloom FilterとIBLTのサイズはリニアには増えないので、(既存の1MBのBTCでは既にCompact Blockでトランザクションの重複は排除済でそんなに効果ないけど)ビッグブロックを前提とした選択肢としての採用はありだと思う。

以下、ホワイトペーパーの日本語訳。

イントロダクション

我々はGrapheneと呼ばれる新しいブロックのアナウンス方法を提案する。この文書は、これまでに発表されているものに追加の実験を加えたGrapheneのより詳細な説明をまとめたものだ。

Grapheneのブロックは、Compact BlockやXtreme Thinblock関連の方法の一部だ。例えば、以下の詳細な例では、17.5 KBのXtreme ThinblockはCompact Blockでエンコードすると10 KBで、Grapheneでエンコードすると2.5 KBになる。シミュレーションでは、GrapheneのエンコードはCompact Blockの約10%のスペースでエンコードできることが分かった。我々はBloom FilterとInvertible bloom lookup tables (IBLTs)の新しいインタラクティブな組み合わせを使って、BitcoinのP2Pネットワークにおける調整の問題に対する効率的なソリューションを提供する。

ブロックの通知は、ブロックを構成するトランザクションを使って検証される。しかし大多数のピアは既にそのトランザクションを受信しており、メモリプール内のトランザクションと識別するだけでいい。原則としてブロックの通知にはそのTXIDのみを含める必要がある。例えばCoralloのCompact Blockの設計ではトランザクションIDのリストを含めることで通知するブロックのサイズを大幅に削減しているが、ピア間の調整コストが増える。Xtreme Thinblockは、Compact Blockと同じように機能するが、データのオーバーヘッドが大きい。具体的には、受信者のメモリプールに無いブロックに対してinvメッセージが送信されると、受信者は持っていないブロックの要求と一緒にIDpoolのBloom Filterをを送信する。その結果、Xtreme ThinblockはCompact Blockよりも大きくなる。コミュニティはブロックの通知を減らすために(Bloom Filterを使用しない)IBLTsの使用について議論してきたが、そのスキームは正式に評価はされておらず、我々のアプローチより効率が悪い。我々の方法は新しいものだ。Compact BlockやXtreme Thinkblockよりも小さく、送信者と受信者の間で3つのメッセージのやりとり(invgetdataresponse)が必要なことを実証した。

Grapheneプロトコル

f:id:techmedia-think:20180413111759p:plain
Figure 1:Grapheneプロトコルのサマリ

他のアプローチと異なり、GrapheneはトランザクションIDの明示的なリストを送信しない。代わりに、小さなBloom Filterととても小さなIBLTを送信する。Grapheneの背景は以下の通りで、Figure 1に概要を示している。

送信者はブロック内のトランザクションIDのリストからIBLT I を作成する。また受信者が同じ(もしくは同様の)IBLTを作成できるように、送信者はブロック内のトランザクションのBloom Filter S を作成する。受信者はSを使って、受信したトランザクションIDのプール(IDpoolと呼ぶ)からフィルタにマッチするものをピックアップし受信者のIBLT I' を作成する。受信者は I' を使って I のデコードを試みる。デコードに成功するとブロックを構成するトランザクションIDが返される。Sに含まれる可能性があると誤って判断され I' に追加されたトランザクションの数は、送信者によって管理されるパラメータによって決定される。このパラメータを使うと、とても高い確率でデコード可能な I を送信者は作成することができる。

まとめると、送信者が作成するBloom Filterは、受信者が自身のメモリプール内のどのトランザクションがブロックにあるか決めるのに使われる。他のアプローチでは、偽陽性率と非常に低くするため大きなBloom Filterを使っているが、Grapheneの偽陽性率は高く、IBLTがその間違いを修正する。同様にIBLTのみを使うケースでは、我々の2つの仕組みを使うケースよりもはるかに大きくなる。

Bloom Filterはy個のアイテムを表すx bitの配列だ。最初にxビットはクリアされている状態で、アイテムがフィルタに追加されるたびに、k個のハッシュ関数を使って選択されたkビットがビット列にセットされる。フィルタに必要なビット数は {x = y \frac{-ln(f)}{ln^{2} (2)}}で、fは意図する偽陽性率。Grapheneの場合、 {f = \frac{a}{m - n}}を使用する(ここでaは II' の期待差)。Bloom Filterにはn個のエントリーがあり、バイトに変換する必要があるので、そのサイズは {\frac{-ln(\frac{a}{m-n})}{ln^{2}(2)} \frac{1}{8}}になる。またaがIBLTサイズの主要なパラメータであるケースもある。I のセルの数が I のエントリーリストと I' のエントリーリストとの間の予想対称差がd倍の場合、非常に高い確率でIBLT II' でデコードできる。我々のケースでは、期待差はaで、d = 1.5で設定する。

IBLTの各セルは、カウント、ハッシュ値および保存された値を持つ(鍵を持つことも可能だが、必要無い)。我々の場合、カウントフィールドは2バイトで、ハッシュ値は4バイト、値はトランザクションIDのラスト5バイト(衝突を防ぐのに十分なサイズ)。まとめると、エントリーの対称差があるIBLTのサイズは、1.5(2 + 4 + 5)a = 16.5a バイトとなる。したがってBloom FilterとIBLTの合計コスト(サイズ)Tは

 {T(a) = n \frac{-ln(f)}{c} + aτ = n \frac{-ln(\frac{a}{m−µ})}{c} + aτ }

となる。全てのBloom Filterの定数を {c = 8 ln^{2}(2)}としてグループ化し、IBLTエントリーのオーバーヘッドを定数τ = 16.5とする。

Bloom Filterを可能な限り小さく設定するには、フィルタの偽陽性率を許可されている限り高くなるようにする必要がある。すべてのinvメッセージがブロックの前に送信済みであると仮定した場合、受信者はすべてのトランザクションをIDpool内に既に持っていることが分かっている(メモリプール内にある必要はない)。したがって、µ = n。すなわちブロック内の全てのトランザクションはフィルタを通過することが保証されているので、m - n個のトランザクションが誤検出になることを許容する。さらに、

 {T(a) = n \frac{-ln(\frac{a}{m-n})}{c} +aτ } (1)

aについて導関数をとる式(1)は、a = n/(cτ )の時、最小になる。

Bloom FilterとIBLTの実際の実装にはいくつかの天井関数が含まれているため、以下のように書き直せる。

 {T(a) = \bigg( \lceil ln (\frac{m-n}{a}) \rceil \lceil \frac{n ln(\frac{m-n}{a})}{\lceil ln(\frac{m-n}{a}) \rceil ln^{2}(2)} \rceil \bigg) \frac{1}{8} + \lceil a \rceil τ} (2)

式(2)の最適値は、簡単なループで見つけることができる。実際には、aの最小値を見つけるループ検索はほとんどコストがかからず、シミュレーションでそれを行う。

IBLTのランダム化特性のため、デコードに失敗する可能性は非常に低いがゼロではない。その場合、送信者はセル数を2倍にしたIBLT(これでも非常に小さい)を再送信する。実際のIBLTとBloom Filterのエンコードの我々のシミュレーションでは、この倍増は非常に少数の失敗したIBLTにとって十分なものだった。

他のアプローチとの比較

我々はGrapheneがCompact Blockに比べて厳密に効果的であると前述したが、説明のためここで例を示す。

m = 4000 のトランザクションのIDPoolを持つ受信者は、n = 2000 のトランザクションを持つ新しいブロックを要求する。コストを最小化するaの値は、a = n/(cτ ) = 31.5である。送信者は偽陽性率 f = a m−n = 31.5/2000 = 0.01577でトータルサイズ2000 × −ln(0.01577) c = 2.1 KBのBloom Filter Sを作成する。送信者はまた、合計16.5a = 521バイトのセルを持つIBLTも作成する。まとめると、合計2160B+521B = 2.6 KBがネットワークを介して送信される。受信者は同じサイズのIBLTを作成し、Eppsteinらが紹介した技術を使って、デコードの前にIBLTをもう一方から減算する。比較すると、n個のトランザクションが含まれるブロックについて、Compact Blockのコストは2000 × 5B = 10 KBで、Grapheneの3倍以上のコストがかかる。

またXtreme Thinblockは、全てのIDとBloom Filterを含んでいるため、Compact Blockよりも確実に大きく、GrapheneはXtreme Thinblockよりも厳密に優れている。

シミュレーション

f:id:techmedia-think:20180413185239p:plain
Figure 2:GrapheneとCompact Blockの比較。

Figure 2はCompact BlockとGrapheneのシミュレーション結果を示している。各試行ではブロックサイズとメモリプールのサイズをインプットとして取る。そして各プロトコルが実行され、必要とされたバイト数が記録される。Bloom FiltreとIBLTは確率的な仕組みなので、シミュレーションでは実際のデータ構造を使い、結果が正確であることを保証する。プロット上の各点は、その時点での何百ものシミュレーションの平均。エラーバーは小さすぎて表示できてない。

図から分かるようにGrapheneはメモリプールのサイズに応じてCompact Blockの1/10以下のコストになる。Grapheneのサイズはメモリプールのサイズに依存するが、その成長は非常に遅い。

順序付けられたブロック

Grapheneはブロック内のトランザクションの順序については何も指定していないが、代わりにトランザクションをID順にソートすること前提としている。Bitcoinは、あるトランザクションがブロック内の別のトランザクションに依存している場合、依存しているトランザクションは依存先の後に配置される必要がある。ただ標準的な順序付けは簡単に指定できる。マイナーがある特定の方法でトランザクションを並べたい場合(例えばASIC Boostのような)、そのオーダリングはIBLTと一緒に送られる。n個の要素があるブロックで、ワーストケースの場合、リストは {n \log{2}(n)}ビット長くなる。その余分なデータがあったとしても、GrapheneのアプローチはCompact Blockよりはるかに効率的だ。上記の例で、Grapheneが順序付けをする場合、追加のコストはn = 2000 トランザクションで、 {n \log{2}(n) bits = 2000 \times \log{2}(2000) bits = 2.74 KB}になる。この結果Grapheneのコストは5.34 KBになるが、まだCompact Blockの半分だ。

安全な0-confirmation決済のためのプレコンセンサス「Ansible」

Satoshi's vision conferenceでテラバイトブロックについて発表していたJoannes Vermorelが最近発表したペーパー↓

http://media.lokad.com/bitcoin/ansible-2018-05-05.pdf

BCHを決済手段として利用する場合に(BTCもしかり)ネックになるのが決済のスピードで、通常ペイメントのサービスを提供している会社はトランザクションがブロックに入るのを待つことなく0-confirmationで決済を受け入れていることが多い。もちろん高額なものの場合はその限りではないけど、もしそれで二重使用された場合は決済サービス側がそこを負担するんだろう。

カジュアルに決済に利用するためにも、ブロックにトランザクションが格納されるまで待つというのは避けたいということで、0-confirmationトランザクションの受け入れを安全にするための研究が最近活発になってきており、↑で提案されているAnsibleもその提案の1つ。

Bitcoinのセキュリティモデル

Bitcoinのコンセンサスでは、平均10分で作成されるブロックにトランザクションが入れられることで決済事実がブロックチェーンに記録される。当然チェーンの一時的な分岐が考えられるので、ブロックに入ったからといってそれは確定的な事実ではなく、後続のブロックが続くほど、その事実は確率的に確定される。

これはあくまでブロックに入ったトランザクションについてであって、ブロックに入る前のトランザクションについて制御するコンセンサスは存在しない。コンセンサスによって0-confirmationトランザクションは保護されないので、ブロックに入るまでの間のトランザクションの制御をするプレコンセンサスを導入しようという話を最近よく聞く。

Bitcoin-NGなんかはキーブロックとマイクロブロックに分けて、10分に一度生成されるブロックでマイクロブロックを生成できる公開鍵を選択し、その後10分間、その公開鍵を使ってトランザクションが含まれるマイクロブロックをより短い間隔で沢山つくることで、より短い決済間隔で決済をできるようにしようと提案していたり、その他の提案もこういったBitcoinのコンセンサスの変更を含むのが多いけど、Ansibleは既存のBitcoinのコンセンサスを維持しつつ0-confirmationトランザクションの安全性を確保しようという提案。

タイムスタンプオーソリティとしてのAnsible

トランザクションの二重使用というのは同じインプットを持つ2つのトランザクションを作り、決済用にその1つを使い、マイナーに別の1つをブロックに入れてもらうことで、決済に使用したトランザクションを無効化してしまおうというもの。トランザクションがブロックに入るまでの間を狙った攻撃になる。

二重使用はブロックに入るまで、どちらのトランザクションが先に出来たものか・有効なものなのか判定する術がないので起きる問題だ。つまりどちらのトランザクションが先に出来たのか識別することができれば解決する問題でもある。

Ansibleでは、それを識別するためにタイムスタンプオーソリティの導入を提案している。

中央集権型のタイムスタンプオーソリティ

プレコンセンサスのシグナルを構築するのに簡単な方法が中央集権型のタイムスタンプオーソリティの導入になる。中央のオーソリティはBitcoinネットワークを関しして、各トランザクション毎に一意の高精度なタイムスタンプを発行する。このタイムスタンプには

このオーソリティにアクセスできるマイナーはトランザクションを全てオーバーレイに送るか、対応するタイムスタンプを取得するかする。

こうやって集めたタイムスタンプ付きのトランザクションで、競合するトランザクション(二重使用のトランザクション)が見つかった場合、タイムスタンプの早いトランザクションを正しいトランザクションとして採用し、そのトランザクションをピアに伝播する。

マイナーがオーソリティにアクセスするコストが、マイニングの収益と比較して十分低ければ、マイナーがオーソリティを採用するのは合理的な選択肢になる。

とは言ってもみんな、こういう中央集権的な仕組みを導入するのは抵抗ありますよねということで↓

分散型のタイムスタンプオーソリティ(Ansible)

↑のような中央集権的なオーソリティの導入は単一障害点の導入にもつながるため、P2P型タイムスタンプオーソリティ「Ansible」を提案している。

Ansibleの実体は既存のCompact Blockのようにネットワーク・プロトコルでサポートされるメッセージの一部とされている。

Ansibleは1人のマスターと複数の参加者で構成され、マイナーがブロックにAnsibleメンバーの公開鍵を入れ、そのブロックが10ブロックと60秒経過すると、そのメンバーが有効になり、以下のルールで運用される。

  • Ansibleが有効なノードは、(失効していない)有効なメンバーによって署名された全てのメッセージを中継する。
  • いずれの時点においても、Ansibleのメンバーは、他のメンバーに対して失効の投票を行うことができる。他のメッセージとは異なり、失効のメッセージは常に伝播されるが、メンバー毎に100の異なるメッセージの制限がある。失効は10〜110ブロックまでのブロックで発見されるメンバーの数による多数決で決定される。
  • 失効していないメンバーの内、最も古参が自動的にAnsibleのマスターに選出される。
  • AnsibleのマスターはAnsibleの他の有効なメンバーの利益のため、タイムスタンプオーソリティとして行動する。マスターが真面目にユニークなタイムスタンプの提供に失敗した場合、メンバーは直ちに失効の投票を始める。
  • メンバーはマスターによって発行されたタイムスタンプをP2Pで伝播する。

マスターによって発行されたタイムスタンプは、Ansibleによって発行されたプレコンセンサスシグナルを表す。Ansibleの一員である正直なマイナーには、Ansibleのプレコンセンサスシグナルに照らして二重使用攻撃を解決することが期待されている。

まとめ&所感

↑なようにAnsibleはタイムスタンプオーソリティによるシグナルをプレコンセンサスとして導入することで、トランザクションの順序を決定しようというアプローチを採っている。他にもオーソリティの地理的な分散や、Bitcoinアドレスにジオロケーションを埋め込む提案などもされているので詳細はホワイトペーパーを要チェック。

まだ細かいプロトコルまでは定義されておらず、ペーパー自体もフィードバックを求めるためのものみたい。個人的には、

  • 実際にオーソリティがタイムスタンプを返さなかったり、失効の投票が行われている間のトランザクションの取扱はどうなるのか?
  • Bitcoinのコンセンサスは変更しないということなので、マイナーの一部でもこれに従わない場合、二重使用のリスクは依然として残るのでは?
  • またマイナーがこれに従うインセンティブは?

といった点が気になる。

BIP-70のPayment Protocolの検証環境を作ってみた

Bitcoinを決済に利用する際に、決済先との間の中間者攻撃やマルウェアなどに感染した環境で、本当の支払先でないアドレスに送金するといったことが起きないよう、送金先をPKIを使って検証する仕組みがBIP-70で定義されているPayment Protocol↓

techmedia-think.hatenablog.com

bitcoinrbでもこれらのプロトコルに対応しようと思って、動作検証する環境をまず作ってみた。

BIP-70自体にはTest Vectorは掲載されていないけど、BIP-70の著者の1人であるGavin AndresenがPayment Protocolのデモ環境を公開してたのでそれを使ってみる↓

github.com

(以前はbitcoincore.orgのサイトでこれがホストされてたっぽいけど、今はなくなってる。)

Payment Requestのテスト環境のセットアップ

↑では以下のツールが提供されてる。

  • PaymentRequestの作成・検証のためのC++コマンドラインツール
  • PaymentRequeststの作成・検証のためのPHPのコードとデモサイト
  • テスト用の証明書作成シェル

まず以下のライブラリをインストールしておく。

テスト用の証明書とルート認証局の作成

BIP-70はPKIを利用して決済先の情報を検証するので、テスト用にルート認証局と、その認証局が発行した決済先用の証明書を作成する。

↑のリポジトリca_in_a_boxにテスト用の認証局と証明書を作成するスクリプトが用意されてるのでそれを実行するだけ。

$ cd ca_in_a_box
$ ./sh create_ca.sh
CA: Creating self-signed root certificate authority (CA) certificate:
Generating a 2048 bit RSA private key
.....+++
............+++
writing new private key to './private/cakey.pem'
-----
MERCHANT: Creating merchant private key and certificate signing request (CSR):
..++++++
...................++++++
CA: Issuing new merchant certificate
Using configuration from openssl.cnf
Check that the request matches the signature
Signature ok
The Subject's Distinguished Name is as follows
commonName            :ASN.1 12:'testmerchant.org'
organizationName      :ASN.1 12:'Payment Request Test Merchant'
Certificate is to be certified until Mar 11 05:27:23 2028 GMT (3650 days)

Write out database with 1 new entries
Data Base Updated
Done.
 Root CA certificate is certs/cacert.pem
 Merchant certificate is certs/demomerchant.pem , private (signing) key is private/demomerchantkey.pem

スクリプトの中身はopensslコマンドを使って、認証局とマーチャントの証明書のファイルを作ってるだけで、実行が完了するとcertsディレクトリができ、そこに認証局とマーチャントの証明書が作成され、privateディレクトリに認証局とマーチャントの秘密鍵が格納される。

  • certs/cacert.pem
    ルート認証局の証明書
  • certs/demomerchant.pem
    マーチャントの証明書
  • private/demomerchantkey.pem
    マーチャントの証明書の秘密鍵

ちなみに生成されたマーチャントの証明書が

X509v3 extensions:
            X509v3 Basic Constraints: 
                CA:TRUE

とCAの証明書になってたりする。同じopenssl.cnf使ってるからそのオプションのせいっぽい。なのでこれで証明書作ららなくても自前で認証局とマーチャントの証明書作る方がいいかも。

PHPのデモサイト

依存ライブラリの関係でPHP5系でしか動作しないみたいなので、PHP7系でなくPHP5系の環境が必要。今回はphpenv使ってPHP5.6.34を入れる。何気にPHPの環境用意するのが一番面倒だった。。

最初にphpenvをインストール↓

参考:phpenvで最新版のPHPをインストールしてWebサイトで使用する - Qiita

PHP 5.6.34のインストール時にpearも欲しかったので以下のように--with-pearを指定する。

$ CONFIGURE_OPTS="--with-pear" phpenv install 5.6.34

続いて、PHPでProtocol Bufferを扱うのに必要なProtobuf-PHPをインストールする。

$ pear channel-discover pear.pollinimini.net
$ pear install drslump/Protobuf-beta

続いてmemcacheモジュールをインストールするんだけど、pearpeclでは見つからなかったのでソースをダウンロードしてきてビルドした。

$ wget https://pecl.php.net/get/memcache-3.0.8.tgz
$ tar xvfz memcache-3.0.8.tgz
$ cd memcache-3.0.8
$ CFLAGS="-fgnu89-inline" ./configure
$ make
$ make install

./configureを実行する際にCFLAGS="-fgnu89-inline" しておかないと後でエラー吐く。

以上でセットアップは環境。

後は簡単で、paymentrequestをcloneしてdemo_websiteをrootに指定して実行し、

$ php -S localhost:8000 -t <clonしてきたパス>/paymentrequest/php/demo_website

http://localhost:8000/createpaymentrequest.php

にアクセスすると↓のような画面が表示される。

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

証明書とその秘密鍵のロケーションを変更

PaymentRequestsを作成する際に、PKIの署名データが付与されるんだけど、この署名を生成するのに証明書を作成する際に使用した秘密鍵が必要になる。

証明書と鍵のロケーションは/home/gavin/.certs/以下のハードコードされてるので、

https://github.com/gavinandresen/paymentrequest/blob/master/php/demo_website/createpaymentrequest.php#L190

https://github.com/gavinandresen/paymentrequest/blob/master/php/demo_website/createpaymentrequest.php#L205

自分の環境に合わせて書き換える必要がある。

// 証明書
$leafCert = file_get_contents("使用するマーチャント証明書ファイルのパス");
...
// 鍵
$priv_key = file_get_contents("使用するマーチャント秘密鍵ファイルのパス");

書き換えたら、↑のURLにアクセスして、最低限アドレスと量(Amount)を入力して、「Create Payment Request」を押せばPayment Requestのメッセージがダウンロードできる。

データを確認すると、Payment Requestのsignatureには↑のマーチャントの秘密鍵を使って生成した署名データがセットされている。

Payment Requestのpki_dataには、仕様的には、まず必須なのが最初に↑のマーチャントの証明書がセットされ、それ以降は任意でその証明書からルート証明書までの証明書のチェーンが一式セットされるようになってる。PHPのデモコードではX.509証明書の拡張プロファイルのauthorityInfoAccessに記載されているURIから親の証明書を辿る仕組みになってるんだけど、↑で生成した証明書にはこのプロファイルが入ってないので、親が辿れず↑のメッセージにはマーチャントの証明書しか入ってない。

なので、PHPのコードを書き換えて↑の認証局の証明書まで含めるようにするか、↑のテスト用の証明書をメッセージを受け取ったクライアント側のOSに仕込んで証明書チェーンを検証するかする必要がある。まぁ実際にルート証明書が入っていないケースも考慮すべきなので、後者の方法を取る方がいいかな。

と、一応動く検証環境はできたけど、環境周りや設定変更とか必要なので、検証終わったらSinatraで簡単なAPIとか作りたいなー。

マルチパーティ間のスクリプトのプライバシーを向上させるTaprootというコンセプト

先日、bitcoin-dev MLにGregory MaxwellがポストしていたTaprootというコンセプトが興味深かったので見てみる↓

[bitcoin-dev] Taproot: Privacy preserving switchable scripting

まだBitcoinにはデプロイされていないが、MASTというscriptPubkeyをマークル化するアプローチが提案されている↓

techmedia-think.hatenablog.com

techmedia-think.hatenablog.com

複数の条件でコインをアンロックできるscriptPubkeyがある場合(例えば、2-of-2の署名があればアンロックできる or 24時間経過したら1人の署名でアンロックできるなど)、通常のP2SHでは元の条件を全て含むredeem scriptを公開してどちらかの条件でアンロックする必要があるが、↑のMASTを利用すると実際にアンロックに使用する条件のみを公開するだけで良い。使用しない条件を公開する必要がないためプライバシーが少し向上し、ブロックチェーン上に記録される容量も削減できる。

ただ、MASTを使用してアンロックしていること自体は分かるので、公開されるのはアンロックに使用した条件のみだが、他に何らかの条件が存在したことは知られてしまう。

これを改善するのに、複数の条件が無い場合にもダミーのハッシュなんかを用意してMASTを構成するスクリプトを作り、別の条件があるかのように偽装するという方法も考えられる。ただこの場合ネックになるのが、複数の条件を必要としないケースに比べて32バイトほど余計にトランザクションスペースを消費する点だ。この余分な32バイトを使ってもプライバシーを考慮すべきかというトレードオフが発生する。

マルチシグ or 他の条件がアンロック条件となるスクリプトに対して、このトレードオフを発生することなくプライバシーの向上と容量のセーブの両方を実現するのがTaprootのコンセプトだ。

アリス(公開鍵A)とボブ(公開鍵B)がいて、以下のいずれかの条件でアンロック可能なコインがあるとする。

  • AとBに対応するアリスとボブそれぞれの秘密鍵による署名でアンロック可能
  • CSVでタイムロックされた時間を経過したらボブの秘密鍵による署名でアンロック可能

普通にscriptPubkeyを書くと以下のようなスクリプトになる。

OP_IF
  2 <A> <B> 2 OP_CHECKMULTISIG
OP_ELSE
  <ロック時間> OP_CSV OP_DROP <B> OP_CHECKSIG
OP_END
TaprootのscriptPubkey

Taprootのコンセプトでは、これを以下のようにしてある1つの公開鍵への支払いにする。
※ 前提としてSchnorrの集約特性を必要とする。

  1. まずAとBのマルチシグの部分について、AとBの公開鍵を集約した集約鍵C = A + Bを作る。(rogue key攻撃の懸念がある場合はMuSig*1を利用して集約鍵を作る。)
  2. タイムロックスクリプトS = <timeout> OP_CSV OP_DROP B OP_CHECKSIGVERIFYとする。
  3. CSから楕円曲線上の点P = C + H(C || S)Gを計算する。
    H()ハッシュ関数で、G楕円曲線のジェネレータ)
  4. scriptPubkey [Taprootのバージョン] [楕円曲線上の点P]宛てに支払いをする。
    (segwitのscriptPubkey [witness version] [witness program]みたいなイメージだと思う)

このscriptPubkeyにロックされた資金をアンロックする方法は当然2つあり、それぞれ以下のようにアンロックする。

アリスとボブのマルチシグを使ってアンロックする方法

P楕円曲線上の点=公開鍵で、この点はアリスとボブの公開鍵を集約して作った点CとH(C||S)をシークレットとして生成した点を加算した点なので、アリスとボブの秘密鍵にH(C||S)を加算して、Pに対して有効な署名を作成することができる。

タイムロックの条件を使ってアンロックする方法

マルチシグ以外でアンロックできる条件がもう1つのタイムロックされている条件で、この条件を使用するのに以下のような新しいコンセンサスルールを導入する。

Pを構成するアリスとボブの集約鍵Cともう1つの条件のスクリプトSを提供し、C + H(C||S) = Pが成立する場合、Sスクリプトのタイムロックの条件をクリアし、ボブの秘密鍵による署名があればコインをアンロックできるというものだ。

どちらの方法でアンロックするかの判定はwitness stackのアイテムの数で判断するのかな?

まとめ

Taprootでは、所謂マルチシグのアンロック条件とそれ以外のアンロック条件を持つスクリプトを組み合わせて1つの公開鍵にする。マルチシグの場合はマルチシグの参加者の署名があればその公開鍵に対する有効な署名を作ることができアンロックできる。もう1つのスクリプトの条件を使ってアンロックする場合は、マルチシグを構成する際の集約鍵とその元の条件のスクリプトを公開することで、スクリプトの条件を使ったアンロックを可能にする。

↑はアリスとボブのだったけど何人でも動作原理は同じで、Sにも任意のスクリプトをセット可能だ。

最初に説明したようにMASTのプライバシーをさらに向上させるのに、複数の条件がない場合でも条件があるように見せるようMASTを構成すると無駄なデータサイズが発生するが、Taprootの場合はロックに使用するのは公開鍵Pだけあれば良いのでこの問題が解消できる。

条件が課されたコントラクトを含むロックスクリプトを、オーバーヘッドの無い単純な公開鍵として表現するアイディアがおもしろいなー。

Schnorrベースのマルチシグネチャスキーム「MuSig」

先日、Gregory MaxwellとAndrew Poelstra、Yannick SeurinとPieter Wuilleらによって、Schnorr署名を使ったマルチシグスキームのホワイトペーパーが発表された↓

https://eprint.iacr.org/2018/068.pdf

これに関する記事をPeiter WuilleがBlockstreamのブログにポストしていたので↓

blockstream.com

まずは↑読んで理解した範囲でMuSigについて書いてみる↓

既存のマルチシグ

Bitcoinにおけるマルチシグはよくm-of-nのように記載されn個の公開鍵の内m個の公開鍵に対応する秘密鍵で署名された署名データがあればコインのロックを解除できるといったもので、以下のようなscriptPubkeyと、アンロックする際のscriptSigが用いられる。

scriptPubkey

2-of-3のマルチシグのscriptPubkey↓

2 <公開鍵1> <公開鍵2> <公開鍵3> 3 OP_CHECKMULTISIG
scriptSig

↑の2-of-3のscriptPubkeyにロックされたコインを使用する際に必要なscriptSig

0 <公開鍵1の秘密鍵による署名> <公開鍵3の秘密鍵による署名>

トランザクションにはn個分の公開鍵と、m個分の署名データが含まれm-of-nの個数が増えるほどこのデータサイズも増えることになる。

鍵と署名の集約

既存のマルチシグは署名にECDSAを採用しているが、MuSigではこの部分をSchnorr署名をベースにした仕組みでサイズの削減とプライバシーを向上させようとしている。MuSigは鍵の集約をサポートする新しいマルチシグの方式で、マルチシグを構成する複数の公開鍵を1つの鍵に集約することができる。既存のマルチシグのscriptPubkeyは複数の公開鍵への支払いとみなすことができるのに対し、MuSigでは集約された公開鍵への支払いとみなすことができる。署名検証時も集約された鍵があれば良いので、個々の公開鍵の値が何なのか検証者に知られることはなく、サイズの削減とプライバシーの向上が見込める。

マルチシグの仕組みをMuSigにすることで、

  • トランザクションの各インプットに複数セットしていた署名の数を1つに減らせる
  • すべての公開鍵を含むスクリプトを1つの集約された公開鍵に減らせる

といった既存のマルチシグへのメリットが考えられる。

またそれ以上に複数のインプットを持つトランザクションの署名を1つに集約するということも可能になる。前者のマルチシグが複数の署名者が同じメッセージ(sighash)に対して署名するのに対し、後者の場合は各署名者は異なるメッセージ(インプット毎にsighashは異なる)に署名することになる。

具体的にどういう署名方式なのか見てみよう。

表記

  •  {x,x_1,x_2,...}を公開鍵 {X,X_1,X_2,...}に対応する秘密鍵とする(ジェネレータGと合わせ、 {X_i = x_{i}G})。
  • 署名されているメッセージはm
  • H()は暗号学的ハッシュ関数

Schnorr署名

Schnorr署名の式は以下のように定義されている。

  • 署名は {(R, s) = (rG, r + H(X, R, m)x)}。rは署名者が選択したランダムなナンス。
  • 検証は {sG = R + H(X, R, m)X}が成立するか。

構成要素はECDSAよりシンプルだ。

※ 他のサイトのSchnorrの式みると {H(R, m)}でXが含まれてないんだけど、どういう違いから来てるのか? Xがあると(R, s)から公開鍵を復元することもできない気がする。

Schnorrベースのマルチシグ

Schnorrベースのマルチシグの署名と検証は以下のように行う。

  • Xを各署名者が持つ公開鍵=点 {X_i}の合計とする。
  • 各署名者はランダムなナンス {r_i}を選択し、他の署名者と {R_i = r_{i}G}を共有する。
  • Rを点 {R_i}の合計とする。
  • 各署名者は {s_i = r_i + H(X, R, m)x_i}を計算する。
  • 最終的な署名データは(R, s)で、sは {s_i}の値の合計。
  • 検証は {sG = R + H(X, R, m)X}が成立するか確認する。ここでXは個々の公開鍵の合計。

署名 {(R, s)}及び検証式 {sG = R + H(X, R, m)X}が↑のSchnorr署名の式を満たす形でマルチシグを構成しているのが分かる。

各署名者がの秘密鍵とナンスから {s_i}を加算して求めた点と、各署名者の公開鍵と {R_i}を加算して出来た点の検証になってるので、楕円曲線の準同型性を利用した仕組みみたいだなー。

rogue-key攻撃の問題

↑のSchnorrベースのマルチシグで問題になるのがrogue-key攻撃。例えばアリス(公開鍵 {X_A})とボブ(公開鍵 {X_B})がマルチシグを構成する場合、お互いに公開鍵を教える必要がある。例えばアリスが公開鍵を教えた後に、ボブがアリスの公開鍵を使って {X'_B = X_B - X_A}を計算して、 {X_B^{'}}を自分の公開鍵として教えることが考えられる。この場合鍵を集約すると {X_A + X'B = X_A + X_B - X_A = X_B}となり、ボブの公開鍵 {X_B}秘密鍵だけで署名ができてしまう。

この問題を回避する方法の1つは、アリスとボブの公開鍵に加えて、それぞれがその公開鍵に対応する秘密鍵を本当に所有しているという証明を最初にするというもの。ボブは {X'_B}秘密鍵を持っていないので証明できず不正を働けない。ただ必ずそういった証明を事前に行えるという保証をプロトコルレベルで保証するものではないので、こういった攻撃ができない仕組みが求められる。

Bellare-Nevenのマルチシグネチャ方式

rogue-key攻撃に対して安全なのがBellare-Nevenのマルチシグネチャで、以下の手順で署名の作成と検証を行う。

  •  {L = H(X_1,X_2,...)}とする。
  • 各署名者はランダムなナンス {r_i}を選択し、他の署名者と {R_i = r_{i}G}を共有する。
  • Rを {R_i}ポイントの合計とする。
  • 各署名者は {s_i = r_i + H(L, X_i, R, m)x_i}を計算する。
  • 最終的な署名データは(R, s)で、sは {s_i}の値の合計。
  • 検証は {sG = R + H(L, X_1, R, m)X_1 +H(L, X_2, R, m)X_2 + ... }が成立するか確認する。

さらに、各署名者は {R_i}を公開する前に、 {H(R_i)}を公開する事前のコミットメントラウンドを設けるケースもある。

検証式を見れば明らかだが、この方式だと↑の通常のSchnorrの式を満たさない。署名の {s_i}を計算する際に、公開鍵に乗算する {H(L, X_i, R, m)}に各公開鍵が含まれており、 {x_i}に乗算する値が署名毎に異なるため、 {sG = R + H(X, R, m)X}のような集約はできない。確かにrogue-key攻撃を防ぐことはできるが、反面、検証には各公開鍵が必要となり、鍵の集約特性が失われてしまう。

MuSig

rogue-key攻撃に対して安全でありつつ、鍵の集約特性を備えたマルチシグネチャ方式が、今回提案されたMuSigで、以下の手順で署名の作成と検証を行う。

  •  {L = H(X_1,X_2,...)}とする。
  •  {H(L, X_i)X_i}の合計をXとする。
  • 各署名者はランダムなナンス {r_i}を選択し、他の署名者と {R_i = r_{i}G}を共有する。
  • Rを {R_i}ポイントの合計とする。
  • 各署名者は {s_i = r_i + H(X, R, m)H(L, X_i)x_i}を計算する。
  • 最終的な署名データは(R, s)で、sは {s_i}の値の合計。
  • 検証は {sG = R + H(X, R, m)X}が成立するか確認する。

ポイントはSchnorrベースのマルチシグのXを、単純な各公開鍵の和でなく、全公開鍵をハッシュした要素に公開鍵を乗算した和にしている点だ。

BNと異なるのは、各署名作成時に署名毎に異なるハッシュ値 {H(L, X_i)}を持つものの、それに対応する点 {H(L, X_i)X_i}を加算してXを作り共有することで、鍵の集約を可能にしている。署名 {(R, s)}及び検証式 {sG = R + H(X, R, m)X}が標準のSchnorrの式と同じになりっており、集約特性があることが分かる。

また各 {s_i}の計算時に署名毎に異なる {H(L, X_i)}秘密鍵 {x_i}に掛けているため、標準的なSchnorrベースのマルチシグに比べてrogue-key攻撃への耐性がある。

というのがMuSigの仕組みみたい。

↑の式だと1つのメッセージへの多重署名なのでマルチシグの置き換えは可能だけど、トランザクションの署名を1つに集約する場合、メッセージはインプット毎に異なるため、 {H(X, R, m)}のmは署名毎に変わるからmを {H(L, X_i, m)}側に移動するのかな?この辺はホワイトペーパー見てみないと分からない。

これがどういう形でBitcoinに適用されるかは、多分またBIPとして出てくるだろう。