Inventing Bitcoin Part 2

Understanding How Bitcoin Works

In part one of this series we worked our way up to understanding the problem Bitcoin had to solve. In this post we will explore how Bitcoin actually solved the problem.

First lets remind ourselves of the formal problem statement Bitcoin had to solve

Can you come up with a protocol to accept or reject transactions and in which order, so that you can feel confident that anyone else in the world who is running that same protocol has a personal ledger that looks the same as yours. This problem must be solved without any centralized party and the protocol must continue to work even if bad actors run malicious protocols designed to thwart the system.

Lets dive in to understanding how Bitcoin solved this problem…

Bitcoin is a peer to peer protocol with no centrally owned component. The following diagram demonstrates a non-working, naive implementation of a peer to peer based currency system.

In this diagram we see that there are five nodes in the network: Alice, Bob, Charlie, Drew and Enemy. Each of the nodes in the network keep their own personal ledger of all the transactions that have occurred. Additionally each node in the network can broadcast new transactions. When a node broadcasts a new transaction, nodes listen to that broadcast and forward that broadcast to other nodes in the network. Eventually the original broadcast will spread out throughout the whole network.

In the diagram shown above Alice broadcasted a message that she paid Bob one Bitcoin. She broadcasted this message to her two neighbor nodes, Bob and Drew, who then broadcasted this message to their neighbor nodes.

In practice there will be many concurrent transaction broadcasts in the system at once. So lets imagine what this looks like for any single node in the system

Bob is listening to transactions that are being broadcast on the network, and he is getting all these different messages. In order to build a currency on top of these broadcasted messages, there needs to be a way for all nodes to agree on which transactions are valid and in which order they occurred. If you imagine yourself as Bob, in the above diagram, this task seems extremely daunting. As Bob, how could you possibly be confident that all other nodes in the network will apply the same transactions that you are applying?

Lets demonstrate the difficulty of this task with an example —

Just suppose that Enemy wanted to exploit the system we have so far. Enemy could send a message to only Bob saying that he had paid one Bitcoin to Bob. Bob would then give Enemy some service in the real world, like cleaning Enemy’s house. Now suppose that Bob tries to give that one Bitcoin to Charlie for some other service. But suppose that Charlie did not receive the notification that Enemy paid Bob the original one Bitcoin. Charlie will not trust that Bob actually has the Bitcoin needed to pay for his service.

Enemy managed to trick Bob by broadcasting a message to only part of the network. The rest of the network still thinks that Enemy has the Bitcoin that Bob thinks he received. This is known as the double spend problem. This is the problem that Bitcoin had to overcome in order to function as a currency.

In order to understand how Bitcoin managed to solve this problem, and thereby enable all nodes to coverage on the same ordered list of transactions, we will walk through an example of how a transaction gets processed on the Bitcoin network. We will then illustrate how this protocol protects against the double spend problem.

In Bitcoin any node can broadcast a transaction. A transaction consists of a sender, receiver and an amount. All transactions are cryptographically signed with the sender’s private key. A transaction is not considered valid by any node in the network if the transaction has not been properly signed using the sender’s private key.

Any node in the Bitcoin network can listen to transactions which are being broadcasted. While it is true that any node can listen, most nodes do not listen to broadcasted transactions. The nodes which listen for broadcasted transactions are called miners. Miners are responsible for collecting an ordered list of transactions and creating a block. A block consists of a relatively small number of transactions that occurred within a specific time window. In the Bitcoin protocol the size of blocks is limited to 1MB, which means that a single block can contain roughly 4,000 transactions and blocks are produced at a rate of roughly one per every ten minutes.

In order to produce a block miner nodes listen for transactions and group those transactions together into a block. But a block is not considered valid unless it contains a valid proof of work. In order to understand what is meant by a valid proof of work, lets consider the following block

Block X
1. Alice pays Bob 1 BTC Alice
2. Charlie pays Drew 5 BTC Charlie
3. Bob pays Charlie 2 BTC Bob

This block contains a list of ordered transactions. We can apply a hash function to this block in order to produce a hash. The hash will be a binary number that looks like 01010101101010101111001011

There are two things to understand about this hash in order to understand proof of work

1. The hash can be very easily computed given a block.
2. Given a hash it is very hard to compute a block that produces that hash. In fact the best way to find a block which produces a given hash is simply to guess and check various blocks until the correct hash is found.

A proof of work is simply a number which when attached to a block causes the hash of the block to start with some number of zeros. Lets look at an example

Block X
1. Alice pays Bob 1 BTC Alice
2. Charlie pays Drew 5 BTC Charlie
3. Bob pays Charlie 2 BTC Bob
Proof of Work: 0101011101010110101

This block now includes some proof of work. In order to determine if this proof of work is valid, nodes would take a hash of the full block, including the proof of work, and verify the resulting hash starts with the required number of zeros. If the required number of zeros is five, then if the resulting hash looked like 00000101101010101111001011 then this proof of work would be considered valid.

