Plonk-4-约束与主协议

Posted on Edited on

论文原文 ==> 953.pdf (iacr.org)，PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge

6 约束系统Constraint systems

​ 给定整数m，n，且n≤m≤2n我们提出一种约束系统，该系统捕获扇入的两个算术电路，这些算术电路具有n个门和m条导线，不受限制地扇出。

​ 约束系统 C=(V,Q) 定义如下:

  • V的约束是 V=(a,b,c)，其中a,b,c∈[m]，[m]的阶数为n。我们将a，b，c分别视为C的左，右和输出序列。

  • Q=(qL,qR,qO,qM,qC)∈(Fn)，其中(Fn)的阶数为5，qL,qR,qO,qM,qC∈**F**n 为选择器向量，每个选择器向量的阶数为n。

x∈*F***m，i∈[n]，为了满足C，需要满足以下条件：
$$
(qL)i \cdot X{a_i} + (qR)i \cdot X{b_i} + (qO)i \cdot X{c_i} + (qM)i \cdot (X{a_i}X_{b_i}) + (qC)_i = 0
$$
​ 为了定义基于C的关系，我们将其扩展为包括正整数l≤m和“公共输入”的子集 *I*⊂[m]。在不失一般性的前提下，假设**I= {1,…,l}。

​ 定义Rc为一组集合对(x,ω)，其中x∈*F**l，l为阶数，ω∈F***m_l，m-l 为阶数，则 x:=(x,ω)满足C。

​ 我们将继续展示此类约束的一些有用实例。

算术电路：n个门且扇入为2的电路，每个门是加法门或乘法门，约束系统可以如下：

1.m设置为线路数，每根线路与索引i∈[m]相关联。

​ 针对每一个i∈[n]，

2.设定ai，bi，ci为第i个门的左、右、输出线路。

3.设定(qL)i=0，(qR)i=0，(qM)i=1，(qO)i=-1，当第i个门是乘法门。

4.设定(qL)i=1，(qR)i=1，(qM)i=0，(qO)i=-1，当第i个门是加法门。（同时可以使用线性组合门，(qL)i，(qR)i为非零整数值）

5.(qC)i=0。

布尔约束：证明系统中常见的一种情况是需要强制执行 Xj∈{0,1}，其中j∈[m]，i∈[n]，则：

​ ai=bi=j，(qL)i=-1，(qM)i=1，(qR)i=(qO)i=(qC)i=0

增强公共输入：非常方便直接，强制执行公共输入值X1,…,Xl：强制约束Xj=Xj，i∈[n]，则：

​ ai=j，(qL)i=1，(qM)i=(qR)i=(qO)i=0，(qC)i=-xj

7 主协议Main protocol

​ 令C=(V,Q)为第6节所述形式的约束系统。我们介绍关系Rc的主要协议。首先，如下定义C的分区（称为Tc）将很方便。

​ 令 V=(a,b,c)，认为V是[m]中的一个向量V，[m]的阶数为3n。令i∈[m]，Ti⊂[3n]为是索引集j∈[3n]，如Vj=i。现在定义：
$$
T_c := {T_i}_{i∈[m]}
$$
​ 在介绍本协议之前，我们先做一个最终定义。如果i∈[l]，我们说C为l个公共输入做好了准备。

​ ai=i，(qL)i=1，(qM)i=(qR)i=(qO)i=0，(qC)i=0

​ 回顾 H∈{g,. . .,gn}，我们提出用于Rc的H范围多项式协议

前处理：令 σ = σ(Tc)

​ 如5.1节所讲，多项式SID1，SID2，SID3，Sσ1，Sσ2，Sσ3∈ F <n[X]。

​ 多项式qL，qR，qO，qM，qC ∈ F <n[X]，针对每一个i∈[n]均满足：
$$
q_L(g^i):=(q_L)_i,q_R(g^i):=(q_R)_i,q_O(g^i):=(q_O)_i,q_M(g^i):=(q_M)_i,q_C(g^i):=(q_C)_i
$$
协议：

1.X∈ F，*F*的阶数为m，令X为Ppoly的公共输入X。P**poly计算3个多项式fL，fR，fO∈ *F*** <n[X]，i∈[n]，
$$
f_L(i)=X_{a_i},f_R(i)=X_{b_i},f_O(i)=X_{c_i}
$$
Ppoly发送fL，fR，fO给到第三方 I。

