Develop with pleasure!

福岡でCloudとかBlockchainとか。

フルノードのストレージ負担を削減しつつIBDの支援を可能にするSecure Fountain Architecture(SeF)

Scaling Bitcoin 2019予習シリーズ第4弾は、カリフォルニア大学の「SeF: A Secure Fountain Architecture for Slashing Storage Costs of Blockchains」。ホワイトペーパーは↓

https://arxiv.org/pdf/1906.12140.pdf

ブロックチェーンのフルノードはジェネシスブロックから始まる全てのブロックチェーンのデータをスタンドアロンで検証し、保存する唯一のノードだ。一方ブロックチェーンはチェーンが伸びるに連れてデータも成長していく。フルノードの消費リソースとしては署名検証のためのCPUリソース、ネットワーク帯域、ストレージ容量などがあるが、今回フォーカスするのはこの内のストレージコストについて。現在Bitcoinブロックチェーンのデータは全体で215GBを超え、そのうちUTXOセットは3〜4GBになる。そしてブロックチェーンのデータは今後も線形増加していく。

このストレージコストを削減する方法として、現在とれる方法は以下の2つ。

  • 軽量ノード
    SPVノードとも呼ばれるが、ブロックチェーンのデータはダウンロードせずブロックヘッダーのみをダウンロードするタイプのノードで、信頼できるフルノードとの接続が必要になる。ダウンロードするデータ量が限定的であるため、スマートフォンやIoTデバイスなどの軽量デバイスでも動作する。トランザクションの有効性を個別検証することはできなかったり、フルノードに対するプライバシーの課題が残る。
  • プルーニングモード
    プルーニングモードはフルノードの動作モード1つで、フルノードと同様ジェネシスブロックから最新のブロックまで全てのブロックをスタンドアロンで検証する。ただ検証し終わった後の古いブロックは削除していくことで、消費ストレージを削減する。

(単純にブロックチェーンのデータの正しさの検証であればプルーニングモードでも可能だが)上記の2つの方法ではストレージコストを削減することはできても、Bitcoinネットワークに新たなノードが参加してきた際に、そのノードにジェネシスブロックから最新のブロックまで配信することはできない。そして、そのようなデータの提供が可能なフルノードの存在は、Bitcoinのような分散ネットワークを維持していくのに重要な役割を果たす。

SeFの提案では、フルノードのストレージコストを削減しつつも、プルーニングモードとは違い新しく参加するノードに対してブロックチェーンの復元をサポートできるような仕組みを提案するもの。

Secure Fountain Architecture

SeFのアプローチは、各ノードはブロックチェーンのデータを符号化し一部だけ保存することでストレージコストを節約する。新しくネットワークに参加したノードは、複数のノードからそれぞれ符号化されたブロックチェーンデータの一部を受け取り、それらを集めてデコードしブロックチェーンのデータを復元する。分散ストレージシステムにおいて、信頼性を低下することなく分散ストレージシステムのストレージコストを大幅に削減する方法として消失符号を利用したりするが、それと同じアプローチっぽい。つまり単一のノードが保持するデータ量は削減し、ネットワーク内の複数のノードからデータを集めることでブートストラップノードがブロックチェーンを復元できるようにする。

ちなみにRippleはHistory Shardingという仕組みで台帳履歴をネットワークで分散管理するようにしている。ただランダムサンプリングを採用しており、新しく参加したノードのブートストラップコストはSeFのアプローチに比べてかなり大きいみたい。

SeFがどのようにブロックをエンコードし、新しい参加ノードがどうやってそれをデコードしブロックチェーンを復元していくかみていこう。

用語

解説にあたって、SeFで扱う用語を整理↓

  • エポック
    ブロックチェーンがkブロック(kは調整パラメータで例えばk = 10000)成長するのに必要な時間の定義で、SeFにおいてブロックを符号化する処理の単位。
  • ドロップレット
    エポック単位にブロックチェーンのオリジナルのブロックをSeFにより符号化した符号化ブロック。
  • ドロップレットノード
    ストレージ制約のあるノードで、バケットノードに対してドロップレットを提供し、新規参加ノードがブロックチェーンを復元するのを支援を行う。
  • バケットノード
    ネットワークに新規参加するノードで、ドロップレットノードと繋いでブロックチェーンを復元する。ブロックチェーンの復元ができたら、ドロップレットノードになれる。

エンコーディング

各ドロップレットノードは、エポック単位でブロックチェーンがkブロック成長したら、そのk個のブロックをs個(例えばs = 10)のドロップレットに符号化する。

SeFでは噴水符号と呼ばれる消失符号をベースにしてブロックをドロップレットにエンコードする。ドロップレットから元のブロックを復号する場合は、元のブロックの数より僅かに多い数分ドロップレットを収集し、そのドロップレットをデコードすることでブロックの復元ができる。

SeFでは基礎的な噴水符号であるLT(Luby Transform)符号を使用し、以下の手順でk個ブロックからs個のドロップレットに符号化する。

