andrewdroll.com

Life in a Bitcoin mine

Yesterday's blog contained an overview of a recent crisis in the Bitcoin world having to do with a single organization achieving a majority of the currency's transaction processing power. Today I want to talk more about mining, and how it actually works at a fundamental level in the Bitcoin protocol.

I originally intended also to address what sorts of attacks on the Bitcoin network are possible by organizations possessing large shares of mining power in this blog. However, I will defer this discussion until my next blog entry - today's blog is already ballooning beyond my original expectations!

I have started investigating the fundamental implementation level of the protocols, but that topic will still mostly be avoided in this entry. Explaining the higher-level theoretical model for the implementation, and the reasoning behind it, seems like a better first step in a blogging setting. The discussion will gradually be shifting towards the more technical side of things, though.

Since this blog is quite long, here are a few quick links to help navigate:

Competitive mining

Hash functions and proof-of-work

Final remarks

What is mining, exactly?

If you have been reading my blogs so far, you probably have a good idea of the answer to this question from a qualitative perspective. Much of this entry will attempt to explore the topic in increasing detail.

Bitcoin is a distributed, open-source currency. To maintain security and complete transparency, part of Bitcoin's strategy is to mirror its entire transaction history on every Bitcoin node across the planet, in a gigantic database called the block chain. I have not yet discussed the precise mechanics of transactions in this blog, and I will continue deferring discussion of their precise nature. Simply assume for now that there are many (maybe approximately 1000 per hour) Bitcoin transactions happening across the planet, and that generally (outside network disruptions, Denial of Service attacks, or intentional filtering) every Bitcoin node receives news of every new transaction that happens. The information that goes along with each transaction includes what Bitcoin addresses are involved (sender and receiver) and how much money was transferred, and each node tracks the time that they receive the transaction information. Transactions are also digital signed using a standard cryptographic scheme (ECDSA) to ensure authenticity, and each transaction may be uniquely identified by a cryptographic hash value calculated before transmission. In fact, each transaction points to the histories of the funds involved - one may track the transaction history through the entire block chain if desired, and eventually figure out how the coins originated and the entire history of ownership, in the form of Bitcoin addresses. Note that Bitcoin addresses do not provide any explicit way to identify the receiver or sender in the real world.

Mining, then, is the process of recording these transaction details in the block chain. The mining process involves construction of new blocks, in a carefully specified format, to be appended to the chain. As I have mentioned previously, the Bitcoin protocol is designed such that block generation is expected to occur at an average rate of one block per 10 minutes (across the entire world). Thus transactions each take, typically, around 10 minutes to be recorded in a valid block and added to the chain. Mining is also the only process by which new Bitcoins are generated. Each time a new block is validated and added to the chain, the owner of the computer relaying the block to the network is awarded a fixed number of Bitcoins (currently, 25 per block). This reward per block is designed to decrease by half for every 210,000 blocks completed (or approximately every 4 years). Bitcoin creation is then viewed as compensation to miners for services rendered in maintaining the entire Bitcoin network.

The last paragraph described mining in a broad sense. In fact, I ignored perhaps its most important practical feature, called proof-of-work, which makes it a artificially computationally-intensive and competitive activity by design. Proof-of-work is also the main mechanism by which mining helps to secure the Bitcoin network. One of my aims in this blog is to detail the mining process, and the mechanics of proof-of-work, more thoroughly.

Competitive mining

A few of the things I've said about mining may seem contradictory, so far. First of all, I said that typically there are in the realm of 1000 or so Bitcoin transactions per hour. I also said that mining constitutes recording these transactions into blocks, and adding them to the block chain. Processing 1000 transactions into a data block is an essentially instantaneous process for modern computers. In this case, how is it that valid blocks are only created every 10 minutes on average? How is it that creating a block can reward Bitcoins without flooding the market with ridiculous amounts of currency? In other words, how is the money supply controlled? And lastly, how is it that mining helps ensure the security and distributed nature of the system?

