Skip to Content
⚠️ This documentation is AI-generated, for personal use only, and is not supported or endorsed by Google.
ReferenceCircuitsECDSA

ECDSA

In-circuit ECDSA verification for generic short Weierstrass curves, instantiated and tested for P-256 and secp256k1. Given a signature (r, s) over a digest e under public key (pk_x, pk_y), the gadget asserts the triple-scalar-multiplication identity g·e + pk·r + (rx, ry)·(-s) == identity, together with on-curve and non-zero checks on its inputs. Typical use inside Longfellow is verifying a TPM2 AIK signature or a TDX attestation-key signature inside a proof without revealing the signature or the attested payload.

When to reach for it

  • Verifying a TPM2 AIK signature over a quote digest inside a ZK proof, so the verifier learns only the predicate “this quote was signed by a key endorsed by the TPM manufacturer.”
  • Verifying an Intel TDX attestation-key signature (P-256) in a proof without revealing quote contents such as report data, measurements, or the signing key.
  • Verifying an issuer signature on a credential — the same pattern the mdoc case study uses to check the IACA-rooted signature over an mdoc MSO.

Design overview

The circuit is curve-generic via the EC template parameter: VerifyCircuit<LogicCircuit, Field, EC>. P256 and P256k1 are the tested instantiations, defined as EllipticCurve<Fp256Base, 4, 256> and EllipticCurve<Fp256k1Base, 4, 256> in lib/ec/.

The most common confusion point is that two distinct prime fields are in play:

  • The base field (e.g., Fp256Base for P-256) is the ambient ZK field — the field your surrounding circuit, the sumcheck prover, and the Ligero commitment live in. Every wire value is a base-field element.
  • The scalar field (e.g., Fp256Scalar) is the field of order n, the curve’s group order. This is where r, s, e, and the private key live. Scalar-field values enter the circuit as base-field elements via Montgomery encoding: the host witness calls to_montgomery before handing them off, and the circuit treats them as opaque base-field scalars. A bitwise comparison against the curve order then asserts r and s are in fact below n, closing the gap between “base-field element” and “valid scalar.”

Triple-scalar-multiplication form. Textbook ECDSA computes u₁ = e/s, u₂ = r/s, forms R' = u₁·G + u₂·Q, and checks R'.x == r. That shape is awkward in a circuit because the prover has to show a fresh scalar multiplication “finds” the point whose x-coordinate equals r. The gadget rewrites the identity as g·e + pk·r + (rx, ry)·(-s) == identity, where (rx, ry) is a witness-supplied curve point whose x-coordinate is claimed to equal r — shifting “find R” from a search into a witness-check. The 256-step loop is windowed: the witness supplies pre[8] — the x and y coordinates of the four precomputed sum-points {G+pk, G+R, R+pk, G+R+pk}, stored as eight field elements in the order [GPK_X, GPK_Y, GR_X, GR_Y, RPK_X, RPK_Y, GRPK_X, GRPK_Y]. G and pk themselves are not stored in pre[]: G is a compile-time constant injected via lc_.konst, and pk arrives as a public input. Three-bit advice digits select which of the eight table entries (identity, G, pk, G+pk, R, G+R, R+pk, G+R+pk) to add at each step, and the intermediate accumulator (int_x, int_y, int_z) after every step keeps the compiled circuit shallow.

Public vs. witness split. From verify_test.cc: pk_x, pk_y, and e are declared via lc.eltw_input() — public inputs visible to the verifier. Everything else — (rx, ry), the three inverses rx_inv, s_inv, pk_inv, the eight sums pre[8], the 256 bit-advice digits bi[kBits], and the 255 intermediate accumulator points — is pulled from the private tape by Witness::input(lc) after Q.private_input().

API surface

In-circuit

Constructor: VerifyCircuit(const LogicCircuit& lc, const EC& ec, const Nat& order). The order argument is the group order n; the constructor decomposes it into bits for range checks.

Entry point: void verify_signature3(EltW pk_x, EltW pk_y, EltW e, const Witness& w) const.

The nested Witness struct holds all the private wires. Its void input(const LogicCircuit& lc) method pulls every field from the private tape in a fixed order; call it on each witness instance after Q.private_input() and before verify_signature3.

Host-side witness

VerifyWitness3<EC, ScalarField> computes the witness values at proving time.

bool compute_witness(Elt pkX, Elt pkY, Nat e, Nat r, Nat s) derives (rx, ry), the three inverses, the precomputed sums, the bit-advice, and the intermediate points. It returns false if the signature is invalid (final accumulator is not the identity) — a useful “this won’t verify, don’t bother proving” short-circuit.

void fill_witness(DenseFiller<Field>&) pours the computed witness into the prover’s dense input buffer in the exact order Witness::input consumes it.

What the gadget does (and does not) check

Checked in-circuit. The identity g·e + pk·r + (rx, ry)·(-s) == identity is asserted by showing the accumulator is the point at infinity (ax == 0 and az == 0) after the 256-step loop. Both (pk_x, pk_y) and (rx, ry) are forced to satisfy the curve equation y² = x³ + ax + b. Non-zeroness of r (as rx in the base field), s, and pk_x is proven via witness inverses: the circuit asserts x · x_inv == 1, which is unsatisfiable if x is zero. Finally, r < order and s < order are enforced by a bitwise less-than comparison against the precomputed bit-decomposition of n.

Not checked — caller is responsible. The gadget does not assert e ≠ 0. The caller must rule out the all-zero digest — either by checking it in the public input, or by ensuring the hash gadget that produces e can never output zero. The gadget also does not hash the message: e arrives as an already-computed digest. Compose it with SHA-256 upstream to hash the attestation bytes (a TPM2 quote, a TDX report body) and feed the resulting digest in.

Cost

For a single P-256 verification, the compiled circuit has depth 7, roughly 21K wires, and about 43K total terms (per the header comment on VerifyCircuit). Cost is fixed per signature regardless of message length; the upstream hash gadget scales separately with payload size. Verifying k signatures costs roughly k times a single verification — exactly the shape verify_test.cc builds via its loop over numSigs.

Example

Adapted from verify_test.cc (the make_circuit driver):

QuadCircuit<Fp256Base> Q(p256_base);
const CompilerBackend cbk(&Q);
const LogicCircuit lc(&cbk, p256_base);
 
using Verc = VerifyCircuit<LogicCircuit, Fp256Base, P256>;
Verc verc(lc, p256, n256_order);
 
// Public inputs: (pk_x, pk_y, e) for the TPM2 AIK and the quote digest.
EltW pkx = lc.eltw_input();
EltW pky = lc.eltw_input();
EltW e   = lc.eltw_input();
 
Q.private_input();
 
Verc::Witness vwc;
vwc.input(lc);                      // pulls (rx,ry), inverses, pre[], bi[], int_*
verc.verify_signature3(pkx, pky, e, vwc);
 
auto CIRCUIT = Q.mkcircuit(1);

On the prover side, build a VerifyWitness3<P256, Fp256Scalar>, call compute_witness(pkX, pkY, e, r, s), then fill_witness(filler) after pushing the public inputs into the same dense buffer.

See it used

Last updated on
SHA-256MAC