Proofs of Proof of Work - Develop with pleasure!

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をいかに速くするかは重要な課題の１つになっている。基本的には各ソフトウェアがチェックポイントを設け、そこのブロックまではこういった検証をスキップすることでIBDを高速化する方法が採用されており、以前よりも高速にIBDが行えるようになっているが、これは同時にソフトウェアへのメンテナーへのトラストポイントが出来ているとも言える。

フルブロックをダウンロードしないSPVはフルノードに比べるとその検証は、ジェネシスブロックから最新ブロックまでチェーンのProof of Workの正しさを検証するだけなので比較的軽い処理ではあるが、今後もブロックが線形に成長していくことを考えると、より効率的なProof of Workの検証が求められる。このプロトコルを提案しているのがAggelos Kiayiasらによる「Proofs of Proofs of Work with Sublinear Complexity」というホワイトペーパーだ↓

http://fc16.ifca.ai/bitcoin/papers/KLS16.pdf

今までは各ブロックが前のブロックのハッシュを参照するハッシュチェーンを形成することでブロックチェーンを構築しており、それを辿ってチェーンの有効性を検証していたが、この仕組みをinterconnected blockchainと呼ばれる仕組みに変える。

※ 既存のBitcoinのプロトコルのままではできないので、実現する場合はプロトコルの拡張やさらなる分析が必要。

Interconnected Blockchain

基本的にブロックヘッダを全てダウンロードしてProof of Workを検証する現在の方法の計算量はチェーンの長さに対して線形になるが、Proofs of Proof of Workではチェーンの長さに準線形な計算量で済むよう設計されており、既存のSPVと比べてより効率的で軽量なSPV検証を可能にする。

線形に増えていくブロックヘッダを全て計算するから計算量が線形になるのであって、間引いた状態でもProof of Workの正しさを検証できれば計算量を減らすことができる。このとき間引いてできるブロックチェーンをinterconected blockchainと呼ぶ。

ではどうやってinterconnected blockchainを構築するのか？

基本的にマイニングというのは予め定められたターゲット以下のハッシュ値を見つける競争で、 ${H(w)＜T}$ を満たすブロックを作ること（Hはハッシュ関数でTはターゲット）になる。マイニングの成功条件はターゲット以下であることだけど、見つかるハッシュはTに近い値だったり、T/2以下だったりT/3以下だったりT/4以下だったりする。そこで ${T / 2^{i}}$ より小さいハッシュが見つかったときに、そのハッシュを深さ（i）と一緒にピックアップしそれらでinnerchainを形成する。

例えば以下のような11個のブロックがある場合（1はジェネシスブロック、ブロック4,7,9がT/2(i = 1)より小さいハッシュを持ち、ブロック7がT/4(i = 2)より小さいハッシュを持つ）

f:id:techmedia-think:20180107153242p:plain

深さ1の ${innerchain_1}$ はブロック1,4,7,9で構成され、深さ2の ${innnerchain_2}$ はブロック1,7で構成される。

また各ブロックは現状のブロック構造に加えて新たにinterlinkと呼ばれるデータ構造を加えることになる。これはブロックのポインタのリストで ${interlink = \langle s_0, ..., s_l \rangle}$ のように表す。ここで ${s_0}$ はジェネシスブロックへのポインタで、 ${s_i}$ は ${T/2^{i}}$ より小さいハッシュ値を持つ前のブロックへのポインタとなる。

↑の11個のブロックにそれぞれのブロックが持つinterlinkを割り当てると以下のようになる。

f:id:techmedia-think:20180107160610p:plain

ブロック4までは ${T/2}$ より小さいハッシュは存在しないので、interlinkは<1>になる。ブロック5からはブロック4が ${T/2}$ より小さいハッシュを満たしているのでinterlinkは<1, 4>となる。ブロック7で ${T/4}$ のブロックが見つかる。ここでブロック8は<1,4,7>になるかと思うけど、interlinkの2つめの要素( ${s_1}$ )は ${T/2}$ より小さいハッシュの条件を満たす直近のブロックなので7になり、3つめのinterlinkの要素( ${s_2}$ )は ${T/4}$ より小さいハッシュの条件を満たす直近のブロックなのでこれも7で、結果<1, 7, 7>となる。ブロック9で ${T/2}$ より小さいハッシュを満たすブロックが見つかると ${s_1}$ を満たす最新が9になるのでブロック10からのinterlinkは<1, 9, 7>に変わる。

このように ${T/2^{i}}$ より小さいハッシュをもつブロックで構成するブロックチェーンをInterconnected Blockchainと呼んでいる。

Interconnected Blockchainを使ったPoWの証明

従来のSPVノードがチェーン全体のPoWを受け取るのに対し、このプロトコルでは軽量ノードはフルノードから ${(\mathcal X, \pi)}$ のペア（PoWの一部）を受け取る。ここで ${\mathcal X}$ はフルノードのローカルチェーンCの右端kブロック分に相当するブロックチェーンの断片で、 ${\pi}$ はローカルチェーンCからkブロック分取り除いたチェーン ${C^{\lceil k}}$ の、長さが少なくともm（mはセキュリティパラメータ）あり深さが一番深いinnnerchainを指す。

軽量ノードはローカルチェーン ${C_A}$ と ${C_B}$ を持つフルノードA, Bからそれぞれ ${(\mathcal X_A, \pi_A)}$ のペアと ${(\mathcal X_B, \pi_B)}$ のペアを受け取り、どちらが正しいProof of Workが行われたチェーンか検証する。

${\pi_A}$ と ${\pi_B}$ の長さが少なくとも（セキュリティパラメータ）mより長いかチェックする。mより短ければこの時点でリジェクト。
${\mathcal X_A}$ と ${\mathcal X_B}$ の中に共通のブロックが無いかチェックする。共通のブロックが見つかり、かつ ${\mathcal X_A}$ と ${\mathcal X_B}$ が異なる場合は直近kブロックで ${C_A}$ と ${C_B}$ がフォークしていることになる。この場合簡単で ${\mathcal X_A}$ と ${\mathcal X_B}$ のどちらが長いかチェックし、長い方を正しい証明と判断すれば良い。
2で共通のブロックが見つからなかった場合、 ${\pi_A}$ と ${\pi_B}$ から、どちらの証明がより沢山の計算をしたProof of Workか判定する必要がある。この場合AとBで共通のprefixを見つける必要があり、AとBに深さが小さいチェーンについて追加の問い合わせが必要になる可能性もある。

