The Zcash ArboretumI–IX The Complete Arboretum
Contents
PDF
Theme

10 Elliptic curves

This section constructs elliptic-curve groups, the standard source of groups of roughly 2255 elements for which no discrete-logarithm attack faster than the generic O(N) attacks of 7.22 is known. The multiplicative groups 𝔽p× lack this property: the index-calculus algorithms exploit the factorisation of the integers behind the residues and run in subexponential time, so p must have thousands of bits to push the cheapest known attack beyond 2128 operations. An elliptic curve is the solution set of a cubic equation in two variables together with one additional point, the “point at infinity”. The section proves that these points form an abelian group under a geometric rule (10.16, associativity in sketch), derives explicit addition formulas, including complete ones valid for every input pair, bounds the group order by Hasse’s theorem (10.22), and states the elliptic-curve discrete logarithm problem.

Throughout, K is a field whose characteristic (4.30) is neither 2 nor 3; in the applications K is a prime field 𝔽p with p large. The running example is the pair of Pasta curves

Ep:y2=x3+5over ⁢𝔽p,Eq:y2=x3+5over ⁢𝔽q,

where p and q are the two 255-bit primes of 6.24 and 7.18,

p =2254+0⁢x⁢224698⁢f⁢c⁢094⁢c⁢f⁢91⁢b⁢992⁢d⁢30⁢e⁢d⁢00000001,
q =2254+0⁢x⁢224698⁢f⁢c⁢0994⁢a⁢8⁢d⁢d⁢8⁢c⁢46⁢e⁢b⁢2100000001.

The primes and the curve equations are the deployed constants, specified in §5.4.9.6 (“Pallas and Vesta”) of the Zcash protocol specification. The curve Ep is called Pallas and Eq Vesta. By design they form a cycle: the number of 𝔽p-points of Pallas equals q, and the number of 𝔽q-points of Vesta equals p. A toy curve over 𝔽11 is treated in parallel for hand computation.

10.1 Weierstrass equations

Definition 10.1 (Short Weierstrass equation).

Let K be a field of characteristic ≠2,3, and let a,b∈K. The short Weierstrass equation with coefficients a,b is the equation

y2=x3+a⁢x+b. (9)

The elements a and b are the Weierstrass coefficients.

Over a field of characteristic ≠2,3, an invertible affine change of variables reduces the most general cubic of this shape, y2+a1xy+a3y=x3+a2x2+a4x+a6, to the form (9): completing the square in y (possible since 2≠0) removes the xy and y terms but changes the quadratic coefficient to a2+a12/4; translating with the substitution x=X−(a2+a12/4)/3 (possible since 3≠0) removes the X2 term. Characteristics 2 and 3 are excluded for this reason: those cases require the longer Weierstrass form, and they do not arise for the Pasta curves, which are defined over large prime fields.

Cubics whose graph has a self-intersection or a cusp are excluded, because the group law defined below fails at such a singular point.

Definition 10.2 (Discriminant and nonsingularity).

The discriminant of the short Weierstrass equation (9) is

Δ=−16⁢(4⁢a3+27⁢b2)∈K. (10)

The equation, and the cubic f(x)=x3+ax+b, is nonsingular (or smooth) if Δ≠0, equivalently 4a3+27b2≠0. (The factor −16 is a convention inherited from the general Weierstrass form; over the fields considered here it is nonzero and does not affect the condition.)

The following lemma expresses 4a3+27b2 through the roots of a depressed cubic (a cubic with no square term); the smoothness criterion is derived from it.

Lemma 10.3 (Discriminant of a depressed cubic).

Let f(x)=x3+ax+b=(x−r1)(x−r2)(x−r3) with r1,r2,r3 in some field containing K. Then

∏i<j(ri−rj)2=−(4⁢a3+27⁢b2).
Proof.

Expanding (x−r1)(x−r2)(x−r3) and comparing coefficients with x3+ax+b gives Vieta’s relations for the depressed cubic:

r1+r2+r3=0,r1⁢r2+r1⁢r3+r2⁢r3=a,r1⁢r2⁢r3=−b.

Differentiating f(x)=∏i(x−ri) by the product rule and evaluating at a root annihilates every term but one: f′(ri)=∏j≠i(ri−rj). Multiplying the three evaluations pairs each factor (ri−rj) with (rj−ri):

∏if′⁢(ri)=∏i<j(ri−rj)⁢(rj−ri)=(−1)3⁢∏i<j(ri−rj)2.

It remains to compute ∏if′(ri)=∏i(3ri2+a). Expanding the product and collecting the elementary symmetric functions of the squares ri2,

∏i(3⁢ri2+a)=27⁢∏iri2+9⁢a⁢∑i<jri2⁢rj2+3⁢a2⁢∑iri2+a3.

Vieta’s relations evaluate each symmetric function: with e1=0, e2=a, e3=−b,

∑iri2=e12−2⁢e2=−2⁢a,∑i<jri2⁢rj2=e22−2⁢e1⁢e3=a2,∏iri2=e32=b2.

Substituting, ∏if′(ri)=27b2+9a3−6a3+a3=4a3+27b2, and the two displays together give ∏i<j(ri−rj)2=−(4a3+27b2). □

Proposition 10.4 (Equivalent conditions for smoothness).

Let f(x)=x3+ax+b∈K[x]. The following are equivalent.

  1. 1.

    The quantity 4a3+27b2 of 10.2 is nonzero.

  2. 2.

    The cubic f has no repeated root in the algebraic closure K¯—the smallest extension field of K in which every nonconstant polynomial over K factors into linear factors.

  3. 3.

    The polynomials f and f′ are coprime in K¯[x].

  4. 4.

    There is no point (x0,y0)∈K¯2 satisfying the curve equation y2=f(x) together with the two partial-derivative equations 2y=0 and f′(x)=0.

Proof.

Equivalence (1)⇔(2): over K¯ the monic cubic factors as f=(x−r1)(x−r2)(x−r3), and 10.3 gives ∏i<j(ri−rj)2=−(4a3+27b2). The left side vanishes exactly when two roots coincide, so f has a repeated root if and only if 4a3+27b2=0.

Equivalence (2)⇔(3): this is the derivative test of 5.40, applied over K¯ where f splits: a repeated root of f is a common root of f and f′, hence a common factor (x−α), and conversely a nontrivial gcd(f,f′) has a root in K¯ which is then a repeated root of f.

Equivalence (4)⇔(2): a singular point of the affine curve y2=f(x) is a point where both partial derivatives of g(x,y)=y2−f(x) vanish, namely ∂g/∂y=2y=0 and ∂g/∂x=−f′(x)=0. Since char(K)≠2, the first equation forces y0=0; the curve equation then gives f(x0)=0, which combined with f′(x0)=0 says x0 is a repeated root of f (5.40(1)). Conversely a repeated root x0 of f yields the singular point (x0,0). □

Definition 10.5 (Elliptic curve and rational points).

An elliptic curve over K is a short Weierstrass equation (9) with nonzero discriminant, 4a3+27b2≠0. For any field extension L⊇K, the set of L-rational affine points is

Eaff⁢(L)={(x,y)∈L×L:y2=x3+a⁢x+b},

and the set of L-rational points is

E⁢(L)=Eaff⁢(L)∪{𝒪},

where 𝒪 is a single formal symbol called the point at infinity. When L=K one writes E for the curve and E(K) for its rational points.

Remark 10.6 (The Pasta curves are smooth).

For the Pasta curves a=0 and b=5, so 4a3+27b2=27⋅25=675=33⋅52. The curve is therefore nonsingular whenever the characteristic does not divide 675, i.e. whenever the prime is neither 3 nor 5; the Pasta primes are far larger than 5, so the condition holds. More generally, any curve y2=x3+b with b≠0 is nonsingular away from characteristics 2 and 3.

10.2 The point at infinity, geometrically

