Develop with pleasure!

福岡でCloudとかBlockchainとか。

軽量クライアント向けのCompact Block Filterを定義したBIP-158

techmedia-think.hatenablog.com

で使用するフィルタの仕様を定義したのがBIP-158↓

https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki

おおまかな仕組みとしては、

BIP-37では軽量クライアント側が自身に関連する公開鍵ハッシュやOutPointなんかをフルノードとのフィルタにセットしていたが、BIP-157,158では逆にフルノード側がブロック内の全トランザクションの全OutPointscriptPubkey内の全データ要素(公開鍵ハッシュなど)を抽出し、それらをゴロム・ライス符号で圧縮してフィルタを生成している。BIP-37が各クライアント毎にフィルタは異なるのに対し、BIP-157,158ではブロック毎にフィルタの中身が決まり、ブロックがチェーンに追加されたタイミングで一度それを生成し保存しておくだけで良い。

BIP-158で定義されている2つのフィルタの構造についてBIPを見てみよう↓

概要

このBIPはBIP-157の軽量クライアントプロトコルで使われるブロックデータのコンパクトなフィルタの構造について説明する。BIP-37のBloom Filterの代替として提案されたフィルタ構成は、圧縮にゴロム・ライス符号を使用することでフィルタサイズを最小限に抑えるようになっている。このドキュメントでは基本的なウォレットとより高度なスマートコントラクトを持つアプリケーションを可能にする、この構成に基づく2つのフィルタの初期タイプについて定義する。

動機

BIP-157はブロックのコンテンツの決定性フィルタに基づいて軽量クライアントプロトコルを定義する。フィルタは軽量クライアントが消費すると予想される帯域幅を最小限に抑えて、フィルタとブロックをダウンロードするように設計されている。このドキュメントでは、基本および拡張用の2つの初期フィルタタイプを定義し、高度なアプリケーションをサポートし、基本的なウォレットのフィルタサイズを縮小する。

定義

[]byteはバイトベクトルを表す。

[N]byteは長さNの固定のバイト列を表す。

CompactSizeはBitcoinのP2Pプロトコルで使われる符号なし整数のコンパクトなエンコード

Data pushesはBitcoinのスクリプトルールに従ってスタックにプッシュされたバイトベクトル。

Bit streamsは個々のbitの読み書き可能なストリーム。このドキュメントの疑似コードでは以下の関数が使われている。

  • new_bit_stream 新しい書き込み可能なBit streamをインスタンス化する。
  • new_bit_stream(vector) vectorからデータを読み込んで新しいBit streamをインスタンス化する。
  • write_bit(stream, b) ストリームの最後にbit bを追加する。
  • read_bit(stream) ストリームから次の利用可能なbitを読み込む
  • write_bits_big_endian(stream, n, k) 整数nk個の最下位bitをビッグエンディアンの順でストリームの最後に追加する。
  • read_bits_big_endian(stream, k) ストリームから次に利用可能なkbitを読み込み、それらをビッグエンディアン整数の最下位bitとして解釈する。

仕様

Golomb-coded set

各ブロックについて、ブロックに関連する項目のセット(例えば送信先のアドレスや使用されたoutpointなど)を含むコンパクトフィルタが導出される。このようなデータオブジェクトのセットはGolomb-coded set (GCS)と呼ばれる確率構造に圧縮される。この確率構造はセット内のアイテムであれば確率1でマッチし、セット内にないアイテムがマッチする確率はある整数パラメータMに対して1/Mである。エンコーディンは剰余符号のビット長であるPによってもパラメータ化される。定義された各フィルターはPとMの値を指定する。

高レベルなGCSはN個のアイテムのセットから次のように構築される。

  1. すべてのアイテムを0 〜 N * Mの範囲の64 bitの整数にハッシュする。
  2. ハッシュ値を辞書順にソートする。
  3. 各値についてその前の値との差を計算する。
  4. 差を順番に書き込み、ゴロム・ライス符号で圧縮する。

以下のセクションではこの各ステップについて詳しく説明する。

データオブジェクトのハッシュ化

フィルタ構築の最初のステップは、セット内の可変サイズのアイテムを[0, F)の範囲内でハッシュ化する(ここでFはF = N * M)。通常Mは2Pに設定される。しかし両方のパラメータを個別に選択できる場合は、より最適な値を選択することができる。ハッシュの出力に対するメンバーシップクエリを設定すると偽陽性率はMになる。数の桁溢れを避けるため、アイテムの数Nは232未満、Mは232未満でなければならない。

アイテムはまず疑似乱数関数SipHashに渡される。疑似乱数関数SipHashは128-bitの鍵と可変サイズのバイト列を受け取り、均一にランダムな64-bitのアウトプットを生成する。このBIPの実装では、SipHashのパラメータはc = 2d = 4を使用しなければならない。

続いて64-bitのSipHashのアウトプットにFを掛けて、その結果の128-bitの上位64-bitを取ることで望ましい範囲にわたって一様にマッピングされる。このアルゴリズムは高価な除算演算を避けるため、モジュロ演算の削減に替わる高速なアルゴリズム*1。この削減を実装する際は、整数乗算の上位64-bitが切り捨てられないよう注意する必要がある。特定のアーキテクチャと高水準言語では、64-bitの乗算を4つの32-bitの乗算に分解し、その結果を再結合するコードが必要になる場合がある。

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
ゴロム・ライス符号

ハッシュされたセット内のアイテムを直接フィルタに書き込むのではなく、連続するアイテム間の差をソート順で書き込むことでより大きな圧縮効果がある。アイテムは一様に分布しているので、その差は幾何分布に似ていることが示されている*2。ゴロム・ライス符号*3は、幾何学的に分布した値を最適に圧縮する方法だ。

ゴロム・ライスでは、値は2Pを法とする商と剰余に分割され、別々にエンコードされる。商qは単身符号としてエンコードされ、qの文字列1つの後に0が1つ続く。余りrはP-bitのビッグエンディアンで表される。例えば以下はP=2を使った場合のゴロム・ライス符号だ。

n (q, r) c
0 (0, 0) 0 00
1 (0, 1) 0 01
2 (0, 2) 0 10
3 (0, 3) 0 11
4 (1, 0) 10 00
5 (1, 1) 10 01
6 (1, 2) 10 10
7 (1, 3) 10 11
8 (2, 0) 110 00
9 (2, 1) 110 01
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は以下の4つのパラメータから構成される。

  • L: N個の元のアイテムのベクトル
  • P: ゴロム・ライス符号のbitパラメータ
  • M: ターゲット偽陽性
  • k: SipHashのアウトプットをランダム化するのに使われる128-bitの鍵

結果はN * (P + 1)の最小サイズのバイト列である。

Lの元のアイテムは最初に上記で指定された64-bitの符号なし整数にハッシュされ、ソートされる。その連続した値間の差(以後deltasと記載する)はゴロム・ライス符号を使って順次bit streamにエンコードされる。最後にbit streamは最も近い境界バイトに0でパディングされアウトプットのバイト列にシリアライズされる。

construct_gcs(L: [][]byte, P: uint, k: [16]byte, M: uint) -> []byte:
    let set_items = hashed_set_construct(L, k, M)

    set_items.sort()

    let output_stream = new_bit_stream()

    let last_value = 0
    for item in set_items:
        let delta = item - last_value
        golomb_encode(output_stream, delta, P)
        last_value = item

    return output_stream.bytes()
