Incremental Merkle Tree Semaphore v4

An Incrememental Merkle Tree (IMT) is a Merkle Tree (MT) designed to be updated efficiently.

The Incremental Merkle Tree in Semaphore v4 (called LeanIMT) is a Binary Tree, a tree in which every node has at most two children.

LeanIMT Implementation

Typescript: https://github.com/privacy-scaling-explorations/zk-kit/tree/main/packages/imt/src/lean-imt

Solidity: https://github.com/privacy-scaling-explorations/zk-kit/blob/main/packages/imt.sol/contracts/LeanIMT.sol

LeanIMT Algorithms

Notation:

leaves would be l_0, l_1, …, l_n from left to the right being n the total number of leaves.

The IMT can start empty or with some values.

The leaves are nodes too.

In the above image, l_0 is a left node, l_1 is a right node, l_2 is a left node, etc.

Insert

There are two cases:

1. When the new node is a left node
2. When the new node is a right node

We will always see one of these cases in each level when we are inserting a node. It is like, when you insert a node, if that node is left node, the parent node which is in the next level, will be the same node. If it is a right node the parent node, will be the hash of this node with the node in its left. This algorithm will be the same in each level, not only in level 0.

Case 1: The new node is a left node

It will not be hashed, it will be sent to the next level itself.

If we add l_4.

Case 2: The new node is a right node

If we add l_5

Insert many (batch insertion)

Using the first IMT, let's insert l_4 and l_5 with the insert many function to see the difference.

The idea of inserting many members at the same time and not insert one, then the other, etc. in a loop is that there are less hashing, so it is faster and more optimized.

Update

Update all the parent nodes.

Update when there is no right sibling

Update l_4 for l_5

Update when there is right sibling

Update l_2 for l_5

Delete

The delete function is the same as the update function but the value used to update is 0.

Delete l_2