2.Ppoly和Vpoly使用5.1节所讲到的排列协议，使用排列σ，σ介于(fL, fR, fO)与自身之间。如5.2阶所讲，将确切地检查(fL, fR, fO)是否满足Tc。

3.Vpoly计算公共输入多项式：
$$
PI(X):= \sum _{i∈[l]}-x_i \cdot L_i(X)
$$
4.Vpoly在H范围内检验恒等式：
$$
q_L \cdot f_L + q_R \cdot f_R + q_O \cdot f_O + q_M \cdot f_L \cdot f_R + (q_C + PI) = 0
$$

8.最终协议

8.1 多项式定义一个专用电路

以下多项式，唯一性地定义一个通用的SNARK电路：

  • qM(X)，qL(X)，qR(X)，qO(X)，qC(X)，定义电路算术化的“选择器”多项式

  • SID1(X)=X，SID2(X)=k1X，SID3(X)=k2X：应用于a, b, c的恒等式排列。选择k1，k2∈*F*** ，使得H，k1·H，k2·H是*F****中H的不同的协集，因此由3n个不同的元素组成。例如，ω是二次残基的，k1为任何二次非残基，而k2为不包含在k1·H中的二次非残基。

  • Sσ1(X)，Sσ2(X)，Sσ3(X)：复制排列应用于a，b，c

  • n为给定电路总的门数。V使用它来计算消失的多项式：
    $$
    Z_H(X)=X^n-1
    $$

8.2 对线路价值的承诺Commitments to wire values

对于以下协议，我们描述了包含n个算术门的通用SNARK电路的证明关系。证据proof的见证人witnesses是线路价值的见证。承诺commitments [a]1，[b]1，[c]1将Kate多项式承诺通过计算方式绑定到线路价值。

8.3 展开的通用的SNARK证明关系

$$
Rsnark(λ)=\begin{Bmatrix} (x,w,crs) = ((w_i){i \in [l]}),((w_i) ^{3n} _{i=1,i \in [l]}),((q{M_i},q_{L_i},q_{R_i},q_{O_i},q_{C_i}) ^n _{i=1}, n, σ(x))\
\text {For all } i \in {1,…,3n }:w_i \in F_p,

\ \text {and for all } i \in {1,…,n}:w_iw_{n+i}q_{M_i} + w_iq_{L_i} + w_{n+i}q_{R_i} + w_{2n+i}q_{O_i} + q_{C_i} = 0
\ \text { and for all } i \in {1,…,3n}:w_i=w_{σ(i)}
\end{Bmatrix}
$$

8.4 协议

​ 我们将下面的协议描述为使用Fiat-Shamir启发式技术的非交互式协议。为此，我们总是通过笔录表示共同的预处理输入，公共输入以及证明者在特定时间点之前编写的证明元素的串联。使用transcript通过(Fiat-Shamir)获得随机挑战。或者，可以通过发送随机字段元素的验证程序替换我们在“compute challenges”下写下的所有要点，以获得交互式协议，从中可以得出非交互式协议。使用R来指代哈希函数R:{0,1}→**F**p来模拟随机预言。

共同的预处理输入：
$$
\begin{matrix}
n,(x \cdot [1]1,…,x^{n+5} \cdot [1]1),(q{M_i},q_{L_i},q_{R_i},q_{O_i},q_{C_i}) ^n _{i=1} , σ(X), \
q_M(X)=\sum ^n _{i=1} q{M_i}L_i(X),\
q_L(X)=\sum ^n {i=1} q{L_i}L_i(X),\
q_R(X)=\sum ^n {i=1} q{R_i}L_i(X),\
q_O(X)=\sum ^n {i=1} q{O_i}L_i(X),\
q_C(X)=\sum ^n {i=1} q{C_i}L_i(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),\
\end{matrix}
$$
公共输入：
$$
l,(w_i){i \in [l]}
$$

证明人算法：

证明人输入：
$$
(w_i)_{i \in [3n]}
$$
Round 1:

​ 生成随机的盲标量(b1,…,b9)∈ Fp