The answer to all of these questions comes from mining's built-in proof-of-work mechanism. Combined with the fact that successful proofs-of-work reward Bitcoins (which are currency), this ingenious scheme is also responsible for mining's competitive nature.

Let us assume that a block has just been added to the block chain. While all of the world's miners were working on this block, a new set of transactions had been piling up, which will all go into the next block. The completion of the last block is broadcasted across the world to every Bitcoin node, and added to every mirrored block chain - and whoever completed the block is rewarded with Bitcoins for their effort.

What happens now? Well, every miner also sees the completion of the last block. And so they start working on the next one. This begins very quickly - by compiling all of the collective information from the transactions that have happened since the previous block into a unified data format, adding a header, creating a unique cryptographic hash of the contents (a very fast operation) to use as an identifier, and adding a pointer to the previous block (in the form of its unique cryptographic hash) to maintain chronological continuity of the block chain.

All of these steps happen in a fraction of a second.

So shouldn't creating a block happen nearly instantaneously? The competition for Bitcoins would then constitute a competition for latency talking to the rest of the network. There would be numerous solutions all declared nearly simultaneously. Each miner would reach some nodes first. Moreover, it would be very easy for a miner to introduce fraudulent data to contaminate part of the network and cause a malicious fork - that is, part of the network would start interpreting an incorrect block chain as the correct one. This could allow double-spending or blocking transactions in a significant proportion of block chain mirrors, and the problem might never be resolved since latency is relatively fixed. Multiple miners would be credited with new Bitcoins.

Since Bitcoin is a functional protocol, we can conclude that there must be the story. Enter the concept of a proof-of-work.

Cryptographic Hash Functions

Before we can talk about proof-of-work per se, we need to solidify an important notion. I have mentioned cryptographic hashes several times, but I've never specified what that term means, and it's the key one to understanding the competitive nature of Bitcoin mining. I will assume some basic mathematical knowledge in the theory of functions.

A mathematical function, for our purposes, is a rule - we'll call it \(F\) - which, when given any input number \(x\), returns a unique output number \(y\). Note that unique here refers to the fact that a given input \(x\) always results in the same output \(y\). It does not mean to imply that \(x\) is necessarily the only input that returns \(y\) when fed to the function \(F\).

A cryptographic hash function is a special type of mathematical function. For simplicity we will define the properties of an ideal cryptographic hash function - in practical contexts, cryptographic hashes not ideal, but they are close enough to ideal that they can be made resistant to current practical attacks. If \(H\) is a hash function, and we have \(H(x) = y\), then we will usually refer to \(x\) as the "message" and \(y\) as the "hash" of \(x\). The properties of an ideal cryptographic hash function, which we'll call \(H\) for now, are the following:

  1. It should be relatively easy to calculated the hash of a message. In other words, given a message \(x\), it there should be a fast algorithm to calculate \(H(x)\).
  2. Message security: Given any number \(y\), there is no fast algorithm which will find an input \(x\) such that \(H(x) = y\). In other words, knowing the hash of a message does not provide any easy way of discovering the message itself.
  3. Near-uniqueness: There is no fast algorithm to find two messages \(x\) which result in the same hash \(y\). In other words, it is very hard to find a situation where \(H(x_1) = H(x_2)\) where \(x_1\) and \(x_2\) are not the same number.
  4. Similarly, given a message \(x_1\), there is no fast algorithm that will find a second message \(x_2\) such that \(H(x_1) = H(x_2)\). In other words, knowing one message should not allow you to easily find another message with the same hash.
  5. Even stronger, there should be no fast algorithm which uses the hash of one message to find the hash of another. Hashes should differ substantially and unpredictably, even for very similar messages.


The first property listed has leeway. There are times at which it may be desirable for a hash function to be slower to compute, or where it may be desirable to have fine control over the calculation of hashes. This fact will warrant further discussion at a future point in my blog series.

Hashes are used in practice as unique identifiers for data which cannot be used to reproduce the data itself. If you've been paying attention carefully, you will notice that I've already mentioned this purpose today. However, they also have many more applications. We'll see one of those in the next section. For more information on hash functions, the wikipedia page is a good start.

