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' -

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.

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

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

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. Elliptic curve
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 -
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)

Line L3 (parallel to x-axis ) and L4 (tangent to the curve) intersect the curve at 2 points.
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.

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

• • •

Missing some Tweet in this thread? You can try to force a refresh

Keep Current with Yatharth Arora

Yatharth Arora Profile picture

Stay in touch and get notified when new unrolls are available from this author!

Read all threads

This Thread may be Removed Anytime!


Twitter may remove this content at anytime! Save it as PDF for later use!

Try unrolling a thread yourself!

how to unroll video
  1. Follow @ThreadReaderApp to mention us!

  2. From a Twitter thread mention us with a keyword "unroll"
@threadreaderapp unroll

Practice here first or read more on our help page!

More from @YatharthArora8

10 Feb
Let's Talk Money.

You don't follow the same diet plan as your Best Friend does. Similarly it is important to invest according to your needs and what works best for you.

A Thread.
1/n A common question that we hear from people when we talk about investments is
'Where is the Money To Invest?',
'We have nothing left to save',
'I have no idea where my Money goes'.
2/n We are often adviced to write down our daily expenses. Doing this results in 2 things -
1. We get bored and stop recording it in a week.
2. We are more focused on the expense sheet rather than enjoying the coffee that we ordered.
Read 58 tweets
21 Jan
The Courage To Be Disliked:

Key takeaway from Adler's theory of Individual psychology. It focuses on the approach of teleology and not aetiology.

-> Does our past matter?
NO. Our past plays no role in deciding who we are or who we want to be as a person. It is the present, your actions that define you. It doesn't matter where you are born or with what you are born, what matters is how you make use of those things.
-> But our past actions do define our future. Don't they?
Past itself has no meaning. It depends on you as an individual what meaning you choose to give it. Anyone can change at any point of their lives. What people lack is the courage to change and attain freedom
Read 40 tweets
7 Jan
Why are there only 21 Million Bitcoins?
A question that has always baffled me.

1/n Bitcoin is a decentralized currency and unlike fiat, government or central banks cannot print it.
In a centralized system, banks can create money to control the prices of goods.
2/n In a decentralized economy, there is no central authority to create more money. Bitcoin is anti inflationary. Hence as a result you never loose the value of money over time.
Read 13 tweets
17 Dec 20
Human Mind is a wonderful EXPLANATION MACHINE. It has an explanation for almost everything, even for the UNCERTAINTIES. What's worrisome is that the explanation is always impeccable. The more intellect a person has, more convincing and precise the explanation is.
1/n The Human Mind suffers from 3 ailments as it comes into contact with history called as the triplet of opacity.
1. The Illusion of Understanding: People have an explanation of everything and anything that is going on in the world which is more complex than we can imagine.
2. Retrospective Distortion: Imagine yourself in the middle of a catastrophic event. Writing the daily account of events then and there is more coherant than narrating the event 𝘢𝘧𝘵𝘦𝘳 it has happened. There are a thousand reasons behind any event.
Read 57 tweets
15 Nov 20

A long thread:
1/ No one is crazy. People make their decisions about money according to their own experiences. You can read history but cannot go through first hand experience. You can read about people loosing all their Life savings in stocks but cannot experience what they went through.
2/ John F Kennedy had a completely different experience about the Depression than the majority of the world. For him it was a fortune. We plug in all the notions & information floating around and formulate a plan and execute it because it seems to be correct at that very moment.
Read 42 tweets

Did Thread Reader help you today?

Support us! We are indie developers!

This site is made by just two indie developers on a laptop doing marketing, support and development! Read more about the story.

Become a Premium Member ($3/month or $30/year) and get exclusive features!

Become Premium

Too expensive? Make a small donation by buying us coffee ($5) or help with server cost ($10)

Donate via Paypal Become our Patreon

Thank you for your support!

Follow Us on Twitter!