In the previous article, we explained the inherent malleability vulnerability in the Groth16 proof system theoretically.

https://glacier-screen-c36.notion.site/Beosin-s-Research-Transaction-Malleability-Attack-of-Groth16-Proof-c090649950804af686e276baa3ba8182

In this article, we take the Tornado.Cash project as an example, modifying parts of its circuit and code to demonstrate malleability attack flows and the corresponding mitigations in the project, hoping to raise awareness for other zkp projects. Tornado.Cash uses the snarkjs library with the following development flow, so we'll dive right in - please refer to the first article in the series if you are unfamiliar with the library.

1 Tornado.Cash Structure

There are 4 main entities in the interaction flow of Tornado.Cash:

Source: https://docs.circom.io/

First the user initiates deposit or withdrawal on Tornado.Cash frontend. Then the Relayer forwards the transaction request to the Tornado.Cash Proxy contract on-chain, which further forwards it to the corresponding Pool based on amount, and finally performs the deposit/withdrawal processing. The architecture is as follows:

As a coin mixer, Tornado.Cash has two main business functions:

Source: https://ipfs.io/ipns/tornadocash.eth/

The server then generates two 31-byte random numbers - nullifier and secret. Concatenating and hashing them generates the commitment. The nullifier + secret is returned to the user as a note, like below:

Then a deposit transaction is initiated, sending the commitment to the on-chain Tornado.Cash Proxy contract. The proxy forwards the data to the corresponding Pool based on deposit amount. Finally the Pool contract inserts the commitment as a leaf node into the merkle tree, and stores the computed root in the Pool contract.

The server then retrieves all Tornado.Cash deposit events off-chain, withdraws the commitments to build a local merkle tree, and uses the user provided note (nullifier + secret) to generate the commitment and corresponding merkle path and root. This is input into a circuit to obtain a zero-knowledge SNARK proof. Finally, a withdraw transaction is initiated to the on-chain Tornado.Cash Proxy contract, which forwards it to the corresponding Pool to verify the proof, and sends the money to the user's specified receiving address.

The core of Tornado.Cash's withdraw is toprove that a certain commitment exists in the Merkle tree without revealing the user's nullifier and secret.

The Merkle tree structure is as follows:

2 Tornado.Cash Vulnerable Version After Modification

2.1 Tornado.Cash Modification

Based on the previous article about Groth16 malleability attack principles, we know attackers can generate multiple different Proofs using the same nullifier and secret, so if developers don't consider replay attacks leading to double-spending, it can threaten project funds. Before modifying Tornado.Cash, this article will first introduce the Pool contract code that handles withdraws in Tornado.Cash:

As shown in the image above, to prevent attackers from double spending using the same Proof, while not revealing the nullifier and secret, Tornado.Cash added a public signal called nullifierHash in the circuit, which is the Pedersen hash of the nullifier, and can be passed as a parameter on-chain. The Pool contract then uses this variable to check if a valid Proof has been used before.However, what if instead of modifying the circuit, the project simply records Proofs to prevent double spending attacks? This would reduce circuit constraints and save costs, but would it work?To test this hypothesis, this article will remove the added nullifierHash public signal from the circuit, and change the contract verification to just check the Proof.Since Tornado.Cash retrieves all deposit events to build the merkle tree on each withdraw, then verifies if the root values are within the last 30 generated, which is cumbersome, this article will also remove the merkleTree circuit, leaving just the core withdraw logic, as follows:

Note: We discovered during the experiments that the latest TornadoCash code on GitHub lacks output signals in the withdraw circuit, requiring manual fixes to run properly. （https://github.com/tornadocash/tornado-core**）**

Based on the modified circuit above, following the development process outlined earlier using snarkjs etc, a normal Proof is generated, denoted as proof1:

2.2 Experimental Verification

2.2.1 Verification with Default circom Contract

First we use the default contract generated by circom. Since it does not record any used Proof info, attackers can replay proof1 multiple times to achieve double-spending attacks. In the following experiment, the same input's proof can be replayed unlimited times and still pass verification.

The image below shows proof1 passing verification in the default contract, including the Proof parameters A, B, C from the previous article, and the final result:

The next image shows the results of calling the verifyProof function multiple times with the same proof1. The experiment finds that for the same input, no matter how many times proof1 is used by the attacker, it always passes:

Testing in the native snarkjs js library also does not defend against reused Proofs, with results as follows:

2.2.2 Verification with Basic Anti-Replay Contract

To fix the replay vulnerability in the default circom contract, this article records a value from the valid Proof(proof1) to prevent replaying already verified proofs for double-spending attacks, as shown below:

Continuing to verify with proof1, the experiment finds the transaction reverts with "The note has been already spent" when reusing the same proof, as shown:

However,although this achieves the goal of preventing basic proof replay attacks, as covered earlier Groth16 has malleability vulnerabilities that can bypass this. The following PoC constructs a forged SNARK proof for the same input based on the algorithm from previous article, and it still passes verification. The PoC code to generate forged proof2 is:

The generated forgery PROOF2 is shown below:

Again using this parameter to call verifyProof function for proof verification, the experiment found that the same input in the case of using proof2 verification has passed again, as shown below:

Although the forged proof2 can only be used once more, since there are nearly unlimited forged proofs for the same input, this could lead to contract funds being withdrawn unlimited times.

Testing in the circom js library also shows proof1 and the forged proof2 passing verification:

2.2.3 Verification with Tornado.Cash Anti-Replay Contract

After so many failed attempts, is there no way to solve this once and for all? Here, following Tornado.Cash's method of checking if the original input has been used, this article further modifies the contract code as:

It should be noted thatto demonstrate simple mitigations against Groth16 malleability attacks, this article takes the approach of directly recording original circuit inputs, which does not conform to zero knowledge principles of keeping inputs private.For example in Tornado.Cash the inputs are private, so a new public input is added to identify a proof. Since this article's circuit does not add an identifier, the privacy is poorer compared to Tornado.Cash - this is just an experimental demo. The results are as follows:

It can be seen that with the same input, only the first proof1 passes verification. After that, both proof1 and the forged proof2 cannot pass verification.

3 Summary and Recommendations

Through modifying TornadoCash's circuit and using the default contract verification generated by the commonly used Circom, this article has verified the existence and risks of replay vulnerabilities. It further proves that using common measures at the contract level can defend against replay attacks, but cannot prevent Groth16 malleability attacks. Based on this, we suggest Zero Knowledge Proof projects note the following during development:

Beosin is a leading global blockchain security company co-founded by several professors from world-renowned universities and there are 40+ PhDs in the team, and set up offices in 10+ cities including Hong Kong, Singapore, Tokyo and Miami. With the mission of "Securing Blockchain Ecosystem", Beosin provides "All-in-one" blockchain security solution covering Smart Contract Audit, Risk Monitoring & Alert, KYT/AML, and Crypto Tracing. Beosin has already audited more than 3000 smart contracts including famous Web3 projects PancakeSwap, Uniswap, DAI, OKSwap and all of them are monitored by Beosin EagleEye. The KYT AML are serving 100+ institutions including Binance.

Contact

If you need any blockchain security services, welcome to contact us:

Official WebsiteBeosin EagleEyeTwitterTelegramLinkedin