The point 𝒪 is the identity element of the group law defined below. To exhibit it as a point of the curve, embed the affine plane in the projective plane. A point of the projective plane ℙ2(K) is an equivalence class [X:Y:Z] of nonzero triples (X,Y,Z)∈K3∖{0}, where (X,Y,Z)∼(λX,λY,λZ) for every λ∈K×. The affine points (x,y) embed as [x:y:1]; the points with Z=0 form the line at infinity, the extra “directions”. Homogenising the Weierstrass equation (9) by setting x=X/Z, y=Y/Z and clearing denominators gives the projective Weierstrass equation

Y2⁢Z=X3+a⁢X⁢Z2+b⁢Z3. (11)

Setting Z=0 in (11) forces X3=0, hence X=0, leaving the single projective point [0:1:0]. This is the point at infinity 𝒪. It is the point at infinity in the vertical direction, and every vertical line x=const passes through it.

10.3 The chord-and-tangent group law: geometry

The geometric definition of addition rests on one fact: a line meets a cubic curve in exactly three points, counted with multiplicity, once the point at infinity is included.

Definition 10.7 (The group law, geometric form).

Let P,Q∈E(K). Define P+Q as follows.

  • •

    If P=𝒪, set P+Q=Q; if Q=𝒪, set P+Q=P.

  • •

    Otherwise P=(x1,y1) and Q=(x2,y2) are affine. Draw the line ℓ through P and Q; if P=Q, let ℓ be the tangent line to the curve at P. The line ℓ meets the curve in a third point R′, counted with multiplicity, where a vertical ℓ has third point 𝒪. Define P+Q to be the reflection of R′ across the x-axis: if R′=(x3,−y3) then P+Q=(x3,y3), and if R′=𝒪 then P+Q=𝒪.

5 draws the chord and the tangent on the real points of y2=x3+5, the equation of the Pasta curves (10.6) read over ℝ.

Refer to caption
Figure 5: The chord-and-tangent law of 10.7 on the real points of E:y2=x3+5. Left: the chord ℓ through P and Q meets E a third time at R′, and P+Q is the reflection of R′ across the x-axis. Right: the tangent ℓ at P=(−1,2), of slope 3/4, meets E again at R′=(41/16,299/64), so [2]P=(41/16,−299/64), as (13) computes.

The reflection turns the rule that the three intersection points of any line with the curve add up to 𝒪 into a group law with identity 𝒪: reflection across the x-axis sends an affine point (x,y) to (x,−y), its additive inverse by the next subsection, and fixes 𝒪. The rule is stated here as a heuristic; every use of it below is discharged by explicit computation with the formulas of §10.4, which obtain the third intersection point from Vieta’s relations, as in 10.3.

10.4 Explicit affine formulas

Fix an elliptic curve E:y2=x3+ax+b over K, and let P=(x1,y1) and Q=(x2,y2) denote affine points.

Definition 10.8 (Negation).

Define

−𝒪=𝒪,−(x1,y1)=(x1,−y1).

The reflected point (x1,−y1) is again on the curve, since the curve equation depends on y only through y2. Geometrically, the line through P and −P is the vertical line x=x1, which meets the curve at P, −P, and 𝒪.

Construction 10.9 (Chord addition).

Suppose P,Q≠𝒪 and x1≠x2. The line through P and Q is y=λx+μ with

λ=y2−y1x2−x1,μ=y1−λ⁢x1.

Substituting the line into the curve equation, (λ⁢x+μ)2=x3+ax+b, and collecting terms gives

g⁢(x):=x3−λ2⁢x2+(a−2⁢λ⁢μ)⁢x+(b−μ2)=0.

Both x1 and x2 are roots of the monic cubic g: each point lies on the line and on the curve, so g(xi)=f(xi)−(λ⁢xi+μ)2=f(xi)−yi2=0. Since x1≠x2, factoring out (x−x1)(x−x2) (5.17, applied twice) leaves a monic linear factor x−x3 with x3∈K: the x-coordinate of the third intersection point R′. By Vieta, the sum of the roots equals the negative of the x2-coefficient—so x1+x2+x3=λ2, which determines the third root without factoring. Hence

x3=λ2−x1−x2,y3=λ⁢(x1−x3)−y1, (12)

and P+Q=(x3,y3). The y-formula already incorporates the reflection across the x-axis: the third intersection point is (x3,λx3+μ), and reflecting gives y3=−(λx3+μ)=−(λx3+y1−λx1)=λ(x1−x3)−y1.

Construction 10.10 (Tangent doubling).

Suppose P=Q=(x1,y1) with y1≠0. Implicit differentiation of y2=x3+ax+b yields the tangent slope: from 2ydy=(3x2+a)dx,

λ=3⁢x12+a2⁢y1.

With μ=y1−λx1, substituting y=λx+μ into the curve equation produces the same monic cubic g(x)=x3+ax+b−(λ⁢x+μ)2 as in 10.9, and here x1 is a double root. The statement that “tangency counts the intersection twice” is verified directly: g(x1)=f(x1)−y12=0, and

g′⁢(x1)=3⁢x12+a−2⁢λ⁢(λ⁢x1+μ)=3⁢x12+a−2⁢λ⁢y1=0

by the choice of λ, so x1 is a repeated root of g (5.40(1)). Factoring (x−x1)2 out of g leaves a monic linear factor x−x3 with x3∈K, and Vieta now reads x1+x1+x3=λ2, hence

x3=λ2−2⁢x1,y3=λ⁢(x1−x3)−y1,[2]⁢P=(x3,y3). (13)

The remaining cases are exactly those in which the line is vertical.

  • •

    If P=𝒪, then P+Q=Q; symmetrically if Q=𝒪.

  • •

    If x1=x2 but y1=−y2 (so Q=−P, including the subcase y1=y2=0), the line is vertical, the third point is 𝒪, and P+Q=𝒪.

  • •

    If P=Q and y1=0, the tangent is vertical (the slope formula in 10.10 has zero denominator), so [2]P=𝒪. These are exactly the points of order two, studied in 10.9.

Every case is covered: either an input is 𝒪; or both inputs are affine with x1≠x2 (use (12)); or both are affine with x1=x2, in which case either y1=−y2 (result 𝒪) or y1=y2≠0 (use (13)). 6 draws the two vertical cases.

Refer to caption
Figure 6: The vertical cases of the group law on the real points of E:y2=x3+5. Left: the line x=−1 through P=(−1,2) and −P=(−1,−2) meets E a third time only at the point at infinity 𝒪, so P+(−P)=𝒪. Right: at P=(−53,0), the only real point with y=0, the tangent x=−53 is vertical, so [2]P=𝒪. Each arrow points in the vertical direction, where both lines pass through 𝒪 (§10.2).
Proposition 10.11 (Closure).

For all P,Q∈E(K), the point P+Q computed by the case analysis above lies in E(K). In particular E(K) is closed under +.

Proof.

If either input is 𝒪, the result is the other input, which lies in E(K) by hypothesis; if the result is 𝒪, it lies in E(K) by definition. Otherwise (x3,y3) is produced by (12) or (13), and in both constructions x3 was exhibited as a root of the cubic g(x)=x3+ax+b−(λ⁢x+μ)2—as the third root beside x1,x2 in 10.9, and beside the double root x1 in 10.10. The equation g(x3)=0 states precisely that the third intersection point (x3,λx3+μ)=(x3,−y3) satisfies the curve equation; and since the curve equation is invariant under y↦−y, the reflected point (x3,y3) is on the curve too, so P+Q∈Eaff(K)⊆E(K). For rationality: all coordinates are rational expressions in x1,x2,y1,y2,a whose denominators are x2−x1 or 2y1, nonzero in the cases where each formula is invoked; so x3,y3∈K. □

Remark 10.12 (Complete versus incomplete addition).

