Bitcoin Classroom: Impossible Results

Impossibility results. The lack of a notion of global time severely limits the set of algorithms that can be used for consensus protocols. In fact, much of the literature on distributed consensus is somewhat pessimistic because of these limitations, and many impossible results have been proven. A famous impossible result involves the Byzantine Generals Problem, a classic problem in which the Byzantine army is divided into several legions, each commanded by a general, who communicate with each other through messengers to develop a joint action plan. Some generals may be traitors and deliberately try to sabotage, so that the loyal generals cannot reach a unified plan. The goal of this problem is to get all loyal generals to reach a consistent plan and prevent traitorous generals from making them accept a bad plan, which has been proven to be impossible when more than a third of the generals are traitors.

A more subtle impossibility result is called the Fisher-Lynch-Patterson Impossibility Result, and is famous for the names of the authors who first proved it. Under some conditions that involve nodes behaving in a deterministic way, they showed that consensus is impossible with just one faulty process.

Despite these improbable results, some consensus protocols have been mentioned in the literature, one of the more famous of which is Paxos. Paxos made some compromises, on the one hand it did not produce a discontinuous result, on the other hand, although it was rare, it accepted trade-offs under certain conditions, resulting in the protocol being stuck in a quagmire and not making any progress.

Breaking traditional assumptions. However, there is some good news: these improbabilities are demonstrated in a specific model used to study distributed databases, and this model does not translate well to the Bitcoin setting, because Bitcoin violates many of the assumptions made by the model. In some ways, they tell us more about the model than they tell us about the problem of distributed consensus.

Ironically, as recent research has shown, consensus in Bitcoin works better in practice than in theory. In other words, we have observed consensus working, but we have not developed a perfect theory to explain how it works. However, developing such a theory is important because it can help us predict some unexpected attacks and failures, and only when we have a strong theoretical understanding of how the Bitcoin consensus mechanism works can we ensure the security and stability of Bitcoin.

What assumptions in the traditional consensus model does Bitcoin violate? First, it introduces the concept of incentives, which is very novel for a distributed consensus protocol. It is only feasible in Bitcoin because it is a currency and thus has a mechanism to incentivize participants to act honestly. So Bitcoin does not solve the distributed consensus problem in general, but it solves it in the specific sense of a monetary system.

Second, Bitcoin embraces the idea of ​​randomness. As we will see in the next two sections, Bitcoin’s consensus algorithm relies heavily on randomization. In addition, it does away with specific start and end times for consensus to occur, instead consensus occurs over a longer period of time, in practice about an hour. But even at the end of an hour, nodes cannot guarantee that any particular transaction or block has made it into the ledger. Instead, as time goes on, the chances that you believe some block will be agreed upon get higher and higher, and the chances of disagreement decrease exponentially. The difference in these models is the key to how Bitcoin is able to circumvent the traditional impossible results for distributed consensus algorithms.