Reduced compression calls about sponge HOT 6 CLOSED

I got some numbers. For Poseidon, it seems that:

3 * a hash function with input size L

is likely MORE EXPENSIVE than

1 * a hash function with input size 5L

both when we consider the # number of constraints and when we consider the # number of constraint system weight.

e.g., for the case of constraints, alpha = 5, ~298-bit prime number,

a 2-input sponge needs 240 constraints => multiplied by 3 = 720
a 10-input sponge needs 435 constraints

This is because Poseidon of state size L + 1

• only do x^\alpha for the first L elements in FULL rounds, which are considerably few
• do x^\alpha for the last element in PARTIAL rounds

That is to say, Poseidon has been intentionally optimized to scale well with a larger state size.

So, for Poseidon, using the transformation of 2021/373 may not be better than using a fatter sponge.

Yet, the result here is also instructive---when we do the Merkle tree, there might be some benefits to use a 4-arity tree compared with a binary tree. (Needs more investigation).

Note that this result might not apply to Rescue. Rescue examines each element in each round (no separation between full rounds and partial rounds).

@burdges What do you think?

from sponge.

Yes. I think the next step is to estimate the cost.

Because sponge parameters can also be selected to be suitable for 5-to-1 compression, and it is unknown which of the following is better:

• a naturally 5-to-1 compression function via sponge
• a 5-to-1 compression function via three invocations of sponges targeted at 2-to-1 cases

from sponge.

Interesting! I thought Poseidon rarely if ever made sense as a binary tree, like mostly using arities divisible by 3?

from sponge.

I think a lot of the time when people use binary trees it is due to convenience, but probably not the best choice after some careful calculation.

It seems that using a high arity is generally beneficial for Poseidon.

from sponge.

If you're simply including the copath elements then binary hashing should handle dense trees better, and works well with skipping logic for sparse cases. In this case, it's simply that zk avoids the space concerns in the first place, and then happens to reduce computation at somewhat higher arities.

We can close this it sounds like..

from sponge.

Good points.

A common concern for the k-arity tree is that the Merkle tree path proofs (i.e., paths and copaths) would be much longer. However, in ZK, they are often witnesses, whose lengths are not a big issue in bilinear-style SNARK.

(Though, it might be a problem for QuickSilver---the state-of-the-art fast interactive ZK proof---where the communication overhead is high, aka non-succinct, in the length of witness.)

from sponge.