Fingers crossed:

Phew...

If we substitute \(c_1\) and \(c_2\) in the formula, we get

\[ F_i = \frac{(1+\sqrt5)^i-(1-\sqrt5)^i}{2^i\sqrt5} \]

We obtained the same solutions we found for \(b\), and we get the same asymptotic growth as well.

Indeed, the numerator grows as \((1+\sqrt5)^i\):

\[ \lim_{i\to\infty} \frac{(1+\sqrt5)^i-(1-\sqrt5)^i}{(1+\sqrt5)^i} = \lim_{i\to\infty} \left(1 - \left(\frac{1 - \sqrt5}{1 + \sqrt5}\right)^i\right) = 1 \]

So, \(F_i \sim \frac{\phi^i}{\sqrt5} = \Theta(\phi^i)\), where \(\phi = \frac{1+\sqrt5}{2}\).

By the way, \(P(x) = \sum_{i=0}^\infty F_i x^i\) is called a generating function.

secp256k1

Ethereum's ECDSA uses the elliptic curve secp256k1, defined as

\[y^2 = x^3 + 7\ (\mathrm{mod}\ p)\]

where \(p\) is a very big prime number.

Here's what the continuous version (i.e. without mod) of the curve looks like:

The continuous elliptic curve is the set of all points \((x, y)\) in the plane such that \(y^2 = x^3 + 7\). Because \(y\) is squared, the curve is symmetric about the X-axis, i.e. \((x, y)\) is on the curve if and only if \((x, -y)\) is.

When we switch to mod \(p\), things get complicated:

To draw that picture I used \(p = 97\), a small prime. The blue line is the continuous curve, while the dots are the solutions in \(\mathbb{Z}_p\times\mathbb{Z}_p\). Note that those solutions must always be finitely many, since they lie on a \(p\times p\) grid.

This figure only shows the upper right part (1st quadrant) of the previous one, so we can't see the symmetry of the continuous curve. Yet, the points in \(\mathbb{Z}_p\times\mathbb{Z}_p\) show a new symmetry: they're reflected across the horizontal line \(y = p/2\). That makes sense:

• \((x, y)\) lies on the continuous curve if and only if \((x, -y)\) also lies on it.
• If \(y\in\mathbb{Z}_p\), then \(-y = p-y\).
• This means that \((x, y)\) lies on the mod curve if and only if \((x, p-y)\) also lies on it.
• \(y = p-y\) gives us \(y = p/2\). In the figure the axis of symmetry is \(y = 97/2 = 48.5\).

Let's plot the negative solutions as well:

As we can see, the part above is identical to the part below, since adding \(p\) or \(-p\) to a coordinate doesn't change anything mod \(p\).

Group

A group \(G\) is a set of elements equipped with a binary operation, \(+\), such that:

• For any elements \(a, b\in G\), we must have \(a+b \in G\).
• There's a neutral element, or identity, \(0\), so that \(a+0 = 0+a = a\) for every \(a\in G\).
• For every \(a\in G\), there exists an additive inverse, or opposite, of \(a\), denoted as \(-a\), such that \(a+(-a) = (-a)+a = 0\).
  • Note: \(a+(-b)\) can also be written as \(a-b\).
• We also want associativity, i.e., for all \(a,b,c\in G\), we must have \(a + (b+c) = (a+b) + c\). So, we can drop the parentheses and write \(a+b+c\).

If for all \(a, b\in G\) we have \(a+b = b+a\), then \(G\) is abelian or commutative.

Notice that we can't have two distinct identities \(0_1 \neq 0_2\), since

\[0_1 = 0_1+0_2 = 0_2\]

Let's break it down:

• \(0_1+0_2\) can be simplified in two ways:
  • Since \(0_1\) is an identity, then it disappears, so \(0_1+0_2 = 0_2\)
  • Since \(0_2\) is an identity, then it disappears, so \(0_1+0_2 = 0_1\)

Therefore, the two identities must be equal.

The same goes for the additive inverse. If \(x\) and \(y\) are opposites of \(a\) then:

\[ \begin{align*} a+x &= 0 \\ a+y &= 0 \end{align*} \]

That means that:

\[ \begin{align*} a+x &= a+y &\implies \\ x+(a+x) &= x+(a+y) &\implies \\ (x+a)+x &= (x+a)+y &\implies \\ 0+x &= 0+y &\implies \\ x &= y \end{align*} \]

So there's only one inverse per element.

Given a subset \(S\) of elements from \(G\), we can define the subgroup \(G_S\) of \(G\) generated by \(S\) as the smallest group that includes all the elements of \(S\). We say that \(S\) is a generator of \(G_S\).

In this article we'll only describe in detail the case where \(S\) has just one element. For simplicity, we'll use the same symbol for the subgroup and its generator, so a generator \(G\) generates the (sub)group \(G\) defined as follows:

\[G = \{0, G, G+G, G+G+G, G+G+G+G, \ldots\}\]

That's very cumbersome to read and write, so let's define

\[nG = G_1 + G_2 + \cdots + G_n,\ \mathrm{where}\ G_1 = G_2 = \cdots = G_n = G\]

Now we can rewrite the definition as

\[G = \{0, G, 2G, 3G, 4G, \ldots\}\]

or even

