Computing, Math and Beauty

I've been reading this really approachable book on Bitcoin — Programming Bitcoin by Jimmy Song. It tries to cover a broad range of topics, from cryptography to abstract algebra, and I think the author has done a solid job making all of it accessible to readers like me. I especially enjoyed the sections on elliptic curve cryptography. That said, there are a few places where the book seems to gloss over details — things that I think are worth digging into if you're reading carefully. I'm going to walk through some of those points here.

Why is integer modulo $$p$$ forms a field iff $$p$$ is prime?

The book doesn't go into details about why it's not a field when $$p$$ is not prime. I feel the proof of it is quite simple and elegant and worth mentioning. Suppose $$p$$ is not prime, then it can be expressed as a product of two integers $$a$$ and $$b$$ such that $$1 < a,b < p$$. i.e., $$p = ab$$.

Now $ab \equiv 0 \mod p$, which means $$a$$ and $$b$$ are both zero divisors in the field of integers modulo $$p$$. Which means $$b$$ doesn't have a well defined multiplicative inverse because there is no way to recover $a$ from $0$ multiplicatively in the field of integers modulo $$p$$, which is what multiplicative inverses are.

Field of scalar multiplicants of elliptical group

In the part Inscribing the Target in Chapter 3, we have lot of these variables like $$k$$, $$z$$, $$r$$ and $$s$$ and work with them to do addition, multiplication and more importantly division ($$u = z/s$$ and $$v = r/s$$). They are considered to be integers, but they can't be integers if we can do division on them right? They have to be a field. But the scalar multiplicands in general case forms a different structure called a ring. A ring is a set of elements that can be added and multiplied, but not necessarily divided.

For example, let $G$ be the generator of the elliptical group with characteristic $n$ (ie., $nG = 0$), let $a$ and $b$ be two multiplicants then

• $$0G = 0$$ (the infinity point)
• $$aG + bG = (a + b)G$$
• $$aG = (a + 0)G = aG + 0G$$
• $$abG = a(bG) = b(aG)$$
• $$aG = (a - n)G + nG = (a - n)G + 0 = bG$$ if $a > n$ and $a \equiv b \mod n$

Hence, the set of scalar multiplicands of the elliptic curve group forms a ring — not a field in general. But the book assumes, somewhat implicitly, that these scalar values form a field, which isn’t true unless the modulus is prime. As discussed earlier, Integer modulo is a field if and only if n is prime. In Bitcoin’s case, this is true — the group is chosen such that the field has a large prime characteristic, which is crucial for security. I think the book glosses over this detail a bit. A careful reader might notice that both the “Programming Signature Verification” and “Signing in Depth” sections silently apply modular arithmetic with a group characteristic — but this isn't called out explicitly. It would’ve been much clearer if those examples consistently used the FieldElement abstraction introduced earlier, which made the underlying field structure obvious

The slope of elliptical curve on cyclic field

In Chapter 2, Point Addition when $$P_1 = P_2$$, the book uses the slope of the elliptical curve to find the tangent line at the point $$P_1$$. At this point in the book we still haven't been introduced to the concept of field and hence it makes sense to use derivatives to find the slope, but after we have been introduced to curves on fields, we don't look back the definition of addition which assumed the points are in euclidean real space. The problem is derivatives are defined geometrically (topologically, to be precise) and not algebraically. There is no concept of set of points close to a point in a cyclic field space (like $$x + \Delta x$$), hence taking derivatives don't hold any meaning in this case.

However the point addition defined as such even works in the cyclic field, why? Because we can derive this algebraically without any geometric notion. We have two equations,

• $$y = mx + c$$ (the equation of the tangent line at $$P_1$$)
• $$y^2 = x^3 + ax + b$$ (the equation of the elliptical curve)

In order to find the $x_3, y_3$ that also solves them, substituting the first equation in second.

• $$(mx + c)^2 = x^3 + ax + b$$ expanding this and regrouping
• $x^3 - m^2x^2 + (a - 2mc)x + (b - c^2) = 0$

Since $P = Q$ we know that this equation has roots $x_1, x_1, x_3$ (double root at $x_1$). ie., $(x - x_1)^2(x - x_3) = 0$. We expand this to get.

• $x^3 - (2x_1 + x_3)x^2 + (x_1^2 + 2x_1x_3)x - x_1^2x_3 = 0$

By matching the coefficients of $x^2$ we get, $x_3 = m^2 - 2x_1$ (same as what the book has, but we haven't gotten $m$ yet)

By matching the coefficients of $x$ we get,

• $a - 2mc = 2x_1x_3 + x_1^2$ (substituting $x_3$ from above)
• $a - 2mc = 2x_1(m^2 - 2x_1) + x_1^2$
• $a - 2mc = 2m^2x_1 - 4x_1^2 + x_1^2$
• $a - 2mc = 2m^2x_1 - 3x_1^2$ (See the $3x_1^2$ term is coming up, Now substituting $c = y_1 - mx_1$)
• $a - 2m(y_1 - mx_1) = 2m^2x_1 - 3x_1^2$
• $a - 2my_1 + 2m^2x_1 = 2m^2x_1 - 3x_1^2$
• $a - 2my_1 = -3x_1^2$
• $m = \frac{3x_1^2 + a}{2y_1}$ (Same as book)

It's bit tedious but without bringing in more machinery from algebraic geometry this is the most honest derivation for newbies. I can understand why these details have been missed out as that would make the book much bigger. Nevertheless I enjoyed the book a lot, I would definitely recommend it to anyone who is newbie and want to know almost everything about crypto like me