セットのクエリ/復元

圧縮されたGCS内にアイテムがあるかどうかメンバーシップを確認するには、エンコードされたdeltasからハッシュされたセットのメンバーを再構築する必要がある。これを行う手順は圧縮の逆で、deltasは1つずつデコードされ累積和に加算される。各中間和はオリジナルのセットのハッシュ値を表す。メンバーシップを照会されたアイテムはセット内のメンバーと同じ方法でハッシュされ、再構成された値と比較される。照会する際に圧縮解除されたセット全体をメモリ上に展開する必要はない。

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:
            return true

        // 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

    return false

一部のアプリケーションでは単一のアイテムの照会でなく、あるセットが含まれているかのチェックが必要になるかもしれない。これには圧縮されたGCSのソート構造を利用することで、個々のアイテムを個別にチェックするよりはるかに効率的に実行できる。まず最初に照会するアイテムはすべてハッシュ及びソートされ、圧縮解除されたGCSのコンテンツと順次比較される。疑似コードについてはAppendix Bを参照。

ブロックフィルタ

このBIPでは1つの初期フィルタタイプを定義する。

  • Basic (0x00)
    • M = 784931
    • P = 19
コンテンツ

Basicフィルタは軽量クライアントが通常のBitcoinウォレットと同期するのに必要なものすべてを含むよう設計されている。Basicフィルタはブロック内の各トランザクション毎に以下のアイテムを正確に含まないといけない。

nil項目はフィルタ要素の最終セットに含まれてはならない。

我々は将来ソフトフォークを介して、フィルタを容易にコミットできるよう全てのOP_RETRUNアウトプットを除外する。現在のwitness commitmentと同様、将来のコミットメントの領域になる可能性があるのが、コインベーストランザクションの追加のOP_RETURNアウトプットだ。全てのOP_RETURNアウトプットを除外することで、コミットメントとコミットされるアイテムの循環依存性を回避する。

構成

Basicフィルタタイプは以下のパラメータを持つゴロム・ライス符号のセットとして構成される。

パラメータPは必ず19に設定し、パラメータM784931に設定しなければならない。PMを個別に設定できる場合、>M=1.497137 * 2Pと設定することが最適に近いことが分析で分かった。

実証分析によると、これらのパラメータは偽陽性によりダウンロードされる予想ブロック数とフィルタ自体のサイズの両方を考慮し、使用帯域幅を最小に抑えるために選択されている。

パラメータkにはフィルタを構築するブロックのハッシュの先頭16バイトを設定しなければならない。これにより鍵に決定性がありながら、ブロックごとに変化することが保証される。

NはGCSをデコードするのに必要なので、シリアライズしたGCSの先頭に含める(CompactSizeで記述する)。したがって完全にシリアライズしたフィルタは以下のようになる。

  • N: CompactSizeとしてエンコードされている
  • 圧縮されたフィルタ自体のバイト
シグナリング

このBIPは新しいservice bitsを割り当てる。

名称 service bit 内容
NODE_COMPACT_FILTERS 1 << 6 このservice bitsが有効なノードは、フィルタタイプ0x00および0x01についてBIP-157のすべてのメッセージに応答しなければならない。

互換性

このブロックフィルタの構成は、既存のソフトウェアと互換性は無く、新しいフィルタの実装が必要。

参照実装

Light client:https://github.com/lightninglabs/neutrino

Full-node indexing:https://github.com/Roasbeef/btcd/tree/segwit-cbf

Golomb-Rice Coded sets:https://github.com/Roasbeef/btcutil/tree/gcs/gcs

Appendix A: 代替案

ゴロム・ライスエンコードセットに決まるまでにはいくつかの代替セットエンコードが検討された。このAppendixのセクションでは、そのいくつかの選択肢と、選択しなかった根拠を列挙する。

Bloom filters

Bloom filtersはおそらくセットのメンバーシップをテストするための最もよく知られた確率的データ構造で、BIP-37でBitcoinに導入された。Bloom filterのサイズは同じ偽陽性率を持つGCSの予想サイズよりも大きく、これが採用しなかった理由だ。

暗号アキュムレータ

暗号アキュムレータ*4は、(他の操作の中で)一方向のメンバーシップテストを可能にする暗号データ構造だ。アキュムレータの1つのメリットは、アキュムレータに挿入されるデータの数に関係なく一定のサイズであることだ。しかし暗号アキュムレータの現在の構成では最初にtrusted setupが必要となる。さらに強RSA仮定に基づくアキュムレータはセットのアイテムを関連グループ内のプライムの代理人マッピングする必要がある。

行列ベースの確率的集合データ構造

Bloom filterに比べて空間的に効率が良いmatrix solverベースのデータ構造が存在する*5。たがGCSベースのフィルタは実装の複雑さがはるかに低く、分かりやすいためGCSベースのフィルタを選択した。

Appendix B:疑似コード

複数の要素にマッチするゴロム・ライスセット

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:
                return true

            // Move on to the next set value.
            else if target_val > value:
                break inner loop

            // Move on to the next target value.
            else if 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]

    return false

Appendix C:Test Vectors

P値が19の5つのテストブロックのTest Vectorここに公開されている。1〜32のPの値についてこれらのTest Vectorを生成するコードはこちら

所感

  • P2SHやP2WSHのredeem scriptにプッシュされているアイテムはこのBIPのフィルタでは対象外なのはちょっと意外。
  • 偽陽性のパラメータはBIP-37は推奨値があるがBIP-158では固定されている(全チェーンで共通のフィルタになるので固定になるのはまぁ当然)。
  • ゴロム・ライス符号含めて理解するのには実装してみた方が早いかも。そのためにも検証用にTest Vectorsが欲しい。

クライアントサイドでブロックのフィルタリングを行う軽量クライアント向けのプロトコル BIP-157

現在のSPVノードの実装は接続先のフルノードとのコネクションにBloom Filterをセットして自身に関連するトランザクションをフィルタリングするBIP-37↓の仕様をベースにしている。

techmedia-think.hatenablog.com

このプロトコルでは、フィルタがフルノード側に送られフルノードがそのフィルタを使ってSPVに関連するトランザクションをフィルタリングし、関連するトランザクションがあればSPVノードにmerkleblockメッセージと共に送信する仕組みになっている。このプロトコルには主に以下の2つの課題がある。

  • プライバシーの問題
    全データをダウンロードするフルノードと違い、フィルタにマッチしたデータを受け取るので、フルノードに自身が管理しているアドレスや残高が分かってしまうというプライバシーの問題がある。フィルタに自身と関係のない条件を加えることで正確な情報をぼかすことはできるが、依然として課題は残る。
  • 悪意あるノードによるデータの省略
    フィルタにマッチしたデータについてはフルノードから通知されるが、悪意あるフルノードは合致するデータがあっても通知しない可能性がある。このため軽量クライアントでは信頼できるフルノードとの接続が必要で、常時複数のノードと接続し漏れがないか検証する必要がある。

これらの課題はいずれもフィルタリング処理を接続先のフルノードに依存しているために発生する。これをクライアントサイド側で行うことでこの課題を解決しようというのが↓のBIP-157の提案。

https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki

正確には↑のBIPにはブロックをフィルタリングする流れと、それを実現する新しいP2Pメッセージが定義されており、フィルタ生成の仕様は別のBIP-158に定義されている。

今回は前者のBIP-157の内容について見てみる。

概要