\[G = \{0G, 1G, 2G, 3G, 4G, \ldots\}\]

where we define \(0G = 0\).

A group for the elliptic curve

ECDSA defines a group over the points on the curve mod \(p\). To do that, we first need to define an addition between points.

Here's how it's done on the continuous version of the elliptic curve:

If \(P\) and \(Q\) are two points on the curve, then \(P+Q\) is the reflection across the X-axis of the intersection between the curve and the line passing through \(P\) and \(Q\).

The line through \(P\) and \(Q\) always intersects the curve at a third point, except when the line is perfectly vertical. In that case, the line is said to intersect the curve at \(0\), called the point at infinity. The point \(0\) acts as the identity, but is not really part of the curve, so it needs to be handled as a special case.

Now, observe that the line through \(R = (x, y)\) and \(-R = (x, -y)\) is vertical, so \(R+(-R)=0\), as suggested by the "\(-\)" sign.

When \(P = Q\), the line through \(P\) and \(Q\) is taken to be the tangent to the curve at \(P\) (or, equivalently, \(Q\)). It makes sense:

• Just imagine fixing \(P\) and sliding \(Q\) along the curve from one side of \(P\) to the other.
• If we want the animation of the line during the sliding to be continuous, the line must be the tangent when \(P = Q\).

After all, the animation is continuous when the slope of the line is continuous, and the slope is continuous at a point when it's equal to its limit, i.e. the derivative, at that point.

Here's a figure with a fixed point \(P\) and secants through \(P\) and several \(Q_i\) points that converge to \(P\). I chose a color map such that the closer a \(Q_i\) is to \(P\), the bluer the secant through it becomes.

By the way, we still count the tangent line as intersecting the elliptic curve in three points, with two coinciding at the point of tangency.

But how is it possible that even an "almost vertical" line through two points on the curve always intersects the curve at a third point? Such a line intersects the curve either at a point towards \((+\infty, +\infty)\) or \((+\infty, -\infty)\).

For \(x\to+\infty\):

• line:
• curve:
  • \(y^2 = x^3 + 7 \sim x^3 \implies\)
    • \(y \sim x^{3/2}\) (upper branch)
    • \(y \sim -x^{3/2}\) (lower branch)

What we're saying is that when \(x\) becomes very big, additive terms such as \(q\) and \(7\) are dwarfed and can be ignored, so the line grows like \(mx\), while the curve grows like \(x^{3/2}\). The curve grows asymptotically faster, so, when \(m > 0\), the upper branch of the curve will hit the line from below and cross it sooner or later. Similarly, when \(m < 0\), the lower branch of the curve will hit the line from above and cross it.

Here's a visual example for \(m>0\):

Finding the intersection point

The algebra is easy enough. We just compute the intersection between the curve and the line. Let's start from the two points \(P = (x_P, y_P)\) and \(Q = (x_Q, y_Q)\).

If the line is vertical, the third intersection point is \(0\). Otherwise, its equation has the form \(y = mx + q\), where

\[ \begin{align*} m &= \frac{y_Q-y_P}{x_Q-x_P} \\ q &= y_P - m x_P \end{align*} \]

We need to solve for \(x\) and \(y\) the system