3の追加検証についてはホワイトペーパー参照。

正直なノードと悪意あるノードにそれぞれ繋がっている場合、↑のように共通のブロックを持つ断片があればどちらのPoWが正か判定できるが、共通のブロックが無い場合が悪意あるユーザーの攻撃ポイントになり、深さが0になるまで軽量ノードに計算と問い合わせを余計にさせるような攻撃が考えられる。ただ実際に軽量ノードにこういった計算量を増やすためには、悪意あるノードはより計算リソースを投入して沢山の偽ブロックを作成する必要があり、そこまでして攻撃が成功する確率も無視できるレベルに低いためホワイトペーパーの性能分析ではそこは省かれている。

データ量と計算量

データ量

Interconnected Blockchainでは各ブロックにinterlinkを新たに追加する必要があり、この分データ量が増える。ホワイトペーパーでは以下のようにT=2²⁰⁰で安定してる際に、interlinkのサイズは（チェーンの長さ）nの対数で安定するとしている。ホワイトペーパーのFigure 2参照。

マークルツリーを使ったinterlinkの圧縮

interlinkはブロックのポインタのリストなので、これをマークルツリーを使って圧縮する方法もある。この場合、ブロックに追加するのはこのマークルツリーのルートハッシュのみで固定サイズになる。

計算量

複数のフルノードから受信したkブロック分の ${\mathcal X}$ に共通のブロックが存在していれば、追加の問い合わせをフルノードにする必要はない。この場合、軽量ノードは受信した証明 ${\pi}$ のサイズに比例した検証を行う必要があり、その計算はセキュリティパラメータをm、チェーン全体の長さをnとした場合、O(m log n)と準線形になる。またマークルツリーを使ってinterlinkを圧縮した場合、これはO(m log log n)に改善される。

所感

既存のSPVはチェーン全体のPoWを送信して検証するのに対し、このホワイトペーパーでは定量サイズのPoWのサンプルを使って検証している。その仕組みのベースになってるのがターゲットTよりさらに小さい（ ${T/2^{i}}$ 未満）ハッシュを集めて構成するinnerchain。より小さいハッシュを使うアイディア自体はBitcoin Forumに投稿されたもの。こういう形でチェーンの検証をスキップする仕組みが成立するのは面白い。

ただ定理含めて理解できてないところも多いので、その辺は個人的にちゃんとした理解のための課題が残る。

Proofs of Proof of Workのホワイトペーパーのプロトコルは、ターゲットTが動的に変化するケースの分析や、PoWの検証が場合に ${\pi}$ を使ったものに及ぶと必要に応じて相手のノードに追加の問い合わせが必要となる対話型のプロトコルといった課題がある。後者の部分を改善したのがNiPoPoWs（Noninteractive-Proofs-of-Proof-of-Work）のプロトコルになるので、その内容についてはまた今度見てみたい。

以下は、ホワイトペーパーのざっとした訳↓（正確な内容はホワイトペーパー参照）

イントロダクション

Nakamotoによって導入されたBitcoin及び、同じコードベースを使って開発された他の多数の分散型暗号通貨は、ブロックチェーンベースの取引台帳が中核になっている。これらのシステム台帳は、トランザクションがブロックに編成された分散データ構造を持つ。ブロック自体はハッシュチェーンを形成し、各ブロックにはProof-of-Workパズルが関連付けられ、1つ前のブロックを指し示す。有効なブロックチェーンは分散台帳をサポートするクライアントソフトウェアにハードコードされたジェネシスブロックに根ざしている。

ブロックチェーンはマイナーと呼ばれる動的に変化するプレーヤーのセットによって維持されている。各マイナーの主な仕事はproof of workを解決し次のブロックを見つけることだ。トランザクションはブロックチェーンに追加する際に検証される。特定のトランザクションの確実性は、ブロックチェーンの深さと関連付けられる。ブロックチェーンのより深い場所にあるトランザクションほどそのトランザクションの確実性は増す。これはもともと正直なプレーヤーは一致して行動し敵対者は特定の戦略に従うという単純化されたモデルだった。正直なプレーヤーが分散し敵対者がこれを利用する可能性がある状況におけるセキュリティは、その後正式に検討されThe Bitcoin Backbone Protocol: Analysis and Applicationsで証明された。この後の研究では2つの特性が紹介された。共通のプレフィックスとチェーンの品質だ。パラメータkで圧倒的な確率で正直なプレイヤーがブロックチェーンの同じプレフィックスに同意することが示された。kブロック経過したチェーンは正直なプレイヤーによっと生成されたブロックを一定の割合含むだろう。これらの2つの特性は、台帳内のトランザクションは永続的で台帳自体が活性的である、つまり敵対者が新しいトランザクションを無期限に抑止することは不可能であることを示している。

この研究ではsimplified payment verification（SPV）の問題について研究する。Bitcoinのホワイトペーパーで紹介されたこの問題は台帳の最近のトランザクションを調べたい検証者を考慮している。検証者はインプットとしてトランザクションの識別子を持つ。検証者はこの情報だけでそのトランザクションが高い確率で台帳に含まれていることを検証し、高い確率でそのトランザクションが台帳に残っていることを確かめたいと考える。上記に基づき、以下のようなSPV検証を簡単に実装することができる。検証者はネットワークに問い合わせ、直近kブロックを除くほとんどのブロックのブロックヘッダを含むさまざまなブロックチェーン（悪意あるユーザーによって作られたチェーンを含め）を受け取る（このような通信は“SPV proofs”と呼ばれる）。検証者は受信したチェーンの完全性を検証し、最も多くの作業をしているチェーンを1つ選択する。最後に探しているtxが深さkで見つかったらトランザクションは有効であると結論付けることができる。このSPVのオペレーションは、全てのトランザクション履歴を受信して検証する必要がないためフルノードを実行するより効率的だ。

上記の解決先の重要な考察は、ブロックチェーンの線形の計算量以下に改善することが一見不可能な点だ。確かに検証者が準線形の計算量しか許可されないようなケースでは、受信したブロックチェーン内の全てのproof of workが有効であるか検証することはできない。この方法では与えられたブロックチェーンの断片しか確認することができず、攻撃者がジェネシスブロックと実は関連が無いが一見有効そうなブロックチェーンの断片を事前に準備することで、攻撃者に潜在的な攻撃の機会を作るかもしれない。

