ZK-Friendly Signature Schemes: Schnorr over Grumpkin, ML-DSA, FN-DSA and SLH-DSA

When a proof has to show that some action was authorised, it has to contain the signature check itself. The circuit re-runs the verifier on the public key, the message and the signature, and the proof attests that the verifier accepted. The signer never runs inside the circuit. A signature scheme is therefore circuit-friendly, or not, almost entirely because of its verification algorithm: what arithmetic it does, in which field, and which hash function it calls.

The four schemes here represent four distinct designs. Schnorr over Grumpkin is the pre-quantum option that Aztec and Noir use when the proof system runs over BN254: ordinary Schnorr on a curve chosen so that its arithmetic is the circuit's native arithmetic. (Circom-based systems make the same move with EdDSA on Baby Jubjub, another curve over the same field^[1].) ML-DSA, SLH-DSA and the forthcoming FN-DSA are NIST's stateless post-quantum signature standards, and each rests on a different idea. ML-DSA is Schnorr's protocol carried over to lattices, FN-DSA is hash-and-sign with a lattice trapdoor, and SLH-DSA uses nothing but a hash function. They appear in the order Schnorr, ML-DSA, FN-DSA, SLH-DSA. ML-DSA is easiest to read as a change to Schnorr, FN-DSA as a lattice scheme that abandons Schnorr's shape, and SLH-DSA as the one that abandons algebra altogether.

1 · What a verifier costs inside a circuit

A SNARK expresses a computation as polynomial constraints over a finite field. For proof systems built on BN254, that field is 𝔽_r, where r is BN254's 254-bit group order. A verifier is cheap to prove when its steps are already statements about elements of 𝔽_r, and expensive when they have to be simulated. Three things decide which.

Arithmetic modulo anything other than r. Arithmetic in another large prime field has to be emulated: each element is split into limbs, products are formed limb by limb, and every carry and the final reduction are proved with range checks. For one R1CS library, emulating a multiplication in BN254's base field inside its scalar field is reported to cost about 600 times a native one^[2]. A small modulus is a different matter. The lattice moduli below, 8380417 and 12289, sit far below r, so products of their residues are exact in 𝔽_r and only the reduction mod q needs a check.

Bit-oriented hash functions. SHA-2 combines additions modulo 2³² or 2⁶⁴ with XOR, AND, NOT, rotations and shifts on words; SHA-3 uses only XOR, AND, NOT and rotations on 64-bit lanes. Over 𝔽_r each bit becomes a variable, so one SHA-256 compression costs about 26,000 to 30,000 R1CS constraints and one Keccak-f[1600] permutation about 150,000. An arithmetic hash such as Poseidon, built from rounds of a low-degree map (x ↦ x⁵) on field elements, costs about 240^[3]. Provers with lookup tables narrow the gap without closing it: in barretenberg's UltraHonk an additional SHA-256 compression costs about 3,900 gates, a Keccak-f permutation about 17,400, and a Poseidon2 permutation 73^[4]. None of the NIST signature standards permits an arithmetic hash, so swapping one in produces a non-standard variant: often a reasonable engineering choice, but not a FIPS-compliant one.

Inequalities. "This value is small" is not a polynomial identity. It has to be enforced with a range check, paid for with a bit decomposition or a lookup table.

What costs nothing is everything only the signer does: sampling, retry loops, floating-point arithmetic, keeping the key secret. Two of the post-quantum signers below are complicated in exactly those ways, and none of it reaches the circuit.

The mainstream reference point is ECDSA over secp256k1, the signature scheme of Ethereum accounts and of all Bitcoin outputs other than Taproot's. Its curve lives over a 256-bit prime foreign to r, so every point operation is emulated. One verification takes about 1.5 million R1CS constraints in 0xPARC's 2022 circom-ecdsa^[5], about 122,000 in gnark's optimised emulated-arithmetic gadget^[6], and about 43,000 gates in UltraHonk^[7]. The UltraHonk figure is about ten times a standalone Schnorr-over-Grumpkin verification (§2), and about twenty-seven times for each further verification, once each circuit's one-time lookup tables have been paid for. RSA-2048 verification, with the message hash left out, is about 186,000 R1CS constraints, most of it 2048-bit big-integer arithmetic^[8]. These numbers are the scale against which the four schemes below should be read.

2 · Schnorr over Grumpkin

Work in a group of prime order n, written additively, with generator G. The secret key is a scalar x ∈ ℤ_n; the public key is the point P = x·G.

Three facts carry the whole scheme.

It verifies because scalar multiplication is a homomorphism. The map a ↦ a·G sends sums of scalars to sums of points. Apply it to the signer's equation and it becomes an equation between public values:

s = k + e·x   ⟹   s·G = k·G + e·(x·G) = R + e·P.

It leaks nothing because the mask is uniform in a finite group. For a fixed challenge, k ↦ k + e·x is a bijection of ℤ_n, so a uniform k gives a uniform s, whatever x is. The verifier's view can be produced without the key at all: choose s and e at random and set R = s·G − e·P. (With a real hash the simulator also has to program H so that H(R, P, m) = e, which is the random-oracle part of the proof.)

It is unforgeable, if discrete logarithms are hard, because the challenge comes after the commitment. A forger can pick s and e and solve R = s·G − e·P, exactly as the simulator does, but then H(R, P, m) equals the chosen e only with probability about 1/n per hash query. A forger that could answer two different challenges for the same R would, by the formula below, have computed x; rewinding a successful forger to obtain two such answers (the forking lemma) turns it into a discrete-log solver. This is the Fiat–Shamir transform: an interactive identification protocol, with the verifier's random challenge replaced by a hash of the commitment and the message.

The linearity cuts both ways. Two signatures made with the same nonce give two linear equations in two unknowns, and the key falls out:

x = (s − s′) · (e − e′)⁻¹ mod n.

The same linearity is what makes Schnorr easy to turn into multi-signatures and threshold signatures (MuSig2, FROST). The danger of a repeated nonce is why Ed25519 derives k deterministically from the key and the message. BIP-340 uses a similar derivation and also mixes in fresh randomness, as a defence against fault and side-channel attacks^[9].

2.1 · A worked example on a toy Grumpkin

Grumpkin's equation is y² = x³ − 17. Over the field 𝔽₉₇, the same equation has exactly 103 points, and 103 is prime, so every point other than the identity generates the group. Take G = (1, 9): 9² = 81 ≡ 1 − 17 (mod 97). The real Grumpkin generator also has x-coordinate 1.

Now sign a second message with the same nonce. Its challenge is, say, e′ = 64, so s′ = 75 + 64·42 ≡ 85. Anyone holding both signatures computes (30 − 85)·(21 − 64)⁻¹ ≡ 48·60⁻¹ ≡ 48·91 ≡ 42 (mod 103), which is the secret key. The toy follows the textbook form above, with the hash replaced by a chosen value; the deployed variant in §2.2 flips a sign and sends (s, e).

