理解 Plonk（五）：多项式承诺

什么是多项式承诺

所谓承诺，是对消息「锁定」，得到一个锁定值。这个值被称为对象的「承诺」。

$c = co mmi t (x)$

这个值和原对象存在两个关系，即 Hiding 与 Binding。

Hiding： $c$ 不暴露任何关于 $x$ 的信息；

Binding：难以找到一个 $x^{'}, x^{'} \neq = x$ ，使得 $c = co mmi t (x^{'})$ 。

最简单的承诺操作就是 Hash 运算。请注意这里的 Hash 运算需要具备密码学安全强度，比如 SHA256, Keccak 等。除了 Hash 算法之外，还有 Pedersen 承诺等。

顾名思义，多项式承诺可以理解为「多项式」的「承诺」。如果我们把一个多项式表达成如下的公式，

$f (X) = a_{0} + a_{1} X + a_{2} X^{2} + \dots + a_{n} X^{n}$

那么我们可以用所有系数构成的向量来唯一标识多项式 $f (X)$ 。

$(a_{0}, a_{1}, a_{2}, \dots, a_{n})$

如何对一个多项式进行承诺？很容易能想到，我们可以把「系数向量」进行 Hash 运算，得到一个数值，就能建立与这个多项式之间唯一的绑定关系。

$C_{1} = SHA256 (a_{0} ∥ a_{1} ∥ a_{2} ∥ \dots ∥ a_{n})$

或者，我们也可以使用 Petersen 承诺，通过一组随机选择的基，来计算一个 ECC 点：

$C_{2} = a_{0} G_{0} + a_{1} G_{1} + \dots + a_{n} G_{n}$

如果在 Prover 承诺多项式之后，Verifier 可以根据这个承诺，对被锁定的多项式进行求值，并希望 Prover 可以证明求值的正确性。假设 $C = C o mmi t (f (X))$ ，Verifier 可以向提供承诺的 Prover 询问多项式在 $X = ζ$ 处的取值。Prover 除了回复一个计算结果之外（如 $f (ζ) = y$ ），还能提供一个证明 $π$ ，证明 $C$ 所对应的多项式 $f (X)$ 在 $X = ζ$ 处的取值 $y$ 的正确性。

多项式承诺的这个「携带证明的求值」特性非常有用，它可以被看成是一种轻量级的「可验证计算」。即 Verifier 需要把多项式 $f (X)$ 的运算代理给一个远程的机器（Prover），然后验证计算（计算量要小于直接计算 $f (X)$ ）结果 $y$ 的正确性；多项式承诺还能用来证明秘密数据（来自Prover）的性质，比如满足某个多项式，Prover 可以在不泄漏隐私的情况下向 Verifier 证明这个性质。

虽然这种可验证计算只是局限在多项式运算上，而非通用计算。但通用计算可以通过各种方式转换成多项式计算，从而依托多项式承诺来最终实现通用的可验证计算。

按上面 $C_{2}$ 的方式对多项式的系数进行 Pedersen 承诺，我们仍然可以利用 Bulletproof-IPA 协议来实现求值证明，进而实现另一种多项式承诺方案。此外，还有 KZG10 方案，FRI，Dark，Dory 等等其它方案。

KZG10 构造

与 Pedersen 承诺中用的随机基向量相比，KZG10 多项式承诺需要用一组具有内部代数结构的基向量来代替。

$(G_{0}, G_{1}, G_{2}, \dots, G_{d - 1}, H_{0}, H_{1}) = (G, χ G, χ^{2} G, \dots, χ^{d - 1} G, H, χH)$

请注意，这里的 $χ$ 是一个可信第三方提供的随机数，也被称为 Trapdoor，需要在第三方完成 Setup 后被彻底删除。它既不能让 Verifier 知道，也不能让 Prover 知道。当 $G$ 设置好之后， $χ$ 被埋入了基向量中。这样一来，从外部看，这组基向量与随机基向量难以被区分。其中 $G \in G_{1}$ ，而 $H \in G_{2}$ ，并且存在双线性映射 $e \in G_{1} \times G_{2} \to G_{T}$ 。

对于一个多项式 $f (X)$ 进行 KZG10 承诺，也是对其系数向量进行承诺：

$C_{f (X)} = a_{0} G_{0} + a_{1} G_{1} + \dots + a_{n - 1} G_{n - 1} = a_{0} G + a_{1} χ G + \dots + a_{n - 1} χ^{n - 1} G = f (χ) G$

这样承诺 $C_{f (X)}$ 巧好等于 $f (χ) G$ 。

对于双线性群，我们下面使用 Groth 发明的符号 $[1]_{1} ≜ G$ ， $[1]_{2} ≜ H$ 表示两个群上的生成元，这样 KZG10 的系统参数（也被称为 SRS, Structured Reference String）可以表示如下：

$srs = ([1]_{1}, [χ]_{1}, [χ^{2}]_{1}, [χ^{3}]_{1}, \dots, [χ^{n - 1}]_{1}, [1]_{2}, [χ]_{2})$

而 $C_{f (X)} = [f (χ)]_{1}$ 。

下面构造一个 $f (ζ) = y$ 的 Open 证明。根据多项式余数定理，我们可以得到下面的等式：

$f (X) = q (X) \cdot (X - ζ) + y$

这个等式可以解释为，任何一个多项式都可以除以另一个多项式，得到一个商多项式加上一个余数多项式。由于多项式在 $X = ζ$ 处的取值为 $y$ ，那么我们可以确定：余数多项式一定为 $y$ ，因为等式右边的第一项在 $X = ζ$ 处取值为零。所以，如果 $f (ζ) = y$ ，我们可以断定： $g (X) = f (X) - y$ 在 $X = ζ$ 处等零，所以 $ζ$ 为 $g (X)$ 的根，于是 $g (X)$ 一定可以被 $(X - ζ)$ 这个不可约多项式整除，即一定存在一个商多项式 $q (X)$ ，满足上述等式。

而 Prover 则可以提供 $q (X)$ 多项式的承诺，记为 $C_{q}$ ，作为 $f (ζ) = y$ 的证明，Verifier 可以检查 $[q (χ)]$ 是否满足整除性来验证证明。因为如果 $f (ζ) \neq = y$ ，那么 $g (X)$ 则无法被 $(X - ζ)$ 整除，即使 Prover 提供的承诺将无法通过整除性检查：

$(f (X) - y) \cdot 1 = ? q (X) \cdot (X - ζ)$

承诺 $C_{f (X)}$ 是群 $G_{1}$ 上的一个元素，通过承诺的加法同态映射关系，以及双线性映射关系 $e \in G_{1} \times G_{2} \to G_{T}$ ，Verifier 可以在 $G_{T}$ 上验证整除性关系：

$e (C_{f (X)} - y [1]_{1}, [1]_{2}) = ? e (C_{q (X)}, [χ]_{2} - ζ [1]_{2})$

有时为了减少 Verifier 在 $G_{2}$ 上的昂贵操作，上面的验证等式可以变形为：

$f (X) + ζ \cdot q (X) - y = q (X) \cdot X$

$e (C_{f (X)} + ζ \cdot C_{q (X)} - y \cdot [1]_{1}, [1]_{2}) = ? e (C_{q (X)}, [χ]_{2})$

同点 Open 的证明聚合

在一个更大的安全协议中，假如同时使用多个多项式承诺，那么他们的 Open 操作可以合并在一起完成。即把多个多项式先合并成一个更大的多项式，然后仅通过 Open 一点，来完成对原始多项式的批量验证。

假设我们有多个多项式， $f_{1} (X)$ ， $f_{2} (X)$ ，Prover 要同时向 Verifier 证明 $f_{1} (ζ) = y_{1}$ 和 $f_{2} (ζ) = y_{2}$ ，那么有

$f_{1} (X) = q_{1} (X) \cdot (X - ζ) + y_{1} f_{2} (X) = q_{2} (X) \cdot (X - ζ) + y_{2}$

通过一个随机数 $ν$ ，Prover 可以把两个多项式 $f_{1} (X)$ 与 $f_{2} (X)$ 折叠在一起，得到一个临时的多项式 $g (X)$ ：

$g (X) = f_{1} (X) + ν \cdot f_{2} (X)$

进而我们可以根据多项式余数定理，推导验证下面的等式：

$g (X) - (y_{1} + ν \cdot y_{2}) = (X - ζ) \cdot (q_{1} (X) + ν \cdot q_{2} (X))$

我们把等号右边的第二项看作为「商多项式」，记为 $q (X)$ ：

$q (X) = q_{1} (X) + ν \cdot q_{2} (X)$

假如 $f_{1} (X)$ 在 $X = ζ$ 处的求值证明为 $π_{1}$ ，而 $f_{2} (X)$ 在 $X = ζ$ 处的求值证明为 $π_{2}$ ，那么根据群加法的同态性，Prover 可以得到商多项式 $q (X)$ 的承诺：

$[q (χ)]_{1} = π = π_{1} + ν \cdot π_{2}$

因此，只要 Verifier 发给 Prover 一个额外的随机数 $ν$ ，双方就可以把两个（甚至多个）多项式承诺折叠成一个多项式承诺 $C_{g}$ ：

$C_{g} = C_{1} + ν * C_{2}$

并用这个折叠后的 $C_{g}$ 来验证多个多项式在一个点处的运算取值：

$y_{g} = y_{1} + ν \cdot y_{2}$

从而把多个求值证明相应地折叠成一个，Verifier 可以一次验证完毕：

$e (C - y * G_{0}, H_{0}) = ? e (π, H_{1} - x * H_{0})$

由于引入了随机数 $ν$ ，因此多项式的合并不会影响承诺的绑定关系（Schwartz-Zippel 定理）。

协议：

公共输入： $C_{f_{1}} = [f_{1} (χ)]_{1}$ ， $C_{f_{2}} = [f_{2} (χ)]_{1}$ ， $ζ$ ， $y_{1}$ ， $y_{2}$

私有输入： $f_{1} (X)$ ， $f_{2} (X)$

证明目标： $f_{1} (ζ) = y_{1}$ ， $f_{2} (ζ) = y_{2}$

第一轮：Verifier 提出挑战数 $ν$

第二轮：Prover 计算 $q (X) = f_{1} (X) + ν \cdot f_{2} (X)$ ，并发送 $π = [q (χ)]_{1}$

第三轮：Verifier 计算 $C_{g} = C_{f_{1}} + ν \cdot C_{f_{2}}$ ， $y_{g} = y_{1} + ν \cdot y_{2}$

$e (C_{g} - [y_{g}]_{1}, [1]_{2}) = ? e (π, [χ - ζ]_{2})$

多项式约束与线性化

假设 $[f (χ)]_{1}, [g (χ)]_{1}, [h (χ)]_{1}$ 分别是 $f (X), g (X), h (X)$ 的 KZG10 承诺，如果 Verifier 要验证下面的多项式约束：

$f (X) + g (X) = ? h (X)$

那么 Verifier 只需要把前两者的承诺相加，然后判断是否等于 $[h (χ)]_{1}$ 即可

$[f (χ)]_{1} + [g (χ)]_{1} = ? [h (χ)]_{1}$

如果 Verifier 需要验证的多项式关系涉及到乘法，比如：

$f (X) \cdot g (X) = ? h (X)$

最直接的方法是利用双线性群的特性，在 $G_{T}$ 上检查乘法关系，即验证下面的等式：

$e ([f (χ)]_{1}, [g (χ)]_{2}) = ? e ([h (χ)]_{1}, [1]_{2})$

但是如果 Verifier 只有 $g (X)$ 在 $G_{1}$ 上的承诺 $[g (χ)]_{1}$ ，而非是在 $G_{2}$ 上的承诺 $[g (χ)]_{2}$ ，那么Verifer 就无法利用双线性配对操作来完成乘法检验。

另一个直接的方案是把三个多项式在同一个挑战点 $X = ζ$ 上打开，然后验证打开值之间的关系是否满足乘法约束：

$f (ζ) \cdot g (ζ) = ? h (ζ)$

同时 Prover 还要提供三个多项式求值的证明 $(π_{f (ζ)}, π_{g (ζ)}, π_{h (ζ)})$ 供 Verifier 验证。

这个方案的优势在于多项式的约束关系可以更加复杂和灵活，比如验证下面的稍微复杂些的多项式约束：

$f_{1} (X) f_{2} (X) + h_{1} (X) h_{2} (X) h_{3} (X) + g (X) = 0$

假设 Verifier 已拥有这些多项式的 KZG10 承诺， $[f_{1} (χ)]_{1}$ ， $[f_{2} (χ)]_{1}$ ， $[h_{1} (χ)]_{1}$ ， $[h_{2} (χ)]_{1}$ ， $[h_{3} (χ)]_{1}$ ， $[g (χ)]_{1}$ 。最直接粗暴的方案是让 Prover 在挑战点 $X = ζ$ 处打开这 6 个承诺，发送 6 个 Open 值和对应的求值证明：

$(f_{1} (ζ), π_{f_{1}}), (f_{2} (ζ), π_{f_{2}}), (h_{1} (ζ), π_{h_{1}}), (h_{2} (ζ), π_{h_{2}}), (h_{3} (ζ), π_{h_{3}}), (g (ζ), π_{g})$

Verifier 验证 $6$ 个求值证明，并且验证多项式约束：

$f_{1} (ζ) f_{2} (ζ) + h_{1} (ζ) h_{2} (ζ) h_{3} (ζ) + g (ζ) = ? 0$

我们可以进一步优化，比如考虑对于 $f (X) \cdot g (X) = h (X)$ 这样一个简单的多项式约束，Prover 可以减少 Open 的数量。比如 Prover 先 Open $\overset{ˉ}{f} = f (ζ)$ ，发送求值证明 $π_{f (ζ)}$ 然后引入一个辅助多项式 $L (X) = \overset{ˉ}{f} \cdot g (X) - h (X)$ ，再 Open $L (X)$ 在 $X = ζ$ 处的取值。

显然对于一个诚实的 Prover， $L (ζ)$ 求值应该等于零。对于 Verifier，它在收到 $\overset{ˉ}{f}$ 之后，就可以利用承诺的加法同态性，直接构造 $L (X)$ 的承诺：

$[L (χ)]_{1} = \overset{ˉ}{f} \cdot [g (χ)]_{1} - [h (χ)]_{1}$

这样一来，Verifier 就不需要单独让 Prover 发送 $L (X)$ 的 Opening，也不需要发送新多项式 $L (X)$ 的承诺。Verifier 然后就可以验证 $f (X) \cdot g (X) = h (X)$ 这个多项式约束关系：

$e ([L (χ)]_{1}, [1]_{2}) = ? e (π_{L (ζ)}, [χ - ζ]_{2})$

这个优化过后的方案，Prover 只需要 Open 两次。第一个 Opening 为 $\overset{ˉ}{f}$ ，第二个 Opening 为 $0$ 。而后者是个常数，不需要发送给 Verifier。Prover 只需要发送两个求值证明，不过我们仍然可以用上一节提供的聚合证明的方法，通过一个挑战数 $ν$ ，Prover 可以聚合两个多项式承诺，然后仅需要发送一个求值证明。

我们下面尝试优化下 $6$ 个多项式的约束关系的协议： $f_{1} (X) f_{2} (X) + h_{1} (X) h_{2} (X) h_{3} (X) + g (X) = 0$ 。

协议：

公共输入： $C_{f_{1}} = [f_{1} (χ)]_{1}$ ， $C_{f_{2}} = [f_{2} (χ)]_{1}$ ， $C_{h_{1}} = [h_{1} (χ)]_{1}$ ， $C_{h_{2}} = [h_{2} (χ)]_{1}$ ， $C_{h_{3}} = [h_{3} (χ)]_{1}$ ， $C_{g} = [g (χ)]_{1}$ ，

私有输入： $f_{1} (X)$ ， $f_{2} (X)$ ， $h_{1} (X)$ ， $h_{2} (X)$ ， $h_{3} (X)$ ， $g (X)$

证明目标： $f_{1} (X) f_{2} (X) + h_{1} (X) h_{2} (X) h_{3} (X) + g (X) = 0$

第一轮：Verifier 发送 $X = ζ$

第二轮：Prover 计算并发送三个Opening， $\overset{ˉ}{f_{1}} = f_{1} (ζ)$ ， $\overset{ˉ}{h}_{1} = h_{1} (ζ)$ ， $\overset{ˉ}{h}_{2} = h_{2} (ζ)$ ，

第三轮：Verifier 发送 $ν$ 随机数

第四轮：Prover 计算 $L (X)$ ，利用 $ν$ 折叠 $(L (X), f_{1} (X), h_{1} (X), h_{2} (X))$ 这四个承诺，并计算商多项式 $q (X)$ ，发送其承诺 $[q (χ)]_{1}$ 作为折叠后的多项式在 $X = ζ$ 处的求值证明

$L (X) = \overset{ˉ}{f}_{1} \cdot f_{2} (X) + \overset{ˉ}{h}_{1} \overset{ˉ}{h}_{2} \cdot h_{3} (X) + g (X)$

$q (X) = \frac{1}{X - ζ} (L (X) + ν \cdot (f_{1} (X) - \overset{ˉ}{f}_{1}) + ν^{2} \cdot (h_{1} (X) - \overset{ˉ}{h}_{1}) + ν^{3} \cdot (h_{2} (X) - \overset{ˉ}{h}_{2}))$

第五轮：Verifier 计算辅助多项式 $L (X)$ 的承诺 $[L]_{1}$ ：

$[L]_{1} = \overset{ˉ}{f}_{1} \cdot [f_{2} (χ)]_{1} + \overset{ˉ}{h}_{1} \overset{ˉ}{h}_{2} \cdot [h_{3} (χ)]_{1} + [g (χ)]_{1}$

计算折叠后的多项式的承诺：

$[F]_{1} = [L]_{1} + ν \cdot [f_{1} (χ)]_{1} + ν^{2} [h_{1} (χ)]_{1} + ν^{3} [h_{2} (χ)]_{1}$

计算折叠后的多项式在 $X = ζ$ 处的求值：

$E = ν \cdot \overset{ˉ}{f}_{1} + ν^{2} \cdot \overset{ˉ}{h}_{1} + ν^{3} \cdot \overset{ˉ}{h}_{2}$

检查下面的验证等式：

$e ([F]_{1} - [E]_{1} + ζ [q (χ)]_{1}, [1]_{2}) = ? e ([q (χ)]_{1}, [χ]_{2})$

这个优化后的协议，Prover 仅需要发送三个 Opening，一个求值证明；相比原始方案的 6 个 Opening和 6 个求值证明，大大减小了通信量（即证明大小）。

World of Z2O-K7E