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 [EMAIL PROTECTED]

Reply via email to