As I mentioned above, there is no cryptographic hash function which can be proved to be ideal in the real world. This is why I left the precise meaning of "there is no fast algorithm" undefined - it is possible to give rigorous definitions mathematically, but in practice, it means that no known algorithm can break the hash function in a realistic period of time running on current hardware.

Bitcoin uses a cryptographic hash function called SHA-256, developed by the NSA. I will leave SHA-256's mathematical and implementation details to a future blog. What is important to know for now is that given any message (or input string), the SHA-256 hash function returns a 64-character hexadecimal hash. For example, the Bitcoin SHA-256 hash of the plaintext message "this is a test" is:

2e99758548972a8e8822ad47fa1017ff72f06f3ff6a016851f45c398732bc50c

Changing the message slightly - say, to "this is a tent" - results in a totally different and unrelated hash:

16899895599448ba21a6899010138c94198dfd7cb030388b57af931169bacf5c

SHA-256's output of 64-character hexadecimal hashes have \(16^{64} = 2^{256} \approx 1.15 \times 10^{77}\) possible hash values. This puts the number of possible SHA-256 hash outputs within a few orders of magnitude of the number of atoms in the observable universe. It is unlikely that SHA-256 resembles a true ideal cryptographic hash function, but in practice it acts very much like one.

For the inquisitive reader, the entire SHA family of standards is officially defined in FIPS 180-4, published by the United States' National Institute of Science and Technology.

Proof-of-work

Proofs-of-work are an extra step artificially added to block creation to force mining to be competitive, to roughly fix the time it takes between the creation of each successive block, and to control the supply of new Bitcoins.

We have already seen that compiling all of the relevant transaction information into a new block, and every other piece of information relevant to block chain continuity, takes only a moment for today's computers. To slow things down, the proof-of-work scheme requires miners to solve a complicated (and here, complicated means "requiring specialized computer hardware to solve," at this point in Bitcoin's existence) mathematical puzzle in order to have a block accepted by the rest of the Bitcoin network.

It works like this: Once all of the transaction information in a block has been assembled, a SHA-256 hash is generated to identify the block. It certainly would be possible to take a hash of the entire block as its identifier, but in the Bitcoin protocol only the block's header is hashed. We will not worry about the specific structure of block headers here; simply take them to be prefaces which are unique to each block, and include important information about the block, but do not include transaction details themselves.

So, now all of the useful information is compiled into the block, and the block has a header and a SHA-256 hash. The miner has one more job before the network will validate the block and add it to the block chain: He has to solve a puzzle.

What type of puzzle, you may ask?

The miner has the hash of the block's header already put together. Let's call the block's hash \(M\). We're picking \(M\) here because we will end up using the hash as part of a new message to be input into the SHA-256 function.

Given any other message - we'll call it \(N\) - we can imagine constructing a new message by appending \(N\) after \(M\), a logical operation called concatenation. We'll denote the concatenated message by \(M|N\); in this construction, \(N\) is simply added as a suffix to the block hash \(M\). We can calculate the SHA-256 hash of this new message \(M|N\), if we desire, to obtain the 64-character hexadecimal hash for the concatenated message. The appended message \(N\), in the language of computer science, is called a "nonce."

The proof-of-work puzzle is the following: Given some number \(B\), smaller than \(16^{64}\), find a nonce \(N\) such that the hash of \(M|N\) is no greater than \(B\).

If \(\text{SHA}\) is the SHA-256 hash function, then the proof-of-work puzzle can be restated in the following way for any given block: Given the block header's hash, \(M\), and an upper bound \(B\), find a nonce \(N\) such that

\begin{equation}\text{SHA}(M|N) \leq B.\nonumber\end{equation}

