為什么零知識證明系統(tǒng)并非萬無一失？

時間：2023-05-06|瀏覽：217

隨著數(shù)字資產(chǎn)和區(qū)塊鏈技術的快速發(fā)展，數(shù)字隱私保護和安全性成為了越來越受關注的話題。在這個背景下，一種名為"零知識證明（Zero-Knowledge Proof）"的技術正在逐漸嶄露頭角。

零知識證明技術可以在不泄露任何信息的情況下證明某些事情的真實性，被廣泛應用于保護隱私和安全性。其中，基于零知識證明技術的zk-SNARK近期備受矚目，成為數(shù)字資產(chǎn)和區(qū)塊鏈技術領域的熱門話題，但有一些安全問題卻往往被我們忽視。

Beosin將陸續(xù)推出zk零知識證明安全研究，第一篇，本文將深入探討zk-SNARK的背景，深度剖析零知識證明zk-SNARK漏洞：輸入假名漏洞是如何被挖掘出來的？

1. 什么是zk-SNARK？

zk-SNARK（Zero-Knowledge Succinct Non-Interactive Argument of Knowledge）是一種基于零知識證明的技術，可以在不泄露真實信息的情況下證明某個聲明的真實性。

它是一種非常高效的零知識證明技術，可以在非常短的時間內(nèi)生成和驗證證明，同時保護隱私和安全性。

零知識證明項目Semaphore上曾經(jīng)被發(fā)現(xiàn)了一個可以導致雙花的輸入假名漏洞，漏洞提出者poma給出了兩筆成功的示例交易：

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

該漏洞影響范圍非常廣，不止涉及到眾多知名zkSNARKs第三方庫，連眾多DApp項目方也不能幸免，本文最后將列舉出各個項目方具體的漏洞代碼以及修復方案，我們先對輸入假名漏洞進行詳細介紹。

2. 漏洞原理

Semaphore項目允許以太坊用戶在不透漏其原始身份的情況下，以某個團隊成員的身份發(fā)送投票等操作，其中所有的團隊成員組成了一棵默克爾樹，每個成員是一個葉子結(jié)點。合約需要團隊成員提供一個零知識證明，以證明其身份的合法性。為了防止身份偽造，每個證明只能使用一次，因此合約中會存儲已經(jīng)驗證過的證明列表，如果用戶提供了使用過的證明，程序就會報錯。具體的實現(xiàn)代碼如下：

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

可以看到，上述代碼首先調(diào)用 verifyProof 校驗零知識證明的合法性，接著通過證明參數(shù)nullifiers_hash 校驗該證明是否是初次使用，但由于未對 nullifiers_hash 進行完整的合法性檢查，使得攻擊者可以偽造出多個證明通過校驗，實現(xiàn)雙花攻擊。具體地說，由于合約變量類型uint256能夠表示的數(shù)值范圍遠大于零知識證明電路，而此處代碼僅考慮了 nullifiers_hash 本身是否已被使用，未限制合約中的 nullifiers_hash 的取值范圍，使得攻擊者利用密碼學中的模運算可以偽造多個證明通過合約校驗。因為參數(shù)的取值范圍涉及到一些零知識證明相關的數(shù)學知識，并且采用不同的零知識證明算法對應不同的取值范圍，因此后文將詳細介紹。

首先如果要在以太坊中生成和驗證zk-SNARK證明，需要使用 F_p-arithmetic 有限域橢圓曲線電路，其中曲線的一般方程如下：

可以發(fā)現(xiàn)曲線上的點都會進行一個模p運算，所以電路生成的證明參數(shù)s值取值范圍為[0,1,…,p-1]，但是鏈上合約的變量類型uint256取值范圍為 [0,115792089237316195423570985008687907853269984665640564039457584007913129639935]，那么當合約的變量范圍大于電路取值范圍時，存在下列多個具有相同輸出的證明參數(shù)值：

綜上，只要知道了其中一個合法的證明參數(shù)s，uint256范圍內(nèi)的s+np( n = 1,2,…,n)都可以滿足驗證計算，于是攻擊者在獲取到任意驗證通過的s，即可構造max(uint256)/p個 s都可以通過校驗，具體的攻擊流程如下：

上文可知，參數(shù)的取值范圍由p決定，而不同類型的F_p對應不同的p，需要根據(jù)具體使用的零知識算法確定，如：

EIP-196 中定義的BN254 曲線（也稱為 ALT_BN128 曲線） p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

circom2 引入了兩個新的素數(shù)，即BLS12-381曲線 p = 52435875175126190479447740508185965837690552500527637822603658699938581184513

以ALT_BN128 曲線為例，共計可以生成5個不同的證明參數(shù)通過驗證，計算過程如下：

3. 漏洞復現(xiàn)

由于Semaphore項目本身代碼已經(jīng)更改，重新部署整個項目較為繁雜，因此我們使用目前常用的零知識證明編譯器circom編寫PoC復現(xiàn)整個攻擊過程。為了方便大家更好的理解整個流程，這里我們先以circom為例，介紹Groth16算法的零知識證明生成和驗證過程。

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

1.項目方需要設計一個算術電路并使用 circom 語法將其編寫為一個電路描述文件 *.circom

2.編譯電路文件，并將其轉(zhuǎn)化為 R1CS 的電路描述文件

3.使用snarkjs庫根據(jù)輸入文件 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相乘的結(jié)果

3.2 編譯電路

使用下列命令行編譯multiplier2.circom，并將其轉(zhuǎn)化為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，是一個符號文件，用于調(diào)試或以注釋模式打印約束系統(tǒng)

?--c：生成文件夾multiplier2_cpp，包含生成witness所需的c代碼文件

注意：生成witness有兩種方式，一種是使用wasm，一種是使用剛生成的C++代碼，如果是大型電路的話使用C++代碼比wasm效率更高

3.3 計算witness

在multiplier2_js文件夾下創(chuàng)建input.json文件，該文件包含了以標準json格式編寫的輸入，此時使用字符串而不是數(shù)字，是因為js不能準確處理大于2^{53}的數(shù)，針對指定的 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、原始驗證參數(shù)originalHash和攻擊參數(shù)attackHash如下圖所示：

3.6 驗證證明

證明的驗證方式同樣也有兩種，一種是使用snarkjs庫進行驗證，一種是合約驗證。我們這里主要使用鏈上合約的驗證方式驗證原始證明參數(shù)originalHash、攻擊證明參數(shù)attackHash。

這里我們使用snarkjs自動生成一個驗證合約verifier.sol，注意最新版本0.6.10的snarkjs生成的合約已經(jīng)修復了這個問題，所以我們使用舊版本生成合約：

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 曲線進行復現(xiàn)，因此共計可以生成5個不同參數(shù)通過驗證：

4. 修復方案

Semaphore 項目已經(jīng)針對該漏洞進行了修復，具體修復代碼如下：

圖源：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

但是該漏洞屬于實現(xiàn)上的通用漏洞，經(jīng)過我們Beosin安全團隊的研究發(fā)現(xiàn)，眾多知名的零知識證明算法組件和DApp項目都受到該漏洞的影響，絕大部分后續(xù)進行了及時修復。以下列舉出部分項目方的修復方案：

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：