Grokking Bitcoin

Suppose the current block height is 100. Tom and Qi have just published their block-signing public keys on the billboard and on the company’s intranet. All wallets start sending transactions to all three block producers, or miners. Figure 3 illustrates what happens.

If they all just do what Lisa did, they’ll produce a block every 10 minutes, resulting in three different blocks with roughly the same transactions. The major differences between the three conflicting blocks are the coinbase transaction and the signatures. The coinbase of Tom’s blocks would pay the block reward to Tom’s cookie token address, whereas the coinbase of Lisa’s blocks would pay the block reward to Lisa’s cookie token address.

To avoid this problem, the miners must somehow decide which one produces the next block. They could take turns, but this would be complicated because Lisa’s computer might be broken, or Tom might refuse to create a block for some reason. In such a scenario, the system would halt.

Let’s try another naive approach (Figure 4). Every second, each miner draws a random number between 0 and 999,999. If a miner happens to draw a number in the range 0 to 555, it will immediately sign and publish a block. The probability of drawing a lucky number on a single try is low—556/1,000,000, or roughly 1 in 1,800 tries. The miners draw one number per second, so each miner is expected to draw a lucky number every 30 minutes (1,800 seconds) on average. The three miners together will then produce on average 1 block every 10 minutes.

When a miner draws a lucky number, chances are low that either of the other two miners also drew a lucky number at the same time. This means, usually, only a single miner will produce the next block.

The miners save their blocks as <_last-8-hexdigits-of-blockid_>.dat in the shared folder, so multiple blocks at the same height don’t have to worry about file naming. An example of a filename is 9ce35c25.dat.

The system ticks on quite well, but once in a while, two miners draw a lucky number at the same time. They aren’t aware that another miner also drew a lucky number, so they’ll both produce a block at the same height. This situation is known as a blockchain split because the chain splits in two. Both branches are equally valid, so which one is “correct”? Which miner will “win” the block and collect the block reward of 50 CT?

You don’t know the winner yet. It’s up to the miners to decide which branch they want to extend with their next blocks. In Figure 4, both Tom and Qi have created a block at height 106. The different miners would likely think as follows:

When the miners have picked a block at height 106 to extend, they build a new block at height 107 and start drawing numbers again. Several outcomes are possible from this situation, assuming everyone is honest: an immediate resolution, a delayed resolution, or a split of a split.

Eventually, one branch of a split will win. The likelihood that two branches of length X happen next diminishes rapidly for increasing X:

A split of branch length 1 is quite likely to happen, but a branch of length 2 probably won’t happen during Lisa’s lifetime (she’s 45). No matter how long the splits are, eventually they’ll resolve with a winner. This seems like a nice scheme. But it has its issues:

Clearly, this system won’t be able to increase the number of miners beyond a controlled group of highly trusted participants. You’ll get a flood of blocks as miners start cheating, but you can’t prove they’re cheating. It’s possible they’re just really, really lucky.

To create a new block, a miner must produce a valid proof of work for the block before it’s considered valid. To make a valid proof of work, the miner must create a block-header hash that’s less than or equal to the target in the block header.

A block ID is a double SHA256 of the block header. As you learned in [ch02], the only way to find a pre-image to a cryptographic hash function is to try different inputs over and over until you find one. The same goes here; the miner must try different block headers until it finds one that hashes to a value less than or equal to the target.

Let’s go back in time and look at how Qi created her block. She creates a block, sets the target to 00000000926e…, and sets the nonce to 0. She then tests whether the proof of work is valid (Figure 12).

She calculates the block ID by hashing her block header with double SHA256. In this case, the block ID is aa9c614e7f50…. This number is bigger than the target:

The rule is that the block ID must be less than or equal to the target for the proof of work to be valid. Qi fails miserably.

This is where the nonce comes in. A nonce is just a silly number that doesn’t mean anything. It can be set to any value. Qi initially set the nonce to 0, but she could just as well have set it to 123 or 92178237. The nonce helps make a change in the block that will affect the block ID without changing any real data, like transactions or the previous block ID.

Qi will now try again to make a valid proof of work. She increases the nonce from 0 to 1 and tests the validity again (Figure 13).

When Qi changes the block header by increasing the nonce, the block ID changes—any tiny change in the header will result in a completely different block ID. This is the same property displayed in [cryptographic_hashing] in [ch02], when we changed the cat picture (Figure 14).

