Bitcoin Cashのブロック伝搬速度を10倍にするという話もあるGrapheneでも使われている Invertible Bloom Lookup Tables(以下、IBLT)について調べました。
背景
IBLTはもともと集合一致などで使われるデータ構造です。ブロックチェーンに限った技術ではありませんが、ここではGrapheneでも導入として話される内容で述べます。
まず、マイナーがBTCやBCHのブロックをマイニングする際には、各マイナーノードが持つmempoolから一定のポリシー(feeが高い順など)に基づき、ユーザのトランザクション(以下、tx)を選びます。
ところが各マイナーが持っているmempoolは完全に同期しておらず、マイナーは新しいブロックを見つけたら(マイニングに成功したら)、そのブロックに含んでいるtxもブロードキャストする必要があります。Grapheneはこの「ブロックに含まれるtxを伝搬するコスト」を下げたいことがモチベーションとなります。
仮に完全にmempoolが同期できており、同じポリシーでtxを選ぶならtxをブロードキャストする必要もありません。例えば、「feeが高い順にtotal block sizeがxxMBまで」というポリシーに基づいて、同期されたmempoolからtxを選べば、新しいブロックに含まれるtxは確定できるため、わざわざ伝達してあげる必要もありません。
しかし、上述の通り、mempoolは完全に同期できてはいません。とはいえ、各マイナーが持つmempoolはほとんど同じです。この前提のときに効率的にmempoolという集合の差分を伝え、集合一致させる技術がIBLTです。
BloomFilterとIBLT
IBLTは、BloomFilterと多数の類似性を持つため、BloomFiterと比較し、IBLTをみていきます。まず、一般的なBloomFilterでは、以下の操作をサポートします。
- keyのInsert
- kyeのGet
counting BloomFilterでは、空間効率性を少々犠牲にし、
- keyのDelete
も可能にします。
※BloomFilterについては、以前の記事 や実装(と要素技術)を参照ください。
対して、IBLTでは、以下の操作をサポートします。
特筆すべきはListEntries
で、IBLTに含まれるkey-value pairを列挙することができます。
ListEntries
の利用方法を見るために、
Bitcoin block propagation with IBLT, Part I: infographicを参考にブロックチェーンでどのようにIBLTが使われるのか見てみたいと思います。リンク先の図を見ながらだとわかりやすいと思います。
IBLTを使った集合一致
集合一致までの流れを箇条書きで記載します。
- マイナーは、複数のtxを含めたブロックを生成
- 各txをkey-value pairとしてIBLTに割り当てる
- k個のハッシュ関数でkeyに対するハッシュ値を計算し、ハッシュ値をindexと思って各txをIBLTのcellに格納
- 3.で作成したIBLTをブロードキャスト
- IBLTを受け取ったマイナーは自分のmempoolから1.のminerと同じポリシーでtxを選ぶ(ただし、mempoolは完全に同期しているわけでないので、同じtxが選ばれるとは限らない)
- 選んだtxたちに対して、2.,3.と同じ操作で、受信側のマイナーでもIBLTを作成
ListEntries
によって3.のIBLTのkey-value pairを列挙し、6.のIBLTからDelete
していく- 7.の操作で選んだtxの差分が得られる
Grapheneでは、上記を効率的に行うために、BloomFilterを差分を計算する補助として使っています。BloomFilterは、false-positiveはあってもfalse-negativeは原理的にないので、受信側でIBLTを作る時のフィルタとして使っているようです。
長くなってしまったので、IBLTのデータ構造やサポートされる各操作の実装は次回の記事にまとめます。
References
- ビットコインキャッシュの使用ブロック伝播速度を10倍にする新技術”Graphene”
- Graphene: A New Protocol for Block Propagation Using Set Reconciliation
- Invertible Bloom Lookup Tables
- O(1) Block Propagation
- ビットコインとは何か? 第4回:ビットコインの仕組み(取引承認と採掘) - Bitcoin日本語情報サイト
- BloomFilterについて調べてみた - 逆さまにした
- GolangでBloomFilterを実装してみた - 逆さまにした
- Golangでcounting BloomFilterを実装してみた - 逆さまにした
- Bitcoin block propagation with IBLT, Part I: infographic