我们假设验证者拥有可以计算函数 g 的预言（Oracle）。也就是说，对于验证者而言，确定某个输入 r 1, ... , rv 之后，计算 g(r 1, ... , rv) 是容易的。但是计算完整的结果 H 是困难的。 事实上，在现实应用当中，预言（Oracle）不会存在，但是可以通过某种手段实现，例如我们可以让证明者帮助验证者计算这个值，并用更多的技巧附加正确性的证明。 第二点，关于协议的目标，事实上 sum-check 协议可以对于任意的集合 B 计算 bBmg(b)，但是不失一般性的，我们假设 B={ 0, 1 }。 3. 协议过程 协议一共包含 v 轮。在每一轮当中会处理 g 中的一个变量。 第 1 轮： 如果证明者是诚实的，应当成立 H=g 1( 0)+g 1( 1)。验证者验证，若通过则选择随机数 r 1 发送给证明者。注意到，根据协议的假设，证明者可以完成上述验证。 我们用 degi(p) 来表示多元多项式 p 当中，第 i 个变量的次数。g 1(X 1) 的次数为 deg 1(g)，所以我们知道 g 1 可以用 deg 1(g)+ 1 个域元素表出。 第 j(j>1) 轮： 如果证明者是诚实的，应当成立 gj-1(rj-1)=gj( 0)+gj( 1)。验证者验证，若通过则选择随机数 rj 发送给证明者。 第 v 轮： 图 2: The Foaks Sum-check protocol Completeness: 若证明者拥有有效的 Witness，则验证者会以不低于（1-negl(n)）的概率接受证明； Soundness： 若证明者没有有效的 Witness，则验证者会以低于 negl（n）的概率拒绝证明 Succinctness: Proof 的 Size 必须远小于 Witness 的 Size； Zero-knowledge：验证者无法通过证明的交互过程获取任何关于 witness 的信息 #其中 negl（n）为任意可忽略的函数 4. 协议复杂度 通过第 3 部分的论证，我们可以看到，协议一共由 v 轮组成，每一轮当中证明者需要给验证者发送一个 degi(g) 次的多项式，也就是 deg 1(g)+ 1 个域元素，所以总体的通信复杂度是 O(i= 1 vdegi(g))。关于计算复杂度方面，在每一轮验证都通过的情况下，证明者最多需要进行 2 v 次对 g 取值的运算；验证者做的运算是对每一轮的 gj 进行取值以及在最后一轮对 g 取值。 下表具体展示了复杂度的结果，其中 T 代表访问一次预言（Oracle）也就是对 g 进行一次求值所需要的开销。 图 3:Sum-check 协议的复杂度 Sum-check Protocol 的应用 在许多的零知识证明算法当中，sum-check protocol 都在发挥着重要的作用。许多问题的证明，都依赖于将原始的问题转化为 sum-check 的形式，再完成后续的步骤。 例如，可以利用 sum-check protocol 来计算一个无向图中的三角形数量。 首先，我们使用邻接矩阵 A 表示无向图 G，设 E 为其边集合，则 Ai, j= 1(i, j)E，也就是说若点 i, j 之间存在一条边则 Ai, j= 1 否则为 0 。对于点 i, j, k，三点构成三角形的条件是 Ai, j= 1, Ai, k= 1, Aj, k= 1 。 接下来记矩阵 A 为一映射表，表示的映射为 f:{ 0, 1 }log n{ 0, 1 }log n{ 0, 1 }，其中 logn 为 i，j 的二进制长度。所以对于点 i, j, k，三点构成三角形的条件进一步可以表示为 f(i, j)f(i, k)f(j, k)= 1 。 此外，在许多证明系统当中，都采用了 sum-check protocol 作为底层逻辑进行构造。下图展示了根据在 sum-check 基础上进行不同改造得到的不同证明系统。 图 4: Sum-check protocol 在四类证明系统当中的应用 图 5: Sum-check protocol 在简洁证明方面的具体应用 结语 本文梳理了 sum-check 协议的具体流程，以及讨论了协议的复杂度，同时展示了其在许多证明系统当中的应用。 在 web3 领域不断拓展的当下，密码学作为区块链技术的底层构件，其作用显得越来越重要。随着 zkrollup、隐私保护等等依赖零知识证明的应用和项目逐渐诞生，sum-check 协议，作为诸多证明系统的重要组件，也正在被学界和产业界同时给予越来越多的关注。 参考文献 [LFKN 92 ] Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. ACM, 39: 859 – 868, October 1992. https://people.cs.georgetown.edu/jthaler/sumcheck.pdf https://zkproof.org/2020/03/16/sum-checkprotocol/ https://eprint.iacr.org/2021/333.pdf 介绍 sum-check 的中文博客 https://blog.csdn.net/mutourend/article/details/111610754 来源：金色财经lg...
北美站