このBIPでは、現在利用可能なオプションを改善するBitcoinの軽量クライアントプロトコルについて説明する。現在使用されているBIP-37で定義された標準の軽量クライアントのプロトコルは、クライアントのセキュリティを弱め、フルノードによるDoS攻撃を可能にする欠陥がある。新しいプロトコルでは、軽量クライアントがフルノードからブロックのコンテンツの確率的なフィルタを取得し、フィルタに関連するデータがマッチする場合にブロックをダウンロードできるようにすることでこの問題を解決する。

新しいP2Pメッセージは、信頼できるソース(フルノード)に頼ることなく、軽量クライアントがブロックチェーンを安全に同期できるようにする。このBIPは、前のブロックのすべてのフィルタへのコミットメントとして機能し、無効なフィルタを提供している悪意あるピアもしくは障害のあるピアを効率的に検出するフィルタヘッダを定義する。結果、プロトコルは、少なくとも1つの正直なピアと接続された軽量クライアントが正しいブロックフィルタを識別できることを保証する。

動機

Bitcoinの軽量クライアントを使用すると、すべてのデータをダウンロードして検証することなく、ブロックチェーンから自分に関連するトランザクションを読み取ることができる。このようなアプリケーションは同時に、ピアへの信頼や帯域幅、ストレージ容量および計算量を最小化しようとする。軽量クライアントはすべてのブロックヘッダをダウンロードし、Proof of Workを検証し、一番長いProof of Workのチェーンを選択することでこれらを実現している。ブロックヘッダは80バイト固定で、平均10分毎に生成されるので、ブロックヘッダの同期に必要な帯域幅は最小限に抑えられる。その後軽量クライアントは、自身に関連するブロックチェーンデータのみをピアから直接ダウンロードし、それがヘッダーチェーンに包含されているか検証する。軽量クライアントは一番長いProof of Workのチェーンのすべてのブロックの有効性はチェックせず、セキュリティためのマイナーのインセンティブに頼っている。

BIP-37は現在Bitcoinで最も広く活用されている軽量クライアントの実行モードだ。BIP-37では、クライアントが監視したいBloom Filterをフルノードのピアに送信し、フィルタにマッチするトランザクションおよびブロック毎に通知を受け取る。クライアントは続いて、ピアに自身に関連するトランザクションとそのトランザクションがブロックに含まれていることのマークルプルーフ(これを使ってブロックヘッダに対して検証を行う)を要求する。Bloom Filterはクライアントのアドレスや未使用のアウトプットなどのデータとマッチする。偽陽性率とリモートピアへリークされる情報とのバランスを取るため、フィルタサイズは慎重に調整する必要がある。しかし利用可能なほとんどの実装では、ウォレットやその他のアプリケーションで実質的にプライバシーは0となっていることが示されている*1。さらに軽量クライアントに対して悪意あるフルノードは検出のリスクが殆ど無くクリティカルなデータを省略することができる。これは特定のオンチェーンイベントに応答する必要のあるアプリケーション(Lightning Networkクライアントなど)では受け入れられない。最後にBIP-37の軽量クライアントにサービスを提供する正直なノードは、悪意を持って作成されたBloom FilterによりI/OやCPUリソースを大量に消費し、DoS攻撃を発生させ、ノード運用者にこのプロトコルをサポートしないようすることが考えられる*2

このドキュメントに記述されている代替案はBIP-37の反対のアプローチとしてみることができる。クライアントがフルノードのピアにフィルタを送るのではなく、フルノードがクライアントに提供されるブロックデータに対して決定性フィルタを生成する。軽量クライアントは自身が監視しているデータとフィルタがマッチする場合、ブロック全体をダウンロードすることができる。フィルタは決定性なので、新しいブロックがチェーンに追加された際に一度だけ作成しディスクに格納すればいい。これによりフィルタ処理に必要な計算が最小限に抑えられ、BIP-37に対応するフルノードを脆弱にするI/Oの問題が排除される。クライアントは、フィルタリングされたブロックの完全性を検証するよりも簡単にピアから受信したフィルタの有効性を検証できるので、関連するすべてのトランザクションをより確実に確認することができる。最後にブロックはどのソース(フルノード)からでもダウンロードできるので、どのピアもクライアントが必要とする情報を得ることができずクライアントのプライバシーが向上する。極めてプライバシーが配慮された軽量クライアントでは、プライバシーを考慮した情報探索*3のような高度な技術を駆使してブロックを匿名でフェッチすることも選択可能だ。

定義

[]byteはバイトベクトルを表す。

[N]byteは長さNの固定のバイト列を表す。

CompactSizeBitcoinP2Pプロトコルで使われる符号なし整数のコンパクトなエンコード

double-SHA256double-SHA256(x) = SHA256(SHA256(x))というSHA256の2回の呼び出しで定義されるハッシュ関数

仕様

フィルタタイプ

将来の拡張性とフィルタサイズ削減のため、どのデータがブロックフィルタに含まれているか決定するのとフィルタの構築/クエリの方法を定義する複数のフィルタタイプがある。このモデルでは、フルノードはサポートされるフィルタタイプ毎に1ブロックあたり1つのフィルタを生成する。

各タイプは1バイトのコードで識別され、フィルタのコンテンツとシリアライゼーションフォーマットを指定する。フルノードはservice bitsを使って特定のフィルタタイプのサポートを通知しても良い。初期のフィルタタイプはBIP-158で別々に定義され、1つのservice bitがそれらのシグナルサポートに割り当てられる。

フィルタヘッダ

この提案は、Bitcoinノードがブロックを同期するのに使用するヘッダファースト*4の仕組みからインスプレーションが浮かんだ。ブロックヘッダがブロック内のすべてのトランザクションに対するマークルコミットメントを持つのと同様に、ブロックフィルタへのコミットメントを持つフィルタヘッダを定義する。またブロックヘッダのようにフィルタヘッダは前のフィルタヘッダへのコミットメントを持つ。軽量クライアントはブロックフィルタ自体をダウンロードする前に、現在のブロックチェーンのすべてのフィルタヘッダをダウンロードし、それを使ってフィルタの信頼性を検証する。複数のピア間でフィルタヘッダチェーンが異なる場合、クライアントはそれらが分岐するポイントを特定し、どちらのピアに欠陥があるか識別することができる。

ブロックフィルタの正規のハッシュは、シリアライズしたフィルタのdouble-SHA256で、フィルタヘッダはブロックフィルタ毎に導出される32バイトのハッシュだ。それらはフィルタハッシュと連結された前のフィルタヘッダのdouble-SHA256として計算されるジェネシスブロックの場合、計算に使用する前のフィルタヘッダは32バイトの0の配列となる。

新しいメッセージ

getcfilters

getcfiltersは特定の範囲のブロックに対して、特定のタイプのコンパクトフィルタを要求するのに使われる。メッセージには以下のフィールドが含まれる。

フィールド名 データ型 バイトサイズ 定義
FilterType byte 1 ヘッダを要求するフィルタタイプ
StartHeight uint32 4 要求する範囲の最初のブロック高
StopHash [32]byte 32 要求する範囲の最後のブロックハッシュ
  1. ノードは接続先のピアがこのフィルタタイプをサポートするシグナルと出していない場合、getcfiltersを送信しない方が良い。サポートしていないフィルタタイプのgetcfiltersを受信した場合、ノードは応答を返さないほうが良い。
  2. StopHashは受信ピアによって受け入れられたブロックに入っているものでなければならない。これはピアが以前に、そのブロックもしくはその子孫が含まれるheadersもしくはinvメッセージを送信していた場合だ。不明なStopHashがセットされたgetcfiltersを受信したノードは応答しなくても良い。
  3. StopHashのブロック高はStartHeight以上でなければならず、またその差は厳密に1000未満でなければならない。
  4. メッセージを受信したノードは要求された範囲内の各ブロックについてブロック高順に1つのcfilterメッセージで応答しなければならない。
