In SnarkyJS, we currently have Poseidon and a (sparse) Merkle Tree implementation to our hands.

We would start by initialized an empty `nullifier_tree`, with all leaves being `0`.

               H(AB,CD)
        |                        |
    H(A,B)                    H(C,D)
|            |            |            |
A            B            C            D
|            |            |            |
0            0            0            0

Our nullifier algorithm could be defined as `N = H(value, secret)`, where `value` could be a coin (tornado cash) or transaction data, and the `secret` a password. For sake of simplicity `H` only returns a 2 bit value, so it fits our tree with 4 leaves.

We would prove, inside a circuit, the following:

function processTransaction(txData: Field, someSecret: Field, nullifierWitness: MerkleWitness) {
    
    let nullifier = N(txData, someSecret);
    
    // proving non inclusion 
    // the provided merkle witness needs to be the one that fits the nullifier, we can do that by calculating the index
    let i = nullifierWitness.calculateIndex();
    i.assertEquals(nullifier);
    
    // now we know that the merkle witness is valid
    // we then check if the leaf at pos i is indeed empty
    
    let calculatedRoot = nullifierWitness.calculateRoot(Field.zero);
    
    calculatedRoot.assertEquals(this.nullifierRoot.get());
        
    // if the proposed nullifier is not part of the tree, we can now add it to the tree
    
    let newRoot = nullifierWitness.calculateRoot(nullifier);
    this.nullifierRoot.set(newRoot);
}

To visualize this, we would go from an empty nullifier tree to a new one which has one nullifier added to it.

               H(AB,CD)
        |                        |
    H(A,B)                    H(C,D)
|            |            |            |
A            B            C            D
|            |            |            |
0            0            0            0

to

               H(AB,CD)
        |                        |
    H(A,B)                    H(C,D)
|            |            |            |
A            B            C            D
|            |            |            |
0            01            0            0

Assuming that we provide the merkle witness for `index = 1` and our nullifier hashes to `01`, which is supposed to be at `index = 1`