Our Results

本研究では、ブロックチェーンの長さに準線形な計算量を持つproofs of proof of workを構築する方法を提示する。これらの証明はフルSPV検証と比べて実質より効率的で軽量なSPV検証を可能にする。我々の解決策では現在のBitcoinのコードベースの変更が必要になる。これにより各ブロックには小さなオーバーヘッドが発生する。これはブロックチェーンの長さの対数を超えることはなく、ブロックチェーンを単一のハッシュに圧縮することができる。これによりinterconnected blockchainと呼ばれる特別なタイプのブロックチェーンが誕生する。

我々の解決方法では、軽量な検証者は( ${\mathcal X, \pi}$ )のペアを受け取る。ここで ${\mathcal X}$ は送信者のチェーンの右端kブロックに相当するブロックチェーンの断片で、 ${\pi}$ はプルーニングされたチェーンが表す（ ${C^{\lceil k}}$ で表される）proof of workの証明である。証明 ${\pi}$ を構築するには以下の仕組みを使う。

ブロックチェーン内の各ブロックは、不等式H(w) < Tを満たすように作られた値wに対応するproof of workに関連付けられていることを思い出して欲しい。ここでHはハッシュ関数（Bitcoinの場合はSHA-256）で、Tはターゲット計算関数で与えられる難易度のターゲットである。

我々の新しい仕組みは次のように動作する。通常より小さいハッシュを持つブロックが生成される度に、次のブロックでより深いチェーンの続きとしてマークする。これを深さiのinnerchainと呼ぶ。iはH(w) < T/2ⁱ を維持する最大の整数。具体的には、各ブロックはポインターのベクトルを運ぶ（これは複数のレベルにまたがるブロックチェーン内の標準的な逆方向リンクを拡張すると考えることができる）。このように変更されたブロックチェーンでは、ブロックは ${interlink = \langle s_0, ..., s_l \rangle}$ と表されるポインターのベクトルを持つ。ここで ${s_0}$ はジェネシスブロックを指し、i = 1, . . . , lと続く。 ${s_i}$ は前のブロックを指し、 ${\mathit T / 2^{i}}$ より小さいハッシュ値を持つ前のブロックを指す。lはブロックチェーン内のハッシュがT /2^lより小さい最大の整数であることに注意する ${s_l}$ は最新のそのようなハッシュのポインタである）。

プルーフ ${\pi}$ の構築方法は以下の通り。送信者はローカルチェーンCからk-suffixを取り除きそれを ${\mathcal X}$ とする。次に、残りのプレフィックスである ${C^{\lceil k}}$ について、少なくとも長さがm（mはセキュリティパラメータ）ある最も深いinnerchain ${\pi}$ を探す。この ( ${\mathcal X, \pi}$ ) のペアがプルーフとなり軽量な検証者に送られる。攻撃者が積極的に干渉しない楽観的なシナリオにおいては、軽量な検証者と証明者間で対話は必要無い。一般的な場合、攻撃者は唯一、軽量検証者と証明者との間の通信量を増加させる目的で、非常に小さいターゲットを持つブロックを生成するためにハッシュパワーを投入することが考えられる。そのようなケースでは軽量な検証者は完全な検証のため証明者とのさらなる対話を行う必要がある。

最後に軽量SPV プルーフのセキュリティの正式な取り扱いについて説明する。この議論はシミュレーションベースの議論である。軽量検証者のセキュリティは以下の声明で捉えることができる。軽量検証者向けのSPV プルーフを生成するどんな敵にとっても、同じ結果をもたらす通常のSPVに検証者むけのSPV プルーフを生成する敵が存在する。上記のセキュリティ条件をm内で圧倒的確率で確立する。mは軽量検証プロトコルのパラメータ。

我々の構成では、軽量検証者の計算量は楽観的なケースではO(m log n)で、これは簡単にO(m log log n)に改善できる。ここでnはマークルツリーを使用したブロックチェーンの長さ。

序文

ホワイトペーパーではBitcoinのバックボーンプロトコルの表記方法に従う。以下にいくつかの基本的な表記方法と用語について紹介する。

