各ブロックについて、ブロックに関連する項目のセット(例えば送信先のアドレスや使用されたoutpointなど)を含むコンパクトフィルタが導出される。このようなデータオブジェクトのセットはGolomb-coded set (GCS)と呼ばれる確率構造に圧縮される。この確率構造はセット内のアイテムであれば確率1でマッチし、セット内にないアイテムがマッチする確率はある整数パラメータMに対して1/Mである。エンコーディンは剰余符号のビット長であるPによってもパラメータ化される。定義された各フィルターはPとMの値を指定する。
hash_to_range(item: []byte, F: uint64, k: [16]byte) -> uint64:
return (siphash(k, item) * F) >> 64
hashed_set_construct(raw_items: [][]byte, k: [16]byte, M: uint) -> []uint64:
let N = len(raw_items)
let F = N * M
let set_items = []
for item in raw_items:
let set_value = hash_to_range(item, F, k)
set_items.append(set_value)
return set_items
golomb_encode(stream, x: uint64, P: uint):
let q = x >> P
while q > 0:
write_bit(stream, 1)
q--
write_bit(stream, 0)
write_bits_big_endian(stream, x, P)
golomb_decode(stream, P: uint) -> uint64:
let q = 0
while read_bit(stream) == 1:
q++
let r = read_bits_big_endian(stream, P)
let x = (q << P) + r
return x
gcs_match(key: [16]byte, compressed_set: []byte, target: []byte, P: uint, N: uint, M: uint) -> bool:
let F = N * M
let target_hash = hash_to_range(target, F, k)
stream = new_bit_stream(compressed_set)
let last_value = 0
loop N times:
let delta = golomb_decode(stream, P)
let set_item = last_value + delta
if set_item == target_hash:
returntrue// Since the values in the set are sorted, terminate the search once// the decoded value exceeds the target.if set_item > target_hash:
break
last_value = set_item
returnfalse
gcs_match_any(key: [16]byte, compressed_set: []byte, targets: [][]byte, P: uint, N: uint, M: uint) -> bool:
let F = N * M
// Map targets to the same range as the set hashes.
let target_hashes = []
for target in targets:
let target_hash = hash_to_range(target, F, k)
target_hashes.append(target_hash)
// Sort targets so matching can be checked in linear time.
target_hashes.sort()
stream = new_bit_stream(compressed_set)
let value = 0
let target_idx = 0
let target_val = target_hashes[target_idx]
loop N times:
let delta = golomb_decode(stream, P)
value += delta
inner loop:
if target_val == value:
returntrue// Move on to the next set value.elseif target_val > value:
break inner loop
// Move on to the next target value.elseif target_val < value:
target_idx++
// If there are no targets left, then there are no matches.if target_idx == len(targets):
break outer loop
target_val = target_hashes[target_idx]
returnfalse
Bitcoinの軽量クライアントを使用すると、すべてのデータをダウンロードして検証することなく、ブロックチェーンから自分に関連するトランザクションを読み取ることができる。このようなアプリケーションは同時に、ピアへの信頼や帯域幅、ストレージ容量および計算量を最小化しようとする。軽量クライアントはすべてのブロックヘッダをダウンロードし、Proof of Workを検証し、一番長いProof of Workのチェーンを選択することでこれらを実現している。ブロックヘッダは80バイト固定で、平均10分毎に生成されるので、ブロックヘッダの同期に必要な帯域幅は最小限に抑えられる。その後軽量クライアントは、自身に関連するブロックチェーンデータのみをピアから直接ダウンロードし、それがヘッダーチェーンに包含されているか検証する。軽量クライアントは一番長いProof of Workのチェーンのすべてのブロックの有効性はチェックせず、セキュリティためのマイナーのインセンティブに頼っている。
クライアントはまずブロックフィルタやフィルタヘッダをダウンロードする前に、標準のヘッダファーストの仕組みを利用してピアからすべてのブロックヘッダの同期をする必要がある。トラステッドチェックポイントを構成するクライアントは、最後のチェックポイントからヘッダの同期を開始するだけでいい。クライアントは接続先のピアのベストチェーンが既知の最長のProof of Workのチェーンよりも大幅に作業量が少ない場合、そのアウトバウンドピアとのコネクションは切断する必要がある。
ProvisionsのプロトコルにFiat-Shamirヒューリスティックを利用することで非対話型のプロトコルになるが、この場合trusted setupが必要になる。trusted setupはしたくないので、将来的にzk-SNARKsなどを利用したproof of solvencyを模索してる模様。
Scaling Bitcoin 2017のFlyClientの内容を追っていったら前提としてNiPoPoWs(Noninteractive-Proofs-of-Proof-of-Work)→ PoPoWs(Proofs of Proof of Work)と関連研究が続くので、まず最初にProofs of Proof of Workのプロトコルについて調べてみる。
Proof of Workの検証
Bitcoinのブロックチェーンでフルノードはジェネシスブロックから全てのブロックをダウンロードし、そのProof of Workが正しいか検証をすることで正しいチェーンであることを確認する。接続先のノードが偽の情報を流すことも考えられるため、複数のノードと接続し、接続先のノードによって異なるブロックチェーンが返ってくるケースでは、よりProof of Workが行われている方(長いチェーン)を正しいチェーンとして採用する。
SPVノードではブロック全体をダウンロードすることは無いが、ブロックヘッダを全てダウンロードし同様の検証を行う。これらの検証は最もProof of Workが行われたチェーンを検証していると言っても良い。ブロックヘッダのデータサイズは80バイトと小さいが、そのデータ自体は今後も線形に増えていく。
ノードを初回起動し最新のブロックを入手するまでブロックデータをダウンロードするIBD(Initial Block Download)では、各トランザクションの検証や正しいProof of Workが行われているかの検証にCPUリソースを消費し、チェーンが長くなるほどのそのリソース使用量と時間がかかるようになっており、IBDをいかに速くするかは重要な課題の1つになっている。基本的には各ソフトウェアがチェックポイントを設け、そこのブロックまではこういった検証をスキップすることでIBDを高速化する方法が採用されており、以前よりも高速にIBDが行えるようになっているが、これは同時にソフトウェアへのメンテナーへのトラストポイントが出来ているとも言える。
フルブロックをダウンロードしないSPVはフルノードに比べるとその検証は、ジェネシスブロックから最新ブロックまでチェーンのProof of Workの正しさを検証するだけなので比較的軽い処理ではあるが、今後もブロックが線形に成長していくことを考えると、より効率的なProof of Workの検証が求められる。このプロトコルを提案しているのがAggelos Kiayiasらによる「Proofs of Proofs of Work with Sublinear Complexity」というホワイトペーパーだ↓
基本的にブロックヘッダを全てダウンロードしてProof of Workを検証する現在の方法の計算量はチェーンの長さに対して線形になるが、Proofs of Proof of Workではチェーンの長さに準線形な計算量で済むよう設計されており、既存のSPVと比べてより効率的で軽量なSPV検証を可能にする。
線形に増えていくブロックヘッダを全て計算するから計算量が線形になるのであって、間引いた状態でもProof of Workの正しさを検証できれば計算量を減らすことができる。このとき間引いてできるブロックチェーンをinterconected blockchainと呼ぶ。
Proofs of Proof of Workのホワイトペーパーのプロトコルは、ターゲットTが動的に変化するケースの分析や、PoWの検証が場合にを使ったものに及ぶと必要に応じて相手のノードに追加の問い合わせが必要となる対話型のプロトコルといった課題がある。後者の部分を改善したのがNiPoPoWs(Noninteractive-Proofs-of-Proof-of-Work)のプロトコルになるので、その内容についてはまた今度見てみたい。
ブロックチェーンはマイナーと呼ばれる動的に変化するプレーヤーのセットによって維持されている。各マイナーの主な仕事はproof of workを解決し次のブロックを見つけることだ。トランザクションはブロックチェーンに追加する際に検証される。特定のトランザクションの確実性は、ブロックチェーンの深さと関連付けられる。ブロックチェーンのより深い場所にあるトランザクションほどそのトランザクションの確実性は増す。これはもともと正直なプレーヤーは一致して行動し敵対者は特定の戦略に従うという単純化されたモデルだった。正直なプレーヤーが分散し敵対者がこれを利用する可能性がある状況におけるセキュリティは、その後正式に検討されThe Bitcoin Backbone Protocol: Analysis and Applicationsで証明された。この後の研究では2つの特性が紹介された。共通のプレフィックスとチェーンの品質だ。パラメータkで圧倒的な確率で正直なプレイヤーがブロックチェーンの同じプレフィックスに同意することが示された。kブロック経過したチェーンは正直なプレイヤーによっと生成されたブロックを一定の割合含むだろう。これらの2つの特性は、台帳内のトランザクションは永続的で台帳自体が活性的である、つまり敵対者が新しいトランザクションを無期限に抑止することは不可能であることを示している。
上記の解決先の重要な考察は、ブロックチェーンの線形の計算量以下に改善することが一見不可能な点だ。確かに検証者が準線形の計算量しか許可されないようなケースでは、受信したブロックチェーン内の全てのproof of workが有効であるか検証することはできない。この方法では与えられたブロックチェーンの断片しか確認することができず、攻撃者がジェネシスブロックと実は関連が無いが一見有効そうなブロックチェーンの断片を事前に準備することで、攻撃者に潜在的な攻撃の機会を作るかもしれない。
Our Results
本研究では、ブロックチェーンの長さに準線形な計算量を持つproofs of proof of workを構築する方法を提示する。これらの証明はフルSPV検証と比べて実質より効率的で軽量なSPV検証を可能にする。我々の解決策では現在のBitcoinのコードベースの変更が必要になる。これにより各ブロックには小さなオーバーヘッドが発生する。これはブロックチェーンの長さの対数を超えることはなく、ブロックチェーンを単一のハッシュに圧縮することができる。これによりinterconnected blockchainと呼ばれる特別なタイプのブロックチェーンが誕生する。
我々の解決方法では、軽量な検証者は()のペアを受け取る。ここでは送信者のチェーンの右端kブロックに相当するブロックチェーンの断片で、はプルーニングされたチェーンが表す(で表される)proof of workの証明である。証明を構築するには以下の仕組みを使う。
ブロックチェーン内の各ブロックは、不等式H(w) < Tを満たすように作られた値wに対応するproof of workに関連付けられていることを思い出して欲しい。ここでHはハッシュ関数(Bitcoinの場合はSHA-256)で、Tはターゲット計算関数で与えられる難易度のターゲットである。
続いて、との中に共通のブロックxがないか確認する。この確認はどっちのチェーンのproof of workがより容易か見つけるために行う。具体的には直近kブロックでとの間にフォークが発生していることを意味する。そのため、軽量な検証者は両者のうちProof of Workがより良い方(同じTに対してxの後により多くのブロックがある方)のsuffixを選択する。
suffixの中に共通のブロックが無い場合は、アルゴリズムを実行し、どっちのプルーフが最も優れたProof of Workか決定する。このアルゴリズムはAとBにさらなる相互作用を求め、以下のように動作する。
続いてMaxChainのアルゴリズムについて説明する。分岐したが与えられると、アルゴリズムはsuffixが十分長い(長さはセキュリティパラメータにmより決まる)限り、最も多くのProof of Workを行ったプルーフを選択する。ただ、アルゴリズムがどちらか決定できない場合は、より小さい深さのプルーフをAとBに要求し、必要に応じてレベル0まで再帰的に行うことでパラメータmとは独立して決定する。これらの再帰ステップの途中で通信ノードA、Bのうち1つが、そのプルーフのサポート(軽量ノードが要求した追加ブロックを提供するの)に失敗するとMaxChainアルゴリズムはもう1方のノードのチェーンが正しいチェーンであると結論付ける(もしくはノードがリクエストに応答しない場合は失敗する)。より詳細には以下のように動作する。
次にアルゴリズムは、どちらのプルーフがよりProof of Workを行っているかチェックする。の場合は少なくとも長さm、の場合は少なくともの長さがあれば最良なProof of Workのプルーフと判断される。この場合、セキュリティパラメータmに依存した決定がされることに注意すること。
最良のProof of Workであると判断するのにプルーフが十分でない場合、アルゴリズムは共通のprefixを使用せず、BもしくはAとBの両方にチェーンのより深い部分のプルーフを問い合わせ、それを再帰的に継続する。bをルートとするチェーンでより小さいハッシュ値を持つプルーフのBからのリクエストを表すのにを使用する。同様に、プレイヤーAに対して同じように機能する。
最終的にアルゴリズムは、十分長いもしくは、proof of workの量のみに基いて決定される(実際のターゲットTが使用される)深さ0に達する分岐suffixを入手する。これによりどちらが正しいプルーフかが決まり、軽量な検証者は別の比較やプロセスを終了する。
プルーフのサイズについて分析する。ここでは敵対者が正直な関係者のプルーフを妨げるような深いフォークを作成していない=敵対者が送信するk-suffixに正直な証明者によって送信されたプルーフのsuffixで共通のブロックが存在する楽観的なシナリオにフォーカスする。正直な関係者はk-suffixより前にチェーンの一部が分岐していることはない(kはそれだけ圧倒的な確率を持つため)。このようなケースでは、軽量な検証者は証明者と余計なやりとりをすることなく最も実証されたproof of workのチェーンを選択することができる。従ってプルーフのサイズはConstructProofアルゴリズムのアウトプットになる。
我々はThe Bitcoin Backbone Protocol: Analysis and Applicationsの分析を行う。彼らのモデルでは、ブロックチェーンを維持するn個のパーティがあり、(ランダムオラクルモデルと考えられる)ハッシュ関数へのq個のクエリが許可され、パーティの内t個は敵の制御下にある。1回のハッシュクエリでProof of Workを見つける確率は(ターゲットはTで安定)。彼らのホワイトペーパーと同じ表記を使用しとする。直感的にαは正直なパーティのハッシュパワーを表す。これは正直なパーティが1つのラウンドで得る予定の解の上限でもある。一方βは敵が1回のラウンドで得る解の予想数である。最後にγは正直なパーティの1人がProof of Workの解を見つけるラウンドの期待値である。