一文了解零知识证明当中的Sum-check Protocol

零知识证明是一类算法的统称,到目前为止,研究者发明了包括 Plonk、Groth 16、zkStark、Virgo、Orion、Foaks 等等在内的许多种协议。不同的协议适用于不同的计算场景,复杂度和效率也各有不同,例如 Foaks 就以线性的证明时间和较小的证明长度为优势。

随着比特币、区块链、智能合约等概念的铺开,越来越多的人关注到 Web3 领域的蓬勃发展。而在技术方面,也有许多开发者关注到支撑区块链底层的密码学协议。在这之中,零知识证明协议以其独特的特性大放异彩,无论是在实现隐私保护,还是在实现 Layer 2 性能扩容的 zkrollup 项目当中,都发挥着关键的作用。

零知识证明是一类算法的统称,到目前为止,研究者发明了包括 Plonk、Groth 16、zkStark、Virgo、Orion、Foaks 等等在内的许多种协议。不同的协议适用于不同的计算场景,复杂度和效率也各有不同,例如 Foaks 就以线性的证明时间和较小的证明长度为优势。

上述的每一种协议,协议目标是相同的,就是证明者(Prover)希望在不向验证者(Verifier)透露任何关于自己的秘密的信息的情况下让验证者相信自己拥有秘密。sum-check protocol 是很多协议的组件,最早在[LFKN 92 ]当中被提出。很多计算问题可以被转化成 sum-check protocol 能处理的问题,从而生成证明。包括 Foaks 在内的不少协议的底层协议都基于 sum-check protocol,在其上进行调整来实现。

在 Fox Tech 所采用的 Foaks 证明系统当中,该协议同样发挥着重要的作用。具体来讲,为了实现对于某一操作码 opcode 正确性的证明,需要先将其转化为算术电路,之后转换为矩阵,最终生成多项式,对多项式应用证明系统当中的算法,在最后压缩证明的部分当中,同样将证明者(Prover)和验证者(Verifier)之间的交互过程转换为计算某个和式,也就是 sum-check protocol 的过程。

一文了解零知识证明当中的Sum-check Protocol
图 1: Sum-check Protocol 所在环节

Sum-check Protocol

1.协议目标

协议的目标非常简单且容易理解。

假设我们有一个定义在有限域 F 上的 v 元多项式,记作 g。协议的目标是计算和式:

一文了解零知识证明当中的Sum-check Protocol

和在 zkRollup 当中考虑的「外包计算」的场景类似,在应用当中,上述式子的计算量会非常大,我们希望将这个式子的计算交给证明者(Prover),之后证明者向验证者(Verifier)证明自己的计算结果是正确的。

2.协议假设

首先,需要明确在这个协议当中验证者的能力。我们假设验证者拥有可以计算函数 g 的预言(Oracle)。也就是说,对于验证者而言,确定某个输入 r 1, … , rv 之后,计算 g(r 1, … , rv) 是容易的。但是计算完整的结果 H 是困难的。

事实上,在现实应用当中,预言(Oracle)不会存在,但是可以通过某种手段实现,例如我们可以让证明者帮助验证者计算这个值,并用更多的技巧附加正确性的证明。

第二点,关于协议的目标,事实上 sum-check 协议可以对于任意的集合 B 计算 bBmg(b),但是不失一般性的,我们假设 B={ 0, 1 }。

3.协议过程

协议一共包含 v 轮。在每一轮当中会处理 g 中的一个变量。

第 1 轮:

一文了解零知识证明当中的Sum-check Protocol

如果证明者是诚实的,应当成立 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) 轮:

一文了解零知识证明当中的Sum-check Protocol

如果证明者是诚实的,应当成立 gj-1(rj-1)=gj( 0)+gj( 1)。验证者验证,若通过则选择随机数 rj 发送给证明者。

第 v 轮:

一文了解零知识证明当中的Sum-check Protocol
图 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 进行一次求值所需要的开销。

一文了解零知识证明当中的Sum-check Protocol
图 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 protocol 作为底层逻辑进行构造。下图展示了根据在 sum-check 基础上进行不同改造得到的不同证明系统。

一文了解零知识证明当中的Sum-check Protocol
图 4: Sum-check protocol 在四类证明系统当中的应用
一文了解零知识证明当中的Sum-check Protocol
图 5: Sum-check protocol 在简洁证明方面的具体应用

结语

本文梳理了 sum-check 协议的具体流程,以及讨论了协议的复杂度,同时展示了其在许多证明系统当中的应用。

在 web3 领域不断拓展的当下,密码学作为区块链技术的底层构件,其作用显得越来越重要。随着 zkrollup、隐私保护等等依赖零知识证明的应用和项目逐渐诞生,sum-check 协议,作为诸多证明系统的重要组件,也正在被学界和产业界同时给予越来越多的关注。

(声明:请读者严格遵守所在地法律法规,本文不代表任何投资建议)

(0)
上一篇 2023年1月30日 下午7:42
下一篇 2023年1月30日 下午7:53

相关推荐

  • 库克与马化腾 不谋而合

    6月21日,腾讯成立XR部门。同一天,Meta、微软、华为、阿里、英伟达、高通等36家科技企业共同创建了一个名为“元宇宙标准论坛”的组织,成员涵盖芯片厂商、游戏公司以及现有的标准制…

    2022年6月28日
    347
  • 从SEC与Coinbase的恩怨情仇说起,美国加密监管会走向何方

    SEC 负责维护全球最大资本市场的有序运作。他们还有权制定新规则,只要符合国会在 1933/1934 年制定的框架即可。SEC 执行这套框架旨在创造一种环境,让不良行为者承担责任,并为良好行为者提供创新机会。

    2023年6月6日
    575
  • 详解ETH合并后可能面临的PoS攻击及防御措施

    以太坊客户端就会进行一次重大升级(称为「合并」),这会关闭保护以太坊的工作量证明(PoW)算法,取而代之的是一种权益证明(PoS)共识机制。造成这种情况的原因有很多,这在其他文章当中已经有详细解释?。这将是一场哲学变革,同时也是一场技术变革。

    2022年8月18日
    720

发表回复

登录后才能评论
微信

联系我们
邮箱:whylweb3@163.com
微信:gaoshuang613