<p><em>Added</em>: 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.</p>

<hr>

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

<p>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.</p>

<p>Assuming that you already have a hash function for each element of a sequence to a finite set [<i>m</i>]={1, …, <i>m</i>}, how about interpreting each element of [<i>m</i>] as an element in a finite group <i>G</i> and using the group operation on <i>G</i>?  You can use any mapping from [<i>m</i>] to <i>G</i>, 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.</p>

<p>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 <i>m</i> may not be so bad.</p>

CC BY-SA 2.5
2010-09-26T12:48:00.843Z
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.
Per Vognsen
CC BY-SA 2.5
2010-09-26T13:09:21.780Z
@Per: I see.  Thank you for explanation.  Then what about using any finite groups?  I modified the answer to this.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-26T13:10:52.293Z
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.
Per Vognsen
CC BY-SA 2.5
2010-09-26T13:14:54.507Z
@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?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-26T13:19:03.550Z
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.
Per Vognsen
CC BY-SA 2.5
2010-09-26T13:32:02.007Z
@Per: Thank you for further explanation.  Now I see that this answer is basically a poor variation of what is already known.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-26T13:33:34.233Z
No, I really appreciate the effort, and it forced me to think through some of my implicit assumptions. Anyway, I hope this also explained, if you were in doubt, why coding theorists are crazy about matrix groups over finite fields in characteristic 2. :)
Per Vognsen
CC BY-SA 2.5
2010-09-26T13:44:40.007Z
@Per: Oops, if my previous comment and edit sounded as if I was upset, sorry about that.  I am not upset, and I really mean “thank you,” not in the sarcastic sense :).  I am happy that now I know why matrix groups are chosen among many groups.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-01T05:41:39.893Z
I decided to accept your answer since no others were forthcoming and it really helped me realize how narrow the effective scope is for solutions to this problem.
Per Vognsen
CC BY-SA 2.5
2010-10-01T12:00:01.597Z
@Per: Thanks, but if a better answer appears, do not hesitate to unaccept my answer.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-26T12:42:32.597Z
2010-09-26T13:43:55.607Z
2010-09-26T13:43:55.607Z
Tsuyoshi Ito
<p>The almost-universal family of hash functions</p>

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

<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$. </p>

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

CC BY-SA 3.0
2013-10-29T14:00:21.017Z
2013-10-29T14:00:21.017Z
jbapple
<p>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.</p>

<p>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 <a href="https://crypto.stackexchange.com/q/11420/351">https://crypto.stackexchange.com/q/11420/351</a> 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.</p>

CC BY-SA 3.0
2013-11-01T00:44:29.340Z
2013-11-01T00:44:29.340Z
2017-04-13T12:48:17.970Z
D.W.
<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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. </p>

<ds.data-structures><cr.crypto-security><functional-programming><hash-function>
Associative hash mixing
Per Vognsen
# Associative hash mixing

(Asked by: username_0 on 2010-09-26)

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.

**Tags:** ds.data-structures, cr.crypto-security, functional-programming, hash-function


---

## 3 answers

### Answer by username_1 on 2010-09-26. Score: 2 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  
> **username_1**: @Per: I see.  Thank you for explanation.  Then what about using any finite groups?  I modified the answer to this.  
> **username_0**: 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.  
> **username_1**: @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?  
> **username_0**: 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.  
> **username_1**: @Per: Thank you for further explanation.  Now I see that this answer is basically a poor variation of what is already known.  
> **username_0**: No, I really appreciate the effort, and it forced me to think through some of my implicit assumptions. Anyway, I hope this also explained, if you were in doubt, why coding theorists are crazy about matrix groups over finite fields in characteristic 2. :)  
> **username_1**: @Per: Oops, if my previous comment and edit sounded as if I was upset, sorry about that.  I am not upset, and I really mean “thank you,” not in the sarcastic sense :).  I am happy that now I know why matrix groups are chosen among many groups.  
> **username_0**: I decided to accept your answer since no others were forthcoming and it really helped me realize how narrow the effective scope is for solutions to this problem.  
> **username_1**: @Per: Thanks, but if a better answer appears, do not hesitate to unaccept my answer.  

---

### Answer by username_2 on 2013-10-29. Score: 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 by username_3 on 2013-11-01. Score: 2

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.


---

