# Introduction

In the rapidly evolving field of cryptographic hashing, Poseidon has emerged as a highly efficient hash function specifically designed for zero-knowledge (zk) proof systems. These systems, which play a crucial role in maintaining privacy and security in digital transactions, demand hash functions that require minimal constraints to operate effectively. Poseidon's low constraint count has made it a popular choice, leading to its widespread implementation in various zk protocols such as Zcash, Mina, Horizen, and Scroll. The latest iteration, Poseidon2, builds upon the strengths of its predecessor by introducing several key optimizations. These enhancements aim to significantly boost performance and efficiency, addressing the growing needs of modern cryptographic applications. Poseidon2’s refined architecture not only improves computational speed but also ensures robust security measures remain intact.

This article explores the specifics of Poseidon2, presenting its sophisticated design and the innovative changes that have been implemented. By examining the underlying architecture and the practical implications of these enhancements, we aim to provide a comprehensive understanding of Poseidon2’s advancements and its potential impact on the future of cryptographic hashing in zk proof systems. Additionally, we have also implemented and integrated Poseidon2 with Halo2 for Fluent, enhancing its efficiency by a factor of 3x.

# The Poseidon Hash Function

Poseidon is a family of hash functions defined over a prime field. It has demonstrated significant efficiency in recent years, making it a preferred choice for many zk protocols. The key to its success lies in its internal permutation, based on the HADES design strategy. This strategy incorporates both full and partial nonlinear rounds, optimizing the balance between security and computational cost. Poseidon's hash function is intricately designed based on the HADES strategy, employing a mixture of full and partial nonlinear rounds. It leverages an efficient Sbox and a fixed MDS matrix as its linear layer. Full Sbox layers provide comprehensive security, while partial Sbox layers ensure computational efficiency. This design makes Poseidon flexible, allowing customization based on field sizes and the number of Sboxes. Poseidon supports various security levels, including 80, 128, and 256 bits, ensuring strong resistance to collision and preimage attacks.

**Definition (Sbox)**: A low-degree polynomial, often represented as $x^3$ or $x^5$, ensuring efficient yet secure nonlinear transformation.

**Definition (MDS Matrix)**: Maximum Distance Separable (MDS) is a fixed matrix used as the linear layer to provide diffusion and resist differential and linear attacks. The properties of the MDS matrix are as follows:
* **Maximum Distance Separable**: Ensures maximum diffusion, which is critical for security in cryptographic functions.
* **Distinct Elements**: The requirement for pairwise distinct entries ensures the matrix's uniqueness and validity.
* **Non-Zero Sums**: Prevents division by zero, maintaining the integrity of the matrix.

# Evolution of SPN (Substitution Permutation Network)

Poseidon's development is rooted in the evolution of SPN, with notable predecessors including SHARK (1996), Zorro (2013), LowMC (2015), and HADESMiMC. These iterations have progressively enhanced the efficiency and security of cryptographic hash functions.

Figure 1: SPN (e.g., SHARK in 1996)

Affine Layer is a combination of a linear transformation and addition of constants. Identity Linear Layer is a special form of linear layer.

* **No Linear Transformation**: The linear part of the Affine Layer is effectively the identity matrix, meaning it does not change the input.
* **Constant Addition**: Constants are added to the state, usually derived from a pre-defined sequence or derived from some randomness.

Figure 2: P-SPN (e.g., Zorro in 2013 and LowMC in 2015)

A crucial component of Poseidon's architecture is the linear layer, implemented using a MDS matrix. An MDS matrix with elements exists if certain conditions are met, ensuring optimal properties for diffusion in cryptographic applications. The MDS matrix is vital for countering differential and linear attacks, providing a robust linear layer that enhances the overall security of the hash function.

## Construction of Hades: The Poseidon Hash Function
Poseidon employs an efficient permutation structure, optimizing both security and performance. It balances the use of full and partial Sbox layers to achieve a high level of security without compromising on computational efficiency. The Poseidon permutation's round function comprises three main components:
* AddRoundConstants (ARC)
* SubWords (Sbox)
* MixLayer (M)

The design involves rounds with full Sbox layers and rounds with partial Sbox layers.

Figure 3: HADES (e.g., HADESMiMC) (used in Poseidon)

