“We have elected to put our money and faith in a mathematical framework that is free of politics and human error.” - Tyler Winklevoss

Intro

This is the first part in a series to re-implement Bitcoin using C++. to build a solid foundation we need to understand the math in Bitcoin’s core. in this post, we will be covering the math behind Bitcoin’s cryptography.

But I have to warn you, I don’t have a formal academic background in math. If you do, you should probably search for a deeper and more technical explanation. The way I approached the mathematical side of Bitcoin Core was to get a high-level overview of the concepts and, most importantly, to answer the question of “why?” Why exactly do we use these mathematical creatures in blockchain cryptography?

Most of what you’ll read here is me trying to make sense of these mathematical concepts intuitively and drawing conclusions without formal proof. Are you okay with that? You better be! I’ve tried to link as many resources as possible for further digging, and I encourage you to do so. Dig deep!

Fields

Our first introduction to mathematics was through real numbers and the basic operations of addition and multiplication. These operations felt concrete and real, but then we encounter algebra where letters represent unknown variables in equations. Abstract algebra is a continuation of this line of thought, but more abstract. As awesome as algebra is, it is limited to a known family of mathematical objects (real numbers, complex numbers, polynomials…) that are not suitable for representing complex computational entities. We need a more general, broad, and abstract way to translate the world into mathematical objects. To that end, an algebraic structure is simply a set of elements with one or more rules defined on them. For example, consider a set of colours (red, blue) and a rule that states that when you mix red and blue in any order, you get purple. This is an algebraic structure: a set of elements (colours) with a rule defined on them (mixing colours). We humans or them mathematicians define what elements should be in the set and what rules should be defined on them. We call these rules axioms. Unsurprisingly, it turns out that many natural phenomena obey our algebraic structures and we can use those to model them. Some examples of algebraic structures include:

• Group

• Ring

• Field

We will provide a formal definition of a field, but I encourage you to watch the videos above on other algebraic structures to gain a better understanding of the concept (yes, they are videos, not Wikipedia articles). Briefly, the difference between these structures lies in the rules defined on the elements. If you can add and subtract elements, you have a group. If you can add, subtract, and multiply elements, you have a ring. If you can add, subtract, multiply, and divide elements, you have a field.

One thing to note is that in abstract algebra, we define subtraction as the “addition of the negative” and call it the additive inverse. That is a + (-a) = 0

The same goes for multiplication. We define division as “multiplication by the multiplicative inverse,” or: a * 1/a = 1

You may be asking why we don’t just define subtraction and division as we’re used to. The truth is, I don’t know why? But I guess that this shift in thinking helps think more abstractly about the properties of the elements in the field.

Now, for a formal definition of a field:

a field is a set of elements with two binary operations defined on them, addition and multiplication, such that:

• addition is commutative and associative

• multiplication is commutative and associative

• addition is distributive over multiplication

• there exists an additive identity element 0 such that for all a in F , a + 0 = 0

• there exists an additive inverse element -a such that for all a in F , a + -a = 1

• there exists a multiplicative identity element 1 such that for all a in F , a * 0 = 0

• there exists a multiplicative inverse element 1/a such that for all a in F , a * 1/a = 1

Here’s a diagram explaining the seven axioms in more detail:


Some examples of fields are (real numbers R, complex numbers C rational numbers Q) meaning all elements in those fields adhere to the axioms defined above, while other fields like integers Z and natural numbers N are not fields because they don’t obey all the axioms. specifically integers don’t have a multiplicative inverse element and natural numbers don’t possess an additive inverse element(they don’t have negative numbers).

Galois Fields

We took this whole detour to get the foundation first! and as you may guess Galois Fields (named after the guy who discovered them, Evariste Galois beside being math savvy this guy was a wild fella who died in his early 20s in a duel fight, check him out here) are a family of fields differentiated from fields like real numbers and complex numbers by the fact that they’re finite and they possess a unique and fascinating property. in cryptography, you almost always wanna deal with finite algebraic structures. my reasoning behind this is to create a deterministic environment for your computations. so what’s this unique and fascinating property about Galois fields, A field is a Galois field if it has P^m elements, where P is a prime number and m is a positive integer.