It is called a proof of work because in order to find a valid proof of work, nodes must try a bunch of options. Computer sciences have not found any method better than simply guessing and checking options until a valid proof of work is found.

Given that guess and check is the best option we know of to find a proof of work, the speed at which a proof of work is found is directly related to the amount of resources which are searching for a valid proof of work.

A good real world example of this is the lottery. In the lottery there is some magic number that people guess. This number consists of some number of digits. The more digits in the number, the harder the number is to guess, while the fewer number of digits, the easier the number is to guess. Therefore the number of digits in the winning lottery number should be set proportionally to the number of people who are playing the lottery.

In the Bitcoin protocol the corollary of this is — the more miner nodes which are searching for proof of work solutions — the more zeros are required for a proof of work to be considered valid. If the number of required zeros is three, then it is not that hard to find a valid proof of work, but if the number of required zeros is 30, then it is very hard to find a valid proof of work.

The difficulty of proof of work is just the number of zeros that the resulting hash is required to start with in order to be considered valid. Bitcoin automatically adjusts this difficulty based on the amount of computing resources which are being used to find proof of work solutions. This difficulty is set such that no matter how many nodes are searching for proof of work solutions, it will take on average ten minutes to find a valid proof of work.

Lets summarize

• A proof of work is a number, that when attached to a block causes the hash of that block to start with some number of zeros.
• The number of zeros which are required is called the difficulty.
• The difficulty is set by the Bitcoin protocol based on the number of resources which are searching for valid proof of work solutions.
• The difficulty is set in order to ensure that on average it takes ten minutes to produce a valid proof of work no matter how many resources are dedicated towards finding the proof of work.
• Any node can quickly check that a proof of work is valid simply by hashing the full block including the proof of work. But computing a proof of work is an expensive operation that amounts to simply guessing and checking possible solutions.

So the next question we are left with is, why on earth would miners spend the effort to compute a valid proof of work? It is because they are rewarded for their efforts with Bitcoin. This reward comes in two forms

New Bitcoin: The only way new Bitcoin ever gets introduced is through mining. When a block is mined the node which mined the block is allowed to attach some special transaction to the block which indicates that some new amount of Bitcoin should be given to the miner node. The amount of new Bitcoin that is given to the miner decreases over time as a geometric series. This means that there is a fixed amount of Bitcoin which will ever exist.

Fees: When nodes in the network broadcast transactions they can optionally include a fee which is paid to the node which mines the block that the transaction is contained in. This fee is completely optional. But the higher the fee is the more motivated miners will be to include the transaction in a block. Remember that a block is limited to a few thousand transactions. If there are more transactions in a 10 minute window than can fit in a block, miners will select which transactions to include in the block, and which to disregard. The higher the fees offered by the broadcasting node — the more motivated miners will be to include the transaction.

If we put this all together our block looks like this

Block X, Mined By Michael
1. Alice pays Bob 1 BTC (0.25BTC fee to miner) Alice
2. Charlie pays Drew 5 BTC (0.1BTC fee to miner) Charlie
3. Bob pays Charlie 2 BTC Bob
4. Michael gets 4BTC for mining Block X
5. Michael gets 0.25BTC from Alice Alice
6. Michael gets 0.1BTC from Charlie Charlie
Proof of Work: 0101011101010110101

Here we see Michael found a valid proof of work and as a result got 4.35BTC, 4 of which is newly created Bitcoin and 0.35 of which is from optional fees.

Now that we understand mining and proof of work, the next reasonable question is — “Can I turn my computer into a mining computer and start making a ton of money?”

The answer is no you can’t, or more accurately, it is extremely unlikely. Finding a valid proof of work is like winning the lottery. It is simply a guessing game. This guessing game is not that hard to win if only a few nodes are searching for a valid proof of work, but it’s extremely hard to be the winning node if a lot of nodes are searching for a valid proof of work.

Across the world today there are tens of thousands of nodes which are constantly searching for a valid proof of work for new blocks. This causes the difficulty of the proof of work to be very high, and therefore makes the probably that you find a valid proof of work very low.

What makes it even harder is that you don’t have all day to find a valid proof of work. All these miner nodes are racing to find a valid proof of work. Once one of the nodes finds a valid proof of work, that node is considered the winner and all other nodes which were searching are the losers. The losing mining nodes will have expended effort searching for a solution but will get no reward for their effort. Instead the losing nodes will simply have to try again for the next block (try again on the next lottery).

Once a miner node finds a valid proof of work, that winning node broadcasts out the block, with the valid proof of work, to the rest of the network. The network can easily verify that the proof of work is valid.

Lets summarize

