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 
[] 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?

[Greg Rose]

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?

[Benja Fallenstein]

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]