LeanIMTData

struct LeanIMTData {
  uint256 size;
  uint256 depth;
  mapping(uint256 => uint256) sideNodes;
  mapping(uint256 => uint256) leaves;
}

WrongSiblingNodes

error WrongSiblingNodes()

LeafGreaterThanSnarkScalarField

error LeafGreaterThanSnarkScalarField()

LeafCannotBeZero

error LeafCannotBeZero()

LeafAlreadyExists

error LeafAlreadyExists()

LeafDoesNotExist

error LeafDoesNotExist()

InternalLeanIMT

The LeanIMT is an optimized version of the BinaryIMT. This implementation eliminates the use of zeroes, and make the tree depth dynamic. When a node doesn't have the right child, instead of using a zero hash as in the BinaryIMT, 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 leaves in the tree. This approach results in the calculation of significantly fewer hashes, making the tree more efficient.

SNARK_SCALAR_FIELD

uint256 SNARK_SCALAR_FIELD

The scalar field

_insert

function _insert(struct LeanIMTData self, uint256 leaf) internal returns (uint256)

Inserts a new leaf into the incremental merkle tree. The function ensures that the leaf is valid according to the constraints of the tree and then updates the tree's structure accordingly.

Parameters

Name	Type	Description
self	struct LeanIMTData
leaf	uint256

Return Values

Name	Type	Description
[0]	uint256	The new hash of the node after the leaf has been inserted.

_insertMany

function _insertMany(struct LeanIMTData self, uint256[] leaves) internal returns (uint256)

Inserts many leaves into the incremental merkle tree. The function ensures that the leaves are valid according to the constraints of the tree and then updates the tree's structure accordingly.

Parameters

Name	Type	Description
self	struct LeanIMTData
leaves	uint256[]

Return Values

Name	Type	Description
[0]	uint256	The root after the leaves have been inserted.

_update

function _update(struct LeanIMTData self, uint256 oldLeaf, uint256 newLeaf, uint256[] siblingNodes) internal returns (uint256)

Updates the value of an existing leaf and recalculates hashes to maintain tree integrity.

Parameters

Name	Type	Description
self	struct LeanIMTData
oldLeaf	uint256
newLeaf	uint256
siblingNodes	uint256[]

Return Values

Name	Type	Description
[0]	uint256	The new hash of the updated node after the leaf has been updated.

_remove

function _remove(struct LeanIMTData self, uint256 oldLeaf, uint256[] siblingNodes) internal returns (uint256)

Removes a leaf from the tree by setting its value to zero. This function utilizes the update function to set the leaf's value to zero and update the tree's state accordingly.

Parameters

Name	Type	Description
self	struct LeanIMTData
oldLeaf	uint256
siblingNodes	uint256[]

Return Values

Name	Type	Description
[0]	uint256	The new root hash of the tree after the leaf has been removed.

_has

function _has(struct LeanIMTData self, uint256 leaf) internal view returns (bool)

Checks if a leaf exists in the tree.

Parameters

Name	Type	Description
self	struct LeanIMTData
leaf	uint256

Return Values

Name	Type	Description
[0]	bool	A boolean value indicating whether the leaf exists in the tree.

_indexOf

function _indexOf(struct LeanIMTData self, uint256 leaf) internal view returns (uint256)

Retrieves the index of a given leaf in the tree.

Parameters

Name	Type	Description
self	struct LeanIMTData
leaf	uint256

Return Values

Name	Type	Description
[0]	uint256	The index of the specified leaf within the tree. If the leaf is not present, the function reverts with a custom error.

_root

function _root(struct LeanIMTData self) internal view returns (uint256)

Retrieves the root of the tree from the 'sideNodes' mapping using the current tree depth.

Parameters

Name	Type	Description
self	struct LeanIMTData

Return Values

Name	Type	Description
[0]	uint256	The root hash of the tree.