Merkle

Merkle: content-addressed hash tree.

Each leaf stores a value and the SHA-256 hash of its byte representation. Each branch stores the SHA-256 hash of (left_hash ++ right_hash). The root hash summarises the entire tree; comparing root hashes detects any difference in O(1), while diff() localises changes in O(k log n) by recursing only into subtrees whose hashes differ.

build/3 constructs a balanced tree from a list of items in O(n). The caller supplies a to_bytes : a -> String function for leaf hashing.

Types

typeMerkleTreeMerkleTree(a) = MLeaf(String, a) | MBranch(String, MerkleTree(a), MerkleTree(a))#

Functions

fnbranchbranch(l : MerkleTree(a), r : MerkleTree(a)) : MerkleTree(a)#

Construct a branch, hashing the concatenation of the children's root hashes.

fnbuildbuild(items : List(a), to_bytes : a -> String) : Option(MerkleTree(a))#

Build a balanced Merkle tree from a non-empty list. Returns None for an empty list.

fncontains_hashcontains_hash(t : MerkleTree(a), h : String) : Bool#

True when the tree contains a leaf whose hash equals h.

fndiffdiff(t1 : MerkleTree(a), t2 : MerkleTree(a)) : List(String)#

Return the leaf hashes that differ between two trees with the same structure.

fnleafleaf(x : a, to_bytes : a -> String) : MerkleTree(a)#

Construct a leaf, hashing the value with to_bytes.

fnleaf_hashesleaf_hashes(t : MerkleTree(a)) : List(String)#

Collect all leaf hashes, left to right.

fnleavesleaves(t : MerkleTree(a)) : List(a)#

Collect all values stored at the leaves, left to right.

fnroot_hashroot_hash(t : MerkleTree(a)) : String#

Return the hash stored at the root of the tree.

fnsizesize(t : MerkleTree(a)) : Int#

Number of leaves in the tree.