## Elliptic Curves on Finite Fields - Bitcoin & Haskell

When merging the last two posts, I immediately run into serious difficulties. Haskell’s type system just made my work harder(well my ignorance did). Until I could come up with a solution, I could not appreciate how the strictness of the type system actually gives flexibility.

## Rewrite the finite field

Previously I used a type that stored the number and the order of the field. That
was the solution of the Python code from the Book^{1}. It is how I would have
done it in any other language I know. However, that was a limitation, for
example when writing the instance for `Num`

, I could not define the function
`fromInteger`

. Researching how could I work with finite fields in Haskell I
found a package for exactly this use: finite-field
. However, reading that code
was too much of a challenge for me. Luckily, I also found this stackoverflow
question “Prime finite field (Z/pZ) in Haskell with Operator Overloading”
. That
gave me a workable solution. I can encode the order of the field as part of the
type. That is really cool!

```
1{-# LANGUAGE DataKinds #-}
2{-# LANGUAGE KindSignatures #-}
3
4import GHC.TypeLits
5newtype FieldElement (n :: Nat) = FieldElement Integer deriving Eq
```

This turned very quickly into quite advanced Haskell. You need 2 language
extensions that I don’t yet know what they mean, but the compiler kindly tells
you, you need them. Importing `GHC.TypeLits`

lets you work with natural numbers
as part of the types. With this, `FieldElement`

only wraps an `Integer`

and
derives the Integer equality. You can use `newtype`

to define the type, because
there is only one constructor, with one field. The cool new stuff happens left
of the `=`

, when defining the type, constraining it to `n :: Nat`

, this `n`

,
that represents the order of the field, must be a natural number.

Now, make `FieldElement`

an instance of `Num`

as before, yet with this new
definition, you don’t need to check the order of the field for each operation,
since it is given by the type. The type system will now check that you don’t mix
`FieldElement`

of different orders, because they are now objects of different
types.

You first need another language extension and a new import. Place them on the top of the file.

```
1{-# LANGUAGE ScopedTypeVariables #-}
2import Data.Proxy
```

The instance is `Num (FieldElement n)`

and you need to make sure that `n`

is an
instance of `KnownNat`

. With that you can use the function `natVal`

to recover
the value of the order of field from the type and use it for all the functions
in `Num`

. `fromInteger`

takes all the management of the field order. In the last
post I could not implement that function and now it is doing all the work.

```
1instance KnownNat n => Num (FieldElement n) where
2 FieldElement x + FieldElement y = fromInteger $ x + y
3 FieldElement x * FieldElement y = fromInteger $ x * y
4 abs x = x
5 signum _ = 1
6 negate (FieldElement x) = fromInteger $ negate x
7 fromInteger a = FieldElement (mod a n)
8 where n = natVal (Proxy :: Proxy n)
```

Using the same trick with `natVal`

create the instance of `Fractional`

and
`Show`

.

```
1instance KnownNat n => Fractional (FieldElement n) where
2 recip a = a ^ (n - 2) where n = natVal (Proxy :: Proxy n)
3 fromRational r = error "cant transform"
4
5instance KnownNat n => Show (FieldElement n) where
6 show (FieldElement a) = "FieldElement_" ++ show n ++ " " ++ show a
7 where n = natVal (Proxy :: Proxy n)
```

You can then define a number (e.g. 3) in the prime field (e.g 17) in this way:

```
1three = FieldElement 3 :: FieldElement 17
```

## Generalizing the elliptic curves over finite fields

In the last post I described the elliptic curve over the reals, more accurately
over floating point numbers of type `Double`

. Mathematically, it is also
possible to describe the elliptic curve over finite fields. The extension
requires no work on the mathematical side, it just works. In our case, you do
need to remove the explicit Type dependence to `Double`

to make things more
general.

This means `ECPoint`

now needs a type parameter, which defines the field over
which the points are defined. It could be `Double`

as previously, but now it can
also be `FieldElement n`

. It can take anything type, but it is over those two
that things will be defined and usable as some type constrains do come up in
later definitions.

```
1data ECPoint a
2 = Infinity
3 | ECPoint
4 { x :: a
5 , y :: a
6 , a :: a
7 , b :: a
8 }
9 deriving (Eq)
```

I could define the constants `a`

and `b`

also as part of the type, yet for the
Moment I’m lazy to implement that and I still don’t find the need to do so as
with finite fields.

To validate a point, the function is the same, yet type constrains already start
to show up. `Eq`

is still mostly defined for all types, yet `Num`

already
constrains the usable ones.

```
1validECPoint :: (Eq a, Num a) => ECPoint a -> Bool
2validECPoint Infinity = True
3validECPoint (ECPoint x y a b) = y ^ 2 == x ^ 3 + a * x + b
```

Defining addition of points in the elliptic curve requires no change in the code, only the enforcement of the type constraints.

```
1add :: (Eq a, Fractional a) => ECPoint a -> ECPoint a -> ECPoint a
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)
```

Finally to get things to show up nicely on the console, I prepare the instances
of show. In this case I learned again about a new language pragma. I wanted to
show the `ECPoint`

as before for other `Double`

type and then be more specific
when dealing with finite fields. Implementing this too instances got the
compiler to complain and so I learned about overlapping instances. First you
need the language extension `FlexibleInstances`