${G(.), H(.)}$ は ${\{ 0, 1 \}^{K}}$ のアウトプットを持つ暗号学的ハッシュ関数。
ブロックBは ${B = ⟨s, x, ctr⟩}$ の形式で表現される。ここで ${s \in \{0, 1\}^{K}}$ 、 ${x \in \{0, 1\}^{*}}$ 、 ${ctr \in \mathbb N}$
ラウンドはネットワーク内の全関係者が同期して互いのメッセージを入手するまでの期間。メッセージのスケジューリングは敵対者によって制御される。さらに、各ラウンドにおいて、敵対者は任意の数のメッセージを生成し、それを選択的に関係者に配信できる。
チェーンCの右端のブロックはhead(C)で、 ${C^{\lceil k}}$ はチェーンCの右からkブロック取り除いたもの。 ${head(C) = ⟨s, x, ctr⟩}$ で前のブロックが ${⟨s', x', ctr'⟩}$ で ${s = H(ctr7, G(s', x'))}$ を保持する。一般的にすべてのブロックは前のブロックへの参照を有し、このためすべてのブロックはチェーンを形成する。
ブロックヘッダは ${⟨ctr, G(s, x)⟩}$ として定義できる。
proof of workは ${ctr : 0 \leq ctr}$ < ${2^{32}}$ の範囲で ${H(ctr, G(s, x))}$ < ${T}$ となる値を見つけること。 ${T \in \{0, 1\}^K}$ はブロックのターゲット。
xは情報がブロックに格納されていることを示す値。Bitcoin プロトコルの場合この情報は一連のトランザクションでマークルツリー形式で構成されている。

Interconnected Blockchains

proof of workのプルーフを生成するため、ローカルチェーンCを持つ証明者は ${\mathcal X}$ をそのローカルチェーンCのk-suffixに設定しプルーフ ${\pi}$ を計算して ${(\mathcal X, \pi)}$ のペアを生成する。プルーフ ${\pi}$ はチェーン ${C^{\lceil k}}$ の一部のブロックの集合を構成し、それは以下に詳述する方法で収集される。

プルーフ ${\pi}$ はプルーフの深さである整数 ${ i \in \mathbb N}$ に関連付けられる。プルーフに含まれるブロックは ${innerchain_i}$ と呼ばれる特別なタイプのチェーンによって決まる。

定義１

インデックス i > 0によってパラメータ化された ${innerchain_i}$ は、各ブロック ${B = ⟨s, x, ctr⟩}$ が ${H(ctr, G(s, x))}$ < ${T/2^{i}}$ を満たす特徴を持つチェーンCから派生した有効なチェーンである。

${innerchain_i}$ では、各ブロックは親チェーンCのターゲットTを持つ ${2^{i}}$ ブロックと同程度のproof of workを表していることが直感的に分かる。その結果、プルーフ ${\pi}$ がmブロックで構成されている場合、 ${innerchain_i}$ はターゲットTの ${m \cdot 2^{i}}$ ブロック分のproof of workを表す。

我々のシステムでは、プルーフを生成するために証明者は ${C^{\lceil k}}$ からi > 0の ${innerchain_i}$ を抽出すべきだ。これはすべての ${i \in \mathbb N}$ に対し、 ${T/2^{i}}$ より小さいハッシュを持つすべてのブロックがチェーンを形成すべきであることを意味し、interconnected blockchainという概念につながる。

${T/2^{i}}$ より小さいハッシュを持つすべてのブロックは、 ${T/2^{i}}$ より小さいハッシュを持つ前のブロックへのポインタを必要とする。これは通常のBitcoinのブロックチェーンには存在しないため、Cの各ブロックに一連のポインタを適切に変更する必要がある。interlink[]と呼ばれる各ブロックへのこのデータ構造の追加はinterconnected blockchainを生み出す。interconnected chainのグラフィカルな説明をFigure 1に示す。

f:id:techmedia-think:20180104175422p:plain — Figure 1: 深さ１のinnerchain（ブロック(1, 4, 7, 9)で構成される）と深さ２のinnerchain（ブロック(1, 7)で構成される）を含む１１個のブロックを持つinterconnected blockchainの図。各ブロックのinterlinkベクトルの値も表示されている。

各ブロックBに含まれるinterlinkのデータ構造は動的で以下に正式に定義する。ブロックBは ${B = ⟨s, x, ctr, interlink⟩}$ と、ブロックヘッダは ${⟨ctr, G(s, x, interlink)⟩}$ と定義される。

定義２

interlinkは各ブロックに含まれるベクトルで、すべてのi > 0について、, interlink[i]は ${\mathit T / 2^{i}}$ より小さいハッシュ値を持つチェーンC内のBの前のブロックハッシュである。interlink[0]はジェネシスブロックのハッシュとなる。

ベクトルの長さは、チェーンCに存在するブロックの種類に依存する。 ${B = ⟨s, x, ctr, interlink⟩}$ がチェーンの先頭で、 ${B' = ⟨s', x', ctr', interlink'⟩}$ が前のブロックとすると、この後説明するアルゴリズムで更新された後のinterlinkとinterlink'は等しくなる。

3.1 interlink-Updateアルゴリズムの説明

このアルゴリズムの目的は、interconnected chainを適切に形成するのに必要な動作を決定することだ。新しいブロックをマイニングする時は、使用される適切なポインタのセットを決定しなければならない。sで表される前のブロックのハッシュが与えられると、アルゴリズムは以下を実行する。

${s = H(ctr', G(s', x', interlink′'))}$ < ${T/2^{i}}$ を満たすiの最大値を見つける。
${i - i'}$ の要素を追加してinterlink′を拡張する。 ${i'}$ の値はsizeof(interlink′) (only if i′ < i)と等しい。
interlink[1],...,interlink[i]に ${H(ctr', G(s', x', interlink')) = s}$ を割り当てる。

f:id:techmedia-think:20180104230258p:plain

4. 準線形のProof of Workの証明

4.1 証明者（Proover）の説明

ローカルチェーンCを持つ証明者が軽量な検証者（Verifyer）から右端のkブロックを要求するリクエストを受け取ると、証明者はConstructProofアルゴリズムを使ってチェーン ${C^{\lceil k}}$ のProof of Workの証明 ${\pi}$ を構築する。

f:id:techmedia-think:20180105115310p:plain

このアルゴリズムのインプットは ${C^{\lceil k - 1}}$ で、そのアウトプットは ${innerchain_i = \pi}$ である。ここでiは最大のiで、チェーン ${C^{\lceil k}}$ には ${\mathit T / 2^{i}}$ より小さいハッシュ値を持つ少なくともm個ブロックが存在する（mはセキュリティパラメータ）。ConstructProofアルゴリズムは（以下に説明する）その次にConstructInChainアルゴリズムを呼び出す。

このアルゴリズムは（key, value）のペアを格納するデータ構造であるハッシュテーブルを使用する。このケースではハッシュテーブルにハッシュ値を持つブロックを格納する。ConstructInChainアルゴリズムはチェーンCとiをインプットとし、そのアウトプットはチェーン ${C^{\lceil 1}}$ 内で ${\mathit T / 2^{i}}$ より小さいハッシュ値を持つ全ブロックのチェーンである。

f:id:techmedia-think:20180105104031p:plain

軽量な検証者（Lite Verifier）の説明

軽量な検証者がチェーン ${C_A}$ とチェーン ${C_B}$ を持つ証明者AとBからそれぞれ ${(\mathcal X_A, \pi_A)}$ と ${(\mathcal X_B, \pi_B)}$ を受け取ったとする。目的はどちらの証明が最もproof of workを行ったチェーンのものか見つけることだ。

