本稿について
Origo Scalable Privacy Preserving Platform For Decentralized ApplicationsのVersion 0.1、最終更新日: 2018/5/5時点のものを対象とします。本稿では「Chapter 4. Technical Design」のうち「4.4. Zero knowledge Proof」の日本語訳を掲載します。
原文はこちらになります。
スポンサードサーチ
4. 技術設計（続き）
4.4. ゼロ知識証明
ゼロ知識証明（ZKP）はOrigoがスマートコントラクトを正確かつ完全に実行しつつプライバシーを保証するための非常に重要な手法である。ZKPは暗号理論に基づいて巧みに作られた手法である。ZKPにおいてはまず2つのパーティがおり、証明者と呼ばれる一方のパーティが検証者と呼ばれるもう片方のパーティに対して、あるステートメントが有効であることをなぜそのステートメントが有効であるかに関する一切の情報を共有することなく証明できる。ZKPプロトコルは以下の特性を満たしていなければならない。
- 完全性（Completeness）：誠実な証明者と誠実な検証者がいるならば、プロトコルは極めて高い確率で成功する。
- 健全性（Soundness）：秘密を知らない者が検証者を納得させられる確率は極めて小さい。
- ゼロ知識性（Zero Knowledge）：証明が何らの追加情報を漏らすことがない。
ZKPプロトコルを作る非常に直観的な方法は証明者と検証者間でインタラクティブなコミュニケーションができるようにするというもので、これはゼロ知識対話証明（Interactive Zero Knowledge Proof, IZKP）と呼ばれる。検証者は証明者に対して（ランダムに）何でも質問を立てることができる。この質問は、証明者が秘密情報を知っていて持っていると主張する秘密情報を本当に持っている場合に限り回答できるという前提に基づく。もちろん証明者の前回の回答をもとにして質問してもよい。
どんなIZKPでも（検証者がパブリックなコインの表裏検証者であれば、つまり検証者が行うランダム選択がパブリックであるならば）Fiat-Shamirヒューリスティック[12]を利用したランダムオラクルモデルでセキュアかつゼロ知識性を有する非インタラクティブなプロトコルに変換することができる。ここでは全てのランダム試行がハッシュに置き換えられる。より具体的に言えば、学術的には非対話型ゼロ知識証明（Non-Interactive Zero Knowledge Proof, NIZK）はユーザのインプットを曝さないスマートコントラクトを実現するためのツールとして提案されたものである。だが、スマートコントラクトを搭載するブロックチェーンでの通信は高価であることとスマートコントラクト自体の計算能力が非常に制限されているという事実ゆえに、NIZKはスマートコントラクトの実用に関して限界がある。現在広く普及しているSNARKs[15]でさえも、スマートコントラクトについては中立的な選択でトラステッドセットアップを要する。トラステッドセットアップのコアとなる共通参照文字列（common reference string, CRS）は通常は長くスマートコントラクトそれぞれに特有のものであり、このことが潜在的なバックアップのせいでSNARKsスキームを信頼できないものにしている。
演算回路（AC）は各電子回路のコアとしてあらゆる数学的表現を作るのに用いることができる。これは加減乗除のような小さな論理操作の組合せである。例えば図4.1は(a+b)*c/dのACフォーマットを示している。
（a）あらゆる計算条件は、いくつかの入力をとり真偽値true or falseを出力するACで表現できること、（b）形式的に仕様化されている言語でチューリング完全なスマートコントラクトは、複雑な計算条件の集まり・相互作用とみなすことができるという事実に基づけば、スマートコントラクトを演算回路に移すというのは驚くようなことではない。任意のACに関して効率的なゼロ知識証明論証を生成する別の手法、つまり証明者がACを満たすような、あるいはACの出力を真にできるような然るべきインプットを持っていることを証明できる手法も提案されている[7、16]。従って、コントラクトのデータや情報を共有せずにコントラクト実行の正当性を証明することは可能になっている。
4.4.1. Origoにおけるゼロ知識証明
Origoでは、ゼロ知識証明をトランザクション情報（送受信者アドレスと金額）とスマートコントラクトのインプット/アウトプットを守るために用いる。セクション3.3に基づくと、プライベートスマートコントラクトを実行する場合、複数のフェーズでパーティPi（i ∈ [N]）と実行者PE双方からのコミットメントを検証するためにZKPが必要である。
- コミットフェーズ：パーティPi（i ∈ [N]）は十分なコインパーティCi（i ∈ [N]）をスマートコントラクトSCに入れたことを証明する必要がある。
- statement := NIZK.Prove（Pi, （Ci||Ki）, witness）（i ∈ [N]）
- NIZK.Verify（Pi, statement）
- 実行フェーズ：パーティPi（i ∈ [N]）はスマートコントラクトSCの自身のプライベートなインプットIprivi（i ∈ [N]）が実行者の公開鍵KEで正しく暗号化されていることを証明する必要がある。
- Iprivi := ENC（Ii, KE）（i[N]）（オフチェーン）
- statement := NIZK.Prove（Pi, Iprivi, witness）（i ∈ [N]）
- NIZK.Verify（Pi, statement）
- 確定フェーズ：実行者PEは自身が正しくスマートコントラクトを実行して正しいアウトプットOi（i ∈ [N]）を出したことを証明する必要がある。
- statement := NIZK.Prove（Pi, Oi, witness）（i ∈ [N]）
- statement := NIZK.Prove（Pi, Iprivi, witness）（i ∈ [N]）
Origoにおける上述の証明プロセスは全てオフチェーンで行われ、完了するまでに数秒から数分かかる可能性がある。検証パフォーマンスの総意はセットアッププロセスの必要性と証明/検証サイズとの間のトレードオフである。
4.4.2. トラステッドセットアップ
上述のように、現在のほとんどの手法はアプリケーションごとにトラステッドセットアップのステップが必要で、そのために信頼できる第三者かマルチパーティ計算（MPC）を利用する必要がある。しかしOrigoはプライバシー保証のスマートコントラクトをサポートするように設計されるので、各スマートコントラクトにはユニークなCRS（共通参照文字列）を生成するためのトラステッドセットアップが必要である。どのトラステッドセットアッププロセスを採用するとしても、プライバシー保証のスマートコントラクト生成をとても重く柔軟性のないものにしてしまう。ゆえにプライバシー保証のスマートコントラクトにとって、Origoを実用的にするのにトラステッドセットアップは必ずしも必要不可欠というわけではない。プライベートトランザクションに関してはトラステッドセットアップの耐性を持つことができる点には留意されたい。というのも、一度実行するだけでよいからである。そして産業的にも有効なセットアップを行った事例が既にある。
私たちはトラステッドセットアップなしで有効なZKPプロトコルを提供する新手法[7, 15]をいくつか調査した。表4.1に示すように、現時点でトラステッドセットアップのない実用的な証明システムは検証者の効率性が悪化することが分かる。高いコストのかかる検証者は、検証をオンチェーンで行わなければならないのであればコンセンサススピードをさらに悪化させる。この問題に対処するには、トラステッドセットアップのない新しい証明システムに起因するドローバックを最小化するためにオフチェーン検証が必要である。
（※筆者注：高速フーリエ変換（FFT）とは本来複雑性O(n2)であるものをO(nlogn)にするもの（厳密には本来の複雑性により異なるが）、線形（linear）とは複雑性がO(n)であることを指す。）
4.4.3. セキュアマルチパーティ計算との比較
ZKPのほかに、準同型暗号やセキュアマルチパーティ計算などのプライバシー保証テクノロジについても調査した。セキュアマルチパーティ計算はインプットをプライベートに保ちつつパーティがインプットに対して連帯して関数を計算できるようにするものである。スマートコントラクトに応用すれば、スマートコントラクトの実行結果を連帯して計算しつつ、インプットはプライベートな状態に保つことができる。
しかし、MPCはパーティ間で複数ラウンドのインタラクションが必要なのに対してNIZKは証明者と検証者間での複数ラウンドのインタラクションは不要である。また、全参加者間で実行結果がプライベートであることを保証する手法は存在しない。最も重要なことは、MPCの計算複雑性はZKPよりもはるかに高いということで、限られた範囲のアプリケーションにしか適用できないということである。このことから、ZKPはプライバシー保証のアプリケーションプラットフォームを構築するのにベターなソリューションだと考えている。
4.4.4. 結論
プライベートトランザクションの効率性を保証するため、プライベートトランザクションの検証にトラステッドセットアップを要するZKPの適用が望ましいと考えている。検証時間についてより効率的であり、検証をブロックチェーンで実行可能だからである。プライバシー保証のスマートコントラクトそれぞれがトラステッドセットアップを行うことを必須とするのは非実用的である。従って、コントラクト実行の検証にはトラステッドセットアップが不要なZKP手法を適用するのが望ましいと考えている。
（Origoホワイトペーパー日本語訳3 ←← 前）｜（次 →→ Origoホワイトペーパー日本語訳5）
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。