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 consice, 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.

---

1. Jimmy Song, Programming Bitcoin, O'Reilly Media, Inc. ISBN: 9781492031499, 2019 ↩ ↩ ↩