密码学 - SUMCHECK速览

SUMCHECK协议

我不会在这里深入探讨它的介绍，但是SUMCHECK协议（Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. “Algebraic Methods for Interactive Proof Systems”, 1992）是许多“可验证计算”原语的基础。如果你正在阅读本文，你可能已经知道它的重要性。

设$\mathbb{F}$是一个有限域，$f(X_1,X_2,\dots,X_n)$是$\mathbb{F}$上的一个$d$次多元多项式。 考虑和$S$定义为：

$S = \sum_{x1 \in {0,1}} \sum{x2 \in {0,1}} \cdots \sum{x_n \in {0,1}} f(x_1,x_2,\dots,xn) = \sum{(x_1,x_2,\dots,x_n) \in {0,1}^n} f(x_1,x_2,\dots,x_n)$

SUMCHECK协议提供了一个$n$轮交互协议来验证$S$的正确性，只需对$f$进行一次求值（即，验证者只需要对$f(X)$进行一次求值，而不是$2^n$次）。

该协议经过$n$轮推进。在每一轮中，证明者向验证者发送一个单变量多项式。作为响应，验证者进行检查并通过发送单个域元素挑战来响应。

第1轮

证明者计算并共享单变量多项式：

$f1(X) = \sum{(x_2,\dots,x_n) \in {0,1}^{n-1}} f(X,x_2,x_3,\dots,x_n)$

验证者确保$f_1$的次数小于$d$，检查$f_1(0) + f_1(1) = S$是否成立，并发出挑战$r_1 \in \mathbb{F}$。

第2轮

证明者计算并共享单变量多项式：

$f2(X) = \sum{(x_3,\dots,x_n) \in {0,1}^{n-2}} f(r_1,X,x_3,x_4,\dots,x_n)$

验证者确保$f_2$的次数小于$d$，检查$f_2(0) + f_2(1) = f_1(r_1)$是否成立，并发出挑战$r_2 \in \mathbb{F}$。

第$i$轮

证明者计算并共享单变量多项式：

$fi(X) = \sum{(x_{i+1},\dots,x_n) \in {0,1}^{n-i}} f(r1,\dots,r{i-1},X,x{i+1},x{i+2},\dots,x_n)$

验证者确保$f_i$的次数小于$d$，检查$f_i(0) + fi(1) = f{i-1}(r_{i-1})$是否成立，并发出挑战$r_i \in \mathbb{F}$。

第$n$轮

证明者计算并共享单变量多项式：

$f_n(X) = f(r1,\dots,r{n-1},X)$

验证者确保$f_n$的次数小于$d$，检查$f_n(0) + fn(1) = f{n-1}(r_{n-1})$是否成立，并发出挑战$r_n \in \mathbb{F}$。

最终检查

验证者计算$f(r_1,\dots,r_n)$并确认它等于$f_n(r_n)$。

为什么它有效

下面，我假设一个大域$\mathbb{F}$，对SUMCHECK协议的有效性给出一个直观的证明。 对于这个解释，Schwartz-Zippel引理是必不可少的。

Schwartz-Zippel 引理

Schwartz-Zippel引理指出：对于域$\mathbb{F}$上总次数最多为$d$的非零多元多项式$P(X_1,\dots,X_n)$，当在$\mathbb{F}$中随机点$r_1,\dots,r_n$处计算$P$时，$P(r_1,\dots,r_n)$为零的可能性小于$\frac{d}{|\mathbb{F}|}$。

在大域中（例如椭圆曲线的标量域，通常具有大约$2^{256}$的域大小，具有密码学安全性），这种概率非常小。 这是因为一个多项式只能有有限数量的零点。 对于单变量多项式，这可以从“因子定理”中立即看出：多项式的每个零点对应于一个线性因子，因此$d$次多项式最多可以有$d$个零点。

Schwartz-Zippel引理的一个常见应用是比较两个单变量多项式$f(X)$和$g(X)$，以确定它们的恒等式。 通过生成一个随机数$r \in \mathbb{F}$并检查$f(r) = g(r)$是否成立，我们可以确定它们是否相同。 这种方法是正确的，但它也是可靠的吗？ 当$f(X)$和$g(X)$不相同时，错误地声称它们是相同的可能性有多大？