cfilter

cfiltergetcfiltersへの応答として送信されるメッセージで、要求された範囲内の各ブロックについて1つずつ送信される。メッセージには以下のフィールドが含まれる。

フィールド名 データ型 バイトサイズ 定義
FilterType byte 1 返されるフィルタタイプのバイト識別子
BlockHash [32]byte 32 フィルタが返すBitcoinのブロックのブロックハッシュ
NumFilterBytes CompactSize 1-5 次のフィールドのフィルタのサイズを表す可変長整数
FilterBytes []byte NumFilterBytes このブロックのシリアライズされたコンパクトフィルタ
  1. FilterTypeはgetcfiltersで要求されたフィールドと一致する必要があり、BlockHashはStartHeight以上の高さを持ちStopHashの祖先のブロックでなければならない。
getcfheaders

getcfheadersはある範囲内のブロックに対して検証可能なフィルタヘッダを要求する際に使われる。メッセージには以下のフィールドが含まれる。

フィールド名 データ型 バイトサイズ 定義
FilterType byte 1 ヘッダを要求するフィルタタイプ
StartHeight uint32 4 要求する範囲の最初のブロック高
StopHash [32]byte 32 要求する範囲の最後のブロックハッシュ
  1. ノードは接続先のピアがこのフィルタタイプをサポートするシグナルと出していない場合、getcfheadersを送信しない方が良い。サポートしていないフィルタタイプのgetcfheadersを受信した場合、ノードは応答を返さないほうが良い。
  2. StopHashは受信ピアによって受け入れられたブロックに入っているものでなければならない。これはピアが以前に、そのブロックもしくはその子孫が含まれるheadersもしくはinvメッセージを送信していた場合だ。不明なStopHashがセットされたgetcfheadersを受信したノードは応答しなくても良い。
  3. StopHashのブロック高はStartHeight以上でなければならず、またその差は厳密に2000未満でなければならない。
cfheaders

cfheadersgetcfheadersへの応答として送信されるメッセージで、複数のフィルタヘッダを含めるのではなく、レスポンスには1つのフィルタヘッダと後続のフィルタハッシュが含まれ、そこからヘッダを導出する。これはクライアントがヘッダ間のバインディングリンクを検証できるというメリットがある。メッセージには以下のフィールドが含まれる。

フィールド名 データ型 バイトサイズ 定義
FilterType byte 1 ハッシュを要求するフィルタタイプ
StopHash [32]byte 32 要求された範囲の最後のブロックのハッシュ
PreviousFilterHeader [32]byte 32 要求された範囲の最初のブロックの前のフィルタヘッダ
FilterHashesLength CompactSize 1-3 次のフィールドのフィルタハッシュのvectorの長さ
FilterHashes [][32]byte FilterHashesLength * 32 要求された範囲内の各ブロックのフィルタハッシュ
  1. FilterTypeとStopHashはgetcfheadersのリクエストと一致する必要がある。
  2. FilterHashesLengthは2000より大きくてはならない。
  3. FilterHashesはStartHeightのブロック高から始まり、StopHashで終了するチェーンの各ブロック毎に1つのエントリーを持たなくてはならない。このエントリーは要求された範囲内のブロック毎の指定されたタイプのフィルタハッシュで、ブロック高の昇順でなければならない。
  4. PreviousFilterHeaderには要求された範囲内の最初のブロックの1つ前のフィルタヘッダをセットしなければならない。
getcfcheckpt

getcfcheckptはブロックのある範囲に渡って均等に間隔を置いたフィルタヘッダを要求するのに使われる。クライアントは、以下のクライアント操作のセクションで説明されているように、getcfheadersのフィルタハッシュを使ってこれらのチェックポイントを繋ぐことができる。getcfcheckptには以下のフィールドが含まれる。

フィールド名 データ型 バイトサイズ 定義
FilterType byte 1 要求されているヘッダのフィルタタイプ
StopHash [32]byte 32 ヘッダが要求されているチェーン内の最後のブロックのハッシュ
  1. ノードは接続先のピアがこのフィルタタイプをサポートするシグナルと出していない場合、getcfcheckptを送信しない方が良い。サポートしていないフィルタタイプのgetcfcheckptを受信した場合、ノードは応答を返さないほうが良い。
  2. StopHashは受信ピアによって受け入れられたブロックに入っているものでなければならない。これはピアが以前に、そのブロックもしくはその子孫が含まれるheadersもしくはinvメッセージを送信していた場合だ。不明なStopHashがセットされたgetcfcheckptを受信したノードは応答しなくても良い。
cfcheckpt

cfcheckptgetcfcheckptへの応答として送信される。含まれるフィルタヘッダは要求されたチェーン上のすべてのフィルタヘッダのセットで、その高さは1000の正の倍数(1000間隔毎のフィルタヘッダ)。メッセージには以下のフィールドが含まれる。

フィールド名 データ型 バイトサイズ 定義
FilterType byte 1 要求されているヘッダのフィルタタイプ
StopHash [32]byte 32 ヘッダが要求されているチェーン内の最後のブロックのハッシュ
FilterHeadersLength CompactSize 1-3 次のフィールドのフィルタヘッダのvectorの長さ
FilterHeaders [][32]byte FilterHeadersLength * 32 1000間隔のフィルタヘッダのリスト
  1. FilterTypeとStopHashはgetcfcheckptリクエストと一致する必要がある。
  2. FilterHeadersはジェネシスブロックからStopHashのブロックまでの間のブロック高が1000の倍数であるブロック毎に1つのエントリーを持たなくてはならない。そのエントリーはそのような各ブロックの与えられたタイプのフィルタヘッダで、ブロック高の昇順でセットされていなければならない。

ノード操作

ルノードは、このBIPをサポートし指定された任意のフィルタタイプを生成することができる。そのようなノードは、フィルタをブロックチェーンの追加インデックスとして扱う必要がある。メインチェーンに接続する新しいブロック毎に、ノードはサポートしているすべてのタイプのフィルタを生成し保存する必要がある。フィルタを保持しておらず、すでにブロックチェーンと同期済みのノードは、起動時にチェーンを再インデックスしジェネシスブロックから最新のブロックまでの各ブロックのフィルタを構築する必要がある。また、getcfcheckptのリクエストにより多くのディスクへのランダムアクセスを引き起こさないようすべてのチェックポイントヘッダをメモリ上に保持する必要がある。

悪意あるピアが大きなブロックから派生した小さなフィルタを要求しDoS攻撃を実行する可能性があるため、要求に応じて動的にフィルタを生成しない方がいい。これはBIP-111に記載されているBIP-37対応ノードに対する攻撃と同じく、ノード上で計算とサービスを行うI/Oの問題が発生する。

ノードはブロックのすべてのフィルタを生成し保存した後であれば、ブロックをプルーニングしてもいい。

クライアント操作

このセクションではクライアントが最大のセキュリティをもってフィルタをダウンロードするための推奨事項を示す。

