MerkleTree

A merkle tree

This library provides a simple merkle tree data structure for Motoko. It provides a key-value store, where both keys and values are of type Blob.

var t = MerkleTree.empty();
t := MerkleTree.put(t, "Alice", "\00\01");
t := MerkleTree.put(t, "Bob", "\00\02");

let w = MerkleTree.reveals(t, ["Alice" : Blob, "Malfoy": Blob].vals());

will produce

#fork (#labeled ("\3B…\43", #leaf("\00\01")), #pruned ("\EB…\87"))
#fork(#labeled("\41\6C\69\63\65", #leaf("\00\01")), #labeled("\42\6F\62", #pruned("\E6…\E2")))

The witness format is compatible with the HashTree used by the Internet Computer, so client-side, the same verification logic can be used.

Revealing multiple keys at once is supported, and so is proving absence of a key.

The tree branches on the bits of the keys (i.e. a patricia tree). This means that the merkle tree and thus the root hash is unique for a given tree. This in particular means that insertions are efficient, and that the tree can be reconstructed from the data, independently of the insertion order.

A functional API is provided (instead of an object-oriented one), so that the actual tree can easily be stored in stable memory.

type Key = Blob

type Path = [Blob]

type Value = Blob

type Tree = LabeledTree

This is the main type of this module: a possibly empty tree that maps Keys to Values.

type Witness = {#empty; #pruned : Hash; #fork : (Witness, Witness); #labeled : (Key, Witness); #leaf : Value}

The type of witnesses. This correponds to the HashTree in the Interface Specification of the Internet Computer

type Hash = Blob

public func treeHash(t : Tree) : Hash

The root hash of the merkle tree. This is the value that you would sign or pass to CertifiedData.set

public func empty() : Tree

Tree construction: The empty tree

public func put(
  t : Tree,
  ks : Path,
  v : Value
) : Tree

Tree construction: Inserting a key into the tree. An existing value under that key is overridden. This also deletes all keys at all paths that are a prefix of the given path!

public func delete(t : Tree, ks : Path) : Tree

Deleting a key from a tree. This removes the given key from the tree, independently of whether there is a value at that label, or a whole subtree. Will also remove enclosing labels if there is no value left.

public func lookup(t : Tree, ks : Path) : ?Value

Looking up a value at a key

This will return null if the key does not exist, or if there is a subtree (and not a value) at that key.

public func labelsAt(t : Tree, ks : Path) : Iter.Iter<Key>

Lookup up all labels at a key. Returns an iterator, so you can use it with

for (k in MerkleTree.labelsAt(t, ["some", "path"))) { … }

public func reveal(tree : Tree, path : Path) : Witness

Create a witness that reveals the value of the key k in the tree tree.

If k is not in the tree, the witness will prove that fact.

public func merge(w1 : Witness, w2 : Witness) : Witness

Merges two witnesses, to reveal multiple values.

The two witnesses must come from the same tree, else this function is undefined (and may trap).

public func revealNothing(tree : Tree) : Witness

Reveal nothing from the tree. Mostly useful as a netural element to merge.

public func reveals(tree : Tree, ks : Iter.Iter<Path>) : Witness

Reveals multiple paths

public func reconstruct(w : Witness) : Hash

We can reconstruct the root witness from a witness

type RawTree = {#value : Blob; #subtree : [(Key, RawTree)]}

The return type of structure

public func structure(t : Tree) : RawTree

Extract the raw data from the trees, mostly for pretty-printing

public func encodeWitness(tree : Witness) : Blob

The CBOR encoding of a Witness, according to https://sdk.dfinity.org/docs/interface-spec/index.html#certification-encoding including the CBOR self-describing tag