algebraic hashing for SNARK circuits

Poseidon and Poseidon2 — the algebraic hash that lives inside the SNARK.

Sponge-mode hashes built from an SPN round function over a prime field: every operation is a field operation, not a bitwise one. A single call compiles to roughly 50–300 PLONK constraints versus roughly 25 000 for SHA-256 — two orders of magnitude cheaper in-circuit.

Poseidon (2021) is the original construction. Poseidon2 (2023) is a faster revision with a streamlined linear layer and a different round schedule — drop-in compatible at the protocol level, not bit-identical.

concrete instantiation Poseidon2 over BLS12-381's scalar field $F_r$, exposed as a host function under CAP-0075 on Stellar Protocol 25, with $R_F = 8$, $R_P = 56$, $\alpha = 5$, state width $t = 3$.
~50–300
constraints / call
~500×
cheaper than SHA-256 in-circuit
α = 5
S-box exponent
t = 3
state width
CAP-0075
host function

the shape

Sponge on the outside, substitution-permutation network on the inside.

A sponge construction absorbs input field elements into the rate portion of the state, runs the permutation, then squeezes a digest. The permutation is a fixed number of rounds, each consisting of add round constants → α-power S-box → MDS matrix. Full rounds apply the S-box to every state element; partial rounds apply it to one element only — the asymmetry that drops constraint count without weakening the algebraic-attack margin.

SPONGE · ARITY-2 MERKLE NODE left ∈ F_r right ∈ F_r absorb STATE · t = 3 s₀ rate s₁ rate s₂ capacity rate r = 2 · capacity c = 1 permute PERMUTATION · 64 ROUNDS R_F = 8 full · R_P = 56 partial 4 full → 56 partial → 4 full over F_r of BLS12-381 (255-bit) Horizen Labs canonical parameter set squeeze digest ∈ F_r ONE ROUND · SPN STRUCTURE + round constants s ← s + c_r FULL ROUND · R_F = 8 x → x⁵ PARTIAL ROUND · R_P = 56 one element only MDS matrix s ← M · s — diffusion next state → next round ROUND SCHEDULE · 4 + 56 + 4 4 full 56 partial — S-box on one element only 4 full
State
t = 3 field elements over $F_r$
Rate 2, capacity 1 — the arity-2 shape used to compress two children into one Merkle parent in a single permutation call.
S-box layer
$x \mapsto x^{5}$  ·  α = 5
The only nonlinear step. A degree-5 monomial — the smallest exponent coprime to $|F_r^\times|$ — keeps multiplicative depth low while leaving algebraic attacks expensive.
MDS matrix
linear · diffusion across the state
A maximum-distance-separable matrix mixes the state every round. Poseidon2 replaces Poseidon's dense MDS with a streamlined version that costs fewer field multiplications natively while preserving diffusion.

The cheap part is that every box in this diagram is a field operation. The expensive part — for SHA-256, in a circuit — is that every box is a bitwise operation, which a PLONK arithmetization has to simulate from scratch.

why it's cheap — interactive comparator

In-circuit constraint count: Merkle path of depth .

A Merkle-membership proof hashes one node per tree level. Pick a depth; see what a PLONK circuit has to spend on the path for each hash family. Order-of-magnitude figures only — the headline ratio is what matters.

Merkle depth
levels
depth 1
depth 32
–  constraints
Algebraic / SPN over $F_r$. Each Merkle level is one permutation call; the constraint count scales linearly with depth.
SHA-256 path
~25 000 / hash
 constraints
Merkle–Damgård / bitwise. Every AND, XOR, and rotation has to be re-expressed as field-arithmetic constraints inside the circuit.
ratio at this depth
~–× cheaper
Every operation in Poseidon is a field operation; every operation in SHA-256 is a bitwise operation. PLONK's gate model rewards the first and punishes the second.

Figures are the source's order-of-magnitude estimates — not measurements from a specific gadget. Poseidon2's roughly 20–30% improvement over Poseidon at the same $t = 3 / \alpha = 5$ parameters comes from a streamlined linear layer and a tighter round schedule, not from a different security target.

parameters

Concrete numbers.

Pinned by the deployment. Parameter discipline matters here — different field × state-width × round-count tuples produce incompatible hashes.

Variant
Poseidon2 (verifier) + Poseidon (legacy)
Field
$F_r$ of BLS12-381 · 255-bit
State width
t = 3 · rate 2 / capacity 1 (Merkle arity-2)
S-box exponent
α = 5 · $x \mapsto x^5$
Full rounds
R_F = 8 · 4 first + 4 last
Partial rounds
R_P = 56 · parameter-dependent
Parameter provenance
Horizen Labs canonical set · round constants & MDS
Soroban host function
Stellar CAP-0075 · Protocol 25

wiring — Merkle hash · transcript hash · host function

Three places the same Poseidon2 instance shows up.

Same permutation, same parameters, three distinct call sites. Two off-chain inside the prover's circuit; one on-chain inside the verifier's host environment. Anything else is a parameter-set bug.

