Beosin|深度剖析零知识证明zk-SNARK漏洞：为什么零知识证明系统并非万无一失？

时间：2023-05-06|浏览：274

随着数字资产和区块链技术的快速发展，数字隐私保护和安全性成为了越来越受关注的话题。在这个背景下，一种名为"零知识证明（Zero-Knowledge Proof）"的技术正在逐渐崭露头角。

零知识证明技术可以在不泄露任何信息的情况下证明某些事情的真实性，被广泛应用于保护隐私和安全性。其中，基于零知识证明技术的zk-SNARK近期备受瞩目，成为数字资产和区块链技术领域的热门话题，但有一些安全问题却往往被我们忽视。

Beosin将陆续推出zk零知识证明安全研究，第一篇，本文将深入探讨zk-SNARK的背景，深度剖析零知识证明zk-SNARK漏洞：输入假名漏洞是如何被挖掘出来的？

1. 什么是zk-SNARK？

zk-SNARK（Zero-Knowledge Succinct Non-Interactive Argument of Knowledge）是一种基于零知识证明的技术，可以在不泄露真实信息的情况下证明某个声明的真实性。

它是一种非常高效的零知识证明技术，可以在非常短的时间内生成和验证证明，同时保护隐私和安全性。

零知识证明项目Semaphore上曾经被发现了一个可以导致双花的输入假名漏洞，漏洞提出者poma给出了两笔成功的示例交易：

图源：https://github.com/semaphore-protocol/semaphore/issues/16

该漏洞影响范围非常广，不止涉及到众多知名zkSNARKs第三方库，连众多DApp项目方也不能幸免，本文最后将列举出各个项目方具体的漏洞代码以及修复方案，我们先对输入假名漏洞进行详细介绍。

2. 漏洞原理

Semaphore项目允许以太坊用户在不透漏其原始身份的情况下，以某个团队成员的身份发送投票等操作，其中所有的团队成员组成了一棵默克尔树，每个成员是一个叶子结点。合约需要团队成员提供一个零知识证明，以证明其身份的合法性。为了防止身份伪造，每个证明只能使用一次，因此合约中会存储已经验证过的证明列表，如果用户提供了使用过的证明，程序就会报错。具体的实现代码如下：

图源：https://github.com/semaphore-protocol/semaphore/blob/602dd57abb43e48f490e92d7091695d717a63915/semaphorejs/contracts/Semaphore.sol#L83

可以看到，上述代码首先调用 verifyProof 校验零知识证明的合法性，接着通过证明参数nullifiers_hash 校验该证明是否是初次使用，但由于未对 nullifiers_hash 进行完整的合法性检查，使得攻击者可以伪造出多个证明通过校验，实现双花攻击。具体地说，由于合约变量类型uint256能够表示的数值范围远大于零知识证明电路，而此处代码仅考虑了 nullifiers_hash 本身是否已被使用，未限制合约中的 nullifiers_hash 的取值范围，使得攻击者利用密码学中的模运算可以伪造多个证明通过合约校验。因为参数的取值范围涉及到一些零知识证明相关的数学知识，并且采用不同的零知识证明算法对应不同的取值范围，因此后文将详细介绍。

首先如果要在以太坊中生成和验证zk-SNARK证明，需要使用 F_p-arithmetic 有限域椭圆曲线电路，其中曲线的一般方程如下：

可以发现曲线上的点都会进行一个模p运算，所以电路生成的证明参数s值取值范围为[0,1,…,p-1]，但是链上合约的变量类型uint256取值范围为 [0,115792089237316195423570985008687907853269984665640564039457584007913129639935]，那么当合约的变量范围大于电路取值范围时，存在下列多个具有相同输出的证明参数值：

综上，只要知道了其中一个合法的证明参数s，uint256范围内的s+np( n = 1,2,…,n)都可以满足验证计算，于是攻击者在获取到任意验证通过的s，即可构造max(uint256)/p个 s都可以通过校验，具体的攻击流程如下：

上文可知，参数的取值范围由p决定，而不同类型的F_p对应不同的p，需要根据具体使用的零知识算法确定，如：

EIP-196 中定义的BN254 曲线（也称为 ALT_BN128 曲线） p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

circom2 引入了两个新的素数，即BLS12-381曲线 p = 52435875175126190479447740508185965837690552500527637822603658699938581184513

以ALT_BN128 曲线为例，共计可以生成5个不同的证明参数通过验证，计算过程如下：

3. 漏洞复现

由于Semaphore项目本身代码已经更改，重新部署整个项目较为繁杂，因此我们使用目前常用的零知识证明编译器circom编写PoC复现整个攻击过程。为了方便大家更好的理解整个流程，这里我们先以circom为例，介绍Groth16算法的零知识证明生成和验证过程。

图源：https://docs.circom.io/

1.项目方需要设计一个算术电路并使用 circom 语法将其编写为一个电路描述文件 *.circom

2.编译电路文件，并将其转化为 R1CS 的电路描述文件

3.使用snarkjs库根据输入文件 input.json 计算出对应的 witness

4.接着通过可信设置生成一个证明密钥 Proving key 和验证密钥 Validation key，其中Proving key用于生成证明Proof， Validation key 用于验证Proof，最后用户利用密钥生成对应的零知识证明Proof

5.验证用户的证明

接下来我们将按照上述流程分步进行介绍。

3.1 编写 multiplier2.circom

为了方便大家理解，我们直接使用circom官方的demo，具体代码如下：

pragma circom 2.0.0;template Multiplier2() {    signal input a;    signal input b;    signal output c;    c <== a*b; }
component main = Multiplier2();

该电路中有两个输入信号a和b，一个输出信号c，并且c的值是a和b相乘的结果

