### Literature about Merkle hash tries?

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

### Re: Literature about Merkle hash tries?

At 01:14 AM 10/1/2003 +0300, Benja Fallenstein wrote: So, anyway, anybody know references? I've not come across any yet. I know that the technique dates back (at least) to IBM in the 60s. I used to know the name of the inventor but can't bring it to mind at the moment. The Berkeley UNIX library dbm uses essentially this philosophy, but the tree is not binary; rather each node stores up to one disk block's worth of pointers. Nodes split when they get too full. When the point is to handle a lot of data, this makes much more sense. Hope that helps, Greg. Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/ Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Literature about Merkle hash tries?

Hi Greg-- Greg Rose wrote: At 01:14 AM 10/1/2003 +0300, Benja Fallenstein wrote: So, anyway, anybody know references? I've not come across any yet. I know that the technique dates back (at least) to IBM in the 60s. Cool-- but-- On second thoughts, do you mean *cryptographic* hash tries or hash tries or plain tries? I know literature on both tries and hash tries (Knuth claimed to have invented the latter in an Literate Programming exercise) but not on using cryptographic hash functions a Merkle hash tree. Reason for my second thoughts is that Merkle's patent on hash trees dates in the 80s ;-) I used to know the name of the inventor but can't bring it to mind at the moment. The Berkeley UNIX library dbm uses essentially this philosophy, but the tree is not binary; rather each node stores up to one disk block's worth of pointers. Nodes split when they get too full. When the point is to handle a lot of data, this makes much more sense. (In Merkle hash trees, on the other hand, signature size is minimized when using a binary tree, at least if I'm not confused right now. :) ) Thanks, - Benja - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]