クライアントはまずブロックフィルタやフィルタヘッダをダウンロードする前に、標準のヘッダファーストの仕組みを利用してピアからすべてのブロックヘッダの同期をする必要がある。トラステッドチェックポイントを構成するクライアントは、最後のチェックポイントからヘッダの同期を開始するだけでいい。クライアントは接続先のピアのベストチェーンが既知の最長のProof of Workのチェーンよりも大幅に作業量が少ない場合、そのアウトバウンドピアとのコネクションは切断する必要がある。

クライアントのブロックヘッダが同期できたら、後でダウンロードする可能性のあるすべてのブロックとフィルタタイプのフィルタヘッダをダウンロードして検証する必要がある。クライアントはgetcfheadersメッセージをピアに送信し、各ブロックのフィルタヘッダを導出し格納する必要がある。クライアントは最初にgetcfcheckptメッセージを送信することで、1,000ブロック間隔でヘッダをフェッチしてもいい。ヘッダチェックポイントを使うとクライアントは複数のピアからさまざまな間隔でフィルタヘッダを並行してダウンロードし、1000個のヘッダの各範囲をチェックポイントに対し検証することができる。

フィルタヘッダを提供する信頼できるピアに確実に接続しているか分からない場合、クライアントは各フィルタタイプをサポートする複数のアウトバウンドピアに接続し、不正なヘッダをダウンロードするリスクを軽減する必要がある。クライアントが任意のブロックやフィルタタイプについて異なるピアから競合するフィルタヘッダを受信した場合、調査しどちらに欠陥があるのか判断する必要がある。クライアントはgetcfheadersおよびgetcfcheckptを使用して一致しなくなった最初のフィルタヘッダを特定する必要がある。クライアントはピアから完全なブロックをダウンロードし、正しいフィルタとフィルタヘッダを導出する必要がある。クライアントは計算したものと一致しないフィルタヘッダを送信したピアをBANする必要がある。

クライアントが必要なすべてのフィルタヘッダをダウンロード及び検証し、アウトバウンドピアが競合するヘッダを送信していなければ、クライアントは必要なブロックフィルタをダウンロードできる。クライアントはこの時点で最初に検証されたフィルタヘッダより前のフィルタヘッダについて埋め戻しても良い、ただし後でダウンロードを開始した場合のみ。クライアントは再起動後に新しいピアから受信したヘッダと比較するため、チェーン内のラスト100ブロック分()の検証済みフィルタヘッダを保持する必要がある。後で再スキャンが必要になった場合に、再ダウンロードを避けるためより多くのファイルヘッダを保存しておいてもいい。

希望する範囲内の最初のブロックから始めて、クライアントはフィルタをダウンロードすることができる。クライアントは、各フィルタが対応するフィルタヘッダと不正なフィルタを送信するBANピアにリンクするかテストする必要がある。クライアントは複数のフィルタを一度にダウンロードしスループットを上げることができるが、フィルタは順番にテストする必要がある。クライアントは、フィルタを要求する前にフィルタヘッダが空のフィルタのハッシュにコミットしているかどうかチェックすることで、不要な往復を避けても良い。

新しい有効なブロックヘッダを受信するたびに、クライアントはすべての適格なピアに対応するフィルタヘッダを要求する必要がある。2つのピアが競合するフィルタヘッダを送ってきた場合、クライアントは上記のようにそれらを調べ、無効なヘッダを送信するピアをBANする必要がある。

クライアントがP2Pネットワークから全ブロックをフェッチする場合、アウトバウンドピアから無作為にダウンロードし、トランザクションの交差分析によるプライバシーの損失を軽減する必要がある。このBIPをサポートしていないピアからブロックをダウンロードできることに注意する。

論拠

フィルタヘッダとチェックポイントメッセージは、競合する情報を送信しているピアに接続されている場合、クライアントがブロックの正しいフィルタを識別するのに役立つ。別の解決方法はBitcoinのブロックにブロックフィルタを導出するためのコミットメントを含める方法で、この場合軽量クライアントはブロックヘッダといくつかの追加のwitness dataを使って信頼性を検証できる。しかしこれはBitcoinのコンセンサスルールをネットワーク全体で変更する必要がありるため、このドキュメントでは純粋にP2Pレイヤのみで解決する方法を提案している。

現在のチェーンの長さと成長率と、2つのチェックポイント間のcfheadersからcfcheckptメッセージのサイズが大幅に大きくならないよう考慮し、チェックポイント間の間隔を1000ブロックとした。また1000は少なくとも10進数で考える我々にとっては良い番号だ。

互換性

この軽量クライアントのモードは、現在の展開されているノードと互換性はなく、新しいP2Pメッセージのサポートが必要となる。この提案のノード実装は、現在のP2Pネットワークルールと互換性はない(つまりフルノードのネットワーク・トポロジーには影響しない)。軽量クライアントはこのBIPに基づくプロトコルを既存のBIP-37の代替として採用することができる。このBIPの採用により、BIP-37のネットワークサポートが低下する可能性がある。

参照実装

Light client:https://github.com/lightninglabs/neutrino

Full-node indexing:https://github.com/Roasbeef/btcd/tree/segwit-cbf

Golomb-Rice Coded sets:https://github.com/Roasbeef/btcutil/tree/gcs/gcs

所感

  • フィルタにマッチした際にそのブロック全部ダウンロードするので、今までよりダウンロードするデータサイズは増える。これは悪意あるフルノードへの対応やプライバシー問題とのトレードオフかな。あとブロックサイズが大きいほどこの負担は増えるので、ビッグブロックのチェーンの軽量クライアントでこれを採用するのは、その部分がネックになりそう。
  • 参照実装のプロダクトみる感じだとbtcdとLightning Networkのクライアントであるneutrinoなので、Coreに実装されるのはまだ先か?
  • 軽量クライアント向けの改善は以前roasbeefがhttps://github.com/Roasbeef/bips/blob/master/gcs_light_client.mediawikiを提案していたが、BIP-157とBIP158に置き換えるみたい。
  • 互換性の部分にこれが採用されることによるBIP-37のネットワークサポートへの影響について記載されているが、競合となる機能リリースする際はこういった影響の視点も重要ね。

BIP-158へ続く。

techmedia-think.hatenablog.com

どうしてECDSA署名から公開鍵が復元できるのか?

ECDSAの署名からどうして公開鍵が取得できるの?という聞かれて何でだろうねって話になったので調べてみた。

署名から公開鍵のセットを復元

Rubyではecdsaのgemを使えば以下のように署名と署名対象のメッセージから公開鍵を取得できる。(署名対象のメッセージはどうせなのでBitcoinで使用されているのと同じトランザクションのsighashを使用。そのためbitcoinrbのgemも利用している)

実行すると↓のように2つの公開鍵が抽出できる。

0259f6658325c4e3ca6fb38f657ffcbf4b1c45ef4f0c1dd86d5f6c0cebb0e09520
03a9255e098f4075e9ebfaf7859f459095667879db33e977fc8c91029afa8a2490

↑のコード上の署名はこの内の0259f6658325c4e3ca6fb38f657ffcbf4b1c45ef4f0c1dd86d5f6c0cebb0e09520に対応する秘密鍵で行ったもの。

署名とメッセージから公開鍵を復元する際の計算

ecdsaのgemで署名とメッセージから公開鍵を計算しているのがrecovery_public_key.rbの↓の部分。

