Thread by @YatharthArora8

1/ De-jargoning the Mathematics behind Bitcoin's secured Signatures and Transactions.

Topics - Finite Fields, Elliptic Curves and Elliptic Curve Cryptography.

A Thread.

2/ Bitcoin makes use of the scep256k1 elliptic curve and to understand how the signing and verification of the transactions work and how are they secured, we need to understand two things which form the base of the Elliptic Curve Crytpography
1. Finite Fields
2. Elliptic curves

3/ What are Finite Fields?

Finite field is a set of finite numbers, any two numbers say 'a' & 'b' from the set satisfy the following operations performed using the operators '+' and 'x' -

4/

1. If a and b belongs to the set, then a+b and a x b also belong to the same set

2. 0 exists and has the property 0 + a = a. This is called as the additive identity.

3. 1 exists and has the property 1 x a = a. This is called multiplicative identity.

5/

4. If a is present in the set and is not zero then a-1 is present in the set. Because a x a-1 = 1.

5. If a is present in the set then -a also exists in the set. Because a + (-a) = 0 exists in the set.

The set {0,1,2} is not a finite field since 1+2=3 is not in the set.

6/
A Finite Field Fp of order 'p' is defined as -
Fp = {0,1,2,3,4 ……… , p-1}

For example:
1. F7 = {0,1,2,3,4,5,6}
2. F11 = {0,1,2,3,4,5,6,7,8,9,10}
3. F37 = {0,1,2,3,4,5,6,7,………….,36}

7/ Modulo Arithmetic on Finite Fields
Finite Fields are closed under Addition, Multiplication, Subtraction and Division. They are defined as follows -
If a, b ∈ Finite Field Fp then -
a+b = (a+b)%p ∈ Fp
a x b = (a x b)%p ∈ Fp
a - b = (a- b)%p ∈ Fp

8/
For example:
F7 = {0,1,2,3,4,5,6} with order p=7
6 + 5 = 11 %7 = 4 ∈ F7
6 x 5 = 30 %7 = 2 ∈ F7

If you have noticed, the order(p) of all the Finite fields used so far is a prime number. There is a solid reason behind this.

9/ Consider a Finite Field Fp of order p where p is a prime number.
We know -
Fp = {0,1,2,3,4,5 …., p-1}

Now, Consider any random number k and multiply all the numbers in the set with this value.

=> {kx0, kx1, kx2, kx3, kx4,…….., k x (p-1)}
What do you observe?

10/ For example:
F7 = {0,1,2,3,4,5,6}, order p of the field = 7 and let k=4,9

F7 = {4x0 % p, 4x1 % p, 4x2 % p, 4x3 % p, 4x4 % p, 4x5 % p, 4x6 % p} = {0, 4, 1, 5, 2, 6, 3}
F7 = {9x0 % p, 9x1 % p, 9x2 % p, 9x3 % p, 9x4 % p, 9x5 % p, 9x6 % p} = {0, 2, 4, 6, 1, 3 ,5 }

11/ Clearly the number in the Finite Field remains the same(although the numbers are not in the same order) no matter what is the value of k. And this is only true when the order of the finite field 'p' is a prime number.

(Try repeating the same experiment with the order as 10)

12/ Finite Fields are also closed under Division. But we use Fermat's Little Theorem to find a inverse.

The theorem states that:
k^(p-1) % p = 1 where k>0 and p is a prime number

Proof:

13/ What are Elliptic Curves?
We are familiar with the following equations and their graphs -
1. y = mx + c
2. y = ax^2 + bx + c
3. y = ax^3 + bx^2 + cx + d

Graphs:

14/ The general equation of Elliptic curve looks like:
y^2 = x^3 + ax + b

The real difference between the cubic curve and the elliptic curve is the presence of y^2 term which makes the graph symmetrical over x-axis.

15/ The Elliptic curve that Bitcoin uses is called as scep256k1 and it has the equation:
y^2 = x^3 + 7

Comparing it with the general equation we have a=0 and b=7

Let's explore the Elliptic Curve a bit more -

16/
For every elliptical curve, A line will intersect it at -

1. 3 points as in the case of line L1 (at points A, B & C)
2. 1 point as in the case of line L2 (at point D)

Exceptions:
Line L3 (parallel to x-axis ) and L4 (tangent to the curve) intersect the curve at 2 points.

17/
What is Point Addition ?
A line is defined using two points and the line cuts through the elliptical curve at three points, so a line that cuts the curve at 2 points must cut the curve at a third point, reflected over the x-axis is the result of the point addition.

