# 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

<!-- ## IMT Data Structure Javascript

The IMT is a class with two private values: `_nodes` and `_hash` and a set of functions.

- The `_nodes` value is a list of lists to store the IMT
- The `_hash` value is the hash function that will be used for the IMT

The type `Node` represents a node value in the tree:

export type Node = number | string | bigint

-->
## 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`