zkSNARKs 合约库「输入假名」漏洞致众多混币项目爆雷
本文作者：p0n1（安比实验室）
大量零知识证明项目由于错误地使用了某个 zkSNARKs 合约库，引入「输入假名 (Input Aliasing) 」漏洞，可导致伪造证明、双花、重放等攻击行为发生，且攻击成本极低。众多以太坊社区开源项目受影响，其中包括三大最常用的 zkSNARKs 零知开发库 snarkjs、ethsnarks、ZoKrates，以及近期大热的三个混币（匿名转账）应用 hopper、Heiswap、Miximus。这是一场由 Solidity 语言之父 Chris 两年前随手贴的一段代码而引发的血案。
双花漏洞：最初暴露的问题
semaphore 是一个使用零知识证明技术的匿名信号系统，该项目由著名开发者 barryWhiteHat 此前的混币项目演化而来。
俄罗斯开发者 poma 最先指出该项目可能存在双花漏洞[1]。
问题出在第 83 行代码[2]，请仔细看。
该函数需要调用者构造一个零知识证明，证明自己可从合约中提走钱。为了防止「双花」发生，该函数还读取「废弃列表」，检查该证明的一个指定元素是否被标记过。如果该证明在废弃列表中，则合约判定校验不通过，调用者无法提走钱。开发者认为，这样一来相同的证明就无法被重复提交获利，认为此举可以有效防范双花或重放攻击。
然而事与愿违，这里忽视了一个致命问题。攻击者可根据已成功提交的证明，利用「输入假名」漏洞，对原输入稍加修改便能迅速「伪造证明」，顺利通过合约第 82 行的零知识证明校验，并绕过第 83 行的防双花检查。
该问题最早可追溯到 2017 年，由 Christian Reitwiessner 大神，也就是 Solidity 语言的发明者，提供的 zkSNARKs 合约密码学实现示例[3]。其后，几乎以太坊上所有使用 zkSNARKs 技术的合约，都照用了该实现。因此都可能遭受以下流程的攻击。
混币应用：该安全问题的重灾区
零知识证明技术在以太坊上最早和最广泛的应用场景是混币合约，或匿名转账、隐私交易。由于以太坊本身不支持匿名交易，而社区对于隐私保护的呼声越来越强烈，因此涌现出不少热门项目。这里以混币合约的应用场景为例，介绍「输入假名」漏洞对零知项目的安全威胁。
混币合约或匿名转账涉及两个要点：
证明自己有一笔钱
证明这笔钱没有花过
为了方便理解，这里简单描述一下流程：
A 要花一笔钱。
A 要证明自己拥有这笔钱。A 出示一个 zkproof，证明自己知道一个 hash (HashA) 的 preimage，且这个 hash 在以 root 为标志的 tree 的叶子上，且证明这个 preimage 的另一种 hash 是 HashB。其中 HashA 是 witness，HashB 是 public statement。由于 A 无需暴露 HashA，所以是匿名的。
合约校验 zkproof，并检查 HashB 是否在废弃列表中。若不在，则意味着这笔钱未花过，可以花（允许 A 的此次调用）。
如果可以花，合约需要把 HashB 放入废弃列表中，标明以 HashB 为代表的钱已经被花过，不能再次花了。
上面代码中的第 82 行 verifyProof(a, b, c, input) 用来证明这笔钱的合法性，input[] 是 public statement，即公共参数。第 83 行通过 require(nullifiers_set[input[1]] == false) 校验这笔钱是否被花过。
很多 zkSNARKs 合约尤其是混币合约，核心逻辑都与第 82 行和 83 行类似，因此都存在同样的安全问题，可利用「输入假名」漏洞进行攻击。
漏洞解析：一笔钱如何匿名地重复花 5 次？
上面 verifyProof(a, b, c, input) 函数的作用是根据传入的数值在椭圆曲线上进行计算校验，核心用到了名为 scalar_mul() 的函数，实现了椭圆曲线上的标量乘法[4]。
我们知道以太坊内置了多个预编译合约，进行椭圆曲线上的密码学运算，降低 zkSNARKs 验证在链上的 Gas 消耗。函数 scalar_mul() 的实现则调用了以太坊预编译 7 号合约，根据 EIP 196 实现了椭圆曲线 alt_bn128 上的标量乘法[5]。下图为黄皮书中对该操作的定义，我们常称之为 ECMUL 或 ecc_mul。
密码学中，椭圆曲线的 {x,y} 的值域是一个基于 mod p 的有限域，这个有限域称之为 Zp 或 Fp。也就是说，一个椭圆曲线上的一个点 {x,y} 中的 x,y 是 Fp 中的值。一条椭圆曲线上的某些点构成一个较大的循环群，这些点的个数称之为群的阶，记为q。基于椭圆曲线的加密就在这个循环群中进行。如果这个循环群的阶数（q）为质数，那么加密就可以在 mod q 的有限域中进行，该有限域记作 Fq。
一般选取较大的循环群作为加密计算的基础。在循环群中，任意选定一个非无穷远点作为生成元 G（通常这个群的阶q是个大质数，那么任选一个非零点都是等价的），其他所有的点都可以通过 G+G+.... 产生出来。这个群里的元素个数为 q，也即一共有 q 个点，那么我们可以用 0,1,2,3,....q-1 来编号每一个点。在这里第 0 个点是无穷远点，点1 就是刚才提到的那个 G，也叫做基点。点2 就是 G+G，点3 就是 G+G+G。
于是当要表示一个点的时候，我们有两种方式。第一种是给出这个点的坐标 {x,y}，这里 x,y 属于Fp。第二种方式是用 n*G 的方式给出，由于 G 是公开的，于是只要给出 n 就行了。n 属于 Fq。
看一下 scalar_mul(G1Point point, uint s) 函数签名，以 point 为生成元，计算 point+point+.....+point，一共 n 个 point 相加。这属于使用上面第二种方法表示循环群中的一个点。
在 Solidity 智能合约实现中需要使用 uint256 类型来编码 Fq，但 uint256 类型的最大值是大于q 值，那么 会出现这样一种情况：在 uint256 中有多个数 经过 mod 运算之后都会对应到同一个 Fq中的值。比如 s 和 s + q 表示的其实是同一个点，即第s个点。这是因为在循环群中点q 其实等价于 点0（每个点分别对应 0,1,2,3,....q-1）。同理，s + 2q 等均对应到点s 。我们把可以输入多个大整数会对应到同一个 Fq中的值 这一现象称作「输入假名」，即这些数互为假名。
以太坊 7 号合约实现的椭圆曲线是 y^2 = ax^3+bx+c。p 和 q 分别如下。
这里的 q 值即上文中提到的群的阶数。那么在 uint256 类型范围内，共有 uint256_max / q 个，算下来也就是最多会有 5 个整数代表同一个点（ 5 个「输入假名」）。
这意味着什么呢？让我们回顾上面调用 scalar_mul(G1Point point, uint s) 的 verifyProof(a, b, c, input) 函数，input[] 数组里的每个元素实际就是 s。对于每个 s，在 uint256 数据类型范围内，会最多存在其他 4 个值，传入后计算结果与原值一致。
因此，当用户向合约出示零知识证明进行提现后，合约会把 input[1] （也就是某个 s）放入作废列表。用户（或其他攻击者）还可以使用另外 4 个值再次进行证明提交。而这 4 个值之前并没有被列入「废弃列表」，因此“伪造”的证明可以顺利通过校验，利用 5 个「输入假名」一笔钱可以被重复花 5 次，而且攻击成本非常低！
还有更多受影响的项目
存在问题的远远不止 semaphore 一个。其他很多以太坊混币项目以及 zkSNARKs 项目都存在同样的允许「输入假名」的问题。
这当中，影响最大的要数几个大名鼎鼎的 zkSNARKs 库或框架项目，包括 snarkjs、ethsnarks、ZoKrates 等。许多应用项目会直接引用或参考他们的代码进行开发，从而埋下安全隐患。因此，上述三个项目迅速进行了安全修复更新。另外，多个利用了 zkSNARKs 技术的知名混币项目，如 hopper、Heiswap、Miximus 也立刻进行了同步修复。这些项目在社区热度都十分高，其中 Heiswap 更是被人们称为 「Vitalik 最喜爱的项目」。
「输入假名」漏洞的解决方案
事实上，所有使用了该 zkSNARKs 密码学合约库的项目都应该立即开展自查，评估是否受影响。那么应该如何修复这个问题？
所幸的是，修复很简单。仅需在验证函数中添加对输入参数大小的校验，强制要求 input 值小于上面提到的 q 值。即严禁「输入假名」，杜绝使用多个数表示同一个点。
暴露的深层问题值得反思
该「输入假名」导致的安全漏洞值得社区认真反思。我们再回顾一下整个故事。2017 年 Christian 在 Gist 网站贴出了自己的 zkSNARKs 合约计算实现。作为计算库，我们可以认为他的实现并没有安全问题，没有违反任何密码学常识，完美地完成了在合约中进行证明验证的工作。事实上，作为 Solidity 语言的发明者，Christian 在这里当然不会犯任何低级错误。而两年后的今天，这段代码却引发了如此的安全风波。两年多的时间内，可能有无数同行和专家看过或使用过这段只有两百多行的代码，却没有发现任何问题。
核心问题出在哪里？可能出在底层库的实现者和库的使用者双方间对于程序接口的理解出现了偏差。换句话说：底层库的实现者对于应用开发者的不当使用方式欠缺考虑；而上层应用开发者没有在使用中没有深入理解底层实现原理和注意事项，进行了错误的安全假设。
所幸的是，目前常见的 zkSNARKs 合约库都火速进行了更新，从底层库层面杜绝「输入假名」。安比（SECBIT）实验室认为，底层库的更新诚然能够很大程度上消除掉后续使用者的安全隐患，但若该问题的严重性没有得到广泛地宣传和传播，依旧会有开发者不幸使用到错误版本的代码，或者是根据错误的教程进行开发（就像因为整数溢出而归零的那些 Token 一样），从而埋下安全隐患。
「输入假名」漏洞不禁让我们回想起此前频繁曝出的「整数溢出」漏洞。二者相似之处颇多：都是源于大量开发者的错误假设；都与 Solidity 里的 uint256 类型有关；波及面都十分广；网络上也都流传着很多存在隐患的教程代码或者库合约。但显然「输入假名」漏洞显然更难检测，潜伏时间更长，需要的背景知识更多（涉及到复杂的椭圆曲线和密码学理论）。安比（SECBIT）实验室认为，随着 zkSNARKs、零知识证明应用、隐私技术的兴起，社区会涌现出更多的新应用，而背后暗藏的更多安全威胁可能会进一步暴露出来。希望这波新技术浪潮中，社区能充分吸收以往的惨痛教训，重视安全问题。
Reference
[1] https://github.com/kobigurk/semaphore/issues/16
[3] https://gist.github.com/chriseth/f9be9d9391efc5beb9704255a8e2989d
[5] https://github.com/ethereum/EIPs/blob/master/EIPS/eip-196.md
