つい最近、Gleb Naumenko氏、前同僚であったGreg Maxwell氏と私はミニスケッチ(Minisketch)を公開しました。ミニスケッチとは、分散システムを構成する各ノード間でデータを同期化する際、必要とする帯域幅を縮小させるソフトウェア・ライブラリーです。

ミニスケッチは本来ビットコインのネットワークを構成するノード間でトランザクション情報を共有する際使用されるセット調和リレー(set reconciliation relay, SRR)の研究プロジェクトの一部として開発されました。SRRの目的はビットコインのフルノードを運営する時に必要とされる帯域幅を大きく縮小することです。

本日、ミニスケッチをSSRとは独立的に公開する理由は、本ライブラリーはビットコイン以外でも幅広く多くのアプリケーションに役に立つと思ったからです。

何故ミニスケッチを使うのか

全ての分散システムは、従来からシステムを構成するノード間データを同期化することが非常に困難でした。一方、中央型システムの場合、中央システムが各ノードが持つデータを決められるのでデータの同期化は極めて簡単にできます。

一例として、分散システムでのノード間データの同期化に使用される技術としてInvertible Bloom Lookup Tables(IBLT)を挙げられます。CPU使用率は比較的に低いIBLTですが、特に二つのノード間データの違いが少ない時には多くの帯域幅が必要となります。ミニスケッチは帯域幅をより効率的に使うアルゴリズムであるPinSketchを使用します。帯域幅を効率的に使うセット調和アルゴリズムの中でCPISyncやPinSketchに比べミニスケッチはより少ない計算能力を要します。ミニスケッチはPinSketchより20から100倍、時にはCPISyncに比べ1000倍の速さで同期化させます。

どのようにして改善されたのか

ミニスケッチで実装されたセット調和(set reconciliation)は各ノードが数学的 「スケッチ」を生成することでノードが保有する全てのデータを送ることなく他のノードと比較することができ、より効率的に帯域幅を使うことができます。スケッチのサイズはデータセットの大きさでは無く、他のノードとのデータの不一致の期待値により決まります。スケッチだけを比べることで他のノードから必要なデータを確実に把握できることになります。

以下で具体的にどのように違いを割り出すのか説明します。例として、Aが{3,5,7,11}のデータセットを持ち、Bが{3,5,7,9,11}を持っているとしましょう。各データセットの元の合計を計算するとAの場合、3+5+7+11=26、Bの場合、3+5+7+9+11=35となります。Aが合計の26をBに送り、Bが自分の合計から引くと違いは9となります。このようにして違いを割り出せるのですが、この例だと一つの違いしか割り出すことができません。ミニスケッチではデータセットの多様な“合計達”を計算し送信することになります。結果的にN個の合計はN個の違いを割り出すことが可能となります。送信された“合計達”の数より、二つのデータセット間の違いが少ない限り、ミニスケッチによって全ての違いを割り出すことができます。

ビットコインでのミニスケッチ

ビットコインネットワークの頑健性はSybilやpartizionamento攻撃から守ることができるよう十分なフルノード間の連結によって左右されます。

残念なことに、現在ビットコインノードが使用するデータの多くは(平均的に40〜70％弱)トランザクション・データでは無くリレーすべき新しいトランザクションを探す為にお互い確認しあうことに使われています。現時点では、ノード毎の接続数を上げることは比例して帯域幅の負担を背負うことになり、よって各ノードが維持できるノード接続数が制限されます。

ここでセット調和技法を活用する場合、全てのピアーにトランザクションを共有し比較しなくても効率的にまだリレーされていないトランザクションを探し出すことができます。帯域幅への負担は接続ノード数とは独立したものとなり、個々のノードが持ち得る接続ノード数の増加が可能となります。このソリューションの一番の魅力は、ビットコイン・ネットワークのコンセンサス・ルールを一切変更しなくても良いという点でしょう。SRRはSRRプロトコルを支援するノード間でのみ利用され、支援しないノードにも悪影響はありません。

SRRプロトコル自体は未だ研究の真っ只中であり、ビットコイン・ネットワークに導入されるには多少時間がかかりそうですが、ミニスケッチのような技術はビットコインフルノードの採用と接近性(他の分散型ネットワークの最適化にも)をより高める大切な進展です。本プロジェクトのアップデート情報は後ほど本ブログで共有します。

ミニスケッチについて詳しく知りたい方はMinisketch GitHub repositoryをご覧ください。