Literature about Merkle hash tries?

[Benja Fallenstein]

Hi all,

Does anybody on this list know literature about cryptographic hash 
tries? (I hit on this idea when mulling about a different problem, and 
was wondering what people have written about it.) I.e., a data structure 
for keeping sets of pieces of data, by:

- computing a cryptographic hash of each piece, treating each hash as a 
bitstring;
- organizing these in a trie ("A tree for storing strings in which there 
is one node for every common prefix. The strings are stored in extra 
leaf nodes," http://www.nist.gov/dads/HTML/trie.html);
- treating this trie as a Merkle hash tree.

For example, if we have four hashes starting [0001], [0010], [1110] and 
[1111] respectively, ::

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


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

        [root]
         /  \
        /    \
       /      \
     [00]      \
     /   \      \
  0001.. 0010.. [111]
                /   \
             1110.. 1111..

This could easily be extended to provide a mapping, by treating the keys 
as above, and putting each values in the "extra leaf node" of their 
corresponding key.

It seems to me that this data structure would--

- allow giving efficient proofs not only of membership, but also 
non-membership, by giving the path through the tree that would end up at 
that item, but show that it ends up at a different item. E.g., to prove 
that a hash starting [0011] is not in the above set, give the path to 
"0010..". (This could be used to implement CRTs.)
- be automatically approximately balanced (I haven't attempted a proof, 
but since all prefixes are conjectured to be equally likely...)
- allow you to maintain a history of such trees with only O(log n) 
additional storage cost per addition or removal-- i.e., if you already 
have a whole tree with n items, and want to additionally store a tree 
that has one item added, you only need O(log n) additional storage 
space-- and you don't need to implement some complicated re-balancing 
algorithm (if the previous conjecture holds).

It's functionally equivalent to having a binary search tree that stores 
a value at each internal node, but it seems potentially simpler to 
implement, particularly when you want to store a versioned history (e.g. 
of a CRT), because you don't need to implement re-balancing.

So, anyway, anybody know references? I've not come across any yet.

Thanks,
- Benja

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com