The new block ID is 863c9bea5fd8… This is also bigger than the target. Qi fails again. I’m sorry, but there’s no way around it—Qi must try once more. She increases the nonce from 1 to 2 and tests again (Figure 15).

The result is the same: miserable failure. The block ID was 005ce22db5aa… this time, which is still bigger than the target.

She repeats this over and over. For example, Figure 16 shows her 227,299,125th try. It was close, but close doesn’t help. She has to keep trying (Figure 17). And finally she gets the result shown in Figure 18.

The nonce 492781982 results in a block ID 000000003c77…. She compares this to the target:

Wow—this block ID is less than the target! Qi has performed a great deal of work to find a nonce that results in a block ID less than the target. She’s created a block with a valid proof of work. Great, now she’ll publish the block to the shared folder.

It’s important to realize that all miners build their own unique blocks. For example, Tom is working on his own block concurrently with Qi (and Lisa), but his set of transactions is different than Qi’s because his coinbase transaction pays the block reward to himself, whereas Qi’s coinbase transaction pays the block reward to Qi. This difference will cause the merkle roots in their respective block headers to differ. If Tom sets Qi’s winning nonce, 492781982, on his own block, he likely won’t meet the target. Other things that probably differ between their blocks could be the timestamp or the selected list of transactions.

Anyone can pick up the block from the shared folder and verify that the rule is met—the block ID is less than or equal to the agreed-on target. Block verification is now slightly different than before (Figure 19).

The difference from verifying a digitally signed block is that the full node verifies the block producer has provided a valid proof of work instead of a valid digital signature.

The blockchain will grow the same way as before, but the drawing of lucky numbers is replaced by hashing the block header (Figure 20). Table 1 compares the two systems.

Instead of drawing a random number each second, the miners draw a number about every 0.02 microseconds through cryptographic hashing. At the same time, the lucky number limit, or target, is set to the 256-bit number 00000000926e…=926eb9*2²⁰⁰ instead of just 555.

subtle but important difference is that with proof of work, it’s the chain with the most accumulated proof of work that’s considered the best branch to follow. In the lucky numbers case, nodes followed the longest chain. The accumulated proof of work for a blockchain is the sum of the difficulty of each individual block in the chain.

The difficulty of a block is a measurement of how many times harder it is to find a valid proof of work for that block compared to finding it for the genesis block.

More exactly, the difficulty of block B is calculated like this:

The target of the genesis block is divided by the target of B, which makes the difficulty of the genesis block exactly 1.

The gist of this is that the higher the target of a block, the lower the difficulty of that block, and the lower the target, the higher the difficulty. So, we sum all blocks’ difficulties in the blockchain to get the chain’s accumulated proof of work.

From now on, I’ll refer to the branch with the most accumulated work as the strongest branch or strongest chain. Another commonly used term is best chain. The distinction between the longest and the strongest chain will become important in Section 7.5.2 when I’ve introduced difficulty adjustments.

The nonce is a 32-bit number. This is pretty small. If a miner has tried all 4,294,967,296 possible numbers without success, they must do something else to change the block header. Otherwise, they’ll redo the exact same tries they’ve already made. Several options exist for making a change (Figure 21):

Changing the timestamp is straightforward—just add a second to the timestamp, and the header will be different. If you use one of the other two options, you’ll have to recalculate the merkle root because the transaction data has changed. When the merkle root is updated, the header changes.

Once you make any of these changes to the block, the header will change so the nonce can be reset to 0, and the miner can begin hashing again.

An interesting aspect of this system is that anyone can become a miner without asking for permission. They can just set up a computer at home and start building blocks. Blocks are no longer tied to a person but to an amount of computing work:

After Lisa’s and Rashid’s added hashrate, the total hashrate in the cookie token system has increased significantly:

Look: we’re producing more blocks per day than we designed for! The goal is 144 blocks per day, and 264 is significantly more than this. The block rate is too high, almost double the desired rate.

A higher block rate might seem beneficial because the confirmation time of transactions will decrease, but it comes with some problems.

We’ve fixed the hard problem of forcing “honest lucky numbers” in an interesting way. Let’s see what issues from Section 7.1.3 remain:

There’s only one problem left in the list. We’ll fix it in the next section.

The block header contains a timestamp. Timestamps are important because you want the system to automatically adjust the target without human intervention so that, on average, 1 block is produced per 10 minutes. The block-creation rate is important because you want a predictable issuance of new cookie tokens.

