[Tornadocash Circuit Breakdown] Part 2

Technical Tutorials
[Tornadocash Circuit Breakdown] Part 2
none 0.0 0
1

Introduction

In the first part of this tutorial, we explored how the MerkleTreeChecker.circom circuit validates the inclusion of a commitment in a Merkle tree, a key component of Tornado Cash’s privacy mechanism. Now, in this second part, we will dive into the Withdraw.circom circuit, which builds upon the Merkle proof verification to implement a full withdrawal process.

The Withdraw circuit ensures that:

  1. The user’s deposit (commitment) exists in the Merkle tree of deposits.
  2. The nullifier used for withdrawal is valid and unique to prevent double-spending.
  3. Metadata like recipient, relayer, fee, and refund cannot be tampered with during the transaction.

By combining cryptographic hashing, Merkle proof verification, and tamper-proof constraints, this circuit forms the backbone of Tornado Cash’s anonymous withdrawal functionality. Let’s break down its components and understand how it works step by step.

To understand how tornado cash works, i suggest you check out the part 1 here

Building the Circuit

For installation and project setup, check out Part1 of this section in the series.

Complete Circuit code

you can check out the tornadocash repo here

include "../node_modules/circomlib/circuits/bitify.circom";
include "../node_modules/circomlib/circuits/pedersen.circom";
include "merkleTree.circom";

// computes Pedersen(nullifier + secret)
template CommitmentHasher() {
    signal input nullifier;
    signal input secret;
    signal output commitment;
    signal output nullifierHash;

    component commitmentHasher = Pedersen(496);
    component nullifierHasher = Pedersen(248);
    component nullifierBits = Num2Bits(248);
    component secretBits = Num2Bits(248);
    nullifierBits.in <== nullifier;
    secretBits.in <== secret;
    for (var i = 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];
}

// Verifies that commitment that corresponds to given secret and nullifier is included in the merkle tree of deposits
template Withdraw(levels) {
    signal input root;
    signal input nullifierHash;
    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 private input nullifier;
    signal private input secret;
    signal private input pathElements[levels];
    signal private input pathIndices[levels];

    component hasher = CommitmentHasher();
    hasher.nullifier <== nullifier;
    hasher.secret <== secret;
    hasher.nullifierHash === nullifierHash;

    component tree = MerkleTreeChecker(levels);
    tree.leaf <== hasher.commitment;
    tree.root <== root;
    for (var i = 0; i < levels; i++) {
        tree.pathElements[i] <== pathElements[i];
        tree.pathIndices[i] <== pathIndices[i];
    }

    // 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);

Code Walkthrough

Overview of the Circuit

The Withdraw circuit consists of:

  1. CommitmentHasher: Computes a commitment and nullifier hash using Pedersen hashing.
  2. MerkleTreeChecker: Verifies the inclusion of the commitment in the Merkle tree.
  3. Constraints for Outputs: Adds constraints for recipient, relayer, fee, and refund to ensure tamper-proofing.

1. CommitmentHasher Template

template CommitmentHasher() {
    signal input nullifier;
    signal input secret;
    signal output commitment;
    signal output nullifierHash;

    component commitmentHasher = Pedersen(496);
    component nullifierHasher = Pedersen(248);
    component nullifierBits = Num2Bits(248);
    component secretBits = Num2Bits(248);
    nullifierBits.in <== nullifier;
    secretBits.in <== secret;
    for (var i = 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];
}

The CommitmentHasher computes two key values:

  1. Commitment: Used to identify the deposit in the Merkle tree.
  2. Nullifier Hash: Prevents double-spending by ensuring each nullifier is unique.

Key Components:

  1. Pedersen Hashing:
  • A zk-SNARK-friendly hash function used to derive cryptographic commitments.
  • Two Pedersen hashers are used:
    • commitmentHasher (496 bits) for the full commitment.
    • nullifierHasher (248 bits) for the nullifier alone.
  1. Num2Bits:
  • Converts inputs (nullifier and secret) into their binary representations for the hashers.
  1. How It Works:
  • Split the nullifier and secret into 248-bit binary arrays.
  • Pass the bits into the hashers to compute the outputs.

2. Withdraw Template

template Withdraw(levels) {
    signal input root;
    signal input nullifierHash;
    signal input recipient; 
    signal input relayer;  
    signal input fee;      
    signal input refund;   
    signal private input nullifier;
    signal private input secret;
    signal private input pathElements[levels];
    signal private input pathIndices[levels];

    component hasher = CommitmentHasher();
    hasher.nullifier <== nullifier;
    hasher.secret <== secret;
    hasher.nullifierHash === nullifierHash;

    component tree = MerkleTreeChecker(levels);
    tree.leaf <== hasher.commitment;
    tree.root <== root;
    for (var i = 0; i < levels; i++) {
        tree.pathElements[i] <== pathElements[i];
        tree.pathIndices[i] <== pathIndices[i];
    }

    signal recipientSquare;
    signal feeSquare;
    signal relayerSquare;
    signal refundSquare;
    recipientSquare <== recipient * recipient;
    feeSquare <== fee * fee;
    relayerSquare <== relayer * relayer;
    refundSquare <== refund * refund;
}

The Withdraw template integrates the CommitmentHasher and MerkleTreeChecker to validate the proof and ensures tamper-proof outputs.

Key Steps:

  1. Inputs:
  • root: The Merkle root of the deposit tree.
  • nullifierHash: To prevent double-spending.
  • recipient, relayer, fee, and refund: Metadata for the transaction.
  • nullifier and secret: Private inputs proving ownership.
  • pathElements and pathIndices: Merkle proof data.
  1. Commitment Validation:
  • Compute the commitment and nullifierHash using CommitmentHasher.
  • Ensure the computed nullifierHash matches the input to prevent mismatches.
  1. Merkle Proof Verification:
  • Use MerkleTreeChecker to verify that the commitment is included in the Merkle tree defined by root.
  1. Tamper-Proofing:
  • Square the recipient, relayer, fee, and refund values to create constraints.
  • Prevents the optimizer from removing these constraints, ensuring that any tampering with outputs will invalidate the proof.

3. Main Component

component main = Withdraw(20);

The main component instantiates the Withdraw template with a Merkle tree depth of 20. This allows for up to 2^{20} leaves in the tree.

How it works

  1. Commitment and Nullifier Hash:
  • Derive the commitment and nullifierHash from the user’s nullifier and secret.
  1. Merkle Proof Validation:
  • Verify that the commitment exists in the Merkle tree with the provided root.
  1. Output Validation:
  • Ensure recipient, relayer, fee, and refund values are consistent and cannot be tampered with.

Conclusion

Congratulations! You’ve completed a hands-on implementation of zero-knowledge proofs. This process may seem complex initially, but as you create more advanced circuits, you’ll see how useful ZKPs can be for privacy-preserving computation.

We encourage you to continue your exploration of topics on zk proofs. If you’re interested in diving deeper, you can follow up on the pathway here Zero-Knowledge Proofs on the Celo Blockchain: A Comprehensive Tutorial Series - Pathways - Celo Academy

Resources

Circom docs
SnarkJS
0xparc Circom Workshop

About the author

I’m Jonathan Iheme, A full stack block-chain Developer from Nigeria. With a great passion for Zero Knowledge Technology.

linkedIn
Twitter