Hi all,

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.

- 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.::

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).

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