Plonk-2-零知识证明的演进
论文原文 ==> 953.pdf (iacr.org)，PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge
摘要
利用可更新的通用结构化参考字符串的zk-SNARK构造消除了部署zk-SNARKs [GKM +]的主要障碍之一。 Maller等人的重要工作，[MBKM19]提出了Sonic-第一个具有实用性的zk-SNARK，具有完全简洁的验证，可用于带有这种SRS(structured reference string)的通用算术电路。但是，支持完全简洁验证的Sonic版本仍然需要相对较高的证明建造费用。 我们提出了一种具有完全简洁验证的通用SNARK结构，并且大大减少了证明方的运行时间（根据电路结构的不同，证明者的运行时间比完全简洁验证程序模式下的[MBKM19]少7.5-20倍）。与[MBKM19]类似，我们依赖于基于Bayer和Groth [BG12]的置换参数。但是，我们专注于“评估亚组而不是单项式系数”； 这样可以简化置换参数和算术化步骤。
4.理想的低度协议
我们在证明者和验证者之间定义了一种有限类型的协议，以清晰地捕获和抽象多项式承诺方案（例如[KZG10]）。在Plonk协议中，证明者将低度的多项式发送给第三方 I。然后，验证者可以询问 I ，证明者的多项式与验证者已知的其他预定义多项式之间是否存在某些恒等式。
定义 4.1. 定值正整数 d, D, t, l . A(d, D, t, l) 多项式协议，其中，证明者Ppoly，验证者Vpoly和受信方**I**之间存在多轮协议，其进行如下。
1.协议定义包括一组预处理多项式 g1, … , gl ∈ F <d[X]。
2.Ppoly的消息被发送到 I，并且对于f∈ F <d[X]，形式为f。 如果Ppoly发送的消息不是这种形式，则协议中止。
3.Vpoly到Ppoly的消息是任意的（但是我们将集中讨论公共硬币协议，其中消息只是随机的硬币）
4.在协议末尾，假设 f1, … , ft 是从Ppoly发送到 I 的多项式。Vpoly可能会问 I 在{f1, . . . , ft , g1, . . . , gl}之间是否存在某些多项式恒等式:
$$
F(X) := G(X,h_1(v_1(X)), … , h_M(v_M(X)))≡0
$$
其中，hi ∈ {f1, . . . , ft , g1, . . . , gl}，G ∈ F [X, X1, … , Xm], v1, … , vm ∈ F <d[X]，此 F ∈ F <D[X]中，任一 f1, . . . , ft 都是Ppoly按照本协议制作的。
5.在收到 I 的回答之后，如果所有身份均成立，则Vpoly输出 acc，否则输出 rej。
结论 4.2. 一个更加复杂的模型，Ppoly发送消息(f, n) 至 I，其中 n ≤ d ，由 I 执行 f ∈ F <n[X] 。但是，我们避免这样做，因为我们的协议不需要这种额外的功能，并且会导致效率降低，因为它转化为需要使用多项式承诺方案，并且能够动态实施小于d度的边界。
我们以自然的方式为关系定义多项式协议。
定义 4.3. 给定关系R，R是具有以下属性的多项式协议。
1.协议的第一步，Ppoly和Vpoly都被给与一个输入 x。假设Ppoly拥有w，并且 (x, ω) ∈ R。
2.完整性(Completeness)：如果Ppoly正确地遵从协议，使用证明人 ω 生成 x，Vpoly将百分之百接受。
3.知识健全性(Knowledge Soundness)：存在一个有效的 E 即给定对Ppoly的消息的访问权，给到 I ，输出ω，使得对于Ppoly的任何策略，下列事件的概率为negl(λ)。
a.在协议的末尾，Vpoly输出acc，并且
b. (x, ω) ∉ R。
结论 4.4. 我们故意不为理想的协议定义零知识属性，因为获得ZK取决于最终“编译”协议中泄漏给我的多项式的信息量。这又取决于用于编译的多项式承诺方案的具体细节。
4.1范围上的多项式协议
在我们的协议中，Vpoly 实际上需要检查某些多项式方程式是否在输入值的特定范围内成立，而不是作为多项式恒等式。首次启发，对于子集 S ⊂ F ，我们定义了一个**S**范围(d, D, t, l)的多项式协议，该协议与 a(d, D, t, l) 多项式协议相同，不同之处在于：验证者询问他的恒等式是否在S的所有点上都成立，而不是完全一样。然后，我们以与定义4.3中完全相同的方式为关系定义范围多项式协议。
我们表明，将范围协议转换为多项式协议只会产生一个额外的证明者多项式。
引理4.5. 令P为R的范围S的(d, D, t, l)多项式协议。然后我们可以构造 a(max{d, |S|, D−|S|}, D, t+1, l+1)，也就是R的多项式协议P∗。
本引理，我们使用以下简单声明。
断言4.6. 定义 F1,…,Fk ∈ F <n[X]。定义 Z ∈ F <n[X]。假设部分 i ∈ [k]，Z ∉ Fi。则：
1.有一种可能性，1/|F| 之上存在a1,…,ak ∈ F ， Z 不属于 F
$$
F := \sum ^k _{j=1} a_j \cdot F_j
$$
2.假设 Z 在 F 上分解为不同的线性因子，有一种可能，k/|F|之上存在a，a∈F，Z不属于 F
$$
G:= \sum ^k _{j=1} a^ {j-1} \cdot F_j
$$
证明. Z|F 等同于 (F mod Z)=0. 另有 R:= (Fi mod Z)， R ≠ 0，则R不为零二项式：
$$
F := \sum ^k _{j=1,j≠i} a_j \cdot F_j + a_i \cdot R(mod Z)
$$
因此，每一个特定的aj，最多有一个值 ai∈*F**，该F*** mod Z = 0。第一点证明完毕。
为了证明第二，类似地写：
$$
G := \sum ^k _{j=1,j≠i} a^{j-1} \cdot F_j + a^{i-1} \cdot R(mod Z)
$$
令 x ∈ F ，使 Z(x)=0，但 R(x)≠0。则 G mod Z = 0，即 G(x)=0，推导出 a 是非零多项式的根。
$$
g(Y) := \sum ^k _{j=1,j≠i} Y^{j-1} \cdot F_j(x) + Y^{i-1} \cdot R(x)
$$
最多k个a值是这种情况。
证明. (引理4.5.) 令P为范围S的(d, D, t, l)多项式协议。构建P*，同P一致，附加条件是 Zs(X) :=∏(X-a), a∈S。P* 的执行与P 一致，直到Vpoly在S域内请求恒等式。假设验证者请求 k 个恒等式：F1(X),…,Fk(X)，Fi的总维度的最大值是D，如定义4.1.所讲。P* 处理如下：
Vpoly发送队列a1,…,ak ∈ F 给到Ppoly。
Ppoly计算二项式
$$
T:=\frac {\sum a_i \cdot F_i} {Z_S} ,i∈[k]
$$Ppoly发送 T 给到 I
Vpoly查询恒等式
$$
\sum _{i∈[k]} a_j \cdot F_i(X) ≡ T \cdot Z_S
$$
遵循断言4.6，即有一种可能性，1/|F| 基于Vpoly的选择的a1,…,ak之上，适当的 T∈F[X]等同于F1,…,Fk，消失于范围S之中。这等效于Vpoly在P的类似执行中输出acc。
4.2从多项式协议到代数协议。
AGM(algebraic group model)只考虑代数对象。一个代数对象A可以任意使用群组中的元素，但是必须根据输入组元素对其输出组元素中的任何一个提供显式分解，即A还必须输出一个解释，说明如何使用组操作从其输入中计算其输出中的任何组元素。
我们希望使用Section 3的多项式承诺方案，将一个多项式协议编译成在代数组模型中具有知识健全性的协议（在第2.2节中定义）。
具体证明略。
减少字段元素的数量 ：我们描述了Mary Maller进行的优化，以减少来自M的证明中的*F*元素的数量。我们从一个说明性示例开始。假设V*希望检查恒等式h1(X)·h2(X)-h3(X)≡0。上述编译将使P以随机x∈F*方式发送h1，h2，h3。V**将检查h1(x)h2(x)-h3(x)=0。因此，P发送了三个字段元素。
但是请注意，我们可以让P只发送c:= h1(x)，然后在开放协议中简单地验证多项式L(X):=c·h2(X)-h3(X)是否在x处为零。请注意，我们可以计算com(L)= c·com(h2)-com(h3)