概要
ビットコインのブロックデータは時間経過に従って概ね線形に増加する。これは全てのトランザクション履歴を管理する暗号通貨においては避けられないことのように思える。
しかし、過去のブロックデータとは結局の所特定の形式に従ったデータであれば、その中身は問われないはずだ。つまり、例えば、100番目のブロックの採掘に成功したのがアリスなのかボブなのかは、プロトコルに従っている限りは問題でない。
ということは、「ブロックの高さXまでのブロックデータが特定のルール（この場合はビットコインコアのコンセンサスルール）に従って正しい方法で生成され、かつその結果として得られたUTXOセットがYである」ということが、ブロックデータ無しに（途中の計算を省略して）暗号学的に証明できるならば、自分でブロックデータをダウンロードせずにYを信頼できる。
これは暗号通貨におけるIBD(Initial Block Download)問題を解決するように思える。
実際にそのような問題を考えてみると、データ無しにその生成と計算の履歴を証明することは容易ではないとすぐにわかる。しかし最新の 証明付きデータ (PCD)または 段階的検証可能計算(IVC) という暗号学的構成を用いることで、少なくとも理論上はその仕組みが実現可能であるとされる。ただし、実現可能なのはビットコインに似たシステムであり、厳密に今のビットコインと同じものではない（＝コンセンサスの変更が必要である）ことに注意する必要がある。（コンセンサス変更が不要な同様の検証については[10]を参照。）
このようなシステムを実現するためのアイデアを記したのが本稿で紹介する [1]の論文である。
前提知識
簡潔非対話知識アーギュメント (SNARK)
[2][4][11]を参照。知識証明の一種であり、検証者は証明の正しさを短い時間で検証でき、かつ、証明の長さが定数サイズとなるもの。二次スパンプログラム(QSP)を楕円曲線と双線形写像上で再現することで行う実装が有名。
これをゼロ知識で行うzk-SNARKというゼロ知識証明のグループもあるが、今回の問題設定においてはゼロ知識で隠したい情報は無いので、ゼロ知識性を使う場面はない。
証明付きデータ (Proof-carrying data: PCD)
[3]を参照。
遵法述語(Compliance predicate)という、特定のデータを検証する条件を設定し、その条件に沿った形で計算されたデータと、データが正しく計算されたことの証明書を考える。データと証明書のペアが証明付きデータである。ある証明付きデータAから派生した証明付きデータBは、Bが正しいということの証明に加えてAの計算が正しいということの証明も可能であるような形式を持つ。
再帰的にこれに従えば、あるデータが特定の条件に沿って改変された結果と、その改変された歴史の証明を保持することが可能になる。
以下の図のようにデータmと証明πをやりとりして最終的に検証者がデータと証明の正当性を確認する。元々は分散コンピューティングの中で信頼できない計算ノードに、特定の計算を証明可能な形で強制するために考えられた技術である。
これは 段階的検証可能計算 (Incrementally verifiable computation: IVC) というものを拡張し一般化した概念と言える。
PCDは当初具体的な実装のない概念的な存在[3]として誕生したが、SNARKアルゴリズムが存在する時には具体的にPCDを構成できることが後に判明した[2]。このあたりの歴史については[9]を参照。
段階的検証可能計算 (Incrementally verifiable computation: IVC)
[5] を参照。非対話知識証明においては、証明者の空間計算量を犠牲に（Poly((元の空間計算量))程度の増加）、検証者の空間・時間計算量を定数にできるという定理に基づく。上記PCDが有向非順回グラフであるのに対し、IVCは直線的に証明が繋げられていく。
[1]の論文で実現したい、ブロックチェーンのようなログが追加されていくタイプの台帳に対する証明においてはPCDよりもIVCのイメージに近いが、実装に使った libsnark ではPCDとしてまとめられている。
一般的な簡潔非対話知識証明(SNARK)から証明付きデータ構造(PCD)への変換
[2]を参照。PCDの遵法述語の内部で以下の2つの計算を要求することで実現する。
- SNARKで証明を作成する
- 一つ前のPCD証明をSNARKで検証する
すなわち、SNARKの証明ステートメントの中に別の証明の検証を含むような構成になる。
しかし、実際に[4]などのSNARKを使って証明を構成しようとすると、非常に煩雑な証明になる。これは、単一の楕円曲線E上ですべての証明を構成しようとすると、Eの位数とE上で定義された有限体Fの標数が原理的に一致しないのにもかかわらず、Eに関するステートメントをFの中で証明する必要が出てくるからである。
この問題は[8]の論文で以下のようにして解決された。
もしも2つの楕円曲線E1, E2で、互いの位数と有限体上の標数が相互に一致し参照し合うようなもの（友好的ペア; amicable pair）があれば、その曲線を使って以下のように証明を効率よく再帰的に構成できる。
- 最初の証明はE1上で証明する。
- (1)を検証できることはE2上で証明する。
- (2)を検証できることはE1上で証明する。以下繰り返し。
なお、実際に[8]で使用された曲線はMNT4-MNT6と呼ばれるペアである。MNTは「宮地-中林-高野」の略であり、研究者の名前に由来している。
論文の解説
ブロックの検証と生成を行うマイナーは、現在のPoWに代わって「これまでの歴史的なブロックの積み重ねが正しかったことの検証」と「新しいブロックを追加する計算が正しく行われたことの証明の生成」を実行することでブロック生成を行う。
これだけであればIVCを実装しただけであるが、この論文ではマイナーによる証明生成の際に行われる計算を以て「PoWが副作用を持つ有意義なものになるようにする」ことも同時に実現しようとしている。
ここでいう副作用とは、証明の生成の際にかかるコストのことである。
たとえば、以下の実験結果の表によればトランザクション数が50からなる場合の証明者の証明生成時間は196.91秒であり、確かに計算に負荷がかかっていると言える。
難易度調整を考えると、特定の難易度d以下の値を持つハッシュを証明と同時に生成する必要があることになる。
この時、証明の一部だけを細工することで難易度d以下になりうるハッシュ値の候補を生成できてしまうと、確実に証明の生成とPoWが一致していることにならないと著者は考えているらしく、難易度d以下になりうるハッシュ値の候補を再度生成するには、一から証明を生成しなおすことをマイナーに強要する構成についても書いている（そこまでせずに証明の生成とPoWは別のものとして捉えてもいいのではないかと思うが）。
なお上図では検証者の検証時間はトランザクション数に関係なく定数であり、証明のサイズも373バイトと非常に小さいことで、PCDが実際に実現されていることが確認できる。
考察
この論文のスキームはビットコインとは厳密には異なる。
- アカウントモデルである。
- Scriptが存在しない。
- 80ビットのセキュリティしかない（使用したlibsnarkライブラリ中のMNT4-MNT6曲線の制約によるもので、128ビットのセキュリティでも構成は可能）。
- トラステッドセットアップが必要である。
- したがってフォークが必要である。
スキームが比較的新しく、追加の暗号学的仮定(トラステッドセットアップなど)を要し、さらにフォークが必要なためすぐにビットコインのコードに取り入れられることは無いと思われる。しかし、既に類似のスキームを実装しようとしているプロトコルで有用性が証明されればビットコインにも将来的に取り入れられる可能性がある。
また、ビットコイン本体のフォークを必要とせずにそのような効率的検証を行うプロトコル[10]も理論上は構成可能であるためそちらは今後も発展の余地がある話題であると考える。なお[10]では再帰的SNARKによるIVC/PCDではなく STARKを利用している。
なお知識証明プロトコルを使って証明を縮約するアイデア自体は[12]から存在している。
本論文の発表後にセキュリティやトラステッドセットアップの問題を解決した論文がいくつか出ている[6][7][9]ため、そちらも参照のこと。
参考文献
[1] Proof of Necessary Work: Succinct State Verification with Fairness Guarantees https://eprint.iacr.org/2020/190.pdf
[2] Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data https://eprint.iacr.org/2012/095.pdf
[3] Proof-Carrying Data and Hearsay Arguments from Signature Cards https://www.cs.tau.ac.il/~tromer/papers/pcd.pdf
[4] 論文解説: Quadratic Span Programs and Succinct NIZKs without PCPs https://tech.hashport.io/2184/
[5] Incrementally verifiable computation or proofs of knowledge imply time/space efficiency https://iacr.org/archive/tcc2008/49480001/49480001.pdf
[6] Recursive Proof Composition without a Trusted Setup https://eprint.iacr.org/2019/1021.pdf
[7] Reducing Participation Costs via Incremental Verification for Ledger Systems (レビュー論文) https://eprint.iacr.org/2020/1522.pdf
[8] Scalable Zero Knowledge via Cycles of Elliptic Curves https://eprint.iacr.org/2014/595.pdf
[9] 第三者を信頼せずに段階的検証可能計算(IVC)を実現するHaloの解説 https://tech.hashport.io/3778/
[10] https://github.com/ZeroSync/ZeroSync
[11] Halo2で使われている最新のzk-SNARKプロトコルPLONKの数学的解説 https://tech.hashport.io/3711/
[12] Really Really ultimate blockchain compression: CoinWitness https://bitcointalk.org/index.php?topic=277389.0
