Associative hash mixing

Question

Consider the lowly singly-linked list in a purely functional setting. Its praises have been sung from the mountain tops and will continue to be sung. Here I will address one among its many strengths and the question of how it may be extended to the wider class of purely functional sequences based on trees.

The problem is the following: You want to test for almost certain structural equality in O(1) time by means of strong hashing. If the hash function is structurally recursive, i.e. hash (x:xs) = mix x (hash xs), then you can transparently cache hash values on lists and update them in O(1) time when an element is consed onto an existing list. Most algorithms for hashing lists are structurally recursive, so this approach is eminently usable in practice.

But suppose instead of singly-linked lists you have tree-based sequences that support concatenating two sequences of length O(n) in O(log n) time. For the hash caching to work here, the hash mixing function must be associative in order to respect the degrees of freedom a tree has in representing the same linear sequence. The mixer should take the hash values of the subtrees and calculate the hash value of the whole tree.

This is where I was six months ago when I spent a day mulling over and researching this problem. It seems to have received no attention in the literature on data structures. I did come across the Tillich-Zemor hashing algorithm from cryptography. It relies on 2x2 matrix multiplication (which is associative) where bits 0 and 1 correspond to the two generators of a subalgebra with entries in a Galois field.

My question is, what have I missed? There must be papers of relevance in both the literature on cryptography and data structures that I failed to find in my search. Any comments on this problem and possible venues to explore would be greatly appreciated.

Edit: I am interested in this question on both the soft and cryptographically strong ends of the spectrum. On the softer side it can be used for hash tables where collisions should be avoided but aren't catastrophic. On the stronger side it can be used for equality testing.

Answer 1

Added: After reading Per’s comments, I think that this answer is just a (poor) variation of the Tillich-Zemor hashing algorithm which is already mentioned in the question. I withdraw this answer, but I leave it hoping that it (and the comments) may be informative for some readers.

---

Edit: An earlier revision of this answer suggested to use a monoid operation on [m], but as Per pointed out in a comment, it is desirable to use a group operation.

This answer is about building a hash function for hash tables which is easy to implement. A provable guarantee on the quality is not expected.

Assuming that you already have a hash function for each element of a sequence to a finite set [m]={1, …, m}, how about interpreting each element of [m] as an element in a finite group G and using the group operation on G? You can use any mapping from [m] to G, but it is desirable that the mapping be injective so that we do not lose the information in the hash value of each element. It is also desirable that the group not be commutative so that the hash function can catch the difference in the order of the elements in a sequence.

I do not know much about finite groups which allow fast operations, but I guess that such groups are known in coding theory. Using the symmetric group of order at least m may not be so bad.

Answer 2

The almost-universal family of hash functions

$$\{h_a(\vec{x}) = \sum a^i x_i \bmod p: a \in \mathbb{Z}_p\}$$

has a nice property here: $h_a(\vec{x}) + a^{|\vec{x}|}h_a(\vec{y}) = h_a(\vec{x} \circ \:\vec{y})$, where "$\circ$" denotes concatenation. If you cache at the root of each tree both its hash value and $a^{|\vec{x}|}$, you can calculate the hash of the concatenation of two trees in $O(1)$ operations on $\mathbb{Z}_p$.

This is both associative and pretty fast. The collision probability of $\vec{x} \neq \vec{y}$ is $O(\min(|\vec{x}|,|\vec{y}|)/p)$. See CLRS or Dietzfelbinger et al.'s in "Polynomial Hash Functions Are Reliable".

Answer 3

One solution is to use Merkle hashing. Use an immutable/persistent binary tree data structure. Annotate each leaf node with the hash of the data contained within that leaf. Annotate each internal node with the hash of the hashes on its two children. In other words, if $n$ is an internal node with children $n',n''$, and they have been annotated with the hash values $y',y''$, then you should annotate the internal node $n$ with the hash value $y=H(y',y'')$, where $H$ is a hash function. This adds only $O(1)$ extra work per node created to all tree operations. For instance, you can support merging of two trees in $O(\lg n)$ time.

Another approach is to use a commutative, associative hash. Label the root of the tree with $H(x_1,\dots,x_m)$, where $x_1,\dots,x_m$ represent the values on the $m$ leaves of the tree. Then, use one of the hash function constructions suggested at https://crypto.stackexchange.com/q/11420/351 to ensure it has the commutative, associative property. Now given two trees, you can merge them and construct the hash value on their root efficiently.