零知识证明 - zkSNARK应用的Nullifier Hash攻击 | 深入浅出区块链 | 技术博客

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

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

源于三天前

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

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

先从 semaphore 项目的代码开始：

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

signal - 广播的消息内容

a/b/c 以及 input - 是 zkSNARK 的证明以及公开信息（statement 信息）

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

什么是 Nullifier？

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

为了保护交易的隐私，在链上只存储 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 函数。

verify 就是验证 Groth16 的验证等式是否成立，再看 Groth16 的验证等式：

其中橙色部分就是 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 大不少。

攻击方法就形成了：

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

如何修复？

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

限制 input 不能超过 q。

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

本文作者为深入浅出区块链共建者：Star Li，他的公众号星想法有很多原创高质量文章，欢迎大家扫码关注。

学习中如遇问题，欢迎到区块链技术问答提问，这里有专家为你解惑。 深入浅出区块链 - 高质量的区块链技术博客 + 问答社区，为区块链学习双重助力

• 发表于 2019-07-29 16:10
• 阅读 ( 2705 )
• 学分 ( 20 )
• 分类：安全/漏洞