One of the important use-cases of Zero-knowledge proofs is privacy focused applications where the identity of the user must remain hidden but verifiable.

There are many schemes, I would like to show a Group signature scheme with merkle tree.

Group Signatures schemes are signature verification schemes where the identity of the signer stays hidden but it’s verifiable to be originating from a group.

The group size is the Anonymity set which determines how private the scheme is. A group of 4 would have the Anonymity set of 4 and a signature would have to originate from 1 of the 4 members to be valid.

I will build a scheme for group signatures, with NiftyZK, that uses merkle tree for group inclusion proof while hiding the signer of the message.

The anonymity set of merkle tree based group signatures can grow arbitrarily large, in case of our circuit it’s going to have the possible max anonymity set of 1048576, which is all the addresses that can fit into a merkle tree with 20 levels, however the actual anonymity set will depend on the signed up users

So let’s scaffold an application

? What project do you want to scaffold?
  Commit-Reveal Scheme
  Commit-Reveal Scheme with Fixed Merkle Tree
  EdDSA signature verification
❯ EdDSA signature verification with Fixed Merkle Tree
  Sparse Merkle Tree with EdDSA, inclusion/exclusion proofs
  Sparse Merkle Tree with EdDSA, insert/update/delete

Select EdDSA signature verification with Fixed Merkle Tree and Poseidon Hash and we are not adding more public inputs via the cli.

The scaffolded project will be very close to the final required scheme and we won’t be coding much.

here is the scaffolded circuit:

pragma circom 2.0.0;

include "../node_modules/circomlib/circuits/eddsaposeidon.circom";
include "../node_modules/circomlib/circuits/poseidon.circom";
include "./merkletree.circom";


template VerifySignature(levels){

    signal input message;
    signal input root;
    signal input pathIndices[levels];
    signal input pathElements[levels];

    //The parameters for the signature
    //The Ax and Ay parameters are the public key, Ax = pubKey[0], Ay = pubKey[1]
    signal input Ax;
    signal input Ay;
    signal input S;
    signal input R8x;
    signal input R8y;
    component eddsa = EdDSAPoseidonVerifier();
    
    component poseidon = Poseidon(1);
    poseidon.inputs[0] <== message;

    
    // Verify the signature on the message hash
    
    eddsa.enabled <== 1;
    eddsa.Ax <== Ax;
    eddsa.Ay <== Ay;
    eddsa.S <== S;
    eddsa.R8x <== R8x;
    eddsa.R8y <== R8y;
    eddsa.M <== poseidon.out;
    
    //We compute a public key by hashing Ax and Ay, 
   // this will be later used with the merkle tree
   component pubKeyHasher = Poseidon(2);
   pubKeyHasher.inputs[0] <== Ax;
   pubKeyHasher.inputs[1] <== Ay;

   //Verify the merkle tree
   component tree = MerkleTreeChecker(levels);


   for (var i = 0; i < levels; i++) {
      tree.pathElements[i] <== pathElements[i];
      tree.pathIndices[i] <== pathIndices[i];
   }
   tree.root <== root;
   tree.leaf <== pubKeyHasher.out; 
}    

component main {public [message,root]}  = VerifySignature(20); 

The circuit is pretty simple, so it will take 2 public inputs a message and a root and the private inputs are pathIndices, pathElements which are the merkle proof of size levels

How does this anonymize users?

Here is a scenario:

• Users of a smart contract implementing the verifier sign up off-chain by generating an EdDSA private and public key pair.

• The merkle root is updated to contain the address derived from the public key, which is a poseidon hash of the public key

• After this, any participant in the group can sign a message and verify that the signer is in the merkle tree, without revealing which signer created the signature.

• The anonymity can be further strengthened on a blockchain by using a relayer which can trustlessly submit the zk proof on behalf of anyone, because if it’s altered it’s invalidated.

  Use this scheme to build Private DAO, Confidential Voting or Private Financial Transactions where the group members can transfer value to each other without revealing their identity.

  Try it out for your project!

