It initializes the tree with an hash function, the depth, the zero value to use for zeroes and the arity (i.e. the number of children for each node). It also takes an optional parameter to initialize the tree with a list of leaves.
The hash function used to create nodes.
The tree depth.
The zero value used to create zeroes.
The number of children for each node.
The list of initial leaves.
Private Readonly _arityThe number of children per node.
Private Readonly _depthThe depth of the tree, which is the number of edges from the node to the tree's root node.
Private Readonly _hashThe hash function used to compute the tree nodes.
Private Readonly _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.
Private Readonly _zeroesA list of zero values calculated during the initialization of the tree. The list contains one value for each level of the tree, and the value for a given level is equal to the hash of the previous level's value. The first value is the zero hash provided by the user. These values are used to calculate the hash of a node in case some of its children are missing.
The number of children per node.
The number of children per node.
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 IMT#_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 IMT#_nodes.
The root hash of the tree.
The list of zero values calculated during the initialization of the tree.
The list of pre-computed zeroes.
It creates a IMTMerkleProof 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.
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 is the hash of that node and the zero value of that level. Otherwise, the hash of the children is calculated.
The new leaf to be inserted in the tree.
It updates a leaf in the tree. It's very similar to the IMT#insert function.
The index of the leaf to be updated.
The new leaf to be inserted.
It verifies a IMTMerkleProof to confirm that a leaf indeed
belongs to a tree. Does not verify that the node belongs to this
tree in particular. Equivalent to IMT.verifyProof(proof, this._hash).
The Merkle tree proof.
True if the leaf is part of the tree, and false otherwise.
Static verifyIt verifies a IMTMerkleProof to confirm that a leaf indeed belongs to a tree.
The Merkle tree proof.
The hash function used to compute the tree nodes.
True if the leaf is part of the tree, and false otherwise.
An IMT (aka Incremental Merkle Tree) is a type of data structure used in cryptography and computer science for efficiently verifying the integrity of a large set of data, especially in situations where new data is added over time. It is based on the concept of a Merkle tree, and its key feature is its ability to efficiently update the tree when new data is added or existing data is modified. In this implementation, the tree is constructed using a fixed IMT#depth value, and a list of IMT#zeroes (one for each level) is used to compute the hash of a node when not all of its children are defined. The number of children for each node can also be specified with the IMT#arity parameter.