Ch12: Bitcoin calculations

The BSV Academy’s free introduction to Bitcoin Theory course covers the design of Bitcoin as a system as prescribed by Satoshi Nakamoto. This course is open to anyone who is interested in Bitcoin and is the beginner course in this series. Some technical experience would be helpful to complete the course, however, it is open to anyone regardless of experience.

The course goes through the Bitcoin white paper section by section elaborating on the concepts contained within each. This section focuses on reclaiming disk space. When the latest transaction in a coin is buried under enough blocks, the spent transactions before it can be discarded to save disk space.

To make it as effortless as possible for you to have access to this educational material, we are publishing the entire course here on our blog. Stay tuned for a section-by-section release, and remember that you are still welcome to enrol in the BSV Academy to gain a certificate of completion to add to your resume.

Attacking the Bitcoin blockchain

We consider the scenario of an attacker trying to generate an alternate chain faster than the honest chain.

- Satoshi Nakamoto, Bitcoin white paper

In this section we will look at the mathematics and practicality of executing a so-called 51% attack on the network. This takes place when a dishonest attacker creates an alternate chain which may contain transactions that misallocate funds or reject other valid actions accepted by the majority consensus.

Things a Bitcoin attacker cannot achieve...

Even if this is accomplished, it does not throw the system open to arbitrary changes, such as creating value out of thin air or taking money that never belonged to the attacker. Nodes are not going to accept an invalid transaction as payment, and honest nodes will never accept a block containing them.

- Satoshi Nakamoto, Bitcoin white paper

This is one of the most important things to understand in this scenario. An attacker trying to make arbitrary changes to the network consensus rules, to create money that doesn’t exist or to spend funds in a way that doesn’t conform to the Bitcoin Protocol cannot attack Bitcoin in this way. This is because the blocks they create would be rejected by all nodes, forcing the attacker to maintain a fork of the network which essentially duplicates the entire block chain database and creates a separate network in which only nodes who agree with their version of consensus can participate.

Learn more about Bitcoin Protocol Rules here.

The only thing a Bitcoin attacker can achieve...

An attacker can only try to change one of his own transactions to take back money he recently spent.

- Satoshi Nakamoto, Bitcoin white paper

In this statement is the whole truth of a 51% attack, which is that an attacker is completely unable to make any permanent changes to consensus rules without creating and managing a completely separate consensus network, and that the only thing that can be achieved is that they would send money to a receiver, and then perform a 51% attack to have the original transaction removed from the network and replaced with another that spends funds into a script they control.

The attacker must do this in a completely public way so that all users of the network can see which transaction was double spent and identify the node which executed the attack.

The Binomial Random Walk

The race between the honest chain and an attacker chain can be characterized as a Binomial Random Walk. The success event is the honest chain being extended by one block, increasing its lead by +1, and the failure event is the attacker's chain being extended by one block, reducing the gap by -1.

- Satoshi Nakamoto, Bitcoin white paper

To analyse the outcome of such an attack, we can characterise the status of the two chain tips as a pair of competing processes, where each vie for leadership. Our gap is characterised as the number of blocks lead that the honest chain tip has and is increased by 1 every time an honest block is found, while being decreased by 1 every time a dishonest block is found.

The block discovery process is a pseudorandom function thanks to proof-of-work, so both honest and dishonest nodes are bound to the probabilities inherent in the proof-of-work process, requiring either party to perform a full network proof-of-work in order to extend or reduce the gap.

The Gambler's Ruin

The probability of an attacker catching up from a given deficit is analogous to a Gambler's Ruin problem. Suppose a gambler with unlimited credit starts at a deficit and plays potentially an infinite number of trials to try to reach breakeven. We can calculate the probability he ever reaches breakeven, or that an attacker ever catches up with the honest chain, as follows [8]:

p = probability an honest node finds the next block

q = probability the attacker finds the next block

qz = probability the attacker will ever catch up from z blocks behind

