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.
c with length
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_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.
/ \ / \
H' 3 1 H'
/ \ / \
1 2 2 3
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.