For cryptographic applications, Poseidon uses two types of Sboxes:
* **α-power Sbox**: Defined by α, where is the smallest positive integer such that $Sbox(x)=x^α$.
* **Inverse Sbox**: We consider the inverse $Sbox(x)= x^{-1}$ (under the assumption Sbox(0)=0).

These Sbox $x^5$ is suitable for two of the most popular prime fields in zk applications, concretely the prime subfields of the scalar field of the BLS12-381 and BN254 curves.

## Sponge/Squeeze Structure
The sponge/squeeze structure is fundamental to Poseidon's operation. Poseidon builds on these advancements, utilizing the sponge/squeeze structure to absorb data and generate a fixed-size output. It takes in data into its internal state and produces the final output through a carefully designed squeezing process.

- Absorbing Phase: Input data is combined with the internal state in chunks, each influencing the internal state through permutation.
- Squeezing Phase: The internal state, after absorbing all input data, produces the final output, such as a hash value.

This structure ensures thorough mixing and diffusion of the data, enhancing security.

Figure 4: Sponge hash construction (P is the Poseidon permutation, width of 𝑟 + 𝑐 elements, adjust 𝒄 according to security level and field size where 𝑟 message elements are added per call 𝑐 elements remain untouched)

Figure 5: High-Level of the Poseidon Hash Function

# Enhancements in Poseidon2
Poseidon2 introduces several key enhancements aimed at improving the performance and efficiency of the original Poseidon hash function. These changes include the addition of a new linear layer at the beginning of the permutation, different linear layer matrices, and round constants applied only to the first word in internal rounds.

## Key Observations During the Design of Poseidon2

- Cost of MDS Matrices: MDS matrices are secure but expensive, leading to higher computational costs.
- Efficiency Improvements: Poseidon2 aims to reduce the number of multiplications in the linear layer by up to 90% and the number of constraints in Plonk circuits by up to 70%.

These changes significantly enhance Poseidon2's efficiency, making it more suitable for practical applications. They do not propose changes to the original permutation, nor do they propose a new security analysis for it. Instead, their modification, Poseidon2, can be thought of as a new and optimized version of Poseidon.

## Key Enhancements
- **Additional Linear Layer**: Introduces an additional linear layer at the beginning of the permutation, enhancing initial diffusion.
- **Different Linear Layer Matrices**: Uses different matrices for external and internal rounds, optimizing performance.
- **Selective Round Constants**: Applies round constants only to the first word in internal rounds, reducing computational overhead.

These enhancements aim to make Poseidon2 faster and more efficient in recent proof systems. While Poseidon's MDS matrices offer excellent statistical security, they are computationally expensive. Poseidon2 seeks to find a more efficient matrix that maintains the same level of security but is cheaper to compute and easier to implement.

Figure 6: Poseidon (left) and Poseidon2 (right) with changes in red!

## Full Round of Poseidon2 through $M_\epsilon$

While the original Poseidon uses the same expensive MDS matrix in each linear layer, in Poseidon2 they use a fixed matrix for the external linear layers and another matrix for the internal linear layers. For the external linear layers (full round), they use the matrix $M_\epsilon=circ(2⋅M_4,M_4,…,M_4 )∈F_p^{t×t}$.

Here, t×t circulant matrix is given by $circ(c_0,c_1,…,c_{t-1})$ and defined by


Here, multiplication by $M_4$ needs 14 operations (both additions and multiplications) while multiplication by $M_\epsilon$ needs only 5t operations in total. At first sight, the multiplication of a dense t×t circulant matrix with a t-element vector may seem to need a number of operations in $O(t^2)$. However, with $R=F_p [X]/(X^t-1)$ denoting the ring of univariate polynomials modulo $X^t-1$, note that there is an isomorphism between R and t×t circulant matrices.

## Performance Comparison

Benchmarks conducted in Rust show that Poseidon2 achieves up to a 4x improvement in performance compared to the original Poseidon for 32-bit primes. The reduction in circuit constraints further highlights Poseidon2's optimized performance.

<message>
<text>
<table>
<thead>
<tr>
<th>Permutation</th>
<th>p≈2^255(2-to-1)</th>
<th>p≈2^64(2-to-1)</th>
<th>p≈2^31(2-to-1)</th>
</tr>
</thead>
<tbody>
<tr>
<td>Poseidon</td>
<td>16.99</td>
<td>7.00</td>
<td>15.01</td>
</tr>
<tr>
<td>Poseidon2</td>
<td>6.49</td>
<td>2.06</td>
<td>2.09</td>
</tr>
</tbody>
</table>
</text>
</message>

