Grokking Bitcoin

To explain transaction malleability, let’s go back to the example in [ch09] in which you gave a time-locked transaction to your daughter. When almost a year has passed since you created your time-locked transaction, you need to invalidate that transaction and create a new time-locked transaction, as Figure 1 shows.

It’s important to give the new time-locked transaction, Tx₃, to your daughter before broadcasting Tx₂, which invalidates the previous time-locked transaction, Tx₁. Otherwise, if you do it the other way around and get hit by a bus between the two steps, your daughter won’t be able to claim the money.

Suppose you do this correctly and first give Tx₃ to your daughter and then broadcast Tx₂. Tx₃ spends the output of Tx₂, which means Tx₃ contains the txid of Tx₂ in one of its inputs. Let’s see what might happen when you broadcast Tx₂ (Figure 2).

Qi wants to mess things up. When she receives your transaction Tx₂, she modifies it in a certain way into Tx_2M, so Tx_2M is still valid and has the same effect as the original transaction, Tx₂. (You’ll see shortly some different ways she can do this.) The result is that two different transactions now flow through the network that spend the same outputs and send the money to the same recipients with the same amounts—but they have different txids.

Because Tx₂ and Tx_2M spend the same outputs, they’re in conflict with each other, and at most one of them will be confirmed. Suppose Tx_2M is the winner and gets mined in the next block. What happens to your daughter’s inheritance? See Figure 3.

The malleated transaction, Tx_2M, is stored in the blockchain. This makes Tx₂ invalid because it spends the same output as Tx_2M. The first input of the time-locked transaction, Tx₃, references Tx₂ using its txid, so when 30 April 2020 has passed, your daughter won’t be able to claim her inheritance: she’ll be trying to spend an output from an invalid transaction.

When a transaction is signed, the signature algorithm hashes the transaction in a certain way.

Remember from [sign-transaction] that you clean all signature scripts before signing. But if you did just that, all the transaction’s signatures would use the exact same hash. If the transaction spent two different outputs that pay to the same address, the signature in one of the inputs could be reused in the other input. That property could be exploited by bad actors.

To avoid this problem, Bitcoin makes each signature commit to a slightly different version of the transaction by copying the spent pubkey script into the signature script of the input that’s currently being signed.

Let’s zoom in a bit on what’s happening. Suppose you want to sign a transaction with two inputs. The first input is signed as illustrated in Figure 5.

The signature scripts of all inputs are empty, but you copy the pubkey script of the spent output and insert it into the signature script of the spending input. You then create the signature for the first input and move on to sign the second input (Figure 6).

Here, all signature scripts except the second one are empty. The second signature script is populated with the spent output’s pubkey script. The signature is then created.

By doing this exercise for each input, you ensure that signatures aren’t reusable across inputs if signed by the same private key. But this also introduces a problem: signature verification becomes inefficient.

Suppose you want to verify the signatures of the aforementioned transaction. For every input, you need to perform basically the same procedure as when the transaction was signed: clean all the signature scripts from the transaction and then, one at a time, insert the pubkey script in the signature script of the input you want to verify. Then, verify the signature for that input.

This might seem harmless, but as the number of inputs grows, the amount of data to hash for each signature increases. If you double the number of inputs, you roughly

If the time to verify the transaction with two inputs in Figure 7 is 1 ms, it will take 4 ms to verify a transaction with four inputs. Double the number of inputs again, and you have 16 ms. A transaction with 1,024 inputs would take more than 4 minutes!

This weakness can be exploited by creating a large transaction with a lot of inputs. All nodes verifying the transaction will be occupied for minutes, making them unable to verify other transactions and blocks during this time. The Bitcoin network as a whole would slow down.

It would be much better if the transaction verification time grew linearly instead of quadratically: the time to verify a transaction would double as the number of inputs doubled. Then, the 1,024 inputs would take roughly 512 ms to verify instead of 4 minutes.

When a full node sends a transaction to a lightweight wallet, it sends the complete transaction, which includes all signature data. But a lightweight wallet can’t verify the signatures because it doesn’t have the spent outputs.

The signature scripts constitute a large percentage of the transaction size. A typical signature script spending a p2pkh output takes 107 bytes. Consider a few different transactions with two outputs, as Table 1 shows.

Wouldn’t it be nice if a full node didn’t have to send the signature script data to the lightweight wallet? You’d probably save more than 50% data traffic. There’s just one problem: such data is needed to calculate txids. If you skip sending signature scripts of transactions, the lightweight wallet won’t be able to verify that the transaction is included in a block because it can’t verify the merkle proof (Figure 8).