2.2 · Why this curve

BN254 is the pairing-friendly curve y² = x³ + 3 behind Ethereum's precompiles and many deployed SNARKs. It is defined over a prime field 𝔽_p and its group has prime order r, so a proof system built on BN254 writes its constraints over 𝔽_r. Grumpkin is the curve y² = x³ − 17 over 𝔽_r, with generator (1, √−16) and group order exactly p^[10]. The two curves form a cycle: each one's base field is the other's scalar field. The toy curve has a partner of the same kind. 103 and 97 are the BN primes for the parameter u = 1, and over 𝔽₁₀₃ the equation y² = x³ − 17 has exactly 97 points, so the toy pair shares one equation (at this size x³ + 3 does not work).

For a circuit over 𝔽_r, a Grumpkin point is a pair of native field elements, and adding or doubling points costs a handful of native multiplications: no limbs, no carries, no range checks. Noir calls it the embedded curve and exposes multi-scalar multiplication on it as a built-in operation^[11]. The one seam is the scalar. Scalars live in ℤ_p, and p > r, so a scalar does not fit in one native element. Noir carries it as two limbs of at most 128 bits, and the scalar multiplication decomposes it into small windows anyway. The seam runs in the convenient direction for hashing: a challenge computed as an element of 𝔽_r is already smaller than p, so it is a valid scalar without reduction.

The variant in use. Aztec's default account contract checks Schnorr signatures over Grumpkin with Noir's schnorr library^[12]. It sends (s, e) instead of (R, s) and flips a sign. The signer computes s = k − x·e mod p. The verifier recomputes R′ = s·G + e·P, hashes e′ = Poseidon2(DST, R′.x, P.x, P.y, m) with a fixed domain-separation constant, and accepts iff e′ = e. The message is a single field element, which for a transaction is a Poseidon2 hash of the payload bound to the account address and chain. Apart from range checks on the two scalars' limbs, every step is native to 𝔽_r: one two-point multi-scalar multiplication on the embedded curve and two Poseidon2 permutations. Compiled alone, the verification comes to about 4,200 gates in barretenberg's UltraHonk arithmetisation, against about 43,000 for one ECDSA secp256k1 verification whose message hash is supplied ready-made. About two-thirds of the Schnorr figure is a one-time cost, which matches the size of barretenberg's range-check table, and any circuit that already range-checks values of that width has paid it; after that, each further verification costs about 1,400 gates, against about 37,000 for ECDSA^[7]. The scheme took this form in May 2026; before that, the challenge was Blake2s over a Pedersen hash, and the message a byte string^[12].

How it differs from mainstream signatures. The algebra is the same as Ed25519 and Bitcoin's BIP-340 Schnorr; the differences are the curve, the hash, the sign convention and the (s, e) encoding. That encoding rules out batch verification, which is why BIP-340 chose (R, s), but it costs nothing inside a circuit. One more difference matters in practice: barretenberg's signer draws k at random instead of deriving it from the key and the message, so it depends on a sound random-number generator^[12]. There is no standard for Schnorr over Grumpkin beyond the implementation and its pinned test vectors. ECDSA differs in kind. Its response s = k⁻¹(z + ρ·x), where z is the message hash and ρ the x-coordinate of k·G reduced mod the group order, multiplies the key by the inverse of the nonce. It is not linear in the signer's secrets taken together, which is why ECDSA resists simple aggregation, and verification needs s⁻¹. Inside a circuit the inverse is cheap: the prover supplies it and the circuit checks one product. ECDSA's cost in a circuit comes from its fields, not its shape: both its coordinates and its scalars live modulo 256-bit primes unrelated to r (§1). Like every discrete-log scheme, Schnorr over Grumpkin falls to a quantum computer running Shor's algorithm, which recovers x from P.

3 · ML-DSA: Schnorr with a short response

ML-DSA keeps Schnorr's shape (commit, challenge, respond) and replaces the group by linear algebra over the ring R_q = ℤ_q[X]/(X²⁵⁶ + 1), with q = 8380417 = 2²³ − 2¹³ + 1. A public matrix A ∈ R_q^k×ℓ takes the place of G, and a pair of short vectors (s₁, s₂), with coefficients in [−η, η], takes the place of x:

t = A·s₁ + s₂  (mod q)public key; recovering s₁ is Module-LWE

Without s₂ the key would be a linear system anyone could solve; the small error term is what hides s₁. Signing then copies Schnorr term by term: a mask y with coefficients in (−γ₁, γ₁], a commitment w = A·y, a challenge c (a polynomial with exactly τ coefficients equal to ±1 and the rest 0, derived by hashing), and the response

z = y + c·s₁.

The verifier, following Schnorr, computes A·z − c·t, and gets

A·z − c·t = A·y + c·A·s₁ − c·A·s₁ − c·s₂ = w − c·s₂.

Two things have broken relative to Schnorr, and ML-DSA's design is the repair of both.

The check is off by a small error. The verifier recovers w − c·s₂, not w. But c·s₂ is small: each of its coefficients is a sum of τ terms ±s_2,j, so ‖c·s₂‖_∞ ≤ β = τη. So the challenge is computed from HighBits(w): each coefficient rounded to a multiple of 2γ₂, keeping only the quotient (with one wrap-around exception, shown in the example below). Adding back c·s₂, whose coefficients are at most β, cannot change the quotient of w − c·s₂ unless one of its coefficients lies within β of a bucket edge. The signer tests this on w − c·s₂, the value the verifier will reconstruct: if ‖LowBits(w − c·s₂)‖_∞ ≥ γ₂ − β, it discards the attempt and starts again. Otherwise the verifier's HighBits(A·z − c·t) equals the signer's HighBits(w), and the recomputed challenge matches.

The mask no longer hides. The response has to be short. With no bound on z, forging would need no key: when A is square, as in ML-DSA-44, a forger can choose the high bits, hash them to get c, and solve for z by linear algebra. The bound is what makes forgery a hard lattice problem (Module-SIS). ML-DSA requires ‖z‖_∞ < γ₁ − β. But short vectors do not wrap around. Over the integers, z = y + c·s₁ is the uniform box of y shifted by c·s₁, and a shifted box shows its shift at the edges: a coefficient of z above γ₁ proves the matching coefficient of c·s₁ is positive. The repair is rejection sampling: publish z only if ‖z‖_∞ < γ₁ − β. Every value in that inner box is reached from exactly one y, whatever c·s₁ is, so a z that passes this test is uniform on the inner box, whatever the key (for a given c).

The second rejection test does not leak s₂ either, although it mentions it. The identity w − c·s₂ = A·z − c·t makes it a function of the signature and the public key, so a simulator holding no secret can evaluate it. ML-DSA withholds the low bits of t from the public key, but FIPS 204 calls that "an optimization for performance, not security", since those bits can be reconstructed from a few signatures^[14], and the Dilithium security proof takes the whole of t as the public key^[15].

