Module @zk-kit/lean-imt

Lean Incremental Merkle Tree

Lean Incremental Merkle tree implementation in TypeScript.

NPM license NPM version Downloads npm bundle size (scoped) Linter eslint Code style prettier

🗣️ Chat & Support   |   📘 Docs

This library has been audited as part of the Semaphore V4 PSE audit:

The LeanIMT is an optimized binary version of the IMT into binary-focused model, eliminating the need for zero values and allowing dynamic depth adjustment. Unlike the IMT, which uses a zero hash for incomplete nodes, the LeanIMT directly adopts the left child's value when a node lacks a right counterpart. The tree's depth dynamically adjusts to the count of leaves, enhancing efficiency by reducing the number of required hash calculations. To understand more about the LeanIMT, take a look at this visual explanation. For detailed insights into the implementation specifics, please refer to the technical documentation.

🛠 Install

npm or yarn

Install the @zk-kit/lean-imt package with npm:

npm i @zk-kit/lean-imt --save

or yarn:

yarn add @zk-kit/lean-imt


You can also load it using a script tag using unpkg:

<script src=""></script>

or JSDelivr:

<script src=""></script>

📜 Usage

import { LeanIMT } from "@zk-kit/lean-imt"
import { poseidon2 } from "poseidon-lite"

* Hash function used to compute the tree nodes.
const hash = (a, b) => poseidon2([a, b])

// To create an instance of a LeanIMT, you must provide the hash function.
const tree = new LeanIMT(hash)

// You can also initialize a tree with a given list of leaves.
// const leaves = [1n, 2n, 3n]
// new LeanIMT(hash, leaves)

// LeanIMT is strictly typed. Default type for nodes is 'bigint',
// but you can set your own type.
// new LeanIMT<number>((a, b) => a + b)

// Insert (incrementally) a leaf with a value of 1.
// [1n]

// Insert (incrementally) a leaf with a value of 3.

// 21106761926285267690763443010820487107972411248208546226053195422384279971821n
// 1
// 2
// [1n, 3n]

// Get the index of the leaf with value 3n.
const idx = tree.indexOf(3n)
// 1

// Check if the tree contains a leaf with value 4n.
const has = tree.has(4n)
// false

// Update the value of the leaf at position 1 to 2n.
tree.update(1, 2n)
// [1n, 2n]

* If you want to delete a leaf with LeanIMT you can use the update function with an
* arbitrary value to be used for the removed leaves.

// Update the value of the leaf at position 1 to 0n (deletion).
tree.update(1, 0n)
// [1n, 0n]

* Compute a Merkle Inclusion Proof (proof of membership) for the leaf with index 1.
* The proof is only valid if the value 1 is found in a leaf of the tree.
const proof = tree.generateProof(1)
// true



Type Aliases