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. That is not 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. The y is squared, and squaring throws away the sign, so (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, where the two points can be dragged around.
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. 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: 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₃). A degree-one factor 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. There is a shortcut. For any cubic written x³ + Ax² + Bx + C with roots r₁, r₂ and r₃, multiplying (x − r₁)(x − r₂)(x − r₃) back out puts −(r₁ + r₂ + r₃) in the x² slot. So the x² coefficient is minus the sum of the roots, always. That relation and its siblings for the other coefficients are Vieta's formulas.
In g the x² coefficient is −s². So 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. They are what the interactive curve on the how it works page computes as you drag, and they are line for line what the challenge's reference implementation computes 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₃. Move either slider and watch: the first two crossings go where you put them, 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 vertical case is fixed by adding one point to the system, the point at infinity, and defining the sum of a point and its mirror image to be that point. It behaves as zero: adding it to anything leaves that thing alone. This one is a definition rather than a consequence, and it is the price of a rule that works in every case. The reference implementation carries that 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 does not come from two points. It comes from the curve. 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. The point has to stay on the curve, so 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.
Press “Tangent” and “Vertical” on the figure above to see both: in one, the cubic meets the axis and turns back without passing through; in the other, there is no cubic at all.
Clock arithmetic
The pictures use ordinary numbers so that the shapes are visible. Bitcoin's curve does not use ordinary numbers. Its coordinates are whole numbers 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: 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), and 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 and you never leave it. That is what makes a private key a sensible idea in the first place: d copies of G is always a point, so the public key Q = dG is 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: four doublings to climb from P to 16P, 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. 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. On an ordinary computer that hardly matters. In the quantum circuit that Shor's attack would run, it is nearly the entire cost.
Division mod p has a name, modular inversion, and it is far more work than adding or multiplying. Profiling the circuit puts one inversion at about 47.6 percent of the expensive gates in a single point addition.
Reversibility then doubles that cost. A quantum circuit has to be able to run backward, so it cannot leave the slope sitting in a register at the end. The slope has to be erased, and 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 are about 95 percent of the circuit's budget. 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.
Keep reading