3.1 · A worked example

Shrink everything to one coordinate: n = 1 (plain integers mod q), k = ℓ = 1, q = 97, η = 2, τ = 1 so that c = ±1 and β = 2, γ₁ = 16 and γ₂ = 8. HighBits splits 0…96 into six buckets: five of width 16, and bucket 0, which wraps around to hold 89…96 and 0…8. (FIPS 204 folds the values that would round up to q − 1 into bucket 0 and lowers their low bits by one, so 89 has high bits 0 and low bits −8.) Key generation picks a = 38, s₁ = 2, s₂ = −1, so

t = 38·2 − 1 = 75.

The signer needs ‖z‖_∞ < 14 and |LowBits(w − c·s₂)| < 6. The challenge is a hash of the message and HighBits(w); in this run it returns c = +1 for high bits 5 and c = −1 for high bits 3.

The verifier checks |7| < 14, computes a·z − c·t = 38·7 + 75 = 341 ≡ 50 (mod 97), takes HighBits(50) = 3, hashes the message with 3, obtains −1, and accepts. It never sees w = 51; it lands on 50, one step away, inside the same bucket.

The toy departs from the standard in two ways besides its size. It publishes t in full; ML-DSA publishes only t₁, the high part of t with d = 13 low bits dropped, which more than halves the public key but adds a second error term c·t₀ to the verifier's computation. The signature therefore carries a hint h, a 0/1 vector with at most ω ones, marking the coefficients where that extra error carries into the high bits. And the real challenge is not a sign but a sparse polynomial, so c·s₁ mixes τ coefficients of the key into each coefficient of the response.

3.2 · The standard, and its cost in a circuit

The full algorithms, with the names FIPS 204 uses^[14]:

H is SHAKE256 and ExpandA uses SHAKE128. M′ prefixes the message with a domain-separation byte (0 for pure ML-DSA), a byte giving the context length, and the context string (up to 255 bytes, empty by default). Signing is hedged by default, with 32 fresh random bytes as rnd; setting rnd to zero makes it deterministic. Decoding the hint rejects more than ω ones, and also any encoding whose indices are not strictly increasing or whose unused bytes are nonzero. The draft standard omitted the ordering check, which let anyone turn a valid signature into a different valid one and so broke strong unforgeability^[14].

Common to all three: q = 8380417, n = 256, d = 13. The attempt counts are those in NIST's list of potential FIPS 204 corrections (July 31, 2026), which would replace the 4.25 / 5.1 / 3.85 printed in Table 1; NIST notes that such entries are not official until an errata update is issued (the printed figures came from the Dilithium submission's approximate formula, which leaves out the rejections at the hint step and slightly understates the other two tests); a simulation of 80,000 signatures per set agrees with the corrected values^[16].

In a circuit. The arithmetic is modest. Residues mod 8380417 have 23 bits, so their products are exact in 𝔽_r and only the reduction needs a range check; ML-DSA-44 verification amounts to about twenty thousand such multiplications if done as a CPU does it (nine forward NTTs, four inverse, twenty pointwise products), plus 1,024 range checks for ‖z‖_∞ and the decomposition inside UseHint. The hashing is heavier. A full ML-DSA-44 verification of a short message (up to 69 bytes, empty context) runs 99 Keccak-f[1600] permutations, and 80 of them are ExpandA regenerating A from its 32-byte seed^[17]. A depends only on the public key, so a circuit that verifies signatures under a known key can hold it as a constant, leaving 19 permutations, or 9 if tr is fixed as well. Removing the rest means leaving the standard. zkDilithium, a variant of round-3 Dilithium2, replaces SHAKE with Poseidon, publishes t uncompressed so that signatures carry no hint, and proves verification in a STARK over an extension of Dilithium's own field^[18]. EIP-8051, aimed at the EVM rather than at circuits, pairs a FIPS ML-DSA-44 precompile with a non-compliant variant that swaps SHAKE for a Keccak256-based generator^[19]. That variant saves gas because Keccak256 is an EVM opcode, but inside a circuit it is the same Keccak-f permutation and saves nothing.

How it differs from mainstream signatures. The public key and signature are 1312 and 2420 bytes at the lowest level, against 32 and 64 for Ed25519. There is no curve arithmetic, only additions and multiplications mod a 23-bit prime. Signing is a loop with a variable number of attempts. The chance that an attempt is rejected is exactly key-independent at the z test and, treating A·y as uniform, at the LowBits test; the hint test depends on the key only through t₀, which FIPS 204 treats as public. The security rests on Module-LWE for key recovery and on Module-SIS variants for forgery, and no quantum algorithm is known to break either.

4 · FN-DSA: a short preimage from a trapdoor

FN-DSA is the name NIST has given to Falcon for the forthcoming FIPS 206. As of this writing no draft has been released, so the reference text is still the Falcon v1.2 specification, together with the changes NIST has announced as provisional^[20][21]. FN-DSA drops the commit–challenge–respond shape altogether. It is hash-and-sign, the same template as RSA-FDH: hash the message to a point, and let the holder of a trapdoor produce a preimage that the public can check. The public key is one polynomial h ∈ R_q = ℤ_q[X]/(Xⁿ + 1) with q = 12289 and n = 512 or 1024, and a signature on m is a pair of polynomials with

s₁ + s₂·h ≡ c  (mod q),    ‖(s₁, s₂)‖² ≤ ⌊β²⌋,c = HashToPoint(salt ‖ m)

The equation alone certifies nothing: (c, 0) satisfies it, and so does (c − a·h, a) for every a. All of the security is in the norm bound. The pairs (u, v) with u + v·h ≡ 0 form a lattice Λ, the solutions of the signing equation are the coset (c, 0) − Λ, and a short solution is the difference between the target (c, 0) and a lattice point close to it. Finding a close lattice point is easy with a basis of short vectors and infeasible, at these dimensions, with only long ones.

The trapdoor is such a basis. Key generation draws small random polynomials f and g and publishes h = g·f⁻¹ mod q, which makes (g, −f) a short vector of Λ. It then solves the NTRU equation

f·G − g·F = q

for a second short pair (F, G), and the rows (g, −f) and (G, −F) form a basis of Λ whose vectors are all short. The public key yields only the basis {(q, 0), (−h, 1)}, whose first vector is as long as the modulus.

4.1 · A worked example in two dimensions

With n = 1 the ring is just ℤ_q and Λ is a lattice in the plane. Take q = 97, f = 3, g = 7. Then h = 7·3⁻¹ = 7·65 ≡ 67 (mod 97). The NTRU equation 3G − 7F = 97 has the short solution F = −13, G = 2 (6 + 91 = 97), so the secret basis is

b₁ = (g, −f) = (7, −3),    b₂ = (G, −F) = (2, 13).

