zk-SNARK proof of Merkle tree membership using circom

This zk-SNARK proof of Merkle tree membership using circom follows:

[1] Jose L. Muñoz-Tapia's circom tutorial 'Introducing Circom 2.0 by Iden3'

[2] Sílvia Margarit Jaile's Master Thesis 'Smart registration in Blockchain using zk-SNARKs'.

This is the attempt to use zk-SNARKs to solve the following problem:

Verifiably prove a membership to the Merkle tree of public keys, without revealing any private information.

[0] Install dependencies

yarn install

[1] Design and create the circom circuit

The Merkle tree membership proof relies on the following circom circuit scheme, as presented in [2]:

Here is the circuit code, with the instantiation of the level 3 Merkle tree verifier. There are four inputs of the main component Mkt2Verifier, and the only public one is root:

• key - the Merkle tree leaf position for the leaf we want to prove membership
• value - the private key for which we want to prove Merkle tree membership
• root - the Merkle tree root
• siblings - an array of siblings of the Merkle tree leaf we're interested in checking

pragma circom 2.0.0;

include "../../node_modules/circomlib/circuits/switcher.circom";
include "../../node_modules/circomlib/circuits/poseidon.circom";
include "../../node_modules/circomlib/circuits/bitify.circom";

template Mkt2VerifierLevel() {
    signal input sibling;
    signal input low;
    signal input selector;
    signal output root;

    component sw = Switcher();
    component hash = Poseidon(2);

    sw.sel <== selector;
    sw.L <== low;
    sw.R <== sibling;

    log(sw.outL);
    log(sw.outR);

    hash.inputs[0] <== sw.outL;
    hash.inputs[1] <== sw.outR;

    root <== hash.out;
}

template Mkt2Verifier(nLevels) {

    signal input key;
    signal input value;
    signal input root;
    signal input siblings[nLevels];

    component hashV = Poseidon(1);

    hashV.inputs[0] <== value;

    component n2b = Num2Bits(nLevels);
    component levels[nLevels];

    n2b.in <== key;

    for (var i=nLevels-1; i>=0; i--) {
        levels[i] = Mkt2VerifierLevel();
        levels[i].sibling <== siblings[i];
        levels[i].selector <== n2b.out[i];
        if (i==nLevels-1) {
            levels[i].low <== hashV.out;
        }
        else {
            levels[i].low <== levels[i+1].root;
        }
    }

    root === levels[0].root;
}

component main { public [root] } = Mkt2Verifier(3);

[3] The trusted setup

Powers of tau ceremony provides the so-called trusted setup for the generation of proving and verification keys. This part is not circuit specific and does not need to be run again if the circuits are altered. Run the setup.sh script:

yarn setup

[4] Generate proof and verification

By running the proof.sh script, we compile the circuit, generate proving and verification keys, and generate the solidity contract for on-chain proof verification. This part is circuit specific and does need to be run again if the circuits are altered:

yarn proof

[5] Local testing

For the purpose of testing, a mock Merkle tree is generated by the help of the functions in the test/utils/merkle.js file. These functions are tested in the test/1_test_merkle_js.js file, and the circuit itself in the test/2_test_merkle_circom.js:

yarn hardhat test