qz =     {   1     if p≤q }

{ (q/p)z    if p>q }

- Satoshi Nakamoto, Bitcoin white paper

Because of the pseudo-random processes involved, we can see that the probability of an attacker regaining the lead is very strongly related to their own ability to perform proof-of-work. In a situation where they can perform proof-of-work equal to or greater than the rest of the network, there is a 100% chance they will eventually have the leading chaintip, however if their capability is less than the network, the chance of them ever catching up goes down with the square of the gap between the two chaintips, leading them to an ever increasing deficit against the rest of the network.

Exponential odds

Given our assumption that p > q, the probability drops exponentially as the number of blocks the attacker has to catch up with increases. With the odds against him, if he doesn't make a lucky lunge forward early on, his chances become vanishingly small as he falls further behind.

- Satoshi Nakamoto, Bitcoin white paper

It is clear from this equation that as the attacker falls further and further behind, the chances of them ever catching the honest chaintip become much smaller as the honest tip is extended, making it exceptionally unlikely for an attacker with less capacity than the rest of the network to ever catch up.

The alternative is for the attacker to increase their hashing capacity to be equal to or greater than the rest of the network for the amount of time needed to catch and overtake the honest chaintip, however this assumes that the dishonest attacker has access to the necessary machinery to add that capacity to their own resources. Hashing machinery is highly application specific and requires a large investment to install and operate, making it unlikely that an attacker simply has the excess capacity available to them at any given moment.

Waiting for confirmation...

We now consider how long the recipient of a new transaction needs to wait before being sufficiently certain the sender can't change the transaction. We assume the sender is an attacker who wants to make the recipient believe he paid him for a while, then switch it to pay back to himself after some time has passed. The receiver will be alerted when that happens, but the sender hopes it will be too late.

- Satoshi Nakamoto, Bitcoin white paper

To explore the probability of a receiver being defrauded, we look at the length of time it takes for both their transaction to be broadcast on the network, added to a block and built upon.

When a transaction is sent to the network, the rapid propagation that happens across the consensus network means that it is seen by almost all nodes within a couple of seconds.

This attack assumes that the malicious party is going to subsequently mine enough blocks to override the network’s original consensus on his own. To do this the attacker has to recruit a significant part of the network’s hashpower and direct them to hash against the alternative chain. Not only is this attack hugely expensive to execute, the problem for the attacker is that the consensus network can see that the blocks being introduced in the alternative chain have the double spend in them. This can lead to legally problematic outcomes for the node operator involved, especially if the double spend is fraudulent in nature.

Attack via proof-of-work

The receiver generates a new key pair and gives the public key to the sender shortly before signing. This prevents the sender from preparing a chain of blocks ahead of time by working on it continuously until he is lucky enough to get far enough ahead, then executing the transaction at that moment. Once the transaction is sent, the dishonest sender starts working in secret on a parallel chain containing an alternate version of his transaction.

- Satoshi Nakamoto, Bitcoin white paper

In Bitcoin, typically payment details are handed out at the time of a transaction. The receiver gives the sender a Bitcoin address or script and the satoshis are transferred.

This means that the attack cannot be started any time prior to the transaction taking place.

Once the transaction has been sent, the attacker begins hashing an alternative chain that spends the same money they sent you to themselves instead. The attacker must then escape with the goods (making the attack impractical for anything that takes days to settle legally) before then releasing an alternative chain of blocks which includes their double spend and is longer than the one which the rest of the network is mining against.

Vanishing probabilities

The recipient waits until the transaction has been added to a block and z blocks have been linked after it. He doesn't know the exact amount of progress the attacker has made, but assuming the honest blocks took the average expected time per block, the attacker's potential progress will be a Poisson distribution with expected value:

To get the probability the attacker could still catch up now, we multiply the Poisson density foreach amount of progress he could have made by the probability he could catch up from that point:

Rearranging to avoid summing the infinite tail of the distribution…

Converting to C code...