module ECDSA
...

  def self.recover_public_key(group, digest, signature)
    return enum_for(:recover_public_key, group, digest, signature) if !block_given?

    digest = normalize_digest(digest, group.bit_length)

    each_possible_temporary_public_key(group, digest, signature) do |point|
      yield calculate_public_key(group, digest, signature, point)
    end

    nil
  end

  private

  def self.each_possible_temporary_public_key(group, digest, signature)
    signature.r.step(group.field.prime - 1, group.order) do |x|
      group.solve_for_y(x).each do |y|
        point = group.new_point [x, y]
        yield point if point.multiply_by_scalar(group.order).infinity?
      end
    end
  end

  def self.calculate_public_key(group, digest, signature, temporary_public_key)
    point_field = PrimeField.new(group.order)

    # public key = (tempPubKey * s - G * e) / r
    rs = temporary_public_key.multiply_by_scalar(signature.s)
    ge = group.generator.multiply_by_scalar(digest)
    r_inv = point_field.inverse(signature.r)

    rs.add_to_point(ge.negate).multiply_by_scalar(r_inv)
  end

end

ここでは以下の計算をしている。

  1. 署名データ(r, s)r楕円曲線のx座標として、y座標を計算する。
    secp256k1の楕円曲線多項式はy2 = x3 + 7なので、rの値をxに入れればyを計算できる。楕円曲線の平面曲線はx軸に対して対称なのでyの取りうる値はx軸を対称に2つある(↑のrecover_public_keyを呼んで2つの公開鍵が返ってきたのはこのため)。ここで計算した2つの点について2以降の計算をして2つの公開鍵を導出する。
  2. rと1で計算したyから[r, y]となる楕円曲線上の点を計算する。
  3. 2で計算した点に(r, s)sを掛けた点rsを計算する。
  4. secp256k1のグループGの生成点にメッセージを掛けた点geを計算する。
  5. 3で計算した点rsに4で計算した点geを減算して出来た点に {r^{-1}}を掛けた点を計算する。

5で計算した点が復元した公開鍵になる。