Both lie in Λ (7 − 3·67 = −194 = −2·97, and 2 + 13·67 = 873 = 9·97), and their determinant, 7·13 + 3·2 = 97, equals that of Λ, which contains one in every 97 integer points, so they generate all of it. Now sign a message that hashes to c = 41. Write the target (41, 0) in the secret basis: (41, 0) ≈ 5.495·b₁ + 1.268·b₂. Round the coefficients to (5, 1) to get the lattice point λ = 5b₁ + b₂ = (37, −2), and the signature is the difference:

s = (41, 0) − (37, −2) = (4, 2),    4 + 2·67 = 138 ≡ 41  (mod 97) ✓,    ‖s‖² = 20.

Rounding in the secret basis never produces ‖s‖² above 53 for any of the 97 possible targets. The solution anyone can write down, (41, 0), has ‖s‖² = 1681. In two dimensions the gap closes instantly, since Lagrange–Gauss reduction turns the public basis into (7, −3), (2, 13) in a few steps, so the toy shows only the geometry. In dimension 2n = 1024, no known algorithm finds a basis anywhere near as short.

4.2 · Why rounding is not enough

Rounding with the secret basis gives short signatures, and it also publishes the basis. Each signature is a point of the centred parallelogram {a·b₁ + a′·b₂ : −½ ≤ a, a′ < ½}; collect enough of them and the parallelogram, and so the secret basis, can be read off the scatter. This is how Nguyen and Regev broke GGH signatures and NTRUSign without perturbations in 2006, recovering an NTRUSign-251 key from 400 signatures; the perturbed variant fell to a refinement of the same attack in 2012^[23]. Deterministic nearest-plane decoding leaks in the same way. GPV's repair is to randomise the decoding. Klein's sampler is a randomised form of Babai's nearest-plane algorithm. It takes the Gram–Schmidt vectors b̃_i from last to first. At each step it replaces the current target's coefficient along b̃_i with an integer drawn from a discrete Gaussian centred on that coefficient, of width σ/‖b̃_i‖, and subtracts that multiple of b_i before moving on. With a wide enough Gaussian, the output is statistically close to a discrete Gaussian over the coset (c, 0) − Λ: its distribution depends on the lattice and the target, both public, and not on which short basis did the sampling. FN-DSA's fast Fourier sampling is a version of Klein's sampler that exploits the ring structure to run in O(n log n)^[24].

4.3 · The standard, and its cost in a circuit

Step 4 works because t·B = (c, 0) and z·B is a lattice point, so s = (c, 0) − z·B: the worked example, with randomised nearest-plane decoding in place of round-off. HashToPoint absorbs the salted message into SHAKE256 and reads 16-bit chunks, keeping those below 61445 = 5q and reducing them mod q, until it has n coefficients. The salt exists for the security proof. Two different short solutions for the same c would differ by a short vector of Λ, so the signer must never publish two signatures on one hash value, and a fresh 320-bit salt makes a repeated c negligible^[22][20]. Signing uses IEEE-754 double precision, which is the source of most of FN-DSA's implementation difficulty. Timing and power leakage from the Gaussian sampler, and electromagnetic leakage from the floating-point FFT, have each led to published key-recovery attacks. So has floating-point disagreement, between implementations or between two signing procedures of one implementation, when a derandomised variant signs the same input twice^[25]. NIST cites this risk as a reason FN-DSA allows only randomised signing^[21]. Verification uses integers only.

Public key and signature together come to 1563 bytes for Falcon-512 (category 1), against 3732 for ML-DSA-44 (category 2, the smallest ML-DSA set). NIST sums up the trade-off: FN-DSA "has very small signatures and public keys but is difficult to implement"^[21]. The provisional FN-DSA changes include hashing a digest bound to the public key and a context string, little-endian encodings, randomised signing only, and an additional bound on the largest coefficient of a signature^[21].

In a circuit. This is the lightest of the three post-quantum verifiers. The arithmetic is one ring product s₂·h mod 12289, one subtraction and a sum of 2n squares, all on integers, plus range checks to centre s₁ and, for the standard byte encoding, decoding of the compressed s₂. The product can be computed with NTTs or, more cheaply inside a proof, supplied by the prover and checked at a single random point, as Miden's verifier does^[26]. An R1CS implementation for Groth16 reports 81,460 constraints for Falcon-512 verification, with HashToPoint, signature decoding and the transform of h left outside the circuit^[27]. The hash is the awkward part. In Falcon v1.2, HashToPoint is SHAKE256 with rejection sampling: 8 or 9 Keccak-f permutations for n = 512 and a message of up to 95 bytes, with a variable number of draws. A circuit therefore has to budget a fixed number of blocks (ten fail with probability below 2⁻¹⁷⁰). The provisional FN-DSA also hashes the public key and a message digest, which adds about eight permutations unless the key is fixed when the circuit is built. Deployments that care about proving cost replace the hash: Poseidon2 on Miden, Poseidon on Starknet. The EVM proposal EIP-8052 offers a Keccak-based generator beside the standard SHAKE256 one, to cut gas rather than proving cost^[28]. Each non-SHAKE variant is a different signature scheme, not interoperable with Falcon or FN-DSA.

How it differs from mainstream signatures. Structurally FN-DSA is closer to RSA-FDH than to ECDSA or Ed25519: the signature is a trapdoor preimage of a hash, not a response to a challenge, and there is no Schnorr-style nonce whose reuse hands over the key. What must not leak is the sampler's randomness and timing, and the power or electromagnetic trace of the floating-point arithmetic on the secret basis. Its costs are lopsided: verification is simpler than ECDSA's, while signing is harder to implement correctly than that of any mainstream scheme. Key recovery rests on the NTRU problem and forgery on SIS over NTRU lattices.

5 · SLH-DSA: signatures from a hash function alone

SLH-DSA uses no algebraic structure at all: there is none for a circuit to exploit and none for a cryptanalyst to attack, beyond the hash function itself. Its security reduces to properties of the hash functions alone: multi-target forms of target-collision and second-preimage resistance for the chain and tree hashes, pseudorandomness of the key-derivation functions, and, for the few-time layer described below, a property of the message hash called interleaved target-subset resilience. For the "simple" instances FIPS 205 approves, these properties are argued in the quantum random-oracle model^[29]. Its one-time signature, WOTS+, is built from one primitive, the hash chain

sk  →  F(sk)  →  F²(sk)  →  ⋯  →  F^w−1(sk) = pk,

which anyone can walk forward and nobody can walk back.

5.1 · The engine: a one-time signature and its checksum

The Winternitz one-time signature (WOTS+ in FIPS 205) writes the message digest in base w, as digits m₁, …, m_ℓ, and keeps one chain per digit. To sign digit m_i, reveal the chain's value at position m_i; to verify, hash it w − 1 − m_i more times and compare with the chain's end in the public key:

σ_i = F^m_i(sk_i),    accept iff F^w−1−m_i(σ_i) = pk_i.

As it stands this is forgeable. Whoever sees a signature can hash any σ_i forward and so sign any message whose digits are all at least as large. The fix is a checksum,

C = Σ_i (w − 1 − m_i),

written in base w and signed with a few more chains. Raising any message digit lowers C, and a lower C has at least one base-w digit that is lower. That digit's chain would have to be walked backward.

A worked example. Take w = 4, so each chain has positions 0 to 3, and a three-digit message (2, 0, 3). The checksum is (3 − 2) + (3 − 0) + (3 − 3) = 4, which is (1, 0) in base 4; the maximum possible checksum is 9, so two base-4 digits always suffice. The signature reveals five chain values: F²(sk₁), sk₂, F³(sk₃), F(sk₄), sk₅, and the verifier completes the chains with 1 + 3 + 0 + 2 + 3 = 9 hash evaluations. A forger holding this signature who wants (3, 0, 3) can advance the first chain, but the checksum drops from 4 to 3 = (0, 3), and the fourth chain now needs position 0 when only position 1 is known. Checking all 64 messages exhaustively: no signature in this toy lets anyone sign a different message.

5.2 · From one signature to 2⁶⁴

A WOTS+ key signs once. SLH-DSA turns it into a many-time scheme in three steps.

Merkle trees authenticate many one-time keys under one root: an XMSS tree of height h′ has 2^h′ WOTS+ public keys as leaves, and a signature includes the h′ sibling hashes on the path from its leaf to the root. A hypertree stacks d layers of such trees, each leaf of one layer signing the root of a tree in the layer below, for 2^h leaves in the bottom layer, with h = d·h′. Nobody ever builds the whole thing: a signature touches only the d small trees on one path, and every tree is regenerated on demand from a secret seed.

Statelessness comes from picking the leaf by hashing the message rather than by counting signatures. Random choices among 2^h leaves collide often: at 2⁶⁴ signatures with h = 63, each leaf is used twice on average. So the message itself is never signed with WOTS+, which must never be reused. Instead each bottom-layer leaf has a FORS key, a few-time scheme, which signs the message digest, and the leaf's WOTS+ key signs that FORS public key. A FORS key is k small trees of 2^a secret leaves each, of which the message digest selects and reveals one leaf per tree. A second use of the same FORS key reveals up to k more leaves, one per tree, and forging requires hitting only revealed leaves in all k trees at once, so security declines gradually with reuse instead of failing. The parameter sets are sized to keep that margin through 2⁶⁴ signatures under one key.

5.3 · The standard, and its cost in a circuit

Signing is hedged by default: opt_rand is fresh randomness, or PK.seed on platforms with no random-bit generator. R travels in the signature, so the verifier never needs the secret PRF. The public key is only 2n bytes, a seed and a root, and the secret key 4n.

The "s" sets are small and slow to sign, the "f" sets fast to sign and large. Hash calls are counted from FIPS 205's verification algorithms, averaged over uniformly random digests, and checked against NIST's test vectors^[30][31]. The spread comes entirely from the WOTS+ chains, whose length depends on the digits. The minimum and maximum are theoretical bounds; in practice a 128s verification stays within a few hundred calls of the mean (standard deviation about 80).

In a circuit. SLH-DSA has the simplest verifier to write down and, with its standard hashes, the most expensive one to prove. It is nothing but hash calls: about 2,100 for SLH-DSA-128s on average and 3,824 at most. A circuit of fixed shape has to accept every valid signature, so it is sized for the worst case. Where proving cost follows the actual count, as in a zkVM, a malicious signer can also grind R to raise it, by a few hundred calls for 2⁴⁰ attempts^[31]. With SHA-256, once the padded PK.seed block is cached, each F and H call is a single compression. (The SPHINCS+ designers padded that block to a full 64 bytes for exactly this reason, and FIPS 205 keeps the padding^[29][30].) The public-key compressions (eight of them for 128s) and the message hash take several compressions each, so one 128s verification averages about 2,190 compressions for a short message (2,142 to 2,316 on the four valid SHA2-128s test vectors), more for long messages. At 19,500 to 30,000 R1CS constraints per compression (an optimised prototype and the usual gadgets, respectively), that is about 43 to 65 million constraints on average^[32].

No standard instance uses an arithmetic hash. The most developed hash-based design for proving is instead stateful: leanSig, the Lean Ethereum project's prototype for post-quantum consensus signatures, is an XMSS-style scheme with one signature per epoch and a Poseidon-family hash over the 31-bit KoalaBear field^[33][34]. It also drops the checksum. Its target-sum encoding has the signer re-randomise until the message digits add up to a fixed T, and two digit vectors with the same sum can never dominate each other. That achieves what the checksum achieves, with no extra chains and with a verification cost that no longer depends on the message. Statelessness is not ruled out, only costlier: the same project's aggregation VM also handles a stateless SPHINCS-style variant^[35]. For deployments that sign rarely, NIST's draft SP 800-230 proposes SLH-DSA parameter sets limited to 2²⁴ signatures per key, with a single-tree hypertree and w = 4 or 8, verifying with six to eight times fewer hash calls than the corresponding "s" set^[36].

How it differs from mainstream signatures. Its assumptions are the most conservative on offer: if the hash function holds, the scheme holds, with no number theory and no lattice problem involved. Its public key, 32 bytes for the 128-bit sets, is as small as Ed25519's, but its signatures are 120 to 780 times larger than a 64-byte ECDSA or Ed25519 signature, and signing costs about 10⁵ hash calls for the fast sets and 2 to 4 million for the small ones. Compared with the stateful hash-based standards, XMSS and LMS, it gives up about an order of magnitude in size in exchange for having no state. With 32-byte hashes, w = 16 and a tree of height 10 (1,024 signatures), an XMSS or LMS signature is about 2.5 KB, against 29.8 KB for SLH-DSA-256s. The state is a real hazard: a signer that reuses a one-time key, after a crash or a restored backup, opens the key to forgery^[37].

6 · Side by side

The last column mixes proof systems and should be read for orders of magnitude only. The post-quantum hashing costs are derived by multiplying call counts by the per-call costs in §1; no public SNARK circuit over a prime field for the unmodified FIPS 204 or FIPS 205 verifier was found^[38]. zkVMs can run the reference verifiers unchanged, and FIPS 205 verification has been implemented as a boolean circuit for ZKBoo, an MPC-in-the-head proof system, passing NIST's test vectors^[39].

Put next to each other, the four engines solve one problem four ways. Every signer must publish a witness to a public relation without leaking the key that let it find the witness. Schnorr gets this for free: a uniform nonce in a finite group masks the response perfectly. ML-DSA must keep its response short, loses the wrap-around that made the mask perfect, and restores it by rejection: only responses in a region every key reaches equally often are published. FN-DSA has a trapdoor basis rather than a secret vector to hide, and hides it by Gaussian sampling, so the signature's distribution depends only on public data: the lattice and the hashed target. SLH-DSA reveals secret values outright and hides nothing algebraically. It limits what the revealed values permit, by one-wayness and the checksum, and limits how often they are revealed, by the hypertree and FORS. Everything else in these standards is engineering around those four ideas.

