Chapter 2: How Bitcoin Achieves Decentralization
In this chapter, we will discuss decentralization in Bitcoin. In the first chapter we looked at the crypto basics that underlie Bitcoin and we ended with a simple currency that we called ScroogeCoin. ScroogeCoin achieves a lot of what we want in a ledger‐based cryptocurrency, but it has one glaring problem — it relies upon the centralized authority called Scrooge. We ended with the question of how to decentralize, or de‐Scrooge‐ify, this currency, and answering that question will be the focus of this chapter.
As you read through this chapter, take note that the mechanism through which Bitcoin achieves decentralization is not purely technical, but it’s a combination of technical methods and clever incentive engineering. At the end of this chapter you should have a really good appreciation for how this decentralization happens, and more generally how Bitcoin works and why it is secure.
2.1 Centralization vs. Decentralization
Copyright By PowCoder代写 加微信 powcoder
Decentralization is an important concept that is not unique to Bitcoin. The notion of competing paradigms of centralization versus decentralization arises in a variety of different digital technologies. In order to best understand how it plays out in Bitcoin, it is useful to understand the central conflict — the tension between these two paradigms — in a variety of other contexts.
On the one hand we have the Internet, a famously decentralized system that has historically competed with and prevailed against “walled‐garden” alternatives like AOL’s and CompuServe’s information services. Then there’s email, which at its core is a decentralized system based on the Simple Mail Transfer Protocol (SMTP), an open standard. While it does have competition from proprietary messaging systems like Facebook or LinkedIn mail, email has managed to remain the default for person‐to‐person communication online. In the case of instant messaging and text messaging, we have a hybrid model that can’t be categorically described as centralized or decentralized. Finally there’s social networking: despite numerous concerted efforts by hobbyists, developers and entrepreneurs to create alternatives to the dominant centralized model, centralized systems like Facebook and LinkedIn still dominate this space. In fact, this conflict long predates the digital era and we see a similar struggle between the two models in the history of telephony, radio, television, and film.
Decentralization is not all or nothing; almost no system is purely decentralized or purely centralized. For example, email is fundamentally a decentralized system based on a standardized protocol, SMTP, and anyone who wishes can operate an email server of their own. Yet, what has happened in the market is that a small number of centralized webmail providers have become dominant. Similarly, while the Bitcoin protocol is decentralized, services like Bitcoin exchanges, where you can convert
Bitcoin into other currencies, and wallet software, or software that allows people to manage their bitcoins may be centralized or decentralized to varying degrees.
With this in mind, let’s break down the question of how the Bitcoin protocol achieves decentralization into five more specific questions:
1. Who maintains the ledger of transactions?
2. Who has authority over which transactions are valid?
3. Who creates new bitcoins?
4. Who determines how the rules of the system change?
5. How do bitcoins acquire exchange value?
The first three questions reflect the technical details of the Bitcoin protocol, and it is these questions that will be the focus of this chapter.
Different aspects of Bitcoin fall on different points on the centralization/decentralization spectrum. The peer‐to‐peer network is close to purely decentralized since anybody can run a Bitcoin node and there’s a fairly low barrier to entry. You can go online and easily download a Bitcoin client and run a node on your laptop or your PC. Currently there are several thousand such nodes. Bitcoin mining, which we’ll study later in this chapter, is technically also open to anyone, but it requires a very high capital cost. Because of this there has been a high degree of centralization, or a concentration of power, in the Bitcoin mining ecosystem. Many in the Bitcoin community see this as quite undesirable. A third aspect is updates to the software that Bitcoin nodes run, and this has a bearing on how and when the rules of the system change. One can imagine that there are numerous interoperable implementations of the protocol, as with email. But in practice, most nodes run the reference implementation, and its developers are trusted by the community and have a lot of power.
2.2 Distributed consensus
We’ve discussed, in a generic manner, centralization and decentralization. Let’s now examine decentralization in Bitcoin at a more technical level. A key term that will come up throughout this discussion is consensus,and specifically,distributed consensus.The key technical problem to solve in building a distributed e‐cash system is achieving distributed consensus. Intuitively, you can think of our goal as decentralizing ScroogeCoin, the hypothetical currency that we saw in the first chapter.
Distributed consensus has various applications, and it has been studied for decades in computer science. The traditional motivating application is reliability in distributed systems. Imagine you’re in charge of the backend for a large social networking company like Facebook. Systems of this sort typically have thousands or even millions of servers, which together form a massive distributed database that records all of the actions that happen in the system. Each piece of information must be recorded on several different nodes in this backend, and the nodes must be in sync about the overall
state of the system.
The implications of having a distributed consensus protocol reach far beyond this traditional application. If we had such a protocol, we could use it to build a massive, distributed key‐value store, that maps arbitrary keys, or names, to arbitrary values. A distributed key‐value store, in turn, would enable many applications. For example, we could use it to build a distributive domain name system, which is simply a mapping between human understandable domain names to IP addresses. We could build a public key directory, which is a mapping between email addresses (or some other form of real‐world identity) to public keys.
That’s the intuition of what distributed consensus is, but it is useful to provide a technical definition as this will help us determine whether or not a given protocol meets the requirements.
What does this mean in the context of Bitcoin? To understand how distributed consensus could work in Bitcoin, remember that Bitcoin is a peer‐to‐peer system. When Alice wants to pay Bob, what she actually does is broadcast a transaction to all of the Bitcoin nodes that comprise the peer‐to‐peer network. See Figure 2.1.
Figure 2.1 Broadcasting a transactionIn order to pay Bob, Alice broadcasts the transaction to the entire Bitcoin peer‐to‐peer network.
Incidentally, you may have noticed that Alice broadcasts the transaction to all the Bitcoin peer‐to‐peer nodes, but Bob’s computer is nowhere in this picture. It’s of course possible that Bob is running one of the nodes in the peer‐to‐peer network. In fact, if he wants to be notified that this transaction did in fact happen and that he got paid, running a node might be a good idea. Nevertheless, there is no requirement that Bob be listening on the network; running a node is not necessary for Bob to receive the funds. The bitcoins will be his whether or not he’s operating a node on the network.
What exactly is it that the nodes might want to reach consensus on in the Bitcoin network? Given that a variety of users are broadcasting these transactions to the network, the nodes must agree on
Distributed consensus protocol. There are nnodes that each have an input value. Some of these nodesare faulty or malicious. A distributed consensus protocol has the following two properties:
● It must terminate with all honest nodes in agreement on the value
● The value must have been generated by an honest node
exactly which transactions were broadcast and the order in which these transactions happened. This will result in a single, global ledger for the system. Recall that in ScroogeCoin, for optimization, we put transactions into blocks. Similarly, in Bitcoin, we do consensus on a block‐by‐block basis.
So at any given point, all the nodes in the peer‐to‐peer network have a ledger consisting of a sequence of blocks, each containing a list of transactions, that they’ve reached consensus on. Additionally, each node has a pool of outstanding transactions that it has heard about but have not yet been included on the block chain. For these transactions, consensus has not yet happened, and so by definition, each node might have a slightly different version of the outstanding transaction pool. In practice, this occurs because the peer‐to‐peer network is not perfect, so some nodes may have heard about a transaction that other nodes have not heard about.
How exactly do nodes come to consensus on a block? One way to do this: at regular intervals, say every 10 minutes, every node in the system proposes its own outstanding transaction pool to be the next block. Then the nodes execute some consensus protocol, where each node’s input is its own proposed block. Now, some nodes may be malicious and put invalid transactions into their blocks, but we might assume that other nodes will be honest. If the consensus protocol succeeds, a valid block will be selected as the output. Even if the selected block was proposed by only one node, it’s a valid output as long as the block is valid. Now there may be some valid outstanding transaction that did not get included in the block, but this is not a problem. If some transaction somehow didn’t make it into this particular block, it could just wait and get into the next block.
The approach in the previous paragraph has some similarities to how Bitcoin works, but it’s not quite how it works. There are a number of technical problems with this approach. Firstly, consensus in general is a hard problem since nodes might crash or be outright malicious. Secondly, and specifically in the Bitcoin context, the network is highly imperfect. It’s a peer‐to‐peer system, and not all pairs of nodes are connected to each other. There could be faults in the network because of poor Internet connectivity for example, and thus running a consensus protocol in which all nodes must participate is not really possible. Finally, there’s a lot of latency in the system because it’s distributed all over the Internet.
Sidebar: The Bitcoin protocol must reach consensus in the face of two types of obstacles: imperfections in the network, such as latency and nodes crashing, as well as deliberate attempts by some nodes to subvert the process.
One particular consequence of this high latency is that there is no notion of global time. What this means is that not all nodes can agree to a common ordering of events simply based on observing timestamps. So the consensus protocol cannot contain instructions of the form, “The node that sent the first message in step 1 must do X in step 2.” This simply will not work because not all nodes will agree on which message was sent first in the step 1 of the protocol.
Impossibility results. The lack of global time heavily constrains the set of algorithms that can be used in the consensus protocols. In fact, because of these constraints, much of the literature on distributed
consensus is somewhat pessimistic, and many impossibility results have been proven. One very well known impossibility result concerns the Byzantine Generals Problem.In this classic problem, the Byzantine army is separated into divisions, each commanded by a general. The generals communicate by messenger in order to devise a joint plan of action. Some generals may be traitors and may intentionally try to subvert the process so that the loyal generals cannot arrive at a unified plan. The goal of this problem is for all of the loyal generals to arrive at the same plan without the traitorous generals being able to cause them to adopt a bad plan. It has been proven that this is impossible to achieve if one‐third or more of the generals are traitors.
A much more subtle impossibility result, known for the names of the authors who first proved it, is called the Fischer‐Lynch‐Paterson impossibility result. Under some conditions, which include the nodes acting in a deterministic manner, they proved that consensus is impossible with even a single faulty process.
Despite these impossibility results, there are some consensus protocols in the literature. One of the better known among these protocols is Paxos.Paxos makes certain compromises. On the one hand, it never produces an inconsistent result. On the other hand, it accepts the trade‐off that under certain conditions, albeit rare ones, the protocol can get stuck and fail to make any progress.
Breaking traditional assumptions. But there’s good news: these impossibility results were proven in a very specific model. They were intended to study distributed databases, and this model doesn’t carry over very well to the Bitcoin setting because Bitcoin violates many of the assumptions built into the models. In a way, the results tell us more about the model than they do about the problem of distributed consensus.
Ironically, with the current state of research, consensus in Bitcoin works better in practice than in theory. That is, we observe consensus working, but have not developed the theory to fully explain why it works. But developing such a theory is important as it can help us predict unforeseen attacks and problems, and only when we have a strong theoretical understanding of how Bitcoin consensus works will we have strong guarantees Bitcoin’s security and stability.
What are the assumptions in traditional models for consensus that Bitcoin violates? First, it introduces the idea of incentives, which is novel for a distributed consensus protocol. This is only possible in Bitcoin because it is a currency and therefore has a natural mechanism to incentivize participants to act honestly. So Bitcoin doesn’t quite solve the distributed consensus problem in a general sense, but it solves it in the specific context of a currency system.
Second, Bitcoin embraces the notion of randomness. As we will see in the next two sections, Bitcoin’s consensus algorithm relies heavily on randomization. Also, it does away with the notion of a specific starting point and ending point for consensus. Instead, consensus happens over a long period of time, about an hour in the practical system. But even at the end of that time, nodes can’t be certain that any particular transaction or a block has made it into the ledger. Instead, as time goes on, the probability that your view of any block will match the eventual consensus view increases, and the
probability that the views will diverge goes down exponentially. These differences in the model are key to how Bitcoin gets around the traditional impossibility results for distributed consensus protocols.
2.3 Consensus without identity using a block chain
In this section we’ll study the technical details of 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
c r e a t i n g n e w n o d e s a t w i l l . T h e t e c h n i c a l t e r m f o r t h i s i s a Sy b i l a t t a c k .S y b i l s a r e j u s t c o p i e s o f n o d e s 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.
Bitcoin consensus algorithm (simplified)
This algorithm is simplified in that it assumes the ability to select a random node in a manner that is not vulnerable to Sybil attacks.
1. New transactions are broadcast to all nodes
2. Each node collects new transactions into a block
3. In each ro
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com