Private Readonly _hashThe hash function used to compute the tree nodes.
Private _nodesThe matrix where all the tree nodes are stored. The first index indicates the level of the tree, while the second index represents the node's position within that specific level. The last level will always contain a list with a single element, which is the root. Most of the attributes of this class are getters which can retrieve their values from this matrix.
The depth of the tree, which equals the number of levels - 1.
The depth of the tree.
The leaves of the tree. They can be retrieved from the first level of the tree using LeanIMT#_nodes. The returned value is a copy of the array and not the original object.
The list of tree leaves.
The root of the tree. This value doesn't need to be stored as it is always the first and unique element of the last level of the tree. Its value can be retrieved in LeanIMT#_nodes.
The root hash of the tree.
The size of the tree, which the number of its leaves. It's the length of the first level's list.
The number of leaves of the tree.
It generates a LeanIMTMerkleProof for a leaf of the tree. That proof can be verified by this tree using the same hash function.
The index of the leaf for which a Merkle proof will be generated.
The Merkle proof of the leaf.
It returns true if the leaf exists, and false otherwise
A leaf of the tree.
True if the tree has the leaf, and false otherwise.
It returns the index of a leaf. If the leaf does not exist it returns -1.
A leaf of the tree.
The index of the leaf.
The leaves are inserted incrementally. If 'i' is the index of the last leaf, the new one will be inserted at position 'i + 1'. Every time a new leaf is inserted, the nodes that separate the new leaf from the root of the tree are created or updated if they already exist, from bottom to top. When a node has only one child (the left one), its value takes on the value of the child. Otherwise, the hash of the children is calculated.
The new leaf to be inserted in the tree.
This function is useful when you want to insert N leaves all at once. It is more efficient than using the LeanIMT#insert method N times because it significantly reduces the number of cases where a node has only one child, which is a common occurrence in gradual insertion.
The list of leaves to be inserted.
It updates a leaf in the tree. It's very similar to the LeanIMT#insert function.
The index of the leaf to be updated.
The new leaf to be inserted.
Updates m leaves all at once. It is more efficient than using the LeanIMT#update method m times because it prevents updating middle nodes several times. This would happen when updating leaves with common ancestors. The naive approach of calling 'update' m times has complexity O(mlog(n)) (where n is the number of leaves of the tree), which ends up in O(nlog(n)) when m ~ n. With this new approach, this ends up being O(n) because every node is updated at most once and there are around 2*n nodes in the tree.
The list of indices of the respective leaves.
The list of leaves to be updated.
It verifies a LeanIMTMerkleProof to confirm that a leaf indeed
belongs to a tree. Does not verify that the node belongs to this
tree in particular. Equivalent to
LeanIMT.verifyProof(proof, this._hash).
The Merkle tree proof.
True if the leaf is part of the tree, and false otherwise.
Static importIt imports an entire tree by initializing the nodes without calculating any hashes. Note that it is crucial to ensure the integrity of the tree before or after importing it. If the map function is not defined, node values will be converted to bigints by default.
The hash function used to create nodes.
The stringified JSON of the tree.
Optional map: ((value) => N)A function to map each node of the tree and convert their types.
A LeanIMT instance.
Static verifyIt verifies a LeanIMTMerkleProof to confirm that a leaf indeed belongs to a tree.
The Merkle tree proof.
True if the leaf is part of the tree, and false otherwise.
The LeanIMT is an optimized binary version of the IMT. This implementation exclusively supports binary trees, eliminates the use of zeroes, and the tree's LeanIMT#depth is dynamic. When a node doesn't have the right child, instead of using a zero hash as in the IMT, the node's value becomes that of its left child. Furthermore, rather than utilizing a static tree depth, it is updated based on the number of LeanIMT#leaves in the tree. This approach results in the calculation of significantly fewer hashes, making the tree more efficient.