## 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.

```
1data FieldElement =
2 FieldElement
3 { number :: Int
4 , prime :: Int
5 }
6 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.

```
1instance Show FieldElement where
2 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.

```
1instance Num FieldElement where
2 (FieldElement a b) + (FieldElement c d)
3 | b /= d = error "Distinct Fields"
4 | otherwise = FieldElement (mod (a + c) b) b
5 (FieldElement a b) * (FieldElement c d)
6 | b /= d = error "Distinct Fields"
7 | otherwise = FieldElement (mod (a * c) b) b
8 abs a = a
9 signum _ = 1
10 negate (FieldElement a b) = FieldElement (mod (b - a) b) b
11 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 required
operations(functions) of the typeclass, and in return you get the operations
that can be formulated in terms of the required ones for free at the same time.
In this case, substraction and exponentiation are 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.

```
1instance Fractional FieldElement where
2 recip a = a ^ (prime a - 2)
3 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 ↩︎

##### 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.