声明：如果$f(X) \neq g(X)$，则检查成功的概率最多为$\frac{d}{|\mathbb{F}|}$。

证明：我们设置$P(X) = f(X) - g(X)$。 假设$f(X) \neq g(X)$，$P(X)$不是零多项式。 根据Schwartz-Zippel，$P(r) = f(r) - g(r) = 0$的概率最多为$\frac{d}{|\mathbb{F}|}$。

从Schwartz-Zippel可以得出一个 简洁的结论：在大域上，两个“低阶”多项式要么几乎处处相同，要么处处不同。

SUMCHECK协议证明

SUMCHECK协议利用此属性将具有可能大量项的和转换为单次求值。 让我们看看它为什么有效，通过尝试创建一个试图欺骗协议的证明者，试图证明一个和$\tilde{S} \neq S$。

第1轮

证明者需要发送一个多项式$\tilde{f_1}(X)$，其属性为$\tilde{f_1}(0) + \tilde{f_1}(1) = \tilde{S}$。任何其他选择都会使第一次检查立即失败，因此毫无意义。

由于$\tilde{S} \neq S$，证明者无法发送诚实的多项式$f_1(X)$。 回想一下，这意味着他们将要发送的多项式几乎处处与$f_1(X)$不同。 更准确地说，它在最多$d$个点上与$f_1$相同。

然后，验证者发送挑战$r_1$。

第2轮

在第2轮中，证明者需要发送一个多项式$\tilde{f_2}(X)$，其属性为$\tilde{f_2}(0) + \tilde{f_2}(1) = \tilde{f_1}(r_1)$。

现在有两种可能性：

• $\tilde{f_1}(r_1) = f_1(r_1)$。 在这种情况下，证明者中了大奖：他可以简单地发送$f_2(X)$（“诚实”的答案）并诚实地继续该协议直到结束。 他将成功作弊。 但是，发生这种情况的概率仅为$\frac{d}{|\mathbb{F}|}$。
• $\tilde{f_1}(r_1) \neq f_1(r_1)$（这极有可能）。 在这种情况下，证明者处于与之前相同的情况：他不能发送诚实的$f_2(X)$，而只能发送一个恶意的$\tilde{f_2}(X)$，其中$\tilde{f_2}(0) + \tilde{f_2}(1) = \tilde{f_1}(r_1)$，它最多可以在$d$个点上与诚实的答案重合。

这在每一轮中都会重复：

第$i$轮

在第$i$轮中，证明者需要发送一个多项式$\tilde{f_i}(X)$，其属性为$\tilde{f_i}(0) + \tilde{fi}(1) = \tilde{f{i-1}}(r_{i-1})$。

同样，有两种可能性：

• $\tilde{f{i-1}}(r{i-1}) = f{i-1}(r{i-1})$。 证明者获胜（发生这种情况的概率为$\frac{d}{|\mathbb{F}|}$）。
• $\tilde{f{i-1}}(r{i-1}) \neq f{i-1}(r{i-1})$。 证明者需要发送$\tilde{f_i}(X)$，其中$\tilde{f_i}(0) + \tilde{fi}(1) = \tilde{f{i-1}}(r_{i-1})$

最终检查

最后，在最后一轮中，验证者检查$f(r_1,\dots,r_n) = f_n(r_n)$是否成立。 假设证明者没有在之前的某轮中“获胜”，那么他会发送一个恶意的$\tilde{f_n}(X)$，它与诚实的$f_n(r_n)$在最多$d$个点上重合，因此，最终检查将通过的概率为$\frac{d}{|\mathbb{F}|}$。

从上面的分析可以看出，证明者在每一轮中都有很小的概率“获胜”并欺骗验证者：如果他的多项式恰好在挑战域元素上具有与诚实版本相同的求值，则证明者可以像诚实的证明者一样继续该协议，并且验证将成功。

但是，假设域$\mathbb{F}$很大，则发生这种情况的概率很小。 由于有$n$轮，因此证明者最多可以以$\frac{nd}{|\mathbb{F}|}$的概率成功。

• 原文链接： dankradfeist.de/ethereum...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～