Merkle hash tries (a data structure)

This dart proposes a cryptographic data structure that may be of use in Storm.

A trie is a tree which stores a set of strings, with a leaf node for every string, and with an internal node for every common prefix. For example,

     [root]
      /  \
    [0]  [1]
    /      \
  [00]     [11]
  /   \      \
0001  0010   [111]
             /   \
          1110   111101

The nodes with one child can also be omitted for efficiency, i.e.

     [root]
      /  \
     /    \
    /      \
  [00]      \
  /   \      \
0001  0010   [111]
             /   \
          1110   111101

A hash trie is a trie where the (bit)strings are the hashes of the objects you actually want to store.

A Merkle hash trie, then, is a hash trie stored as a Merkle hash tree: The root and internal nodes are labelled with the hash of their children.

In Storm, each node would be a Storm block, and the root and internal nodes would contain the block ids of their child nodes.

Obviously, we would also use Storm ids as the hashes stored in the trie.

Hash tries can also be used to implement a mapping, rather than a set: Then, each leaf node stores a key/value pair (where both key and value are hashes), and the key is used for traversing the trie.

Merkle hash tries can be used to--

• give an efficient proof that a certain element is part of a set (this is what vanilla Merkle hash trees also do);
• give an efficient proof that a certain key maps to a certain value-- and only that value-- in a mapping;
• give an efficient proof that a certain element or key doesn't exist in a set or mapping;
• given a whole trie, traverse the trie to find the value associated with a given key.

"Efficient" means that for n elements in the trie, the proofs need only O(log n) space (and time to verify).

Also, the data structure leans itself to versioning: Storing an updated version of a trie needs only O(log n) additional space per added/modified/deleted entry.

Finally, the tree automatically approximately balances itself (because the hashes are approximately randomly distributed).

Applications could include, for example, certificate revocation trees.

0x00 -- branch node (may be the root)
0x01 -- leaf node of set (one element)
0x02 -- leaf node of map (key/value pair)