Some examples of Galois fields are:

$$GF(2^3) = [0,1,2,3,4,5,6,7] (2^3 = 8)$$

$$GF(3^2) = [0,1,2,3,4,5] (3^2 = 9)$$

$$GF(5^2) = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14] (5^2 = 25)$$

Some examples of non-Galois fields are:

$$GF(5^2) = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14] (5^2 = 25)$$

$$GF(6^2) = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23](6^2 = 36)$$

How to compute in a Galois field?

In finite fields, addition, subtraction, multiplication, and division are performed in a similar way to how they are performed in a set of real numbers. However, the main difference is that in a finite field, and make sure to remember this the result of any of these operations must always be an element of the field.

For example, if we have a finite field with the elements {1, 2, 3, 4, 5}, we can perform addition and subtraction in the same way we do with real numbers. For example, if we want to add 5 + 3, we would simply calculate 5 + 3 = 8. However, since 8 is not an element of our finite field, we need to “wrap around” and find the remainder when 8 is divided by the number of elements in the field. In this case, that would be 3, so the result of 5 + 3 in our finite field would be 8 mod 5 = 3.

Multiplication in a finite field works similarly. For example, if we want to multiply 2 * 6, we would calculate 2 * 6 = 12. Since 12 is not an element of our finite field, we would again need to “wrap around” and find the remainder when 12 is divided by the number of elements in the field, which would give us 12 mod 5= 2.

With Division things get more interesting, first let’s look at division in regular arithmetic. Suppose we want to perform the division 6/3. We know that division is the inverse of multiplication, so we can rewrite this as 6 * (1/3). The inverse of 3 is 1/3 because 3 * 1/3 = 1. Therefore, we can simplify this expression to 6 * (1/3) = 2.

Now what about division in a finite field? Suppose we want to perform the division 3/7 in the finite field of prime order 19. We know that division in a finite field is closed, which again means that the result of any operation must always be an element of the field, we again need to “wrap around”. 3 * 7 = 21 % 19 = 2 which means that 2/7 = 3 not as intuitive hmmm ?.

So how do we find the inverse of the divisor in a finite field? One way to do this is by using Fermat’s little theorem, this theorem states that if p is a prime number and a is an integer not divisible by p, then a^(p-1) = 1 (mod p). In other words, if we raise a to the power of p-1 and take the result modulo p, we get 1. This can be useful in finding the inverse of an element in a finite field because if we raise the element to the power of p-2 (which is the same as raising it to the power of -1), we should get its inverse.

For example, consider a finite field of prime order 19, and suppose we want to calculate 2/7. In this case, we can first calculate the inverse of 7 using Fermat’s little theorem: 7^(-1) = 7^(19-2) = 7^17. Then, we can use this value to perform the division using the formula c = (a/b) % p, where c is the result of dividing a by b, a and b are elements of the finite field, and p is the prime order of the field:

c = (2/7) % 19 = (2 * 7^17) % 19 = (2 * 232630513987207) % 19 = 3

Not as intuitive hmmm?

We can beat the intuitiveness by refactoring our division to an exponentiation and indeed as you might guess for large prime orders (and that’s what we deal with the most in cryptography), finding the inverse of an element in a finite field can be crazy computationally expensive, finding the inverse requires computing modular exponentiation, which is indeed a very slow operation for large exponents.

ok enough talking, let’s get coding: my initial folder structure looks like this:

.
├── Makefile
├── README.md
├── crypto
│   ├── FieldElem.cpp
│   └── includes
│       └── FeildElem.hpp
└── main.cpp

I represented a field element in FieldElem.hpp as:

