Written by Markus Schofnegger, [e-mail]

Efficient hash functions play a major role in modern zero-knowledge settings. One of these hash functions, Poseidon, has found use in many of the currently used protocols, including Zcash and Mina. However, it has certain disadvantages. We identify those and present Poseidon2, a faster version of Poseidon.

This work is the result of a collaboration between Horizen Labs, Ethereum Foundation, and Ponos Technology. For more details we refer to the full paper.

Hash Functions in ZK Settings and Poseidon

Hash functions for ZK settings are specifically designed to be efficient in use cases for computational integrity. Part of this efficiency comes from a simpler polynomial description when writing down all the functions needed to compute a single hash output.

In the last couple of years, many new such hash constructions emerged, including Poseidon, Rescue, Griffin, and Anemoi. Out of these, Poseidon is arguably still the most popular one, finding its use in many well-known ZK protocols such as our ginger-lib library used in our chain network. It often also serves as the workhorse in implementations of STARK-based frameworks, one recent example being Plonky2 by Polygon.

Poseidon needs a comparatively small number of constraints in many proving systems and is thus often much more efficient than traditional hash functions like AES-based approaches, SHA-2, and SHA-3. However, its plain performance (i.e., the plain hashing performance outside of the circuit) is a bottleneck. This is mostly attributed to the fact that Poseidon uses many expensive linear layers, which in symmetric cryptographic primitives are often implemented with matrix multiplications. Indeed, the original Poseidon hash function is responsible for almost half of the computational resources needed for a Plonky2 proof.

What is Poseidon2 ?

Poseidon2 is a modification of Poseidon which manages to solve the issue identified above by making individual subcomponents more efficient and thus laying a larger focus on plain performance. Just like Poseidon, it is usable as a sponge hash function, but in the paper we also recommend using a compression mode for settings where only k-to-1 compression is needed. For example, this is the case in a generic construction of a Merkle tree. We define the compression mode by using a classical truncated approach including a feed-forward operation:

Another advantage of Poseidon2 is its simplicity. Indeed, Poseidon2 achieves maximum performance without needing the original Poseidon's efficient implementation transformation. This means that it is also more memory-efficient and does not require the storage of many different matrices for the partial rounds.

How does Poseidon2 work?

The general structure of Poseidon2 is the same as in the original Poseidon. Full nonlinear layers with S-boxes applied to the entire state are used at the beginning and at the end, while partial nonlinear layers with S-boxes only applied to the first state element are used in the middle of the permutation.

The main difference between Poseidon and Poseidon2 lies in its linear layers. For Poseidon2, we took inspiration from recent symmetric constructions and from hardware-focused lightweight cryptography. This allows us to find matrices which are particularly efficient to compute both in plain and when representing them by constraints. In particular, our new matrices require only a short chain of additions in order to be computed, significantly reducing both the number of multiplications and the number of reductions.

In more detail, while the original Poseidon uses the same expensive MDS matrix in each linear layer, in Poseidon2 we use a fixed matrix for the external linear layers and another matrix for the internal linear layers. For the external linear layers, we use the matrix

where we define

This is inspired by recent work in lightweight symmetric cryptography, where the goal is to minimize the number of XOR gates in e.g. a hardware implementation. The matrix M₄ is MDS and thus has a branch number of 5. We make use of a proof in the original Griffin paper which states that the branch number of M_E is t/4 + 4 for a t-element state.

The advantage of M_E is that it can be computed by using only 5t operations, and thus the scaling is linear in t (as opposed to a classical random MDS where it is quadratic). To see this, consider an input vector x = (x₀, x₁, x₂, x₃) and let

Then

for an output vector x'=(x'₀, x'₁, x'₂, x'₃). This finalizes the computation of x' = M₄ ⋅ x for 4 elements of the state, needing 12 opeartions. Depending on efficiency, the constant multiplications above can be replaced by additions. This may be helpful when dealing with large primes, for example.