. Then using the `OVERLAPPABLE`

pragma when defining the most generic `Show`

instance, which only requires the
type to be instance of `Num`

. That covers the instance of `Double`

. Because,
`FieldElement n`

is an instance of `Num`

the problem of overlapping arose, with
the pragma `OVERLAPPING`

, it is now allowed as it is more specific than the
`Num`

case, and it will be used for the field elements.

```
1{-# LANGUAGE FlexibleInstances #-}
2import Text.Printf (PrintfArg, printf)
3
4instance {-# OVERLAPPABLE #-} (PrintfArg a, Num a) => Show (ECPoint a) where
5 show Infinity = "ECPoint(Infinity)"
6 show p = printf "ECPoint(%f, %f)_%f_%f" (x p) (y p) (a p) (b p)
7
8instance {-# OVERLAPPING #-} KnownNat n => Show (ECPoint (FieldElement n)) where
9 show Infinity = "ECPoint(Infinity)"
10 show p = "ECPoint_" ++ show n ++ points ++ params
11 where
12 n = natVal (Proxy :: Proxy n)
13 points = "(" ++ si (x p) ++ ", " ++ si (y p) ++ ")"
14 params = "a_" ++ si (a p) ++ "|b_" ++ si (b p)
15 si (FieldElement r) = show r
```

I can define a point like this

```
1dd =
2 let a = FieldElement 0 :: FieldElement 223
3 b = FieldElement 7
4 x = FieldElement 192
5 y = FieldElement 105
6 in ECPoint x y a b
```

Haskell’s compiler will infer the field order for the variables `b`

, `x`

and
`y`

, to be also `FieldElement 223`

. Because `ECPoint`

requires all arguments to
be of the same type. As a matter of fact, because I defined `fromInteger`

earlier in `Num`

for `FieldElement`

, I can define that point like this too:

```
1ee = ECPoint 192 105 (FieldElement 0 :: FieldElement 223) 7
2ff = ECPoint 192 105 0 7 :: ECPoint (FieldElement 223)
```

### Scalar multiplication

Having addition already defined over points on the elliptic curve with the
function `add`

, it is also useful to use multiplication as an abbreviated sum.
That is

\[5 \cdot A = A + A + A + A + A\]

Very naively that can be implemented as:

```
1aPoint = ECPoint 192 105 0 7 :: ECPoint (FieldElement 223)
2total = add aPoint $ add aPoint $ add aPoint $ add aPoint aPoint
```

That looks like a job for `foldr`

```
1totalfoldr = foldr add Infinity $ replicate 5 aPoint
```

However, the process of adding each term as many times as the factor we are
using is very CPU time consuming. When working on very large fields and with
very large factors, the individual sum becomes unfeasible. However, we can
shorten the multiplication by using a binary expansion, using the accumulated
sum of `A`

, in powers of two. That is:

\[ 5 \cdot A = (\underbrace{(A + A)}_{2A} + 2A) + A\]

Which is possible because addition on elliptic curves is associative and commutative.

This binary expansion and the corresponding scalar product can be implemented
using Haskell’s library for bitwise operations `Data.Bits`

.

```
1import Data.Bits
2
3binaryExpansion :: (Eq a, Fractional a) => Integer -> ECPoint a -> ECPoint a -> ECPoint a
4binaryExpansion m value result | m == 0 = result
5 | otherwise = binaryExpansion (m `shiftR` 1) (add value value) accumulator
6 where
7 accumulator = if m .&. 1 == 1 then add result value else result
8
9scalarProduct :: (Eq a, Fractional a) => Integer -> ECPoint a -> ECPoint a
10scalarProduct m ec = binaryExpansion m ec Infinity
```

This way that product can be calculated as:

```
1totalbin = scalarProduct 5 aPoint
```

### Instantiating the monoid type class for `ECPoint`

By now you might have noticed that points on the elliptic curve are also monoids, and thus just for completeness we can implement it.

```
1instance (Eq a, Fractional a) => Semigroup (ECPoint a) where
2 (<>) = add
3
4instance (Eq a, Fractional a) => Monoid (ECPoint a) where
5 mempty = Infinity
```

This way we create another way of expressing the multiplication:

```
1totalmconcat = mconcat $ replicate 5 aPoint
```

And also even a more general way of representing the `binaryExpansion`

expansion.

```
1binaryExpansion :: (Semigroup a) => Integer -> a -> a -> a
2binaryExpansion m value result | m == 0 = result
3 | otherwise = binaryExpansion (m `shiftR` 1) (value <> value) accumulator
4 where
5 accumulator = if m .&. 1 == 1 then result <> value else result
```

That is awesome, now it has become a quite generic function, as it should, because the binary expansion is a very generic procedure.

## Conclusion

This was a fascinating learning experience. It was a lot more than just translating Python code to Haskell. Haskell made it difficult to just take the Python solution, and at the same time it forced me to investigate a lot more on its capabilities. Trying to compile this small program and having error messages that at least hint me to my next web search was of enormous help.

I find it fantastic that learning Haskell also forces you to think about properties of the objects you are dealing with. It was only through Haskell, that I thought of points on the elliptic curve to be monoids, and that by recognizing that property as a consequence my code can be refactored to be more generic.

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.