\[ \left\{ \begin{align*} y &= mx + q \\ y^2 &= x^3 + 7 \end{align*} \right. \]

We substitute the first equation into the second and get

\[ \begin{gather*} (mx + q)^2 = x^3 + 7 &\iff\\ m^2x^2 + q^2 + 2mqx = x^3 + 7 &\iff\\ x^3 - m^2x^2 - 2mqx + 7 - q^2 = 0 \end{gather*} \]

Before giving in to despair, we remember that we already know two solutions, \(x_P\) and \(x_Q\), and we're looking for the third point \(-R = (x_{-R}, y_{-R})\). This means that the LHS of the equation in \(x\) must be factorizable as

\[(x - x_P)(x - x_Q)(x - x_{-R}) = 0\]

Let's expand it to get

\[x^3 + x^2(-x_P-x_Q-x_{-R}) + \ldots = 0\]

The second term is all we need: for the two LHS to be equal, we must have

\[ \begin{align*} -m^2 &= -x_P-x_Q-x_{-R} \iff\\ x_{-R} &= m^2 - x_P - x_Q \end{align*} \]

The \(y\) coordinate is simply \(y_{-R} = m x_{-R} + q\).

Therefore, the sum of the two points can be computed as

\[ \left\{ \begin{align*} m &= (y_Q-y_P)/(x_Q-x_P) \\ x_R &= m^2 - x_P - x_Q \\ y_R &= m (x_P - x_R) - y_P \end{align*} \right. \]

As we can see, finding the sum of two points requires subtractions, multiplications, and one division to compute \(m\). To sum two points on the curve mod \(p\), we just need to do the calculations mod \(p\). We know how to "divide" mod \(p\), so we're good.

Let's briefly go through the case with \(P=Q=(x,y)\). Recall that we need to consider the tangent to the curve at \((x,y)\). Note that for \(y=0\) the tangent is perfectly vertical, so the result is \(0\) (look at the figure). For \(y\neq 0\), we need to compute the derivative.

We start from the equation

\[y^2 = x^3 + 7\]

and derive both sides with respect to \(x\):

\[2y \frac{dy}{dx} = 3x^2\]

We solve for the derivative:

\[\frac{dy}{dx} = \frac{3x^2}{2y}\]

That's our \(m\).

A complete implementation will also handle the (trivial) edge cases with \(P=0\) or \(Q=0\), of course.

Why reflect the intersection point

Having to reflect the intersection point might seem a little arbitrary at first, but if we think about it, not reflecting it is problematic. Indeed, since the three points lie on the same line, without reflection all the following equations would hold:

• \(P + Q = R\)
• \(P + R = Q\)
• \(Q + R = P\)

By summing the first two equations, we'd get \(2P+Q+R=R+Q\), i.e. \(P=0\). Analogously, by summing the last two equations, we'd get \(R=0\). Since \(P=Q=R=0\), that rule would only work for \(0\).

The correct rule will look less asymmetric if we think of it as \(P+Q+R=0\), which gives

• \(P+Q=-R\)
• \(P+R=-Q\)
• \(Q+R=-P\)

But what about this point at infinity? Where does it come from? All I know is that it has to do with the so-called projective space.

I got somewhat acquainted with that space when I was doing 3D graphics. In 3D, we may add a 4th coordinate, so that \((x, y, z)\) is represented by \((wx, wy, wz, w)\) and some computations become more regular (i.e. with fewer exceptions). At the end, we divide by \(w\) to go back to the usual coordinates.

There's also the 2D case when we project a 3D scene onto a 2D screen: \(\pi(x, y, z) = (x/z, y/z)\), where I used \(\pi\) for projection. This has to do with how we perceive the world, so that the farther an object is from us, the smaller it looks (assuming, from our POV, that \(z\) is the distance of the object from us).

Projective space

Let's say we have some 3D space. We make it projective by imposing that, in general, \((x, y, z) \sim (\lambda x, \lambda y, \lambda z)\) for all \(\lambda\neq 0\), and \((x, y, z)\neq(0, 0, 0)\), where \(\sim\) means equivalent. In words, all non-zero scalings of a non-zero point are equivalent. Those are all the points, origin excluded, on the same line through the origin.

The classes partition the punctured (i.e. without the origin) 3D space. The origin, if included, would be in its own singleton class \(\{0\}\) anyway. If we instead allowed \(\lambda = 0\), then two points \(x\) and \(y\) on different lines through the origin would violate the equivalence relation: \(x\sim 0\) and \(y\sim 0\), but \(x\nsim y\).

Indeed, an equivalence relation must follow three rules:

• reflexivity: \(x\sim x\)
• symmetry: \(x\sim y\iff y\sim x\)
• transitivity: \(x\sim y \wedge y\sim z\implies x\sim z\)

where "\(\wedge\)" means "and".

To remember the rules, we can just think of equality, which is also an equivalence relation:

• \(a=a\)
• \(a=b\iff b=a\)
• \(a=b\wedge b=c\implies a=c\)

So, if \(x\sim 0\) and \(0\sim y\), then we must have \(x\sim y\). If \(0\) is equivalent to elements that belong to different classes, then it breaks transitivity.

Since the origin doesn't belong to the projective space, any generic point \((x, y, z)\) in it is to be considered non-zero.

Back to our elliptic equation. On the 2D plane, the equation is \(y^2 = x^3 + 7\), but that won't work in the projective space. Since \((x, y, z)\sim (\lambda x, \lambda y, \lambda z)\), with \(\lambda\neq 0\), we'd like for \((\lambda x, \lambda y, \lambda z)\) to be on the curve whenever \((x, y, z)\) is.

Let's write the equation in the projective space as

\[Y^2 = X^3 + 7\]

and do the substitution \((X, Y, Z) = (\lambda x, \lambda y, \lambda z)\):

\[\lambda^2 y^2 = \lambda^3 x^3 + 7\]

We want that to hold whenever \((x, y, z)\) is a solution, i.e. whenever \(y^2 = x^3 + 7\). For that to happen, the equation must factorize as

\[f(\lambda)(y^2 - x^3 - 7) = 0\]

so that when the second factor is \(0\), the equation holds regardless of the factor with \(\lambda\).

We still have a \(Z\) to add, so why not use it to balance the degree of the terms? That is:

\[Y^2 Z = X^3 + 7 Z^3\]

Now the substitution gives

\[ \begin{gather*} \lambda^3 y^2 z = \lambda^3 x^3 + 7 \lambda^3 z^3 &\iff \\ \lambda^3 (y^2 z - x^3 - 7 z^3) = 0 \end{gather*} \]

We did it, but what about that annoying extra \(z\)? If we want to recover the original equation, we need to set \(z=1\), i.e. we need to restrict ourselves to \((x, y, 1)\).

That's perfectly fine, though: the original curve lies on the \(z=1\) plane, while on each \(z=\lambda\) plane, with \(\lambda\neq 0\), lies a \(\lambda\)-scaled version of the original curve:

With this setup, we can say that either all the elements of an equivalence class (a punctured line through the origin) are on the curve or none of them are.

There's actually an easier way to get the equation in \(x\), \(y\), and \(z\) coordinates. The original 2D curve is embedded in the 3D space by adding a \(z = 1\) coordinate, i.e.

\[(x, y)\mapsto (x, y, 1) \sim (\lambda x, \lambda y, \lambda) = (X, Y, Z)\]

Starting from a generic point \((X, Y, Z)\) with \(Z\neq 0\), we can go back to the 2D case by just dividing by \(Z\) and dropping the third coordinate, i.e.

\[(x, y) = (X/Z, Y/Z)\]

Now, let's substitute \(x = X/Z\) and \(y = Y/Z\) into the starting equation and get rid of the denominators:

\[ \begin{align*} y^2 &= x^3 + 7 \\ (Y/Z)^2 &= (X/Z)^3 + 7 \\ \frac{Y^2}{Z^2} &= \frac{X^3}{Z^3} + 7 \\ Y^2 Z &= X^3 + 7Z^3 \end{align*} \]

One can also apply other projections. For instance, \(x = X/Z^2\) and \(y = Y/Z^3\) lead to

\[ \begin{align*} y^2 &= x^3 + 7 \\ (Y/Z^3)^2 &= (X/Z^2)^3 + 7 \\ \frac{Y^2}{Z^6} &= \frac{X^3}{Z^6} + 7 \\ Y^2 &= X^3 + 7Z^6 \end{align*} \]

This is actually nicer and used to greatly speed up computations. It's called Jacobian projection.

We still haven't solved the mystery of the point at infinity. That was the main reason why we decided to explore projective spaces.

Point at infinity

We know that a vertical line intersects the planar elliptic curve either at no points at all or at the points \(P\), \(-P\), and \(0\) for some point \(P\), where \(0\) is the so-called point at infinity. Let's try to make sense of it.

On the plane, a vertical line has equation \(x = k\), but in our projective space that's the equation of a plane. Like with the elliptic curve, we want to upgrade the equation so that if \((x, y, z)\) is on the line, then so is \((\lambda x, \lambda y, \lambda z)\). We use the same substitution as before:

\[ \begin{align*} x &= k \\ \frac{X}{Z} &= k \\ X &= kZ \end{align*} \]

So the equation of the vertical plane becomes \(X = kZ\), which represents a family of \(Z\)-scaled vertical lines. The equation \(X = kZ\) makes sense since, as \(Z\) gets closer to \(0\), the line must also get closer to the origin because everything, curve included, gets scaled down.

Let's find the intersections between the curve and the line by solving

\[ \begin{cases} Y^2 Z = X^3 + 7Z^3\\ X = kZ \end{cases} \]

We substitute the second equation into the first:

\[Y^2 Z = k^3 Z^3 + 7Z^3\]

That can be rewritten as

\[Z (Z^2 (k^3 + 7) - Y^2) = 0\]

For \(Z\neq 0\), we can divide by \(Z\), so we're left with

\[Z^2 (k^3 + 7) - Y^2 = 0\]

which gives two solutions for each \(Z\neq 0\) because of that \(Y^2\). Those two solutions correspond to two points \(P\) and \(-P\).

For \(Z = 0\), we get \(X = 0\) from the second equation, i.e. the solutions are \((0, \lambda, 0)\) for \(\lambda\neq 0\), which is the Y-axis without the origin. We can take \((0, 1, 0)\) as the representative of that class, which is exactly the point at infinity. As we can see, it doesn't live in any plane with the curve, so it doesn't exist in our original 2D space, but we already knew that.

This reminded me that we never designated representatives for the equivalence classes. Let's see:

• Each class \(C\) is a punctured line through the origin.
• If \(C\) intersects the plane \(Z = 1\) at some point \(P = (X, Y, 1)\):
• Else:
  • \(C\) must lie on the plane \(Z = 0.\)
  • If \(C\) intersects the line \(\{Y=1; Z=0\}\) at some point \(P = (X, 1, 0)\):
  • Else:
    • \(C\) lies on the X-axis, i.e. \(\{Y = Z = 0\}\).
    • \(C\) has the form \((X, 0, 0)\).
    • \(\mathrm{repr}(C) = (1, 0, 0)\)

So, we have three groups of representatives:

• \((X, Y, 1)\): on the curve if and only if \(Y^2 = X^3 + 7\).
• \((X, 1, 0)\): on the curve if and only if \(X = 0\), which gives the point at infinity \((0, 1, 0)\).
• \((1, 0, 0)\): not on the curve.

Addition in projective space

Computing \(m\), the slope of the line through the points \((x_1, y_1)\) and \((x_2, y_2)\), requires a division, which, mod \(p\), is a relatively expensive operation (compared to simple additions and multiplications).

Let's recall how to compute the point \((x_3, y_3) = (x_1, y_1) + (x_2, y_2)\), assuming \(x_1\neq x_2\):

\[ \begin{align*} m &= (y_2-y_1)/(x_2-x_1) \\ x_3 &= m^2 - x_1 - x_2 \\ y_3 &= m (x_1 - x_3) - y_1 \end{align*} \]

To go from the plane to the 3D projective space, we proceed as we did before with the elliptic curve and the line equations, i.e. we make the substitution \((x,y) = (X/Z, Y/Z)\).

Let's start with \(m\):

\[ \begin{align*} m &= \frac{y_2-y_1}{x_2-x_1} \\ &= \frac{Y_2/Z_2 - Y_1/Z_1}{X_2/Z_2 - X_1/Z_1} \\ &= \frac{Y_2/Z_2 - Y_1/Z_1}{X_2/Z_2 - X_1/Z_1} \cdot \frac{Z_1 Z_2}{Z_1 Z_2} \\ &= \frac{Y_2 Z_1 - Y_1 Z_2}{X_2 Z_1 - X_1 Z_2} \end{align*} \]

We define

\[ \begin{align*} A &= Y_1 Z_2 \\ B &= Y_2 Z_1 - A \\ C &= X_1 Z_2 \\ D &= X_2 Z_1 - C \end{align*} \]

Therefore:

\[ m = \frac{Y_2 Z_1 - Y_1 Z_2}{X_2 Z_1 - X_1 Z_2} = \frac{B}{D} \]

Now we deal with \(x_3\):

\[ \begin{align*} x_3 &= m^2 - x_1 - x_2 \\ \frac{X_3}{Z_3} &= \frac{B^2}{D^2} - \frac{X_1}{Z_1} - \frac{X _2}{Z_2} \\ X_3 &= Z_3 \frac{B^2 Z_1 Z_2 - D^2 (X_1 Z_2 + X_2 Z_1)}{D^2 Z_1 Z_2} \\ &= Z_3 \frac{B^2 Z_1 Z_2 - D^2 (D + 2C)}{D^2 Z_1 Z_2} \end{align*} \]

It's \(y_3\)'s turn:

\[ \begin{align*} y_3 &= m (x_1 - x_3) - y_1 \\ \frac{Y_3}{Z_3} &= \frac{B}{D} \left(\frac{X_1}{Z_1} - \frac{X_3}{Z_3}\right) - \frac{Y_1}{Z_1} \\ Y_3 &= Z_3 \frac{B(X_1 Z_3 - X_3 Z_1) - Y_1 D Z_3}{D Z_1 Z_3} \\ &= \frac{B(X_1 Z_3 - X_3 Z_1) - Y_1 D Z_3}{D Z_1} \\ &= \frac{B\left(X_1 Z_3 - \left( Z_3 \frac{B^2 Z_1 Z_2 - D^2 (D + 2C)}{D^2 Z_1 Z_2} \right) Z_1\right) - Y_1 D Z_3}{D Z_1} \\ &= Z_3\frac{B\left(X_1 - \frac{B^2 Z_1 Z_2 - D^2 (D + 2C)}{D^2 Z_2}\right) - Y_1 D}{D Z_1} \\ &= Z_3\frac{B\left(X_1 - \frac{B^2 Z_1 Z_2 - D^2 (D + 2C)}{D^2 Z_2}\right) - Y_1 D}{D Z_1}\cdot \frac{D^2 Z_2}{D^2 Z_2} \\ &= Z_3\frac{B(X_1 Z_2 D^2 - B^2 Z_1 Z_2 + D^2 (D + 2C)) - Y_1 D^3 Z_2}{D^3 Z_1 Z_2} \\ &= Z_3\frac{B(D^2 (D + 3C) - B^2 Z_1 Z_2) - Y_1 D^3 Z_2}{D^3 Z_1 Z_2} \\ \end{align*} \]

We substituted \(X_3\) into \(Y_3\), so we could factor out \(Z_3\), since \(X_3 = Z_3 (\ldots)\).

We end up with

\[ \begin{align*} X_3 &= Z_3\frac{B^2 Z_1 Z_2 - D^2 (D + 2C)}{D^2 Z_1 Z_2} \\ Y_3 &= Z_3\frac{B(D^2 (D + 3C) - B^2 Z_1 Z_2) - Y_1 D^3 Z_2}{D^3 Z_1 Z_2} \end{align*} \]

and by choosing \(Z_3 = D^3 Z_1 Z_2\), we get rid of the denominators:

\[ \begin{align*} X_3 &= D(B^2 Z_1 Z_2 - D^2 (D + 2C)) \\ Y_3 &= B(D^2 (D + 3C) - B^2 Z_1 Z_2) - Y_1 D^3 Z_2 \\ Z_3 &= D^3 Z_1 Z_2 \end{align*} \]

We can clean that up further by defining

\[ \begin{align*} E &= B^2 Z_1 Z_2 - D^2 (D + 2C) \\ F &= D^3 Z_2 \end{align*} \]

which results in

\[ \begin{align*} X_3 &= DE \\ Y_3 &= B(D^2 C - E) - Y_1 F \\ Z_3 &= Z_1 F \end{align*} \]

Note that further micro-optimizations are possible. For instance, we shouldn't compute \(D^2\) and \(D^3\) separately.

I hope my calculations are correct, since this is my first time doing them. Either way, I'm satisfied with the result from a pedagogical point of view. I hope you are as well. As we can see, the common denominator was put in \(Z_3\) to avoid intermediate divisions. Now we can add many points together without any division and only do one single division when we want to go back to our 2D plane:

\[ \begin{align*} Z_{\text{inv}} &= Z^{-1} \\ (x, y) &= (XZ_{\text{inv}}, YZ_{\text{inv}}) \end{align*} \]

That's one slow (at least in \(\mathbb{Z}_p\)) division and 2 fast multiplications.

Note that the \(P=Q\) case is handled similarly. Moreover, the same approach will also work for the Jacobian projection, i.e. for \((x, y) = (X/Z^2, Y/Z^3)\).

This is almost a philosophical observation. When we substitute \(x\) with \(X/Z\), we're not promoting \(x\) to a fraction, but we're reexpressing it as a fraction, since they're assumed to be equal.

For example, if \(x\) is a simple integer in \(\mathbb{Z}\) (without mod) and we replace it with \(X/Z\) where \(X\) and \(Z\) are also in \(\mathbb{Z}\), then we're ranking up from integers to rational numbers, which is a promotion. Indeed, unless \(X\) is divisible by \(Z\) or we're willing to lose some information, we won't be able to go back to \(x\) when the time comes.

In the ECDSA case, though, \(x\) is in \(\mathbb{Z}_p\), with \(p\) prime, so \(X/Z\) is also in \(\mathbb{Z}_p\): we're not promoting \(x\) to something more, but just reexpressing it.

Let's say we have a huge matrix that can be factorized into two small matrices because it's low-rank (i.e. many of its rows or columns are linear combinations of a selected few). Instead of carrying around the huge matrix during the computations, we may want to keep it in factorized form, \((L, R)\), and then update the factorized form itself:

\[(L', R') = (f(L, R), g(L, R))\]

One way to find \(f\) and \(g\) is to do the substitution \(M = LR\) into whatever expression we want to evaluate involving \(M\), and put the result back into factorized form. Note that if we end up with \(L=I\) or \(R=I\) (where \(I\) is the identity matrix), then the factorization is useless for our purposes.

Back to the group

ECDSA uses the addition operation we defined above to generate a group from a predetermined generator \(G\). All the considered points are on the curve mod \(p\), meaning that their coordinates are in \(\mathbb{Z}_p\). Here's the group:

\[G = \{0, G, 2G, 3G, \ldots, (N-1)G\}\]

Notice that \(G\) has only a finite number of elements, which is to be expected since the points lie on a \(p\times p\) grid, which contains \(p^2\) distinct points at most.

We start from \(0\) and keep adding \(G\) until we loop, i.e. we get a point that we've already seen. Let's assume this is our current list:

\[0, G, 2G, 3G, \ldots, kG, \ldots, hG\]

We assume we've just looped, so the first \(h\) elements are all distinct, and \(hG = kG\), with \(k < h\).

We must have \(0 = hG-kG = (h-k)G\). The only elements in the list that can be 0 are the first one and the last one. Since \(h-k>0\), \((h-k)G\) must be the last element, so \(h-k=h\), which gives \(k=0\). This means that when we loop we restart from \(0\).

So we end up with the following group:

\[G = \{0, G, 2G, 3G, \ldots, (N-1)G\}\]

\(G\) has order \(N\), i.e. it has \(N\) elements. This looping should remind you of \(\mathbb{Z}_N\):

\[\mathbb{Z}_N = \{0, 1, 2, 3, \ldots, N-1\}\]

Indeed, \(\mathbb{Z}_N\) is also a (commutative) group:

• group operation: \(+\)
• identity: \(0\)
• inverse of \(x\): \(-x\)
  • so that \(x + (-x) = (-x) + x = 0\)

Moreover, it's generated by \(1\):

\[\mathbb{Z}_N = \{0, 1, 1+1, 1+1+1, \ldots, (N-1)1\}\]

If we couldn't inspect the single elements, and we just used the group laws, we'd actually be unable to tell \(G\) and \(\mathbb{Z}_N\) apart.

For instance, let's say we're given, as programmers, an opaque type Element together with an identity zero and an operation add. Would we be able to tell whether we're working with \(G\) or \(\mathbb{Z}_N\) without looking inside Element or at the implementation? No, we wouldn't. By defining a common API, we abstracted away the differences.

So, we've got ourselves an isomorphism between groups:

\[aG + bG = (a+b)G\]

More formally, let's define \(f: a\mapsto aG\), which is a bijection, i.e. a 1-1 mapping between all the elements of \(\mathbb{Z}_N\) and all the elements of \(G\). This means that we can invert \(f\) and use \(f^{-1}\) to go the other direction (however computationally expensive it is to do).

Then the equation above can be rewritten as

\[f(a) +_G f(b) = f(a+_{\mathbb{Z}_N}b)\]

That means that we can either

• transform the addends into \(G\)'s elements and then add them up using \(G\)'s addition operation, or
• sum the addends using \(\mathbb{Z}_N\)'s addition operation and then transform the result into the corresponding element in \(G\).

The final result will be the same.

Another way of saying this is that we can move back and forth between \(G\) and \(\mathbb{Z}_N\) without losing information.

For example, for \(N = 7\):

• \(3G + 5G = 8G = 7G + G = 0 + G = G\)
• \((3 + 5)G = (8)G = (1)G = G\)
  • because \(8\ \mathrm{mod}\ 7 = 1\)

In the first case the looping comes from \(G\), while in the second case it comes from \(\mathbb{Z}_7\). In the second case we only worked inside the parentheses, i.e. with the numbers in \(\mathbb{Z}_7\): we didn't touch \(G\) at all.

The idea is to work with numbers in \(\mathbb{Z}_N\), which are easier to work with, and then transform them into points by multiplying them by \(G\). While it's very easy to go from \(k\) to \(kG\), it's computationally infeasible to go back from \(kG\) to \(k\).

It shouldn't surprise that ECDSA represents private keys as numbers in \(\mathbb{Z}_N\), and then multiplies them by \(G\) to get the associated public keys. This makes recovering the private key from a public key computationally infeasible.

Signing a message

I'll cheat a little and read my notes for the signing part of the algorithm:

Let's see:

• \(G\) is both:
  • the group of points on the elliptic curve (with coordinates in \(\mathbb{Z}_p\), with \(p\) prime)
  • the generator of that group
• \(n\), a prime number, is the order of \(G\)
• \(z\) is the message hash
• \(d\) is the private key of the account
• \(k^{-1}\) is the multiplicative inverse mod \(n\), i.e. \(k\cdot k^{-1} = 1\ (\mathrm{mod}\ n)\).

Note that I wrote \(F_n\) or, better, \(\mathbb{F}_n\) instead of \(\mathbb{Z}_n\) because, when \(n\) is prime, the latter is actually a field. The coordinates we've been working with for all this time are in \(\mathbb{Z}_p\), which is also a field, since \(p\) is prime. That's why I wrote "some 3D space" before: depending on which field we choose, we'll end up with a different 3D space.

We basically already observed that \(\mathbb{Z}_n\), with \(n\) prime, is a field, but we never spelled it out.

That's actually why our math works both in the continuous case and mod \(p\). The theory only requires that the coordinates are elements of a field. It doesn't matter which one.

A field \(\mathbb{F}\) is a set equipped with two binary operations, addition and multiplication, such that:

• \(\mathbb{F}\) is a commutative group under addition
• \(\mathbb{F}\setminus\{0\}\) is a commutative group under multiplication
• A distributive law holds:

Note that \(\mathbb{F}\setminus\{0\}\) means "\(\mathbb{F}\) minus \(\{0\}\)", i.e. \(\mathbb{F}\) without the element \(0\).

\(\mathbb{Z}_n\setminus\{0\}\), with \(n\) prime, is a group under multiplication because:

• Multiplication is associative: \(a(bc) = (ab)c = abc\).
• There's an identity: \(1\)
• Every (non-zero) element \(x\) has inverse, i.e. the famous multiplicative inverse mod \(n\).

The \(0\) element has no multiplicative inverse since there's no \(x\) such that \(0\cdot x = 1\). That would be against the very definition of \(0\) as the identity for the addition operation.

When \(n\) is not prime, we lose the group under multiplication because the inverse doesn't exist for all elements. For instance, let's consider mod \(6\):

• \(3\cdot 0 = 0\)
• \(3\cdot 1 = 3\)
• \(3\cdot 2 = 0\)
• \(3\cdot 3 = 3\)
• \(3\cdot 4 = 0\)
• \(3\cdot 5 = 3\)

Since \(3\) and \(6\) are not coprime, \(3\) has no inverse.

When \(n\) is not a prime number, \(\mathbb{Z}_n\) is just a (commutative) ring, which has a weaker structure.

Well-known examples of fields are:

• \(\mathbb{Q}\): the rational numbers
• \(\mathbb{R}\): the real numbers
• \(\mathbb{C}\): the complex numbers

The integers are clearly not a field since, for instance, \(3x = 1\) has no integer solution, so \(3\) has no multiplicative inverse. So, by adding a mod \(p\), with \(p\) prime, we gain more structure, and we get ourselves a field!

Back to the algorithm. The first two lines are pretty easy:

• We generate a random (uniformly distributed) temporary nonce \(k\) (a number to be used only once ever)
• We convert \(k\) into the associated point \(R\) on the curve
  • The point has coordinates \((R_x, R_y)\) (mod \(p\))
  • It's computationally infeasible to go back from \(R\) to \(k\).
• Note that \(n < p\), otherwise \(r\) would just be \(R_x\).

Since \(d\) is the private key, then \(dG\) is the public key. We'll call it \(Q\).

Verifying the signature

Given \(r\), \(s\), \(Q\), and the message, we can verify the signature by:

• hashing the message to get \(z\)
• recovering \(R\)
• checking that \(R_x\ \mathrm{mod \ n} = r\)

We know that \(R = kG\) and that \(s\) contains \(k\), but in inverse form. If we invert \(s\) and multiply it by \(G\), we get

\[s^{-1}G = (z+rd)^{-1}kG = (z+rd)^{-1}R\]

Mhm... if we had \(d\), we could compute \((z+rd)\) and use it to cancel \((z+rd)^{-1}\) and get \(R\).

While we don't have \(d\), we do have \(Q = dG\), which means that although we can't compute \((z + rd)\), we can compute \((z + rd)G\):

\[(z + rd)G = (zG + rQ)\]

If we multiply that by \(s^{-1}\) we get

\[s^{-1}(zG + rQ) = s^{-1}G(z+rd) = (z+rd)^{-1}R(z+rd) = R\]

In words, we factor out \(G\) from \(zG + rQ\) and form \(s^{-1}G\), which is just \((z+rd)^{-1}R\), as we saw at the beginning.

We did it! Now we check that \(r = R_x\ \mathrm{mod}\ n\).

Here's the algorithm:

• \(w = s^{-1}\ \mathrm{mod}\ n\)
• \(u_1 = (z\cdot w)\ \mathrm{mod}\ n\)
• \(u_2 = (r\cdot w)\ \mathrm{mod}\ n\)
• \(R = u_1\cdot G + u_2\cdot Q\)
• check that \(r = R_x\ \mathrm{mod}\ n\)

Observe that \(((zw)G + (rw)Q)\) is more efficient than \(s^{-1}(zG + rQ)\) because, in the former, \(w\) multiplies two numbers, while, in the latter, \(s^{-1}\) multiplies a point.

Recovering \(Q\)

Now the only problem is that in Ethereum the public key \(Q\) doesn't come with the signature. However, we can recover it from \(r\), \(s\), and \(v\).

As we know, \(Q = dG\) and \(s = k^{-1}(z+rd)\), so we should try multiplying \(s\) by \(G\):

\[sG = k^{-1}(z+rd)G = k^{-1}(zG + rQ)\]

To solve for \(Q\), we need to get rid of that \(k^{-1}\). We can't just multiply \(sG\) by \(k\) because we don't know \(k\)... but wait:

\[(zG + rQ) = ksG = s(kG) = sR\]

Therefore:

\[Q = r^{-1}(sR - zG)\]

Unfortunately, we don't know \(R\). But can we recover it? We know \(r = R_x\), so we only need to recover \(R_y\), since \(R = (R_x, R_y)\). We're forgetting something, though: \(r = R_x\ \mathrm{mod}\ n\). Recall that the coordinates of the points on the curve are in \(\mathbb{Z}_p\), not \(\mathbb{Z}_n\). We need to recover the original \(R_x\) from \(r\).

We know that \(R_x \in \{0, \ldots, p-1\}\), and, apparently, \(n\) is just a little smaller than \(p\), which means that \(R_x = r + jn\) for some very small \(j\). We start from \(j = 0\) and keep trying as long as \(r + jn < p\). We say that \(r + jn\) is a candidate for \(R_x\). Let's call the current candidate simply \(x\).

Given \(x\), we can recover \(y\) by using the equation \(y^2 = x^3 + 7\ (\mathrm{mod}\ p)\) itself and solve for \(y\). There are fast algorithms to do that. If there's no solution, we try the next candidate. Otherwise, we get two possible solutions: \(y\) and \(-y\). If you recall, \(v = R_y\ \mathrm{mod}\ 2\), which tells us the solution to pick:

• if \(y\ \mathrm{mod}\ 2 = v\), we choose \(y\)
• otherwise, we choose \(-y\)

One might wonder why we preserve the least significant bit of \(R_y\) to select the correct \(y\). That's because if \(y\) is in \(\{0, \ldots, p-1\}\), then \(-y\ \mathrm{mod}\ p = p-y\). It's clear that \(y + (p-y) = p\), which is odd (being a big prime), which implies that only one of \(y\) and \(-y\) can be odd (or even) mod \(p\).

Anyway, once we have \(R = (x, y)\), we compute \(Q = r^{-1}(sR - zG)\).

Now we must check that \(Q\) is valid, i.e. that \(Q\) is on the curve. If it's not, then we try the next candidate.

We should actually check that \(Q\) is in \(G\), but, apparently, \(G\) contains all the solutions of \(y^2 = x^3 + 7\ \mathrm{mod}\ p\), so if \(Q\) is on the curve then it's also in \(G\).

Signature malleability attack

We left this for last, but after all we've been through, this is disappointingly straightforward.

If \((r, s, v)\) is a signature created by signing a message \(M\) with a private key \(d\), then so is \((r, n-s, 1-v)\).

That's it. The problem arises when someone blacklists \((r, s, v)\) (once it's been used) believing that this will prevent double spending. An attacker will use the signature \((r, n-s, 1-v)\) to send the same message for a second time, bypassing the blacklist.

Instead, programs should use nonces contained directly in the messages and blacklist the nonces or the messages themselves.

Let's see why both signatures are valid.

Let's recall the signing algorithm:

Now let's see what happens if we use \(-k\) instead of \(k\):

\[ \begin{align*} k' &= -k \\ R' &= k'G = -kG = -R = (R_x, p-R_y) \\ r' &= R'_x\ \mathrm{mod}\ n = R_x\ \mathrm{mod}\ n = r \\ s' &= (k'^{-1} (z + r'd))\ \mathrm{mod}\ n \\ &= -(k^{-1}(z + rd))\ \mathrm{mod}\ n \\ &= -(k^{-1}(z + rd)\ \mathrm{mod}\ n)\ \mathrm{mod}\ n \\ &= -s\ \mathrm{mod}\ n \\ &= n-s \\ v' &= R'_y\ \mathrm{mod}\ 2 = (p-R_y)\ \mathrm{mod}\ 2 = 1-v \\ (r', s', v') &= (r, n-s, 1-v) \\ \end{align*} \]

That is, given the signature computed with \(k\), we can trivially get the one computed with \(-k\).

Basically, by using \(-k\) instead of \(k\), we reflect \(R\) across the X-axis and flip \(v\) to signal that we switched the \(y\) coordinate.

The end

I hope you enjoyed the ride and deepened your understanding of ECDSA as much as I did.