​ 计算线路多项式 a(X)，b(X)，c(X):
$$
\begin{matrix}
a(X)=(b_1X+b_2)Z_H(X)+\sum {i=1} ^n w_iL_i(X) \
b(X)=(b_3X+b_4)Z_H(X)+\sum _{i=1} ^n w{n+i}L_i(X) \
c(X)=(b_5X+b_6)Z_H(X)+\sum {i=1} ^n w{2n+i}L_i(X) \
\end{matrix}
$$
​ 计算
$$
[a]_1 := [ \alpha (x)]_1,[b]_1 := [b(x)]_1,[c]_1 := [c(x)]_1
$$
​ 第一个输出 P 为：
$$
[a]_1 ,[b]_1 ,[c]_1
$$
Round 2:

​ 计算排列挑战(β, γ)∈ Fp: β = R(transcript,0), γ = R(transcript,1)

​ 计算排列多项式 z(X):
$$
\begin{matrix}
z(X)=
(b_7X^2+b_8X+b_9)Z_H(X)+ \
L_1(X)+ \
\sum {i=1} ^{n-1}\left(L{i+1}(X) \prod ^i {j=1} \frac{(w_j+\beta w^{j-1}+\gamma)(w_{n+j}+\beta k_1w^{j-1}+\gamma)(w_{2n+j}+\beta k_2w^{j-1}+\gamma)}{(w_j+\sigma(j)\beta+\gamma))(w{n+j}+\sigma(n+j)\beta+\gamma)(w_{2n+j}+\sigma(2n+j)\beta+\gamma)}\right)
\end{matrix}
$$
​ 计算:
$$
[z]_1:=[z(x)]_1
$$
​ 第二个输出 P 为：
$$
([z]_1)
$$
Round 3:

​ 计算商数挑战α∈ Fp：α = R(transcript)