• Nodes all over the world are collecting broadcasted transactions into blocks. These nodes are called miners.
• For each block, miner nodes expend effort to find a valid proof of work.
• Miner nodes expend this effort because they are rewarded if they are the node which successfully mines a block.
• All miners are constantly racing with each other to be the successful miner of a block. The winner of this race gets rewarded, but all the losers will have simply wasted resources trying to search for a solution.
• Since blocks are limited in size, during heavy traffic times miner nodes can be selective as to which transactions to include in the block they produce. The higher the transaction fees offered by the payee, the more likely the miner is to accept the transaction into the created block.

We still have a problem though. The problem is there could be multiple winners at roughly the same time. Remember that a winner is any node which can find a valid proof of work for some block. Let’s suppose that miners Foo and Bar both manage to find a valid proof of work at roughly the same time and they broadcast out their winning block to other nodes in the network. How does the network know which block is actually valid?

Understanding the answer to this question requires us to introduce one final concept — the blockchain…

So far we have talked about blocks as a grouping of transactions with a valid proof of work. But in Bitcoin these blocks are actually linked together into a chain. This is where the term blockchain comes from. Lets look at an example of what this chain looks like

In this diagram we see an example of a blockchain. There are four blocks which are all linked together. In technical terms, blocks are linked together by including the id of the previous block as part of the current block. This means the hash of each block depends on the previous block. This is extremely powerful because it means that if you wanted to go back and reconstruct block 1, you would not just need a valid proof of work for block 1, but you would also need to recompute a valid proof of work for every block that comes after block 1.

There are two important observations to make about this

1. The more blocks that come after block X, the harder block X is to change.
2. Each block in the chain needs a valid proof of work, therefore, the longer a chain is the more total work has gone into producing that chain.

Now that we understand that blocks are organized into a chain, we are ready to answer the next question — what happens if there are multiple miners which win at roughly the same time? Suppose that mining nodes Foo and Bar both manage to construct a block and find a valid proof of work at roughly the same time. Both Foo and Bar will want the reward for their effort so they will broadcast their block throughout the network. Nodes in the network will now receive two blocks both of which have a valid proof of work — how do nodes know which block is actually valid?

The answer is nodes in the network will keep both of the blocks and they will consider the block which is part of the longer chain valid. Lets demonstrate what this looks like

Here we see the creation of a fork in the blockchain. We then see that nodes consider the chain with the most blocks to be the winning chain. One of these chains will ultimately win and the other chain will be abandon by miner nodes so no new blocks will be added to it.

So it’s not a problem if two nodes successfully mine a block at roughly the same time. Both of those nodes will broadcast their blocks, both blocks will be stored, eventually one block will become part of a longer chain and that block will be considered the winning block.

Lets summarize everything we have learnt so far

• A block consists of a collection of transactions.
• Miners construct blocks by working hard to find a valid proof of work.
• When miners construct a block, they broadcast that block out into the network. Miners are rewarded for constructing blocks with new bitcoin and fees.
• Blocks are linked together via keeping a record to the previous block. This creates a chain of blocks.
• The chain that is considered valid is the longest chain. Also note that the longest chain is the chain that has had the most work put into constructing it.

Given all this understanding we can now turn back to the original double spend problem. We are now in a position to understand how bitcoin solves the double spend problem.

Suppose Enemy wanted to trick Bob into thinking that he paid him one bitcoin. In order to do this Enemy would need to construct a valid proof of work for a block and broadcast it to only Bob. Note that Enemy does not have all day to construct this block, he is racing against all other miners to try to try to construct a block. But let’s suppose Enemy does manage to get lucky and win the lottery. Enemy will have constructed a block and broadcasted it to only Bob. But Enemy is not done there, Enemy needs to keep up the lie. Bob will realize that Enemy’s block was not valid as soon as it fails to become part of the longest chain. This means that in order to keep up the lie Enemy needs to keep constructing blocks and broadcasting them to Bob.

But Enemy is in for a world of pain, because Enemy will need to consistently construct blocks faster than the rest of the network combined in order to keep Bob believing his lie. There is no way Enemy would possibly be able to do this, unless Enemy held 51% of the computing resources of all miners. This is what is known as the 51% attack. In theory if a single miner did own 51% of the mining power they could reinvent the history of bitcoin blockchain and could double spend bitcoins. But in practice it is not possible for a single party to own 51% of the mining resources — that is simply too many computers.

So eventually Enemy will fail to keep up his initial lie to Bob. Bob will stop trusting the original block from Enemy.

Notice that this means that new blocks cannot really be trusted all that much. But blocks become more trustworthy as more and more blocks are added after them.

So if Bob is smart he will not clean Enemy’s house as soon as he sees a block indicating he has been paid 1BTC by Enemy, but instead will wait for a few more blocks before deciding to clean Enemy’s house. If the block which says Enemy paid Bob 1BTC is still part of the longest chain, than Bob can be pretty darn sure that the network has converged on that blockchain. This means Bob can be confident he can pay Charlie with the bitcoin he got from Enemy.

And that is it — that is how bitcoin solved the double spend problem and became a peer to peer based currency system.

Until Next Time,

Andrew