[Bitcoin] Verifying Satoshi Nakamoto's original treatise with Python [Blockchain]

Introduction

I don't think anyone knows the terms ** Bitcoin ** and ** Cryptocurrency ** now. A few years ago, there was a virtual currency boom, and people who were "** billion people **" came out, which is new to my memory. Many entertainers were also out there, and there were frequent commercials on TV. I wasn't interested at all at the time, but recently I've become interested in cryptocurrencies and their underlying technology, ** blockchain **.

** Bitcoin ** was the first cryptocurrency to appear in history. When you look into the birth of Bitcoin, the name of one person emerges. That is ** Satoshi Nakamoto **. In 2009, this ** Satoshi Nakamoto's only nine-page treatise gave birth to the concept of Bitcoin and blockchain for the first time **. It's a name like Japanese, but it doesn't seem to know the actual nationality, let alone one or more people. The identity is still unknown. Here is such a historical treatise.

"Bitcoin: A Peer-to-Peer Electronic Cash System" https://bitcoin.org/bitcoin.pdf

Now that I've read this treatise, I'm impressed, so I'd like to summarize the origins of blockchain in my own way. Finally, let's visualize and verify the mathematical formulas written in the original paper with Python. For the sake of clarity, explanations that are not written in the treatise are also included here and there.

Why do you need a blockchain?

You may not usually be aware of it, but whenever we make a financial transaction with someone, there is a ** trusted third party . For example, when sending money to someone, " Bank " or " Credit Card Company **". Why do you need these? For example, in the case of paying a reliable person such as a family member, it may be possible to meet in person and hand it over. But in many cases, they are not 100% reliable. Even if you send money with a promise to return it later, there is a possibility that the other person will actually be taken away by a bad person.

Therefore, we ask a third party that everyone can trust, such as "** bank " or " card company **", to mediate the transaction. Even if you buy or sell products at ** Mercari ** or ** Yahoo Auction **, you can trade with confidence because there is a company that acts as an intermediary.

In the first place, everyone is using the Japanese yen, which is just a piece of paper, without any doubt because ** Japan and its banks have credibility . This isn't just good. For example, in the case of a credit card company, the brokerage fee is charged by a third party. In the case of the Japanese yen, the government decides all monetary policies such as " How much money do you want to print? **". We Japanese people do not have any decision-making power, so we will be swayed by government policy.

Also, ** the country may not be completely credible . For example, the currency of the country of Turkey ( Turkish lira **) has a considerable risk due to frequent wars and conflicts around it. Greece has collapsed because it couldn't return the money it borrowed, and Argentina has collapsed with foreign bonds as well.

In this way, the credibility of the country is constantly swaying, and we do not know when and what will happen. Blockchain tried to solve this with the power of technology. ** The point is that if you create a mechanism to send money safely, there will be no trustworthy third party **, which is a fairly revolutionary idea. A direct interaction without a third party is sometimes read as Peer to Peer (P2P). The title of the treatise, "Peer-to-Peer Electronic Cash System," is a system that allows the sender and recipient to directly interact with each other.

How blockchain works

When sending money from someone to someone, the blockchain uses the ** digital signature ** mechanism. To put it simply, a digital signature is a mechanism that makes it impossible to tamper with two keys, a ** public key ** and a ** private key **. The public and private keys are always generated as a set. The private key is used to encrypt the record (strictly speaking, the Hash value generated from it), and the public key is used to decrypt it. Keep your private key in a safe place, but it's okay to keep your public key public. The important thing is that ** cryptography generated with a private key can only be decrypted with a set of public keys **. Therefore, if the encrypted information can be decrypted using the public key, it is certain that the information was sent by the sender. Since this is similar to the mechanism of stamps and signatures, it is called ** electronic signature **.

Let's think concretely in the figure below. From Owner1 to Owner2 and from Owner2 to Owner3, each transaction is connected as a "Transaction". I think it's okay if you can imagine the transaction here as a remittance. The sender (Owner1) uses the private key to encrypt a value called the Hash value and sends it to the recipient (Owner2) along with the public key. The recipient decrypts the Hash value using the public key given by Owner1 and checks whether it is the same as the Hash value calculated from the data sent. If the Hash values ​​match, you know that they have not been tampered with. If the data is tampered with in the middle, the Hash value calculated from it will also change.

"** I actually sent only 10,000 yen, but I tampered with it and decided to send about 1 million yen! **"

You can prevent such things.

By the way, this digital signature mechanism itself is not a new technology, and has been used frequently for a long time. Also, according to the treatise, it is possible to protect privacy by narrowing the disclosure range of the public key.

Let's consider another example for the sake of clarity. Suppose you bought a desk on Amazon. Suppose that when the desk arrives at the house safely and is assembled, the instruction manual says something like this.

"** There are n screws and m boards as parts of this desk **"

Obviously, the number of boards and screws that are the parts of the desk that you actually received should match the instructions. If a bad person sneaks out some screws during shipping, the number of screws listed in the instructions and the ones you actually counted should be inconsistent.

How Timestamp works