The chord formula (12) is incomplete: it fails whenever x1=x2—the doubling and inverse cases—and an implementation must branch into the case analysis above. Complete addition formulas, valid for all input pairs including P=Q and P=−Q, exist for the curves used here, at the cost of more field operations per addition; 10.13 exhibits the deployed set and 10.14 proves it complete. Later volumes depend on the distinction. Halo 2’s elliptic-curve gadgets provide complete addition and use incomplete gates only where their callers justify the exclusions. The Sinsemilla hash of Orchard deliberately uses the incomplete formulas nondeterministically: an exceptional case does not violate the constraints but leaves the affected output unconstrained (the prover may choose the intermediate slope freely), which the specification models by letting the hash return ⊥ and weakening the proved statement accordingly; its Merkle path validity check may pass on the resulting sentinel values. Security follows not from the proof system but from Theorem 5.4.4 of the Zcash protocol specification: any input reaching an exceptional case of the incomplete addition yields a nontrivial discrete-logarithm relation among the Sinsemilla generators, so under discrete-log hardness on Pallas (10.31) such inputs are infeasible to find, for honest and adversarial provers alike.

A circuit cannot branch. A proof system checks the group law by a fixed list of polynomial identities in the input, output, and auxiliary cells of a row, evaluated on every row alike, so each branch of the case analysis appears as a factor that vanishes exactly when the branch is not taken. The deployed gate uses five auxiliary cells, four of them “inverse-or-zero” hints that let a polynomial test a field element for zero.

Construction 10.13 (Complete addition as deployed).

Let E:y2=x3+b over 𝔽p with p>3, and encode the point at infinity as the pair (0,0), so that every element of E(𝔽p) is a pair of field elements. For z∈𝔽p let inv0(z) be z−1 if z≠0 and 0 if z=0. For encoded inputs P=(xp,yp) and Q=(xq,yq) the prover fills five auxiliary cells,

