#78 - Poseidon: Hashes for Zero-Knowledge Proofs (A Guide for Engineers)

Poseidon2, explained: how its sponge + partial rounds make circuits fast

Stanford Blockchain Review
Volume 8, Article No. 8

✍🏻 Author: Billy Gao — Stanford Blockchain Club
Poseidon Network

⭐️ Technical Prerequisite: Intermediate

If you have worked with SNARKs or zkVMs, you have probably heard of Poseidon. The reason behind is simple: traditional cryptographic hash functions like SHA256 are catastrophically expensive to compute inside arithmetic circuits. Every bitwise operation, every XOR, every rotation translates to thousands of constraints in the proof system. Poseidon solves this by redesigning the hash function from the ground up to work natively in finite fields.

The core insight behind this design is that proof systems like Groth16, Plonk, or STARKs all work over finite fields (arithmetic modulo some large prime). So instead of bit-level operations in this setting, Poseidon operates directly on field elements. As such, the state is no longer a sequence of bits, but rather a vector of elements in F_p (for example p is 2²⁵⁴ for BN254 curves).

Sponge Construction

Poseidon uses the sponge construction. The idea is to maintain an internal state larger than both the input and output, then squeeze entropy through it. You have a state of width t field elements, and it is partitioned into a rate r and a capacity c where t = r + c. The rate is how many field elements you can absorb per iteration, while the capacity provides a security margin.

For instance, assume the case of Poseidon with t=3, so the state is three field elements. Setting r=2 and c=1 (absorb two field elements per round while one element stays as the capacity), and suppose we want to hash four field elements: [a, b, c, d]. The state starts at [0, 0, 0].

During absorption, we take the first chunk [a, b] and add it into the rate portion: state becomes [0+a, 0+b, 0] = [a, b, 0]. Then we apply the permutation function P to mix everything: state becomes [P₀, P₁, P₂] where those values depend on the complex mixing of a and b. Now we absorb the second chunk [c, d]: state becomes [P₀+c, P₁+d, P₂]. Apply the permutation again to get [Q₀, Q₁, Q₂].

Once everything is absorbed, we switch to squeezing. We output the first r=2 elements [Q₀, Q₁] as the hash. If we needed more output (say for a 3-element hash), we would apply the permutation again and output another r elements. The capacity c never gets directly exposed, which is what gives resistance to length extension attacks and maintains collision resistance. An attacker cannot efficiently reconstruct the internal state from the output because they could only see r out of t elements.

The Permutation Function

The heart of Poseidon is its permutation function, which gets applied repeatedly during both absorption and squeezing. Each round of the permutation consists of three layers. First is AddRoundConstants, where we add a predetermined constant to each state element. This breaks symmetry and prevents slide attacks. Second is SubWords, which applies a power map (S-box) to each element: we compute x^α where α is typically 5 or 7. This provides the only nonlinear component and is where most of the constraint cost comes from. Third is the MixLayer, which multiplies the state vector by a chosen MDS (Maximum Distance Separable) matrix to ensure that changes diffuse across the entire state.

Here’s what a full round actually looks like with numbers. Let’s say the state is [100, 200, 300] and α=5.

AddRoundConstants: Add predetermined constants, say C = [42, 17, 99]. The state becomes [100+42, 200+17, 300+99] = [142, 217, 399].

SubWords: Apply the S-box to each element. State becomes [142⁵, 217⁵, 399⁵]. These are huge numbers but remember everything is mod p. This is the nonlinear layer and costs one constraint per element in most SNARK systems.

MixLayer: Multiply by an MDS matrix M. For t=3, this might look like: M = [[2, 1, 1], [1, 2, 1], [1, 1, 2]]. If the state after SubWords was [s_0, s_1, s_2], the new state becomes: [2*s_0 + 1*s_1 + 1*s_2, 1*s_0 + 2*s_1 + 1*s_2, 1*s_0 + 1*s_1 + 2*s_2]. Each output element is a weighted sum of all input elements, ensuring complete diffusion.

The breakthrough in the original Poseidon design was the concept of partial rounds. Instead of applying the expensive S-box to all t state elements in every round, we can apply it to just one element for most rounds while still maintaining security. The structure is R_f/2 full rounds at the beginning, then R_p partial rounds in the middle where only the first state element gets the S-box, then R_f/2 full rounds at the end. (R_f refers to the total number of full rounds, where R_p refers to partial rounds)

For a typical configuration we might have 8 full rounds total (4 at the start, 4 at the end) and 56 partial rounds in the middle. So a partial round would look the same except in SubWords, we only compute state[0]^5 and leave state[1] and state[2] unchanged. This approximately halves the constraint count because the S-box is where all the cost is (80 S-box operations instead of 192 if all rounds were full).

The initial 4 full rounds ensure that by the time we hit the partial rounds, every state element is already a highly nonlinear function of the inputs. Each partial round then adds one more layer of nonlinearity to state[0], with the MDS matrix spreading that change across all positions. By the time of 56 partial rounds, the S-box has been applied 56 times to state[0], with the MDS matrix diffusing that nonlinearity to state[1] and state[2]. The final 4 full rounds then add another complete layer of mixing.

Poseidon2 Improvements

Poseidon2, published in 2023, takes this further with several optimizations. The main innovation is how the MDS matrix is constructed. The original Poseidon used a single MDS matrix throughout, but this matrix multiplication is actually pretty expensive in constraints because we need t² multiplications per round. Poseidon2 splits this into internal and external diffusion layers.

