Elliptic Curves - Bitcoin & Haskell
In this series of posts I’m solving the exercises of Programming Bitcoin1 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.
1import Text.Printf
2
3data ECPoint
4 = Infinity
5 | ECPoint
6 { x :: Double
7 , y :: Double
8 , a :: Double
9 , b :: Double
10 }
11 deriving (Eq)
12
13instance Show ECPoint where
14 show Infinity = "ECPoint(Infinity)"
15 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 book1, but I don’t know how to do that yet. Thus, I implement the validation as a separate function.
1validECPoint :: ECPoint -> Bool
2validECPoint Infinity = True
3validECPoint 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
Book1. 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.
1add :: ECPoint -> ECPoint -> ECPoint
2add Infinity p = p
3add p Infinity = p
4add p q
5 | a p /= a q || b p /= b q = error "point not on same curve"
6 | x p == x q && y p /= y q = Infinity
7 | x p /= x q = new_point $ (y q - y p) / (x q - x p)
8 | x p == x q && y p == 0 = Infinity
9 | p == q = new_point $ (3 * x p ^ 2 + a p) / (2 * y p)
10 | otherwise = error "Unexpected case of points"
11 where
12 new_point slope =
13 let new_x = slope ^ 2 - x p - x q
14 new_y = slope * (x p - new_x) - y p
15 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 ↩︎ ↩︎ ↩︎
Dr. Óscar Nájera
Software archeologist – Recovering Physicist – Dancer
As scientist I studied the physics of the very small quantum world. As a computer hacker I distill code. Software is eating the world, and less code means less errors, less problems. Millions of lines of legacy code demand attention and have to be understood and simplified for future reliable operation.