α=inv0⁡(xq−xp),β=inv0⁡(xp),γ=inv0⁡(xq),δ={inv0⁡(yq+yp)if ⁢xq=xp,0otherwise,
λ={(yq−yp)⁢αif ⁢xq≠xp,3⁢xp2⁢(2⁢yp)−1if ⁢xq=xp⁢ and ⁢yp≠0,0otherwise,

and an output pair (xr,yr): it is Q if xp=0; else P if xq=0; else (0,0) if xq=xp and yq=−yp; else xr=λ2−xp−xq and yr=λ(xp−xr)−yp. The verifier accepts the row iff the twelve identities

(xq−xp)⁢((xq−xp)⁢λ−(yq−yp)) =0, (C1)
(1−(xq−xp)⁢α)⁢(2⁢yp⁢λ−3⁢xp2) =0, (C2)
xp⁢xq⁢(xq−xp)⁢(λ2−xp−xq−xr) =0, (C3a)
xp⁢xq⁢(xq−xp)⁢(λ⁢(xp−xr)−yp−yr) =0, (C3b)
xp⁢xq⁢(yq+yp)⁢(λ2−xp−xq−xr) =0, (C3c)
xp⁢xq⁢(yq+yp)⁢(λ⁢(xp−xr)−yp−yr) =0, (C3d)
(1−xp⁢β)⁢(xr−xq) =0, (C4a)
(1−xp⁢β)⁢(yr−yq) =0, (C4b)
(1−xq⁢γ)⁢(xr−xp) =0, (C5a)
(1−xq⁢γ)⁢(yr−yp) =0, (C5b)
(1−(xq−xp)⁢α−(yq+yp)⁢δ)⁢xr =0, (C6a)
(1−(xq−xp)⁢α−(yq+yp)⁢δ)⁢yr =0 (C6b)

hold in 𝔽p. These are, in this order, the twelve constraints of the complete-addition gate of the halo2_gadgets crate, each carrying there one further factor, a per-row cell equal to 1 on the rows where the gate applies and 0 elsewhere, which switches the list on or off; the crate assigns the cells as above, and the circuit field is the Pallas base field 𝔽p.

Proposition 10.14 (The gate is complete and sound).

Suppose no affine point of E(𝔽p) has x=0 and none has y=0—for y2=x3+b, that b is a non-square and −b a non-cube in 𝔽p. Then for all P,Q∈E(𝔽p), encoded as in 10.13:

  1. 1.

    (completeness) the prover’s cells satisfy (C1)–(C6b), and the output pair encodes P+Q;

  2. 2.

    (soundness) every (λ,α,β,γ,δ,xr,yr)∈𝔽p7 satisfying (C1)–(C6b) has (xr,yr) equal to the encoding of P+Q.

This is what complete means for a gate: the twelve identities are satisfiable for every input pair—doublings, inverse pairs, and the identity included—and the output they admit is unique, so they are the graph of the total function +:E(𝔽p)×E(𝔽p)→E(𝔽p), with no case left to a branch outside the constraint system.

Proof.

Under the hypothesis an encoded pair has x=0 iff it is 𝒪, and two affine points with the same x-coordinate have yq=±yp with yp≠0, so they are equal or inverse and not both. Every case uses one observation: for z∈𝔽p and any cell value h, the factor 1−zh equals 1 when z=0, whatever h is, while for z≠0 the honest choice h=z−1 makes it 0. A constraint of the shape (1−zh)t=0 therefore forces t=0 exactly when z=0 and is discharged by the honest hint otherwise. Five cases exhaust the input pairs.

Case P=𝒪. Then xp=0, so (C4a)–(C4b) force (xr,yr)=(xq,yq), the encoding of 𝒪+Q=Q; that is soundness. The prover outputs Q by the first clause, and its cells satisfy the rest: (C1) reads xq(xqλ−yq)=0 and holds for λ=yqinv0(xq); (C2) and (C3a)–(C3d) carry a factor xp or 2ypλ−3xp2, both zero; (C5a)–(C5b) are discharged by γ=xq−1 if Q≠𝒪, and read (xr,yr)=(0,0)=(xp,yp) if Q=𝒪; and (C6a)–(C6b) have first factor 1−xqα−0, which is 0 for α=xq−1 when Q≠𝒪, while for Q=𝒪 the other factor xr=yr=0 vanishes.

Case Q=𝒪, P≠𝒪. Then xq=0≠xp, so (C5a)–(C5b) force (xr,yr)=(xp,yp), the encoding of P: soundness. The prover outputs P by the second clause, with α=(−xp)−1 and λ=(−yp)α=yp/xp; then (C1) reads (−xp)(−xpλ+yp)=0 and holds; (C2) and (C6a)–(C6b) carry the factor 1−(xq−xp)α=0, the latter with δ=0; (C3a)–(C3d) carry xq=0; and (C4a)–(C4b) are discharged by β=xp−1.

Case P,Q affine with xq≠xp. Constraint (C1) forces λ to be the chord slope (yq−yp)/(xq−xp), and since xpxq(xq−xp)≠0, (C3a)–(C3b) force (xr,yr) to be the chord formula (12)—the encoding of P+Q, which is affine because xp≠xq. That is soundness. The prover’s λ is that slope and its output that formula, by the fourth clause; (C3c)–(C3d) contain the same two vanishing factors; (C2), (C4a)–(C4b), (C5a)–(C5b) are discharged by the honest α, β, γ; and (C6a)–(C6b) have first factor 1−1−0=0, since δ=0.

Case Q=−P, P affine. Here xq=xp and yq+yp=0, so both hint-bearing products in (C6a)–(C6b) are 0 whatever α and δ are, and the constraints force xr=yr=0: the encoding of P+(−P)=𝒪, which is soundness. The prover outputs (0,0) by the third clause; (C1) and (C3a)–(C3b) carry xq−xp=0, and (C3c)–(C3d) carry yq+yp=0; (C2), whose first factor is now 1, needs 2ypλ=3xp2, which the honest λ=3xp2(2⁢yp)−1 supplies (yp≠0); and (C4a)–(C5b) are discharged by β=γ=xp−1.

Case Q=P affine. Again xq=xp fixes (xq−xp)α=0, so (C2) forces λ to be the tangent slope 3xp2/(2yp), and since xpxq(yq+yp)=2xp2yp≠0, (C3c)–(C3d) force (xr,yr) to be the doubling formula (13)—the encoding of [2]P, affine because yp≠0. That is soundness. The prover’s λ is that slope and its output that formula, by the fourth clause; (C1) and (C3a)–(C3b) carry xq−xp=0; (C4a)–(C5b) are discharged by β=γ=xp−1; and (C6a)–(C6b) have first factor 1−0−2ypδ=0 for the honest δ=(2⁢yp)−1. □

Example 10.15 (The gate on the toy curve).

Pallas satisfies both hypotheses of 10.14: 5 is a non-square in 𝔽p (7.16) and −5 is not a cube (10.26). The toy curve y2=x3+5 over 𝔽11 of 10.38 satisfies neither—5=42 gives the points (0,±4), and (8,0) has order 2—so on it the gate can be examined both on inputs satisfying the hypotheses and on inputs violating them. For each input pair considered below, a script determines every output pair (xr,yr) that some assignment of the five auxiliary cells in 𝔽11 makes the twelve identities accept—the search over α,β,γ,δ factored by which identities mention each: β only (C4), γ only (C5), α and δ only (C2) and (C6)—so soundness is checked against all provers, not only the honest one. On the nine points 𝒪, (4,±5), (5,±3), (6,±1), (10,±2) with x,y≠0, all 81 ordered pairs—eight doublings, eight inverse pairs, seventeen involving 𝒪—admit exactly one output, the encoding of the true sum. Three of them, worked: for [2](5,3) the honest cells are λ=3⋅52⋅6−1=9⋅2=7 and δ=6−1=2, giving (xr,yr)=(49−10, 7(5−6)−3)=(6,1), the value of (13); for the inverse pair (5,3)+(5,8) the prover supplies the same λ=7 but δ=inv0(11)=0, and (C6a)–(C6b) force (0,0); for 𝒪+(5,3) the cells are α=5−1=9, λ=3⋅9=5, β=0, and (C4a)–(C4b) force (5,3). Off the admissible set the gate fails as the proof predicts. With P=(0,4) and Q=(5,3) the identities admit only the output (5,3)—the coordinate xp=0 is read as 𝒪—whereas P+Q=(10,9) (10.38); the pair (0,4)+(0,7) admits no output at all, (C4b) demanding yr=7 and (C5b) yr=4; and (8,0)+(8,0) admits none either, since (C2) reduces to 3⋅82=0, false in 𝔽11. On Pallas none of the three inputs exists, and the gate is complete.

10.5 Identity, inverses, commutativity, and associativity

Theorem 10.16 (Group law).

Let E be an elliptic curve over a field K. The set E(K) with the chord-and-tangent operation + of 10.7 is an abelian group with identity 𝒪.

Closure is 10.11. The next proposition establishes every remaining axiom except associativity.

Proposition 10.17 (Identity, inverses, commutativity).

The operation + on E(K) has the following properties.

  1. 1.

    The point 𝒪 is a two-sided identity: P+𝒪=𝒪+P=P for all P.

  2. 2.

    Every P has the two-sided inverse −P of 10.8: P+(−P)=𝒪.

  3. 3.

    The operation is commutative: P+Q=Q+P.

Proof.

Item (1) is the first clause of 10.7. For item (2), let P=(x,y) be affine. If y≠0, the line through P and −P=(x,−y) is vertical, so its third point is 𝒪 and P+(−P)=𝒪 by the vertical-line case; if y=0, then P=−P and [2]P=𝒪 directly by the vertical-tangent case; and 𝒪+(−𝒪)=𝒪+𝒪=𝒪. For item (3), the chord through P and Q does not depend on the order in which the two points are named, and neither does the tangent in the doubling case; algebraically, the formulas (12) are symmetric under the swap (x1,y1)↔(x2,y2)—the slope λ is unchanged, and x3=λ2−x1−x2 is symmetric in x1,x2. □

The remaining axiom is associativity, (P+Q)+R=P+(Q+R). A direct verification through the explicit formulas divides into many coordinate cases, each a lengthy rational-function identity; we sketch the conceptual proof instead.

Proof of associativity (sketch).

The proof uses the classical Cayley–Bacharach theorem for plane cubics: if two cubics with no common component meet in nine points counted with intersection multiplicity, then any third cubic passing through eight of them with the required multiplicities also passes through the ninth. To prove (P+Q)+R=P+(Q+R), one writes both sides via the chord-and-tangent construction and arranges the relevant intersections among the curve E and two degenerate cubics, each a product of three suitably chosen lines. Cayley–Bacharach forces the two candidate sums to coincide; its intersection-multiplicity formulation includes tangencies and coincident points. Replacing “reflect across the x-axis” by “the three points of any line sum to 𝒪” makes the bookkeeping uniform.

A complete, case-free treatment identifies E(K) with the degree-zero part Pic0(E) of the divisor class group of the curve via the map P↦[P]−[𝒪], a bijection that intertwines the two operations; the group law on Pic0(E) is manifestly associative, because it is inherited from addition of divisors modulo principal divisors. Either route yields a complete proof; both lie beyond the elementary scope of this volume, so we take associativity as established. □

Remark 10.18 (The notation [n]P).

For n∈ℤ and P∈E(K), we write [n]P for the n-fold sum P+⋯+P, with [0]P=𝒪 and [−n]P=−([n]P). This makes the abelian group E(K) a ℤ-module: integers act on points. The map n↦[n]P is the scalar multiplication of 10.20—not any coordinate-wise product.

10.6 Projective and Jacobian coordinates

The affine formulas (12) and (13) each require a field inversion, by x2−x1 or 2y1, which in a large prime field costs roughly as much as dozens of multiplications, whether computed by the extended Euclidean algorithm (6.1) or as zp−2 by Fermat (6.4). Over a long chain of group operations, as in scalar multiplication, it is cheaper to carry points in a redundant coordinate system whose group law uses only additions, subtractions, and multiplications, and to invert once at the end.

Remark 10.19 (Inversion-free coordinate systems).

Two redundant systems serve this purpose. In (homogeneous) projective coordinates, a triple [X:Y:Z] with Z≠0 represents the affine point (X/Z,Y/Z) on the projective curve (11), with 𝒪=[0:1:0]. In Jacobian coordinates, a triple (X:Y:Z) with Z≠0 represents (X/Z2,Y/Z3), under the equivalence (X,Y,Z)∼(λ2X,λ3Y,λZ); the curve equation becomes Y2=X3+aXZ4+bZ6. In either system addition and doubling need no divisions, at the cost of more multiplications per operation; the final recovery of affine coordinates computes Z−1 once, then the needed powers of it by multiplication. Jacobian coordinates usually yield the faster doubling and are the standard choice in cryptographic libraries; the pasta_curves crate used by Halo 2 carries its curve points in them. For curves y2=x3+b with a=0, the term aZ4 in the Jacobian doubling formulas vanishes, which lowers the cost of doubling; this is one reason the Pasta curves take a=0.

10.7 Scalar multiplication and double-and-add

Scalar multiplication computes, for a point P and an integer n≥0,

[n]⁢P=P+P+⋯+P⏟n⁢times.

Computing this by n−1 successive additions is infeasible when n has hundreds of bits. Double-and-add uses the binary expansion of n instead; it is the additive form of square-and-multiply (6.2), anticipated in 6.3.

Definition 10.20 (Double-and-add).

If n=0, return 𝒪. Otherwise write n=∑i=0k−1ni2i with digits ni∈{0,1} and top digit nk−1=1. The left-to-right double-and-add algorithm computes [n]P as follows: set R←P; for i=k−2 down to 0, set R←[2]R, and if ni=1 set R←R+P; return R.

Proposition 10.21.

For n≥1, double-and-add returns [n]P using exactly k−1 doublings and at most k−1 additions, where k=⌊log2n⌋+1 is the bit length of n. For n=0, it returns 𝒪 without a group operation.

Proof.

The case n=0 is immediate. Let n≥1, and let Rj denote the value of R after bits nk−1,…,nj have been incorporated. We claim Rj=[⌊n/2j⌋]P, by downward induction on j. At initialisation, Rk−1=P=[⌊n/2k−1⌋]P because the top bit is 1. Assuming Rj+1=[⌊n/2j+1⌋]P, the next iteration computes

[2]⁢Rj+1+[nj]⁢P=[ 2⁢⌊n/2j+1⌋+nj]⁢P=[⌊n/2j⌋]⁢P,

where the last step is the digit identity 2⌊n/2j+1⌋+nj=⌊n/2j⌋: stripping the last bit of ⌊n/2j⌋ and appending it again recovers the number. At j=0 the invariant reads R0=[n]P, which is what the algorithm returns. For the counts, the loop has exactly k−1 iterations, each performing one doubling and at most one addition. □

Scalar multiplication by an n-bit scalar therefore costs O(n) group operations—O(n) field operations up to constant factors, or O(nlog2p) bit operations with schoolbook field arithmetic. Elliptic-curve cryptography rests on the contrast between this forward map and the apparent hardness of inverting it (§10.11).

10.8 The group structure of E(𝔽p)

Let K=𝔽p with p prime, p>3. Each of the p values of x admits at most two values of y (5.18, applied to y2−f(x) as a polynomial in y), so with 𝒪 there are at most 2p+1 points, and by 10.16 the set E(𝔽p) is a finite abelian group. Hasse’s theorem bounds its order.

Theorem 10.22 (Hasse).

Let E be an elliptic curve over 𝔽p. Write

#⁢E⁢(𝔽p)=p+1−t,

which defines the integer t, called the trace of Frobenius. Then

|t|≤2⁢p;

equivalently, #E(𝔽p) lies in the Hasse interval [p+1−2p,p+1+2p].

Proof (sketch).

The count has an exact character-sum expression. For fixed x, the number of y∈𝔽p with y2=f(x) is 1+(f⁢(x)p) when f(x)≠0—two solutions for a nonzero square, none for a non-square (7.12)—and exactly 1=1+(0p) when f(x)=0, using the Legendre symbol of 7.14 with the convention (0p)=0. Summing over x,

#⁢Eaff⁢(𝔽p)=∑x∈𝔽p(1+(x3+a⁢x+bp))=p+∑x∈𝔽p(x3+a⁢x+bp),

so t=−∑x(x3+a⁢x+bp). Heuristically, as x ranges over 𝔽p the value f(x) is a nonzero square about half the time (two points), a non-square about half the time (none), and zero occasionally (one point); the p summands ±1 behave like a random walk, and Hasse’s bound |t|≤2p is exactly square-root cancellation in this character sum.

The conceptual proof realises t as the trace of the p-power Frobenius endomorphism π:(x,y)↦(xp,yp) of the curve—the curve-level counterpart of the field automorphism of 6.15. One shows that π satisfies the characteristic equation π2−[t]π+[p]=0 in the endomorphism ring of E, and that the associated quadratic form (the degree) is positive definite; the discriminant condition t2−4p≤0 for the complex roots of the characteristic polynomial then yields |t|≤2p. The full argument requires the theory of isogenies and the Weil pairing, beyond the present scope. □

By Hasse’s theorem the relative deviation of the order from p is of order p−1/2, so the bound guarantees without a brute-force count that the group has about p elements, about 255 bits for the Pasta curves. The bound also underlies the point-counting algorithms (Schoof–Elkies–Atkin) that compute the exact order in polynomial time, by which curve designers certify their group orders.

Cryptographic use requires E(𝔽p) to contain a large subgroup of prime order. The general structure theory of E(𝔽p) is not needed in this series: the Pasta curves are designed so that #E(𝔽p) is itself prime, and a group of prime order is cyclic with no proper nontrivial subgroups (3.34).

10.9 Torsion, the cofactor, and prime-order subgroups

Definition 10.23 (Order of a point and torsion).

The order of a point P∈E(𝔽p) is its order as a group element (3.11): the least integer m≥1 with [m]P=𝒪. It exists and divides #E(𝔽p), by Lagrange’s theorem (3.29 via 3.30). For an integer m≥1, the m-torsion subgroup is

E⁢[m]={P∈E⁢(𝔽p¯):[m]⁢P=𝒪},

the points over the algebraic closure killed by m; its rational part is E(𝔽p)[m]=E[m]∩E(𝔽p).

Definition 10.24 (Cofactor).

Suppose #E(𝔽p)=h⋅r, where r is the (large) prime to be used and h is the remaining factor. The integer h is the cofactor, and r is the order of the prime-order subgroup: a point P of order r generates a cyclic subgroup ⟨P⟩≅ℤ/rℤ, and cryptographic protocols operate in this subgroup.

A nontrivial cofactor h>1 is undesirable: it admits small-subgroup points, of order dividing h, which can leak information or break protocol assumptions—the small-subgroup attacks of 7.25. Implementations therefore either clear the cofactor, multiplying incoming points by h, or use prime-order curves with h=1. The Pasta curves have cofactor 1: the orders #Ep(𝔽p)=q and #Eq(𝔽q)=p are themselves prime, so Ep(𝔽p)≅ℤ/qℤ and Eq(𝔽q)≅ℤ/pℤ, and no cofactor clearing is needed.

Proposition 10.25 (Two-torsion).

The affine points of order 2 in E(𝔽p) are exactly the points (x0,0) with f(x0)=x03+ax0+b=0. Hence E(𝔽p) has 0, 1, or 3 points of order 2 according as f has 0, 1, or 3 roots in 𝔽p; and #E(𝔽p) is even if and only if f has a root in 𝔽p.

Proof.

A point P=(x,y) has order 2 iff P=−P and P≠𝒪, i.e. y=−y, i.e. y=0 (since char(𝔽p)≠2); the curve equation then forces f(x)=0. Conversely each root x0 of f in 𝔽p gives the order-2 point (x0,0).

Next, the number N of roots of f in 𝔽p can only be 0, 1, or 3: two roots force a third. Suppose f has distinct roots r1≠r2 in 𝔽p. The factor theorem (5.17) gives f=(x−r1)h; evaluating at r2 yields 0=(r2−r1)h(r2), so h(r2)=0, and a second application factors the monic cubic completely, f=(x−r1)(x−r2)(x−r3) with r3∈𝔽p—explicitly r3=−r1−r2 by Vieta, the depressed cubic having no x2 term. Nonsingularity says f has no repeated root even over 𝔽p¯ (10.4(2)), so r3∉{r1,r2}, and f has exactly three roots (5.18 caps the count). Hence N∈{0,1,3}, matching the trichotomy of the statement. Together with 𝒪 the order-2 points form the rational 2-torsion subgroup E(𝔽p)[2], which is accordingly trivial, ℤ/2ℤ, or ℤ/2ℤ×ℤ/2ℤ.

For the parity claim, consider negation P↦−P, an involution—a self-inverse map—of the finite set E(𝔽p). Its fixed points are exactly 𝒪 and the points (x0,0); every other point pairs off with its distinct negative into a 2-element orbit. Counting the set by orbits,

#⁢E⁢(𝔽p)≡1+N(mod2),

where N∈{0,1,3} is the number of roots of f in 𝔽p. Hence #E(𝔽p) is even iff N is odd, i.e. iff N≥1, i.e. iff f has a root in 𝔽p. (In general, an involution of a finite set determines the cardinality of the set modulo 2 from its fixed points alone.) □

Remark 10.26 (No two-torsion on the Pasta curves).

For y2=x3+5 over 𝔽p, the curve has a point of order 2 iff x3+5=0 has a solution, i.e. iff −5 is a cube in 𝔽p. For the Pasta primes the order #Ep(𝔽p)=q is odd (it is prime), so there are no rational 2-torsion points; consistently, −5 is not a cube in 𝔽p.

10.10 Base fields, scalar fields, and the Pasta cycle

An elliptic-curve computation involves two prime fields. Every operation of the group law on E(𝔽p)—the slope λ=(y2−y1)(x2−x1)−1, the squarings, and the inversions needed to add and to double—is arithmetic in 𝔽p, the base field (or coordinate field), performed with the prime-field algorithms of 6.1. Keys and signatures reside in the subgroup of large prime order r (10.24), and a scalar multiplication P↦[s]P on a point of order r depends only on smodr, since [r]P=𝒪 (3.12); scalars are therefore residues modulo r, and since r is prime, they form a field (4.26).

Definition 10.27 (Base field and scalar field).

For an elliptic curve used in cryptography, with a prime-order subgroup of order r:

  • •

    the base field 𝔽p is the field over which the curve is defined and in which point coordinates lie;

  • •

    the scalar field 𝔽r=ℤ/rℤ is the field of scalars by which one multiplies points, i.e. the integers modulo the subgroup order r.

Both are prime fields, but in general p≠r.

Remark 10.28 (Two fields at once, and the Pasta cycle).

Scalar arithmetic runs in 𝔽r and coordinate arithmetic in 𝔽p. Halo 2’s Pallas and Vesta curves (the “Pasta” pair) form a cycle of curves: the base field of one is the scalar field of the other and vice versa,

#⁢Ep⁢(𝔽p)=q,#⁢Eq⁢(𝔽q)=p,

so the scalar field of Pallas is 𝔽q, the base field of Vesta, and symmetrically (§5.4.9.6 of the Zcash protocol specification). This lets a proof system express the verifier of one curve’s arithmetic natively in the field of the other, which enables the recursive proof composition of Halo 2. Both primes are chosen ≡1(mod232), so by 6.23 each field contains a multiplicative subgroup of order 232, furnishing the high-order roots of unity that the number-theoretic transform of 9 needs for fast polynomial multiplication.

10.11 The elliptic-curve discrete logarithm problem

The discrete logarithm problem of 7.21, stated there for an abstract cyclic group, reads as follows for elliptic curves in additive notation.

Definition 10.29 (ECDLP).

Let P∈E(𝔽p) be a point of large prime order r, generating G=⟨P⟩. The elliptic-curve discrete logarithm problem (ECDLP) is: given P and a point Q∈G, find the unique integer n∈{0,1,…,r−1} with Q=[n]P. One writes n=logPQ.

The map n↦[n]P is a group isomorphism ℤ/rℤ→G (3.43), so a discrete logarithm always exists and is unique; the difficulty of the problem is purely computational. The forward map is fast by double-and-add (10.21); on a well-chosen curve the best known algorithms to invert it are the two generic attacks, which transfer verbatim from 7.22 to the additive setting.

Proposition 10.30 (Square-root attacks).

Baby-step giant-step solves the ECDLP in a group of prime order r in O(r) group operations and O(r) space. Pollard’s rho method matches the O(r) bound in expectation with only O(1) space, under a modelling assumption on its pseudo-random walk that is stated explicitly in the proof and is unproved for every concrete walk.

Proof.

For baby-step giant-step, set m=⌈r⌉ and write the unknown logarithm as n=im+j with 0≤i,j<m; since m2≥r, every n∈{0,…,r−1} has such a decomposition. Tabulate the baby steps [j]P for j=0,…,m−1 (a table of m points, built with m−1 additions), compute S=[m]P once, and walk the giant steps Q−[i]S for i=0,1,2,…, testing each against the table. At i=⌊n/m⌋ the walk hits Q−[im]P=[n−im]P=[j]P, a table entry; the collision reveals i and j, hence n=im+j. Both the table and the walk cost O(m)=O(r) group operations, and the table holds O(r) points.

Pollard’s rho eliminates the table, at the price of an explicitly heuristic analysis. The algorithm takes a pseudo-random walk on G whose every position is maintained in the form [a]P+[b]Q with known coefficients a,b, started from such a combination with random coefficients; the walk’s next step depends only on the current point, so once the walk revisits a point it cycles from then on. A repeat is therefore detected with O(1) memory: run a second copy of the walk at double speed, and the two copies meet at a common point inside the cycle within a constant factor of the first repeat time. Modelling assumption: the successive positions of the walk behave like independent uniform samples from G. No proof of this is known for any concrete walk—the assumption is what “well-designed” means, and experiment supports it—and the rest of the argument is conditional on it. Under the assumption, the first k positions are pairwise distinct with probability at most e−k⁢(k−1)/(2⁢r) by the birthday bound (a forward reference: 11.18 belongs to the closing section), so the number T of steps to the first repeat satisfies Pr[T>k]≤e−k⁢(k−1)/(2⁢r). The tail-sum formula (11.33) converts the tail bound into an expectation bound: with m=⌈r⌉ and r≥4,

𝔼⁢[T]=∑k≥1Pr⁡[T≥k]≤m⁢∑j≥0Pr⁡[T>j⁢m]≤m⁢(1+∑j≥1e−j/4)=O⁢(r),

where the middle step groups the indices k into blocks of length m, bounding each block by its first term, and the last uses jm(jm−1)≥j2m(m−1)≥j2(r−r)≥j2r/2 for j≥1, so that Pr[T>jm]≤e−j2/4≤e−j/4, a convergent geometric tail. A repeat presents one group element with two representations, [a]P+[b]Q=[a′]P+[b′]Q. If b′≢b(modr), this rearranges to [a−a′]P=[b′−b]Q=[(b′−b)n]P, whence

n≡(a−a′)⁢(b′−b)−1(modr),

the inverse existing because r is prime. If instead b′≡b, then [a]P=[a′]P forces a≡a′: the two representations coincide, the collision reveals nothing, and the walk is restarted with fresh random starting coefficients; that such degenerate collisions are rare is a further part of the heuristic, borne out in practice. Both algorithms run in time exponential in the bit length log2r. □

Remark 10.31 (Best known attacks on well-chosen curves).

For well-chosen curves, no unrestricted classical attack faster than O(r) is known; this is not an unconditional lower bound for all classical algorithms. In the classical generic-group model, however, Shoup’s matching lower bound is proved (7.22). For the 255-bit Pasta orders r, slightly above 2254, the square root is r≈2127.0, and the expected cost of Pollard’s rho on these curves is about 2126 group operations (10.40), infeasible. Curves with special structure can be weaker, and the known weak classes are avoided by design. Anomalous curves, those with #E(𝔽p)=p, admit a polynomial-time attack through the formal group. The MOV/Frey–Rück attack transfers the ECDLP into a finite-field discrete logarithm when the embedding degree—the least k≥1 with r∣pk−1, i.e. the degree (8.4; the dimension of the extension over its base) of the smallest extension of 𝔽p whose multiplicative group contains a subgroup of order r—is small, where index calculus applies. Cryptographically secure curves, the Pasta curves included, are chosen with a large prime subgroup order, a large embedding degree, and #E(𝔽p)≠p, which excludes every known subexponential attack.

Remark 10.32 (The index-calculus contrast).

In 𝔽p× the index-calculus method solves the discrete logarithm in subexponential time Lp[1/3]—shorthand for 2Θ⁢(λ1/3⁢(log⁡λ)2/3) operations in the bit length λ=log2p, a notation defined precisely in 11.60 of the closing section—exploiting the integer arithmetic behind the residues (7.22); those groups must therefore be large. On a well-chosen elliptic curve no index calculus is known—the points offer no analogue of “factoring into small primes”—so the generic O(r) bound stands, and much smaller groups suffice: about 256 bits for 128-bit security, versus thousands of bits for 𝔽p×. Smaller groups mean faster arithmetic and shorter keys, which is why elliptic curves dominate modern protocols, including Halo 2.

10.12 The j-invariant and the GLV endomorphism

The j-invariant classifies curves up to isomorphism; when it vanishes, as it does for the Pasta curves by design, the curve has an additional endomorphism.

Definition 10.33 (j-invariant).

The j-invariant of the curve y2=x3+ax+b (with 4a3+27b2≠0) is

j=1728⁢4⁢a34⁢a3+27⁢b2∈K,

where 1728=123 is a normalising constant of historical origin.

Proposition 10.34.

Two elliptic curves over K¯ are isomorphic over K¯ if and only if they have the same j-invariant. The admissible coordinate changes preserving short Weierstrass form are (x,y)↦(u2x,u3y) for u∈K¯×, under which (a,b)↦(u4a,u6b); the combination j is invariant.

Proof (sketch).

A direct computation shows that the only isomorphisms between short Weierstrass curves fixing 𝒪 are the scalings (x,y)↦(u2x,u3y). Substituting x=u−2x′, y=u−3y′ into y2=x3+ax+b and clearing u6 gives y′⁣2=x′⁣3+u4ax′+u6b, which is the stated action on coefficients. Under it, numerator and denominator of 4a3/(4a3+27b2) both scale by u12, so j is unchanged. Conversely, given two curves with equal j-invariants one solves for a suitable u transforming one coefficient pair into the other, treating separately the cases j=0 (both a vanish) and j=1728 (both b vanish). □

Remark 10.35 (The Pasta curves have j=0).

For y2=x3+b one has a=0, so j=0; both Pasta curves have j=0. Curves with j=0 admit an additional automorphism of order 3, which underlies the efficient endomorphism described next. (In the other exceptional case, b=0 gives j=1728 and an order-4 automorphism.) The Pasta design chooses j=0 to make the Gallant–Lambert–Vanstone (GLV) speedup available, which roughly halves the doubling count in scalar multiplication.

Proposition 10.36 (The GLV endomorphism for y2=x3+b).

Suppose 𝔽p contains a primitive cube root of unity ω, i.e. p≡1(mod3) (6.23), so ω∈𝔽p satisfies ω2+ω+1=0. On E:y2=x3+b, the map

ϕ⁢(x,y)=(ω⁢x,y),ϕ⁢(𝒪)=𝒪,

is a group endomorphism of E(𝔽p). Let G=⟨P⟩ be a subgroup of prime order r with r≡1(mod3) and ϕ(G)⊆G. Then ϕ acts on G as multiplication by a scalar: there is λ∈ℤ/rℤ with λ2+λ+1≡0(modr) and

ϕ⁢(Q)=[λ]⁢Qfor all ⁢Q∈G.

For the Pasta curves the hypothesis ϕ(G)⊆G is automatic, since E(𝔽p) itself is the prime-order group G; and r≡1(mod3) holds for both orders.

Proof.

The map lands on the curve. If y2=x3+b then y2=(ω⁢x)3+b, because ω3=1; so (ωx,y)∈E(𝔽p).

The map is a homomorphism. We check ϕ(P1+P2)=ϕ(P1)+ϕ(P2) against the case analysis of §10.4. The 𝒪 cases are immediate, and ϕ(−P)=−ϕ(P) since negation touches only y; in particular the inverse case ϕ(P)+ϕ(−P)=𝒪=ϕ(𝒪) is respected, and ϕ preserves the case split, since it preserves equality of x-coordinates. For a chord (x1≠x2), the slope transforms as

λ′=y2−y1ω⁢x2−ω⁢x1=ω−1⁢λ=ω2⁢λ,

using ω−1=ω2. Then, by (12) and ω4=ω,

x′3=λ′⁣2−ω⁢x1−ω⁢x2=ω4⁢λ2−ω⁢x1−ω⁢x2=ω⁢(λ2−x1−x2)=ω⁢x3,
y′3=λ′⁢(ω⁢x1−x′3)−y1=ω2⁢λ⋅ω⁢(x1−x3)−y1=λ⁢(x1−x3)−y1=y3,

so ϕ(P1)+ϕ(P2)=(ωx3,y3)=ϕ(P1+P2). The tangent case is identical, with λ′=3(ω⁢x1)2/(2y1)=ω2λ in (13).

The relation ϕ2+ϕ+id=0. Let P=(x,y) be affine; we show P+ϕ(P)+ϕ2(P)=𝒪 directly from the formulas of §10.4.

First let x≠0. The points P=(x,y), ϕ(P)=(ωx,y), ϕ2(P)=(ω2x,y) share their y-coordinate and have pairwise distinct x-coordinates, since 1,ω,ω2 are distinct and x≠0. The chord formula (12) applies to P+ϕ(P), with slope λ=(y−y)/(ωx−x)=0:

x3=0−x−ω⁢x=−(1+ω)⁢x=ω2⁢x,y3=0⋅(x−x3)−y=−y,

using 1+ω+ω2=0. Hence P+ϕ(P)=(ω2x,−y)=−ϕ2(P) (10.8), and P+ϕ(P)+ϕ2(P)=𝒪.

If instead x=0, the three points coincide: ϕ(P)=ϕ2(P)=P. Here y≠0, since x=y=0 on the curve would force b=0, which nonsingularity 27b2≠0 forbids; so the doubling formula (13) applies, with a=0:

λ=3⋅02+02⁢y=0,x3=0−2⋅0=0,y3=0⋅(0−0)−y=−y,

so [2]P=(0,−y)=−P, hence P+ϕ(P)+ϕ2(P)=[3]P=𝒪 in this case too. (The three points P, ϕ(P), ϕ2(P) are exactly the intersections of the horizontal line through P with the curve, the roots of X3=y2−b being x, ωx, ω2x; the computation above proves the rule “three points of a line sum to 𝒪” for this line, including the triple intersection at x=0.)

With ϕ(𝒪)=𝒪 the identity holds on all of E(𝔽p); as an identity of endomorphisms, ϕ2+ϕ+id=0. Moreover ϕ3=id, since ω3=1; and whenever #E(𝔽p)>3—as always at cryptographic sizes, the Pasta curves included—ϕ has order exactly 3, because at most two affine points, (0,±y0) with y02=b, share the coordinate x=0, so some point of E(𝔽p) has x≠0 and ϕ moves it. The proviso is necessary: y2=x3+4 over 𝔽7 has only the three points 𝒪, (0,2), (0,5), and there ϕ=id.

Action on G as a scalar. The subgroup G≅ℤ/rℤ is cyclic with generator P, and ϕ(G)⊆G by hypothesis, so ϕ(P)=[λ]P for some λ∈ℤ/rℤ; then for any Q=[m]P∈G, the homomorphism property gives ϕ(Q)=[m]ϕ(P)=[mλ]P=[λ]Q. (This is the statement Hom(ℤ/rℤ,ℤ/rℤ)≅ℤ/rℤ: an endomorphism of a cyclic group is determined by, and equal to multiplication by, the image of a generator.) Applying the endomorphism relation to P,

[λ2+λ+1]⁢P=𝒪⟹λ2+λ+1≡0(modr),

since P has order r. Consistently, this congruence is solvable exactly when 𝔽r contains a primitive cube root of unity, i.e. when r≡1(mod3) (6.23 again)—the hypothesis of the statement. □

Remark 10.37 (How GLV halves the doubling count).

Computing ϕ costs a single field multiplication x↦ωx, negligible against a group operation. A scalar n∈ℤ/rℤ is decomposed as

[n]⁢P=[n1]⁢P+[n2]⁢ϕ⁢(P),n≡n1+n2⁢λ(modr),

where n1,n2 can each be taken about 12log2r bits long; such a pair is found by lattice reduction in the lattice of pairs (c1,c2) with c1+c2λ≡0(modr). The two half-length scalar multiplications are then run simultaneously, sharing their doublings (Straus–Shamir’s trick): one double-and-add loop of half the length, adding P, ϕ(P), or both according to the bits of n1 and n2. The result costs about half the doublings of a single full-length double-and-add; this saving is one reason the Pasta curves take the form y2=x3+b over primes p≡1(mod3).

10.13 A worked toy example

Example 10.38 (The curve y2=x3+5 over 𝔽11).

Take p=11: then p>3, and 4⋅0+27⋅52=675≡4≢0(mod11), so the curve E:y2=x3+5 is nonsingular over 𝔽11 (10.5). Squaring the residues 0,1,…,10 yields the squares {0,1,3,4,5,9}, so the nonzero quadratic residues are {1,3,4,5,9}. Tabulating f(x)=x3+5mod11 and reading off the y-values:

xx3mod11f⁢(x)=x3+5y⁢ with ⁢y2=f⁢(x)005±4⁢(42=16≡5)116none⁢(6∉QR)282none3510none493±5⁢(52=25≡3)549±3671±1727none8600938none10104±2

Counting: the five values x∈{0,4,5,6,10} contribute two points each (10 points), x=8 contributes the single point (8,0), and 𝒪 is the remaining point:

#⁢E⁢(𝔽11)=10+1+1=12.

Hasse’s bound holds: p+1=12, so the trace is t=0, and |t|=0≤211≈6.63. The point (8,0) has order 2, consistent with 10.25 and the even order 12; here −5≡6 is a cube, namely 83=512≡6.

An addition. Let P=(0,4) and Q=(5,3). Since x1=0≠5=x2, the chord formula (12) applies:

λ=3−45−0=(−1)⋅5−1=(−1)⋅9=−9≡2(mod11),

using 5−1=9 (check: 5⋅9=45≡1). Then

x3=λ2−x1−x2=4−0−5=−1≡10,y3=λ⁢(x1−x3)−y1=2⁢(0−10)−4=−24≡9,

so P+Q=(10,9). The result is on the curve: 92=81≡4 and 103+5=1005≡4(mod11), as required.

A doubling. Take P=(0,4). With a=0, formula (13) gives

λ=3⁢x12+a2⁢y1=08=0,x3=λ2−2⁢x1=0,y3=λ⁢(x1−x3)−y1=−4≡7,

so [2](0,4)=(0,7)=−(0,4). Hence [3](0,4)=𝒪: the point (0,4) has order 3.

The GLV endomorphism. Since 11≡2(mod3), the field 𝔽11 contains no primitive cube root of unity (6.23 requires 3∣p−1), so the GLV map is not available over 𝔽11. The Pasta primes do satisfy p≡q≡1(mod3), so GLV applies there. For a small GLV-friendly illustration take instead p=13≡1(mod3), where ω=3 satisfies 32+3+1=13≡0(mod13); then ϕ(x,y)=(3x,y) is a nontrivial endomorphism of y2=x3+b over 𝔽13.

10.14 Pallas and Vesta assembled

Example 10.39 (The Pasta curves).

For the running example y2=x3+5, with p and q the 255-bit primes of the section opening:

  • •

    Pallas, over 𝔽p: the order is #Ep(𝔽p)=q, a prime, so the group is cyclic, Ep(𝔽p)≅ℤ/qℤ (3.34), with cofactor h=1 (10.24). The trace is t=p+1−q, an 87-bit (negative) integer, far inside the Hasse bound 2p≈2128 of 10.22.

  • •

    Vesta, over 𝔽q: the order is #Eq(𝔽q)=p, a prime, so Eq(𝔽q)≅ℤ/pℤ, again with cofactor 1.

  • •

    Both curves have j=0 (10.35), and both primes satisfy p≡q≡1(mod3), so each curve admits the order-3 endomorphism ϕ(x,y)=(ωx,y) of 10.36 and supports the GLV speedup of 10.37.

  • •

    Both fields have two-adicity 32 in the sense of 9.10: 232 divides p−1 and q−1, so each field carries the multiplicative subgroups of order 232 asserted in 10.28, the evaluation domains of the fast polynomial arithmetic of 9.

  • •

    The cycle property #Ep(𝔽p)=q and #Eq(𝔽q)=p means the scalar field of each curve is the base field of the other (10.27): the base field of Pallas is 𝔽p and its scalar field is 𝔽q, matching the base field of Vesta, and symmetrically. This lets recursive proof systems chain proofs across the two curves without expensive non-native field arithmetic (10.28). The cycle is deployed: the pasta_curves crate defines the scalar field of Pallas to be 𝔽q and that of Vesta to be 𝔽p, as specified in §5.4.9.6 of the Zcash protocol specification.

The discrete logarithm problem in Ep(𝔽p) and Eq(𝔽q) is believed to require about 2126 group operations: Pollard’s rho, run on the classes of the automorphisms ±ϕi, expects about 2126.0 steps, against r≈2127.0 for either order r∈{p,q} (10.40, which follows), and no faster attack is known (10.31). This is slightly below the 128-bit security level targeted by Halo 2 and Zcash Orchard.

Remark 10.40 (The expected cost of Pollard’s rho on the Pasta curves).

We bound the expected step count of Pollard’s rho under the modelling assumption of 10.30, applied to a walk on a set of N elements (a forward reference: the probability results used here belong to the closing section). The first k positions are pairwise distinct with probability ∏i<k(1−i/N), the equality of 11.18. The tail-sum formula (11.33), the bound 1−x≤e−x, and k(k−1)≥(k−1)2 for k≥1 give, for the index T of the first repeat,

𝔼⁢[T]=∑k≥0∏i<k(1−iN)≤1+∑j≥0e−j2/(2⁢N)≤2+∫0∞e−x2/(2⁢N)⁢𝑑x=2+π⁢N/2,

the last sum bounded by the integral of its decreasing summand, which the substitution x=u2⁢N turns into 2⁢N times the Gaussian integral ∫0∞e−u2𝑑u=π/2. The bound is tight up to its additive constant: the sum defining 𝔼[T], less its first term, is Ramanujan’s Q-function of N, whose asymptotic expansion (Flajolet, Grabner, Kirschenhofer and Prodinger, On Ramanujan’s Q-function, J. Comput. Appl. Math. 58 (1995), Theorem 1) gives

𝔼⁢[T]=π⁢N/2+23+O⁢(N−1/2).

Three walks apply to a Pasta group G=⟨P⟩ of prime order r, each maintaining its position as [a]P+[b]Q with known a,b.

  • •

    The walk of 10.30 runs on the N=r points of G.

  • •

    A walk on the classes {R,−R} replaces each position by a representative of its class fixed by a rule, and runs on N=(r−1)/2+1 classes.

  • •

    A walk on the classes {±ϕi(R):i=0,1,2} of the automorphism ϕ of 10.36 does the same. The automorphism acts on G as [λ], and λ has order 3 modulo r (as λ2+λ+1≡0 and r>3), so the six scalars ±λi are distinct (−1, of order 2, is no power of λ); since a point R≠𝒪 has order r, its class has exactly six points, and the walk runs on N=(r−1)/6+1 classes.

In a class walk a repeat presents positions R=[a]P+[b]Q and R′=[a′]P+[b′]Q with R=[s]R′ for a known s∈{±λi}. Then [a−sa′]P=[(sb′−b)n]P, and n≡(a−sa′)(s⁢b′−b)−1(modr) whenever sb′≢b, as in the proof of 10.30. Both Pasta orders r satisfy log2r=254.0000 to four places, so the expansion, whose additive terms are negligible, gives

π⁢r/2≈2127.3,π⁢r/4≈2126.8,π⁢r/12≈2126.0

expected steps to the first repeat for the three walks, against r≈2127.0. A step is one group operation, plus, in a class walk, a few field operations to choose the representative; a class walk must also detect and leave the short cycles that the class map creates, which the modelling assumption ignores. Detecting the repeat, as the proof of 10.30 does with a second walk at double speed, multiplies the count by a constant. Up to these constants, negation and the automorphism remove one bit from the bare square root: the best known attack on either curve costs about 2126 group operations.

Each Pasta curve is thus a cyclic group of prime 255-bit order (10.22 and 3.34), with a fast forward map (10.21, accelerated by 10.37) whose inversion, the ECDLP, resists every known attack except the O(r) attacks of 10.30, at the cost computed in 10.40. Later volumes build on this pair.