Class LeanIMT<N>

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.

Type Parameters

  • N = bigint

Constructors

  • It initializes the tree with a given hash function and an optional list of leaves.

    Type Parameters

    • N = bigint

    Parameters

    Returns LeanIMT<N>

Properties

The hash function used to compute the tree nodes.

_nodes: N[][]

The 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.

Accessors

  • get depth(): number
  • The depth of the tree, which equals the number of levels - 1.

    Returns number

    The depth of the tree.

  • get leaves(): N[]
  • 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.

    Returns N[]

    The list of tree leaves.

  • get root(): N
  • 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.

    Returns N

    The root hash of the tree.

  • get size(): number
  • The size of the tree, which the number of its leaves. It's the length of the first level's list.

    Returns number

    The number of leaves of the tree.

Methods

  • It enables the conversion of the full tree structure into a JSON string, facilitating future imports of the tree. This approach is beneficial for large trees, as it saves time by storing hashes instead of recomputing them

    Returns string

    The stringified JSON of the tree.

  • It returns true if the leaf exists, and false otherwise

    Parameters

    • leaf: N

      A leaf of the tree.

    Returns boolean

    True if the tree has the leaf, and false otherwise.

  • It 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. The tree must be empty before importing.

    Parameters

    • nodes: string

      The stringified JSON of the tree.

    Returns void

  • It returns the index of a leaf. If the leaf does not exist it returns -1.

    Parameters

    • leaf: N

      A leaf of the tree.

    Returns number

    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.

    Parameters

    • leaf: N

      The new leaf to be inserted in the tree.

    Returns void

  • 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.

    Parameters

    • leaves: N[]

      The list of leaves to be inserted.

    Returns void

  • It updates a leaf in the tree. It's very similar to the LeanIMT#insert function.

    Parameters

    • index: number

      The index of the leaf to be updated.

    • newLeaf: N

      The new leaf to be inserted.

    Returns void

  • 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).

    Parameters

    Returns boolean

    True if the leaf is part of the tree, and false otherwise.

Generated using TypeDoc