VOLE-Based ZK

CnP zkの効率的な構成手法の一種でnon-interactive CnP-ZK requiring public-key operations per gate.と紹介されている。

メモリ効率が良さそうではあるが、証明時間が短縮されるのか疑問。あと、任意のcommitment手法でもいけるのか？

大きくCommitment PhaseとPriving Phaseに分かれる。この記事は対話的コミットメント方式と、このコミットメント方式に基づく対話的ゼロ知識証明プロトコルを用いて説明している。

この対話的ZK証明では、加法的同型コミットスキームが重要な要素となる。証明者はまず入力値にコミットする。次に、ゲートをトポロジカルに通過することで、中間配線と出力配線に対するコミットメントを、証明者と検証者が共同で計算する。

加算ゲートの出力に対するコミットメントは、コミットメントスキームの同型性により、局所的に計算することができる。

乗算の出力に対するコミットメントの計算と証明には、計算コストと通信コストがかかる。この分野の研究では、このコストを削減することに焦点が当てられている。我々はゲート数に依存しないコストで、すべてのコミットされた乗算関係が正しいことを証明できる方式を提案する。これはバッチ・チェックとしても知られている。概念的には、バッチ・チェックはすべての乗算の正誤チェックを1つのチェックに変換し、2者が所有するすべての変換値が1つの線形関係を満たすことを検証する。

Quicksilver Protocol

QuicksilverはCnP-ZKプロトコルである。基本的な構成要素として、IT-MACベースのコミットメントと特別な一貫性チェックプロトコルを利用している。どちらの構成要素も、VOLEベースのIT-MACコミットメント・プロトコルを呼び出します

IT-MACをコミットメントスキームとして使用する。これをVOLEを使って効率的に実装できる点がポイントらしい

https://scrapbox.io/files/67555c736cb9d02f39b381ba.png

ProverとVerifierは(w,m,Δ,k)からなるIT-MACを協力して生成する。

global key:$ Δ,k ∈F_{2^{128}}はverifierのみ知ることができる。

only prover has $ ω,m∈F_{2^{128}}.

only verifier has$ Δ,k∈F_{2^{128}}

検証者はopening commitmentにおいて最終的に$ m=k-Δ・wを満たすことを確認する

ここで$ w ∈F_{2}であり、 binaryとなる

Commitment Phase

Quicksilverでは、まず証明者と検証者が共同で回路内のすべてのワイヤ値のコミットメント（IT-MAC）を生成する。