Elliptic Curves  Bitcoin & Haskell
In this series of posts I’m solving the exercises of Programming Bitcoin^{1} in Haskell, I’m learning Bitcoin and Haskell in one go.
To describe a point in the elliptic curve, we need four data points. \((x, y)\)
are the coordinates themselves, additionally we need the constants \((a, b)\)
that define the elliptic curve given by the equation \(y^2 = x^3 + ax +b\).
Finally, there is the special case of the point at infinity, which does not
really fit in the previous constrain. In other languages I would just describe
with an invalid or null value, in Python for example I would use the None
value in both \((x, y)\) coordinates, yet in Haskell it can be beautifully
defined as an element of the type. That is certainly a killer feature of the
language, and I expect to be using it more often.
import Text.Printf
data ECPoint
= Infinity
 ECPoint
{ x :: Double
, y :: Double
, a :: Double
, b :: Double
}
deriving (Eq)
instance Show ECPoint where
show Infinity = "ECPoint(Infinity)"
show p = printf "ECPoint(%f, %f)_%f_%f" (x p) (y p) (a p) (b p)
That is very concise, the point at infinity stands on its own with the
Infinity
constructor, and then rest of the points that are on the curve are
defined with the constructor ECPoint
. We derive the equality for this type,
and specify how to show it, this time using printf
for string
interpolation(notice also the import).
This type can store any point, yet it does not validate that we effectively have a point on the elliptic curve. It would be nice to have the validation in the constructor, as done in the book^{1}, but I don’t know how to do that yet. Thus, I implement the validation as a separate function.
validECPoint :: ECPoint > Bool
validECPoint Infinity = True
validECPoint p = y p ^ 2 == x p ^ 3 + a p * x p + b p
With this I’m responsible for checking the validity of points by myself whenever I use them. A bit inconvenient, but for carring on as solution is good enough.
I’ll let you go over the mathematical derivation of point addition on the
Book^{1}. Here, I just present you how concisely it can be expressed using
guards in Haskell. It is like a case/switch statement in other languages. I also
like the where
keyword, after which I can define local auxiliary functions.
add :: ECPoint > ECPoint > ECPoint
add Infinity p = p
add p Infinity = p
add p q
 a p /= a q  b p /= b q = error "point not on same curve"
 x p == x q && y p /= y q = Infinity
 x p /= x q = new_point $ (y q  y p) / (x q  x p)
 x p == x q && y p == 0 = Infinity
 p == q = new_point $ (3 * x p ^ 2 + a p) / (2 * y p)
 otherwise = error "Unexpected case of points"
where
new_point slope =
let new_x = slope ^ 2  x p  x q
new_y = slope * (x p  new_x)  y p
in ECPoint new_x new_y (a p) (b p)
That is a very compact solution. Maybe to dense for my taste, yet because it can be so compact, I imagine maintenance of the code should be easier and localized. Although, small auxiliary functions rarely need maintenance. That might be again another feature of Haskell, as you try to keep functions small and with one responsibility, maintenance becomes manageable when the project grows.
I’m still in the getting used process. Haskell at this point is incredibly concise, and tries to avoid clutter in the code. Having worked with LISP lately, I start missing parenthesis in Haskell. Maybe with more experience my mind will get used to it, recognize that functions bind the strongest, and that parenthesis are indeed noise. Other than that, I do find the solution very nice.

Jimmy Song, Programming Bitcoin, O’Reilly Media, Inc. ISBN: 9781492031499, 2019 ↩︎