3.2 编译电路

使用下列命令行编译multiplier2.circom，并将其转化为R1CS：

circom multiplier2.circom --r1cs --wasm --sym --c

编译后会生成4个文件，其中

•--r1cs：生成的circuit.r1cs是二进制格式的电路约束文件

•--wasm：生成的multiplier2_js文件夹包含wasm汇编代码，和生成witness所需的其他文件目录（generate_witness.js、multiplier2.wasm）

•--sym：生成文件夹multiplier2.sym，是一个符号文件，用于调试或以注释模式打印约束系统

•--c：生成文件夹multiplier2_cpp，包含生成witness所需的c代码文件

注意：生成witness有两种方式，一种是使用wasm，一种是使用刚生成的C++代码，如果是大型电路的话使用C++代码比wasm效率更高

3.3 计算witness

在multiplier2_js文件夹下创建input.json文件，该文件包含了以标准json格式编写的输入，此时使用字符串而不是数字，是因为js不能准确处理大于2^{53}的数，针对指定的 input.json 生成对应的witness：

node generate_witness.js multiplier2.wasm input.json witness.wtns

3.4 可信设置

该步骤主要是选取零知识证明需要的椭圆曲线类型，以及生成一系列原始密钥*.key文件，其中multiplier2_0000.zkey包含证明密钥、验证密钥，multiplier2_0001.zkey则是验证密钥，最终导出的验证密钥文件是verification_key.json

snarkjs powersoftau new bn128 12 pot12_0000.ptau -vsnarkjs powersoftau contribute pot12_0000.ptau pot12_0001.ptau --name="First contribution">

3.5 生成证明

利用snarkjs有两种方式可以生成证明，一种是命令行，一种是脚本生成。由于我们需要构造攻击向量，所以这里主要使用脚本生成。

3.5.1 生成正常 publicSignal

snarkjs groth16 prove multiplier2_0001.zkey witness.wtns proof.json public.json

该命令会输出两个文件，其中proof.json是生成的证明文件，public.json是公共输入值。

3.5.2 生成攻击 publicSignal

async function getProof() { let inputA = "7" let inputB = "11" const { proof, publicSignals } = await snarkjs.groth16.fullProve({ a: inputA, b: inputB }, "Multiplier2.wasm", "multiplier2_0001.zkey") console.log("Proof: ") console.log(JSON.stringify(proof, null, 1));

    let q = BigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617")    let originalHash = publicSignals    let attackHash = BigInt(originalHash) + q
    console.log("originalHash: " + publicSignals)    console.log("attackHash: " + attackHash)}

生成的证明Proof、原始验证参数originalHash和攻击参数attackHash如下图所示：

3.6 验证证明

证明的验证方式同样也有两种，一种是使用snarkjs库进行验证，一种是合约验证。我们这里主要使用链上合约的验证方式验证原始证明参数originalHash、攻击证明参数attackHash。

这里我们使用snarkjs自动生成一个验证合约verifier.sol，注意最新版本0.6.10的snarkjs生成的合约已经修复了这个问题，所以我们使用旧版本生成合约：

snarkjs zkey export solidityverifier multiplier2_0001.zkey verifier.sol

合约关键代码如下：

function verify(uint[] memory input, Proof memory proof) internal view returns (uint) {        VerifyingKey memory vk = verifyingKey();        require(input.length + 1 == vk.IC.length,"verifier-bad-input");        // Compute the linear combination vk_x        Pairing.G1Point memory vk_x = Pairing.G1Point(0, 0);        for (uint i = 0; i < input.length; i++)            vk_x = Pairing.addition(vk_x, Pairing.scalar_mul(vk.IC[i + 1], input[i]));        vk_x = Pairing.addition(vk_x, vk.IC[0]);        if (!Pairing.pairingProd4(            Pairing.negate(proof.A), proof.B,            vk.alfa1, vk.beta2,            vk_x, vk.gamma2,            proof.C, vk.delta2        )) return 1;        return 0;}

此时，使用originalHash验证通过：

最后使用刚伪造的attackHash：

21888242871839275222246405745257275088548364400416034343698204186575808495694，同样验证通过！即同一份proof，可以被多次验证通过，即可造成双花攻击。

此外，由于本文使用ALT_BN128 曲线进行复现，因此共计可以生成5个不同参数通过验证：

4. 修复方案

Semaphore 项目已经针对该漏洞进行了修复，具体修复代码如下：

图源：https://github.com/semaphore-protocol/semaphore/blob/0cb0ef3514bc35890331379fd16c7be071ada4f6/packages/contracts/contracts/base/SemaphoreVerifier.sol#L42

图源：https://github.com/semaphore-protocol/semaphore/blob/0cb0ef3514bc35890331379fd16c7be071ada4f6/packages/contracts/contracts/base/Pairing.sol#L94

但是该漏洞属于实现上的通用漏洞，经过我们Beosin安全团队的研究发现，众多知名的零知识证明算法组件和DApp项目都受到该漏洞的影响，绝大部分后续进行了及时修复。以下列举出部分项目方的修复方案：

ethsnarks：

图源 https://github.com/HarryR/ethsnarks/commit/34a3bfb1b0869e1063cc5976728180409cf7ee96

snarkjs：

图源：https://github.com/iden3/snarkjs/commit/25dc1fc6e311f47ba5fa5378bfcc383f15ec74f4

heiswap-dapp：

图源：https://github.com/kendricktan/heiswap-dapp/commit/de022ffc9ffdfa4e6d9a7b51dc555728e25e9ca5#diff-a818b8dfd8f87dea043ed78d2e7c97ed0cda1ca9aed69f9267e520041a037bd5

EY Blockchain：