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/2 constructs a balanced tree from a list of items in O(n). The caller supplies a to_bytes : a -> String function for leaf hashing. Hashes are lowercase hex SHA-256 strings (Crypto.sha256).

Types

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

A node: MLeaf(sha256_hex, value) or MBranch(sha256_hex, left, right).

Functions

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

A branch over l and r, whose hash is the SHA-256 of the two children's root hashes concatenated (left first, as hex strings).

Examples

march> Merkle.size(Merkle.branch(Merkle.leaf(1, int_to_string), Merkle.leaf(2, int_to_string)))
2
march> Merkle.root_hash(Merkle.branch(Merkle.leaf("a", fn s -> s), Merkle.leaf("b", fn s -> s))) == Crypto.sha256(Crypto.sha256("a") ++ Crypto.sha256("b"))
true

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

Build a tree from items, hashing each with to_bytes. Leaves are paired left to right, layer by layer; an odd node at the end of a layer is carried up unpaired. Returns None for an empty list. O(n).

Examples

march> Merkle.build([], int_to_string)
None
march> Option.map(Merkle.build([1, 2, 3], int_to_string), Merkle.leaves)
Some([1, 2, 3])

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

True when any node of the tree, leaf or branch, has hash h. A branch match stops the search, so this also answers "is this subtree present". O(n) in the worst case.

Examples

march> let mt1 = Option.unwrap(Merkle.build([1, 2, 3, 4], int_to_string))
march> Merkle.contains_hash(mt1, Crypto.sha256("2"))
true
march> let mt1 = Option.unwrap(Merkle.build([1, 2, 3, 4], int_to_string))
march> Merkle.contains_hash(mt1, Merkle.root_hash(mt1))
true
march> let mt1 = Option.unwrap(Merkle.build([1, 2, 3, 4], int_to_string))
march> Merkle.contains_hash(mt1, "nope")
false

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

The hashes, taken from t1, of the leaves where t1 and t2 differ, left to right. Subtrees whose hashes match are skipped, so for k changed leaves this is O(k log n). Meant for trees of the same shape (built from lists of the same length); where the shapes diverge it reports t1's node at that point, which for a branch is a branch hash, not a leaf hash.

Examples

march> let mt1 = Option.unwrap(Merkle.build([1, 2, 3, 4], int_to_string))
march> let mt2 = Option.unwrap(Merkle.build([1, 2, 30, 4], int_to_string))
march> Merkle.diff(mt1, mt1)
[]
march> let mt1 = Option.unwrap(Merkle.build([1, 2, 3, 4], int_to_string))
march> let mt2 = Option.unwrap(Merkle.build([1, 2, 30, 4], int_to_string))
march> Merkle.diff(mt1, mt2) == [Merkle.root_hash(Merkle.leaf(3, int_to_string))]
true

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

A single-leaf tree holding x, whose hash is Crypto.sha256(to_bytes(x)).

Examples

march> Merkle.leaves(Merkle.leaf(42, int_to_string))
[42]
march> Merkle.root_hash(Merkle.leaf("abc", fn s -> s)) == Crypto.sha256("abc")
true

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

All leaf hashes, left to right.

Examples

march> let mt1 = Option.unwrap(Merkle.build([1, 2, 3, 4], int_to_string))
march> Merkle.leaf_hashes(mt1) == List.map([1, 2, 3, 4], fn x -> Crypto.sha256(int_to_string(x)))
true

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

All values stored at the leaves, left to right (the order given to build).

Examples

march> let mt2 = Option.unwrap(Merkle.build([1, 2, 30, 4], int_to_string))
march> Merkle.leaves(mt2)
[1, 2, 30, 4]

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

The hash stored at the root: the leaf's hash for a leaf, the branch hash otherwise. Two trees built the same way from equal leaves have equal root hashes. O(1).

Examples

march> String.byte_size(Merkle.root_hash(Merkle.leaf("abc", fn s -> s)))
64

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

Number of leaves in the tree. O(n).

Examples

march> let mt1 = Option.unwrap(Merkle.build([1, 2, 3, 4], int_to_string))
march> Merkle.size(mt1)
4