Consensus in Bitcoin: One system, many models

At a technical level, the Bitcoin protocol is a clever solution to the consensus problem in computer science. The idea of consensus is very general — a number of participants together execute a computation to come to agreement about the state of the world, or a subset of it that they’re interested in.

Because of this generality, there are different methods for analyzing and proving things about such consensus protocols, coming from different areas of applied math and computer science. These methods use different languages and terminology and embody different assumptions and views. As a result, they’re not always consistent with each other. This is a recipe for confusion; often people disagree because they’ve implicitly assumed one world-view or another. In this post I’ll explain the two main sets of models that are used to analyze the security of consensus in Bitcoin.

The traditional application of consensus is to distributed databases. A good example is a data center with numerous nodes that all operate on the same data. The system must defend against failures of its components, but failures of a relatively benign kind —  nodes may crash, or at worst, behave randomly. As malware and attacks over the Internet became more common, distributed consensus researchers also studied Byzantine faults where nodes may be taken over by an adversary and may behave in an arbitrary way. In this field of research the usual goal is to prove that consensus is or isn’t possible in various scenarios. Some percentage of nodes are assumed to be “honest,” which means that they always follow a specified protocol, and others are “malicious,” which means that they may deliberately try to subvert the protocol.

When Bitcoin came along, people looked for models to analyze its behavior, and the Byzantine consensus model looked like a decent fit, provided we make some tweaks. In particular, in Bitcoin when we talk about fractions of nodes we must weight them by hash power. This is the model that the original paper uses to analyze security, as well as several follow-up works.

But notice how different Bitcoin is from the traditional applications that the model is meant for. In a distributed system it’s a good bet that a system administrator will notice that something is wrong before too many nodes get compromised, and fix them, so it makes sense to assume that some fraction of nodes are always honest. But what compels any Bitcoin node or miner to follow the protocol?

In fact, miners have powerful monetary incentives, and one argument is that they’ll try and maximize their profits, regardless of whether or not that means following the protocol. The branch of math that studies the behavior of interacting participants who follow their incentives is called game theory. This is the other main set of models that’s been applied to Bitcoin.

In this view, we don’t classify nodes as honest and malicious. Instead, we assume that each node picks a (randomized) strategy to maximize its payoff, taking into account other nodes’ potential strategies. If the protocol and incentives are designed well, then most nodes will follow the rules most of the time. “Honest” behavior is just one strategy of many, and we attach no particular moral salience to it.

This model has a certain elegance to it, and avoids assumptions that look arbitrary and are hard to justify, such as 50% of nodes being honest. In practice there is some diversity of client implementations, and the protocol evolves over time, so even to designate some behavior as honest is somewhat arbitrary.

But elegance of the theory is not enough. Can we effectively model the system with all its interacting components in the language of strategies and payoff-maximization? Is the resulting model tractable — can we analyze it mathematically or using simulations? And most importantly, do its predictions match what we observe in practice? I’ll discuss these questions in a follow-up post.