The digital signature mechanism seen above cannot be tampered with, but it does not actually solve the problem of double payments. If it is a normal remittance, a trusted third party will monitor all the records and will refund you.

"There is certainly a record of payment on ◯ month ✖︎ day and ◯ month △ day. Since it is a double payment, I will refund it."

It's like that. However, as I said at the beginning, we aim to create a system that does not require a reliable third party in blockchain. Therefore, record the timestamp (in short, the time when the transaction was made) for each transaction, and record that the transaction was certainly made at that time. We also guarantee that the record is still tampered with.

The server that records this timestamp is called the timestamp server.

This timestamp is recorded along with the hash of the transaction and is chained together. Now you can see when and what kind of transaction was made.

In addition, each block is connected like a chain, which prevents the record from being tampered with later. This is because each block also refers to the Hash of the previous transaction, so if one part is tampered with, it will be inconsistent with the previous and next blocks. Therefore, if you want to tamper with one place, you have to tamper with all the blocks in a row.

These hashes and timestamps are publicly available, so if there is any fraud, someone will notice the contradiction.

The following page was very easy to understand about timetamp. https://www.ogis-ri.co.jp/otc/hiroba/technical/bitcoinpaper/part4.html

In order to record timestamps and Hashes more efficiently, this paper introduces a method using a Markle tree (in short, a binary tree). For example, when there are 4 transactions such as Tx0, Tx1, Tx2, Tx3, it is a method to record all 4 Hash and timestamp together instead of recording all of them individually. At this time, Hash0, Hash1, Hash2, and Hash3 are generated from the original four transactions. Here, by generating Hash01 from Hash0 and Hash1, Hash23 from Hash2 and Hash3, and Root Hash from Hash01 and Hash23, the four Hashes are combined into one. By grouping them into four, you will not be able to understand the context of these four transactions, but since all the contexts for each block are recorded, you can save computational resources.

Proof of work By the way, it turned out that safe trading can be realized by recording the transaction time and Hash, which is the record of the transaction, as a set by the timestamp server. So who issues the timestamp? The goal of blockchain is a world without "trustworthy third parties". We need a mechanism that does not depend on any particular person. The mechanism adopted here is Proof of work (PoW). Simply put, everyone uses CPU power to calculate the Hash value, and the person who first finds the correct Hash value can write it to the block. The first person to find a Hash value will receive Bitcoin as a reward. This is called "mining" because it is similar to the act of digging gold veins and mining gold.

So why do we need PoW? As an example, let's consider a mechanism such as "** You can vote one vote for each IP address **" like a majority vote. It looks good at first glance, but if a person who plans to tamper with the record collects a large amount of IP, the block can be rewritten. Blockchain is a mechanism in which all participants write blocks together, so the moment someone gets the power to rewrite the majority of the whole, this mechanism breaks down.

Calculation

Now let's calculate how safe this blockchain is. Suppose there is an attacker (bad guy) here. Blockchain cannot generate coins that it has never handled due to its mechanism. An attacker can only ** rewrite his transaction record **. Even if an attacker rewrites a certain block, if the hash values ​​do not match in the next block connected by a chain, the fraud will be revealed. So, in order for an attacker to cheat, they have to generate a rogue chain faster than the chain that connects from the correct node. If the node is branched, a long chain will be adopted, so it is necessary to make a chain longer than the correct chain in order to cheat. If this setting is illustrated, it looks like the following.

--p: Probability that the correct node can find the next block --q: Probability of attacker finding next block --z: Number of blocks required for an attacker to catch up

Then, the probability qz that the attacker catches up can be expressed as follows.

q_{z}=\left\{\begin{array}{cc}
1 & \text { if } p \leq q \\
(q / p)^{z} & \text { if } p>q
\end{array}\right\}

Here, the probability that an attacker will find a block should be lower than the probability that many others will find the correct block. So let's assume p> q.

Let's think concretely. For example, let's say an attacker has a 1% chance of finding the next block and a correct node has a 10% chance of finding the next block. If the block required for an attacker to catch up is 1 (z = 1),

q_{z}=\begin{array}{cc}
(0.01 / 0.1)^{1} = 0.1& 
\end{array}

It will be. The numbers given here are just examples, so they have nothing to do with the actual numbers. You can feel that the larger z is, the more difficult it is for the attacker to catch up exponentially.

This setting is called "Binomial Random Walk" in the original paper. This is because the distance of z becomes z + 1 with a certain probability and shrinks to z-1 with a certain probability, so it moves randomly in two directions.

He also describes this problem as an analogy to the Gambler's Ruin problem. For example, suppose Mr. A and Mr. B are betting. If you think about the setting such as 100,000 yen for Mr. A-> B if the front side comes out with coins, 100,000 yen for Mr. B-> Mr. A if the back side comes out, the probability that each of Mr. A and Mr. B will go bankrupt Think about it. For example, if Mr. A's funds are only 100,000 yen, Mr. A will go bankrupt when the table first appears.

