scalus.cardano.onchain.plutus.crypto.tree

Incremental Merkle tree for oracle-managed sets.

Fixed-depth D binary Merkle tree where leaves are appended sequentially. The tree is 1-indexed: tree(1) = root, tree(2^D + i) = leaf i.

Leaf i stores blake2b_256(key_i) or EmptyLeafHash if unused. EmptyLeafHash = blake2b_256(0x00..00) (hash of 32 zero bytes).

State: (root, size) where size = number of appended elements (next free slot).

Operations:

• append: oracle adds a new member (2*D + 2 blake2b, single pass)
• verifyMembership: user proves membership (D + 1 blake2b)

Membership proofs use interleaved format: D * (direction[1] + sibling[32]) = D*33 bytes. Append proofs are flat ByteStrings: D consecutive 32-byte sibling hashes.

Plain Merkle tree for static membership verification.

Built once from a known set of elements. Supports only membership proofs — no insert/delete/append. This is the cheapest on-chain option when the set is static.

Membership proofs use the same interleaved format as IMT: D * (direction[1] + sibling[32]) = D * 33 bytes. The depth is derived from the proof length, so no depth parameter is needed.

Cost: D + 1 blake2b_256 calls for depth D.