A Merkle Tree for Motoko for use with Certified Variables
A merkle tree
Same as https://github.com/nomeata/motoko-merkle-tree but with reconstruct added
If you benefit from this added function, please consider donating to help me continue building cool stuff All procededs will be locked in 8 year ICP Neurons ICP: 8521de510a846b6b20b2d4795630a29f4f937f0dd09b3bd802f3319d6b1aef45 ETH: 0xeF5f8a19300f85Fe0806cA4816FcB10bDd24b313 BTC: 3QLgWdjbF1K5j12T2sHqZtzHHLphyZVA8z
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"))
The witness format is compatible with the HashTree used by the Internet Computer, so client-side, the same logic can be used, but note
- the trees produces here are flat; no nested subtrees
// (but see
witnessUnderLabel
to place the whole tree under a label). - keys need to be SHA256-hashed before they are looked up in the witness
- no CBOR encoding is provided here. The assumption is that the witnesses are transferred via Candid, and decoded to a data type understood by the client-side library.
Revealing multiple keys at once is supported, and so is proving absence of a key.
By ordering the entries by the hash of the key, and branching the tree based on the bits of that hash (i.e. a patricia trie), 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.
The tree-related functions are still limited, only insertion so far, no lookup, deletion, modification, or more fancy operations. These can be added when needed.