We’d definitely like to solve this somehow.

Sometimes, we want to extend the script language with new operations. For example, OP_CHECKSEQUENCEVERIFY (OP_CSV) and OP_CHECKLOCKTIMEVERIFY (OP_CLTV) were introduced in the language in 2015 and 2016. Let’s look at how OP_CLTV was introduced.

We’ll start with what OP_ codes are. They’re nothing but a single byte. OP_EQUAL for example, is represented by the byte 87 in hex code. Every node knows that when it encounters byte 87 in the script program, it needs to compare the top two items on the stack and push the result back on the stack. OP_CHECKMULTISIG is also a single byte, ae. All operators are represented by different bytes.

When Bitcoin was created, several NOP operators, OP_NOP1–OP_NOP10, were specified. These are represented by the bytes b0–b9. They’re designed to do nothing. The name NOP comes from No OPeration, which basically means, “When this instruction appears, ignore it and move on.”

These NOPs can be used to extend the script language, but only to a certain extent. The OP_CLTV operator is actually OP_NOP2, or byte b1. OP_CLTV was introduced by releasing a version of Bitcoin Core that redefines how OP_NOP2 works. But it needs to be done in a compatible way so we don’t break compatibility with old, non-upgraded nodes.

Let’s go back to the example from [absolute-time-locked-outputs], where you gave your daughter an allowance in advance that she could cash out on 1 May (see Figure 9).

The pubkey script for this output is

This is how a new node—which is aware of the new meaning of byte b1—interprets the script. It will do the following:

An old node, on the other hand, will interpret the script as follows:

It will

Old nodes still treat OP_NOP2 as they used to—by doing nothing and moving on. They aren’t aware of the new rules associated with the byte b1.

The old and the new nodes will behave the same if the OP_CLTV succeeds on the new node. But if the OP_CLTV fails on the new node, the old node won’t fail, because “do nothing” never fails. The new nodes fail more often than the old nodes because new nodes have stricter rules. The old nodes will always finish the script program with success whenever the new nodes finish with success. This is known as a soft fork—a system upgrade that doesn’t require all nodes to upgrade. We’ll talk more about forks, system upgrades, and alternate currencies born from Bitcoin’s blockchain in [ch11].

You might be wondering what the OP_DROP instruction is for. OP_DROP takes the top item on the stack and discards it. OP_CLTV is designed to behave exactly like OP_NOP2 when it succeeds. If OP_CLTV had been designed without taking old nodes into account, it would probably remove the top item from the stack. But because we need to take old nodes into account, OP_CLTV doesn’t do that. We must add the extra OP_DROP after OP_CLTV to get rid of the time item from the stack.

This was an example of how old script operators can be repurposed to do something stricter without disrupting the entire network.

This method of script upgrades has been done for two operators so far:

Only 10 OP_NOP operators are available to use for script upgrades, and such upgrades are limited to exactly mimic the OP_NOP behavior if they don’t fail.

Sooner or later, we’ll need another script-upgrade mechanism, both because we’ll run out of OP_NOPs and because we want the new script operators to behave differently than OP_NOP when they succeed.

Suppose your wallet uses segwit, and you’re selling a laptop to Amy. Your wallet needs to create an address that you can give to Amy. So far, nothing new.

But segwit defines a new address type that’s encoded using Bech32 instead of base58check. Suppose your wallet creates the following segwit address:

This address format provides several improvements compared to the base58check addresses you’re used to:

Your segwit address consists of two parts. The first two characters, bc (short for bitcoin) is the human-readable part. The 1 is a delimiter between the human-readable part and the data part, which encodes the actual information that Amy will use to create the transaction output:

We’ll explain what the witness program is a bit further on. Think about it as a PKH for now. The version and witness program aren’t directly extractable from the address because they’re encoded using bech32. You give the address bc1qeqzj…ag6jdmkj to Amy by showing her a QR code. She has a modern wallet that understands this address format, so she scans your address and extracts the version and witness program, as Figure 12 illustrates.

This occurs in multiple steps:

Amy creates a transaction with a new kind of pubkey script that you aren’t used to (Figure 13).

She broadcasts this transaction on the Bitcoin network. The network will accept the transaction because it’s correctly signed in the old-fashioned way. Eventually, it will be confirmed in a block. Your wallet will acknowledge that you’ve received the money, and you’ll give the laptop to Amy.

Now that you’ve received your money, you want to spend it on a used popcorn machine. It costs only 0.09 BTC. It’s a bargain! Suppose the owner of the popcorn machine has the segwit address bc1qlk34…ul0qwrqp.

