A detailed read about how we implemented non-membership proof for passports in proof of passport. The issue and code is here for reference.

We majorly discuss the verification of proof generated by zk-kit/smt on circuit. But just to brief, we hashed the passports from ofac member lists to create standard data points, from which we created a Sparse Merkle Tree, against which a user can give a non-membership proof for verification.

Before we dive into the circuit implementation, let’s look at how sparse merkle trees works -

(If you know all about smt's, click here to take you directly to the circuit.)

Sparse Merkle Trees :

Sparse Merkle Trees are basically indexed merkle trees, where each datapoint is at a specific index, decided by the bits of the data leaf in our case.

You should read this small article to get a brief understanding of Merkle trees and Sparse Merkle Trees, then come back to this.

Everything is much simpler and definite if we create a full SMT, but for cases where your data space can be anything or is a hash, we would have 2^256 leaves, not ideal.

One could write his own optimised implementation but open source is awesome..so here’s creating a SMT using zk-kit/smt through an example.

Our data points are [0,1,2,3,8], each a BigInt. The hash of leaves are taken as Hash(key, value,1). The last 1 just being there in order to differentiate between nodes and leaves. We have also taken value as 1 in this example as it’s not essential to us. All other nodes are calculated with Hash(left-child, right-child). I have calculated the actual hashes and represented the nodes in the diagram by the first 4 digits of the hashes.

This is how your tree would actually look like. You can experiment with the code given below.

import { SMT, ChildNodes } from "@zk-kit/smt"
import { poseidon2, poseidon3 } from "poseidon-lite"

const hash = (childNodes: ChildNodes) =>
    childNodes.length === 2 ? poseidon2(childNodes) : poseidon3(childNodes);  

const tree : SMT = new SMT(hash, true);

tree.add(BigInt(0), BigInt(1));
tree.add(BigInt(1), BigInt(1));
tree.add(BigInt(2), BigInt(1));
tree.add(BigInt(3), BigInt(1));
tree.add(BigInt(8), BigInt(1));

console.log(tree.createProof(BigInt(4)));
console.log(tree.createProof(BigInt(8)));
console.log(tree.createProof(BigInt(24)));

Notice how the depth is variable for different leaves, i.e not creating a full sparse merkle trees saves us a lot of space. We only keep those leafs as 0 when it is essential to maintain the integrity of the tree. This is one way of optimising smt’s. Also it’s obvious but note that 0 leaf is actually 0 and not hash of 0 leaf (will be useful later).

We are not gonna delve into the process of adding leaves and etc. We’ll focus on the process of creating and verifying a membership/non-membership proof for SMT’s. Suppose you needed to create proof for 8 in the SMT given above, here are the steps :

1. You would convert 8 to bits (i.e 1000)

2. You would reverse the bits and pads them with 0’s till the length is 256. (0001000..) This standardises the form of each number. Let’s name this function Num2Bits(256).

3. Now, we move along the tree (left if 0, right if 1) until we hit a leaf node. (A leaf node is either a zero node or has 3 siblings (key, value, 1), you can read the src code of zk-kit/smt for finer details)

4. While moving down, we capture and store the siblings at each step into a siblings array.

   Eg : For our diagram and example as 8, the path would be 0001 and the siblings array would be [8057, 4413, 0, 1105] with a depth of 4.