Closure
Adding two points on secp256k1 is a line and a reflection. What I keep coming back to is that the rule cannot fail. Whichever two points you start with, the answer is another point on the curve, every time. Rather than luck, it falls out of counting the roots of a cubic, and the same count hands over the formula the attack circuit spends most of its budget on, in algebra no harder than a quadratic.
The claim
A point is on a curve when its two coordinates satisfy the curve's equation. secp256k1's equation is y² = x³ + 7, so the point (x, y) is on it when squaring y gives the same number as cubing x and adding 7. There is nothing more to the test.
One consequence is worth having early. Because the y is squared, and squaring throws away the sign, (x, y) is on the curve if and only if (x, −y) is. The curve is its own mirror image across the x-axis. Reflecting a point can therefore never take you off the curve, which is what lets the addition rule end with a reflection.
Closure is the claim that the whole rule behaves that way. Take any two points on the curve, draw the line through them, find the third place that line crosses, reflect it across the x-axis, and the result is on the curve again, not merely close to it. The rule itself is drawn on the how it works page.
The question
Lines and curves are under no obligation to meet. A line can miss a circle entirely, graze it at one point, or cut through it at two. So “the line through P and Q crosses the curve exactly once more” is a claim that needs an argument rather than a picture, because a picture can only show the cases someone drew.
The argument is short. Write down what it takes for a point to be on the line and on the curve at the same time, then count how many such points there can be.
Step one
A point where the line meets the curve is a point whose coordinates satisfy both equations at once. So put the two equations together and solve them as a pair.
The line through P = (x₁, y₁) and Q = (x₂, y₂) has a slope, and once you have the slope you can write the line in the usual form.
s = (y₂ − y₁) / (x₂ − x₁) y = sx + c, c = y₁ − sx₁
s is the rise over the run between the two points; c is where the line cuts the y-axis.
Now substitute that y into y² = x³ + 7 and move everything to one side. Expanding (sx + c)² gives s²x² + 2scx + c², so what is left is:
x³ − s²x² − 2scx + (7 − c²) = 0
Call the left side g(x).
Every x where the line meets the curve is a solution of g(x) = 0, and every solution of g(x) = 0 is such an x. The two questions have become one question.
g is a cubic, which means its highest power of x is three. Two of its solutions are already in hand, because P and Q sit on the line and on the curve both. So x₁ and x₂ are roots of g.
A polynomial with a root at x₁ has (x − x₁) as a factor. This one has (x − x₁) and (x − x₂) as factors, so divide both out. Dividing something of degree three by something of degree two leaves degree one, a single factor (x − x₃), which has exactly one root.
That root is the third crossing, and that is the whole proof. A cubic has room for exactly one more root once two are accounted for, so the third point cannot fail to be there.
Step two
You could carry out that polynomial division and read x₃ off what is left, but there is a shortcut. Take any cubic x³ + Ax² + Bx + C with roots r₁, r₂ and r₃. Because it factors as (x − r₁)(x − r₂)(x − r₃), multiplying that back out puts −(r₁ + r₂ + r₃) in the x² slot. So the x² coefficient is minus the sum of the roots, always. This relation, and the matching ones for the other coefficients, are Vieta's formulas.
Because in g the x² coefficient is −s², the three roots have to add up to s²:
x₁ + x₂ + x₃ = s² x₃ = s² − x₁ − x₂
Two of the roots are the x-coordinates you picked, so the third is whatever is left over.
That is the third crossing's x-coordinate. Its y comes from the line, y = sx₃ + c, and the last step of the addition rule is to reflect, which flips that sign. Doing both at once:
y₃ = s(x₁ − x₃) − y₁
The minus sign at the front of y₁ is the reflection.
Those two lines are the addition formula. The interactive curve on the how it works page computes them, and so, line for line, does the challenge's reference implementation on 256-bit numbers.
Interactiveone cubic, three roots
P = (-1.00, 2.45)
Q = (2.00, -3.87)
the cubic: g(x) = x³ − 4.44x² + 1.44x + 6.88
slope s
-2.11
x₁ + x₂ + x₃
4.44
s²
4.44equal ✓
The curve crosses zero at x₁ and x₂ because P and Q lie on both the line and the curve. A cubic cannot stop there, so it comes back to zero once more, at x₃. The first two crossings are the points chosen, and the third has no choice.
What I like about this is how little it asks for. No calculus, no geometry past a straight line. You count the degree of a polynomial, notice that two of its roots are already spoken for, and the third one has nowhere else to be.
The exceptions
Both slip out of the setup above, and each needs its own handling.
The fix for the vertical case is to add one point to the system, the point at infinity, and to define the sum of a point and its mirror image to be that added point. The added point behaves as zero, in that adding it to anything leaves that thing alone. Unlike everything above, this is a definition rather than a consequence, the price of a rule that works in every case. The reference implementation carries the extra point as the pair (0, 0), a value no real curve point takes, and checks for it before anything else runs.
The tangent case needs a slope that comes from the curve rather than from two points. Nudge x by a little and x³ + 7 changes by about 3x² times the nudge. Nudge y and y² changes by about 2y times that nudge. Because the point has to stay on the curve, those two changes are equal, and the rise over the run is:
s = 3x₁² / (2y₁)
A general curve y² = x³ + ax + b gives (3x₁² + a) / (2y₁). secp256k1 has a = 0, so the a drops out.
Clock arithmetic
The pictures use ordinary numbers so that the shapes are visible. Bitcoin's curve instead has whole-number coordinates with every operation taken mod p, meaning you keep only the remainder after dividing by p. For secp256k1 that modulus is 2²⁵⁶ − 2³² − 977, a prime a little under 2²⁵⁶. Plotted, those points are a scatter with no shape to read.
So look back at what the proof used. Adding, subtracting, multiplying, dividing. No distances, no smoothness, no picture, no notion of one point being near another. That is the entire list.
Mod p, the first three carry over directly, because you do the operation on whole numbers and keep the remainder. Division needs one adjustment, because there is no dividing mod p. Multiplying by a modular inverse stands in for it: for a nonzero value v, the inverse is the number z with v · z ≡ 1 (mod p). Since p is prime, every nonzero value has exactly one.
With that one substitution the whole derivation survives. Same line, same cubic, same two known roots, same leftover factor of degree one, same Vieta sum. Every point the formula produces satisfies y² ≡ x³ + 7 (mod p), so closure holds in the scatter exactly as it held in the picture.
Why it transfers
What it is for
Because the answer is always on the curve, you can keep going. Add the shared starting point G to itself, add G again, and again, and every stop along the way is another curve point. You are walking inside a finite set that you never leave. That is what makes a private key a sensible idea in the first place, since d copies of G is always a point and the public key Q = dG is therefore always defined. The threat primer covers what that pair of keys is doing.
Staying inside also makes the walk cheap, because nobody performs d additions one at a time. Write d in binary and use doubling instead. 25 is 11001, which reads as 16 + 8 + 1, so 25P is 16P + 8P + P, which takes four doublings to climb from P to 16P and then two additions to put the pieces together, six steps rather than 24. A 256-bit key takes 256 doublings and at most 256 additions, which is why going forward is quick.
Keep adding G to itself and the walk eventually comes back to the point at infinity, after exactly n steps, where n is a 256-bit prime published with the curve. So the points reachable from G form a closed loop of n of them. Although going around the loop is fast, working out how far around somebody else went, given only where they landed, is the problem the whole scheme rests on.
Back to the project
Exactly one division appears in the whole derivation: the slope. Everything else is adding, subtracting and multiplying. Although that hardly matters on an ordinary computer, in the quantum circuit that Shor's attack would run it is nearly the entire cost.
Division mod p, called modular inversion, is far more work than adding or multiplying. Profiling put one inversion at about 47.6 percent of the expensive gates in a single point addition, measured on the construction the challenge shipped through August.
Reversibility then doubles that cost. Because a quantum circuit has to be able to run backward, it cannot leave the slope sitting in a register at the end. The slope has to be erased, but by the time the circuit gets there the inputs have been overwritten by the outputs, so the slope can only be rebuilt out of the outputs. Rebuilding it is a second division, costing the same share again.
The two together were about 95 percent of that circuit's budget. The construction that replaced it on August 23 is built around the same pair, a divide traversal and a multiply traversal running the same machinery. The squaring step sits beside them at about 6 percent. A competition to shrink the machine that could break these signatures is, underneath, a competition to divide. What the rest of that circuit is made of is on the how it works page.
The addition and doubling formulas, the curve constants a = 0 and b = 7, the modulus, and the (0, 0) convention for the point at infinity are from the challenge's reference implementation. The 47.6 and 95 percent figures are from the profiling notes in my fork, measured on the construction that shipped through August, while the 6 percent is from the note on the one that replaced it.
Keep reading