Finite Fields - Bitcoin & Haskell

Bitcoin's price has gone crazy up, and now I'm really responsible for learning it. I found the book Programming Bitcoin^[1] by Jimmy Song, it looks good enough to give it a try. It uses Python to teach, which is uninteresting and I end up only skimming over it, which leads to low retention. Learning necessitates inefficiencies, trial and error, solving problems and sharing. Thus to learn I need to throw an extra challenge. I'm going to learn another programming language(Haskell) to solve the book's problems.

The first chapter in Programming Bitcoin^[1] deals with finite fields. In Python a class is implemented which holds 2 values and then methods are attached to that class. In Haskell, I use the same idea, only that the procedure is different.

Define a data type, using the record syntax you name the fields number and prime, which gives you the getters automatically. There are no setters, as in Haskell you work with values and those are immutable. deriving (Eq) is really nice, as you get the most evident equality defined for free. In this case, it is the want we need.

data FieldElement =
  FieldElement
    { number :: Int
    , prime  :: Int
    }
  deriving (Eq)

The level of conciseness for this small definition is great compared to Python. I also get the type safety, that ensures this two fields are integers. However, my current ignorance forbids me to implement the check that number<prime on the constructor.

Next step is to implement how to print the value to the screen. You could directly use deriving (Show) and it would be good enough. Yet to have your personal touch you can implement your own instance for the Show typeclass.

instance Show FieldElement where
  show a = "FieldElement_" ++ show (prime a) ++ " " ++ show (number a)

This uses string concatenation, I find it too explicit, yet for the moment I don't know if string interpolation is possible.

The challenging part is now to implement the arithmetic operations. In Python you implement the methods __add__(self, other), __mul__, etc. In Haskell, you have something more interesting. The Num typeclass, which defines the operations numbers should have, and as we are implementing a number in finite field, those operations need to be define for our number. Haskell has codified this mathematical behaviors in the language. You have to provide the implementations, this is my approach.

instance Num FieldElement where
  (FieldElement a b) + (FieldElement c d)
    | b /= d = error "Distinct Fields"
    | otherwise = FieldElement (mod (a + c) b) b
  (FieldElement a b) * (FieldElement c d)
    | b /= d = error "Distinct Fields"
    | otherwise = FieldElement (mod (a * c) b) b
  abs a = a
  signum _ = 1
  negate (FieldElement a b) = FieldElement (mod (b - a) b) b
  fromInteger _ = error "can't transform"

This is absolutely beautiful and elegant, it absolutely trashes the way you implement the same behavior in Python. You must formally define all operations(functions) of the typeclass, and at the same time you get operations for free. Substraction and exponentiation as inferred from these definitions. In the book^[1], there is an optimization for the exponentiation indeed, yet for the moment the goal is to solve the problem, and the inferred definitions are good enough.

Division in missing from the previous typeclass, for that you must also implement and instance of Fractional, which defines the recip function, which lets Haskell infer division for you.

instance Fractional FieldElement where
  recip a = a ^ (prime a - 2)
  fromRational _ = error "can't transform"

I find this a very simple and elegant solution, which passes the simple tests from the Book^[1], yet to reach this solution I had to cover half the book Learn you a Haskell for great good^[2] by Miran Lipovača. That is OK, in the end you must learn your tools first, yet I learn best if instead of the simple exercises matching each chapter I have a challenge I need to solve. I makes my reading more careful as I'm looking for the solution on the materials. Starting with the problem first works better than getting the skill first and then looking for the problem to solve.

Jimmy Song, Programming Bitcoin, O'Reilly Media, Inc. ISBN: 9781492031499, 2019 ↩ ↩ ↩ ↩
Miran Lipovača, Learn You a Haskell for great good!, no starch press ISBN-13: 9781593272838, 2011 ↩