# 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:
```ts
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.
![IMT Semaphore v4](https://hackmd.io/_uploads/S17OnF4kT.png)
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`.
![Add left node](https://hackmd.io/_uploads/By8k3B1ep.png)
#### Case 2: The new node is a right node
If we add `l_5`
![](https://hackmd.io/_uploads/SJtnnHkep.png)
### 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.
![](https://hackmd.io/_uploads/H1FNAr1ea.png)
### Update
Update all the parent nodes.
#### Update when there is no right sibling
Update `l_4` for `l_5`
![](https://hackmd.io/_uploads/HkNTGL1g6.png)
#### Update when there is right sibling
Update `l_2` for `l_5`
![Update with right sibling](https://hackmd.io/_uploads/BJqjxUJlp.png)
### Delete
The `delete` function is the same as the `update` function but the value used to update is `0`.
Delete `l_2`
![](https://hackmd.io/_uploads/r1jiZUJgT.png)

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up