​ 计算商数二项式t(X)：
$$
\begin{matrix}
t(X)=(a(X)b(X)q_M(X)+a(X)q_L(X)+b(X)q_R(X)+c(X)q_O(X)+PI(X)+q_C(X)) \frac{1}{Z_H(X)} \+ ((a(X)+\beta X+\gamma)(b(X)+\beta k_1X+\gamma)(c(X)+\beta k_2X+\gamma)z(X)) \frac{\alpha}{Z_H(X)}
\- ((a(X)+\beta S_{\sigma 1} (X)+\gamma)(b(X)+\beta S_{\sigma 2} (X)+\gamma)(c(X)+\beta S_{\sigma 3} (X)+\gamma)z(X\omega))\frac{\alpha}{Z_H(X)}
\+ ((z(X)-1)L_1(X)\frac{\alpha ^2}{Z_H(X)}
\end{matrix}
$$
​ 拆分 t(X) 为多项式 tlo(X)，tmid(X)和thi(X)， tlo(X)阶数<n，thi(X)阶数≤n+5，即
$$
t(X)=t_{lo}(X)+X^nt_{mind}(X)+X^{2n}t_{hi}(X)
$$
​ 计算
$$
[t_{lo}]1:=[t{lo}(x)]1, [t{mid}]_1:=[tmid(x)]1, [t{hi}]1:=[t{hi}(x)]1
$$
​ 第三个输出 P 为：
$$
([t{lo}]1,[t{mid}]1,[t{hi}]_1)
$$
Round 4:

​ 计算评估挑战ζ∈ Fp：ζ= R(transcript)

​ 计算开放评估：
$$
\overline a=a(ζ),\overline b=b(ζ), \overline c=c(ζ),\overline S_{\sigma 1}=S_{\sigma 1}(ζ), \overline S_{\sigma 2}=S_{\sigma 2}(ζ), \overline t=t(ζ), \overline z=z(ζω)
$$
​ 计算线性化多项式 r(X)：
$$
\begin{matrix}
r(X)=(\overline a \overline b \cdot q_M(X)+\overline a \cdot q_L(X)+\overline b \cdot q_R(X)+ \overline c \cdot q_O(X)+q_C(X)) \

  • ((\overline a+\beta ζ+\gamma)(\overline b+\beta k_1ζ+\gamma)(\overline c+\beta k_2ζ+\gamma)\cdot z(X))\alpha
    \- ((\overline a+\beta \overline S_{\sigma 1}+\gamma)(\overline b+\beta S_{\sigma 2}+\gamma)\beta \overline z_ω \cdot S_{\sigma 3}(X)) \alpha
    \+ ((z(X))L_1(ζ){\alpha ^2}
    \end{matrix}
    $$
    ​ 计算线性化评估
    $$
    \overline r = r(ζ)
    $$
    ​ 第四个输出 P 为：
    $$
    (\overline a, \overline b, \overline c, \overline S_{\sigma 1},\overline S_{\sigma 2},\overline z_ω,\overline t,\overline r)
    $$

Round 5:

​ 计算开放挑战 υ∈ Fp：υ= R(transcript)

​ 计算开放证明多项式 Wζ(X)：
$$
W_ζ(X)=\frac{1}{X-ζ}\left(
\begin{matrix}
(t_{lo}(X)+ζ^nt_{mid}(X)+ζ^{2n}t_{hi}(X)-\overline t)\
+υ(r(X)-\overline r)\
+υ^2(a(X)-\overline a)\
+υ^3(b(X)-\overline b)\
+υ^4(c(X)-\overline c)\
+υ^5(S_{\sigma 1}(X)-\overline S_{\sigma 1})\
+υ^6(S_{\sigma 2}(X)-\overline S_{\sigma 2})\

\end{matrix}
\right)
$$
​ 计算开放证明多项式：
$$
W_{ζω}(X)=\frac{(z(X)-\overline z_ω)}{X-ζω}
$$
​ 计算：
$$
[W_ζ]1:=[W_ζ(x)]_1,[W_ζω]_1:=[W_ζω(x)]_1
$$
​ 第五个输出P为
$$
([W_ζ]_1,[W_ζω]_1)
$$
​ 返回
$$
π{SNARK}=\left(
[a]1,[b]1,[c]_1,[z]_1,[t{lo}]1,[t{mid}]1,[t{hi}]1,[W_ζ]_1,[W_ζω]_1,\overline a, \overline b, \overline c, \overline S{\sigma 1},\overline S{\sigma 2},\overline r, \overline z_ω
\right)
$$
​ 计算多点评估挑战 u∈ Fp：u = R(transcript)

​ 现在，我们以最小化G1标量乘法次数的方式描述验证程序算法。

验证人算法：

验证预处理输入：
$$
\begin{matrix}
[q_M]1:=q_M(x)\cdot [1]_1\,
[q_L]_1:=q_L(x)\cdot [1]_1\
,[q_R]_1:=q_R(x)\cdot [1]_1\
,[q_O]_1:=q_O(x)\cdot [1]_1\
,[S{\sigma 1}]1:=S{\sigma 1}(x)\cdot [1]1\
,[S{\sigma 2}]1:=S{\sigma 2}(x)\cdot [1]1\
,[S{\sigma 3}]1:=S{\sigma 3}(x)\cdot [1]_1\
x \cdot [1]_2
\end{matrix}
$$

$$
\begin{matrix}
1.验证 \left(
[a]1,[b]1,[c]_1,[z]_1,[t{lo}]1,[t{mid}]1,[t{hi}]_1,[W_ζ]_1,[W_ζω]_1
\right) \in G_1 \
2.验证\left(
\overline a, \overline b, \overline c, \overline S{\sigma 1},\overline S_{\sigma 2},\overline r, \overline z_ω
\right) \in F ^7 p \
3.验证 (w_i)_{i \in [l]} \in F ^l _p \
4.计算 \beta,\gamma,\alpha,ζ,v, u \in F_p 如证明人算法描述 \
5.计算零多项式评估 Z_H(ζ)=ζ^n-1 \
6.计算拉格朗日多项式评估 L_1(ζ)=\frac{ζ^n-1}{n(ζ-1)} \
7.计算公共多项式评估 PI(ζ)=\sum{i\in l} w_iL_i(ζ) \
8.计算求商多项式评估 \overline t = \frac{\overline r + PI(ζ) - ((\overline a+\beta \overline S_{\sigma 1}+\gamma)(\overline b+\beta \overline S_{\sigma 2}+\gamma)(\overline c+\gamma) \overline z_ω)\alpha - L_1(ζ)\alpha ^2)}{Z_H(ζ)}
\end{matrix}
$$

9.计算第一部分的批多项式承诺
10.计算整体批多项式承诺
11.计算群编码批评估
12.验证全部评估