In this case, there is no "bankruptcy". You just have to think about the probability that the attacker will eventually catch up with the difference in z by repeating the trial infinitely. Therefore, in this case, it can be replaced with the bankruptcy problem of a gambler who has infinite assets.

You can find a lot of explanations about this problem by google.

The important thing here is that if z = 1, the attacker may catch up with a lucky punch, but as time goes by, it becomes harder to catch up. So how long can you be relieved?

Consider the case where the transaction is over and z correct blocks are connected. Assuming that the attacker is tampering at this time, the recipient does not know exactly how many blocks have been tampered with. However, if the probability of successful tampering is q, it is roughly

\lambda = z\frac{q}{p}

You can see that the blocks are connected with about the progress. For example, if the probability that an attacker can find a block is half the probability of the correct block, it means that about z/2 blocks have been found.

Since we do not know exactly how many blocks the attacker is able to generate, we will consider the probability distribution. Since there are two choices as to whether or not it can be generated, it seems that the binomial distribution should be considered, but here we consider the Poisson distribution. Why is it Poisson distribution?

The Poisson distribution is the binomial distribution with the limit of the number of trials-> ∞ and the probability-> 0. In the case of blockchain, this assumption seems correct given that the attacker has a low probability of trying many times. So, considering the Poisson distribution with the expected value λ defined above, it can be written as follows.

P(k) = \frac{\lambda^{k} e^{-\lambda}}{k !} \begin{array}{cc}  
\end{array}

It is easy to imagine that k is the horizontal axis and λ is a parameter. This is the probability distribution of how many blocks an attacker can generate. It looks like this in terms of image.

Let's calculate the probability that the attacker will catch up in this state. If the attacker's current location is k, then z-k should be caught up, so the sum should be taken for all k in the probability distribution.

\sum_{k=0}^{\infty} \frac{\lambda^{k} e^{-\lambda}}{k !} \cdot\left\{\begin{array}{cc}
(q / p)^{(z-k)} & \text { if } k \leq z \\
1 & \text { if } k>z
\end{array}\right\}

Here, since it is a probability distribution, k> z, that is, when z correct blocks are connected, the possibility that the attacker has succeeded in generating more blocks is not 0, so it is divided into cases. When calculating with a program, it is inconvenient to have infinity, so it will be transformed. The above formula can be rewritten as follows.

\sum_{k=0}^{z} \frac{\lambda^{k} e^{-\lambda}}{k !} 
(q / p)^{(z-k)}  + \sum_{k=z}^{\infty}\frac{\lambda^{k} e^{-\lambda}}{k !} \\
= \sum_{k=0}^{z} \frac{\lambda^{k} e^{-\lambda}}{k !} 
(q / p)^{(z-k)}  + 1 - \sum_{k=0}^{z}\frac{\lambda^{k} e^{-\lambda}}{k !} \\
=1-\sum_{k=0}^{z} \frac{\lambda^{k} e^{-\lambda}}{k !}\left(1-(q / p)^{(z-k)}\right)

Visualization

Let's visualize Python and matplotlib. In the treatise, the same calculation is done using C language.

import math
import numpy as np
import matplotlib.pyplot as plt

def AttackerSuccessProbability(q, z):
  p = 1.0 - q;
  lam = z * (q / p);
  sum_k = 1.0;
  for k in range(z+1):
    poisson = math.exp(-lam);
    for i in range(1, k+1):
      poisson *= lam / i;
    sum_k -= poisson * (1 - (q/p) ** (z-k) )
  return sum_k

q1 = 0.1
q2 = 0.3
Nz = 10

# q=0.1
p_list1 = []
p_list2 = []
z_list = []

for z in range(Nz):
  P1 = AttackerSuccessProbability(q1, z)
  P2 = AttackerSuccessProbability(q2, z)
  z_list.append(z)
  p_list1.append(P1)
  p_list2.append(P2)


plt.plot(z_list, p_list1,
         color='blue', marker='o',
         markersize=5, label='q=0.1')


plt.plot(z_list, p_list2, 
         color='red', marker='o',
         markersize=5, label='q=0.3')

plt.grid()
plt.xlabel('z')
plt.ylabel('P')
plt.legend(loc='upper right')
plt.ylim([0., 1.0])
plt.tight_layout()
plt.show()

Here, we are visualizing two patterns, q = 0.1 and q = 0.3.

You can see that the more blocks are calculated from a normal node, the more difficult it is to cheat. You can also see that the more z you have, the more difficult it is to cheat.

Summary

--By using blockchain, you can create a P2P remittance mechanism that does not require "** trusted third party **". --By using the PoW mechanism, it is possible to make it difficult to falsify records.

Remarks

――After reading the treatise, I noticed that the word Bitcoin, which is also the title of the treatise, does not appear in the treatise at all **. ――What is the true meaning of putting it only in the title? ――By the way, regarding PoW, if everyone in the world starts trading with Bitcoin, the electricity bill will be high, so there seems to be a movement like having to get rid of PoW. ――The alternative is called Proof of Stake (PoS), which is a mechanism that makes it easier to generate blocks as the amount of coins held increases (it can be kind to the earth!).