揭秘新型零知识证明漏洞:算术运算后缺乏多项式标准化

该漏洞会破坏假设并导致错误的计算,或者导致通过 rust panic 进行的拒绝服务攻击。

作者:Salus Insights

Salus 向 0xPARC 的 zk-bug-tracker 库添加了一种新型的 ZK 漏洞,算术运算后缺乏多项式标准化, 该漏洞由以太坊基金会 PSE 安全团队负责人 Kyle Charbonnet 审核。该漏洞会破坏假设并导致错误的计算,或者导致通过 rust panic 进行的拒绝服务攻击。为了更好地理解这个漏洞,我们将以 Zendoo 库中的一个具体实例进行说明。请大家对此类漏洞保持警惕。

1. 背景

在代码中,多项式被表示为向量的形式。即,多项式 a0+a1x+…+an-1xn-1+an*xn 被表示为[a0,a1,…,an-1,an]。在 ZK 证明系统中,需要对多项式进行标准化操作,即将多项式的最高次项的系数调整为非零。比如,将[1,2,0]调整为[1,2]才是标准化的多项式表示。

对多项式进行标准化操作是必要的。如果不进行标准化,系统会错误地存储多项式的最高次数,即它会大于其实际的最高次数。比如,对于[1,2,0],如果不进行标准化操作,它的最高次数会被错误地存储为 2,而实际是 1。基于非标准化的多项式生成证明时,错误的多项式实现将会使得 ZK 证明系统 panic,导致无法生成证明。

2. 案例分析

算术运算后缺乏多项式标准化,该漏洞属于 ZK 证明系统实现上的通用性漏洞。以下,我们以 Zendoo 库中用于快速傅里叶变换(FFT)的密集多项式(dense polynomials)实现的代码为例,说明其中存在的算术运算后缺乏多项式标准化的漏洞。

add() 函数是用来对两个密集多项式(self 和 other)进行加法运算的,加法运算的结果(result)也是一个密集多项式,这需要进行标准化。然而,该函数仅在最后一个分支处对 result 进行了标准化操作(19-21 行)。该函数默认在前三个分支出计算得到的 result 就是标准化的,但这是不合理的。比如,当 self 是[1,2,3],other 是[1,2,-3],此时满足第三个分支(7-12 行),即 self 和 other 这两个多项式最高次数相等,都是 2。而在第三个分支处计算后的 result 是[2,4,0],并未对其进行标准化操作。

非标准化的多项式在之后的计算过程中会产生错误。具体的实现代码如下:

揭秘新型零知识证明漏洞:算术运算后缺乏多项式标准化插图1

而且,在这段代码中,不只是在加法算法后缺乏多项式标准化。在加法运算前,self 和 other 作为 add() 函数的入参,也并没有检查他们是否是标准化的多项式表示。或者说,构造 self 和 other 的函数是否是按照标准化的方法进行构建的,也未可知。degree() 函数用来返回多项式的最高次项的指数。在 add() 函数中,非标准化的 self 和 other 在调用 degree() 函数时会引起 rust panic。

举个例子,self 是非标准化的多项式 1+2x+0x2,即向量[1,2,0],其最高次项的系数为 0。当 other 也不是零多项式时,满足 add() 函数的第三个分支,以 self 来调用 degree() 函数。在 degree() 函数中进入 else 分支。在 else 分支中有一个 assert! 宏,用来确保多项式的最高次数的系数不为 0。如果为 0,self.coeffs.last().map_or(false, |coeff| !coeff.is_zero()) 表达式结果为 false。即 self 向量的最后一个元素,即多项式的最高次项的系数为 0,返回 false。此时,assert! 宏会 panic。

Rust panic 会导致 ZK 证明系统遭受 DOS 攻击。攻击者可以通过构造大量的非标准化多项式,并且不断调用 add() 函数。由于这些输入会导致程序 panic,所以程序会不断地停止并重启。这将占用大量的计算和网络资源,从而影响到其他正常用户的使用,这就构成了一种 DOS 攻击。

揭秘新型零知识证明漏洞:算术运算后缺乏多项式标准化插图3

3. 总结

Salus 在 0xPARC 的 zk-bug-tracker 库中添加的新型 ZK 漏洞,即算术运算后缺乏多项式标准化,是具有通用性的。在 ZK 证明系统中,我们需要特别注意避免该漏洞。该漏洞会造成 ZK 证明系统的计算错误,或使系统遭受 DOS 攻击。可以在返回算术运算结果之前调用truncate_leading_zeros()函数进行标准化操作,同时,基于from_coefficients_vec()函数来构造标准化的多项式也是必要的。

针对此漏洞,Salus 团队提醒 ZK 项目方,在构建多项式时和执行多项式操作之后对其进行标准化,以免破坏 ZK 证明系统的完整性。同时,强烈建议项目方在项目上线之前,寻求专业的安全审计公司进行充分的安全审计,确保项目安全。

参考

https://github.com/0xPARC/zk-bug-tracker/pull/16

https://research.nccgroup.com/wp-content/uploads/2021/11/NCC_Group_ZenBlockchainFoundation_E001741_Report_2021-11-29_v1.2.pdf

https://github.com/HorizenOfficial/ginger-lib/blob/master/algebra/src/fft/polynomial/dense.rs#L151

https://github.com/HorizenOfficial/ginger-lib/blob/master/algebra/src/fft/polynomial/dense.rs#L87

联系邮箱:idea2003@foxmail.com

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注