The miner creating a block sets the timestamp to the current time before producing a proof of work. But because different full nodes run on different computers, their clocks might not be in perfect sync.

Suppose Lisa produces a block with timestamp 2017-08-13 07:33:21 UTC and publishes it on the shared folder. Tom then produces the next block, but his clock is behind Lisa’s clock.

Tom produces a block with an earlier timestamp than the previous block. This isn’t a problem as long as the timestamps don’t differ too much (Figure 23).

The timestamp must obey a few rules. Suppose the cafe’s full node is about to verify Tom’s block:

These rules ensure that no one manipulates their blocks’ timestamps to influence the next target calculation. Imagine if the last block before the retarget had a timestamp six weeks after the current time. This would cause the next target to increase by a factor of 4, as Table 2 shows.

The last timestamp is six weeks later than when the block was actually mined. All full nodes will reject this block because it violates the timestamp rules. Someone wants to manipulate the target. If this block had been accepted, the next target would be four times bigger than the current target, making it four times easier to find a valid proof of work. This kind of misbehavior is prohibited by the timestamp rules just described. Given that you can’t lie more than two hours with your timestamp, the next target can’t be manipulated more than marginally.

Let’s get back to the discussion on chain strength and why it’s important not to merely look at chain length. It intuitively seems reasonable that the harder it is to rewrite the chain’s history, the better, so you should follow the strongest chain. But when do the strongest and longest chain differ?

They can differ for several reasons:

We’ll look only at the first option here. Suppose a natural split occurs (Figure 24).

This is an unlikely scenario, but we need to consider it because it might happen. A split happens right before a retarget, and the 2 blocks’ timestamps differ by four hours. Next, 2 new blocks are produced at the same time, one on each branch. These new blocks have been retargeted based on different histories. The last timestamps in the respective retarget periods differ by four hours, which causes the new targets to be different. Recall the retarget formula:

Because the new targets are different, the new difficulty of the last block on each branch is different. This means the chain strength differs because the branches now have different accumulated proof of work.

Suppose Lisa is about to pay for a cookie in the cafe. But at the time she pays, she also prepares a double-spend transaction (Figure 25).

C is the transaction to the cafe. L is Lisa’s double-spend transaction that she’s going to use to snatch her money back. Both transactions are perfectly valid on their own, but both can’t be valid at the same time because they both spend a common output. An output can be spent only once.

Lisa sends the honest payment, C, to all miners. While other miners try to add her honest transaction into a block and create a valid proof of work, Lisa secretly puts the double-spend transaction, L, into a secret block of her own and starts working on that block (Figure 26).

Lisa’s goal is to secretly find a valid proof of work for her fraud branch, containing L, that exceeds the honest chain’s proof of work. If she succeeds, she’ll publish all blocks in her branch, and all miners will switch over to her branch and start working to extend her branch instead. For simplicity, let’s assume this all happens without any retargets (difficulty adjustments) happening; we’re in the middle of a retarget period. This means all blocks have the same target (or difficulty), so we can strictly look at branch length instead of branch strength (accumulated proof of work).

A bunch of miners are trying to confirm Lisa’s honest transaction, C, while Lisa works to find a valid proof of work for her block with the double-spend transaction, L. The cafe is waiting for a valid transaction before it hands out the cookie.

Eventually, the honest transaction will be confirmed on the honest chain. The cafe sees that block, verifies it, and gives the cookie to Lisa. Lisa eats it. While she swallows the last crumb, her computer happens to find a valid proof of work for her block. She doesn’t publish her block yet because it won’t help her. Miners are already mining on the honest branch because that’s where they first saw a block.

The combined hashrate of all miners on the honest chain is 350 Mhash/s, whereas Lisa has only 200 Mhash/s. This means the honest chain should be able to find blocks more often than Lisa.

But everyone gets lucky once in a while. Lisa is lucky to find yet another block on her fraudulent branch. She now has 2 blocks on her branch, whereas the honest branch is only 1 block long. Lisa has more total proof of work on her chain than the honest miners have on their branch. Lisa publishes her 2 blocks to the shared folder.

Other miners will see those 2 blocks, see that Lisa’s branch has more proof of work than the honest branch, and switch over to Lisa’s branch. The miners that switch can’t see that a crime is being committed or who create the blocks; they’ll neutrally jump to the strongest valid chain.