f:id:techmedia-think:20190826094722p:plain
SeFエンコード処理

  1. 最初にランダムに1〜kの範囲内の数値を選択する。この数値をdとする。
  2. エポックで取り扱うk個のブロックの中からランダムにd個のブロックを選択する。
  3. 選択したd個のブロックについてビット単位のXORを取り、その結果をドロップレットとする。ドロップレットの計算に使われたd個のブロックのことをそのドロップレットに対するネイバーと呼ぶ。
  4. 続いて長さkのバイナリベクトルを生成し、m番目のブロックがこのドロップレットの計算に含まれている場合は1、そうでない場合は0をセットする。これがドロップレットに対するd個のブロックのインデックス情報となる。
  5. 4で計算したインデックス情報と一緒に3のドロップレットを保存する。

上記、エンコードが済むとs個の符号化されたブロックが生成され、それを保存し、元のブロックは削除し、エンコード処理は次のエポックへ進む。

このようにして符号化するとk個のブロックがs個のドロップレットになるので、ノードが保存するデータのサイズはs/kに削減できる。例えば k = 10,000でs = 10であれば、データサイズは1/1000になる。Bitcoinの場合、現在の215GBのデータが215MBになる。

reorgへの対応

reorgが発生するとブロックチェーンの一部のブロックが変わる可能性があるため、直近τブロック(例えばτ=550)のブロックはドロップレットにエンコードから除外され、そのまま保存する。

デコーディング

新たにネットワークに参加するバケットノードは、最初に十分な数のn個のドロップレットノードに接続し、 {1 ≦ l ≦ e}個のドロップレットを収集する( e = (t - τ) / kで、tは現在のブロック高)。またまだ符号化されていないブロックを入手するため、1つもしくはそれ以上のドロップレットノードからτ個分のブロックを別途ダウンロードする。

バケットノードはまず最初に最長チェーンのブロックヘッダーをダウンロードしておく(ドロップレットノードもブロックヘッダーは全て保持している)。続いて、各ドロップレットノードから収集したドロップレットを使って、以下の手順でブロックチェーンを復元する。

f:id:techmedia-think:20190826111647p:plain
2部グラフの例:k = 6、ns = 9 ドロップレットの初期2部グラフ

  1. k個のオリジナルのブロックと、収集したドロップレットを使って2部グラフを形成する。各ドロップレットは何番目のブロックがそのドロップレットの生成に関与したか示すインデックスを持っているので、各ドロップレットからブロックに対して接続するエッジがある。
  2. 2部グラフの中からブロックとドロップレットノードの接続が1つだけのブロックを見つける。このようなドロップレットをシングルトンと呼ぶ(↑の図では {C_4}がシングルトン)。
  3. 見つかったシングルトンのヘッダー*1が、最初にダウンロードしているブロックヘッダーと一致するか検証する。またシングルトンのペイロード(ヘッダーより後ろのデータ)からトランザクションのマークルツリーを構築し、そのルートがブロックヘッダーのマークルルートと一致するか検証する。
    • これが一致する場合、このドロップレットは対象のブロックをデコードできたことになる。
    • 一致しない場合、このドロップレットは濁っているのでこのドロップレットを2部グラフから削除する。
  4. 上記のグラフで言うと {C_4}により {B_3}がデコードされたので、 {B_3}と繋がっている他のドロップレット( {C_1, C_2, C_6, C_8})に対して、 {B_3}とbit単位のXORを取り各ドロップレットを更新する。そして、 {B_3}との接続を削除し、2部グラフを更新する。
  5. 全てのブロックがデコードされるまで、2〜4を繰り返す。

上記のようにデコード済みのブロックのデータを各ドロップレットから除去するということを繰り返すことで、新たなシングルトンができそれによりブロックがデコードできるというプロセスを繰り返すことになる。

ちなみに収集したドロップレットに、シングルトンが存在しない場合、ノードは追加のドロップレットノードに接続し、シングルトンが見つかるまでドロップレットを収集する。

上記のデコードを繰り返すことで、ネットワークに新しく参加したノードは、ストレージ制約のあるノードから収集したドロップレットを使ってブロックチェーンのデータを復元できる。

悪意あるノードによるドロップレットの細工

中には悪意のあるノードがいて、正しくないドロップノードを提供するパターンも考えられる。SeFでは単純なLT符号に加えて、上記のデコード処理でシングルトンのヘッダーおよびペイロードと予めダウンロードされた正しいブロックヘッダーの値を比較することで、このような汚れたドロップレットを区別し、処理するように設計されている。

所感

以上が全ブロックチェーンのデータを保持せずストレージ負担を削減しながらも、他の新規参入ノードのブロックチェーンIBDを支援できるノード実装の提案。

  • ネットワークを維持するためには今のところ(既存の軽量クライアントやプルーニングノードでは提供できない)IBDを支援できるノードの存在は重要。
  • 今までそれは全てのデータを保持するフルノードしか無かったので、ネットワークを分散ストレージとみなして、データを再構成するアプローチも興味深い(XOR演算ベースのLT符号とか他にもいろいろ利用できそう)。

*1:(ドロップレットは複数のブロックをXORしたものなので、先頭80バイトはブロックヘッダー)