新型零知识证明漏洞剖析：算术运算后缺乏多项式标准化

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]，并未对其进行标准化操作。

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

而且，在这段代码中，不只是在加法算法后缺乏多项式标准化。在加法运算前，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. 总结

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

关联标签

DOS 攻击零知识证明漏洞 Salus ZK

链捕手ChainCatcher提醒，请广大读者理性看待区块链，切实提高风险意识，警惕各类虚拟代币发行与炒作，站内所有内容仅系市场信息或相关方观点，不构成任何形式投资建议。如发现站内内容含敏感信息，可点击“举报”，我们会及时处理。