BTC#: Finite Fields in C#

Series: BTC# – Learning to Program Bitcoin in C#

« Previous: Big Integers in C#

Next: Elliptic Curves »

Finite Fields

To understand Bitcoin transactions, you need to understand elliptic curve cryptography. To understand elliptic curve cryptography, you need to understand finite fields. Programming Bitcoin’s first chapter goes through the maths of finite fields and develops a Python implementation.

The maths of addition, subtraction, and multiplication of finite fields is essentially the maths of modular arithmetic. Division is less intuitive and it’s best to think of it simply as the inverse of multiplication. The book gives an extensive explanation, which I won’t repeat here, but I will give a hand-waving summary (mainly to help cement it in my own mind.)

Multiplication is simply standard multiplication mod the field order. For example in F5, 2 x 4 = 8 % 5 = 3.

MultiplicationF5.png

Division is simply the inverse operations, so 3 ÷ 2 = 4 and 3 ÷ 4 = 2.

A rigorous explanation of how to do finite field division, courtesy of Jimmy Song and Pierre de Fermat, is given in Programming Bitcoin.

Now we can see why finite fields must have a prime field order. Where we have a non-prime field order, division is not defined because the products are not unique. We can see the repetition in the rows and columns below.

MultiplicationF6.png

In F6, 2 x 4 = 8 % 6 = 2. But 2 x 1 = 2 and 5 x 4 = 2 as well.

(2 x 4) ≡ (2 x 1) ≡ (5 x 4)

So 2 ÷ 2 and 2 ÷ 4 don’t have unique answers.

The Code

The book’s GitHub repo has all the Python source code; mine has the C# version that I’m developing as I work through the book.

The class developed to represent a finite field element has two properties: the value of the element and its field order (i.e. the number of elements in the field). As mentioned in the previous post, I implemented these properties as BigIntegers because I know what’s coming.

public BigInteger Value { get; }
public BigInteger Order { get; }

ValueAndOrder.png

If you grab a copy of the code you can see that all the rest is implementations of various mathematical operators.

In Python, this is done by defining special operator functions, like __eq__. In C# this is done using overloadable operators.

Equality

The C# version of the equality operator looks like this:

public static bool operator ==(FiniteFieldElement a, FiniteFieldElement b)
{
    return ((object)a == null && (object)b == null) || (object)a != null && a.Equals(b);
}

Note that in C# if the == operator is overloaded, the != operator needs to be as well. They both do similar work, which has been delegated to the Equals method:

public override bool Equals(object obj)
{
    if ((obj == null) || !GetType().Equals(obj.GetType()))
    {
        return false;
    }
    else
    {
        FiniteFieldElement fe = (FiniteFieldElement)obj;
        return (Value == fe.Value) && (Order == fe.Order);
    }
}

This is a very common way of implementing this method: a null check and a type check and, if that’s all OK, checking that the two properties are the same.

When Equals() is overridden, GetHashCode() must also be overridden. For a simple class like this it’s easy and quick to take the hashes of the two properties and XOR them.

public override int GetHashCode()
{
    return Value.GetHashCode() ^ Order.GetHashCode();
}

One little gotcha comes up if you ever want to test against null. You can see that in the null check in the operator, the value being tested is cast to an ‘object’ type. If you don’t do that the operator calls itself and eventually causes a stack overflow, so you need to call the base implementation to get the expected behaviour.

Arithmetic Operators

The addition, subtraction, multiplication, and division operators are all also overridden, the first three using simple modular arithmetic equivalents, and the divide operation using a result found in the book, derived from a definition of division as the inverse of multiplication.

In the operator definitions, note the use of the mod() method I talked about in a previous post to handle C#’s lack of a modulo operator, which could bite you when it comes to subtraction.

public static FiniteFieldElement operator -(FiniteFieldElement a, FiniteFieldElement b)
{
    if (a.Order != b.Order)
    {
        throw new ArgumentException($"Subtraction operator is not defined for elements of different order ({a.Order} and {b.Order}.");
    }
    return new FiniteFieldElement((a.Value - b.Value).Mod(a.Order), a.Order);
}

In the book, there’s some discussion of how to reimplement exponentiation for finite fields. This is one thing that’s easier in C# because we can just use BigInteger’s built-in ModPow function.

public FiniteFieldElement Pow(BigInteger exp)
{
    return new FiniteFieldElement(BigInteger.ModPow(Value, exp, Order), Order);
}

Unit Tests

Mathematical libraries like this are the perfect place for textbook Test Driven Development. The functions are all nicely contained and there are no dependencies like user interfaces or databases that need to be stubbed out or worked around. It’s quick and easy to test first, write failing tests for every bug, and maintain good coverage.

To check that the remainder vs. modulus problem isn’t tripping us up, we can do this:

[TestMethod]
public void operatorSubtraction_modulo()
{
    var a = new FiniteFieldElement(7, 13);
    var b = new FiniteFieldElement(12, 13);
    var c = new FiniteFieldElement(8, 13);

    Assert.AreEqual(c, a - b);
}

SubtractionInF13.png

In F13, 7 – 12 = 8 and all is well.

« Previous: Big Integers in C#

Next: Elliptic Curves »

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s