GroupSignMerkle.md

Open this in zkREPL →

This file can be included into other zkREPLs with include "gist:fc9c9e31483a83d585de19604c5b5056";

merkleproof.circom

pragma circom 2.1.4;

include "circomlib/circuits/poseidon.circom";
include "circomlib/circuits/mux1.circom";
include "circomlib/circuits/comparators.circom";

template Secret2Public () {
    signal input sk;
    signal output pk;
    
    component poseidon = Poseidon(1); // the input of poseidon hash is the number of variables you want to hash, normally one or two
    poseidon.inputs[0] <== sk;
    pk <== poseidon.out;
    log("pk:", pk);
}

template Sign(){
    signal input m;
    signal input sk; // private
    signal output pk;

    component checker = Secret2Public();
    checker.sk <== sk;
    pk <== checker.pk;
}

template GroupSign(n){
    signal input m;
    signal input sk; // private
    signal input pk[n];
    
    component checker = Secret2Public();
    checker.sk <== sk;

    signal zeroChecker[n+1];
    zeroChecker[0] <== 1;
    for(var i = 0; i < n; i++){
        // the following line is not work because cirom cannot multiple more than 2-order to one variable
        // and the self multiple is not allowed,too
        // zeroChecker <== zeroChecker * (pk[i] - checker.pk);
        zeroChecker[i+1] <== zeroChecker[i] * (pk[i] - checker.pk);
    }
    zeroChecker[n] === 0;
}

template PoseidonComputer(){
    signal input left;
    signal input right;
    component poseidons = Poseidon(2);
    poseidons.inputs[0] <== left;
    poseidons.inputs[1] <== right;
    log("out", poseidons.out);
}

template MerkleTreeMembership(nLevels){
    signal input sk; // private
    signal input pathIndices[nLevels];
    signal input siblings[nLevels];
    signal input root; // public input

    // check that we know the secret key corresponding to the public key
    component checker = Secret2Public();
    checker.sk <== sk;

    component poseidons[nLevels];
    component mux[nLevels];

    signal intermediatHashes[nLevels+1];
    intermediatHashes[0] <== checker.pk;

    for(var i = 0; i < nLevels; i++){
        pathIndices[i] * (1 - pathIndices[i]) === 0;

        // the poseidon hash component cannot be reused
        //because the wire is fixed one the has is done.
        poseidons[i] = Poseidon(2);
        mux[i] = MultiMux1(2);

        // select the scenario of hash is left leaf or right leaf node through selector
        mux[i].c[0][0] <== intermediatHashes[i];
        mux[i].c[0][1] <== siblings[i];

        mux[i].c[1][0] <== siblings[i];
        mux[i].c[1][1] <== intermediatHashes[i];

        mux[i].s <== pathIndices[i];

        poseidons[i].inputs[0] <== mux[i].out[0];
        poseidons[i].inputs[1] <== mux[i].out[1];

        intermediatHashes[i+1] <== poseidons[i].out;
    }

    // root <== hashes[nLevels];
    // check if the root is equal to the computed results
    component rootChecker = IsEqual();
    rootChecker.in[0] <== intermediatHashes[nLevels];
    rootChecker.in[1] <== root;
    rootChecker.out === 1;
}

component main {public [root]}= MerkleTreeMembership(2);
// component main = PoseidonComputer();
/* nLevels = 3
        -
    -        -
-      *   -    -
*/
/* INPUT = {
    "sk": "5",
    "root": "11430533323050598331064087431769380666823219951566281601915492140621000439116",
    "pathIndices": ["1","0"],
    "siblings": ["1","2"]
} */