I am exploring the class of functions that I have seen called "hash combination functions". These functions are arguably distinct from hash functions, generally providing second-preimage resistance, but not preimage resistance. I am interested in these functions for combining non-leaf nodes in a computing a merkle tree, but I'm struggling to find resources defining their security.

In this answer by Pieter Wuille, he references a function f(a,b) = (a+b,ab) % p, which combines two hashes to produce a tuple of their sum and product modulo a large prime. Pieter says that each output uniquely identifies some given inputs, but not their order - f(a,b) = f(b,a).

Assuming that one initializes the leaf labels of a merkle tree using a secure hash function like poseidon, those labels can be combined with this function in a way that ensures that the inputs have no small factors. Each non-leaf node of the tree would have a label that is the tuple output by the hash combination function.

The advantage of this approach would seem to be that it's very inexpensive to compute within the prime field of a ZK SNARK. My experiments with this seem to show that the cost of verifying a sparse merkle proof is n+1 linear constraints, where n is the depth of the tree. This is a several-hundred-fold reduction in proving cost versus using poseidon to hash combinations of nodes.

Are there any significant issues with the security of this approach? Are there any related functions in this class which might have better security properties but similar efficiency?

  • $\begingroup$ In some usage this is not a good idea, you wanted the 4th entry, however, the attacker sent you the 4th, and you wanted 4rd and they sent you 3rd and you cannot detect it as long as you put some additional countermasures. $\endgroup$
    – kelalaka
    Apr 4 at 0:30


Your Answer

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