Bitcoin’s consensus algorithm. Recall that Bitcoin nodes do not have persistent, long‐term identities. This is another difference from traditional distributed consensus algorithms. One reason for this lack of identities is that in a peer‐to‐peer system, there is no central authority to assign identities to participants and verify that they’re not creating new nodes at will. The technical term for this is a Sybil attack. Sybils are just copies of nodes that a malicious adversary can create to look like there are a lot of different participants, when in fact all those pseudo‐participants are really controlled by the same adversary. The other reason is that pseudonymity is inherently a goal of Bitcoin. Even if it were possible or easy to establish identities for all nodes or all participants, we wouldn’t necessarily want to do that. Although Bitcoin doesn’t give strong anonymity guarantees in that the different transactions that one makes can often be linked together, it does have the property that nobody is forced to reveal their real‐life identity, like their name or IP address, in order to participate. And that’s an important property and a central feature of Bitcoin’s design.
If nodes did have identities, the design would be easier. For starters, identities would allow us to put in the protocol instructions of the form, “Now the node with the lowest numerical ID should take some step.” Without identities, the set of possible instructions is more constrained. But a much more
serious reason for nodes to have identities is for security. If nodes were identified and it weren’t trivial to create new node identities, then we could make assumptions on the number of nodes that are malicious, and we could derive security properties out of that. For both of these reasons, the lack of identities introduces difficulties for the consensus protocol in Bitcoin.
We can compensate for the lack of identities by making a weaker assumption. Suppose there is somehow an ability to pick a random node in the system. A good motivating analogy for this is a lottery or a raffle, or any number of real‐life systems where it’s hard to track people, give them identities and verify those identities. What we do in those contexts is to give out tokens or tickets or something similar. That enables us to later pick a random token ID, and call upon the owner of that ID. So for the moment, take a leap of faith and assume that it is possible to pick a random node from the Bitcoin network in this manner. Further assume, for the moment, that this token generation and distribution algorithm is sufficiently smart so that if the adversary is going to try to create a lot of Sybil nodes, all of those Sybils together will get only one token. This means the adversary is not able to multiply his power by creating new nodes. If you think this is a lot to assume, don’t worry. Later in this chapter, we’ll remove these assumptions and show in detail how properties equivalent to these are realized in Bitcoin.
Implicit Consensus. This assumption of random node selection makes possible something called implicit consensus. There are multiple rounds in our protocol, each corresponding to a different block in the block chain. In each round, a random node is somehow selected, and this node gets to propose the next block in the chain. There is no consensus algorithm for selecting the block, and no voting of any kind. The chosen node unilaterally proposes what the next block in the block chain will be. But what if that node is malicious? Well, there is a process for handling that, but it is an implicit one.
Other nodes will implicitly accept or reject that block by choosing whether or not to build on top of it. If they accept that block, they will signal their acceptance by extending the block chain including the accepted block. By contrast, if they reject that block, they will extend the chain by ignoring that block, and building on top of whichever is the previous block that they accepted. Recall that each block contains a hash of the block that it extends. This is the technical mechanism that allows nodes to signal which block it is that they are extending.
Let’s now try to understand why this consensus algorithm works. To do this, let’s consider how a malicious adversary — who we’ll call Alice — may be able to subvert this process.
Stealing Bitcoins. Can Alice simply steal bitcoins belonging to another user at an address she doesn’t control? No. Even if it is Alice’s turn to propose the next block in the chain, she cannot steal other users’ bitcoins. Doing so would require Alice to create a valid transaction that spends that coin. This would require Alice to forge the owners’ signatures which she cannot do if a secure digital signature scheme is used. So as long as the underlying cryptography is solid, she’s not able to simply steal bitcoins.
Denial of service attack. Let’s consider another attack. Say Alice really dislikes some other user Bob. Alice can then decide that she will not include any transactions originating from Bob’s address in any block that she proposes to get onto the block chain. In other words, she’s denying service to Bob.
While this is a valid attack that Alice can try to mount, luckily it’s nothing more than a minor annoyance. If Bob’s transaction doesn’t make it into the next block that Alice proposes, he will just wait until an honest node gets the chance to propose a block and then his transaction will get into that block. So that’s not really a good attack either.
Double‐spend attack. Alice may try to launch a double‐spend attack. To understand how that works, let’s assume that Alice is a customer of some online merchant or website run by Bob, who provides some online service in exchange for payment in bitcoins. Let’s say Bob’s service allows the download of some software. So here’s how a double‐spend attack might work. Alice adds an item to her shopping cart on Bob’s website and the server requests payment. Then Alice creates a Bitcoin transaction from her address to Bob’s and broadcasts it to the network. Let’s say that some honest node creates the next block, and includes this transaction in that block. So there is now a block that was created by an honest node that contains a transaction that represents a payment from Alice to the merchant Bob.
Recall that a transaction is a data structure that contains Alice’s signature, an instruction to pay to Bob’s public key, and a hash. This hash represents a pointer to a previous transaction output that Alice received and is now spending. That pointer must reference a transaction that was included in some previous block in the consensus chain.
Note, by the way, that there are two different types of hash pointers here that can easily be confused. Blocks include a hash pointer to the previous block that they’re extending. Transactions include one or more hash pointers to previous transaction outputs that are being redeemed.
Let’s return to how Alice can launch a double spend attack. The latest block was generated by an honest node and includes a transaction in which Alice pays Bob for the software download. Upon seeing this transaction included in the block chain, Bob concludes that Alice has paid him and allows Alice to download the software. Suppose the next random node that is selected in the next round happens to be controlled by Alice. Now since Alice gets to propose the next block, she could propose a block that ignores the block that contains the payment to Bob and instead contains a pointer to the
previous block. Furthermore, in the block that she proposes, Alice includes a transaction that transfers the very coins that she was sending to Bob to a different address that she herself controls. This is a classic double‐spend pattern. Since the two transactions spend the same coins, only one of them can be included in the block chain. If Alice succeeds in including the payment to her own address in the block chain, then the transaction in which she pays Bob is useless as it can never be included later in the block chain.
And how do we know if this double spend attempt is going to succeed or not? Well, that depends on which block will ultimately end up on the long‐term consensus chain — the one with the Alice → Bob transaction or the one with the Alice → Alice transaction. What determines which block will be included? Honest nodes follow the policy of extending the longest valid branch, so which branch will they extend? There is no right answer! At this point, the two branches are the same length — they only differ in the last block and both of these blocks are valid. The node that chooses the next block then may decide to build upon either one of them, and this choice will largely determine whether or not the double‐spend succeeds.
A subtle point: from a moral point of view, there is a clear difference between the block containing the transaction that pays Bob and the block containing the transaction in which Alice double spends those coins to her own address. But this distinction is only based on our knowledge of the story that Alice first paid Bob and then attempted to double spend. From a technological point of view, however, these two transactions are completely identical and both blocks are equally valid. The nodes that are looking at this really have no way to tell which is the morally legitimate transaction.
In practice, nodes often follow a heuristic of extending the block that they first heard about on the peer‐to‐peer network. But it’s not a solid rule. And in any case, because of network latency, it could easily be that the block that a node first heard about is actually the one that was created second. So there is at least some chance that the next node that gets to propose a block will extend the block containing the double spend. Alice could further try to increase the likelihood of this happening by bribing the next node to do so. If the next node does build on the double‐spend block for whatever reason, then this chain will now be longer than the one that includes the transaction to Bob. At this point, the next honest node is much more likely to continue to build on this chain since it is longer. This process will continue, and it will become increasingly likely that the block containing the double‐spend will be part of the long‐term consensus chain. The block containing the transaction to Bob, on the other hand, gets completely ignored by the network, and this is now called an orphan block.
Let’s now reconsider this whole situation from Bob‐the‐merchant’s point of view. Understanding how Bob can protect himself from this double‐spending attack is a key part of understanding Bitcoin security. When Alice broadcasts the transaction that represents her payment to Bob, Bob is listening on the network and hears about this transaction even before the next block is created. If Bob was even more foolhardy than we previously described, he can complete the checkout process on the website and allow Alice to download the software right at that moment. That’s called a zero‐confirmation transaction. This leads to an even more basic double spend attack than the one described before. Previously, for the double‐spend attack to occur, we had to assume that a malicious actor controls the node that proposes the next block. But if Bob allows Alice to download the
software before the transaction receives even a single confirmation on the block chain, then Alice can immediately broadcast a double‐spend transaction, and an honest node may include it in the next block instead of the transaction that pays Bob.
On the other hand, a cautious merchant would not release the software to Alice even after the transaction was included in one block, and would continue to wait. If Bob sees that Alice successfully launches a double‐spend attack, he realizes that the block containing Alice’s payment to him has been orphaned. He should abandon the transaction and not let Alice download the software. Instead, if it happens that despite the double‐spend attempt, the next several nodes build on the block with the Alice → Bob transaction, then Bob gains confidence that this transaction will be on the long‐term consensus chain.
In general, the more confirmations a transaction gets, the higher the probability that it is going to end up on the long‐term consensus chain. Recall that honest nodes’ behavior is always to extend the longest valid branch that they see. The chance that the shorter branch with the double spend will catch up to the longer branch becomes increasingly tiny as it grows longer than any other branch. This is especially true if only a minority of the nodes are malicious — for a shorter branch to catch up, several malicious nodes would have to be picked in close succession.
In fact, the double‐spend probability decreases exponentially with the number of confirmations. So, if the transaction that you’re interested in has received k confirmations, then the probability that a double‐spend transaction will end up on the long‐term consensus chain goes down exponentially as a function of k. The most common heuristic that’s used in the Bitcoin ecosystem is to wait for six confirmations. There is nothing really special about the number six. It’s just a good tradeoff between the amount of time you have to wait and your guarantee that the transaction you’re interested in ends up on the consensus block chain.
To recap, protection against invalid transactions is entirely cryptographic. But it is enforced by consensus, which means that if a node does attempt to include a cryptographically invalid transaction, then the only reason that transaction won’t end up in the long‐term consensus chain is because a majority of the nodes are honest and won’t include an invalid transaction in the block chain. On the other hand, protection against double‐spending is purely by consensus. Cryptography has nothing to say about this, and two transactions that represent a double‐spend attempt are both valid from a cryptographic perspective. But it’s the consensus that determines which one will end up on the long‐term consensus chain. And finally, you’re never 100 percent sure that a transaction you’re interested in is on the consensus branch. But, this exponential probability guarantee is rather good.
After about six transactions, there’s virtually no chance that you’re going to go wrong.