In-circuit · Merkle compression
In-circuit · Fiat-Shamir transcript
On-chain · CAP-0075 host function
prover · off-chain
Tree node = Poseidon2(left, right)
Every internal node of the membership tree is the arity-2 compression of its children. The prover walks the witness path from leaf to root.
F_r · arity-2
Path → group commitment C_g
The chain of hashes reaches the public group commitment $C_g$ without revealing which leaf the prover knows. One permutation call per tree level.
scaling Depth-20 Merkle path → 20 Poseidon2 calls → roughly $20 \times 50\text{–}200 \approx 1\,000\text{–}4\,000$ constraints. The same path in SHA-256 sits near half a million.
prover · off-chain
Fiat-Shamir challenges
Every PLONK challenge — $\beta, \gamma, \alpha, \zeta$ — is drawn by hashing the transcript-so-far with Poseidon2. The verifier replays the same hashes.
F_r · transcript
Public inputs ⊕ commitments
Each absorbed message is one or more $F_r$ elements: serialised commitments, evaluations, the public input. Native field absorption — no bit decomposition.
simulation-extractability Every public input must enter the transcript before the first challenge is drawn. Skipping this has caused real proof-malleability bugs.
CAP-0075
Same permutation, on-chain
stellar_poseidon2_hash
A Soroban host function exposes the same Poseidon2 instance to verifier contracts. Identical parameter set; bit-identical digests with the in-circuit hash.
Protocol 25
Verifier-side Fiat-Shamir replay
The on-chain verifier reconstructs the challenges from the proof bytes by calling the host function — never by computing Poseidon in guest WASM.
why a host function Computing Poseidon in pure Soroban guest code costs an order of magnitude more in WASM bytecode than the host implementation. CAP-0075 makes Poseidon2 native to the runtime.

Cool/blue tint for the two in-circuit lanes — those run off-chain inside the prover. Amber for the on-chain lane — the only call site the chain pays for, on the verifier side. The red callout points at the cross-reference to PLONK's simulation-extractability requirement; the hash itself doesn't carry that risk, the way it's used does.

security

A hash that survives the curve break around it.

Two assumptions, two horizons — and unusually for this stack, both cards are green. The post-quantum card is the good news here: a Grover speedup halves the security level, it does not collapse it. The catch is that the system around the hash still falls.

classical · holding
128-bit

Collision & (second-)preimage resistance of the permutation.

Instantiated with the Horizen Labs canonical round-constant and MDS matrix set. Published analysis covers the relevant algebraic-attack families with a safety margin against the best known cryptanalysis at $R_F = 8 / R_P = 56$.

  • Algebraic attack families covered: Gröbner-basis, interpolation, higher-order differential.
  • Safety margin chosen against the best known cryptanalysis — round counts have been adjusted twice since the 2021 publication.
  • Sponge mode reduces to permutation security via the standard indifferentiability argument.
post-quantum · conjectured
~64-bit

Grover's $\sqrt{N}$ — and nothing worse — is the relevant quantum speedup.

The hash is hash-based. A CRQC finds collisions at roughly half the classical bit-security level; 128-bit classical collision resistance becomes ~64-bit post-quantum collision resistance. The permutation itself survives.

  • Grover is the only relevant quantum speedup; no Shor-style polynomial-time attack applies to a hash.
  • But the system around it does not. KZG and PLONK on BLS12-381 fall under Shor regardless of which hash the Fiat-Shamir transcript uses.
  • Migration headroom is in the state width $t$ and the digest size — not in the hash family. A wider Poseidon recovers the bit-security margin without changing the construction.

This is the opposite colour story from the BLS12-381 and PLONK sheets: there, the post-quantum card was the red one. Here both cards are green. The visual contrast — a dashed border on the post-quantum card — is between well-studied and younger: algebraic cryptanalysis of Poseidon is on a shorter timeline than half a century of analysis around SHA-256's design family.

poseidon vs poseidon2 vs sha-256

Where each hash is cheap, and where it isn't.

Three hashes, three trades. Algebraic structure is what makes Poseidon and Poseidon2 cheap inside a SNARK and slow outside it. SHA-256 is the opposite — fast on hardware, prohibitively expensive in a circuit.

Poseidon

algebraic · SPN over $F_r$
Family
algebraic · sponge + SPN
In-circuit cost
~50–300 constraints / call
Native CPU cost
slower than SHA-256 natively
PQ stance
conjectured PQ-secure
Maturity
USENIX Security 2021 · round count adjusted twice since
this page

Poseidon2

streamlined linear layer · drop-in
Family
algebraic · sponge + SPN
In-circuit cost
~20–30% cheaper than Poseidon at the same parameters
Native CPU cost
faster than Poseidon natively
PQ stance
conjectured PQ-secure
Maturity
IACR ePrint 2023 · drop-in compatible at the protocol level

SHA-256

Merkle–Damgård · bitwise
Family
Merkle–Damgård · bitwise compression
In-circuit cost
~25 000 constraints / call
Native CPU cost
fastest natively · decades of hardware acceleration
PQ stance
conjectured PQ-secure · ~64-bit Grover bound
Maturity
FIPS 180-2, 2002 · conservative default outside SNARKs

All three are conjectured PQ-secure under Grover; the difference is age. SHA-256's design family has decades of cryptanalysis behind it. Poseidon's algebraic-attack analysis is younger — treat it with proportional humility for protocols where the hash is the long-term bottleneck.

parameter discipline
Different field × state-width × round-count tuples produce incompatible hashes. A careful deployment pins the parameter set alongside the SRS provenance. Poseidon and Poseidon2 are not bit-identical — upgrading from one to the other rewrites every Merkle root in the registry. The current deployment standardises on Poseidon2 as the canonical hash.

references

Primary literature.

Four sources. The two Poseidon papers, the Stellar CAP defining the host function, and the PLONK paper that consumes the hash on the transcript side.