The result is that transaction C to the cafe is effectively undone. It’s no longer part of the chain with the most proof of work. The cafe has lost the 10 CT it thought it had when it gave the cookie to Lisa.

From this point forward, new blocks will extend Lisa’s branch, and things will continue normally. The block with transaction C will become stale.

Although the odds are against Lisa, she could get lucky and succeed in a double-spend attack, as in the previous example. Trying to pull off a double spend of 10 CT isn’t economically feasible from Lisa’s perspective. She risks spending lots of electricity and making her own blocks stale if she doesn’t succeed. She’d lose out on the rewards from those stale blocks.

But what if she tried to double spend a larger amount than 10 CT: say, 100,000 CT? Then it might be worth it for Lisa to try to double spend. Just imagine if she could buy the whole cafe and pull off a double-spend attack. Then she would have a cafe and still have her 100,000 CT.

The cafe owner is willing to sell the cafe to Lisa for 100,000 CT. But the cafe is, of course, aware of double-spend attacks. So, the cafe owner tells Lisa that for this much money, he’ll give her the cafe after six confirmations.

What does this mean? Lisa must pay the cafe owner 100,000 CT and then wait until the transaction is included in a block and 5 blocks have been built after that block. Only then will the owner hand the cafe over to Lisa.

To pull off a double-spend attack, Lisa must build an alternate branch in secret, just like in her previous attack, while the cafe awaits six confirmations. When the cafe owner has seen six confirmations and given the cafe to Lisa, she must at some point upload a stronger double-spend branch to the shared folder. This means Lisa must be lucky for a longer time period than in the previous example.

Let’s see how it goes (Figure 27).

The outcome is as expected. Lisa couldn’t produce more blocks than the honest chain in the long run. She gave up at 7–4.

The following table shows the sequence of events in this example:

Lisa gives up for several reasons:

The key here is that the cafe demanded six confirmations. The more confirmations needed, the harder it is for Lisa to build a stronger branch than the honest miners. She needs more luck.

When the cafe got its six confirmations, Lisa was 2 blocks behind. She would need to grow faster than the honest chain and become 1 block longer than the honest chain. Her chances are small. The more blocks she has to catch up with, the smaller the chances, as Table 3 shows.

The probability, \(q_z\), is calculated as

Look at the column for a 36% hashrate, which is what Lisa has. When she’s 3 blocks behind, she must produce 4 blocks more than the honest miners in the future. This gives her a roughly 0.10 chance of ever succeeding in this double spend—if she’s prepared to try indefinitely. She probably doesn’t want to keep trying forever, which gives her a slightly smaller probability of succeeding.

Suppose Lisa and Tom find valid proof of work for their respective blocks at the same time. Lisa’s block is 200 KB and contains 400 transactions, whereas Tom’s block is 100 KB and contains 200 transactions. They both want their own block to become part of the strongest chain, but only one of them can take that place. They start uploading their respective blocks to the shared folder at the exact same time (Figure 31).

Tom’s block is smaller than Lisa’s. This means Tom will upload his block to the shared folder faster than Lisa uploads hers. It will also be faster for Qi to download Tom’s block than it will be to download Lisa’s block. Finally, Qi has to verify blocks she downloads before building on them. A smaller block will typically be faster to verify than a big block, so Tom’s block is also faster to verify than Lisa’s block.

The result is that Qi will, at time T, select Tom’s block as the current best chain tip and start mining on top of Tom’s block. Lisa’s block doesn’t really exist for Qi at time T because Qi hasn’t verified it yet. She’s still downloading Lisa’s block from the shared folder. When Qi finally verifies Lisa’s block at time L, Qi has already decided to go for Tom’s block, and Lisa’s block will be stored in case of future chain reorganizations.

Miners have a clear incentive to keep their blocks small. For each extra transaction they add to their blocks, they lose a little competitiveness in the block race.

This is where transaction fees come in. If the miner could get paid a little extra for each transaction it adds to its block, that would compensate for the loss of competitiveness.

People making payments are keen on having their transactions confirmed in the blockchain. Wouldn’t it be great if John could reserve a little money in his transaction for the miner who includes it? This way, the payer could compensate the miner for the loss of competitiveness.

If you use the transactions a little differently, you can offer this feature. Let’s say John wants to buy a cookie. To give miners an incentive to include his transaction, he decides to add a transaction fee. He constructs his transaction as shown in Figure 32.