One of the important use-cases of Zero-knowledge proofs is privacy focused applications where the identity of the user must remain hidden but verifiable.

There are many schemes, I would like to show a Group signature scheme with merkle tree.

Group Signatures schemes are signature verification schemes where the identity of the signer stays hidden but it’s verifiable to be originating from a group.

The group size is the Anonymity set which determines how private the scheme is. A group of 4 would have the Anonymity set of 4 and a signature would have to originate from 1 of the 4 members to be valid.

I will build a scheme for group signatures, with NiftyZK, that uses merkle tree for group inclusion proof while hiding the signer of the message.

The anonymity set of merkle tree based group signatures can grow arbitrarily large, in case of our circuit it’s going to have the possible max anonymity set of 1048576, which is all the addresses that can fit into a merkle tree with 20 levels, however the actual anonymity set will depend on the signed up users

So let’s scaffold an application

? What project do you want to scaffold?
  Commit-Reveal Scheme
  Commit-Reveal Scheme with Fixed Merkle Tree
  EdDSA signature verification
❯ EdDSA signature verification with Fixed Merkle Tree
  Sparse Merkle Tree with EdDSA, inclusion/exclusion proofs
  Sparse Merkle Tree with EdDSA, insert/update/delete

Select EdDSA signature verification with Fixed Merkle Tree and Poseidon Hash and we are not adding more public inputs via the cli.

The scaffolded project will be very close to the final required scheme and we won’t be coding much.

here is the scaffolded circuit:

pragma circom 2.0.0;

include "../node_modules/circomlib/circuits/eddsaposeidon.circom";
include "../node_modules/circomlib/circuits/poseidon.circom";
include "./merkletree.circom";


template VerifySignature(levels){

    signal input message;
    signal input root;
    signal input pathIndices[levels];
    signal input pathElements[levels];

    //The parameters for the signature
    //The Ax and Ay parameters are the public key, Ax = pubKey[0], Ay = pubKey[1]
    signal input Ax;
    signal input Ay;
    signal input S;
    signal input R8x;
    signal input R8y;
    component eddsa = EdDSAPoseidonVerifier();
    
    component poseidon = Poseidon(1);
    poseidon.inputs[0] <== message;

    
    // Verify the signature on the message hash
    
    eddsa.enabled <== 1;
    eddsa.Ax <== Ax;
    eddsa.Ay <== Ay;
    eddsa.S <== S;
    eddsa.R8x <== R8x;
    eddsa.R8y <== R8y;
    eddsa.M <== poseidon.out;
    
    //We compute a public key by hashing Ax and Ay, 
   // this will be later used with the merkle tree
   component pubKeyHasher = Poseidon(2);
   pubKeyHasher.inputs[0] <== Ax;
   pubKeyHasher.inputs[1] <== Ay;

   //Verify the merkle tree
   component tree = MerkleTreeChecker(levels);


   for (var i = 0; i < levels; i++) {
      tree.pathElements[i] <== pathElements[i];
      tree.pathIndices[i] <== pathIndices[i];
   }
   tree.root <== root;
   tree.leaf <== pubKeyHasher.out; 
}    

component main {public [message,root]}  = VerifySignature(20); 

The circuit is pretty simple, so it will take 2 public inputs a message and a root and the private inputs are pathIndices, pathElements which are the merkle proof of size levels

How does this anonymize users?

Here is a scenario:

• Users of a smart contract implementing the verifier sign up off-chain by generating an EdDSA private and public key pair.

• The merkle root is updated to contain the address derived from the public key, which is a poseidon hash of the public key

• After this, any participant in the group can sign a message and verify that the signer is in the merkle tree, without revealing which signer created the signature.

• The anonymity can be further strengthened on a blockchain by using a relayer which can trustlessly submit the zk proof on behalf of anyone, because if it’s altered it’s invalidated.

  Use this scheme to build Private DAO, Confidential Voting or Private Financial Transactions where the group members can transfer value to each other without revealing their identity.

  Try it out for your project!