Quicksilver Protocol
1.概要
INZKに分類される Designed Verifier type
一つのgateを評価するためにwireの数だけVOLE correlationが必要になる。
論理回路の評価が可能であり、 Proof time, Mermory の効率が高いがProof sizeが大きくなる
gate by gateでCommitment PhaseとPriving Phaseを繰り返す
Commitment PhaseにはさらにSetup PhaseとOnline Phaseがある。
1.1前提知識
2. Commitment Phase
2.1 setup phase
ProverとVerifierが協力してN個のrandomなVOLE Correlationを作るphase
$ N=10^7の場合、この処理は20 nsくらいで終わる。
2.1.1Multiple Commitments From VOLE
最終的にProverとVerifierは以下の要素をそれぞれ受け取る
Prover
A length-N vector $ \vec{m}of which all individual elements belong to the field $ F_2^{128}
A length-N vector $ \vec{r}of which all individual elements belong to the field $ F_2
Verifier
A global key Δ that belongs to the field $ F_2^{128}
A length-N vector $ \vec{k}of which all individual elements belong to the field $ F_2^{128}
これらはVOLE Correalation:$ \vec{m}=\vec{k}-\Delta\cdot\vec{r}を満たす。
$ \begin{pmatrix}m_1 \\ m_2 \\ \vdots \\ m_N \end{pmatrix}=\begin{pmatrix}k_1 \\ k_2 \\ \vdots \\ k_N \end{pmatrix} -\Delta\cdot\begin{pmatrix}r1 \\ r_2 \\ \vdots \\ r_N \end{pmatrix}
2.1.2 Packing VOLE
後述するProving phaseの(batch)consistency checkでは$ C_0=D-C_1\cdot\Delta ($ C_0,C_1,D,\Delta \in{F_2^{128}})という形で複数のVOLE correalationをpackingする必要があるので、setup phaseでそれ用のrandom VOLE correlationを用意しておく。
具体的にはrandom VOLE correlations$ (r_0,m_0,k_0,\Delta)\dots(r_{127},m_{127},k_{127},\Delta)を$ R,M,K,\Delta \in F_2^{128}に変換することで、複数のrandom VOLE correlations を一つのrandom VOLE correlationsにpackingし、$ M=K-R\cdot\Deltaとして表現する。
つまり128個のVOLE correlationを一つのVOLE Correlationに変換する。
今までのVOLE correlationはrだけ$ F_2だった。
まず$ i \in{[0,127]} についてi番目のbitに対してのみ1をセットする(i番目以外の要素は全て0になる)selector gadget:$ g_iを定義する。ProverとVerifier はそれぞれ以下の多で項式をローカル計算する。
Prover
$ R=r_0\cdot g_0+r_1\cdot g_1+\dots+r_{127}\cdot g_{127}\in{F_2^{128}}
$ M=m_0\cdot g_0+m_1\cdot g_1+\dots+m_{127}\cdot g_{127}\in{F_2^{128}}
Verifier
$ K=k_0\cdot g_0+k_1\cdot g_1+\dots+k_{127}\cdot g_{127}\in{F_2^{128}}
これらはi番目の項だけ係数が1の127次多項式としてみなせる
VOLEプロトコルのセキュリティは、各パーティが相手パーティから受信した値に関する情報を持たないことを要求する。
疑問：Selectorつけたら一つだけだからpackingの逆では？どうやってgを生成する？
g_iに関して、お互い共通の値(0/1)でなければ機能しないはず
2.2 online phase
ProverがN個の要素を送信し、commitmentを生成するフェーズ。
ここでのcommunication complexityはNに対してlinearになる。
まずProverは$ \vec{w}をwitnessとしてcommitする。これは$ \vec{d}=\vec{r}-\vec{w}としてverifierに送られる。
これを受け取ったverifierはローカルで$ \vec{k'}=\vec{k}-\Delta\cdot\vec{d}を計算する。
すると、$ k=k'+(r-w)\Deltaなので、$ \vec{m}=\vec{k}-\Delta\cdot\vec{r}→$ \vec{m}=\vec{k`}-\Delta\cdot\vec{w}という式変換ができる。
これはVOLE correlationを満たし、hidingとbindingを保持している。
3. Proving Phase
3.1 Single AND gate
あるAND gateのproovingを示す。ここでは二つのinput wireのAND演算結果$ w_a \cdot w_bがoutput wire$ w_cの値と一致することを制約したい。
Notationを整理すると以下のようになる。
$ w : wire value(bit), $ m : IT-MAC, $ k : random, $ \Delta : global key
prover owns: $ w_x, $ m_x
verifier owns: $ k_x, $ \Delta
ここで満たすべきVOLE Correlationとwire valueの関係性は以下の通り
$ w_c = w_a \cdot w_b
$ m_a=k_a-w_a\cdot\Delta
$ m_b=k_b-w_b\cdot\Delta
$ m_c=k_c-w_c\cdot\Delta
AND gateでは二つの一次関数を掛け合わせると二次関数になりVOLE Correlationを維持できなくなるので、次数を1にする工夫が必要になってくる。
https://scrapbox.io/files/67712cb1cc111e7fc0e1f06b.png
そこでまずgate constraintsを表すためにProverとVerifierはlocalで保持する値を以下のように結合させる。
prover computes : $ A_0 = m_a\cdot m_band $ A_1 = w_a\cdot m_b+w_b\cdot m_a-m_c
verifer computes:$ B=k_a\cdot k_b-k_c\cdot\Delta
$ A_0,A_1,Bの三つのvalueはgate constraintsであり、
これらはVOLE correlation$ A_0=B-A_1\cdot\Deltaを満たす。言い換えると、commitmnet$ [A_1\rbrackを表す
このcommitmentにより、Verifierは$ w_c = w_a \cdot w_b を検証できる。
ただし、単純にProverがverifierに $ A_0,A_1をそのまま送るとwitnessに関する情報が漏れるので工夫が必要である。これは$ C_0=D-C_1\cdot\Deltaを満たす$ (C_0,C_1,D)\in{F_2^{128}}を導入することで解決される。
$ (C_0,C_1)はrandom valueでprivate input xとは独立しているので、正しい$ (A_0,A_1)を持っていないcheat proverは$ \Deltaを予測し、$ U,Vを導く必要がある。
$ C_0=D-C_1\cdot\Deltaの生成はこの記事の2.1.2を参照
1. Proverは以下の計算を行う
$ U=C_0-A_0 , $ V=C_1-A_1
2. Verifierは以下の計算を行う
$ W=D-B
3. Proverは$ U,VをVerifierに送信する
4. Verifierは$ U=W-V\cdot\Deltaを検証する
IT-MACとcommitmentにより、Verifeirは以下の点についてcheckする
その要素が確かにProverから送られたこと
Proverから受け取る要素が$ w_c=w_a\cdot w_bであること
このようにしてAND gatesが正しいinput(output) commitmentを含んでいることを確認するステップをconsistency checkと呼ぶ
3.2 Multi AND gate
複数のAND gatesを考える。
各AND gateごとにconsisitency checkを行うのは効率が悪いので、一つのcorrelated tupleにバッチする。これにはrandom linear combinationのテクニックが応用される
1. ProverとVerifierはそれぞれ$ (A_{0,1},A_{1,1})_\dots,(A_{0,N},A_{1,N})と$ B_1,\dots,B_Nを計算する
2. verifierはrandom seed $ s をサンプリングし、proverに送る。二人はPRGを使ってN random coeeficients $ x_1,\dots,x_Nに拡張する
3. proverは$ U=C_0-\sum_{i=1}^{N}{x_i\cdot A_{0,i}},$ V=C_1-\sum_{i=1}^{N}{x_i\cdot A_{1,i}}を計算する。
同様にverifier は$ W=D-\sum_{i=1}^{N}{x_i\cdot B_{i}}を計算する
4.Proverは$ U,VをVerifeirに送る
5.Verifeirは$ U=W-V\cdot\Deltaをチェックする
4. 効率性
1. フェーズ構成:
Setup phase: 2つの当事者がVOLEプロトコルを使用して N 個のVOLE相関を生成します。このフェーズの通信コストは N に対して多対数的（polylogarithmic）
Online phase: Proverは N 個のフィールド要素を送信してコミットメントを生成。この際、通信コストは N に対して線形で、計算コストはフィールド要素の加算と乗算のみで済むため非常に軽量
2. 性能: セキュリティパラメータ( \lambda = 10^7 )の場合、1つのVOLE相関を生成するのにかかる平均時間は20ナノ秒未満
3. 比較: 従来の加法的ホモモルフィック非インタラクティブコミットメントでは、大規模な計算コストが必要な公開鍵操作に依存していますが、VOLEベースの方式はインタラクティブである代わりに、計算効率と軽量さを重視している
https://scrapbox.io/files/6778b9e9c7d7ad7c46e0836a.png
参照