Your transaction sends the money to the popcorn machine owner’s segwit address and pays a 0.01 BTC transaction fee (Figure 14). The input has an empty signature script; the signature data is instead added as a witness field in the attached witness.

Had there been multiple inputs in this transaction, there would be multiple witness fields in the witness, one for each input. You can mix segwit inputs and legacy inputs, in which case the witness fields for the legacy inputs would be empty because their signatures are in the respective signature script, as they always were.

You’ve sent your transaction for the popcorn machine to the Bitcoin peer-to-peer network for processing. Let’s see how an upgraded full node verifies this transaction before relaying it to other nodes (Figure 15). Because it’s running the latest and greatest software, it knows how to deal with segwit transactions.

The full node, which knows about segwit, looks for a pattern in the pubkey script starting with a single version byte followed by a 2- to 40-byte witness program. In this case, the pattern matches, which means this is a segwit output.

The next step for the full node is to understand what kind of segwit output it is. As of this writing, there’s only one version of segwit output: version 00. This version comes in two different flavors:

In this case, we have the version byte 00 followed by exactly 20 bytes, which means this is a p2wpkh payment. If the version byte is unknown to the node, the node will immediately accept this input without further processing. This acceptance of unknown versions will become useful for future, forward-compatible upgrades of the script language. All segwit nodes will recognize version 00.

The p2wpkh is the simplest of the two types because it’s similar to the well-known p2pkh. Let’s look at how they both work:

In the end, it’s seemingly the exact same program that is run for both of these two types. The difference is where the components come from. But other differences exist between segwit scripts and legacy scripts—for example, the meaning of OP_CHECKSIG has changed, as you’ll see in Section 10.2.6.

Why do p2wpkh at all when we’re running the exact same script program as in p2pkh? Recall that we want to solve transaction malleability. We do this by removing the signature data from the transaction inputs so no one can change the txid by making subtle changes to the signature script.

The full node has verified this transaction and sends it to its peers. There’s just one problem: one peer has no idea what segwit is. It’s an old node that hasn’t been upgraded for a while.

Your segwit transaction has propagated through the network, and all nodes have verified it along the way. Now, a miner wants to insert the transaction into a new block. Suppose the miner runs modern software and thus knows about segwit. Let’s look at how it’s included in the block (Figure 17).

The block is built as before, but with one important difference. A new block rule is introduced in segwit: if there are segwit transactions in the block, the coinbase transaction must contain an output with a witness commitment. This witness commitment is the combined hash of the witness root hash and a witness reserved value. The witness root hash is the merkle root of the witness txids (wtxids) of all transactions in the block. The wtxid is the hash of the transaction including the witness, if there is one. An exception exists for the coinbase, whose wtxid is always defined as 32 zero bytes. The witness reserved value is dedicated for future system upgrades.

The witness commitment is written in an OP_RETURN output (Figure 18).

The witness reserved value can be any value. But a full node verifying this block needs a way to know what that value is. If the node didn’t know the witness reserved value, it wouldn’t be able to reconstruct the witness commitment for comparison with the OP_RETURN output’s witness commitment. The coinbase transaction’s witness contains the witness reserved value so full nodes can verify the witness commitment.

Do you remember when we introduced p2sh in [pay-to-script-hash]? p2sh moves the pubkey script part of the program to the spending input. Let’s have another look at the charity wallet that John, Ellen, and Faiza set up (Figure 20).

The idea here was that the payer—the donor, in this case—shouldn’t have to pay a higher fee for a big, complex pubkey script. Instead, the recipient wanting to use this fancy scheme will pay for the complexity.

With segwit, you can do about the same thing using pay-to-witness-script-hash, which is the segwit version of p2sh. Isn’t naming in Bitcoin fantastic?

Suppose John, Ellen, and Faiza use segwit for their charity wallet and that the previous popcorn machine owner wants to give the money he received for the popcorn machine to the charity.

John, Ellen, and Faiza must provide the popcorn guy with a p2wsh address. Their witness script is the same as their p2sh redeem script was when they were using p2sh (Figure 21).

They use this witness script hash to create a p2wsh address in the same way you created your p2wpkh address. They encode

using Bech32 and get the p2wsh address:

This address is handed to the popcorn guy, who creates and broadcasts a transaction like that shown in Figure 22.

The transaction has the witness attached, just like your transaction to the popcorn guy. The only difference between your transaction and the popcorn guy’s transaction is that their outputs have a different witness program length. Your transaction had a 20-byte witness program because it was a SHA256+RIPEMD160 hash of a public key, and the popcorn guy’s transaction has a 32-byte witness program because that’s a SHA256 of a witness script.