もう少し簡略化してみよう。署名データを(r, s)、1でrを使って計算した2つの点をRとR'とし、メッセージのハッシュ値e、secp256k1の楕円曲線の生成点をGとした場合、算出している公開鍵は以下の2つだ。

 {\displaystyle \frac{sR - eG}{r}}および {\displaystyle \frac{sR' - eG}{r}}

補足

↑の1の計算についてコメントもらったので追記。

1でrをx座標として2つのRとR'を計算すると書いたが、楕円曲線のペーパーには、このx = r + jnでx座標を求めるようになっている。ここでj {j \in \{0, 1, ...., h\}}の集合でhは各楕円曲線毎に定義されており、secp256k1の場合h = 1だ。つまりx座標の候補はrr + nの2つになる(nはグループの位数)。r + nがグループの剰余系の素数を超えないようになってるので、実際にその範囲内のr + nが候補に上がるのは、r剰余系の素数 - 1 - n以下の場合。最初の復元コードの出力結果が2つの公開鍵だったのはr + nがこの範囲外で、rのみの計算となったため。

なぜこれが公開鍵になるのか?

という疑問が当然わくが、これはECDSAの署名生成と署名検証時のロジックからそれっぽい理由が分かる↓(数学的にはもっとちゃんとした解説があると思う)

秘密鍵p、その公開鍵をQ = pGとし、メッセージのハッシュ値eへのECDSAの署名データ(r, s)は以下のようにして計算される。

  1. 最初にランダムな値kを選択する。
  2. kを使って楕円曲線上の点=kG = (x, y)を計算し、そのx座標をrとする。
  3.  {s = k^{-1}(e + r*p) \bmod n}を計算する。
  4. 算出した(r, s)が署名データとなる。

そしてその署名データが正しいかどうかは以下のようにして判定される。

 {\displaystyle R = (e/s)G + (r/s)Q}

となる点Rを計算し、Rのx座標がrと同じであれば署名は正しい。

この検証に使用した式を公開鍵Qを求めるように展開すると

 {\displaystyle R = \frac{eG + rQ}{s}}
 {\displaystyle sR = eG + rQ}
 {\displaystyle sR - eG = rQ}
 {\displaystyle \frac{sR - eG}{r} = Q}

署名が正しい場合Rのx座標はrと等しいということを思い出そう。公開鍵の復元に使用したRR'のx座標はいずれもrで、公開鍵による検証の際に使用した楕円曲線上の点と合致する。

このことから(r, s)およびそのメッセージeから計算した {\displaystyle \frac{sR - eG}{r}}および {\displaystyle \frac{sR' - eG}{r}}が公開鍵と言える。

取引所の支払い能力を証明する(Proof of Solvency)Provisionsプロトコル

Mt.Goxの破綻後に発表された取引所の支払い能力を証明するプロトコルProvisionsのホワイトペーパー↓

http://www.jbonneau.com/doc/DBBCB15-CCS-provisions.pdf

仮想通貨を取り扱う取引所では、一般的な銀行の仕組みである部分準備金銀行のようなアプローチはコミュニティから良しとされず、顧客が預入をしているコインの総量以上のコインを取引所が保有していることが求められる傾向がある。実際に顧客が預けたり取引所上で購入したコインの総量と同じ量のコインを実際に取引所が持っていない場合、一斉に引き出しが発生すると一部の顧客はコインを引き出すことができないし、取引所がハッキングを受けたり、破綻した場合、不足しているコインは顧客の元に戻ってこない可能性が高い。

取引所の破綻そのものを回避する仕組みはないものの、顧客が預入・取引しているコインを取引所が確かに支払うことができることを証明する仕組みは、顧客の資産保護という点で重要だ。↑のProvisionsでは暗号学的な仕組みを利用して取引所の支払能力を証明するためのプロトコルを提案している。

ざっとホワイトペーパーの内容を見てみる↓

Proof of Solvency

取引所に支払能力があるかどうかは、単純に取引所の総資産 ≧ 取引所の総負債であることが証明できればいい。このためProof of Solvencyを構成するは以下の3つのプロトコルで構成される。

  • プロトコル1 資産の証明
    取引所が署名可能なBitcoinの合計量にコミットした証明
  • プロトコル2 負債の証明
    取引所のすべての顧客のBitcoinの残高にコミットした証明
  • プロトコル3 支払能力の証明
    負債の証明と資産の証明のコミットメントの差を準同型的に計算し、支払能力を証明する

Provisionsは、Confidential Transactionなどでお馴染みのPedersen Commitmentやゼロ知識を使ってこれらのプロトコルを実現する。

表記
  • gとhを楕円曲線のグループGのジェネレータ(固定値)とする。
  • yを公開鍵、xを秘密鍵とする。
  • xとyの関係は、 {y = g^{x}}と表記する(一般的な楕円曲線の公開鍵と秘密鍵の表記は {y = xG}だけど、このホワイトペーパーでは←を使う)。

プロトコル1資産の証明

プロトコル1では取引所が持つ総資産へのコミットメントを生成する。この時重要なポイントが、取引所が実際にいくらの資産を保有しているのかを明かすこと無く資産の証明ができること。

総資産へのコミットメントの作成

取引所はまず公開鍵の匿名セット {PK = {y_1, ..., y_n}}を用意する(yは公開鍵)。このセットの内、取引所が実際に対応する秘密鍵xを知っている公開鍵のセットをSとする。SとPKの関係は {S \subseteq PK}。また、0か1の値を持つ {s_i}を定義し、取引所が秘密鍵を知っている場合はs = 1、知らない場合はs = 0とする。公開鍵 {y_i}にロックされているビットコインの量を {bal(y_i)}とすると、取引所の総資産は↓のように表現できる。

 {\displaystyle \sum_{i=1}^{n} s_i \cdot bal(y_i)}

ここで、公開鍵 {y_i}が持つコインの量 {bal(y_i)}には取引所が秘密鍵を持っている分と持っていない分が含まれ、持っていない分については {s_i} = 0なので合計に加えられない。PKが与えられれば検証者は(誰でも)ブロックチェーンを確認することで各 {bal(y_i)}の量を確認できる。

続いて {bal(y_i)}を使って以下の式を定義する。

 {b_i = g^{bal(y_i)}}

この式では {b_i}が、 {bal(y_i)}秘密鍵としたときの公開鍵となることが分かる。先述したように誰もが {bal(y_i)}の値を知ることができるので、誰もが {b_i}を計算できることになる。

取引所は {s_i \cdot bal(y_i)}毎にランダムな値 {v_i}を選択して、以下のPedersen Commitmentを作成する。

 {p_i = b_{i}^{s_i} \cdot h^{v_i}} [1]

ここで {h^{v_i}}はgとは異なる別のジェネレータhとランダムに選択した秘密鍵 {v_i}から生成した公開鍵になる。 {s_i}については取引所が秘密鍵を知らない場合0なので、その場合 {b_{i}^{0} = 1} {p_i}は実質 {p_i = h^{v_i}}

このコミットメントをi=1,..,nまで足していくと

{ \displaystyle
Z_{Assets} := \prod_{i=1}^{n} p_i = \prod_{i=1}^{n} b_i^{s_i} \cdot h^{v_i} = g^{Assets}h^{(\sum_{i=1}^{n} v_i)}
} [2]

と、取引所の資産の合計額へのコミットメントが出来上がる。
※ 合計額へのコミットメントを公開するだけで実際の合計額が明らかになる訳ではない。
 { g^{Assets}}のAssetsが実際に取引所が所有する=秘密鍵を持つコインの合計)

ちなみに {Z_{Assets}}が取引所の本当の総資産かどうかは分からない。支払能力を証明するには総負債以上の総資産があることが証明できれば良いのでコミットメントには含まれていない余剰金があっても問題はない。

総資産へのコミットメントの証明

総資産へのコミットメント {Z_{Assets}}が計算できても、 {s_i = 1}の公開鍵 {y_i}に対する秘密鍵を本当に取引所が所有しているのだろうか?という疑問は残る。

これが証明できないと {Z_{Assets}}が実際に取引所の管理下にある資産なのか分からないので、取引所は合計額を秘匿したままゼロ知識でこれを証明する。

証明のためまず取引所は各i毎にランダムな値 {t_i}を選択して以下のような {s_i}のPedersen Commitmentを作成する。

 {\displaystyle l_i = y_{i}^{s_i}h^{t_i} \in G} [3]

このコミットメントは以下のように { y_{i}^{s_i}}の部分を量 {x_i \cdot s_i}に対するPedersen Commitmentに置き換えることができる。

 {\displaystyle l_i= g^{x_i \cdot s_i}\,h^{t_i}}[4]

 {\hat x_{i} := x_i \cdot s_i}として以下のように記述する。

 {\displaystyle l_i= g^{\hat x_i}\,h^{t_i}}[5]

 {Z_{Assets}}が取引所の資産の下限値であることを証明するのに、取引所は[1], [3], [5]を満たす以下の数量の知識を証明する。

 {s_i \in \{ 0, 1 \} および、v_i, t_i, x_i \cdot s_i \in \mathbb Z_q}[6]

この証明により {s_i = 1}の時、取引所が公開鍵 {y_i}に対応する秘密鍵 {x_i \in \mathbb Z_q}を知っていることを検証者に確信させる。

取引所はΣプロトコルを利用した以下のProtocol 1を使って[6]の知識を証明する。

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

プロトコル1自体は対話型のプロトコルになっているけど、これはFiat-Shamirヒューリスティックというのを使用すると非対話型にできるみたい。

プロトコル2負債の証明

まず顧客毎に顧客の一意な情報(ユーザー名、メールアドレス、口座番号など)とランダムに選択したnonceを使って顧客毎のコミットメントCIDを生成する(※異なる顧客に同じエントリーを与えられないよう顧客毎の一意な情報からCIDは生成される)。

 {CID = H(username || n)} (※Hはハッシュ関数

全顧客のCIDとその残高及び、残高のrange proofを持つ、債権者リスト(LiabList)を作成する。この債権者リストには取引所が顧客数を秘匿するため残高0のダミーの顧客が含まれている場合もある(残高があるダミー顧客を追加しても良いが、追加した分債務は増える)。

債権者リストは大まかに以下のようにして作られ、できたリストを公開する。

  1. 顧客の残高に対するPedersen Commitmentを作成する。この時残高をm-bitの二進数で表す(mは {m = \lceil lg_2 \, MaxBTC \rceil}で計算)。
  2. 1で計算した残高の各bit毎にPedersen Commitmentを作成する。
  3. 各顧客ごとに、取引所がPedersen Commitmentに使用したランダム値と残高の各bit値を知っていることを証明=range proofを生成する。
  4. 顧客の固有情報とnonceを使ってCIDを計算する。
  5. 顧客分↑を計算したら、全顧客分の債権リスト = <CID, 残高の各bit値のリスト, ゼロ知識>, ...を生成し公開する。

残高をm-bitの2進数にしてるのが不思議だが、おそらく残高をオーバーフローさせてマイナス残高を設定できないようにするためと思われる(マイナスの残高が加わると総負債が減って見えてしまう)。各bitは0か1かのどちらかであり、それを証明するのにステップ3でrange proofを作っているのか?

各顧客は以下の手順で自分の残高が正しいか検証することができる。

  1. 取引所にログインして、今回の使用されたCIDのnonceの値と、残高のPedersen Commitmentを作成するのに使われたランダム値を取得する。
  2. 1のnonceを使って今回のCIDを計算し、それが公開されている債権者リストの中にあるか確認する。(リストの中に無い場合は取引所が不正を働いていることになる)
  3. 債権者リストの中に自分のデータがあれば、自分の債権リストの自分のデータの残高の各bit値のリストが正しい残高のコミットメントになっているか検証する。

基本的に顧客が確認できるのは自分の残高が間違っていないかということで、債権者リストの他の顧客のデータを見たからといって他の顧客の残高が分かるわけではない。

これらの具体的な計算が以下のProtocol2↓

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

そして債権者リストのすべての 残高の各bit値のリストを合計すると、総負債額へのコミットメント {Z_{Liabilities}}が計算できる。

債権者リストの拡張

債権者リストのCIDと残高へのコミットメントをリーフとしたマークルツリーを構成することで負債の証明を拡張することもできる。ツリーの内部ノードは2つの子ノードのハッシュとそれらの残高の合計のコミットメントが含まれるようになる。そうやって計算したマークルルートには全顧客の残高の合計へのコミットメントが含まれる。各顧客は自分の残高からマークルルートまでのパスが提供されれば検証が可能だ。このツリーを生成する場合、取引所の証明の生成時間が2倍になるため、オプションとされている。

プロトコル3 支払能力の証明

プロトコル1で総資産額へのコミットメント {Z_{Assets}}が計算され、

プロトコル2で総負債額へのコミットメント {Z_{Liabilities}}が計算されたので、

 {Z_{Assets - Liabilities}}

が0へのコミットメントであれば、総資産額と総負債額はイコールであることになり、取引所に支払能力があることを証明できるということみたい。(hの指数はランダム値なのにこの計算で0へのコミットメントになるというのがイマイチしっくりこない。。)

びったり同額になるということはなく余剰金が発生するケースも考えれる。その場合、余剰金へのコミットメント {Z_{Surplus}}を作成し(当然range proofも一緒に作る。)

 {Z_{Assets - Liabilities - Surplus}}

が0へのコミットメントか確認する。

制限事項

  • Provisionsはある時点における支払能力の証明を提供するのであって、その後の取引所の行動を含め、顧客の資産を確実に保護するプロトコルではない。
  • Provisionsでは公開鍵で口座の所有権を管理しているので、一度も使用されたことのないP2PKHのアドレスやP2SH、複雑なマルチシグなどのアドレスタイプについてはサポートしていない。基本的に取引所はP2SHのマルチシグでコインを管理していることが多いと思うので、実際に導入する際はP2SHベースのアドレスタイプをサポートする拡張が必要になる。
  • ProvisionsのプロトコルにFiat-Shamirヒューリスティックを利用することで非対話型のプロトコルになるが、この場合trusted setupが必要になる。trusted setupはしたくないので、将来的にzk-SNARKsなどを利用したproof of solvencyを模索してる模様。

というのがProof of Solvencyのプロトコルの概要みたい。

この他に悪意ある取引所が結託して取引所間で資産のアドレスを共有する結託攻撃へのアプローチや、総資産へのコミットメントを作成する際の匿名セットの選択方法など、詳しい内容はホワイトペーパー参照。

Proofs of Proof of Work

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」というホワイトペーパーだ↓

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が行われたチェーンか検証する。

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

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

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

データ量と計算量

データ量

Interconnected Blockchainでは各ブロックにinterlinkを新たに追加する必要があり、この分データ量が増える。ホワイトペーパーでは以下のようにT=2200で安定してる際に、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/2i を維持する最大の整数。具体的には、各ブロックはポインターのベクトルを運ぶ(これは複数のレベルにまたがるブロックチェーン内の標準的な逆方向リンクを拡張すると考えることができる)。このように変更されたブロックチェーンでは、ブロックは {interlink = \langle s_0, ..., s_l \rangle}と表されるポインターのベクトルを持つ。ここで {s_0}ジェネシスブロックを指し、i = 1, . . . , lと続く。 {s_i}は前のブロックを指し、 {\mathit T / 2^{i}}より小さいハッシュ値を持つ前のブロックを指す。lブロックチェーン内のハッシュがT /2lより小さい最大の整数であることに注意する {s_l}は最新のそのようなハッシュのポインタである)。

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

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

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

関連研究

ハッシュ値を使用する最初の提案はBitcoinフォーラムの投稿*1にあった。この投稿では、各ブロックに前のブロックのハッシュ値の半分未満のハッシュ値を有する最新ブロックへの単一back-linkを含めるための、Bitcoinプロトコルの変更が提案された。SPV Proofsでこのようなポインタを使用する可能性を含め、この変更に伴う潜在的なメリットについて議論された。

Bitcoin-development listに掲載された短い記事*2では、このアイディアはさらに、前の複数のブロックへのさまざまなバックリンクを含むデータ構造含むものとして提案された。正確なデータ構造は記述されておらず、最も適切なデータ構造を決定するのにはさらに研究が必要であることが示唆された。コンパクトなSPV proofsを構築する可能性やBitcoinとサイドチェーン間の「対称双方向ペグスキーム」の設計など多くのユースケースが議論された。この後者のコンセプトは、Enabling Blockchain Innovations with Pegged Sidechainsで定義されており、台帳の資産を1つのメインチェーン(Bitcoin)からペグしたサイドチェーンに転送することができる。サイドチェーンではブロックチェーンの設計に関する新しい機能を試すことができ、ペグすることでBitcoinブロックチェーンからこれらの代替ブロックチェーンへの流動的な資産の移動を可能にすると言われている。ペグのオペレーション自体は、メインチェーン上でサイドチェーンにおけるSPV proofによってのみアンロック可能な特殊なアウトプットに資金を移動するトランザクションを指す。これにより資金をメインチェーンからサイドチェーンへ移転させることができ、所有者が望めばメインチェーンに資金を戻すことも可能だ。効率的なSPV proofを構築することはこの仕組において重要な側面で、上記の短い記事に沿った提案が上記ホワイトペーパーに記載されている。敵対者がSPV proofの仕組みを利用する可能性も認識されており、明示的なデータ構造やproofの構築アルゴリズムの結論や正式な分析などはないが、いくつかの対策について議論されている。

最後に、SPVノードの検証に関連するBitcoinの変更は、ブロックチェーンのフルノードに影響を及ぼさないので、ブロックチェーン選択のためのGHOSTルールやInclusive Block Chain Protocolsのようなチェーン選択と報酬の仕組みの変更とは異なる性質を持つ。

序文

ホワイトペーパーでは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}と呼ばれる特別なタイプのチェーンによって決まる。

定義1

インデックス 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: 深さ1のinnerchain(ブロック(1, 4, 7, 9)で構成される)と深さ2のinnerchain(ブロック(1, 7)で構成される)を含む11個のブロックを持つinterconnected blockchainの図。各ブロックのinterlinkベクトルの値も表示されている。

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

定義2

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

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

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という2つのサブプロシージャを使用する。 {(\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のうち1つが、そのプルーフのサポート(軽量ノードが要求した追加ブロックを提供するの)に失敗するとMaxChainアルゴリズムはもう1方のノードのチェーンが正しいチェーンであると結論付ける(もしくはノードがリクエストに応答しない場合は失敗する)。より詳細には以下のように動作する。

  • 最初にアルゴリズムはRemoveCPlowを呼び出して、プルーニングされたsuffixを取得する(これは対話を必要としない)。続いてそれを {i > 0}かチェックする。このケース時点でプルーフは異なる深さを持つので、アルゴリズム {\pi_B^{\prime}.pow \geq  \pi_A^{\prime}.pow}と同時に {\pi_B^{'}.length \geq m}かチェックする。この2つの条件が成立する場合、軽量な検証者は {\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の範囲にありターゲットが2200で安定している場合、interlinkの数がnの対数であることを示している。

f:id:techmedia-think:20180106152743p:plain
Figure 2 : ターゲットT=2200の場合のブロックチェーンの長さを関数とした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*の説明は以下のとおり。

  1. AはAの動作をシミュレートし、さらに各ラウンドで完全な検証者として動作し、 {C_1, ..., C_e}の正直なノードにチェーンをリクエストする。全てのブロックを含むブロックツリーBTを維持し、そこに敵によって生成されたブロックを追加する。ランダムオラクルモデルではAハッシュ関数 {H(\cdot)}に対するAの全てのクエリを監視することが可能なので、A*はこれを実行可能であることに注意する。有効なブロックに対応しないAによるクエリは無視される。
  2. 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の定義において上記ケース2に必然的に対応する。この後の事象を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で実行する必要があるため、プルーフの検証中にいくつか注意を払う必要がある。動的な設定の分析については将来の研究として残しておく。