昨年スタンフォードで開催されたScaling Bitcoin 2017のBrian N. Levineのセッションで発表されてたのが効率的なブロック伝播のためのプロトコルGraphene↓
時間が空いたけど、どういうプロトコルなのかホワイトペーパーを読んでみた↓（珍しく短めのペーパーで読みやすい）。
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）を利用している。具体的には以下のステップで新しいブロックをアナウンスする。
- 新しいブロックの送信者はそのブロックの存在を
invメッセージを使って受信側のピアに伝える（このプロセスは今までと変わらない）。 - 受信側のピアは
invのブロックハッシュを確認し、自分がまだ受け取っていないブロックなら、相手にそのブロックを要求する。 - 送信側のピアは、ブロック内の全トランザクションのTXIDを要素にしてBloom FilterとIBLT I 作成し、ブロックヘッダと合わせて受信側ピアに送信する。
- 受信側のピアはメモリプール内の全トランザクションのTXIDを受信したBloom Filterにかけ、ブロックに含まれている可能性があるTXIDをピックアップし、ピックアップしたTXIDを使って受信者のIBLT I' を作成する。
- 受信側のピアは生成した 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つのメッセージのやりとり（inv、getdata、response）が必要なことを実証した。
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のみを使うケースでは、我々の２つの仕組みを使うケースよりもはるかに大きくなる。
Bloom Filterはy個のアイテムを表すx bitの配列だ。最初にxビットはクリアされている状態で、アイテムがフィルタに追加されるたびに、k個のハッシュ関数を使って選択されたkビットがビット列にセットされる。フィルタに必要なビット数はで、fは意図する偽陽性率。Grapheneの場合、
を使用する（ここでaは I と I' の期待差）。Bloom Filterにはn個のエントリーがあり、バイトに変換する必要があるので、そのサイズは
になる。またaがIBLTサイズの主要なパラメータであるケースもある。I のセルの数が I のエントリーリストと I' のエントリーリストとの間の予想対称差がd倍の場合、非常に高い確率でIBLT I は I' でデコードできる。我々のケースでは、期待差はaで、d = 1.5で設定する。
IBLTの各セルは、カウント、ハッシュ値および保存された値を持つ（鍵を持つことも可能だが、必要無い）。我々の場合、カウントフィールドは2バイトで、ハッシュ値は4バイト、値はトランザクションIDのラスト5バイト（衝突を防ぐのに十分なサイズ）。まとめると、エントリーの対称差があるIBLTのサイズは、1.5(2 + 4 + 5)a = 16.5a バイトとなる。したがってBloom FilterとIBLTの合計コスト（サイズ）Tは
となる。全てのBloom Filterの定数をとしてグループ化し、IBLTエントリーのオーバーヘッドを定数τ = 16.5とする。
Bloom Filterを可能な限り小さく設定するには、フィルタの偽陽性率を許可されている限り高くなるようにする必要がある。すべてのinvメッセージがブロックの前に送信済みであると仮定した場合、受信者はすべてのトランザクションをIDpool内に既に持っていることが分かっている（メモリプール内にある必要はない）。したがって、µ = n。すなわちブロック内の全てのトランザクションはフィルタを通過することが保証されているので、m - n個のトランザクションが誤検出になることを許容する。さらに、
aについて導関数をとる式（1）は、a = n/(cτ )の時、最小になる。
Bloom FilterとIBLTの実際の実装にはいくつかの天井関数が含まれているため、以下のように書き直せる。
式（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よりも厳密に優れている。
シミュレーション
Figure 2はCompact BlockとGrapheneのシミュレーション結果を示している。各試行ではブロックサイズとメモリプールのサイズをインプットとして取る。そして各プロトコルが実行され、必要とされたバイト数が記録される。Bloom FiltreとIBLTは確率的な仕組みなので、シミュレーションでは実際のデータ構造を使い、結果が正確であることを保証する。プロット上の各点は、その時点での何百ものシミュレーションの平均。エラーバーは小さすぎて表示できてない。
図から分かるようにGrapheneはメモリプールのサイズに応じてCompact Blockの1/10以下のコストになる。Grapheneのサイズはメモリプールのサイズに依存するが、その成長は非常に遅い。
順序付けられたブロック
Grapheneはブロック内のトランザクションの順序については何も指定していないが、代わりにトランザクションをID順にソートすること前提としている。Bitcoinは、あるトランザクションがブロック内の別のトランザクションに依存している場合、依存しているトランザクションは依存先の後に配置される必要がある。ただ標準的な順序付けは簡単に指定できる。マイナーがある特定の方法でトランザクションを並べたい場合（例えばASIC Boostのような）、そのオーダリングはIBLTと一緒に送られる。n個の要素があるブロックで、ワーストケースの場合、リストはビット長くなる。その余分なデータがあったとしても、GrapheneのアプローチはCompact Blockよりはるかに効率的だ。上記の例で、Grapheneが順序付けをする場合、追加のコストはn = 2000 トランザクションで、
になる。この結果Grapheneのコストは5.34 KBになるが、まだCompact Blockの半分だ。
