Lecture 6: Proof of Work Mining

Announcements

Reading: NBFMG, chapters 2-3
Homework 2 and Lab 2 make-ups are due on Friday at 10pm on Gradescope
Challenge problem set 1 will be released this week, and due on Friday 2/21 at 10pm on Gradescope

Learning outcomes

By the end of today’s lecture, you will learn:

The critical role that miners play to ensure agreement on the blockchain, meaning that everyone’s view is essentially the same (except for very recent events).
Three types of attacks that a malicious could perform, and how Bitcoin is designed to prevent or disincentivize them.
The importance of an “honest majority” assumption, which means that the Bitcoin participants do need to trust that enough of the miners perform their role correctly, but do not need to trust any single one of them (and therefore, any single miner is easily replaceable).

Review from last lecture

Bitcoin was invented in 2009 by an anonymous party (or parties) holding the pseudonym Satoshi Nakamato. Bitcoin is a digital currency that does not require a single, trusted banking authority to manage everybody’s transactions and bank balances. Instead, everyone on the Internet that uses the Bitcoin software collectively keeps track of how many Bitcoins each party holds at any moment in time.

There are three types of data structures to consider within Bitcoin:

A transaction is a transfer of coins from one or more senders to one or more receivers. All senders must indicate their agreement with the transfer by digitally signing the transaction.
Transactions are grouped into blocks. Each block contains a few thousand transactions (say, a few thousand). In Bitcoin, one block is created approximately every 10 minutes.
Finally, the blocks are linked together into a blockchain. Every block references the hash of the previous block in the chain (except for the first block, called the genesis block).

A blockchain is a public ledger. It is:

Public, meaning that anyone can read it at any time.
Append-only, meaning that
- Anyone can add new information at the end of the ledger, but
- Nothing that is already in the ledger can ever be erased or overwritten.

There are three types of participants within Bitcoin.

A light client only needs to hold one or more secret keys for a digital signature scheme.
A node additionally stores the entire state of the blockchain.
A miner additionally tries to write new blocks on the blockchain. (We will discuss miners in more detail today.)

5.5 Mining Attacks

Unless they steal your secret key, a malicious miner cannot directly create a new transaction to spend your money. Nevertheless, here are 3 types of attacks that a malicious miner could perform.

Censorship: The miner can refuse to post certain transactions. This would break our goal of allowing anyone to append new information to the blockchain.
Inconsistency: The miner can send different states of the blockchain to different nodes. This would break our goal that the ledger is publicly agreed-upon.
Double spending: The miner could go back in time and rewrite an earlier block. This would break our goal that the ledger is append-only.

As an example, consider the sequence of transactions Mallory \(\to\) Alice \(\to\) Carol.

If a miner deletes the Mallory \(\to\) Alice transaction, then the latter transaction becomes invalid as well because Alice no longer has any money to spend.

Even worse, if Mallory is the miner, then Mallory could post a new transaction that pays the money to another account under her own control… perhaps her friend Bob, or perhaps another account held by herself (this is called a sybil attack). In this way, Mallory could reclaim her previously-spent money to spend again in the future.

6.1 Bitcoin ensures consistency, not speed

Modern computers are incredibly fast. They can transmit, write, and overwrite data in the blink of an eye.

But in a financial system like Bitcoin, speed is not the most important goal. Instead, we want to make sure that everyone has a consistent view of the blockchain ledger that they agree upon.

Cryptocurrencies like Bitcoin have been carefully designed to ensure that censorship, inconsistency, and double spending attacks are practically infeasible to perform.

(Note: Bitcoin’s protections against these 3 attacks are actually related, but for the purposes of this class, we will treat them separately.)

Within Bitcoin, “practically infeasible” does not always mean “energy of the sun” levels of difficult. Instead, the goal is to ensure that the attacks are onerous enough to perform that:

It’s very computationally expensive to try, and
Any rational attacker Mallory is incentivized to use that computing power instead to make money as a legitimate miner.

Question. How would you design a financial payment system to protect against censorship, inconsistency, and double-spending?

One possible option is to find a single person who the whole world trusts, and ask that person to be the sole miner in the scheme.

Sadly, we do not have such fully-trusted people. If we somehow found such a person, we might ask them to run everything for us, not just the banks. In political terms, this corresponds to a (benevolent?) dictatorship.

To extend the political analogy further, over the centuries humankind has designed democratic social structures in which we:

Impose limits on the power of any single actor, even the ones who seek power, and
Use elections to decide who gets to have temporary and limited power.

These political systems are often less efficient and nimble than a dictatorship might be, but they are more stable as a result.

Cryptocurrencies abide by these principles too! Let’s see how.

6.2 Censorship Resistance via Leader Election

