SoraSue Commitments

この記事は、eeic Advent Calendar 2022の15日目の記事になります。

導入

皆さんこんにちは。そらすえこと末神奏宙です。アドカレのおかげで、久しぶりにブログを書く動機ができました。今回はeeicらしいテーマとして、（論理）回路の知識が暗号学の分野でどのように役立つか私見を書きたいと思います。

「暗号」と聞くと、多くの方は「特定の人のみが中身を解読できるようにデータを変換する手法」というイメージを持つでしょう。もう少し詳しい方は、「特定の人が特定のメッセージを発行したことを証明する手法」として、電子署名スキームもご存知だと思います。このような暗号スキームは、データが指定の方法で変換されるだけであり、アプリケーションによって処理方法が異なることはありません。

しかし、近年発展している高機能暗号では、同じ暗号スキームを用いながらも、アプリケーションの処理内容に応じてfunctionalにデータが変換されます。例えば、完全準同型暗号(FHE)と呼ばれる暗号スキームでは、単にデータを暗号化できるだけではなく、2つのデータ $x_0,x_1$ の暗号文 $\textsf{Enc}(x_0), \textsf{Enc}(x_1)$ だけから、それらをNOT, OR, ANDした値の暗号文 $\textsf{Enc}(\lnot x_0), \textsf{Enc}(x_0 \lor x_1), \textsf{Enc}(x_0 \land x_1)$ などを計算することも可能です。さらに、ある関数 $f(x_0,x_1)$ をNOT, OR, ANDゲートで構成される論理回路 $C(x_0,x_1)$ として表現すれば、ゲートごとに暗号文を変換していくことで、入力データの暗号文 $\textsf{Enc}(x_0), \textsf{Enc}(x_1)$ だけから任意の*1関数の出力の暗号文 $\textsf{Enc}(f(x_0,x_1))=\textsf{Enc}(C(x_0,x_1))$ を求められるのです。このように、高機能暗号ではその暗号スキームの方式だけではなく、アプリケーションで扱いたい関数に応じてデータがfunctionalに変換されます。そして、その関数を具体的に記述する手段の一つが回路になります。

以降では、回路を用いる高機能暗号の例として、ゼロ知識証明と秘密計算を紹介します。*2 前半(本記事)ではゼロ知識証明を扱い、後半で秘密計算と高機能暗号に対する個人的な意見を述べたいと思います。

ゼロ知識証明と回路

ゼロ知識証明(ZKP)とは、誤解を恐れず定義すれば、あるデータが特定の条件を満たしていることを、データそのものは教えずに第三者に対して証明することができる暗号スキームです。一般に、その証明を行う役割の人をそのまま証明者(prover)、証明者が提示した証明(proof)をチェックする役割の人を検証者(verifier)と呼び、検証者は本来の検証処理よりも大幅に小さな計算量・データ量で証明を検証することが可能です。この技術は、主に次の2つの用途に使われることが多いです。

プライバシー保護: 証明者がプライベートなデータを秘匿したまま、そのデータが特定の条件を満たすことだけを検証者に示す。
検証コストの圧縮: 検証処理の計算量が非常に大きいデータ・条件に対して、そのデータがその条件を満たすことの証明を証明者が作成することで、検証者の計算量を大きく圧縮する。*3

最近は、ブロックチェーン・クリプト界隈でZKPが~~もてはやされている~~有望な技術として大変注目されている訳ですが、それはブロックチェーンの1) 取引履歴がパブリックに公開されておりプライバシー保護が不十分である、2) 原則的にネットワークに参加する全てのコンピューターが同一の取引を検証するため処理可能な取引量が小さい*4といった課題を、ZKPで解決できる可能性があるためです。1の課題の場合、仮想通貨の送金額や残高情報は隠したまま、「送金額は元の残高以下である」などの送金時の条件を満たしていることをZKPで証明し、その証明をネットワーク内で公開することで、プライバシーを保護したまま取引の正当性を他のコンピューターに検証してもらうことができます [1-3]。また、課題2の解決策は、ZK-Rollupという名称で知られており [4]、現在のブロックチェーン界隈で最もホットなトピックの一つになっています。

ZKPの遊び方

ブロックチェーン界隈でZKPの重要性が増したことなどを背景に、ここ数年(2019~)実用化が大きく進み、誰でも簡単にZKPを利用できるようになりました。例えば、circomという言語を使うと、ZKPの詳しい仕組みを完全に理解せずとも、Verilogのような記法で、証明したい条件を回路として記述することができます。

次のコードは、circomドキュメントの"Signals & Variables"のページから引用したものになります。Verilogで喩えると、Multiplier2はin1, in2という2つの入力wireを受け取るモジュールであり、出力wire outがその積に等しくなるように制約しています。最後のcomponent main {public [in1,in2]} = Multiplier2();という行は、Multiplier2モジュールをトップモジュールとして利用し、入力wire in1, in2の両方をpublicにする、つまり検証者に公開することを表しています。ここで、もしcomponent main = Multiplier2();などと記述すれば、in1, in2は検証者に公開されません。検証者はoutの値のみ知ることができますが、この回路に対応する証明を検証することで、積がoutと等しくなるようなin1, in2の値を、証明者が何かしら知っていることを確かめられます。

