[MerkleProof Circuit] Circom and SnarkJS

Technical Tutorials
[MerkleProof Circuit] Circom and SnarkJS
none 0.0 0
1

Introduction

Zero-knowledge proofs (ZKPs) enable privacy-preserving verification of information, and Circom is a popular tool for building ZK circuits. In this tutorial, we’ll create a zk circuit, this circuit implements a Merkle Proof verification. It allows a prover to prove that a specific leaf (like a transaction or a piece of data) is part of a known Merkle tree with a specific root, without revealing the entire tree. This is a crucial component in privacy-preserving systems like blockchain, cryptocurrencies (e.g., Bitcoin, Zcash), and rollups like StarkNet, or zkSync.

Key Concepts:

Merkle Tree

  • A Merkle Tree is a binary tree where each non-leaf node is the hash of its two child nodes.
  • The Merkle Root is the hash at the top of the tree, representing the integrity of the entire tree.
  • Merkle Proof: To prove that a leaf (like a transaction) belongs to the tree, you provide the leaf and its path to the root (sibling hashes at each level) and whether it is on the left or right of its sibling.

Merkle Proof Verification

  1. Start from the leaf node.
  2. Using the provided path elements (sibling hashes) and path indices (whether the leaf is on the left or right), compute the intermediate hashes up to the root.
  3. Check if the final computed root matches the public Merkle root.
  4. If they match, the proof is valid.

ZK Concepts

  1. Prover and Verifier: The prover generates a proof that the verifier can use to confirm a statement’s validity without learning any details.
  2. Proof: A piece of cryptographic evidence that convinces the verifier.
  3. Witness: Hidden input data used to construct the proof.
  4. Circuit: A set of logical steps used to create a proof. It defines how the inputs relate to the outputs.
  5. Constraint System: Rules combining inputs using mathematical and cryptographic operations.
  6. Trusted Setup: A one-time process to generate cryptographic keys for the prover and verifier to use.

The combination of these elements allows zero-knowledge proofs to provide privacy, security, and verification without revealing sensitive information.

To learn more, read this introduction

Introduction to Zero-Knowledge Proofs

Tools and Environment Setups.

To build and run ZKPs, you’ll need the following tools installed on your system:
Note: you can use zkREPL as a faster and easier web based editor with built in circom compiler.

  1. Node.js: JavaScript runtime to run SnarkJS scripts.
  2. Rust: Used to compile Circom.
  3. Circom: A specialized programming language for ZK circuits.
  4. SnarkJS: A JavaScript library for generating and verifying ZKP proofs.

Step 1: Install Prerequisites

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

Building the Circuit

Create a file called merkleproof in the circuits/ folder.

merkleproof.circom


pragma circom 2.1.6;

include "circomlib/poseidon.circom";
// include "https://github.com/iden3/circomlib/blob/master/circuits/poseidon.circom";

template MerkleProof (n) {

    //public inputs
    signal input leaf;              // Precomputed hash of the transaction (leaf)
    signal input pathElements[n];   // Precomputed sibling hashes
    signal input pathIndices[n];    // 0 = left, 1 = right (must be Boolean)
    signal input root;              // Precomputed Merkle tree root


    signal output isValid;            // 1 if the proof is valid, 0 otherwise

     
     signal intermediateHashes[n + 1];   // Array to store intermediate hashes
     signal leftCombination[n];          // Array for left combinations
     signal rightCombination[n];         // Array for right cobinations
     signal selectedLeft[n];             // Array for selected left branch
     signal selectedRight[n];            // Array for selected right branch


     
     intermediateHashes[0] <== leaf;     // Initialize with the leaf hash


    // Compute the root based on the path provided
    for (var i = 0; i < n; i++) {
        // Ensure pathIndices[i] is Boolean
        pathIndices[i] * (1 - pathIndices[i]) === 0;

        // Compute both possible branches
        leftCombination[i] <== intermediateHashes[i] + pathElements[i]; // Left sibling
        rightCombination[i] <== pathElements[i] + intermediateHashes[i]; // Right sibling

        // Select the correct branch
        selectedLeft[i] <== leftCombination[i] * (1 - pathIndices[i]); 
        selectedRight[i] <== rightCombination[i] * pathIndices[i];

        // Update intermediate hash
        intermediateHashes[i + 1] <== selectedLeft[i] + selectedRight[i];
    }

    // Validate that the computed root matches the provided root

    signal difference;
    difference <== intermediateHashes[n] - root;
    isValid <== 1 - difference * difference; // isValid == 1 if difference == 0


}

component main = MerkleProof(3);

Code Walkthrough

Signals Declaration

// Public Inputs
signal input leaf;              // The leaf (hashed data) for which we want to prove inclusion
signal input pathElements[n];   // Array of n sibling hashes for Merkle path
signal input pathIndices[n];    // Array of n path indicators (0=left, 1=right)
signal input root;              // Public Merkle root

// Output
signal output isValid;           // 1 if the proof is valid, 0 otherwise
  • Public Inputs:
    • leaf: The Merkle tree leaf that needs to be proven.
    • pathElements[n]: The array of sibling hashes along the path from the leaf to the root.
    • pathIndices[n]: The array of path indices, where 0 means “leaf is on the left” and 1 means “leaf is on the right”.
    • root: The public Merkle tree root that we want to verify against.
  • Output:
    • isValid: A Boolean value (1 or 0) indicating whether the Merkle proof is valid.

Intermediate Hashes

