SoraSue Commitments

SoraSueが暗号学・ブロックチェーンなどに関して学んだことを記録していきます。

ゼロ知識証明の数学的概要

初めまして。
趣味で暗号学やBitcoin・Ethereum周りの技術を勉強している、SoraSueと申します。
このブログでは、僕が学んだ暗号学の理論や技術、論文の内容をcommitしていきます。
(同時にopenしているじゃないかというツッコミは無しで…)

第一回の記事では、Ethereumのプライバシー・スケーリング問題をある程度解決できる技術として注目されている、ゼロ知識証明プロトコルの数学的な概要について解説していきます。 ("ある程度"というのは、ゼロ知識証明だけではプライバシーを保護できないアプリケーションが存在するからです。)

ゼロ知識証明の目的と性質

ゼロ知識証明プロトコルとは、簡単に言えば証明者という役割の人物と検証者という役割の人物が行うやり取りのプロトコルです。 証明者は、自分がある問題の答えを知っていることを検証者に納得させたいと考えています。 しかし、答えそのものは検証者に教えたくないため、証明者は答えの所有を示す証明データを検証者に送ります。 検証者はその証明に対してある検証処理を行うことで、証明者が答えを知っているか否かのみを確認することが可能です。 このように構成されるプロトコルが、ゼロ知識証明プロトコルになります。

ゼロ知識証明プロトコルの中にはさらに細かい分類が存在するのですが、そのうちZK-SNARKsやZK-STARKs、Bulletproofsと呼ばれるものは、次の性質を満たします [1]。

  • 証明のデータサイズもしくは検証処理の計算量は、問題のサイズが大きくなっても十分小さいままである。(e.g. データサイズも計算量もLogオーダーでしか増加しない。)
  • 証明者は一回証明を検証者に送れば、それ以上やり取りする必要はなく非対話的である。(逆に、対話的なものは検証者から証明者へ乱数などを送る必要がある。)

プライバシー保護のためにゼロ知識証明を利用する際は、隠したい秘密情報を問題の答えとして、その情報が満たすべき要件を問題として表現し、ユーザーが秘密情報を使って証明を生成します。また、計算資源の乏しいクライアントが外部のサーバーに複雑な計算を委託する場合、サーバーが信頼できないものであれば返された計算結果が誤っている可能性がありますが、クライアントはその計算結果をZK-SNARKsなどで簡単に検証することができます。*1

ゼロ知識証明の数学的な仕組み - human-friendlyな問題からproof-friendlyな問題への変換

では、上で述べたゼロ知識証明の魔法のような性質は、数学的にはどのような手順によって実現されているのでしょうか？ 一言で言えば、証明で扱いたい問題を最初は人間が記述しやすい形式の問題(human-friendlyな問題)として記述し、それを元の問題と等価だが証明が簡単な形式の問題(proof-friendlyな問題)に変換することで、複雑な問題を簡潔に証明できるようにしています。*2

初めに、以下の説明は全てのゼロ知識証明スキームについて成り立つ話ではなく、少なくとも現在ブロックチェーン系のプロジェックトで実用化されているスキーム(e.g. ZK-SNARKsのGroth16 [2]やPlonK [3], Bulletproofs [4], ZK-STARKs [5])の多くで成り立つ考え方であることを断っておきます。これらのスキームでは、まずは問題を算術回路またはRAMプログラムという形式で表します。次に、その問題をconstraintsという(誤解を恐れず言えば)連立方程式のような形式に変換します。もしこの段階で証明するならば、証明者はそのconstraintsを満たす変数の値を知っていることを(変数自体は教えずに)示す必要がありますが、これを簡潔に行うのは難しいので問題を更に変換します。

最終的に、問題は多項式か内積の形に変換されます。どちらに変換するかはゼロ知識証明の具体的なスキームによって変わります。(e.g. PlonKでは多項式、Groth16では内積に変換する。)多項式の場合、証明者は「検証者が知っている d,a,zについて、 f(a)=zになるような秘密の次数 d多項式 f(x)を知っている。」ということを示し、内積の場合は「検証者が知っている n,zについて、内積が\bf{a} \cdot \bf{b}=zになるような秘密の長さ nベクトル \bf{a},\bf{b}を知っている。」ことを示します。実は、多項式に関してこのような証明を行うスキーム(polynomial commitment scheme)は、次数 dによらずコンスタントな証明データサイズ・検証計算量で作れることが2010年から知られていました [6]。内積についても、証明のサイズが O(\log n)でしか増加しないスキーム(inner product argument)が存在します [4]。そのため、多項式や内積はproof-friendlyな問題と言えます。

以上の話をまとめると、ゼロ知識証明スキーム(のうち実用化されているもの)は、問題を算術回路/RAMプログラム->constraints ->多項式/内積というように、human-friendlyな問題からproof-friendlyな問題へと変換します。変換した問題にはpolynomial commitment schemeやinner product argumentを適用できるので、証明者は秘密を隠したまま証明し、検証者は小さなデータと簡単な計算で証明を検証することが可能になるのです。

参考文献

[1] 岡本 龍明. 現代暗号の誕生と発展 ポスト量子暗号・仮想通貨・新しい暗号. 近代科学社, 2019.

[2] J. Groth, On the size of pairing-based non-interactive arguments, in: Annual international conference on the theory and applications of cryptographic techniques, Springer, 2016, pp. 305–326.

[3] A. Gabizon, Z. J. Williamson, O. Ciobotaru, Plonk: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge, Cryptology ePrint Archive (2019).

[4] B. B ̈unz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, G. Maxwell, Bulletproofs: Short proofs for confidential transactions and more, in: 2018 IEEE Symposium on Security and Privacy (SP), IEEE, 2018, pp. 315–334.

[5] E. Ben-Sasson, I. Bentov, Y. Horesh, M. Riabzev, Scalable, transparent, and post-quantum secure computational integrity, Cryptology ePrint Archive (2018).

[6] A. Kate, G. Zaverucha, I. Goldberg, Constant-Size Commitments to Polynomials and Their Applications, in: International conference on the theory and application of cryptology and information security, Springer, Berlin, Heidelberg, 2010, pp. 177-194.

*1:具体的には、サーバーはクライアントから与えられたプログラムと入力から計算結果を求めた後、「この計算結果はこの入力とこのプログラムから求めた結果と等しい」という問題について証明を生成します。クライアントはサーバーから計算結果と証明の両方を受け取り、その証明を検証することで計算結果が正しいことを確かめられます。（注意: ZK-SNARKsなど検証処理の計算量が小さいプロトコルを用いていれば、証明を検証する処理はクライアントでも実行することが可能です。）

*2:"human-friendlyな問題"、"proof-friendlyな問題"というのは僕の造語で、一般的に言われている概念・分類ではありません。