For circuits the conclusion is equally short. All four verifiers are compute-and-compare, with no secrets and no branching on secrets. One caveat applies to every post-quantum row: a proof is only as quantum-safe as the system that produces it. UltraHonk and Groth16 over BN254 rest on pairings and discrete logarithms, so a quantum adversary could forge the proof without touching the signature. The BN254 figures measure the size of the verifier; a post-quantum deployment needs a hash-based proof system, such as the STARKs used by zkDilithium and Miden. Schnorr over Grumpkin is the cheapest by construction: it is the only scheme here whose arithmetic and hash are both native to the circuit. The three post-quantum verifiers are dominated by their standard hash, not by their algebra. FN-DSA does the least arithmetic and the least hashing, ML-DSA needs 99 permutations unless the key is fixed, and SLH-DSA has no arithmetic at all and some two thousand hash calls. Two levers move these numbers. Fixing the public key when the circuit is built removes ML-DSA's matrix expansion and lets FN-DSA precompute the transform of h. Replacing the hash with an arithmetic one leaves the standard, and the zk-oriented variants cited above (zkDilithium, Miden's Falcon, leanSig) all do it. How much that second lever buys depends on the prover. In R1CS an arithmetic permutation is about a hundred times cheaper than a SHA-256 compression and several hundred times cheaper than a Keccak-f permutation. With UltraHonk's lookup tables the factors are about fifty and two hundred. On provers over binary fields the comparison can reverse, since bit-oriented hashes become native there. The Lean Ethereum project's leanVM, built to aggregate hash-based signatures, has moved from KoalaBear and Poseidon to a binary-field design, with BLAKE2s as a placeholder hash while SHA-2, SHA-3 and BLAKE3 are considered^[35].

References

Standards are cited by section and algorithm number; repositories by commit. Web pages that cannot be pinned carry the date they were read.

