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.
This is the main type of this module: a possibly empty tree that maps
Key
s to Value
s.
The type of witnesses. This correponds to the HashTree
in the Interface
Specification of the Internet Computer
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 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