Let’s see how Bitcoin thwarts these attacks, one at a time. For now, let’s just assume that the miners all promise never to conduct a double-spend attack. (We’ll fix this trust issue later.)

Bitcoin includes two components to thwart censorship:

There is a connected peer-to-peer network of Bitcoin nodes that gossip or broadcast any transaction they hear. This way, any sender can get their transactions heard by any node and miner who happen to be connected to the network right now. (We will say more about broadcast protocols in future lectures. For now let’s assume that this part works perfectly.) To see how it works, take a look at the animation at time 1:48 to 2:03 in this YouTube video.

There is a randomized election system (or in other words, a lottery) to choose the next miner. It doesn’t matter (much) who wins the election; the important part is that the nodes reach consensus on who has won.

The upshot here is: each individual miner can still censor your transaction if they want. Nevertheless, as long as at least one miner is honest, then your transaction will eventually get put into a block.

This is an example of an anytrust assumption; we will see more examples later in the semester.

The miner inserts into the newly-created block their winning lottery ticket – which is formally called a nonce, because it can only be used once.

Other miners and nodes will only consider a block to be valid if it includes a winning nonce.

Block header and transactions (image source: Nakamoto whitepaper)

Just like with the earlier political analogy: we have designed a cryptocurrency that is more stable, but at the expense of speed. Whereas you might assume that an Internet-based money scheme would be fast, instead this system is purposely slow. Within Bitcoin,

A new miner is elected approximately once every 10 minutes. (More precisely, the time to the next winner is determined by a Poisson random variable.)
Each miner can create a block that is about 2 megabytes in size. Each block can hold a few thousand transactions.

In computing & data science terms: the throughput of this monetary system is low.

6.3 Consistency via Block Heights

This strategy also solves the problem of inconsistency, which was the fear that nodes might see different blockchains.

(Recall that we are assuming for the moment that miners will never go back and try to rewrite history.)

Even with this simplifying assumption in place, one concern is that two miners might win the lottery at (almost) the same time. If this happens:

They will produce different blocks, called B and B2 in the picture below. These blocks might have the same transactions or they may have different transactions. Either way, they contain different nonces, and each block creator has awarded all mining rewards and fees to themselves.
But: both blocks will point to the same previous block, called A in the picture below.

In Bitcoin terminology, this is called a fork of the blockchain.

Fork in the chain (image source: Mango Research)

We can overcome this forking issue by using the peer-to-peer network to broadcast these blocks as well. Then we can impose a rule that all honest nodes should follow:

Always choose the largest blockchain. As a tiebreaker, choose the chain that you heard first.

(Note: we will make one small tweak to this rule in a few minutes.)

In Bitcoin terminology, each block contains a counter called its block height. In the picture below, D has a block height of 3 whereas B2 has a block height of 1.

Bitcoin’s consistency rule (image source: Mango Research)

Once again, we have resolved an attack at the expense of speed. Let’s look at the above picture in the following scenario: block A already exists, and then two miners win the lottery at nearly the same time and post blocks B and B2.

Suppose also your transaction occurred in block B but not in block B2.

Since a temporary fork has occurred, you cannot yet be sure that the whole network will coalesce around the block containing your transaction.
You will need to wait a few minutes to see which block “wins” by being extended first through another randomized election. (That could potentially have its own fork, but it’s unlikely that too many of them will occur in a row.)

In computing & data science terms: the latency of any individual transaction is high.

6.4 Preventing Double Spends via Proof of Work

The final – and most insidious – attack that we have to prevent is the double spend. The threat here is that a malicious buyer Mallory does the following.

Create a block in which she gives her coins to seller Alice.
Then create a new chain that is two blocks long in which she gives her coins to seller Bob. According to the rule we imposed previously, the whole world will switch to this new chain, so Alice no longer gets paid.

We will also solve this problem by intentionally imposing friction into the cryptocurrency. Specifically, we haven’t discussed yet how miners win the election and get the right to create a new block.

Assume that there are more honest miners than dishonest miners. Our goal is to choose an election method that is fairly likely to elect an honest miner.

Here’s how it works. Every miner collects all of the transactions from the peer-to-peer network, and forms a block. Then:

The miner chooses the nonce value however it wants. (It can choose this at random, or make a counter, or anything it wants.)
It runs the SHA-256 cryptographic hash over the block contents and the nonce.
If the resulting hash digest starts with sufficiently many 0 bits, then the miner has won the election and quickly posts the result to the peer-to-peer network. Otherwise, it goes back to step #1 to try again.

Note that in each calculation of the hash function, the transactions in the block can remain the same (or they can change, if new transactions arrive and the miner wishes to add them to the block).

What’s important is that the nonce changes for each execution of the hash function. The Bitcoin miners keep calculating

\[y = \texttt{SHA-256}(\texttt{block}, \texttt{nonce})\]