Solving this puzzle requires calculating the hash \(\text{SHA}(M|N)\) for many values of the nonce \(N\). The bound \(B\) determines how many attempts are required on average to solve the proof-of-work puzzle; smaller values of \(B\) mean it will be harder to find a nonce \(N\) satisfying the inequality above. In practice, billions of calculations of SHA-256 hashes, for different nonces, may be required to solve a proof-of-work puzzle for a single block. This is no easy computational task. In fact, the computational difficulty is precisely the point of the construction.

Remark that the time to finish any particular puzzle is random. It may be that the first nonce that you attempt gives you a valid solution. It may be that you end up having to do trillions of calculations, when only billions are expected. The bound \(B\) determines the average time to complete the puzzle, but any given instance of the puzzle may be solved almost instantaneously, or alternately, may take much longer than expected to solve.

Once a miner finds a solution to the proof-of-work puzzle for a given block, how does he proceed? He appends both the nonce and the solution hash to the block, and broadcasts the block to the Bitcoin network. Appending the nonce means that every node on the network can check his solution for correctness: They have the block hash, the nonce, the bound \(B\), and the claimed solution. Thus they can run SHA-256 on the concatenation of the block hash and the nonce and make sure that they arrive at the claimed solution, and that the solution satisfies the proof-of-work puzzle. When a node performs this check sucessfully, the block is finally added to the node's block chain as the newest entry in Bitcoin's historical transaction record.

There's an implicit question here that I've ignored, and it's a big one: How does the Bitcoin protocol determine the bound \(B\) to enforce in proof-of-work puzzles? The answer to this question also explains how an average of one block per 10 minutes is maintained worldwide.

Indeed, the protocol's intent is to maintain this 10 minute average interval per new block added to the chain. It achieves this in the following way: Each block is given a timestamp by the miner who completes it, before it is broadcasted and added to the block chain. Every 2016 completed blocks (at 10 minutes per block, this is approximately 2 weeks), each Bitcoin client checks the timestamp for the first of these 2016 blocks and for the last of these 2016 blocks. Call these timestamps \(T_{i}\) and \(T_f\), for the initial and finishing times respectively.

The true average completion time per block, which we will denote by \(\Delta_T\), is then calculated:

\begin{equation} \Delta_T = \frac{T_f - T_i}{2016}\nonumber\end{equation}

If \(\Delta_T\) is greater than 600 seconds, then over the last 2016-block period, proofs-of-work took longer than 10 minutes on average to be finished. If \(\Delta_T\) is less than 600 seconds, then over the same period, proofs-of-work took less than 10 minutes on average to be finished.

How far \(\Delta_T\) is from the expected average time of 600 seconds is a strong measure of how much the total hashing power in the world, devoted to Bitcoin proofs-of-work, has changed over the course of the previous 2016 blocks in the block chain. This measure allows the bound \(B\) used by proof-of-work puzzles worldwide to be increased or decreased according to the change in computing power. Given an initial bound of \(B_i\), the new bound \(B_f\), which will adjust the difficulty of proof-of-work puzzles back to a completion time of 10 minutes on average, may be calculated as follows:

\begin{equation}B_f = \frac{B_i\Delta_T}{600 \ \text{seconds}}\nonumber\end{equation}

Every 2016 blocks, the bound used for proof-of-work puzzles in Bitcoin mining worldwide is updated according to this calculation. Here the choice of 2016 block update intervals is arbitrary, except in that it corresponds to roughly two-week intervals in real time. Any interval sufficiently long for average properties to dominate would suffice for the protocol's purposes.

Remark that one may also calculate the average number of nonces tested per second worldwide over the course of the previous 2016 blocks:

\begin{equation}\text{nonces per second} = \frac{2^{256}}{B_i\Delta_T}\end{equation}

As such, it is possible for any observer to monitor exactly how much computing power is being devoted to Bitcoin mining over any such period. Data from blockchain.info indicates that at the present time, the global rate is approximately \(10^{17}\) nonce tests per second (or 100 quadrillion tests per second). At 10 minutes per block on average, this puts the bound \(B\) at approximately \(2 \times 10^{57}\). The correctness of this calculation can be observed in recent blockchain.info data - for example, the last validated block submitted (height 306947) had a proof-of-work solution hash of