signal intermediateHashes[n + 1];  // Stores hashes as we climb the Merkle tree
signal leftCombination[n];         // If the current node is on the right, we combine it to the right
signal rightCombination[n];        // If the current node is on the left, we combine it to the left
signal selectedLeft[n];            // The selected left branch
signal selectedRight[n];           // The selected right branch
  • These are internal signals used to compute intermediate hashes and track combinations at each level of the tree.
  • The array intermediateHashes stores the computed hashes at each level, starting from the leaf and moving upward to the root.
  • The leftCombination and rightCombination compute potential hashes for the two possible cases (leaf on left or right).
  • selectedLeft and selectedRight ensure only one of them is selected depending on the path index (0 for left, 1 for right).

Core Logic

intermediateHashes[0] <== leaf;  // Start with the leaf
  • This initializes the first hash as the leaf itself.

Merkle Proof Computation

for (var i = 0; i < n; i++) {
    pathIndices[i] * (1 - pathIndices[i]) === 0;  // Ensure pathIndices are Boolean

    // Compute possible branches
    leftCombination[i] <== intermediateHashes[i] + pathElements[i];  // If the current node is on the right
    rightCombination[i] <== pathElements[i] + intermediateHashes[i]; // If the current node is on the left

    // Select which one to use
    selectedLeft[i] <== leftCombination[i] * (1 - pathIndices[i]);  // Use left if pathIndices[i] is 0
    selectedRight[i] <== rightCombination[i] * pathIndices[i];      // Use right if pathIndices[i] is 1

    // Update intermediate hash
    intermediateHashes[i + 1] <== selectedLeft[i] + selectedRight[i];
}
  • For each level i of the Merkle tree:
    • Boolean Check: Ensure pathIndices[i] is either 0 or 1.
    • Hash Combination:
      • If the current node is on the left (pathIndices[i] = 0), it computes:
leftCombination = intermediateHashes[i] + pathElements[i]
  • If the current node is on the right (pathIndices[i] = 1), it computes:
rightCombination = pathElements[i] + intermediateHashes[i]
  • Branch Selection:
    • If pathIndices[i] = 0, select left branch.
    • If pathIndices[i] = 1, select right branch.
  • Hash Update:
    • The new intermediate hash is computed by selecting the appropriate branch.
    • This process repeats for n layers, starting from the leaf and moving upward.

Final Verification

signal difference;
difference <== intermediateHashes[n] - root;
isValid <== 1 - difference * difference;  // isValid = 1 if difference = 0
  • Once the final intermediate hash is computed (which should be the Merkle root), it is compared to the public input root.
  • If difference == 0, then the proof is valid.
isValid = 1 - (difference * difference)

If difference == 0, then isValid = 1. If difference != 0, then isValid = 0.

How it Works (Example)

  1. Merkle Tree (3 levels):
          Root
         /    \
     H1       H2
    /  \     /  \
  L1   L2  L3   L4
  1. Prover’s Goal:
  • Prove that L2 belongs to the Merkle tree.
  • Provide:
    • Leaf = L2
    • Path Elements = [L1, H2] (L1 is L2’s sibling, and H2 is the sibling of H1)
    • Path Indices = [1, 0] (L2 is on the right, and H1 is on the left)
    • Root = Public Merkle root
  1. Computation:
  • Combine L2 with L1 to get H1.
  • Combine H1 with H2 to get the Root.
  • Check if computed Root matches the public root.

Compiling the Circuit

Run the following command to compile the circuit:

circom circuits/merkleproof.circom --r1cs --wasm --sym -o output/

Let’s look at each file:

  • –r1cs: Generates the Rank 1 Constraint System (R1CS) file.

  • –wasm: Outputs a WebAssembly file for computation.

  • –sym: Outputs a symbol file for debugging.

  • -o output/: Specifies the output directory.

Check for the following files in output/:

  • merkleproof.r1cs: The constraint system file.

  • merkleproof.wasm: The WebAssembly file.

  • merkleproof.sym: The symbol file for debugging.

Generating Trusted Setup

Generate the keys for the prover and verifier:

wget https://hermez.s3-eu-west-1.amazonaws.com/powersOfTau28_hez_final_10.ptau -O outputs/pot10.ptau

snarkjs groth16 setup outputs/merkleproof.r1cs outputs/pot10.ptau outputs/merkleproof_final.zkey

Export the Verification Key

snarkjs zkey export verificationkey outputs/merkleproof_final.zkey outputs/verification_key.json

Creating Inputs

Create an input file input/input.json with the following content:

{
 "leaf": "123456789",
"pathElements": [
"987654321"
"484848484"
"894934934"
],
"pathIndices": [0, 1, 0],
"root": "1023456342"
}

These Inputs will be used to generate the proof.

Generating the Proof

  1. Generate Witness

node outputs/merkleproof_js/generate_witness.js outputs/merkleproof_js/merkleproof.wasm inputs/input.json outputs/witness.wtns

  1. Generate the Proof

snarkjs groth16 prove outputs/merkleproof_final.zkey outputs/witness.wtns outputs/proof.json outputs/public.json

  1. Verify the Proof

snarkjs groth16 verify outputs/verification_key.json outputs/public.json outputs/proof.json

If everything is setup correctly, you should see:

snarkJS: OK!

Summary

  1. Design the Circuit: Create the logic of the proof in a Circom file.

  2. Compile the Circuit: Convert the logic to constraint systems and WebAssembly files.

  3. Generate Trusted Setup: Produce keys for the prover and verifier.

  4. Input Data: Provide the inputs for the computation.

  5. Generate Witness: Produce intermediate computation results.

  6. Generate Proof: Create a proof from the witness.

  7. Verify Proof: Use the verifier to check the proof’s validity.

Use Cases

  • Blockchain/DeFi:
    • Prove a transaction exists in a Merkle tree of transactions (like in Ethereum).
  • ZK-Rollups:
    • Prove that a specific leaf (a user’s balance) is part of the rollup Merkle tree.
  • Private Voting:
    • Prove that a user’s vote is included in a larger list of votes.

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
Youtube Resource

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