Table 1: Benchmarks in Rust and timings in microseconds

## Benchmarks and Timings
Poseidon2's performance improvements are evident in the reduced timings for various operations, showcasing its enhanced efficiency. These benchmarks confirm that Poseidon2 is consistently faster, making it a superior choice for cryptographic applications.

Figure 7: Comparison between Poseidon, Neptune, GMiMC, and Poseidon2 for 255-bit prime

Figure 8: Comparison between Poseidon, Neptune, GMiMC, and Poseidon2 for 64-bit prime

Poseidon2 is consistently faster, achieving up to 4x improvement for 32-bit primes.

## Circuit Constraints
Poseidon2's optimizations result in a significant reduction in the number of operations and circuit constraints needed for the linear layers. This makes it more efficient for use in proof systems like Plonk. For Constraints in Plonk Circuits,

* **Poseidon**: We assume the use of 2-fan-in gates. The arithmetization in Plonk is then similar to the plain computation, with various small differences. It requires 8 constraints for each $M_4$ computation and t constraints for finalization, totaling $8(t/4) + t = 3t$ constraints.
* **Poseidon2**: Significantly reduces the constraints, highlighting its efficiency improvements (i.e., $t*R_F+R_P-t+1$ constraints of degree d).

These reductions underscore Poseidon2's advantage in minimizing computational overhead while maintaining security. These changes decrease the number of multiplications in the linear layer by up to 90% and the number of constraints in Plonk circuits by up to 70%.

Figure 9: Number of operations and Plonk constraints needed for the linear layers of Poseidon and Poseidon2, where $p ≈ 2^{64}$.

# Enhancing Proof Efficiency in Fluent's VM with Poseidon2

Fluent ([fluentlabs.xyz](https://)) has opted to use the Poseidon hash function for its virtual machine (VM) due to its SNARK-friendly properties. Poseidon is particularly advantageous in the context of zk proofs because it is designed to be efficient both in terms of computation and proof generation. Compared to traditional hash functions like Keccak, Poseidon significantly reduces the complexity of constructing proofs. This efficiency is critical in applications requiring scalable and secure proof systems, making Poseidon an ideal choice for Fluent's VM architecture.

With the advent of Poseidon2, an improved version of the original Poseidon hash function, Fluent has an excellent opportunity to enhance its prover side capabilities. Poseidon2 offers even better performance and security features, making the proof construction process more efficient. The migration from Poseidon to Poseidon2 is anticipated to provide substantial benefits, including faster proof generation times and reduced computational overhead. This upgrade not only improves the overall efficiency of Fluent's VM but also reinforces the security and scalability of the system, positioning it for future advancements and increased user trust.

# Conclusion

Poseidon2 represents a significant advancement in SNARK-friendly hashing, offering enhanced efficiency and speed without compromising on security. Its innovative design, leveraging the HADES strategy and introducing key optimizations, makes it a powerful tool for cryptographic applications. By reducing computational costs and circuit constraints, Poseidon2 sets a new standard for performance in zk proof systems.

As cryptographic needs continue to evolve, Poseidon2's improvements ensure it remains at the forefront of efficient and secure hashing solutions. Whether in zk protocols or other cryptographic applications, Poseidon2's blend of security, efficiency, and performance makes it a valuable asset in the realm of modern cryptography.

# References
1. Algebraic Cryptanalysis of HADES Design Strategy: Application to POSEIDON and Poseidon2, https://eprint.iacr.org/2023/537.pdf, Apr 2023.
2. Poseidon2: A Faster Version of the Poseidon Hash Function, https://eprint.iacr.org/2023/323.pdf, Mar 2023.
3. Horst Meets Fluid-SPN: Griffin for Zero-Knowledge Applications, https://eprint.iacr.org/2022/403.pdf, Mar 2022.
4. Poseidon: A New Hash Function for Zero-Knowledge Proof Systems, https://eprint.iacr.org/2019/458, May 2019.
5. Horizen - The Horizen Foundation, https://github.com/horizenofficial (Accessed on 18 May 2024).
6. Poseidon2 with Halo2. https://github.com/fluentlabs-xyz/poseidon2, May 2024.