00000000000000002b1f6cb76687b390dfcc42cc3b7e093225b080e2221b57f2

which translates to approximately \( 1.05 \times 10^{57}\) in decimal, within a factor of 2 from our calculated value for \(B\).


A few caveats

Given many miners in the world, how is it that the one with the most computing power does not automatically dominate the completion of blocks? If everyone were to start testing nonces \(N\) at \(N=0\), and just increment upward, for example, the miner with the fastest processor would always solve the proof-of-work puzzle first. This remains true if all the miners use the same algorithm to choose nonces, regardless of what that algorithm is. Even if their algorithms are only somewhat related, it may remain true.

In fact, this problem is resolved by choosing the nonces themselves by a strong pseudo-random method, unique to each miner. Another hash function with a non-deterministic input may be used for this purpose, for example. I have not yet examined the details of this implementation in Bitcoin's code itself. However, this is an important factor to keep in mind, as it also must significantly increase the complexity of solving proof-of-work puzzles.

Given truly random independently selected sequences of nonces for each miner, who wins the race to complete the proof-of-work puzzle is a simple proportional affair. If you have 30% of the global mining power, you will win the race 30% of the time on average. If you have 1% of the global mining power, you will win 1% of blocks on average. If you have 70% of the power, you will win 70% of blocks - presuming you do not abuse other aspects of Bitcoin's protocol (yet to be discussed in detail) in order to achieve an easy monopoly.

Finally, I will note that Bitcoin actually uses two iterations of SHA-256 for most of its hashing functions. This is for security purposes. Additional iterations of hash functions make them even harder to break. Even if you can attack the hash to find the message once, it will just be another hash. You will have to break it again to recover the original message. In practice, there are no feasible attacks on SHA-256 hashes of the type used by Bitcoin at the present time. The double iteration used by Bitcoin is essentially a future-proofing feature.

What does it all mean?

Now that we have examined some details of Bitcoin's mining protocol, it seems like a good time to step back and ask: What do all of these details of mining's protocol design actually mean? The answer recalls to an idea we have already alluded to: Mining as a competitive activity.

As we have seen, extraordinary computational power is required to effectively compute solutions to Bitcoin block proofs-of-work. Without doing these calculations it is impossible to complete blocks, and thus impossible to earn any newly created Bitcoins. Moreover, in an ideal world, the proportion of blocks that a miner completes, and thus the proportion of new Bitcoins that the miner earns, will be equal to the proportion of global hashing power the miner has devoted to Bitcoin.

Companies, organizations, and pools of users have, over the last few years, been developing and acquiring optimized hardware for SHA-256 hash calculations with the aim of profiting from Bitcoin mining. At this point it is effectively impossible to earn any Bitcoins from mining unless you invest in this hardware. If you want Bitcoins, and do not have a lot of disposable cash to spend on specialized hardware, you will need to either trade for them or buy them with traditional currency from someone willing to sell. This is not a problem for the Bitcoin market, per se. If you want Japanese Yen, you also have to exchange your native currency at a brick-and-mortar bank. This is essentially the same as buying Bitcoins from an online exchange or from another individual.

However, in a different sense, the highly specialized hardware required for mining may present a problem for the Bitcoin network. Bitcoin's design calls for a highly-distributed mining community, in order to ensure that no one organization can establish control over the creation of many consecutive blocks. The reason is that an organization that can produce blocks fast enough to surpass the rest of the mining network combined would have the power to manipulate their contents and still maintain control over the global block chain. This situation could easily be abused for malicious purposes.

A highly-distributed mining network solves the problem, and this was part of the original vision for the Bitcoin protocol. However, the recent arrival of >51% mining entities indicates that there may be a serious problem with this vision. Changes to the protocol itself - probably to the ways in which it incentivises mining - may be required in order to address this situation and restore this aspect of its vision and security.

***

I'm going to leave today's blog at this. Next time: Majority miners, types of attacks on the block chain, and more!