【CTO Tech Blog】IBDを高速化する新たな提案SwiftSync
- CTO Tech blog
先日SwiftSyncというBitcoinのブロックチェーンの初期同期（IBD）を高速化するための新しい提案が発表された↓
SwiftSync — Speeding up IBD with pre-generated hints (PoC) – Implementation – Delving Bitcoin
現状のIBD
ブロックチェーンの履歴データは成長とともに増えていくため、時間が経過するほど新規参加ノードが同期すべきデータは増えていく。ジェネシスブロックから始まり、現在の最新のブロックまでをダウンロードし、各ブロック内のトランザクションを処理/検証するのが初期同期（IBD）のプロセス。
トランザクションを処理するということは、
- 新しく生成したアウトプットをUTXOセットに追加し、
- トランザクションインプット使われたアウトプットをUTXOセットから削除する
ことであり、全ブロック分の同期が完了すると、その時点で最新の状態（UTXOセット）を保持できる。
現在Bitcoin Coreはこの初期同期の際に、デフォルトでassumevalidと呼ばれる機能を使っている。この機能は、ジェネシスブロックからハードコードされているブロックまで、トランザクション内のスクリプトの検証をスキップするというもので、これにより同期を高速化している。
それでもIBDには2日くらいかかる。
SwiftSync
SwiftSyncが解消するのは、↑のIBD中のUTXOセットへの追加/削除処理の部分。UTXOセットはLevelDBで管理されているため、同期中の追加/削除でディスクIOが発生する。
この同期中のUTXOセットに対する無駄なIO（後で削除することになるTXOの追加処理と削除処理）をなくしてしまおうというのがSwiftSyncの提案。あるブロック高Nにおいて有効なUTXOのデータをヒントとして提供することで、同期中にブロックNにおいて未使用のUTXOのみをUTXOセットとして追加するというアプローチ（Nは再編成が起こりそうにないブロック）。これでIBDが5.28倍高速化したみたい（8時間弱）。
各ブロックのトランザクションを処理する際、すべてのアウトプットについて、
- ヒントがアウトプットが未使用であると示している場合は、UTXOセットに書き込み
- ヒントがアウトプットは使用済みであると示している場合は、アウトプットのOutPointをハッシュし、それをハッシュの集約値に加算する。
また、すべてのインプットに対しては、
- インプットのOutPointをハッシュし、ハッシュの集約値から減算する
という処理を行う。実際に使用されたアウトプットに対して上記のハッシュ処理と加算/減算処理をするのがポイントで、ブロック高Nまで処理が完了した段階で、ハッシュの集約値がゼロであれば、ヒントは正しくブロック高N時点のUTXOセットを示していることが保証される。
要は、2つのセット、A（使用済みのアウトプットのセット）とB（インプットのセット）が一致することを検証するというもの。各OutPoinのハッシュ値を計算し、それを（モジュロ演算で）加算/減算した値がハッシュの集約値*1。たとえば、
- 使用済みのアウトプット
- OutPointA
- OutPointB
- インプット
- OutPointC
- OutPoincD
とした場合、
H(OutPointA || salt) + H(OutPointB || salt) - H(OutPointC || salt) - H(OutPointD || salt) mod N == 0
となれば*2、セットAとBは正確に等しいことが証明でき、集約値の対象にならなかったアウトプットはUTXOセットと等しくならなければならない。このプリミティブ自体は、Bitcoinや同期処理に関係なくいろんなところで使えそう。
集約値がゼロでない場合は、不正なヒントファイルが提供されたということなので、別の同期方法にフォールバックする必要がある。
ヒントファイル
ヒントファイルは、ブロック高Nまでに作成されたトランザクションアウトプットが、未使用なままであるかどうかを示す結果をビットマップとしてエンコードしたファイルで、ブロック高NのUTXOセットから生成するツールが提供されている↓
- ブロック高
Nまで同期したBitcoin CoreノードでdumptxoutsetRPCを実行して、その時点のUTXOセットをエクスポートし、 - エクスポートしたダンプファイルをSQLiteのDBに変換し*3、
- ツールbooster-gen.pyを使って、ヒントファイルを生成*4。このツールは、各ブロックに対して以下の処理を行いヒントファイルを作成する
- ブロックデータを読み込み
- SQLiteのDBから対象ブロック内の未使用のアウトプットを検索
- ブロック内のトランザクションについて先頭から、アウトプットが未使用であれば
1、使用済みであれば0としてマークし、ブロック内のすべてのアウトプットに対するビットマップを作成 - ブロックごとにビットマップをエンコード
現状、ブロック高850900の圧縮されたヒントファイルは約90MB弱で、解凍すると365MBほど。
ただ、ブロック毎のアウトプットの総数が2 byteだと理論的に上限が足りないとか、もっと効率的なエンコードが可能とか、ヒントファイルのフォーマット自体は今後また色々変わってきそう。
並列処理
従来のIBD方式では、TXOを生成してから使用されていた場合に削除する必要があることから、基本的にジェネシスブロックから順番にブロックを処理する必要がある。一方、SwiftSyncの場合、処理するブロックが前後しても、使用済みのTXOに関する処理は、減算して加算するか、加算して減算するかの違いで、どちらの順番で行っても最終的に結果はゼロになればいいので問題ない。そのため、マルチスレッド環境では、ブロックの並列処理が可能になり、さらに↑のSwiftSyncの速度は向上するとされている（現状、まだ並列処理には対応していないため）。
assumeutxoとの関係
IBDを高速にする手法としては、Bitcoin Core v28.0から導入されたassumeutxoもある↓
techmedia-think.hatenablog.com
このUTXOセットのスナップショットベースの同期は、4時間ちょっとで完了するので、SwiftSyncよりも高速だ。しかし、assumeutxoは、同期後もバックグラウンドでジェネシスブロックからスナップショットまでの間のブロックのダウンロードと検証は行われているため、これにSwiftSyncを適用することでその部分の高速化ができると提案されている。
*1:最初はMuHashを使って実装されてたけど、その後SHA-256とsecp256k1曲線の有限体上でモジュロ演算することで高速化した模様
*2:saltは外部から偽のデータを挿入されないようにするための保護
*3:Bitcoin Core v29.0でリリースされたutxo_to_sqlite.pyを使用
*4:2に加えて、Bitcoin Coreのデータディレクトリも参照するので、実行する際はBitcoin Coreをシャットダウンしておく必要がある
ブログ元記事へのリンク
Chaintopeでブロックチェーンの未来を共に創りませんか？
Chaintopeは、独自のブロックチェーン「Tapyrus」と、開発プラットフォーム「Tapyrus Platform」を活用し、デジタル社会の信頼基盤を構築しています。
私たちは、ブロックチェーン技術の可能性を最大限に引き出し、社会に新しい価値を提供することを目指しています。
募集職種：
ブロックチェーンエンジニア
アプリケーションエンジニア
インフラ・保守エンジニア
プロジェクトマネージャー
フィールドセールス
Chaintopeで働く魅力：
最先端のブロックチェーン技術に触れる機会
リモートワークやフレックスタイム制による柔軟な働き方
専門性の高いチームとの協働
ブロックチェーン技術に情熱を持つあなたのスキルを、私たちのチームで活かしませんか？
詳細は、採用情報をご覧ください。
https://www.chaintope.com/recruit/