for many, many different nonces. The miner wins the election if this hash digest \(y\) is a small enough number, i.e., it begins with enough 0 bits.

Currently, the Bitcoin miners collectively perform about \(817 \cdot 10^{18}\) hashes per second (as of February 6, 2025).

This corresponds to \(490 \cdot 10^{21}\) hashes every 10 minutes. The difficulty level of Bitcoin is currently set to require this many hash computations in expectation, in order to produce a winning nonce.

Bitcoin’s SHA-256 hash rate, where an “exahash” is \(10^{18}\) hashes (image source: blockchain.com)

This effort by the miners is called a proof of work. Only after performing this work can a miner post a block.

This is a lot of computational work! By means of comparison,

Your laptop’s computer processor can probably perform about 100 million hashes per second.
If you have a nice video graphics card, it might be able to perform a few billion hashes per second.

So you would need around 100 billion graphics cards to keep up with the hash rate of the entire Bitcoin network!

Note: actual Bitcoin miners do not use general-purpose computer processors and graphics cards. Instead, they use special hardware that is designed solely to perform SHA-256 as quickly and cheaply as possible.

6.5 Puzzle Friendliness

To see the proof of work property in action, let’s look at a recent block created on the Bitcoin blockchain.

# Every block references the hash of the previous block
# Fetching block 881900 that we explored last time

import requests
from binascii import unhexlify

# getting the block hash of block 881900
block_hash = requests.get('https://mempool.space/api/block-height/881900').text

# get block metadata
response = requests.get('https://mempool.space/api/block/' + block_hash)

block_hash = response.json()['previousblockhash']
print(block_hash)

000000000000000000003a28145184ad450f7a8f275dc3fd55ab14218c76a1c3

The block hash starts with a lot of 0 hex characters! (20 of them, to be precise.) This is very unlikely to occur by chance.

Let’s look at the hash digest in binary format.

print(format(int(block_hash, 16), '#0258b')[2:])

0000000000000000000000000000000000000000000000000000000000000000000000000000000000111010001010000001010001010001100001001010110101000101000011110111101010001111001001110101110111000011111111010101010110101011000101000010000110001100011101101010000111000011

This 256 bit string begins with 82 zeroes!

Question. If you choose a bitstring \(x\) at random and feed it into SHA-256, what is the probability that the resulting output begins with 82 zeroes?

We can reason about this question using the random oracle property of a hash function, which states that the output “looks random.”

If an adversary [Mallory] has not explicitly queried … on some point \(x\), then the value of \(H(x)\) is completely random… at least as far as [Mallory] is concerned.

– Jon Katz and Yehuda Lindell, Introduction to Modern Cryptography

If every bit of the hash digest “looks” uniformly random, then this question is essentially asking about the chance of flipping a coin and it landing heads 82 times in a row.

The probability of this happening is \(\frac{1}{2^{82}}\). You will need to attempt this experiment \(2^{82}\) times, in expectation, in order to find a hash digest like this one.

That is the proof of work game in action!

Additionally, each missed attempt doesn’t help the miner at all to solve the puzzle. That is: the miner learns that this particular nonce doesn’t work, but cannot use this information to solve a system of equations that will lead to a nonce that does win the lottery.

In probability terminology: the game is memoryless. As a result:

The distribution of the time to solve one proof-of-work puzzle is an exponential random variable.
The distribution of the number of solved puzzles in a particular amount of time is a Poisson random variable.

To be more precise: Bitcoin relies on the following property of a hash function called puzzle friendliness.

Definition (puzzle friendliness). If we ask the miners to find an input \(x\) whose SHA-256 hash digest \(H(x)\) begins with \(d\) zero bits in a row, then we believe there is no strategy that the miners can perform that is more effective than a guess-and-check approach. As a result, this computation is expected to take \(2^d\) time.

Puzzle friendliness is a stronger guarantee than collision resistance, but a weaker guarantee than the random oracle assumption.

We have four different assumptions that we can make about a hash function:

Preimage resistance < Collision resistance < Puzzle friendliness < Random oracle.

Cryptographers assume that the SHA-2 and SHA-3 family of hash functions satisfy all of these assumptions.

Difficulty level adjustments

Because the computational power in the world goes up over time due to Moore’s Law, the difficulty of the puzzle must adjust over time.

In Bitcoin, the difficulty changes once every 2 weeks or so.

If miners are finding blocks faster than every 10 minutes (on average), then the difficulty of finding a block increases. For example: the miners might be tasked to find hash digests that start with even more 0s.
If miners are finding blocks too slowly (on average), then the difficulty of finding a block decreases.

As a result, we need to make a small change to the rule that honest nodes follow:

Always choose the blockchain with the most cumulative difficulty.

In general, this typically corresponds to the blockchain with the tallest height.