一般性を失うことなく、 ${\pi_A = innerchain_{\mu}}$ とするとそのブロックのハッシュ値は ${T' = \mathit T / 2^{\mu}}$ より小さい。
${\pi_B = innerchain_{i + \mu}}$ とするとそのブロックのハッシュ値は ${\mathit T / 2^{i + \mu} = \mathit T' / 2^{\mu}}$ より小さい ${(i \geq 0)}$ 。

まず軽量な検証者は ${\pi_A}$ と ${\pi_B}$ の長さがそれぞれジェネシス抜きでmより長いかsuffixの長さがkかどうかそれぞれ確認する。プルーフがこの特性を満たさない場合、無効なプルーフとしてリジェクトされる。

続いて、 ${\mathcal X_A}$ と ${\mathcal X_B}$ の中に共通のブロックxがないか確認する。この確認はどっちのチェーンのproof of workがより容易か見つけるために行う。具体的には直近kブロックで ${C_A}$ と ${C_B}$ の間にフォークが発生していることを意味する。そのため、軽量な検証者は両者のうちProof of Workがより良い方（同じTに対してxの後により多くのブロックがある方）のsuffixを選択する。

suffixの中に共通のブロックが無い場合は、 ${MaxChain [\pi_A, \pi_B ]}$ アルゴリズムを実行し、どっちのプルーフが最も優れたProof of Workか決定する。このアルゴリズムはAとBにさらなる相互作用を求め、以下のように動作する。

f:id:techmedia-think:20180105115924p:plain

MaxChainアルゴリズムはRemoveCPhighとRemoveCPlowという２つのサブプロシージャを使用する。 ${(\pi_A, \pi_B)}$ をインプットとするRemoveCPlowアルゴリズムは、共通のブロックをプルーニングし、 ${\pi_A^{\prime}}$ 、 ${\pi'_B}$ を共通のブロックの無いプルーフにセットし、 ${(\pi_A, \pi_B)}$ の中で最も直近のブロックにbをセットする。

${(\pi_A, \pi_B)}$ をインプットとするRemoveCPhighは、 ${\pi_B}$ で省略された ${\mathit T / 2^{\mu}}$ より小さいハッシュのブロックのチェーンについてBに問い合わせる。RemoveCPhighは ${(\pi_A^{\prime}, \pi'_B, b)}$ を返す。 ${\pi_A^{\prime}}$ 、 ${\pi_B^{\prime}}$ は共通のprefixが無いプルーフで、bは ${C_A}$ と ${C_B}$ の ${\mathit T / 2^{i + \mu}}$ より小さいハッシュ値を持つ最も最新の共通のブロックだ。より詳細には以下のように動作する。

証明は2つの配列にそれぞれ格納されている前提で、このアルゴリズムは ${\pi_A}$ 内のブロック ${\pi_B [1]}$ を探し、 ${\pi_A}$ 内にはない ${\pi_B [i']}$ を見つけるまで続ける。 ${\pi_B [i' - 1]}$ は ${\pi_A}$ に含まれるので ${\pi_A[j] = \pi_B[i' - 1]}$ となる。
${\pi_B [i' - 1]}$ から。 ${\pi_B [i']}$ の間に ${\mathit T / 2^{\mu}}$ より小さいハッシュ値を持つブロックの配列VをBに問い合わせる。Bから配列Vが返ってこない場合RemoveCPhighは失敗する。
${\pi_A [j']}$ が ${V [j' - 1]}$ とは異なるような最小の ${j′ \geq j + 1}$ を探す。
${\pi_B^{\prime}}$ は最初の ${i' - 1}$ ブロックが無い ${\pi_B}$ で、 ${\pi_A^{\prime}}$ は最初の ${j' - 1}$ ブロックが無い ${\pi_A}$ である。
${b = \pi_A [j' - 1]}$
${(b, \pi_A^{\prime}, \pi'_B)}$ を返す。

続いてMaxChainのアルゴリズムについて説明する。分岐した ${\pi_A, \pi_B}$ が与えられると、アルゴリズムはsuffixが十分長い（長さはセキュリティパラメータにmより決まる）限り、最も多くのProof of Workを行ったプルーフを選択する。ただ、アルゴリズムがどちらか決定できない場合は、より小さい深さのプルーフをAとBに要求し、必要に応じてレベル0まで再帰的に行うことでパラメータmとは独立して決定する。これらの再帰ステップの途中で通信ノードA、Bのうち１つが、そのプルーフのサポート（軽量ノードが要求した追加ブロックを提供するの）に失敗するとMaxChainアルゴリズムはもう１方のノードのチェーンが正しいチェーンであると結論付ける（もしくはノードがリクエストに応答しない場合は失敗する）。より詳細には以下のように動作する。

最初にアルゴリズムはRemoveCPlowを呼び出して、プルーニングされたsuffixを取得する（これは対話を必要としない）。続いてそれを ${i > 0}$ かチェックする。このケース時点でプルーフは異なる深さを持つので、アルゴリズムは ${\pi_B^{\prime}.pow \geq \pi_A^{\prime}.pow}$ と同時に ${\pi_B^{'}.length \geq m}$ かチェックする。この２つの条件が成立する場合、軽量な検証者は ${\pi_B}$ を選択する。そうでない場合アルゴリズムはプルーフ ${\pi_A, \pi_B}$ から共通のprefixを見つけるためRemoveCPhighを使用する（これはBとの対話が必要になる）。
次にアルゴリズムは、どちらのプルーフがよりProof of Workを行っているかチェックする。 ${\pi_B^{'}}$ の場合は少なくとも長さm、 ${\pi_A^{'}}$ の場合は少なくとも ${2^{i} m}$ の長さがあれば最良なProof of Workのプルーフと判断される。この場合、セキュリティパラメータmに依存した決定がされることに注意すること。
最良のProof of Workであると判断するのにプルーフが十分でない場合、アルゴリズムは共通のprefixを使用せず、BもしくはAとBの両方にチェーン ${(C_A^{\lceil k} or \, C_B^{\lceil k})}$ のより深い部分のプルーフを問い合わせ、それを再帰的に継続する。bをルートとするチェーン ${C_{B}^{\lceil k}}$ で ${T' = \mathit T / 2^{y}}$ より小さいハッシュ値を持つプルーフのBからのリクエストを表すのに ${RequestB[b, y]}$ を使用する。同様に、 ${RequestA[b, y]}$ プレイヤーAに対して同じように機能する。

最終的にアルゴリズムは、十分長いもしくは、proof of workの量のみに基いて決定される（実際のターゲットTが使用される）深さ0に達する分岐suffixを入手する。これによりどちらが正しいプルーフかが決まり、軽量な検証者は別の比較やプロセスを終了する。

効率解析

このセクションでは、プルーフシステムの効率解析を提示する。最初にスペースの使用量、すなわちinterconnected blockchainのデータ構造により全ノードのローカルストレージに必要とされる拡張について説明する。次にプルーフを送信するために必要な通信と軽量な検証者の検証の計算量について分析する。

スペースの使用量

最初にinterconnected blockchainの各ブロックで唯一の加算ベクトルであるinterlinkの適切な上限を示す。

定理1

${T = 2^{f}}$ より小さいハッシュ値を持つブロックで構成されるチェーンCの長さをnとする。次に動的ベクトルであるinterlinkの予想されるサイズは ${f - \sum_{i=1}^{f} (1 - \frac{1}{2^{i}})^{n}}$ 。

証明。各ブロック ${C[j]}$ に対応する離散確率変数を ${X_j \in \{0, ..., f\}}$ と定義すると、

${X_{j} = i \iff \frac{T}{2^{i+1}} \leq H_{B} < \frac{T}{2^i}, i \in 0, ..., f - 1 }$ ${X_j = f \iff 0 \leq H_B < \frac{T}{2^f}}$

（ ${H_B}$ は ${C[j]}$ のハッシュ値。）

各チェーンのブロック ${H_B}$ のハッシュ値は{0, ..., T − 1}の一様な離散分布となる。そのため

${P_r (X_j = i) = P_r (\frac{T}{2^{i+1}} \leq H_B < \frac{T}{2^i}) = \frac{1}{2^{i+1}}, i \in 0,...,f-1 }$ ${P_r (X_j = f) = P_r (0 \leq H_B < \frac{T}{2^f}) = \frac{1}{2^f}}$

結果、

${\sum^{f}_{i=0} P_r (X_j = i) = 1}$

次にinterlinkのサイズはY = max{X1, ..., Xn}の分布に従う。0 ≤ y < fの場合

${P_r (Y \leq y) = (P_r (X_j \leq y))^n = (\sum^{y}_{i=0} \frac{1}{2^{i+1}})^n = (1 - \frac{1}{2^{y+1}})^n}$ ${P_r (Y = y) = P_r (Y \leq y) - P_r (Y \leq y - 1) = (1 - \frac{1}{2^{y+1}})^n - (1 - \frac{1}{2^{y}})^n}$

結果： ${P_r (Y \leq f) = 1}$ かつ ${P_r (Y = f) = 1 - (1 - \frac{1}{2^{f}})^{n}}$ となり

以下が成立する。

${E(Y) = \sum^{f-1}_{y=0} y \cdot [ (1 - \frac{1}{2^{y+1}})^{n} - (1 - \frac{1}{2^{y}})^{n} ] + f \cdot [ 1 - (1 - \frac{1}{2^{f}})^{n} ] \\ = (f-1) \cdot (1 - \frac{1}{2^{f}})^{n} - \sum^{f-1}_{i=1} (1 - \frac{1}{2^{i}})^{n} + f \cdot [ 1 - (1 - \frac{1}{2^{f}})^{n} ] \\ = f - \sum^{f}_{i=1}(1 - \frac{1}{2^{i}})^{n}}$

Figure 2は、現在のブロックチェーンの長さがnの範囲にありターゲットが2²⁰⁰で安定している場合、interlinkの数がnの対数であることを示している。

f:id:techmedia-think:20180106152743p:plain — Figure 2 : ターゲットT=2²⁰⁰の場合のブロックチェーンの長さを関数としたinterlinkのサイズ

マークルツリーを使ったinterlinkの圧縮

ブロック当たりのデータサイズを減らすのにマークルツリーを使ってinterlinkを圧縮する方法がある。より詳細にいうと、各ブロックにinterlink全体を格納するのではなく、interlinkでマークルツリーを構成しそのルートハッシュのみを各ブロックヘッダに格納する方法だ。この結果ブロックヘッダにinterlinkのハッシュ値を順番にセットする必要はなくルートハッシュのみの追加ですむ。ConstructProofに必要な変更については簡単なので省略する。

5.2 通信と時間

プルーフ ${\pi}$ のサイズについて分析する。ここでは敵対者が正直な関係者のプルーフを妨げるような深いフォークを作成していない＝敵対者が送信するk-suffixに正直な証明者によって送信されたプルーフのsuffixで共通のブロックが存在する楽観的なシナリオにフォーカスする。正直な関係者はk-suffixより前にチェーンの一部が分岐していることはない（kはそれだけ圧倒的な確率を持つため）。このようなケースでは、軽量な検証者は証明者と余計なやりとりをすることなく最も実証されたproof of workのチェーンを選択することができる。従ってプルーフのサイズはConstructProofアルゴリズムのアウトプットになる。

軽量な検証者が証明者に尋ねたk-suffixを除いたローカルチェーンを ${C^{\lceil k}}$ とし、チェーンの長さをn、セキュリティパラメータをmとする。まず最初に、 ${C^{\lceil k}}$ のブロックが ${\frac{T}{2^{i}}}$ より小さいハッシュ値を持つ確率が ${\frac{1}{2^{i}}}$ になることを証明する。

ブロックBのハッシュ値を ${H_B}$ 、 ${j \in \mathbb N}$ 、 ${ j ＜ T}$ で、 ${P_r (H_B = j | H_B ＜ T) = \frac{1}{T}}$ の場合

${P_r (H_B ＜ \frac{T}{2^{i}} | H_B ＜ T) = \sum^{\frac{T}{2^{i}} - 1}_{j=0} P_r (H_B = j | HB ＜ T) = \frac{\frac{T}{2^{i}}}{T} = \frac{1}{2^{i}}}$

チェーン ${C^{\lceil k}}$ でハッシュ値が ${\frac{T}{2^{i}}}$ より小さいブロックの数は、パラメータ ${(n, p_i = \frac{1}{2^{i}})}$ の二項分布に従う離散確率変数 ${D_i}$ となり、その期待値は ${E(D_i) = n \cdot p_i}$ 。

ConstructProofアルゴリズムのアウトプットが ${innerchain_{i_0} = \pi}$ であることを思い出して欲しい。ここで ${i_0}$ は ${C^{\lceil k}}$ 内でハッシュ値が ${\frac{T}{2^{i}}}$ より小さいmブロックを持つ最大のiである。結果としてアルゴリズムが返すプルーフの深さ ${i_0}$ とプルーフ ${\pi}$ に含まれる（ ${D_i0}$ で示される）ブロックの数を調べる必要がある。

次の補助定理では、ConstructProofアルゴリズムが返すinnerchainの長さが最適値（約 ${\log{\frac{n}{m}}}$ ）に非常に近いことを確認する。

補助定理1

プルーニングされた証明者のローカルチェーン ${C^{\lceil k}}$ のサイズをnとする。 ${n ＜ T_m}$ とし ${2^{i}m \leq n ＜ 2^{i+1}}$ となるiを定義する。次に ${P_r (D_{i-1} \leq m - 1) \leq exp(-Ω(m))}$ を保持する。

証明。 ${n \cdot p_{i-1} = \frac{n}{2^{i-1}} \geq \frac{2^{i}m}{2^{i-1}} = 2m ＞ m -1}$ であることを観察する。これから二項分布のチェルノフ限界によれば以下のようになる。

${P_r (D_{i-1} \leq m - 1) \leq exp(-\frac{(np_{i-1} - (m - 1))^{2}}{2np_{i-1}}) \\ \leq exp(-\frac{1}{2／(2^{i-1})}) \cdot (n(1／(2^{i-1})) - (m-1))^2／n \\ \leq (- (2m - m + 1)^2 ／ 2^{3}m) \leq exp(- Ω(m))}$

これで証明は完了となる。

この補助定理を利用して次にinnerchainの長さが実質的にmより大きくならないことを観察する。

補助定理2

${n ＜ T_m}$ とし、 ${2^{i}m \leq n ＜ 2^{i+1}m}$ となるiを定義する。 ${P_r (D_{i-1} \geq 5m) \leq exp(-Ω(m))}$ とする。

証明。まず ${2m／n \leq p{i-1} = 1／2^{i-1} ＜ 4m／n}$ を観察する。 ${X}$ が ${\mu}$ と ${\delta \in (0, 1]}$ を持つ二項分布であるとき、 ${P_r [X \geq (1 + \delta \mu ] \leq exp(-\delta^{2}\mu／3))}$ の右端のチェルノフ限界を考えてみる。これは[tex: {P_r \[ D{i-1} \geq 5m \] \leq P_r \[ D{i-1} \geq (1 + 1/4) p{i-1} n \] \leq exp(-p{i-1} n/48) \leq exp(-m/24)}]に従う。

ここまでで、構築し軽量な検証者に伝達されるプルーフの効率を確立する定理を述べる準備ができた。

定理2

楽観的なケースにおいて、軽量な検証者に対して証明者が送信するプルーフ ${\pi}$ のサイズは、mの圧倒的な確立でO(m)となる。

証明。楽観的なケースでは証明者が軽量な検証者に送るプルーフ ${\pi}$ はConstructProofアルゴリズムのアウトプットである。証明者がプルーフを構築するローカルチェーンの長さをnとし、 ${i \geq 1}$ について ${2^{i}m \leq n ＜ 2^{i+1}m}$ とすると、ConstructProofアルゴリズムは補助定理1で証明したようにmで圧倒的な確率で深さi-1のプルーフを返す。さらにプルーフのサイズ ${D_{i-1}}$ は、補助定理2で証明したようにmで圧倒的な確率で5mに制限される。これで証明が完了する。

上記では、敵が明示的に干渉せず、軽量な検証者の複雑さを増やそうとしない楽観的なケースの議論が完成した。敵が干渉しRequestコマンドを使って軽量ノードが余計な通信を行うようにさせた場合、攻撃が成功させるためにはかなりの努力が必要で、攻撃が成功する確率も無視できるレベルのものだ。軽量な検証者の検証を遅らせるためだけに攻撃者がこのような攻撃を行うとは考えにくいため、上記の楽観的な効率解析がプロトコルの実際の性能を完全に示すものだと考えられる。

最後に時間量に関して、楽観的なケースでは、検証者は受信したプルーフのサイズに比例する多数の検証ステップを実行する必要がある。従って検証者の計算量はO(m log n)である。

圧縮されたinterlinkを使用する場合の計算量

この場合の通信量と時間は、interlinkの各ブロックからコミットされたマークルツリーのルートハッシュまでのツリー内のパスのみを送信すればよく改善する。楽観的なケースでは軽量な検証者の計算量はO(m log log n)になることが容易に分かる。

6. セキュリティ分析

この軽量な検証への攻撃が成功するということは、軽量な検証者が特定のトランザクションにおいて完全な検証者とは異なる結論に達することを示唆する。セキュリティのための証明論証は次のようになる。軽量な検証者に応答する攻撃者Aが与えられた時、完全な検証者に応答する攻撃者Aを構築する。高い確率でAと協調する完全な検証者は、Aと協調する軽量な検証者と同じ結論に至る。

直感的に上記は、軽量な検証者が受け入れ、処理する任意のプルーフに対して、リカバリし通常のSPV検証者へ同じアウトプットを生成できるフルチェーンが存在することを意味する。

A*の説明は以下のとおり。

AはAの動作をシミュレートし、さらに各ラウンドで完全な検証者として動作し、 ${C_1, ..., C_e}$ の正直なノードにチェーンをリクエストする。全てのブロックを含むブロックツリーBTを維持し、そこに敵によって生成されたブロックを追加する。ランダムオラクルモデルではAはハッシュ関数 ${H(\cdot)}$ に対するAの全てのクエリを監視することが可能なので、A*はこれを実行可能であることに注意する。有効なブロックに対応しないAによるクエリは無視される。
Aがペア ${(\mathcal X, \pi)}$ で軽量な検証者に応答すると、AはBTにおいて ${(\mathcal X, \pi)}$ と一致するチェーンCを検索する。すなわち ${\mathcal X}$ はCのsuffixで ${\pi}$ はCのサブチェーン。そのようなチェーンが見つかると、Aは完全な検証者にCで応答する。見つからなかった場合は、A*は完全な検証者に応答を返さない。

我々はThe Bitcoin Backbone Protocol: Analysis and Applicationsの分析を行う。彼らのモデルでは、ブロックチェーンを維持するn個のパーティがあり、（ランダムオラクルモデルと考えられる）ハッシュ関数へのq個のクエリが許可され、パーティの内t個は敵の制御下にある。1回のハッシュクエリでProof of Workを見つける確率は ${T / 2^{\mathcal K}}$ （ターゲットはTで安定）。彼らのホワイトペーパーと同じ表記を使用し ${α = (n - t)pq, β = pqt, γ = α - α^{2}}$ とする。直感的にαは正直なパーティのハッシュパワーを表す。これは正直なパーティが1つのラウンドで得る予定の解の上限でもある。一方βは敵が1回のラウンドで得る解の予想数である。最後にγは正直なパーティの1人がProof of Workの解を見つけるラウンドの期待値である。

準備ができたので軽量な検証者のセキュリティを確立する定理を定式化する。定理は ${γ > (1 + \delta)β}$ を条件とする。これは正直なパーティが過半数のハッシュパワーを持つ設定である。

定理3

（軽量な検証者のセキュリティ）いくつかの ${\delta > 0}$ について、 ${γ > (1 + \delta)β}$ とする。A*と協調する完全な検証者は確率 ${1 - exp(-Ω(\delta^{2}m))}$ でAと協調する軽量な検証者と同じ結論に至る。

証明。軽量な検証者がAにプルーフを要求して実行する場合と、完全な検証者がAににプルーフを要求して実行する場合を比較する。2つの検証者が異なる結論に至る場合をBADと定義する。BADでは、敵対者Aが生成するプルーフ ${(\mathcal X, \pi)}$ に対応するBTからのチェーンCを再構成出来ない場合、Aの定義において上記ケース２に必然的に対応する。この後の事象をNOWITと定義し、 ${BAD \subseteq NOWIT}$ を観測する。NOWITが発生した場合、圧倒的な確率mにおいて正直なパーティから送られたプルーフでMaxChainを実行した結果それが勝利する。この事象をHWINとする。より詳細には ${P_r (\neg HWIN \wedge NOWIT)}$ が指数関数的に減少することを証明する。これが ${BAD \subseteq \neg HWIN}$ で十分であること観察する。従って ${P_r (BAD)}$ が指数関数的に低下することになる。

事象 ${\neg HWIN}$ （HWINでない場合）は、攻撃者Aが正直なパーティのパフォーマンスを上回るプルーフを生成できたケースとなる。さらにNOWITも発生した場合、AがMaxChainアルゴリズムに勝利したプルーフに対応するチェーンを再構築することは不可能である。これは勝利したプルーフ ${(\mathcal X, \pi)}$ がレベル0からのチェーンの有効な拡張ではないために、AによってブロックチェーンツリーBTに取り付けることができないブロックを含んでいることを示唆している。従って ${(\mathcal X, \pi)}$ のレスポンスでは、プルーフ[\pi]は正直なパーティのチェーンからは分岐するはずだ。bを正直なパーティに属するBTの最長のチェーンCの ${\pi}$ で最も最新の正当に生成されたブロックとする。bをCのオーナーによって提供されたプルーフに対してMaxChainが選出した ${\mathcal X, \pi}$ に与える。 ${\pi}$ はターゲット ${T/2^{i}}$ 未満であるbから始まる少なくともm個のブロックを含み、 ${\pi}$ の深さはi > 0である。ブロックbが作られたラウンドをrとする。次に、Aが正直なパーティのチェーンが ${2^{i}m}$ 進むより速く ${T/2^{i}}$ 未満のハッシュ値を持つmブロックを得る確率がmで無視できることを示す。これはAがMaxChainによって選択される証明を生成できる確率が無視できるほど小さいことになる。

rがsuccessul roundの場合、 ${X_r}$ を1に等しい確率変数とする。The Bitcoin Backbone Protocol: Analysis and Applicationsでは、ラウンドrの後の任意のsラウンドにおいて、正直なパーティのチェーンの長さは少なくとも ${\ell + \sum_{l=r}^{s}X_l}$ である。ここで ${\ell}$ はrでの正直なパーティのチェーンの長さ。

敵対者が ${T/2^{i}}$ 未満のハッシュ値を持つブロックをmブロック作成するのに必要なラウンド数は負の二項分布に従う。ラウンド数の期待値は ${p = T/2^{K}, β = pqt}$ の場合、 ${2^{i}β^{-1}m}$ 。負の二項分布にtail boundを適用するとラウンド数が ${(1 - \delta / 4)2^{i}β^{i-1}m}$ より小さい確率は ${exp(-Ω(\delta^{2}m))}$ であることが分かる。

一方、 ${(1 - \delta / 4)2^{i}β^{i-1}m}$ ラウンドでは、チェルノフ限界を適用することで、正直なパーティが ${(1 - \delta/4)^{2}γ2^{i}β^{-1}m}$ ブロック未満を生成する確率は ${exp(-Ω(\delta^{2}m))}$ によって制限される。

ここで ${γ＞ (1+\delta)β}$ は ${γ(1 - \delta / 4)^{2}β^{-1} ＞ 1}$ を意味し、正直なパーティのチェーンのPoWが敵のPoWを超える確率は ${1 - exp(-Ω(\delta^{2}m))}$ 。

非対話型および固定サイズの証明についての実現可能性と実現不可能性

プルーフのセキュリティパラメータはmで、楽観的なケースの場合プルーフのサイズはO(m)であることを観察する。我々の構成では、軽量な検証者は受信したinnerchainの分岐を見つけると、証明者と追加の対話を必要とする場合がある。ここで、例えば（固定サイズの）短い証明が可能か？、もしくはフルノードから軽量な検証者への単一のメッセージのみで済む非対話型のプルーフが可能か？疑問が残る。固定サイズのプルーフに関してはここで検討しているようなテクニックでは改善は考えにくい。例えば例外的に低いハッシュ値のブロックが比例長の多くPoWのプルーフとして送信されると、攻撃の確率が十分低くはならない。言い換えるとこのような短い証明は攻撃者の攻撃難易度と比例し、安全ではない。同様にinnerchainに関して任意の低いプルーフが非対話的に与えられると、innerchainの最後で攻撃をしようとする攻撃者がいた場合に、正直なパーティに比べて攻撃者に有利に働くと考えられる。しかし、そのような低いハッシュブロックに十分な数のブロックを必要とするようにすれば対抗することができる。将来の研究として短くセキュアな非対話型SPV プルーフの設計と調査の可能性を残している。

動的な設定

Bitcoinおよび関連するブロックチェーンプロトコルでは、ターゲットは定期的に再計算される。Interconnected Blockchainも同様に動的なターゲット設定で構築することは可能だ。ただターゲットの再計算はinnnerchainで実行する必要があるため、プルーフの検証中にいくつか注意を払う必要がある。動的な設定の分析については将来の研究として残しておく。

*1:https://bitcointalk.org/index.php?topic=98986.0

*2:https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2014-March/004727.html