Poseidon2 is a SNARK-friendly cryptographic hash designed to be efficient inside prime-field arithmetic circuits. It follows the Poseidon2 paper and refines the original Poseidon hash.

This implementation includes:

A sponge construction over the BN254 scalar field following the (draft) C2SP Poseidon Sponge spec based on the Duplex Sponge model.
The Poseidon2 permutation, i.e. the round function used by the sponge.
Circuit custom gate relations that enforce the permutation’s correctness.

The Sponge Construction

The sponge absorbs input elements into an internal state, applies permutations, and squeezes output elements.

Sponge constants.

State size (t): 4 field elements
Rate (r): 3 elements
Capacity (c): 1 element

Details

Let the input be

\[ \mathbf{a} = (a_0, a_1, \dots, a_{N-1}). \]

Partition it into blocks of size \(r=3\):

\[ B_j = (a_{3j},, a_{3j+1},, a_{3j+2}) \quad\text{(pad missing entries with 0)},\qquad m = \left\lceil \frac{N}{3}\right\rceil . \]

Padding

In Poseidon paper, the padding scheme for variable input length hashing suggests padding with \( 10^\ast\).

"Domain Separation for Poseidon" section (see 4.2 in Poseidon) suggests using domain separation IV defined as follows

\[ \mathrm{IV} = (\texttt{input_length}^{64}) \]

Initialize the state:

\[ \mathbf{s}^{(0)} = (0,0,0,\mathrm{IV}). \]

Since we only use Poseidon2 sponge with variable length inputs and the length is a part of domain separation, we can pad the inputs with \( 0^\ast \), which would not lead to collisions (tested here).

Note that we initialize \( \mathrm{IV} \) as a fixed witness. It ensures that the first invocation of the Poseidon2 permutation leads to a state where all entries are normalized witnesses, i.e. they have multiplicative_constant equal 1, and additive_constant equal 0.

Absorb phase

For each block \(j=0,\dots,m-1\),

\[ \mathbf{s}^{(j+1)} = P\left(\mathbf{s}^{(j)} + (B_j,0)\right), \]

where \(P\) is the Poseidon2 permutation and \((B_j,0)\) is an array of size \( 4 \) with \(r\) state elements and a \(0\) capacity limb.

Squeeze (single output)

After absorption, produce one output field element via one duplex step:

\[ y_0 = \big(P(\mathbf{s}^{(m)})\big)_0. \]

The Poseidon2 Permutation

Each permutation consists of:

Initial linear layer: multiply state by external matrix \(M_E\). Corresponds to matrix_multiplication_external method.
4 External rounds (full S-box):
- Record the state and the correspoding round constants \( c_{0}^{(i)} \) into a Poseidon2 External Gate.
- Natively compute the next state.
- Re-write the state with the new witnesses.
- After the final round, record the computed state in the next row of the Poseidon2 external gates block, as it is required for the custom gate relation.
56 Internal rounds (partial S-box):
- Record the state and the correspoding round constants \( c_{0}^{(i)} \) into a Poseidon2 Internal Gate.
- Natively compute the next state.
- Re-write the state with the new witnesses.
- After the final round, record the computed state in the next row of the Poseidon2 internal gates block,
Final external rounds (same as step 2).

Note that in general, step 1 requires 6 arithmetic gates, the steps 2-4 create total number of rounds + 3 gates. Hence a single invocation of Poseidon2 Permutation results in 73 gates.

External Matrix

As proposed in Section 5.1 of Poseidon2 paper, we set

\[ M_E = \begin{bmatrix} 5 & 7 & 1 & 3 \\ 4 & 6 & 1 & 1 \\ 1 & 3 & 5 & 7 \\ 1 & 1 & 4 & 6 \end{bmatrix} \]

Internal Matrix

\[ M_I = \begin{bmatrix} D_1 & 1 & 1 & 1 \\ 1 & D_2 & 1 & 1 \\ 1 & 1 & D_3 & 1 \\ 1 & 1 & 1 & D_4 \end{bmatrix} \]

Implementation note: The code stores internal_matrix_diagonal_minus_one[i] = D_i - 1 (not the actual diagonal values \(D_i\)). This is because the algorithm computes \(v_i = (D_i - 1) \cdot u_i + \text{sum}\) where \(\text{sum} = u_1 + u_2 + u_3 + u_4\), which equals \(D_i \cdot u_i + (\text{sum of other elements})\).

Constants

The constants are generated using the sage script authored by Markus Schofnegger from Horizen Labs.

Security Level

Based on Section 3.2 of Poseidon2 paper.

Given \( R_P = 56 \), \( R_F = 8\), \( d = 5\), \( \log_2(p) \approx 254 \), we get \( 128 \) bits of security.

Custom Gate Relations

For an external round with state \( \mathbf{u}=(u_1,u_2,u_3,u_4) \), define \( \mathbf{v}=M_E\cdot\mathbf{u}\). Poseidon2 External Relation enforces that the permuted values equal the values in the next row (accessed via shifts):

\[ v_k = w_{k,\mathrm{shift}} \qquad \text{for } k \in \{1,2,3,4\}. \]

We encode four independent constraints under a selector \( q_{\mathrm{poseidon2_external}}\) and aggregate them with independent challenges \( \alpha_i = \alpha_{i, Poseidon2_ext}\) from SubrelationSeparators:

\[ q_{\mathrm{poseidon2_external}}\cdot \Big( \alpha_0\big(v_1 - w_{1,\mathrm{shift}}\big) + \alpha_1\big(v_2 - w_{2,\mathrm{shift}}\big) + \alpha_2\big(v_3 - w_{3,\mathrm{shift}}\big) + \alpha_3\big(v_4 - w_{4,\mathrm{shift}}\big) \Big) = 0. \]

To ensure that the relation holds point-wise on the hypercube, the equation above is also multiplied by the appropriate scaling factor arising from GateSeparatorPolynomial.

Internal rounds follow the same pattern, using \( M_I \) and the partial S-box on the first element.

Number of Gates

Hashing a single field element costs \( 73 \) gates. As above, let \( N > 1\) be the input size. Define \( m = \lceil N/3 \rceil \) and let \( N_3 = N\pmod{3} \). The number of gates depends on the number of padded fields equal to \( N_3 \). If \( N_3 = 0\), we get

\[ 1 + 73\cdot m + 3\cdot (m - 1) \]

gates, otherwise we get

\[ 1 + 73\cdot m + 3\cdot (m - 2) + N_3.\]

According to TACEO blog post Poseidon{2} for Noir, a single permutation cost for \( t = 4 \) implemented without Poseidon2 custom gates is \( 2313 \) gates.