# Are there any hash functions that are commutative yet secure for ordered lists?

I'm looking for a hashing function that can combine random numbers together in any order yet still find the same value. But it needs to be secure against hackers.

The idea is if I'm hashing together: $$A, B, C$$, and $$D$$

Where hash of $$x = h(x)$$:

I'm looking for a hash function that allows: $$h(A+B+C+D) = h(A)+h(B)+H(C+D) = h(A+B) + h(C) + h(D)$$

The $$+$$ symbol could be the same hash, could be something different.

I want something that is highly compressed, as in no matter how many additional items you add, the length doesn't grow.

The idea is that I can pop out any item from a long list of hashed items and prove that the items before X plus X plus the items after X can be proved to be part of a set.

I don't want Merkle tree or accumulator because both have relatively long proofs or the total size of the 'key' though that's kind of what I'm looking for. For my application, unfortunately, memory is very important.

• Is this a correct restatement of the problem: you want a commitment $H(a+b+ …+p+q+r+ …, +y+z)$ such that, if want to prove that $q$ is in the list, you can publish the three values $H(a+b+ …+p) + H(q) + H(r+…,+y+z)$ (with the security goal that someone cannot find values $x + H(q) + w$ that sum to the commitment). Is this correct? I don't know if this can be done more efficiently than a Merkle tree, but at least I'd like to be sure on the question. Feb 13 '20 at 15:28
• How could +, which has two arguments, be "the same hash" when the hash h has a single argument? Also, there seems to be two different +: one operates on messages, like in h(A+B); the other operates on hashes, like h(A)+h(B). Can they be separate operations? Which, if any, needs to be commutative? Note: the stated property is reminiscent of associativity, with no relationship to commutativity.
– fgrieu
Feb 13 '20 at 15:31
• @poncho this is comment of OP I realize this may not be possible but would love thoughts. Thanks. Feb 13 '20 at 20:16
• Thank you whoever bunch me up high enough to comment! I'm thinking something like ChaCha20-poly1305, where they create a block cipher using nothing but XOR, Shift, and Addition. Each of which is commutative themselves. Basically a stream cipher but be able to prove any piece of it using the 'hash' to the left and the 'hash' to the right which is the rest of the string. All of that hashes together to create one short 'public key'. Feb 14 '20 at 3:20