14
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Yeah, Tillich-Zemor hashing also uses matrix multiplication. What you suggest can't work without further modifications a la Tillich-Zemor. For example, you must avoid singular matrices or you get accumulation at 0, ruining the hash statistics. Tillich-Zemor works over a Galois field; an earlier version of their algorithm had issues because they used a generating polynomial that had suboptimal statistics, so the particular Galois field can be very important. $\endgroup$ – Per Vognsen Sep 26 '10 at 12:48
  • $\begingroup$ @Per: I see. Thank you for explanation. Then what about using any finite groups? I modified the answer to this. $\endgroup$ – Tsuyoshi Ito Sep 26 '10 at 13:09
  • $\begingroup$ I agree. The best way of generating infinite families of groups is with matrix groups over finite fields (cf. the classification theorem for finite simple groups), so it seems algorithms of this form will be of the Tillich-Zemor type. $\endgroup$ – Per Vognsen Sep 26 '10 at 13:10
  • $\begingroup$ @Per: I am not familiar with the group theory, and I cannot see why matrix groups over finite fields are better than symmetric groups in this context. Can you elaborate on it? $\endgroup$ – Tsuyoshi Ito Sep 26 '10 at 13:14
  • 1
    $\begingroup$ There's a couple of reasons. For one, you cannot compute efficiently in big symmetric groups, and you need the groups to be on the order of 2^128 for collision resistance. By contrast, you can compute with matrices over characteristic 2 finite fields very efficiently, especially if you pick a sparse generator polynomial; it's just a bunch of bit manipulations. $\endgroup$ – Per Vognsen Sep 26 '10 at 13:19
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.