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
A B C D
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.