Take no hint: soundness vulnerability in gnark zk-SNARK library
How a missing on-curve constraint in fake GLV scalar multiplication allowed ECDSA signature forgery in zk-SNARK circuits.
TL;DR: gnark’s fake GLV scalar multiplication did not check that the prover-supplied result point lies on the curve. In circuits that verify ECDSA signatures over P-256, P-384 and the STARK curve, a malicious prover could use this to forge a signature for any public key. Affected components include the in-circuit implementation of EIP-7951’s P-256 verification. The issue was fixed in gnark v0.16.4 (advisory GHSA-7fx8-hmgc-82jp).
Gnark is a Go library for writing zk-SNARK circuits; it compiles them into constraint systems (R1CS or PLONKish) that can be proven and verified with multiple backends, such as Groth16 and PLONK. The library ships with a collection of predefined gadgets (standard library), ranging from group algebra operations to cryptographic primitives.
We found a high-severity soundness vulnerability in one such mathematical operation used in the larger circuit of ECDSA signature validation. The issue could have made the verifier of every circuit that uses gnark’s ECDSA signature validation over curves such as P-256, P-384, and the STARK curve vulnerable to signature forgery.
In this blogpost we explain what all that means without requiring too much previous knowledge of ZK cryptography.
If there’s only one concept to understand about ZK in general, it is the fact that a circuit does not compute anything. A circuit is a set of relations that certain values must satisfy, not a sequence of instructions. In other words, a circuit doesn’t compute but rather constrains.
This is easy to miss when reading gnark code, because a circuit's Define method looks like ordinary imperative Go. But Define runs only once, at compile time, on symbolic variables. Each call to the frontend API (e.g. api.Mul, api.AssertIsEqual) doesn't produce a value but only records a constraint in a constraint system, such as R1CS for Groth16 or SparseR1CS for PLONK, which the backend then consumes. That's also why Go control flow can't depend on circuit variables: an if in Define is resolved at compile time, so conditional logic must be expressed with constraints like api.Select.
Actual computation happens elsewhere entirely: the prover solves the constraint system to obtain a witness, which is a vector of the concrete values satisfying every constraint, and the backend uses the witness to produce a proof that the verifier can check without ever re-running anything.
It doesn't help that circuit definition and witness computation are spatially overloaded, in the sense that the same lines of code serve both roles. Take api.Mul(a, b) for example. At compile time, a and b are placeholders, called wires in ZK jargon, that will only hold concrete values at proving time, so nothing gets multiplied. Instead, the call does two things: it allocates a new wire c and returns it, and it adds the constraint to the constraint system. At proving time, the solver builds the witness by walking the constraints in order and solving each one for its unknown wire. So is both the rule the proof enforces (a rule defined at compile time) and, when read by the solver, the instruction to compute c as a · b. The code only ever states constraints and the computation is derived from them in a separate stage. That's why a circuit reads like a program that computes its values step by step, even though it doesn't.
This overlap is confusing, but it is also defensive: in gnark's standard API, a value can't be computed without being constrained, on the principle that danger arises when the two roles are separated: a value that is computed but never constrained is the classic underconstrained-circuit bug that makes the news. Some frameworks, such as Circom, allow this separation by marking the boundary syntactically: for instance, Circom distinguishes assignment (<--) from constraint (===), but because they are separate operators, nothing prevents writing the first and forgetting the second.
However, this coupling of constraint definition at compile time and computation at proving time makes some values hard or expensive to compute because they must be expressed using constraints alone. This leaves no option other than “liberating” the computation entirely from the paradigm and allowing exceptions in the form of hints, which are values that are computed from outside the constraint format and that can be verified cheaply. A square root is a good example: computing one with constraints is cumbersome, but checking that r is the square root of x takes the single constraint . A hint is an ordinary Go function that runs outside the circuit, during witness solving, and hands its result back as a new wire:
Here, the coupling described above is untangled. NewHint returns a wire holding a computed value but adds no constraint at all, so the last line is what actually ties r to x. Without the AssertIsEqual constraint, nothing in the circuit would relate the two, and any value of r would be independent of x. The hint's code (sqrtHint) offers no guarantee either: the verifier never runs it, and a dishonest prover is free to swap in a different hint function that returns whatever is convenient. Stated otherwise, only the constraints are checked by the verifier.
Interestingly enough, the coupled API (the compute-and-constrain paradigm) brings safety because computing and constraining can't be separated, but that same coupling makes some computations impractical to express. Hints bring that flexibility back by separating the two roles again, and in doing so they reintroduce the very same pitfall that the coupling wanted to eliminate, i.e. a computed value whose constraint is missing.
The vulnerability we are illustrating is an instance of such a problem of lacking the appropriate constraint on a hint needed to optimize scalar multiplication over elliptic curves.
There are many ways to compute the scalar multiplication over an elliptic curve. The simplest is the double-and-add method, the elliptic curve version of square-and-multiply:
As an illustration, consider a scalar s = 5 with binary representation 101. The accumulator point is initialized to the point at infinity. During the initial iteration, doubling O preserves O; however, because the most significant bit equals 1, point addition updates T to Q. In the subsequent step, doubling T produces 2Q, and the addition is omitted since the second bit is 0. In the final loop, doubling T yields 4Q, where a non-zero trailing bit dictates a final addition, concluding with 5Q.
Double-and-add is simple, but it has a high cost floor: for an m-bit scalar, it performs one doubling per bit, so roughly m doublings no matter how the additions are arranged. Refinements such as windowing reduce the additions, but the doublings remain, and we must shorten the scalar to improve on those.
Suppose indeed we could rewrite as + where s₁ and s₂ are only about half as long as s. Both multiplications can share the same sequence of doublings, processing the bits of s₁ and s₂ side by side, so the doublings drop to roughly m/2. Recall that in double-and-add, each step doubles the accumulator and then, if the current bit is 1, adds Q. Doubling the accumulator scales everything it contains, so if it holds a combination of Q and U, one doubling advances both at once. We can therefore scan the bits of s₁ and s₂ together, from the most significant to the least. At each step we double the accumulator once, then look at the current pair of bits: for (1, 0) we add Q, for (0, 1) we add U, for (1, 1) we add Q + U, which we compute once in advance, and for (0, 0) we add nothing. After processing all the bits, the accumulator holds + . Since s₁ and s₂ are about m/2 bits long, this takes only about m/2 doublings instead of m, with at most one addition per step, the same as plain double-and-add on a single scalar of that length:
To put numbers on this, let n be the prime order of the group generated by the base point G. Since [n]Q = O for any point Q in this group, scalars only matter modulo n, so s has at most bitlen(n) bits, about 256 for a curve like P-256. Splitting s into two halves of about 128 bits each cuts the doublings from about 256 to about 128.
The difficulty is in finding a point U and a split of s (scalar decomposition) that makes this work cheaply. On certain curves, an extra algebraic structure provides exactly that. After all, in double-and-add, the curve is irrelevant to the algorithm, as the latter uses only the group operation without exploiting anything inherent to the curve structure. But some curves have additional structure. This is the idea behind the GLV method.
If U = [λ]Q for some known integer λ, then any split with s ≡ s₁ + s₂λ (mod n) gives
= + [s₂λ]Q = + . But computing U = [λ]Q is itself a scalar multiplication, the very thing we're trying to speed up, so this is only useful if U can be obtained in some other way.
On certain curves of the form , such as secp256k1 or BN254, if β is a non-trivial cube root of unity in the base field 𝔽ₚ (that is, and ), then the map , y) sends curve points to curve points (since (βx)³ = x³), and respects the group law, which makes it an endomorphism of the curve. By virtue of being an endomorphism, the map acts on the group generated by Q exactly like multiplication by some fixed scalar λ: . So instead of computing U = [λ]Q with a full double-and-add, we can simply compute U = , y): multiplying the x-coordinate of Q by the constant β gives the same point, at the cost of a single field multiplication.
This works only because the curve equation contains nothing but x³ and a constant. A general Weierstrass curve has the form , and with a ≠ 0, the same substitution gives (βx)³ + a(βx) + b = x³ + aβx + b, which differs from x³ + ax + b because . The point (βx, y) is no longer on the curve, so the trick no longer works.
That doesn't mean every curve with a ≠ 0 lacks a cheap endomorphism. Some other special families have one of their own, given by a different formula; curves with b = 0 are one example. But these are exceptions, since curves with such structure are rare and have to be deliberately chosen. A typical curve has no endomorphism as cheap as φ, and that includes widely used ones such as the NIST curves P-256 and P-384 and the STARK curve. As a consequence, the GLV method doesn't apply to them directly.
For curves without a cheap endomorphism, there's a different trick, but it works in a different setting. Suppose we don't need to compute R = ourselves but someone hands us a point R and claims that R = , and we only need to check that claim. This situation should by now sound familiar in the context of circuits, as it is indeed one of the motivations for introducing hints. We have learned that complex computations could become cumbersome to carry out in constrained arithmetic form, therefore we delegate them to functions computed at proving time, outside the circuit, by means of the hint mechanism. Once the task becomes verifying the computation, then the trick works as follows.
We must find two integers s₁ and s₂, each about half the length of n, such that . Such a pair always exists, and it can be found efficiently, for example by running the extended Euclidean algorithm on n and s and stopping halfway. Multiplying the claimed equation R = by s₂ gives = [s₂ · s]Q = , so it is enough to check that - = O. Conversely, if the equation holds and R is a point of the group, then multiplying both sides by the inverse of s₂ modulo n (which exists because n is prime and s₂ ≠ 0) gives back R = . Checking this one equation is therefore equivalent to checking the original claim R = , with the difference that the check is a two-scalar multiplication with half-length scalars, exactly the shape we had with GLV, so the doublings can be shared and their number drops to about m/2.
It is important to put emphasis on the distinction with the original GLV: In GLV, the second point U is produced by the endomorphism. Here it's the claimed result R itself, and the half-length scalars come from the decomposition of s rather than from any special curve structure. That's why the technique is called fake GLV: it works on any curve, including P-256, P-384 and the STARK curve, but only when we're verifying a result rather than computing one.
Gnark’s standard library provides circuit gadgets for scalar multiplication over P-256, P-384 and the STARK curve using the fake GLV method, implemented in the scalarMulFakeGLV function. Therein, the circuit must thus verify that some point R is equal to without actually computing but by checking that - = O. The two integers s₁ and s₂ are supplied as hints and constrained to satisfy the congruence . A non-triviality constraint is also enforced here.
The point R also is supplied by the prover as another hint; the circuit does not assert - = O literally but rather it asserts − + [3]R == [3]R. But [3]R appears identically on both sides and so it cancels. Therefore, we are in the presence of the following constraints:
And they appear to be enough to satisfy the claim that R = without the need to compute the scalar multiplication, thanks to the fake GLV trick.
But let’s reason about what the real computation of the scalar multiplication means: above, n is the order of the subgroup generated by the generator point G of the curve. For curves with cofactor h = 1, such as P-256, P-384, and the STARK curve, the subgroup ⟨G⟩ generated by G is the entire group of curve points, which has exactly n points (including the point at infinity O). Since n is prime, the group is cyclic and has no subgroups other than the trivial one {O} and itself. Since the group is closed under point addition, computing with Q ∈ ⟨G⟩ always yields another point R ∈ ⟨G⟩ on the curve. But recalling that the circuitry in scalarMulFakeGLV never really computes the scalar product but only checks the relation of constraint 3, we realize that nothing enforces curve membership of point R. So supplying an off-curve R can still satisfy the check.
In gnark, the multiplication proxied by R traces back to the circuit gadgets for the verification of ECDSA signatures. In general, one of the steps of the verification of a signature (r,σ) over a message msg entails the computation of a point P = (Pₓ, Pᵧ) = [msInv]G + [rsInv]PK, where msInv = z ⋅ σ⁻¹ (mod n) and rsInv = r ⋅ σ⁻¹ (mod n), with G the generator point, PK the public key of the signer, and z = hash(msg). The signature is valid if . Note that P is the addition of two components and, of the two, [rsInv]PK stands for exactly the scalar multiplication that ends up being checked with the fake GLV method rather than computed. Given that ECDSA verification prescribes to always ascertain that PK belongs to the curve, computing [rsInv]PK would yield a point on the curve, whereas scalarMulFakeGLV, lacking an AssertIsOnCurve constraint on R, also accepts an R that is off the curve.
The consequence is signature forgery. Because R = [rsInv]PK is no longer tied to the curve, the prover gains a handle on that component that an honest computation would never give, and hence on the sum P = [msInv]G + R and on its x-coordinate Pₓ. As mentioned, signature validity rests on a single scalar condition, . Once Pₓ is no longer forced to its honest value, the prover can make it meet that condition for an (r, σ) of their choosing, producing a proof that the circuit accepts as a valid ECDSA signature under a public key PK whose private key they never held. The missing AssertIsOnCurve then allows the prover to supply whichever [rsInv]PK balances the equation, and that single degree of freedom is all a forgery needs.
We would like to thank the gnark team at Consensys and SEAL for their quick response and smooth disclosure coordination with all the live protocols that were affected.
Lior Oppenheim
Giuseppe Cocomazzi