Chapter 5: Bitcoin Mining
This chapter is all about mining. We’ve already seen quite a bit about miners and how Bitcoin relies on them — they validate every transaction, they build and store all the blocks, and they reach a consensus on which blocks to include in the block chain. We also have already seen that miners earn some reward for doing this, but we still have left many questions unanswered. Who are the miners? How did they get into this? How do they operate? What’s the business model like for miners? What impact do they have on the environment? In this chapter, we will answer all of these questions.
5.1 The task of Bitcoin miners
Do you want to get into Bitcoin mining? If you do, we’re not going to completely discourage you, but beware that Bitcoin mining bears many similarities to gold rushes. Historical gold rushes are full of stories of young people rushing off to find fortune and inevitably many of them lose everything they have. A few strike it rich, but even those that do generally endure lots of hardship along the way. We’ll see in this section why Bitcoin mining shares many of the same challenges and risks as traditional gold rushes and other get‐rich‐quick schemes.
Copyright By PowCoder代写 加微信 powcoder
But first, let’s look at the technical details. To be a Bitcoin miner, you have to join the Bitcoin network and connect to other nodes. Once you’re connected, there are six tasks to perform:
1. Listenfortransactions.First,youlistenfortransactionsonthenetworkandvalidatethemby checking that signatures are correct and that the outputs being spent haven’t been spent before.
2. Maintain block chain and listen for new blocks.You must maintain the block chain. You start by asking other nodes to give you all of the historical blocks that are already part of the block chain before you joined the network. You then listen for new blocks that are being broadcast to the network. You must validate each block that you receive — by validating each transaction in the block and checking that the block contains a valid nonce. We’ll return to the details of nonce checking later in this section.
3. Assemble a candidate block.Once you have an up‐to‐date copy of the block chain, you can begin building your own blocks. To do this, you group transactions that you heard about into a new block that extends the latest block you know about. You must make sure that each transaction included in your block is valid.
4. Find a nonce that makes your block valid.This step requires the most work and it’s where all the real difficulty happens for miners. We will see this in detail shortly.
5. Hope your block is accepted.Even if you find a block, there’s no guarantee that your block will become part of the consensus chain. There’s bit of luck here; you have to hope that other miners accept your block and start mining on top of it, instead of some competitor’s block.
6. Profit.If all other miners do accept your block, then you profit! At the time of this writing in early 2015, the block reward is 25 bitcoins which is currently worth over $6,000. In addition, if
any of the transactions in the block contained transaction fees, the miner collects those too. So far transaction fees have been a modest source of additional income, only about 1% of block rewards.
We can classify the steps that a miner must take into two categories. Some tasks — validating transactions and blocks — help the Bitcoin network and are fundamental to its existence. These tasks are the reason that the Bitcoin protocol requires miners in the first place. Other tasks — the race to find blocks and profit —‐ aren’t necessary for the Bitcoin network itself but are intended to incentivize miners to perform the essential steps. Of course, both of these are necessary for Bitcoin to function as a currency, since miners need an incentive to perform the critical steps.
Finding a valid block.Let’s return to the question of finding a nonce that makes your block valid. In Chapter 3 we saw that there are two main hash‐based structures. There’s the block chain where each block header points to the previous block header in the chain, and then within each block there’s a Merkle tree of all of the transactions included in that block.
The first thing that you do as a miner is to compile a set of valid transactions that you have from your pending transaction pool into a Merkle tree. Of course, you may choose how many transactions to include up to the limit on the total size of the block. You then create a block with a header that points to the previous block. In the block header, there’s a 32 bit nonce field, and you keep trying different nonces looking for one that causes the block’s hash to be under the target — roughly, to begin with the required number of zeros. A miner may begin with a nonce of 0 and successively increment it by one in search of a nonce that makes the block valid. See Figure 5.1.
Figure 5.1: Finding a valid block. In this example, the miner tries a nonce of all 0s. It does not produce a valid hash output, so the miner would then proceed to try a different nonce.
In most cases you’ll try every single possible 32‐bit value for the nonce and none of them will produce a valid hash. At this point you’re going to have to make further changes. Notice in Figure 5.1 that there’s an additional nonce in the coinbase transaction that you can change as well. After you’ve exhausted all possible nonces for the block header, you’ll change the extra nonce in the coinbase transaction — say by incrementing it by one — and then you’ll start searching nonces in the block header once again.
When you change the nonce parameter in the coinbase transaction, the entire Merkle tree of
transactions has to change (See Figure 5.2). Since the change of the coinbase nonce will propagate all
the way up the tree, changing the extra nonce in the coinbase transaction is much more expensive
operation than changing the nonce in the block header. For this reason, miners spend most of their
time changing the nonce in the block header and only change the coinbase nonce when they have 32
exhausted all of the 2possible nonces in the block header without finding a valid block.
Figure 5.2: Changing a nonce in the coinbase transaction propagates all the way up the Merkle tree.
The vast, vast majority of nonces that you try aren’t going to work, but if you stay at it long enough you’ll eventually find the right combination of the extra nonce in the coinbase transaction and the nonce in the block header that produce a block with a hash under the target. When you find this, you want to announce it as quickly as you can and hope that you can profit from it.
Is everyone solving the same puzzle? You may be wondering: if every miner just increments the nonces as we described, aren’t all miners solving the exact same puzzle? Won’t the fastest miner always win? The answer is no! Firstly, it’s unlikely that miners will be working on the exact same block as each miner will likely include a somewhat different set of transactions and in a different order. But more importantly, even if two different miners were working on a block with identical transactions, the blocks would still differ. Recall that in the coinbase transaction, miners specify their own address as the owner of the newly minted coins. This address by itself will cause changes which propagate up to the root of the Merkle tree, ensuring that no two miners are working on exactly the same puzzle unless they share a public key. This would only happen if the two miners are part of the same mining pool (which we’ll discuss shortly), in which case they’ll communicate to ensure they include a distinct nonce in the coinbase transaction to avoid duplicating work.
Difficulty.Exactly how difficult is it to find a valid block? As of March 2015, the mining difficulty target (in hexadecimal) is:
0000000000000000172EC0000000000000000000000000000000000000000000
so the hash of any valid block has to be below this value. In other words only one in about 2nonces
that you try will work, which is a really huge number. One approximation is that it’s greater than the human population of Earth squared. So, if every person on Earth was themselves their own planet
67 Earth with seven billion people on it, the total number of people would be close to 2.
Determining the difficulty. The mining difficulty changes every 2016 blocks, which are found about once every 2 weeks. It is adjusted based on how efficient the miners were over the period of the previous 2016 blocks according to this formula:
next_difficulty = (previous_difficulty * 2016 * 10 minutes) / (time to mine last 2016 blocks)
Note that 2016*10 minutes is exactly two weeks, so 2016 blocks would take two weeks to mine 2016 blocks if a block were created exactly every 10 minutes. So the effect of this formula is to scale the difficulty to maintain the property that blocks should be found by the network on average about once every ten minutes. There’s nothing special about 2 weeks, but it’s a good trade‐off. If the period were much shorter, the difficulty might fluctuate due to random variations in the number of blocks found in each period. If the period were much higher, the network’s hash power might get too far out of balance with the difficulty.
Each Bitcoin miner independently computes the difficulty and will only accept blocks that meet the difficulty that they computed. Miners who are on different branches might not compute the same difficulty value, but any two miners mining on top of the same block will agree on what the difficulty should be. This allows consensus to be reached.
You can see in Figure 5.3 that over time the mining difficulty keeps increasing. It’s not necessarily a steady linear increase or an exponential increase, but it depends on activity in the market. Mining difficulty is affected by factors like how many new miners are joining, which in turn may be affected by the current exchange rate of Bitcoin. Generally, as more miners come online and mining hardware gets more efficient, blocks are found faster and the difficulty is increased so that it always takes about ten minutes to find a block.
In Figure 5.3 you can see that in the red line on the graph there’s a step function of difficulty even though the overall network hash rate is growing smoothly. The discrete step results from the fact that the difficulty is only adjusted every 2016 blocks.
Another way to view the network’s growth rate is to consider how long it takes to find a block on average. Figure 5.4 (a) shows how many seconds elapse between consecutive blocks in the block chain. You can see that this gradually goes down, jumps up and then gradually goes down again. Of course what’s happening is that every 2016 blocks the difficulty resets and the average block time goes back up to about ten minutes. Over the next period the difficulty stays unchanged, but more and more miners come online. Since the hash power has increased but the difficulty has not, blocks are found more quickly until the difficulty is again adjusted after 2016 blocks, or about two weeks.
Figure 5.3: Mining difficulty over time (mid‐2014). Note that the y‐axis begins at 80,000 TH/s.
Figure 5.4 (a) : Time to find a block (early 2014). Note that the y‐axis begins at 460 seconds. Due to continued rapid growth in mining power during this time, the time to find a block decreased steadily within each two‐week window. Source: bitcoinwisdom.com
Figure 5.4 (b) : Time to find a block (early 2015). Note that the y‐axis begins at 540 seconds. As the growth of the network has slowed, the time to find each block is much closer to 10 minutes and is occasionally over during periods where the network’s hash power actually shrinks. Source: bitcoinwisdom.com
Even though the goal was for a block to be found every ten minutes on average, for most of 2013 and 2014 it was closer to about nine minutes on average and would approach 8 minutes at the end of each two week cycle. Quick calculations show that this requires an astonishing 25% growth rate every two weeks, or several hundred fold per year.
Unsurprisingly, this was not sustainable forever and in 2015 the growth rate has been much slower (and occasionally negative). In Figure 5.4(b), we can see that as the mining power is closer to a
steady‐state, the period to find each block stays much closer to 10 minutes. It can even take longer t h a n 1 0 m i n u t e s , i n w h i c h c a s e t h e r e w i l l b e a d i f f i c u l t y de c r e a s e .O n c e c o n s i d e r e d u n t h i n k a b l e , t h i s has happened fairly regularly in 2015.
While there have been no catastrophic declines of the network’s mining power so far, there’s no inherent reason why that cannot happen. One proposed scenario for Bitcoin’s collapse is a “death spiral” in which a dropping exchange rate makes mining unprofitable for some miners, causing an exodus, in turn causing the price to drop further.
5.2 Mining Hardware
We’ve mentioned that the computation that miners have to do is very difficult. In this section, we’ll discuss why it is so computationally difficult and take a look at the hardware that miners use to perform this computation.
The core of the difficult computation miners are working on is the SHA‐256 hash function. We discussed hash functions abstractly in Chapter 1. SHA‐256 is a general purpose cryptographic hash function that’s part of a bigger family of functions that was standardized in 2001 (SHA stands for Secure Hash Algorithm). SHA‐256 was a reasonable choice as this was strongest cryptographic hash function available at the time when Bitcoin was designed. It is possible that it will become less secure over the lifetime of Bitcoin, but for now it remains secure. Its design did come from the NSA (US National Security Agency), which has led to some conspiracy theories, but it’s generally believed to be a very strong hash function.
A c l o s e r l o o k a t S H A ‐ 2 5 6 . Fi g u r e 5 . 5 s h o w s m o r e d e t a i l a b o u t w h a t a c t u a l l y g o e s o n i n a S H A ‐ 2 5 6 computation. While we don’t need to know all of the details to understand how Bitcoin works, it’s good to have a general idea of the task that miners are solving.
SHA‐256 maintains 256 bits of state. The state is split into eight 32‐bit words which makes it highly optimized for 32‐bit hardware. In each round a number of words in the state are taken — some with small bitwise tweaks applied — and added together mod 32. The entire state is then shifted over with the result of the addition becoming the new left‐most word of the state. The design is loosely inspired by simpler bitwise Linear Feedback Shift Registers (LFSRs).
Sidebar: the SHA family.The “256” in SHA‐256 comes from its 256‐bit state and output. Technically SHA‐256 is one of several closely‐related functions in the SHA‐2 family, including SHA‐512 (which has a larger state and is therefore more secure). There is also SHA‐1, an earlier generation with 160‐bit output which is now considered insecure but is still implemented in Bitcoin script.
Although the SHA‐2 family, including SHA‐256, are still considered to be cryptographically secure, the next generation SHA‐3 family has now been picked by a contest. SHA‐3 is in the final stages of standardization today, but it wasn’t available at the time Bitcoin was designed.
Figure 5.5 shows just one round of the SHA‐256 compression function. A complete computation of SHA‐256 does this for 64 iterations. During each round, there are slightly different constants applied so that no iteration is exactly the same.
Figure 5.5 : The structure of SHA‐256. This is one round of the compression function.
The task for miners is to compute this function as quickly as possible. Remember that miners are racing each other so the faster they do this, the more they earn. To do this, they need to be able to manipulate 32‐bit words, do 32‐bit modular addition and also do some bitwise logic.
As we will see shortly, Bitcoin actually requires SHA‐256 to be applied twice to a block in order to get the hash that is used by the nodes. This is a quirk of Bitcoin. The reasons for the double computation are not fully specified, but at this point, it’s just something that miners have to deal with.
CPU mining. The first generation of mining was all done on general purpose computers — that is general purpose central processing units (CPUs). In fact, CPU mining was as simple as running the code shown in Figure 5.6. That is, miners simply searched over nonces in a linear fashion, computed SHA 256 in software and checked if the result was a valid block. Also, notice in the code that as we mentioned, SHA‐256 is applied twice.
TARGET=(65535<<208)/DIFFICULTY; coinbase_nonce=0; header=makeBlockHeader(transactions,coinbase_nonce); for(header_nonce=0;header_nonce<(1<<32);header_nonce++){ if(SHA256(SHA256(makeBlock(header,header_nonce)))< TARGET) break;//blockfound! coinbase_nonce++; } Figure 5.6 : CPU mining pseudocode. How fast will this run on a general purpose computer? On a high‐end desktop PC you might expect to compute about 20 million hashes per second (MH/s). At that speed, it would take you several hundred thousand years on average at the early‐2015 difficulty level (2) to find a valid block. We weren’t kidding when we said mining was going to be a difficult slog! If you're mining on a general purpose PC today, CPU mining is no longer profitable with the current difficulty. For the last few years, anyone trying to mine on a CPU probably doesn’t understand how Bitcoin works and was probably pretty disappointed that they never made any money doing it. GPU mining. The second generation began when people started to get frustrated with how slow their CPUs were and instead used their graphics card, or graphics processing unit (GPU). Almost every modern PC has a GPU built‐in to support high performance graphics. They’re designed to have high throughput and also high parallelism, both of which are very useful for Bitcoin mining. Bitcoin mining can be parallelized easily because you can try computing multiple hashes at the same time with different nonces. In 2010, a language called OpenCL was released. OpenCL is a general purpose language to do things other than graphics on a GPU. It's a high level‐language and over time people have used it to run many types of computation more quickly on graphics cards. This paved the way for Bitcoin mining on GPUs. Mining with graphics cards had several attractive properties at the time. For one thing, they're easily available and easy for amateurs to set up. You can order graphics cards online or buy them at most big consumer electronics stores. They’re the most accessible high‐end hardware that's available to the general public. They also have some properties that make them specifically good for Bitcoin mining. They're designed for parallelism so they have many Arithmetic Logic Units (ALUs) that can be used for simultaneous SHA‐256 computations. Some GPUs also have specific instructions to do bitwise operations that are quite useful for SHA‐256. Most graphics cards can also be overclocked,meaning you can run them faster than they're actually designed for if you want to take on the risk that they might overheat or malfunction. This is a property gamers have demanded for years. With Bitcoin mining, it might be profitable to run the chip much faster than it was designed for even if you induce a few errors by doing so. For example, say you can run your graphics card 50 percent faster but doing so will cause errors in the SHA‐256 computation to 30 percent of the time. If an invalid solution is erroneously declared valid by the graphics card — something that would happen rarely — you can always double‐check it on your CPU. On the other hand, if a valid solution is erroneously missed, you’d never know. Bu 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com