pragma circom 2.0.0;

template Multiplier2(){
   //Declaration of signals
   signal input in1;
   signal input in2;
   signal output out;
   out <== in1 * in2;
}

component main {public [in1,in2]} = Multiplier2();

このように、各モジュールごとにsignalという変数を定義してその間の制約条件を記述することで、ZKPで証明したい条件を回路として実装することができます。circomを実際に書いてみたい方は、ぜひcircomのドキュメントをご覧ください！

なお、circomなどZKPの回路を記述するツールでは、多くの場合既存のアルゴリズムの実装を流用することができません。なぜなら、ZKP用回路の実装では、既存のチューリング完全なプログラミング言語にはない、次のような制限があるためです。

変数の実行時の値に基づいた、動的な条件分岐やループができない。(条件分岐については、x if a==1 else yと実装する代わりに、a * x + (1-a) * yという値として定義します。)
サイズが可変長の配列を利用できない。
いくつかの演算では、signal変数に値を代入する処理とそれが満たすべき制約条件を別々に記述する必要がある。(例:signal a, b, cに対して割り算の関係を定義したい時、まずc <-- a/bとcに商の値を代入し、その後a == b * cと制約条件を明記します。)

ハッシュ関数など既存のアルゴリズムを回路で利用したい場合、これらの制約を満たした実装を各ツールごとに製作することになります。例えばcircomの場合、circomlibというレポジトリにcircomの便利な回路実装がまとまっています。私も、halo2というZKPライブラリでRSA署名を検証するための回路を実装しました。普通のプログラミング環境だと当たり前に存在するアルゴリズムを一から作るのは大変ですが、個人的にはアルゴリズムの中身を知る良いきっかけになると思います。~~これでいつ人類が石化しても回路を一から書き直せますね！~~

今後のZKPの発展(というより、僕が注目しているもの)

今後、どのようなZKPの回路が開発されていくでしょうか？個人的には、次の3つの流れに注目しています。

ZKEVMなど、既存の命令実行環境の処理を逐一検証する回路

一つ目は、既存の命令実行環境の処理を逐一検証する回路です。これは、「アプリケーションごとに毎回新しい回路を製作するのではなく、既存の命令実行環境に対応する回路セットを1個作ることで、既存のプログラミング言語で書かれた処理をそのまま証明できるようにしよう」というモチベーションから開発されています。もう少し具体的には、幾つかのオペコードに従ってメモリやスタックの状態を更新するスタックマシンに対して、メモリやスタックの正しい状態遷移の条件を表す回路を各オペコードごとに実装すれば、その回路を順番に適用することで命令全体の正当性を証明することが可能です。雑に言えば、ある命令のバイトコードがオペコード[A, B, C]で構成されている時、A, B, Cの状態遷移に対応する回路の条件を順に全て満たしているならば、命令全体の状態遷移も正しいという話です。このような回路を用いると、その実行環境のバイトコードに変換されるプログラミング言語で実装された処理をそのまま証明することができます。そのため、既存の言語のライブラリ資産もそのまま利用でき、回路の開発効率は大きく向上するでしょう。

開発が現在進んでいるものとしては、EVM*5に対する回路であるZKEVM[5-8]、RISC-Vアーキテクチャの命令セットに対する回路のRISC Zero[9]などが挙げられます。特にZKEVMは、Ethereumの利用コストを低減したいという需要のために実用化が急がれていますが、それを抜きにしても、既存のプログラミング言語の処理をそのまま証明できる技術には大きな価値があると僕は思います。

電子メールなど、既存の認証付きメッセージを検証する回路

二つ目は、電子メールなど、現在幅広く利用されているかつ暗号学的な認証が付いているメッセージを検証する回路です。電子メールのDKIMというプロトコルの場合、メール送信者のドメインサーバーがメールの内容に対して電子署名を付与することで、メールの送信者メールアドレスが偽造されていないことを受信者が検証できます。これらは既に検証可能性が保証されている訳ですが、わざわざZKPを使うメリットはどこにあるのでしょうか？まず、ZKPでは一部の情報のみを公開しながら正当性を証明できるため、認証されたメッセージを部分的に隠しながら、それが認証されたメッセージの一部であることを示せます。先ほどの電子メールの例では、メール自体は公開せずに、1) 電子メール全体に対して有効な電子署名が存在すること、2) そのメールの送信者メールアドレスが指定のものであること、3) メールの本文の一部に「緊急」という文字列が含まれることを証明できます。次に、Ethereumなどのブロックチェーン上で動くプログラム(所謂スマートコントラクト)も、電子メールを効率的に検証することが可能になります。*6 それにより、電子メールの情報をブロックチェーン外部の情報を提供するオラクルとして利用する、電子メールで仮想通貨の送金を指示するといった、新しいインターフェイスを作れるのではないかと思います。詳細はこちらをご覧ください。

