Bitcoin Cashのブロック伝搬速度を10倍にするGrapheneで使われているInvertible Bloom Lookup Tables(IBLT)について調べてみた

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では、以下の操作をサポートします。

  • (key, value)のInsert
  • (key)のGet
  • (key, value)のDelete
  • ListEntries

特筆すべきはListEntriesで、IBLTに含まれるkey-value pairを列挙することができます。 ListEntriesの利用方法を見るために、 Bitcoin block propagation with IBLT, Part I: infographicを参考にブロックチェーンでどのようにIBLTが使われるのか見てみたいと思います。リンク先の図を見ながらだとわかりやすいと思います。

IBLTを使った集合一致

集合一致までの流れを箇条書きで記載します。

  1. マイナーは、複数のtxを含めたブロックを生成
  2. 各txをkey-value pairとしてIBLTに割り当てる
  3. k個のハッシュ関数でkeyに対するハッシュ値を計算し、ハッシュ値をindexと思って各txをIBLTのcellに格納
  4. 3.で作成したIBLTをブロードキャスト
  5. IBLTを受け取ったマイナーは自分のmempoolから1.のminerと同じポリシーでtxを選ぶ(ただし、mempoolは完全に同期しているわけでないので、同じtxが選ばれるとは限らない)
  6. 選んだtxたちに対して、2.,3.と同じ操作で、受信側のマイナーでもIBLTを作成
  7. ListEntriesによって3.のIBLTのkey-value pairを列挙し、6.のIBLTからDeleteしていく
  8. 7.の操作で選んだtxの差分が得られる

Grapheneでは、上記を効率的に行うために、BloomFilterを差分を計算する補助として使っています。BloomFilterは、false-positiveはあってもfalse-negativeは原理的にないので、受信側でIBLTを作る時のフィルタとして使っているようです。

長くなってしまったので、IBLTのデータ構造やサポートされる各操作の実装は次回の記事にまとめます。

References