This transaction will be verified and eventually included in a block.

One problem that segwit solves is inefficient signature hashing. As explained in Section 10.1.2, if the number of inputs doubles, the time it takes to verify the transaction roughly quadruples. This is because you

If you double the number of hashes performed and double the amount of data each hash needs to process, you effectively quadruple the total time spent on hashing.

The solution is to make the signatures in steps. Suppose you want to sign all four inputs of a transaction, as Figure 26 shows.

First you create an intermediate hash of the complete transaction. If the transaction contains non-segwit inputs, those signature scripts will be cleaned prior to hashing. The intermediate hash commits to all of that transaction’s inputs and outputs. Then, for each input, add the intermediate hash to some input-specific data:

The bulk of the transaction is hashed only once to create the intermediate hash. This drastically reduces the amount of hashing needed. When the number of inputs doubles, the needed amount of hashing only doubles. This makes the hashing algorithm perform linearly with the number of inputs instead of quadratically. The time to verify the transaction with 1,024 inputs discussed in Figure 7 is reduced from 262,144 ms to 512 ms.

Segwit removes the signature data from the transaction, so when a lightweight wallet requests a transaction from a full node, the full node can send the transaction without the witness data. This means less data traffic is needed per transaction. This fact can be used to either

The version byte is used for future script language upgrades. Before segwit, we had to use the OP_NOPs to introduce new features to the language—for example, OP_CSV. This wasn’t optimal for the following reasons:

The version byte allows for much more powerful future upgrades. We can do anything from slight modifications of specific operators to implementing completely new languages.

In 2010, the Bitcoin software was updated with a block size limit of 1,000,000 bytes. It isn’t totally clear why this was done, but most people think the limit was introduced to reduce the impact of certain denial of service (DoS) attacks. DoS attacks aim at stalling or crashing Bitcoin nodes so the network can’t function properly.

One way to mess with the network is to create a very large block that takes 10 seconds to download on a good internet connection. This might seem fast enough, but uploading this block to five peers will take 50 seconds. This will cause the block to propagate very slowly across the peer-to-peer network, which will increase the risk of an unintended blockchain split. Unintended splits will resolve with time, as you saw in [draw-lucky-numbers], but Bitcoin’s overall security will decrease during such splits.

Another potential problem with big blocks that attackers could exploit is that people with poor internet connections will be left out completely because they can’t keep up with the network, or they don’t have the required processing power, RAM, or disk storage space needed to run a full node. These people will need to switch to systems with less security, such as lightweight wallets, reducing the security of the whole network.

Regardless of the reason, this limit is in place.

The signature operations limit was put in place because signature-verification operations are relatively slow, especially in non-segwit transactions. An attacker could stuff a transaction with a tremendous number of signatures, causing verifying nodes to be busy verifying signatures for a long time. The limit of 20,000 such operations per block was somewhat arbitrarily chosen to prevent such an attack.

It will take a hard fork to remove or increase these limits. A hard fork is a rule change that causes old nodes and new nodes to disagree on what the strongest valid blockchain is. We’ll examine forks and upgrades in [ch11]. For now, suppose new nodes decide that 8,000,000-byte blocks are OK. When a miner publishes a block that’s bigger than 1,000,000 bytes, new nodes will accept it, whereas old nodes won’t. A permanent blockchain split will occur, and we’ll effectively have two different cryptocurrencies.

Segwit offers an opportunity to somewhat increase both these limits without a hard fork.

By moving signature data out of the base transaction, that data will no longer be part of the txid.

If the signature is malleated, it won’t affect the txid. Unconfirmed chains of transactions become unbreakable.

A new signature-hashing algorithm is used that makes the verification time grow linearly with the number of inputs. The old signature-hashing algorithm hashes the entire transaction for each signature.

Signatures in witnesses will hash the transaction only once.

The intermediate hash is reused for each signature, which greatly reduces the total amount of hashing.

The bandwidth that lightweight wallets require decreases because they don’t have to download the witnesses to verify that a transaction is included in a block. They can use the per-transaction savings to increase their privacy by decreasing their bloom filter size or to reduce data traffic with preserved privacy.

The witness version in the pubkey script allows for future upgrades of the script language. These upgrades can be arbitrarily complex with no restrictions on functionality.

New rules apply for blocks containing segwit transactions. An output in the coinbase transaction must commit to all the block’s witnesses.

Old nodes will still work because they aren’t aware of the commitment in the coinbase transaction. This let us introduce segwit without disrupting, or splitting, the blockchain into two separate cryptocurrencies.