IncrementalMerkleTree

scalus.crypto.tree.IncrementalMerkleTree

See theIncrementalMerkleTree companion object

Off-chain incremental Merkle tree.

Fixed-depth binary Merkle tree backed by a persistent (structurally-shared) tree.

append replaces one leaf and rebuilds O(depth) nodes on the path — everything else is shared with the previous version.
rootHash is O(1) — just the root node's hash.
proveMembership / proveAppend walk root→leaf collecting siblings — O(depth).
Empty subtrees are shared: an empty tree of depth 20 uses only 21 node objects.

Attributes

Append a new key to the next available slot.

Number of leaf slots (2^depth).

Check if a key is in the tree.

Generate an append proof for the next empty slot.

Returns siblings (D * 32 bytes) for slot size.

Generate a membership proof for a key.

Returns D * 33 bytes: D repetitions of (direction[1] + sibling[32]). direction is 0 (left child) or 1 (right child).

Current root hash.

In this article

Generated with