10
$\begingroup$

Git uses SHA hashing as a content address key. This relies on their being a vanishingly small probability that two different pieces of content will ever hash to the same key.

For content c with length l(c), SHA(c) can be computed in time O(l(c)) and uses constant space.

I am curious if there are hashes with a similar extremely low probability of collision that can be considered to be "associative".

What do I mean by "associative"?

I am looking for something with an additional constraint over SHA. Given any bisection of c in to two parts c_l, c_r, which can be recombined so c = c_l + c_r, I want a hash H that is able to compute H(c) based on H'(c_l) and H'(c_r). I'm writing H' here because perhaps it is necessary for there to be some intermediate hashed value from which a final hash is computed.

H' should also require time linear to the content and have constant space.

The use case of this is that I have a tree with content in the leaves and intermediate hash values (the H` results) in its nodes. I want to be able to compute the root hash over all of the elements. But I want the root hash to be equal for all trees that have the same order of elements.

      a          b
               
     H'          H'
    /  \        /  \
   H'   3      1   H'
  /  \            /  \
 1    2          2    3

Trees a and b should have the same root hash because while they have different structure, they have the same leaves in the same order.

More specifically, I want to be able to compute the hash of the leaf elements of a BTree based on partial hashes stored in its non leaf nodes. The root node's hash should be equal for all trees that have the same leaf elements, regardless of the exact structure of the tree.

Ideally this hash scheme would be "cryptographic" in that it is impractically costly to engineer content that deliberately causes a collision. However, this is not a hard requirement.

Also, if no such linear time and constant space sceheme exists, then log time and log space could be acceptable.

Thank you!

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ A better term for the property that $H(c_1 + c_2) = H(c_1) * H(c_2)$ for some operation $*$ would be homomorphic, though you are specifically interested in hashes which are homomorphic with respect to concatenation of the inputs (rather than some other operation). See also this Q&A on Cryptography SE. $\endgroup$
    – kaya3
    Commented Dec 3, 2023 at 14:54
  • $\begingroup$ Thank you @kaya3! That makes really good sense, and I think it makes a lot more clear to me what a homomorphism is as well, so that's double helpful, thank you. $\endgroup$
    – Benjohn
    Commented Dec 4, 2023 at 21:41

1 Answer 1

Reset to default
9
$\begingroup$

There is a plausible construction of such a hash. At design time, randomly choose two $2\times 2$ matrices with entries in $\mathbb{F}_{2^n}$ that have determinant 1, fix them, and call them $h(0),h(1)$. Then, for any string $x \in \{0,1\}^*$, define

$$h(x_1 \cdots x_k) = h(x_1) \times \cdots \times h(x_k),$$

where the product is of $2 \times 2$ matrices with entries in $\mathbb{F}_{2^n}$.

Then, the hash of a tree can be defined as the result of hashing the concatenation of all leaves, in left-to-right order. You can store, in each internal node, the hash of the leaves under it, which allows you to efficiently update the hash of the tree as you insert or delete into the tree.

For security, I suggest choosing $n \ge 256$. For example, for $n=256$, the output of the hash is 1024 bits long (though it can be compressed to 768 bits by using the fact that the matrix has determinant 1). Of course, for equality checking, it's enough to store the SHA256 hash of the output of $h(\cdots)$, which is even shorter.

As far as I can tell, there are no known attacks in the literature on such a scheme, so this scheme seems like it might be cryptographically collision-resistant -- though the security of such schemes appears to be quite tricky, and I am not an expert on this subject, so there might be fatal flaws in the scheme that I am unaware of.

References:

Separately: I also encourage you to check out Canonical representation of finite maps on non-overlapping finite rational intervals and Can ropes (AVL trees) be interned?, which address closely related problems, and might suggest alternate approaches to your problem.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Neat! That makes sense, thank you. I guess many finite groups would work here? The requirement would be that any element of the group could be reached by a a sequence of products of the two picked elements? And ideally that there’s a fairly uniform distribution? I assume the determinate of 1 is to help ensure the product doesn’t collapse quickly to 0? $\endgroup$
    – Benjohn
    Commented Dec 2, 2023 at 11:30
  • 2
    $\begingroup$ @Benjohn, I think the choice of group might be subtle/tricky, if you want cryptographic collision-resistance. But if you don't care about crypto, then many finite groups might be OK. Yes, and to avoid leaking information about the value being hashed (which might not be relevant for your application). $\endgroup$
    – D.W. ♦
    Commented Dec 2, 2023 at 11:41
  • $\begingroup$ Also, your links look extremely relevant. Thank you 🙏 $\endgroup$
    – Benjohn
    Commented Dec 2, 2023 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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