The new version of NiftyZK is available, v0.2.0, which contains a long awaited feature, sparse merkle trees (SMT)

$ niftyzk --version  
0.2.0

The previous implementation of Merkle Trees in NiftyZk were fixed merkle trees which can be used with commit-reveals and EdDSA schemes.

The fixed trees allow for inclusion proofs and are always fully populated and never contain zeroes in the leaves. The fixed tree must be computed and updated off-chain and the updated root is created with arbitrary verification methods.

$ niftyzk init 
Setting up your current directory
? What project do you want to scaffold? (Use arrow keys)
❯ 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

Sparse trees on the other hand offer inclusion/exclusion proofs and proof of insert/update/delete so they have more versatile use-cases and allow fine grained verification.

Sparse merkle trees are like normal merkle trees except that the contained data is indexed and the tree functions as a verifiable key value store.

Sparse Merkle Trees give efficient proofs of inclusion and non inclusion.
With an example use-case of blacklists and whitelists for address.

A non-inclusion proof can be used to verify that an address is not in a blacklist, or an inclusion proof can be used to verify that an address is in a whitelist.

Sparse Merkle Trees are implemented using circomlib / circomlibjs .

Serialization

One of the features that NiftyZK provides is a method of serialization for SMT.

The tree object is implemented in Javascript and doesn’t provide a serializable interface, so the solution was provided by storing and mutating the merkle tree leaves separately.

To create an SMT, first you must initialize it with a list of key and value pairs.

For an example implementation scaffold a project with an SMT and see test/input.js and lib/smt.js

Niftyz will give you an await initializeTree(leaves, tree) function that takes leaves which are an array of key-value pairs [{key,value}] and the tree is newMemEmptyTrie() from circomlibjs,

The initializeTree will insert the leaves into the tree for you in a loop.

Niftyzk will provide you with a serializeLeaves and deserializeLeaves functions

Mutating the tree

Here comes the important part, usually you mutate the tree inside the SMT object and then create a proof using the SMT object directly but it doesn’t allow you to serialize/deserialize from it directly, so a mutateTree function was implemented which wraps the insert/update/delete to return serializableLeaves after each action.

To update into a tree: {serializableLeaves, updateResult} = await mutateTree(“insert”,key,value,serializableLeaves,smt);

The first argument is insert | update | delete ,the next is the key and value that will be inserted, updated or deleted. The serializableLeaves are the list of key-value pairs we had earlier and the smt is the newMemEmptyTrie we initialized.

The function will return new serializableLeaves and the updateResult is the direct result from mutating the tree, used for creating the circom inputs later.

Circuits

The provided circuits come with an EdDSA verification scheme and the SMT verification.

if you select a Sparse Merkle Tree with EdDSA, inclusion/exclusion proofs

pragma circom 2.0.0;

include "../node_modules/circomlib/circuits/eddsaposeidon.circom";
include "../node_modules/circomlib/circuits/poseidon.circom";
include "../node_modules/circomlib/circuits/smt/smtverifier.circom";


template VerifySMTAndSignature(levels){

    signal input message;

    signal input value;
    signal input root;
    signal input siblings[levels];
    signal input oldKey;
    signal input oldValue;
    signal input fnc;
    signal input isOld0;

    //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;
    
    
   component pubKeyHasher = Poseidon(2);
   pubKeyHasher.inputs[0] <== Ax;
   pubKeyHasher.inputs[1] <== Ay;
            
    component smt = SMTVerifier(levels);
    poseidon.out === value;
    //Checking is enabled
    smt.enabled <== 1;
    //Inclusion or exclusion. Its a public input
    smt.fnc <== fnc;
    smt.root <== root;
    smt.oldKey <== oldKey;
    smt.oldValue <== oldValue;
    smt.isOld0 <== isOld0;
    smt.key <== pubKeyHasher.out;
    smt.value <== value;

    for(var i = 0; i< levels; i++){
      smt.siblings[i] <== siblings[i];
    }
    }    
component main {public [message,root, fnc, value]}  = VerifySignature(10); 

So let me explain it from top down

message signal is the signed message.

value the value signal is the value inserted into the SMT. The value in this circuit is the hash of the message which is later asserted.

root is the smt merkle root where we want to verify inclusion/exclusion

siblings are the merkle proof, the levels variable is the merkle tree levels, which is always the same as the merkle proof size.

oldKey newKey, isOld0 are hard coded 0 for inclusion test and then for exclusion tests they are created using variables returned from tree.find you can see the exact values needed in test/input.js

fnc is the functionality, 0 for inclusion and 1 for exclusion tests

Ax,Ay, S,R8x, R8y these are the EdDSA signature inputs, the circuit uses the EdDSA poseidon verifier.

Poseidon hash is used to compute the message’s hash that is signed. This message signature is asserted to be the value that is checked for inclusion/exclusion inside the tree.

The signature is verified and then the SMT verifier is used for the tree verification.

The public inputs are message, root,fnc,value and these are the inputs exposed to the public in a smart contract. You can chose to hard code the fnc if you only want to test for 1 thing with your circuit.

Insert/Update/Delete

You can mutate the merkle tree on-chain by providing a proof of update. These actions are preformed by a different circuit than the inclusion/exclusion proofs, so you will need to set up 2 projects

Select ❯ Sparse Merkle Tree with EdDSA, insert/update/delete to scaffold the project. The circuit will use an smtprocessor instead of the smtverifier that was used for the inclusion/exclusion proofs.
Some key differences will the the public inputs that it has newKey and newValue signals an a newRoot output signal. Otherwise the circuit is very similar to the above explained one.
The fnc is an array, so to insert it’s [1,0] to update it’s [0,1] and to delete it’s [1,1] . See the /test/input.js for the examples.

And that’s it for now. Go ahead and try it.
you can install the cli from git and specifically target the v0.2.0 branch to get this version:npm install -g git+https://github.com/NiftyZk/niftyzk.git#v0.2.0