We repeat this procedure for every other 4-element part of the state, requiring 12 ⋅ t/4 = 3t operations in total. To get the entire multiplication by M_E, we need another 2t additions. Indeed, given the output vector x'=(x'₀, x'₁, … x'_t-1) after applying M₄ to the entire state, the final output y = (y₀, y₁, y₂,… y'_t-1) considering also circ(2 ⋅ M₄,M₄,…M₄) is given by

The internal matrix of Poseidon2 is given by

for random elements µ_i ∈ F_p \ {0, 1} such that the matrix is invertible and no arbitrarily long subspace trails exist. We suggest using small coefficients to make the constant multiplications more efficient. Note that the multiplication by M_I requires only 2 t - 1 additions and t multiplications for a state of t elements. Indeed, computing the sum Σ of all input elements requires t-1 additions, and storing µ_i - 1 we can then add (µ_i - 1) ⋅ x_i + Σ to each original input element to obtain the final output.

We also change the definition of the round constant addition. In the original Poseidon only a single addition in each partial round is needed with the efficient implementation, whereas we directly make this change in Poseidon2 without requiring the efficient representation.

The original Poseidon is on the left side, the new Poseidon2 is on the right side. Changes are highlighted in red.

While it may seem that the security of Poseidon2 is weakened after these changes, this is not the case. Indeed, the matrices in the external (full) rounds mainly have an impact on the statistical security of the construction. In symmetric cryptography, statistical security is often argued by using the wide trail strategy and combining full nonlinear layers with matrices with high branch numbers. The branch number of a matrix essentially describes the quality of its diffusion, and Poseidon uses so-called maximum distance separable (MDS) matrices to achieve the highest possible branch number.

We determined that this is not needed in Poseidon2, and a more efficient matrix with slightly lower branch numbers is equally secure. First, the probability of having a certain output difference Δ₀ given an input difference Δ_I is

and the differential probability of our degree-d monomial S-box is upper-bounded by (d - 1)/ p for a prime number p. Then, using the matrix M_E shown above for the external rounds, we achieve a sufficiently high security against (classical) statistical attacks. This is measured by considering pairs of consecutive external rounds, following the wide trail strategy. With the branch number of M_E being (t / 4) + 4= t' + 4, as determined above, we have that

and hence three pairs of two consecutive external rounds are sufficient even with our more efficient matrix.

Another major attack vector against arithmetization-oriented schemes is the class of algebraic attacks. To gain resistance against these approaches, the polynomial representations of the scheme have to be dense and reach the maximum degree. We determined that this is the case for the new matrices chosen for Poseidon2. In particular, we determined that the maximum number of monomials of total degree ≤ d in n_v variables

is always reached in Poseidon2. This is supported by multiple practical experiments using different instances of Poseidon2.

Moreover, we analyzed Gröbner basis attacks, which consist of building an equation system in the unknown variables (for example, an unknown preimage to a known hash output) and solving this system. For this purpose, we compared the resistance of the original Poseidon to the resistance of Poseidon2 with our new matrices, and we observe that the difference between these two is negligible. Indeed, the solving times and Gröbner basis computation times were the same.

Combining the resistance against statistical attacks and the unchanged resistance against algebraic attacks allows us to use the same round number formula as in the original Poseidon. Hence, the round numbers are the same, which means that the number of S-boxes (and the number of nonlinear constraints in general) is also the same in original Poseidon instances and their equivalent Poseidon2 counterparts.

Applications

We recommend using Poseidon2 in all use cases where Poseidon has proven its efficiency in the last couple of years. Without increasing the number of rounds or having any other disadvantages, Poseidon2 gives a performance boost by a factor of up to 4. This makes Poseidon2 the currently fastest hash function optimized for zero-knowledge applications without using lookups.

In particular, together with the newly recommended compression mode, Poseidon2 is significantly more efficient for Merkle tree computations. We see an improvement over the original Poseidon in sponge mode by a factor of up to 5, while at the same time requiring around 30% fewer constraints. The fact that Poseidon2 scales almost linearly with the state size makes it also an attractive choice for larger compression ratios in Merkle trees, such as 4-to-1.

Conclusion

With Poseidon2, we improve the state of the art in fast hashing for zero-knowledge use cases. We achieve our goals by optimizing various internal components of the original Poseidon hash function, and we also show that our modifications do not decrease the advertised security level.

Further Reading

Poseidon: https://eprint.iacr.org/2019/458
Poseidon2: https://eprint.iacr.org/2023/323
Rescue: https://eprint.iacr.org/2019/426
Griffin: https://eprint.iacr.org/2022/403
Anemoi: https://eprint.iacr.org/2022/840
plonky2: https://polygon.technology/blog/introducing-plonky2