#pragma once
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
class FieldElem
{
public:
    FieldElem(cpp_int num, cpp_int prime);
    FieldElem(const FieldElem &other);
    FieldElem &operator=(const FieldElem &other);
    ~FieldElem();
    // getters
    cpp_int const &getNum() const;
    cpp_int const &getPrime() const;
    // overloads
    bool operator==(const FieldElem &other) const;
    bool operator!=(const FieldElem &other) const;
    FieldElem operator+(const FieldElem &other) const;
    FieldElem operator*(const FieldElem &other) const;
    FieldElem operator/(const FieldElem &other) const;
    FieldElem pow(cpp_int exponent) const;

private:
    cpp_int num;
    cpp_int prime;
};

Our constructor, copy constructor, destructor and Copy assignment operator and getters are as simple as:

#include "includes/FieldElem.hpp"

FieldElem::FieldElem(cpp_int num, cpp_int prime) : num(num), prime(prime)
{
    if (num >= prime || num < 0)
    {
        throw std::invalid_argument("Num is not in field range 0 to prime-1");
    }
}
FieldElem::FieldElem(const FieldElem &other) : num(other.num), prime(other.prime)
{
}

FieldElem &FieldElem::operator=(const FieldElem &other)
{
    if (this != &other)
    {
        num = other.num;
        prime = other.prime;
    }
    return *this;
}

FieldElem::~FieldElem()
{
}

// Overload
bool FieldElem::operator==(const FieldElem &other) const
{
    return (num == other.num && prime == other.prime);
}

bool FieldElem::operator!=(const FieldElem &other) const
{
    return !(*this == other);
}
cpp_int const &FieldElem::getNum() const { return num; }
cpp_int const &FieldElem::getPrime() const { return prime; }

pretty self-explanatory, Two points worth highlighting is first that we’re using arbitrary length integer from the boost library as moving on we’ll deal with pretty big numbers, and second that we check in our constructor if num is in the range from 0 to prime-1 and throws an exception if not.

probably what matters most is our arithmetic operator overloads and they look like the following:

FieldElem FieldElem::operator+(const FieldElem &other) const
{

    if (prime != other.prime)
    {
        throw std::invalid_argument("Cannot add two numbers in different Feilds");
    }
    FieldElem res = *this;
    res.num = (res.num + other.num) % prime;
    return res;
}

FieldElem FieldElem::operator*(const FieldElem &other) const
{
    if (prime != other.prime)
    {
        throw std::invalid_argument("Cannot multiply two numbers in different Feilds");
    }
    FieldElem res = *this;
    res.num = (res.num * other.num) % prime;
    return res;
}

FieldElem FieldElem::operator/(const FieldElem &other) const
{
    if (prime != other.prime)
    {
        throw std::invalid_argument("Cannot divide two numbers in different Feilds");
    }
    FieldElem res = *this;
    res.num = (res.num * other.pow(prime - 2).num) % prime;
    return res;
}

FieldElem FieldElem::pow(cpp_int exponent) const
{
    cpp_int n = exponent % (prime - 1);
    if (n < 0)
    {
        n += prime - 1;
    }
    /* 
       we make use of binary exponetiation to 
       reduce complexity from O(n) to O(log n).
    */
    cpp_int res = 1;
    cpp_int x = num;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            res = (res * x) % prime;
        }
        x = (x * x) % prime;
        n /= 2;
    }
    FieldElem result(res, prime);
    return result;
}

operator+ and operator* methods take another FieldElem object as an argument and returns a new FieldElem object that is the sum or product of the two params. The method checks if the two field elements have the same prime, and if not, it throws an exception. it then executes the operation and reduces the result modulo prime.

pow is our exponentiation method, exponentiation This method takes a cpp_int as an argument and returns a new FieldElem object that is the power of the field element raised to that exponent. also, we’re using the binary exponentiation algorithm to reduce the complexity of you know exponentiation from O(n) to O(log n).

operator/ performs division on FieldElement objects. as we mentioned by using Fermat’s little theorem. we make use of pow method for that.

And with that, I see you in the next part where we’ll be talking about Elliptic curves.