Plonkup
前提
pinochioやgroth16は固有のstructured reference string (SRS)を必要とし、異なるMPCによるTrusted Setupが前提であった。
しかし、Marlin, PlonkなどのUniversal SNARKと分類されるプリミティブではUpdatable SRSを用いた全く異なるMPCにより、いつでも誰でもどんな回路でも(限定されたサイズに限り)使用できる。
Plonkについておさらいする。
q = selector vectors, a = left wire, b = right wire, c = output とすると
$ qLi · ai + qRi · bi + qOi · ci + qM i · aibi + qCi = 0.
またset of selector vectors は
$ {q_L = (q{L_i})^n_{i=1}, q_R = (q_{R_i})^n_{i=1}, q_O = (q_{O_i})^n_{i=1}, q_M = (q_{M_i})^n_{i=1}, q_C = (q_{C_i})^n_{i=1}}
となる。
PlonkはKate commitments を用いて、a,b,cベクトルの各iにおける要素がi-th constraintsを持っていることを証明し、wireが正しいgateに接続していることを証明する.
この第二の条件は、変数の並べ替えを表す追加のベクトルを用いて構築される grand product argumentによって強制される。
XOR, AND演算の計算コストを抑える手法の一つとして、Plonkupの設計者はよく使われる計算をlookup tableに登録し、そこから必要に応じて引き出す手法を提案した。これは、元の計算全体を、addition、multiplication、constantゲートの他に、Lookup gateと呼ばれる第4のタイプのゲートを用いて、より一般的なタイプの回路に変換できるというもの
ここでは、ルックアップゲートをファンイン2、ファンアウト1のゲートと考え、その動作を公開テーブルで記述する。この場合、表は3列で、入出力ごとに1列、各行は出力と入力の組の関係を記述しなければならない。
この種のゲートを回路に組み込む場合、証明者は自分の証人の値がテーブルの中に存在することを証明することになる。
数学的準備
基本的にplonkを理解できれば準備ok(読んでない)
Kate Commitment
paring
ラグランジュ補間公式
3.1 General Overview
Lookup tableの選択
プロトコルのルックアップ部分とPlonK部分は同じ変数を参照できる必要があり、通常の演算ゲートの出力変数がPlookupゲートの入力となり、逆もまた然り
そのため、演算ゲートとLookup gateで同じwireを使用し、必要に応じてLookup gateのみを選択するセレクタqKを使用する。
公開されたテーブル( 3 columns and n rows)として、$ T ∈ F^{n×3} を定義し、$ T_{i,j}をその要素とする
行(row)を圧縮するため、$ i∈[n]、$ ζ∈F(は検証者から得たランダムな要素)とした以下の要素からなるベクトル$ t = (t_1, . . . , t_n) ∈ F_nを定義する。
$ t_i = T_{1,i} + ζT_{2,i} + ζ^2T_{3,i}
nとdを二つの整数とし、$ f = {f_i}^{n}_{i=1}∈F_n と$ t = {t_i}^{d}_{i=1}∈F_d を$ {f_i}^{n}_{i=1}⊂ {t_i}^{d}_{i=1}∈F_dとなる二つのベクトルであるとする。
fに現れる値がtに現れるのと同じ順序であるとき、fはtによってソートされていると言う。
いずれも長さ$ nのquery vector $ fとtable vector $ t を定義し、proverはvector $ s = (f,t)を計算し、$ tでソートする。
回路のゲート数、つまり演算ゲートとLookup gatesの総和はn以下と仮定する。
ベクトルtの長さ(表Tの行数と一致)もn以下とする。
回路がm本、Tがn行の場合、m < nのとき、長さが一致するまでワイヤはm - n個のダミー値で、セレクタはm - n個のゼロでパディングされる
n < mなら, テーブルの要素の1つをn・mコピーしてパディングする。
query vector$ f = (f_1, ... , f_n)は、ワイヤa, b, cから構成され、ルックアップセレクタ$ q_{K_i}が0のとき、$ f_iは公開テーブルからダミー値をとり、$ q_{K_i}が1のとき、$ f_iは圧縮となる。すなわち、$ f_iを次のように定義する。
$ f_i =(a(ω^i) + ζ · b(ω^i) + ζ^2· c(ω^i)if the i-th gate is a lookup gate,
$ f_i =T_{1,n} + ζ · T_{2,n} + ζ^2· T_{3,n}otherwise.
ランダムに選択されたδを用いて、tとsのrandomized difference setsをは以下のようになる
$ ∆t_i = \left\{ \begin{array}{l}\displaystyle t_i + δt_{i+1}\; for\; i ∈ {0, ..., n − 2} \\t_i + δt_0, \;for\; i = n − 1\end{array} \right.
$ ∆s_i = \left\{ \begin{array}{l}\displaystyle s_i + δs_{i+1}\; for\; i ∈ {0, ..., n − 2} \\s_i + δs_0, \;for\; i = n − 1\end{array} \right.
ここで、sを以下のように分割する
$ h_1 = (s_0, s_2, s4, ..., s_{2n−2}) \;, h_2 = (s_1, s_3, s_5, ..., s_{2n−1}).
この分割は、順列多項式表現(permutation polynomial expression)を形づけるものであり、plookupでも同様に分割されるが、余分な検証を必要としていた $ ∆s_{2i} = s_{2i} + δs_{2i+1} は$ h_{1i} + δh_{2_{i}}と表現でき、$ ∆s_{2i+1} = s_{2i+1} + δs_{2i+2} は$ h_{2_{i}} + δh_{1_{i+1}}と表現できる。
このとき、順列多項式表現は以下のようになる
$ Z(Xω) = Z(X)\frac{(1 + δ)(ϵ + f(X))(ϵ(1 + δ) + t(X) + δt(Xω))}{(ϵ(1 + δ) + h_1(X) + δh_2(X))(ϵ(1 + δ) + h_2(X) + δh_1(Xω))}
さらに、前処理されたテーブルのソート版(t')を導入することにより、上記の順列多項式を修正し、拡張する。
これにより、複雑さO(nlogn)のアルゴリズムでソートされた多項式sを構成できるようになり、最終的に効率が向上する。
plookupでもソートアルゴリズムは、テーブルカラムとクエリカラムの両方が、チャレンジスカラーの昇順乗を持つフィールド要素の単一ベクトルに圧縮された後に実行される。その結果、フィールド要素のリストに関してソートすることができる適用可能なアルゴリズムの複雑さクラスは、他のプローバ操作の複雑さクラスとは似て非なるものとなる
証明者は$ \frac{t'i+θ}{ti+θ}を追加することで積の並べ換えから制約を強制することができる。
最終的な順列多項式表現は以下のようになる
$ Z(Xω) = \frac{Z(X)(1 + δ)(ε + (X))(ε(1 + δ) + t'(X) + δt'(Xω))(θ + t'(X))}{(ε(1 + δ) + h_1(X) + δh_2(X))(ε(1 + δ) + h_2)(X) + δh_1(Xω)(θ + t(X))}
Multiset checks
アイデアとして、サンプリングでマルチセットを検証するような処理がある。
Permutations via Multiset checks
Table lookups via Multiset checks
aとbの集合が等しくない(ペアとならない)場合は失敗する確率が高いのでパディングする?
セレクタの存在は、テーブルとゲートの関係に大きく関わってる
多項式
table polynomial
$ t(X) = \sum^{n}_{i=1} t_iL_i(X)
算術回路の演算を定義するselector polynomials$ q_M(X), q_L(X), q_R(X), q_O(X), q_C (X) ∈ F_{<n}[X]
lookup gateのセレクタとして追加で$ q_K(X) ∈ F_{<_{n}}[X\;] を定義する
$ q_K(ω^i) = q_{k_i} = \left\{ \begin{array}{l}\displaystyle 1,\; if \;i-th gate\; is\; a\;lookup\; gate \\ 0,\; others\end{array} \right.
The identity permutation polynomials(恒等順列多項式) $ S_{ID1}(X) = X, S_{ID2}(X) = k_1 · X, S_{ID3}(X) = k_2 · X を a, b, c に適用し、$ H、k1 - H、k2 - H が $ F^∗ における別個の coset となるように定数$ k_1, k_2∈F を選び、3n 個の別個の要素から構成される。
$ H′:=H∪k1・H∪k2・Hとし、$ σ:[3n]→[3n]をpermutation(並び替え)とする。
ここで、$ i →ω^i, n + i →k_1・ω^i, 2n + i →k_2・ω^i を介して $ [3n] を $ H′ に同定する。
最後に、$ σを適用して得られる3nからH′への写像と、このH′への射影写像を示す$ σ^*を以下に定義する。 $ σ^*は3つのコピー順列多項式$ S_{σ_1}(X), S_{σ_2}(X), S_{σ_3}(X) ∈ F<n[X]で符号化する。
$ S_{σ1}(X) = \sum^{n}_{i=1}σ^∗(i)L_i(X),
$ S_{σ_2}(X) = \sum^{n}_{i=1}σ^∗(n + i)L_i(X),
$ S_{σ_3}(X) = \sum^{n}_{i=1}σ^∗(2n + i)L_i(X)
途中で読むの止めてます。ここから先のロジックは参考資料をどぞ
参考資料