<div dir="ltr">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.<br><div><br></div><div>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.</div><div><br></div><div>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.</div></div><br><div class="gmail_quote">On Wed, May 27, 2015 at 1:09 PM Ben Laurie <<a href="mailto:ben@links.org">ben@links.org</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On 27 May 2015 at 18:47, Jelle van den Hooff <<a href="mailto:jelle@vandenhooff.name" target="_blank">jelle@vandenhooff.name</a>> wrote:<br>
> Hi everyone,<br>
><br>
> If you are interested in hash functions or data structures, I wrote a short<br>
> paper (<a href="http://jelle.vandenhooff.name/seqhash.pdf" target="_blank">http://jelle.vandenhooff.name/seqhash.pdf</a>) you might like on<br>
> associative hash functions. An associative hash function is a hash function<br>
> that allows you to efficiently calculate hash(concat(a, b)) from hash(a) and<br>
> hash(b). In the paper, I describe how to build an associative hash function<br>
> from history-independent data structures.<br>
><br>
> There is a small catch, as the associative hash function described has an<br>
> output that grows in size as O(log n), instead of the O(1) delivered by SHA<br>
> et al. That is, for now, the price to pay for associativity.<br>
<br>
Sounds exactly like a Merkle tree.<br>
</blockquote></div>