Deep Learningなど、機械学習の推論過程を検証する回路

三つ目は、機械学習の推論過程を検証する回路です。例えばDeep Learningの場合、各ニューロンの線形計算や活性化関数の過程を全て検証することで、ある入力に対する推論結果が指定の値（e.g., 分類モデルの場合なら特定のクラス）になることを証明できます。MNISTの分類など簡単なタスクをZKPで証明した事例はいくつかあり[10]、pytorchなどと同じ要領でモデルを記述できるライブラリも存在しています[11]。ただし、実用的なサイズのモデルに対する証明を実用的な計算量やメモリ消費量で生成できるかは定かではありません。

先述した「既存の認証付きメッセージを検証する回路」と組み合わせると、電子メールについて単にデータの存在を示せるだけではなく、そのメールに添付された画像に特定の顔写真が映っていると証明することも（理論上）可能です。つまり、データの存在証明からその編集・分析過程までを、一つの証明の中で示せるのです。特に、その証明をスマートコントラクトで検証する場合、Ethereumなどのブロックチェーンが電子メールのドメインサーバー以外の第三者を必要とせずに電子メールを解釈することができるという点が、非常に興味深いと思います。

（後半に続く。）

参考文献

Bünz, B., Agrawal, S., Zamani, M., & Boneh, D. (2020, February). Zether: Towards privacy in a smart contract world. In International Conference on Financial Cryptography and Data Security (pp. 423-443). Springer, Cham.
Sasson, E. B., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., & Virza, M. (2014, May). Zerocash: Decentralized anonymous payments from bitcoin. In 2014 IEEE symposium on security and privacy (pp. 459-474). IEEE.
AZTEC, Aztecprotocol, https://github.com/AztecProtocol/AZTEC/blob/master/AZTEC.pdf, (Accessed on 12/14/2022).
Buterin, V. (2021, January). An Incomplete Guide to Rollups, https://vitalik.ca/general/2021/01/05/rollup.html, (Accessed on 12/14/2022).
privacy-scaling-explorations. (n.d.). Circuits for zkEVM, https://github.com/privacy-scaling-explorations/zkevm-circuits, (Accessed on 12/15/2022).
0xPolygonHermez. (n.d.). zkEVM Prover, https://github.com/0xPolygonHermez/zkevm-prover, (Accessed on 12/15/2022).
matter-labs. (n.d.). zkSync: scaling and privacy engine for Ethereum, https://github.com/matter-labs/zksync, (Accessed on 12/15/2022).
StarkWare. (n.d.). StarkNet and Cairo Documentation, https://www.cairo-lang.org/docs/index.html, (Accessed on 12/15/2022).
risc0. (n.d.). RISC Zero, https://github.com/risc0/risc0, (Accessed on 12/15/2022).
0xPARC. (2022, April). ZK Machine Learning, https://0xparc.org/blog/zk-mnist, (Accessed on 12/15/2022).
zkonduit. (n.d.). EZKL, https://github.com/zkonduit/ezkl, (Accessed on 12/15/2022).

*1:厳密には、計算量の上限が決まっている、動的に処理が変わる条件分岐やループは使えないなど、いくつか制限はあります。

*2:「ゼロ知識証明は広義の秘密計算に含まれうる」、「この2つではジャンルの大きさが異なり、対比させるのは不適切だ」などの批判はあると思いますが、ここでは分かりやすさを優先しているため、ご了承いただけますと幸いです。

*3:ZKPの方式によっては、元のデータサイズや検証処理の計算量に依らず、数百byteの証明データに対して数百ms程度の計算を行うだけで検証することができます。

*4:とても雑な説明です。突っ込まないで。詳しくは、"blockchain scailability "などのキーワードで調べてみてください。

*5:Ethereumで使われる仮想マシン<-雑すぎる説明

*6:理論的には、ZKPを使わずともスマートコントラクトで電子メールを検証することは可能です。しかし、実際にはRSA署名の検証などの計算量が大きいため、非現実的な計算コストを支払う必要があります。

初めまして。
趣味で暗号学や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な問題"というのは僕の造語で、一般的に言われている概念・分類ではありません。

SoraSue Commitments

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

暗号と回路 (前半)

導入

ゼロ知識証明と回路

ZKPの遊び方

今後のZKPの発展(というより、僕が注目しているもの)

ZKEVMなど、既存の命令実行環境の処理を逐一検証する回路

電子メールなど、既存の認証付きメッセージを検証する回路

Deep Learningなど、機械学習の推論過程を検証する回路

参考文献

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

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

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

参考文献