Milestone08.SumcheckProtocol

title: Milestones 08. Sumcheck Protocol tags: zk computation theory interactive proof sumcheck protocol WTF zk 教程 里程碑 08：Sumcheck Protocol 在本讲中，我们将介绍 Sumcheck 协议（Sumcheck Protocol），一个非常经典的交互式证明系统的协议。在这个协议中，验证者通过与证明者的交互，以很小的开销验证一个非常复杂的多项式求和结果。 多项式求和问题 给定一个定义在有限域 $F$ 上的 $n$ 元多项式 $P(x1, x2, \dots, xn)$，我们想要求解： $$ S = \sum{x1, x2, ..., xn \in \{0,1\}^n} P(x1, x2, \dots, xn) $$ 即这些多项式在所有可能的 $\set{0, 1}$ 输入上求和的结果。 这个问题看起来简单，但是却包含 $2^n$ 项的求和。当 $n$ 很大的时候，计算这个求和的值是及其困难的。 举个例子，对于一个 3 元多项式： $$ P(x1, x2, x3...