Elliptic Curves

lib/ec/elliptic_curve.h is the curve layer that the ECDSA verification circuit consumes. It provides a curve-agnostic EllipticCurve<Field, W, kN> template plus two concrete instantiations, P256 and P256k1. Points live in standard projective (homogeneous) coordinates, scalar multiplication uses Bos-Coster when combining multiple scalars, and the concrete curves ship with pre-computed generators and orders.

When to reach for it

You are preparing an ECDSA witness off-circuit — hashing the message, computing r and s^{-1}, and packing (g \cdot e + pk \cdot r + (r_x, r_y) \cdot (-s)) for the circuit to check.
You are adding support for a new curve: this page shows what the EllipticCurve template needs.
You are debugging a signature mismatch and want to know whether the fault is in coordinate conversion, scalar reduction, or the circuit itself — this page draws the off-circuit/on-circuit boundary.

Design overview

EllipticCurve<Field, W, kN> is parametrised by:

Field — the base field the curve’s coordinates live in (e.g., Fp256).
W — the scalar’s word count (usually the same as the base field, but the template keeps them separate so the order can sit in a different field).
kN — the bit-length of the curve order, used to cap scalar-multiplication loops.

Point representation. Points are stored in standard projective (homogeneous) coordinates (x, y, z) representing the affine point (x/z, y/z). z = 0 is the point at infinity (canonical form (0, 1, 0)). Projective coordinates avoid field inversions during doubling and addition; the one inversion happens once at the end, in normalize().

Doubling and addition. Both routines have specialised fast paths:

doubleE/doubleEf has an a = 0 path (secp256k1) and an a = -3 path (NIST curves) that both use the exception-free complete projective formulas from Renes-Costello-Batina 2016. The general fallback path uses the 1998 Cohen-Miyaji-Ono formulas.
addE/addEf likewise has a = 0 and a = -3 specialisations using Renes-Costello-Batina complete projective addition, plus the Cohen-Miyaji-Ono general path with short-circuits for the point-at-infinity and self-addition edges.

Scalar multiplication.

scalar_multf(p, scalar) — single-point right-to-left (LSB-first) binary method.
scalar_multf(n, p[], scalar[]) — multi-scalar multiplication on n (P_i, k_i) pairs using the Bos-Coster heap algorithm (called internally as bos_coster) for n >= 2; n == 1 falls through to single-scalar, n == 0 returns identity. This is what verify_circuit uses for the triple-scalar-mul identity g \cdot e + pk \cdot r + (r_x, r_y) \cdot (-s); it minimises the total bit count across the three scalars. Each iteration chooses between a Bernstein step and a double-and-add step — whichever reduces the largest scalar more — which caps the worst-case at plain binary multiplication.

API surface

`EllipticCurve<Field, W, kN>`


template <class Field, size_t W, size_t kN>
class EllipticCurve {
 public:
  using Field = Field_;
  using Elt = typename Field::Elt;
  using N   = Nat<W>;
 
  struct ECPoint { Elt x, y, z; };  // standard projective
 
  // Curve constants
  ECPoint generator() const;
  ECPoint zero() const;
 
  // Point equality and validity
  bool equal(const ECPoint& p, const ECPoint& q) const;
  bool is_on_curve(const ECPoint& p) const;
 
  // Point ops
  void addE(ECPoint& p, const ECPoint& q) const;         // in-place
  ECPoint addEf(ECPoint p, const ECPoint& q) const;      // functional
  void doubleE(ECPoint& p) const;                        // in-place
  ECPoint doubleEf(ECPoint p) const;                     // functional
  void normalize(ECPoint& p) const;   // projective → affine, one inversion
 
  // Scalar multiplication
  ECPoint scalar_multf(const ECPoint& p, const N& scalar) const;
  ECPoint scalar_multf(size_t n, ECPoint p[], N scalar[]) const;
};

The curve order is not a method on EllipticCurve. It is exposed as an external constant in each curve-specific header: n256_order (p256.h) and n256k1_order (p256k1.h).

Concrete curves

P256 (lib/ec/p256.h) — instantiation with Fp256Base as the base field and the NIST secp256r1 curve constants: a = -3, b is the standard secp256r1 coefficient, generator and order drawn from the NIST specification. The curve order is exposed as the external constant n256_order.
P256k1 (lib/ec/p256k1.h) — instantiation with Fp256k1Base and the Bitcoin/Ethereum secp256k1 constants: a = 0, b = 7, different generator and order. The curve order is exposed as the external constant n256k1_order.

Both ship pre-computed generator() and zero() helpers so constructor cost is essentially nil.

The off-circuit / on-circuit split

EllipticCurve runs in native C++ at witness-generation time. The in-circuit check lives in circuits/ecdsa/verify_circuit.h and uses the sumcheck-friendly arithmetic gates from circuits/logic/, not the projective-doubling formulas above. The bridge is the witness: the prover uses EllipticCurve::scalar_multf to compute the intermediate points, packs them as witnesses, and the circuit verifies the elliptic-curve relation as a small arithmetic predicate over the affine coordinates. See the ECDSA gadget for that side.

See it used

longfellow-zk/lib/ec/p256_test.cc — p256_test.cc
longfellow-zk/lib/ec/p256k1_test.cc — p256k1_test.cc
longfellow-zk/lib/circuits/ecdsa/verify_witness.h — calls scalar_multf (multi-scalar overload) to build the witness for the triple-scalar-mul identity.

Prime Fields — the base field the curve stands on.
ECDSA Gadget — the in-circuit consumer.
Verifying a Signed Document — end-to-end pattern.