scalus.crypto.tree

Frontier-based append-only Merkle tree.

Stores only D sibling hashes (the "frontier") instead of the full tree, giving O(D) memory regardless of how many elements have been inserted. Supports depths up to 256, enabling trees with up to 2^256 leaf slots.

Produces identical root hashes and append proofs as IncrementalMerkleTree for the same key sequence. On-chain IncrementalMerkleTree.append() and verifyMembership() work unchanged with proofs from this tree.

Membership proofs require an external element source — see proveMembership.

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.

Off-chain static Merkle tree.

Built once from a known set of elements. Supports membership proofs but no insert/delete/append. Uses a heap-indexed array of hashes: index 1 = root, 2i/2i+1 = children of node i.

Leaf hashing: blake2b_256(element). Empty leaf: blake2b_256(ByteString.empty).

Cache for intermediate subtree hashes, used by FrontierMerkleTree.proveMembership.

Reuse a single cache across multiple proveMembership calls: the first call is O(N) (computes all subtree hashes), subsequent calls are O(D) (cache hits for shared subtrees).