For the external rounds (the full rounds at the beginning and end), Poseidon2 uses a matrix M_E that is relatively dense but only applied infrequently. For the internal rounds, it uses a much sparser matrix M_I that is often circulant or nearly circulant, such that the matrix-vector product can be computed with far fewer field multiplications. Security analyses show that it is viable to use these cheaper matrices for the partial rounds because the full rounds at the boundaries provide enough mixing to prevent attacks.

The round constants are also generated differently in Poseidon2, using a more robust method that eliminates potential biases. Combined with improved cryptanalysis that allows for fewer total rounds while maintaining 128-bit security, Poseidon2 typically gives us 2-4x speedup in proving time compared to original Poseidon.

Barretenberg and Noir

Barretenberg is Aztec’s proving backend, it is a C++ library that implements various proof systems with custom gates and lookup tables. At this level, we are thinking about representing field operations as polynomial constraints.

For Poseidon2 in Barretenberg, each S-box operation can be done in a single custom gate that handles the multiplication chain efficiently. The matrix multiplications get compiled into linear combinations which are significantly cheaper in the constraint system. The result is that hashing 2 field elements with Poseidon2 might cost around 150-200 constraints total, whereas implementing SHA256 over the same field would cost hundreds of thousands.

Noir is the high-level language that compiles down to Barretenberg circuits. At the Noir level, we are not thinking about constraints directly but instead writing what looks like normal Rust code. But under the hood, the Noir compiler is making choices about how to represent them as arithmetic circuits. When we call the standard library’s Poseidon2 hash function, the compiler emits the optimized Barretenberg-specific implementation.

The great thing about this is that we can call std::hash::poseidon2::hash([x, y]) and get a cryptographically secure hash that is practical to prove. This enables things like Merkle trees in zkVMs, making the difference between a proof that takes seconds versus hours.

Why Poseidon2 is Secure

The security of Poseidon2 rests on a fundamentally different hardness assumption than traditional hash functions like SHA256. When you try to break Poseidon2 (finding two inputs that produce the same hash, or computing an input that hashes to a specific value) you end up needing to solve a system of multivariate polynomial equations over a finite field. This is the MQ problem (Multivariate Quadratic), which is NP-hard in the general case. The S-box operation raising elements to the 5th or 7th power creates these high-degree polynomial relationships. After just 8 full rounds, the output is a polynomial of degree 5⁸ = 390625 in terms of the input. Even with quantum computers and Grover’s algorithm, solving these systems at the scale of Poseidon would take far longer than the available time.

The MDS matrix plays a crucial role with its Maximum Distance Separable property guaranteeing that if you change k input positions, at least t-k+1 output positions must change. For the t=3 case, changing even one input element forces all three state elements to change after the MDS layer. This prevents differential cryptanalysis, where an attacker tries to track how specific input differences propagate through the function. With Poseidon, a single field element difference in your input affects all state elements after just one round, and the probability of finding a differential characteristic that holds through all rounds drops exponentially.

The partial round structure might seem like it would weaken security, but the sandwich design is what makes it work. An attacker trying to find a collision or preimage would need to simultaneously solve through the initial full rounds, track 56 rounds of partial-round diffusion, and invert through the final full rounds. The combined complexity of this meets the 128-bit security target.

The sponge construction adds another layer of security through the capacity. When you squeeze out the hash, you are only seeing r out of t state elements with the remaining c elements staying hidden. An attacker who wants to forge a hash or extend it would need to guess the capacity elements, with c around 254 bits (one field element), that’s 2¹²⁷ operations.

The specific attacks that cryptographers worry about for Poseidon include Gröbner basis attacks (trying to solve the polynomial system directly), algebraic attacks (looking for low-degree relationships), differential cryptanalysis (tracking how differences propagate), and invariant subspace attacks (finding symmetries in the permutation). The round constants are specifically chosen to break symmetries, the degree growth from the S-boxes makes Gröbner basis methods infeasible at 128-bit complexity, and the MDS diffusion kills differential characteristics. The original Poseidon paper included extensive cryptanalysis and added a security margin with the recommended parameters being stronger than the bare minimum needed.

Poseidon2’s security level is calibrated to 128 bits, which means an attacker with unlimited classical computing power would need about 2¹²⁸ operations to break it. That’s the same security level as AES128. With quantum computers, Grover’s algorithm could reduce this to 2⁶⁴, which is why some protocols are already planning for 256-bit security parameters for post-quantum resistance. But for current applications, 128 bits is considered the minimum acceptable security level for financial and cryptographic systems.

The Ecosystem

Poseidon2 is becoming a default zk-friendly hash in many modern zkVM/proving stacks, especially where Merkleization and recursion dominate runtime. SP1 uses Poseidon2 over the BabyBear field (with Plonky3-aligned parameters), and RISC Zero has adopted Poseidon2 in parts of its recursion pipeline. Plonky2 uses a Goldilocks-field Poseidon variant, while Plonky3 commonly uses Poseidon2 and supports multiple field/hash configurations. The exact parameters and optimizations differ, but the core idea remains the same.

The standardization around Poseidon2 is one of those quiet infrastructure wins that makes the entire ZK ecosystem viable. Without SNARK-friendly hash functions, you simply couldn’t build practical zkVMs or zkRollups. With them, you can prove execution of millions of instructions in reasonable time.