Bitcoin mining – an overview

In my recent posts in this series, I have walked you in detail through two of the basic objects that make up the bitcoin blockchain – participants, represented by public / private key pairs, and transactions. Time to look at the third major ingredient – blocks.

What are blocks and why are they necessary? When the bitcoin protocol was invented in 2008 by a person (or group of persons) acting under the pseudonym Satoshi Nakamoto (see [1]), the real novelty was not the usage of a chain of transactions in order to model payments. The real novelty was the proposed solution for a major issue with a cryptocurrency that is based solely on such a chain: the problem of double spending. To understand this, suppose that Eve agrees on a deal with Alice: Eve will transfer a certain amount of bitcoin to Alice in exchange for another currency like USD. She would pick an unspent transaction output of the correct amount, create and sign a transaction and publish that transaction in the network. Alice could see and validate the transaction appearing in the network and would then transfer the USD amount to Eve.

Unfortunately, Eve could, at virtually the same time, agree on a similar deal with Bob and create another transaction transferring the same unspent output to Bob.

Now we have two transactions in the network that both claim to spend the same previously unspent transaction output. However, what if, due to some network latency, Bob and Alice detect the second transaction only after they have initiated the transfer of the USD amount? And if they detect the problem, how can they – and the entire network – agree on which of these transactions should be considered valid and which should be discarded? This is the double spend problem.

To solve this, a mechanism is needed that allows all nodes of the network to agree on an order of transactions. If we have that order, the solution to our problem is easy – the first transaction, i.e. the transaction with the lowest order wins. Satoshis proposal was to implement an ordering by what he called a timestamp service and what is now known as the blocks of the blockchain.

Essentially, blocks are groups of transactions. Nodes in a bitcoin network collect transactions that have been posted, but not yet included in a block. They then calculate hash values of these transactions and organize them into a larger data structure – the block. But similar to transactions, blocks are linked into a chain – Satoshi calls this proof-of-work chain and in fact the term blockchain does not appear at all in his paper but was introduced later. Each (full) node in the network maintains a local copy of this chain. Whenever a node creates a block, it includes the hash value of the current last block in the chain in the block data structure. It then publishes the block on the network. If other nodes pick up the block, they can verify that it is valid – in particular they can verify that none of the transactions included in the block lead to double spending with respect to any other transaction in this or earlier blocks. If this validation is successful, the block is added to the copy of the chain maintained by the server.

Blockchain

The fact that the blocks in the chain are linked makes it more difficult to alter a block (and the transactions contained in it) that is already buried below some new blocks. In fact, in order to do this, we would have to recreate all blocks between the current last block and the block that we want to alter, as the blocks contain hash values of their predecessor. In order to make sure that this is virtually undoable, every node that creates a block needs to solve a mathematical puzzle – a so called proof of work. The difficulty of this puzzle can be adjusted dynamically and is kept at a level where approximately 10 minutes of work are required to create a new block. This also makes it less likely that new blocks are created at exactly the same point in time.

In the bitcoin block chain, this proof of work is designed as follows. The block data structure contains hash values of the transactions that are part of the block and – in addition – a field called the nonce that the node creating the block can determine at will. As the nonce enters the hash value of the block, this implies that, simply by trying out different values for the nonce, a node can create blocks whose hash value has certain properties. The mathematical challenge that a node has to solve to create a block that is accepted by the network is to adjust the nonce such that the hash value of the block is zero in the first few hexadecimal digits. The number of leading digits that need to be zero is the difficulty which is adjusted over time to make sure that the block creation rate is kept at one block per ten minutes.

Thus a node that wishes to create a new block will collect transactions not yet included in a block, verify them (and will thereby avoid double spend), add them to a block along with the hash of the current last block, try out some value of the nonce, calculate the hash value, check whether its first digits are zero, try a different nonce if that is not the case and so on until a matching nonce is found. Then the block is published, verified by the other nodes and – if it passes the checks – added to the block chain as the next block. Nodes that create new blocks are called miners.

Let us now trace the full history of a sample transaction throughout this process.

FullProcess

Suppose Alice wants to transfer 50 BTC to Bob. She creates and signs a transaction according to the rules that we have seen in the previous posts. That transaction is then published in the network. A mining node picks up the transaction and assembles it – along with many other transactions – in a new block. That block is then distributed on the network. Each node on the network validates the block and adds it to the copy of the blockchain that this node maintains. Finally, Bob can listen on the network as well. As soon as Bob finds that the transaction has been added to a block and this block has been included in the network, he can be relatively sure that the transaction is valid. Bob can now be confident to be protected against double spend and use this transaction in turn as unspent output (as a rule of thumb, a transaction is considered to be confirmed if it is included in a block and at least five additional blocks have been added on top of that, i.e. after roughly one hour).

There are still a few open ends. Why, for instance, should a mining node invest CPU power in the creation of blocks? And what happens if two different blocks are mined at the same time?

Let us first start with the question of incentivation. In order to make sure that miners participate in the process, a miner is rewarded for every block that he creates. In fact, each new block contains a special transaction called a coinbase transaction. Such a transaction has no inputs, and the mining node can determine the address to which the output is credited. Thus, effectively, mining creates bitcoins, and the miner earns the newly created bitcoins.

The amount of a coinbase transaction used to be 50 BTC in the first days of the bitcoin protocol, and is halved every 210.000 blocks. At the moment, the reward is 12.5 BTC, which is the equivalent of roughly 10.000 USD at the current exchange rate. This is the incentive for the mining node to invest energy and hardware cost into the process.

Now let us see what happens if two valid blocks are mined at the same time. In this case, we create a fork of the chain.

fork.png

Suppose, for instance, that two different nodes find a solution for the mathematical puzzle at exactly the same point in time and publish two blocks that could fit into position N of the chain. Let us call these blocks N and N’. Now all the other nodes in the network have to take a decision which chain they consider to be the main chain – the chain continued with N or the chain continued with N’. There is one basic rule in this game – the longest chain wins. However, at this point in time, both chains have the same length. So some of the nodes – say roughly half of them – will opt for the first chain, the other part of the nodes will opt for the second chain. Now each mining node will continue to work on the chain that this node considers to be valid. So roughly 50% of the miners will start to work on a block which could follow block N and the other nodes will start to search for a block that could follow N’.

Now it is rather unlikely that again, both puzzles are solved at exactly the same point in time. So let us assume that the next block which is mined is based on N. This block will then be published. Now the chain based on N is longer than the chain based on N’, and all the other nodes will – according the rule that the longest chain is the winning chain – discard the chain based on N’ and continue to mine blocks based on the new chain that included N. Thus the fork is resolved and all chains agree again on one copy of the chain.

That completes our short overview of the mining process. In the next couple of posts, we will again analyze the structure of a block in detail and see whether we will eventually be able to mine and publish a block in our test network.

References

1. Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System, 2008
2. Bitcoin History: Pre-Blockchain Digital Currencies

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s