零知识证明 – zkSNARK 应用的 Nullifier Hash 攻击

早上很多朋友 @我,安比实验室发表了一篇文章 zkSNARK 的 “输入假名” 的攻击。迅速看了看,很赞。这个攻击原理其实比较简单,但是,不深入理解 zkSNARK 以及使用场景的朋友确实很难发现和理解。本文讲讲我对这个攻击的分析和理解。

源于三天前

这种攻击方式一直潜伏着,没被发现。直到三天前:

零知识证明 - zkSNARK 应用的 Nullifier Hash 攻击

俄罗斯开发者 poma,在项目 semaphore 提交了一个 issue,公开了这个攻击方法。poma 同时也在 kovan 测试网络验证了这种攻击方式。

先从 semaphore 项目的代码开始:

零知识证明 - zkSNARK 应用的 Nullifier Hash 攻击

话说,semaphore 是个很有意思的项目,它提供了一套方法能让用户不暴露自己身份的情况下广播消息。暂不深入介绍这个项目的内容,直接看函数。broadcastSignal 函数提交了证明,某个用户发送某个消息(signal)。只有具体的某个 broadcaster(server)才会调用这个函数。

signal – 广播的消息内容

a/b/c 以及 input – 是 zkSNARK 的证明以及公开信息(statement 信息)

函数实现(第 82 行),调用 verifyProof 函数验证证明以及 statement 信息是否是合理的证明。第 83 行,查看 nullifier_hash 是否被用过。

什么是 Nullifier?

熟悉 ZCash 的朋友,估计对 Nullifier 比较熟悉。

零知识证明 - zkSNARK 应用的 Nullifier Hash 攻击

为了保护交易的隐私,在链上只存储 Note 和 Nullifier 对应的 hash 信息。Note 代表可以花的钱,Nullifier 表示某笔钱已经消费。Note 和 Nullifier 一一对应,一个 Note 只存在一个 Nullifier。通过 zkSNARK 生成证明,证明 Note 和 Nullifier 的正确性以及存在某种联系。在链上,为了防止双花,在执行某个交易时,必须确定某个 Note 是否已经消费。确定的方法就是记录下 Nullifier 对应的 hash 信息。

verifyProof 的计算

verifyProof 的函数实现在 snarkjs 项目的 templates/verifier_groth.sol(以 Groth16 为例)。verifyProof 只是个简单的 wrapper,具体计算的实现时 verify 函数。

verifyProof的计算

verify 就是验证 Groth16 的验证等式是否成立,再看 Groth16 的验证等式:

零知识证明 - zkSNARK 应用的 Nullifier Hash 攻击

其中橙色部分就是 input,蓝色部分就是 vk.IC。scalar_mul 是椭圆曲线的 “标量乘法” 计算。vk.IC 是椭圆曲线上的一个点(假设为 P),input 是个标量(假设 x)。scalar_mul(P, x) 表示为 xP。如果椭圆曲线的阶为 q 的话,下面的等式成立:

(x+q)P = xP + qP = xP

也就是说,x+p 和 x 作为 input 的话,scalar_mul 的计算结果相等。也就是说,Groth16 的等式依然成立。

如何攻击?

在智能合约中,输入 input 是用 uint 表示。以太坊上一般采用 bn254 的曲线,q 为:

21888242871839275222246405745257275088548364400416034343698204186575808495617。虽然这个 q 比较大,但是,uint 的最大值还是比 q 大不少。

攻击方法就形成了:

零知识证明 - zkSNARK 应用的 Nullifier Hash 攻击

在一个用户提交了证明以及公开的 input 信息后,攻击者修改 input 中的 nullifier_hash 即可。虽然逻辑上在花费同一笔钱,但是,智能合约却认为是花费不同的费用。智能合约认为一个 Note 只能对应一个 Nullfier,事实上,在这样的情况下,一个 Note 对应了多个 Nullfier。

如何修复?

修复的方式有好多种,目前最简单的修复方式是在 verify 函数加限制:

零知识证明 - zkSNARK 应用的 Nullifier Hash 攻击

限制 input 不能超过 q。

总结:

三天前,俄罗斯开发者 poma 公开了 zkSNARK 应用模型下的一种攻击方式。攻击不需要重新生成证明信息,只需要修改 Statement 中 Nullfier 对应的 hash 数据。原理是,椭圆曲线是个循环群,scalarMul 计算在输入的标量加上椭圆曲线的阶的情况下,结果相等。

本文作者为深入浅出区块链共建者:Star Li,他的公众号星想法

该内容来自于互联网公开内容,非区块链原创内容,如若转载,请注明出处:https://htzkw.com/archives/5831

联系我们

aliyinhang@gmail.com