Overwrite Mode in Sponge-Based Permutations

By Héctor and Tomer. This note comes out of a discussion with Markus, Tomer, Al, and Jordi.

Diagram comparing Poseidon's standard sponge mode with the overwrite mode, where the four top outputs are rerouted to the four bottom inputs of the next permutation

What others do

Poseidon is a hash function instantiating a sponge construction using the Poseidon $^\pi$ permutation. The standard way to use the sponge construction is to carry over the output of one permutation call as input to the next. A widely used optimization, sometimes known as overwrite mode, is to truncate the top part of the permutation and only carry over the lower part to the next call.

What we do

In Polygon zkEVM, we are using a slightly modified version of this construction. The modification is in how we use the output of one permutation call as input to the next one. Rather than preserving the order of inputs between permutations, we carry over the four topmost elements of the last permutation output to be the bottom four elements of the next permutation’s input.

Where do we do It

Linear Hashing. Here we just need to squeeze out four output elements and therefore only one permutation call is made in the squeezing phase. Also, by continuosly linear hashing distinct leaf elements and hashing together the result of distinct levels we can build a Merkle tree.
Fiat-Shamir’ing things. In this scenario, we may need more than four output elements. To this end, we make as many permutation calls as necessary squeezing out four output elements each time until the desired number of outputs is achieved.

Is it safe to do it?

Yes, assuming Poseidon $^\pi$ is a secure permutation. To see this, observe that the routing of output wires can be achieved by multiplying the output vector with a permutation matrix. Then, this permutation matrix can be absorbed into Poseidon $^\pi$ ’s last MDS matrix without affecting its cryptographic properties. Then, employing this new variant of Poseidon $^\pi$ in overwrite mode results in our construction.

Another approach to this question, providing a more general result, is to consider that if the four topmost elements can be distinguished from the bottom four elements it implies that they have different distributions; and therefore, at least one of these sets is not uniformly distributed. This in turn implies that the unmodified sponge function is insecure.