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 , ,  and  respectively, ::
[root] / \   / \   / \ \ 0001.. 0010..  / \ 1110.. 1111..
The nodes with one child can also be omitted for efficiency, i.e.::
[root] / \ / \ / \  \ / \ \ 0001.. 0010..  / \ 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  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]