18/ For any two points A and B on the curve -

1. We draw a line through A and B which intersects the curve at say third point C.
2. Reflect the point C over the x-axis
3. The resulting point is the point addition of A and B

Point Addition is non linear

19/ Some observations:
1. A+B is to the right of both A & B
2. A+C is between both the points
3. B+C is to the left of both the points B & C

Point Addition follows the same laws of associativity, commutativity, identity and invertibility, & can be easily proved using the graphs.

20/ ELLIPTIC CURVE CRYPTOGRAPHY

The concepts of Finite Fields and Elliptic Curves together form the basis of the Elliptic Curve Cryptography which is used in the signing and verification of the transactions in the Bitcoin protocol.

21/ We can use the point addition over Finite Fields. The only difference is that we have to use the addition/multiplication as defined in Finite Fields.

We can check that the point (17,64) lies on the Bitcoin curve y^2 = x^3 + 7 over F103
64^2 % 103 = ( 17^3 + 7 )%103 (= 79)

22/
What is Discrete Log Problem?
Scalar Multiplication is repeated addition.
Since Point Addition is non-linear, Scalar Multiplication is a complete scattershot. Doing the Scalar Multiplication is straightforward, however doing the opposite, point division is not.

23/ Another point of scalar multiplication is that at a certain multiple, we get to a point at infinity. Imagine a point G & scalar multiply until we get the point at infinity, we end up with having -
{G, 2G, 3G, 4G, …… , nG} where nG = 0

This set is called a Finite Group.

24/ Consider the point P = (47,71)
1.P = (47,71)
2.P = (36, 111)
3.P = (15, 137)
.
.
.
.
20.P = (47,152)
21.P = (0,0)

If you look carefully there is no discernible pattern to the scalar multiplication. The x or the y coordinate do not increase or decrease continuously.

25/ The key to making scalar multiplication into public key cryptography is using the fact that scalar multiplication on elliptic curve is very hard to reverse. Scalar multiplication looks really random and what's what gives this equation asymmetry, easy to solve in one direction

26/ DEFINING THE CURVE FOR BITCOIN
Equation of scep256k1: y^2 = x^3 + 7
Comparing it with the general equation y^2 = x^3 + ax + b
For Bitcoin we have -
1. a = 0 and b =7
2. p(order) = 2^256 - 2^32 - 977
3. Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

27/
4. Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
5. n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
Gx refers to the x coordinate of the point G and Gy the y coordinate. The numbers
starting with 0x are hexadecimal numbers

28/ p and n are extremely close to 2^256
HOW BIG IS 2^256 ?
No. of atoms on Earth: 2^50
No. of atoms in solar system: 2^57
No. of atoms in milky way: 2^68
No. of atoms in Universe: 2^80

There are as many possible private keys in Bitcoin as there are atoms in a billion galaxies.

29/
Public Key Cryptography:
P = eG
P is the Public key and e is the private key.
It is easy to calculate P when e and G are given but not possible to find e when P and G are given.

Private Key is a single 256 bit number and public key is a 256 bit coordinate.

30/ Signing & Verification of Transactions

Whenever you do a transaction in Bitcoin, it has to be signed by your private key to give a signature. Both the Public Key and the Signature are attached to the Transaction to send it to memepool and get verified by the miners.

31/ Miners further put the transaction into the blockchain. This signing of the transaction is important to ensure that the transaction is not a fraud and is done by the right person who owns the private key.

32/ How does it work?

P = eG

Choose any random number k and we have kG = r where r is a random public key.

At this point we claim an equation:
uG + vP = kG
vP = (k-u)G
P = (k-u)/v . G
Hence we have,

e = (k-u)/v
If we don’t know 'e', we'll have to play with u,v.

33/
If we are able to find any value of u and v this means that we have found e without knowing P and G. In other words we have broken the discrete log problem.Since we assume discrete log is hard, we can say e is assumed to be known by the one who came up with u and v.

34/ We further have a signature hash denoted by z, this hash is a function that returns the fingerprint of the message.
We have u = z/s and v=r/s

Put u = z/s and v=r/s in the claimed equation and solving for s we get:

s = (z + re)/k
This is the basis of signature algorithm.

35/ To verify we are given -
1. (r,s) as the signature, z as the hash of the thing being signed, and P as the public key of the signer.
2. We calculate u = z/s, v = r/s.
3. We calculate uG + vP = R.
If R’s x coordinate equals r, the signature is valid.

A simple depiction:

Reference Book:

Programming Bitcoin by Jimmy Song

@threadreaderapp unroll please