When John created a similar transaction in [ch05], the sum of the inputs was equal to the sum of the outputs. He didn’t pay a transaction fee.

This time, John wants to add a small transaction fee to his transaction. He spends two inputs, totaling 13 CT, and adds an output of 10 CT to the cafe and a change output of 2.5 CT to himself. He then signs the transaction just as he always does and sends it to all the miners.

Lisa, the miner, receives this transaction from John. She notices that there is a transaction fee of 0.5 CT in it. She wants that fee and decides the transaction fee compensates more than enough for the small incremental risk of losing the block race due to including the transaction.

We’ll talk more about fees, and how you can change a transaction’s fee if it gets stuck pending—also known as fee bumping—in [ch09].

For Lisa, when she’s deciding whether to include a transaction, all that matters is how big the transaction is and what fee it pays. Basically, it’s the fee per byte she’s interested in. John’s transaction is about 400 bytes and pays a 0.5 CT fee. That’s 0.00125 CT/byte. This is a simple calculation for Lisa to do, and she does the same for all transactions. If the fee per byte is above a certain threshold, she’ll include the transaction.

She can select transactions however she wants, as described in [transaction-selection]. For example, she can include her own transaction without any fee, or she can drop all transactions that pay for cookies no matter how high the fee is. And that’s OK. Other miners will have different strategies for selecting transactions. Most will probably make decisions based only on fee per byte.

How does Lisa collect this fee? By using her coinbase transaction (Figure 33).

Lisa sums up all transaction fees from the transactions in her block and increases the coinbase output with this amount. The amount in the coinbase output—the block reward—is the sum of the block subsidy, the 50 new cookie tokens this block creates, and all transaction fees from the transactions in the block. Note that we’ve widened the term block reward to include both the block subsidy (newly created money) and the transaction fees.

When the block is set up correctly, Lisa starts working to find a valid proof of work for this block.

Blocks aren’t allowed to be infinitely large. Simply put, the maximum block size is 1,000,000 bytes, but we’ll discuss some nuances of this in [block-size-limit]. If more transactions are waiting to be confirmed than there is block space available, miners have to choose which transactions to include in the block and which to exclude.

The transaction fee plays an important role in this situation because a higher transaction fee gives miners more incentive to include the transaction in a block instead of other transactions. The fee is used to compete against other transactions for block space, in addition to compensating for the lost competitiveness. This situation is known as a fee market (Figure 34).

If more block space is available than there is transaction data waiting to be confirmed, transactions don’t compete with each other in the same sense (Figure 35).

In this situation, any transaction that bears the cost of lost competitiveness will be confirmed.

As we discussed in [ch02], the block subsidy will be halved roughly every four years. At some point, the block subsidy won’t be big enough on its own to give miners incentive to mine. If the value of the block reward is smaller than the electricity bill, what’s the point in mining?

Transaction fees will play a bigger and bigger role for miners as the block subsidy decreases. The typical miner wants the income from mining to at least cover their electricity bill (Figure 36).

Note that the value of the block subsidy might not always decrease over time. Table 4 shows some examples.

This shows that the block subsidy by itself isn’t a measurement of mining income. We have to look at the value of the block subsidy and the value of the transaction fees. One thing is for sure: when the subsidy is zero, the value of the subsidy is also zero. At some point, the block subsidy isn’t incentive enough to mine.

When this happens, transaction fees will help give efficient miners revenue. If John wants his transaction confirmed, he must pay a fee big enough that one or more miners are willing to include his transaction. This is a market for block space at play.

We can only speculate about where fee levels will be in the future. Some people argue that Bitcoin’s fees are already too high for how they want to use Bitcoin today. As transaction fees go up, some current use cases for Bitcoin—for example, payments with tiny amounts—will have to find other ways to work. New systems are being developed on top of Bitcoin that enable people to lump a nearly infinite number of payments together into just one or two transactions. One such system, the Lightning Network, is of particular interest. If a million payments can be made with a single Bitcoin transaction, all those user transactions can share the cost of the transaction fee.

Proof of work replaces the block signatures introduced in [ch06], and we can remove them from the concept mapping table (Table 5).

Lisa is now doing the exact same tasks as a Bitcoin miner, which is why we remove Lisa from the table as well. The shared folder will be the last bit of the cookie token system we’ll take care of. That’s for the next chapter.

It’s time to release a shiny new version of the cookie token system (Table 6).