暗号と回路 (前半) - 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署名の検証などの計算量が大きいため、非現実的な計算コストを支払う必要があります。