[Cryptography] an associative hash function

[Jelle van den Hooff]

Like the abstract says, the hash function is based on a Merkle hash. The
key issue the paper addresses is what shape to use for the underlying
Merkle tree. Most underlying trees are not suitable for concatenation.

For example, the tree used in Bitcoin to compute the hash over transactions
in a block is a full binary tree. Those full binary trees support efficient
appends on the right side, but do not support efficient prepends.

The problem is the rigid shape of such trees: In a full Merkle binary tree,
the first and second node always share the same parent, the third and
fourth share the same parent, and so forth. Maintaining that structure is
hard when you prepend a new element, as after prepending all indices
change. What used to be the first node is now the second, and the second
became the third, and so forth. That means that all parent nodes are now in
the wrong place and need to move. But moving nodes means that their hashes
change, and so if you use the wrong tree, concatenation can require
computing O(n) hashes -- not efficient at all.

On Wed, May 27, 2015 at 1:09 PM Ben Laurie <ben at links.org> wrote:

> On 27 May 2015 at 18:47, Jelle van den Hooff <jelle at vandenhooff.name>
> wrote:
> > Hi everyone,
> >
> > If you are interested in hash functions or data structures, I wrote a
> short
> > paper (http://jelle.vandenhooff.name/seqhash.pdf) you might like on
> > associative hash functions. An associative hash function is a hash
> function
> > that allows you to efficiently calculate hash(concat(a, b)) from hash(a)
> and
> > hash(b). In the paper, I describe how to build an associative hash
> function
> > from history-independent data structures.
> >
> > There is a small catch, as the associative hash function described has an
> > output that grows in size as O(log n), instead of the O(1) delivered by
> SHA
> > et al. That is, for now, the price to pay for associativity.
>
> Sounds exactly like a Merkle tree.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150527/5991ccd9/attachment.html>