See equation below as I see an easier alternative, as I'm having trouble explaining it. Is there a hash function where many hashes can be combined together in a way where any single hash can be combined with a hash of the rest of the hashes to generate the hash of all hashes?

Seems to me like a hash that fits this property might exist.. and be an excellent way to seriously compress Merkle proofs very significantly.

Example: Let's say you want to hash 4 blocks of data together


And in my below equations: () = hash + = some function that combines together the hashes append, xor, and, etc.

Is there a hash where this property is true: (A + B + C + D) = (A) + (B + C + D) = (A) + (B) + (C + D) = (A + B) + (C) + (D) = (A + B + C) + (D)

Alternatively would be ideal, but I see this being harder to do: (A + B + C) = (A) + (B + C) = (B) + (A + C) = (C) + (A + B)

This would mean that instead of providing proof at every level of a tree, you could instead submit 2 hashes as well as the root hash to prove that an item is included.

Imagine that this was used as an alternative to a Merkle tree for 128 items. Instead of submitting 7 hashes to prove you own one, now you only have to submit 3. This would lead to a compression of roughly 60%

In fact, any Merkle proof for more than 8 items would still only require 3 hashes to prove it's correctness. Use it for something like Zero-Knowledge Proofs with millions of items and seems to me like theoretically, you could compress the data structure by 90% or more.

Which leads to my final question: Do you know of a hashing function that could work like this and have this property? I don't understand hashing well enough.

  • $\begingroup$ That would be very dangerous to find collisions. $\endgroup$ – kelalaka Aug 17 '19 at 18:39
  • $\begingroup$ You're right it would indeed have to be very carefully crafted to avoid this. But I do still suspect doable. $\endgroup$ – mczarnek Aug 17 '19 at 18:57
  • $\begingroup$ Note alternatively could construct alternative hashes or proofs while hashing for every input that is used only to prove that hash is correct without actually requiring them to be hashed combinations themselves. $\endgroup$ – mczarnek Aug 17 '19 at 19:47
  • $\begingroup$ Are you looking for cryptographic accumulators? $\endgroup$ – Natanael Aug 17 '19 at 20:06
  • $\begingroup$ @Natanael I think that is indeed what I'm looking for. Thanks! $\endgroup$ – mczarnek Aug 17 '19 at 22:23

Your Answer

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

Browse other questions tagged or ask your own question.