1. B. WhiteHat, M. Bellés, J. Baylina, "ERC-2494: Baby Jubjub Elliptic Curve" — eips.ethereum.org/EIPS/eip-2494; EdDSA on it in circomlib, iden3/circomlib@35e54ea · circuits/eddsa*.circom.
2. M. Orrù, G. Kadianakis, M. Maller, G. Zaverucha, "Beyond the Circuit: How to Minimize Foreign Arithmetic in ZKP Circuits," ePrint 2024/265 — eprint.iacr.org/2024/265, §1: non-native arithmetic is "multiple orders of magnitude more expensive"; a BN254 base-field multiplication emulated in the scalar field has "a 600x overhead", attributed to the arkworks-rs/nonnative R1CS library.
3. R1CS costs. SHA-256 compression: 25,840 constraints in bellman's gadget (zkcrypto/bellman@b726862 · src/gadgets/sha256.rs L307–332); 29,725 for circomlib's one-block Sha256(440), compiled for this article with circom 2.2.3 at --O2. Keccak: 150,848 for Keccak-256 of 32 bytes (vocdoni/keccak256-circom@af3e898). Poseidon: 243 per width-3 permutation, against 27,534 for a SHA-256 Merkle node — L. Grassi et al., "Poseidon," USENIX Security 2021, ePrint 2019/458, Tables 1 and 4.
4. Barretenberg per-opcode gate constants — aztec-packages@86ba738 · dsl/acir_format/gate_count_constants.hpp (L20–59): SHA-256 compression 6,704; Keccak-f 17,388; Poseidon2 74. Marginal costs for a second call, 3,946 / 17,380 / 73 gates, measured for this article with nargo 1.0.0-rc.2 and bb 5.2.0; the file lists a 32-bit range opcode at 2,745 gates, consistent with the ≈ 2,760-gate difference between the standalone and marginal SHA-256 costs.
5. 0xPARC, circom-ecdsa — 0xPARC/circom-ecdsa@d87eb70 · README (Benchmarks): 1,508,136 constraints for secp256k1 verification without public-key validation (2022).
6. Consensys gnark, package std/signature/ecdsa, v0.16.3 documentation — pkg.go.dev/github.com/consensys/gnark/std/signature/ecdsa: "approximately 122k constraints in R1CS and 453k constraints in PLONKish" for one secp256k1 verification in a BN254 SNARK. Read 2026-09-30.
7. Barretenberg per-opcode gate counts (Ultra builder), the same file as the UltraHonk hash-cost reference above: aztec-packages@86ba738 · dsl/acir_format/gate_count_constants.hpp (L20–59): ECDSA secp256k1 verification 42,838; one-point Grumpkin MSM 3,558; Poseidon2 permutation 74; SHA-256 compression 6,704. Full Schnorr verification, 4,199 gates: noir-lang/schnorr CI report, noir-lang/schnorr#17 (nargo and bb 1.0.0-beta.21). Standalone and marginal costs remeasured for this article with nargo 1.0.0-rc.2 and bb 5.2.0: Schnorr (v0.4.0) 4,178 gates alone and 1,383 for a second verification in the same circuit; ECDSA secp256k1 42,892 alone and 37,455 for a second.
8. zk-email, RSAVerifier65537(121, 17) — zkemail/zk-email-verify@066c874 · packages/circuits/lib/rsa.circom: 185,903 R1CS constraints at --O2 (circom 2.2.3, compiled for this article), covering PKCS#1 v1.5 padding and the modular exponentiation but not the message hash.
9. P. Wuille, J. Nick, T. Ruffing, "BIP 340: Schnorr Signatures for secp256k1" — bitcoin/bips@3a10b5b · bip-0340.mediawiki (nonce generation; the choice of (R, s) over (e, s) for batch verification: §Design). Ed25519: RFC 8032, §5.1.6. MuSig2: BIP 327. FROST: RFC 9591.
10. Grumpkin parameters in barretenberg: aztec-packages@86ba738 · ecc/curves/grumpkin/grumpkin.hpp (L20–45), with the BN254 fields in ecc/curves/bn254/fr.hpp and fq.hpp. Group order equal to BN254's base-field prime, cofactor 1, and embedding degree (p − 1)/6 were rechecked by script for this article; Pollard rho with the negation map and the order-3 automorphism costs about √(πp/12) ≈ 2^125.8 group operations.
11. Noir standard library, std::embedded_curve_ops (EmbeddedCurvePoint, EmbeddedCurveScalar { lo, hi }, multi_scalar_mul) — noir-lang/noir@a6fcfd2 · noir_stdlib/src/embedded_curve_ops.nr. Limb widths (128 and 126 bits) and their in-circuit range checks: barretenberg stdlib/primitives/group/cycle_scalar.hpp L39–44 at aztec-packages@86ba738.
12. noir-lang/schnorr v0.4.0 — noir-lang/schnorr@9995bcc · src/lib.nr; barretenberg signer and verifier, crypto/schnorr/schnorr.tcc at the same aztec-packages commit as the Grumpkin reference; the switch from Blake2s/Pedersen to Poseidon2: AztecProtocol/aztec-packages#21808 (merged 2026-05-18). The account contract that uses it: aztec-labs-eng/aztec-node@2677d4f · schnorr_account_contract/src/main.nr; "Schnorr Account … (default)" per the Aztec accounts documentation, docs.aztec.network, read 2026-09-30.
13. V. Lyubashevsky, "Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures," ASIACRYPT 2009 — doi.org/10.1007/978-3-642-10366-7_35; and "Lattice Signatures Without Trapdoors," EUROCRYPT 2012 — doi.org/10.1007/978-3-642-29011-4_43. A gap in the CMA-to-NMA step of several ROM and QROM proofs for Fiat–Shamir with aborts, including Dilithium's, was identified and closed by Barbosa et al. (eprint.iacr.org/2023/246) and independently by Devevey, Fallahpour, Passelègue and Stehlé (eprint.iacr.org/2023/487), both CRYPTO 2023.
14. NIST, FIPS 204: Module-Lattice-Based Digital Signature Standard, August 13, 2024 — nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.pdf. Parameters: §4, Table 1. Algorithms: ML-DSA.Sign_internal (Alg. 7), ML-DSA.Verify_internal (Alg. 8), HintBitUnpack (Alg. 21), Decompose / MakeHint / UseHint (Alg. 36–40). The draft's missing hint-ordering check and its consequence for strong unforgeability: App. D.2–D.3 (compare the draft's Alg. 15 with Alg. 21, line 9). Dropping t₀ as "an optimization for performance, not security": §6.1.
15. L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, D. Stehlé, "CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme," TCHES 2018(1), 238–268 — tches.iacr.org/index.php/TCHES/article/view/839. Rounding lemmas: §2.4; zero-knowledge argument, including the identity w − cs₂ = Az − ct and the assumption that the public key is all of t: App. B.
16. NIST, FIPS 204 potential-updates spreadsheet, entry of 2026-07-31 (Table 1 repetitions 4.36 / 5.14 / 3.91; loop bound 821) — csrc.nist.gov/…/fips-204-potential-updates.xlsx, read 2026-09-29. The 80,000-signature simulation behind "agrees" was run for this article on an implementation that reproduces NIST ACVP keyGen, sigVer and deterministic sigGen vectors (ACVP-Server @ 975de31).
17. Keccak-f[1600] permutation count for ML-DSA-44 verification (pure mode, empty context, 32-byte message): ExpandA 16 × 5, tr 10, μ 1, SampleInBall 1, final hash 7. Computed from FIPS 204 Alg. 8 and the SHAKE rates of FIPS 202 §6.2 (168 and 136 bytes), and measured on 30 verifications with the implementation described in the previous reference. The 9-permutation figure for a precomputed key matches Fireblocks' EVM verifier — fireblocks-labs/evm-ml-dsa-verifier@cca262b · docs/EXPLAINER.md §2.1.
18. G.-V. Policharla, B. Westerbaan, A. Faz-Hernández, C. A. Wood, "Post-Quantum Privacy Pass via Post-Quantum Anonymous Credentials" (zkDilithium), ePrint 2023/414 — eprint.iacr.org/2023/414, §2 (the field 𝔽_q⁶) and §3.4: SHAKE replaced by Poseidon, the public key sent uncompressed so no hint, a modified SampleInBall, and τ raised from 39 to 40.
19. R. Dubois, S. Masson, "EIP-8051: Precompile for ML-DSA signature verification," draft, created 2025-10-15 — eips.ethereum.org/EIPS/eip-8051 (read at ethereum/EIPs 1ccf659). Two precompiles: FIPS ML-DSA-44 and an "ETH" variant using a Keccak-based PRNG in place of SHAKE256, which is not FIPS 204 compliant.
20. P.-A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Prest, T. Ricosset, G. Seiler, W. Whyte, Z. Zhang, Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU, specification v1.2, October 1, 2020 — falcon-sign.info/falcon.pdf. Bases and lattice: §3.1, eqs. 3.1–3.3; salt and the ban on two signatures for one hash: §2.2.2; HashToPoint: Alg. 3; signing: Alg. 10; verification: Alg. 16; parameters: Table 3.3. Signature sizes (padded 666 / 1280 B; compressed averages 651.6 / 1261.1 B): reference implementation, falcon.h.
21. Status of FIPS 206 as of 2026-09-29: no initial public draft on the CSRC FIPS list or in the Federal Register. NIST's provisional list of changes from Falcon, and its summary that FN-DSA "has very small signatures and public keys but is difficult to implement": R. Perlner, "FIPS 206 Status Update," 6th PQC Standardization Conference, September 25, 2025 — csrc.nist.gov/presentations/2025/fips-206-fn-dsa-falcon. A draft-tracking implementation by a Falcon co-author: T. Pornin, pornin/c-fn-dsa@1b85888 (README of 2026-07-22: "no FN-DSA draft has been published yet").
22. C. Gentry, C. Peikert, V. Vaikuntanathan, "Trapdoors for Hard Lattices and New Cryptographic Constructions," STOC 2008 — eprint.iacr.org/2007/432. Theorem 4.1: the randomised nearest-plane sampler's output is statistically close to a discrete Gaussian over the lattice coset, "oblivious to B's particular geometry"; hash-and-sign from preimage-sampleable functions: §6.
23. P. Q. Nguyen, O. Regev, "Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures," EUROCRYPT 2006; full version J. Cryptology 22(2), 2009 — cims.nyu.edu/~regev/papers/gghattack.pdf. 400 signatures recover an NTRUSign-251 key without perturbations (abstract). The perturbed variant: L. Ducas, P. Q. Nguyen, "Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures," ASIACRYPT 2012.
24. L. Ducas, T. Prest, "Fast Fourier Orthogonalization," ISSAC 2016 — eprint.iacr.org/2015/1014. Klein's sampler: P. Klein, "Finding the Closest Lattice Vector When It's Unusually Close," SODA 2000.
25. Timing leakage of Gram–Schmidt norms: Fouque, Kirchner, Tibouchi, Wallet, Yu, EUROCRYPT 2020 — eprint.iacr.org/2019/1180. Power analysis of the base sampler: S. Zhang, X. Lin, Y. Yu, W. Wang, "Improved Power Analysis Attacks on Falcon," EUROCRYPT 2023 — eprint.iacr.org/2023/224. Electromagnetic analysis of the floating-point FFT: Karabulut, Aysu, "Falcon Down," DAC 2021 — eprint.iacr.org/2021/772. Floating-point discrepancies when a derandomised signer samples twice on the same input: X. Lin, M. Tibouchi, Y. Yu, S. Zhang, "Do Not Disturb a Sleeping Falcon," EUROCRYPT 2025 — eprint.iacr.org/2024/1709.
26. Miden VM, Falcon-512 with Poseidon2 hash-to-point: the product h·s₂ is supplied as advice and checked by evaluation at a random point; about 59,900 VM cycles per verification — 0xMiden/miden-vm@8160d8a · falcon512_poseidon2.md.
27. Z. Zhang, falcon-r1cs (arkworks, Groth16 over the BLS12-381 scalar field): 81,460 constraints for Falcon-512 verification using NTTs, with the hash-to-point, the NTT of the public key and the signature decoding done outside the circuit — zhenfeizhang/falcon-r1cs@bff9280 (README).
28. R. Dubois, S. Masson, A. Sanso et al., "EIP-8052: Precompile for Falcon support," draft, created 2025-10-17 — eips.ethereum.org/EIPS/eip-8052 (read at ethereum/EIPs 87b0660): a hash-to-point precompile in SHAKE256 and Keccak-PRNG versions, plus a core verification precompile. Starknet Poseidon variant: feltroidprime/s2morrow@4eff9ab.
29. J.-P. Aumasson, D. J. Bernstein, W. Beullens, C. Dobraunig, M. Eichlseder, S. Fluhrer, S.-L. Gazdag, A. Hülsing, P. Kampanakis, S. Kölbl, T. Lange, M. M. Lauridsen, F. Mendel, R. Niederhagen, C. Rechberger, J. Rijneveld, P. Schwabe, B. Westerbaan, SPHINCS+: Submission to the NIST post-quantum project, v.3.1, June 10, 2022 — sphincs.org/data/sphincs+-r3.1-specification.pdf. "Padding PK.seed … allows for reuse of the intermediate SHA2 state": §7.2.2; security argument: §9.
30. NIST, FIPS 205: Stateless Hash-Based Digital Signature Standard, August 13, 2024 — nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.205.pdf. WOTS+: §5 (Alg. 5–8); XMSS and hypertree: §6–7; FORS and its gradual degradation under reuse: §8; signing and verification: Alg. 19–20; parameter sets and the 2⁶⁴-signature design limit: §11, Table 2; SHA-2 instantiation, including the padding of PK.seed to a full block: §11.2. Security properties required of the hash functions, including interleaved target-subset resilience of H_msg: see the SPHINCS+ specification.
31. Tweakable-hash calls in SLH-DSA verification: FORS k + ka + 1, plus d × (WOTS+ chain steps + 1 + h′), plus one H_msg. Expected values computed from the exact distribution of WOTS+ digits including the checksum, and confirmed with an instrumented verifier that passes the 336 pure and internal-interface NIST ACVP SLH-DSA sigVer vectors (ACVP-Server @ 975de31; the HashSLH-DSA vectors were not run): 2,069–2,159 calls and 2,142–2,316 SHA-256 compressions observed for SHA2-128s. Grinding bound (a few hundred calls above the mean for 2⁴⁰ attempts) computed from the exact distribution of per-layer chain lengths. Drake, Khovratovich, Kudinov and Wagner make the same observation about grinding the randomness of a Winternitz encoding (the paper cited for leanSig, §5.2).
32. M. Stopar, sphincs-circuit: an R1CS verifier for SPHINCS+-SHA2-128s-simple with one SHA-256 compression per folding step, about 2,236 compressions measured per verification and about 19,500 constraints per compression on a BLS12-381 test constraint system — miha-stopar/sphincs-circuit@5817315 (docs/FOLDING.md §4.4, docs/PLAN.md). A prototype; no end-to-end proving benchmark is published.
33. J. Drake, D. Khovratovich, M. Kudinov, B. Wagner, "Hash-Based Multi-Signatures for Post-Quantum Ethereum," IACR Communications in Cryptology 2(1), ePrint 2025/055 — eprint.iacr.org/2025/055. Synchronised (stateful) XMSS-style signatures aggregated by a post-quantum SNARK; target-sum Winternitz encoding: Construction 6.
34. leanEthereum/leanSig @ c08a3ba (April 29, 2026) — a prototype, "not meant to be used in production" (README); github.com/leanEthereum/leanSig: KoalaBear field (p = 2³¹ − 2²⁴ + 1), Poseidon hashing, lifetime 2³² epochs, rejection-sampled target-sum message encoding (src/signature/generalized_xmss/instantiations_aborting.rs).
35. leanEthereum/leanVM, README — leanEthereum/leanVM@248da07, read 2026-09-30: a binary-field SNARK for aggregating XMSS- and SPHINCS-style signatures, with BLAKE2s described as a placeholder hash; the earlier KoalaBear/Poseidon design is kept on a separate branch.
36. NIST, SP 800-230 (initial public draft), Additional SLH-DSA Parameter Sets for Limited-Signature Use Cases, April 13, 2026 — csrc.nist.gov/pubs/sp/800/230/ipd. Sets limited to 2²⁴ signatures with d = 1 and lg w = 2, 3, 2; expected verification hash calls about 278 / 493 / 536, against 2,124 / 3,060 / 4,451 for the corresponding "s" sets of FIPS 205 (computed as in the SLH-DSA hash-call reference).
37. NIST, SP 800-208, Recommendation for Stateful Hash-Based Signature Schemes (LMS and XMSS), October 2020 — nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-208.pdf; RFC 8391 (XMSS) and RFC 8554 (LMS). Sizes from the RFC formulas: XMSS-SHA2_10_256 2,500 B; LMS SHA-256 M32/H10 with W4, 2,508 B. State hazards (a crash before the state write, cloned or restored keys): SP 800-208 §1.2, §8.1, §9.1. WOTS+ forgery after two uses: FIPS 205 §8.
38. Derived for this article: verification hash-call counts (ML-DSA-44: 99 Keccak-f, or 19 with the expanded key precomputed; Falcon-512 HashToPoint: 8–9; SLH-DSA-SHA2-128s: 2,142–2,316 SHA-256 compressions on NIST's test vectors) multiplied by the per-call R1CS and UltraHonk costs cited in §1 (and, for the lower SLH-DSA R1CS bound, the 19,500 constraints per compression of the SPHINCS+ prototype). No public prime-field SNARK circuit for the unmodified FIPS 204 or FIPS 205 verifier was found in searches of GitHub and IACR ePrint made for this article in September 2026. These are floors for the hashing only, not measurements of complete circuits.
39. zkboo/zkboo-slhdsa — zkboo/zkboo-slhdsa@5fef0ca (2026-09-19): SLH-DSA-SHA2/SHAKE-128s/128f verification as ZKBoo circuits, "validated … against the official NIST ACVP FIPS 205 gen/val vectors", with a full prove/verify round trip over the 128s circuit (README).