Cryptographic Adversaries in Blockchain Consensus: Part 1, Overview
Imagine we lived in a world where everyone was honest. Wouldn’t that make all situations where large groups of people have to come to agreement significantly easier? Utopia is quite far from reality, which is why we have computer security techniques, cryptographic primitives, and more recently, blockchain protocols.
Human beings are intrinsically complex and so are their actions. Thus, creating protocols that deal with interactions between many of them is quite a challenging task. Each person is motivated by a unique set of factors and thus responds differently to stimuli. Figuring out the right set of assumptions that apply to the majority of human beings is thus a major step in designing an algorithm to come to an agreement on a common worldview i.e. a consensus protocol.
In consensus protocols, any action that is outside of the expected behavior of a node and is not protocol following is considered malicious. Large degrees of malicious activity could potentially break fundamental assumptions of the protocol and prevent participants in the protocol from ever coming to consensus. This results in either the consensus or blockchain protocol halting in the best case (sometimes called a liveness failure). In the worst case, malicious actors can cause false agreement on multiple inconsistent views or even cause a reversion of agreements that were already made (safety failures). Such situations need expensive external intervention to reboot the consensus algorithm. Thus, creating protocols with the right set of assumptions is critical in order to minimize expensive operations.
The first set of consensus protocols that were developed tended to operate under simple adversarial assumptions. The goal was just for a predetermined set of nodes to come to an agreement by assuming an environment which had no malicious actors. This is a trivial problem and once such protocols were designed, the natural next step was to improve them. Protocols that could not handle any sort of faults or malicious actions were impractical to implement in certain settings, such as the internet. These protocols required all the participating nodes to be known ahead of time and for all of these nodes to remain online in addition to always acting honestly in order for the protocol to terminate correctly. This was impractical because if even one node went offline because of an unstable communication channel, it could prevent consensus.
Neither fiber optic cables nor the internet itself provides reliable enough communication channels. In the case of a power outage or a disconnection of a wire, the system would fail.
In order to build a system that was practically more beneficial in unstable environments, the system had to at minimum tolerate nodes going offline. It couldn’t assume that all nodes were completely honest. Thus came the earliest assumptions on what kinds of security breaches protocols can tolerate through the creation of malicious actors called adversaries.
Types of Adversaries
The first method of classifying adversaries was based on the most powerful action that adversary could take. The simplest adversaries of this kind were just nodes that would go offline permanently. This sort of protocol-deviating behavior on the part of a node was a called crash fault. Nodes going offline happens when there is any sort of disruption or termination in the internet connection. To expect multiple nodes globally to stay online all the time over the internet is impractical because any power outage can cause a node to go offline. Nodes may also go out of sync for a few seconds if packets over the internet are dropped or delivered late. The internet itself is not sufficiently secure and works on a “try my best” to deliver packets approach. Therefore, it is unreasonable to expect that all information will be exchanged in a timely manner and that all nodes will always remain online. As such, protocols that were crash fault tolerant played an important role in the development of consensus algorithms that could actually work on the internet.
The next iteration of protocols handled adversaries that could eavesdrop on messages sent between users. Those adversaries could infringe on the privacy of the communicating parties by reading messages that weren’t meant to be shared with anyone else. These adversaries were called passive adversaries. The goal of this type of adversary was to impersonate the honest participants after eavesdropping on multiple rounds of the protocol. These adversaries were a threat to protocols where confidential information was supposed to be transmitted. These adversaries were also a threat because a minority of dishonest actors were able to affect the value that the majority of honest actors agreed upon since the minority could impersonate other honest actors. These types of adversaries were studied in the 1970s and 1980s. Encryption and Public Key Infrastructure are techniques used to retain privacy, data integrity, and security in the Passive Adversarial Model.
Naturally, the next step was for protocols to handle adversaries that could use the information which they gathered to act arbitrarily. This could include sending false or conflicting messages. These adversaries were called Byzantine or active adversaries. The term Byzantine originates from a landmark paper written in 1982 by Leslie Lamport called “The Byzantine Generals problem”. The paper describes the problem of consensus that the Byzantine army surrounding a city faces as they try to come to an agreement on if they should all attack or retreat. As they try to come to an agreement, they face issues with messages getting dropped, duplicated and altered. These messages are delivered out of order by an unreliable messenger and the dishonest generals try to confuse the rest of the army with contradictory messages. The goal of the dishonest generals is to ensure that the army loses the war by splitting up the efforts of the army having some of the generals attack while having the others retreat or not act at all. Despite all of these challenges, the goal of all honest generals is to act in one common way.
Similarly, any public blockchain consensus protocol would have to be able to grow and remain consistent despite arbitrary attacks. Users of certain applications may not want some transactions to ever be recorded on the blockchain and might actively act maliciously and try to censor these transactions. Examples of these include front-running attacks, double spend attacks, and transaction censorship attacks to prevent the settlement of payment channels. These attacks are to be anticipated once there is a huge financial ecosystem relying on the blockchain and the protocol needs to be able to tolerate these attacks in order for it to be practically usable at a large scale. Thus, public blockchain consensus protocols have to be Byzantine fault tolerant.
The strength of an adversary, however, is more than just the most drastic action that the adversary can take. It also involves consideration of the time it takes for the adversary’s action to take effect or the time it takes for adversaries to corrupt different participants of the network.
Another way of classifying adversaries is based on how long it takes an adversary to corrupt another node after they have decided who to corrupt. If the adversary can instantaneously corrupt participants, the adversary is called “strongly adaptive”. In “static” adversarial models, the adversary is allowed to choose the participants that they want to corrupt at the start before the protocol execution starts. After that point, no changes can be made. Adversaries which take some time (longer than instantaneous but less than infinite time) to corrupt participants of the protocol are called “mildly adaptive”. The time it takes for an adversary to corrupt a participant of the protocol is related to the process by which validators and committee members are selected.
The strength of an adversary is also closely tied with the computational and storage limits placed on the adversary. If the adversary is assumed to have some fixed amount of resources, then we can assume a model which is computationally secure. The common assumption of most protocols is the existence of a polynomially bounded adversary. This means that an adversary cannot in a polynomial number of steps / time /space break any of the primitives of the protocol. This also means that the adversary can with a very small probability break the security of the protocol. This is often sufficient since it translates to an adversary taking over 50–60 years to break primitives with this level of security. On the other hand, if the adversary is assumed to be extremely rich and powerful, the protocol would have to be statistically secure. This means that even with infinite computing resources and a billion years, the adversary shouldn’t be able to break the protocol. Most cryptographic primitives used in practice are only computationally secure. This is sufficient security until quantum computers become widespread.
Economic Adversaries
So far, we considered assumptions that stem from computation and storage considerations. All of these assumptions focus actors who have decided they want to attack the system. All public blockchain consensus protocols are a lot more complex and need to often deal with more than adversaries who are sure they want to attack the system. For public blockchain protocols to sustain themselves in the long run, economic assumptions that relate to how actors respond to incentives are an important aspect to get right. These are important because they determine what incentivizes someone to act honestly and follow the protocol in the first place. There are three kinds of actors in any system. The first is economically rational, the second is altruistic and the third kind is irrational malicious. Majority of the blockchain protocols designed don’t align incentives for the economically rational actors to always follow protocol and this leads to the several attack vectors that might be unaccounted for at merely the protocol level.
In part 2 of this blog post, we will cover an analysis of some protocols that we looked at in our Meta-Analysis of Alternative Consensus Protocols based on adaptiveness of the adversaries that each of them can handle. For a more detailed description of why these are the adversarial models, read about the randomness generation schemes of each of these protocols.
Having an understanding of adversarial models is crucial to designing secure systems. There is still a lot of work to be done with respect to modeling humans behavior and creating blockchain protocols. While we have come quite far, there are still several assumptions about the systems we create that if broken could render these protocols useless. As Vitalik says “Cryptoeconomics is about agents with IQ 5 trying to control agents with IQ 150 ”. Human behavior is always hard to model, but with the emergence of fields like Cryptoeconomics, we get closer to capturing the multiple layers of human complexity in the systems we design. Even so, there still are a lot of solutions that are outside the field of Cryptoeconomics. A combination of developing new fields and re-using old concepts and ideas in clever ways is going to yield several new ways of modeling adversaries and designing more secure systems.
Twitter: @aparnalocked
Acknowledgments: I would like to thank Zubin Koticha, Alexis Gauba, and Sunny Aggarwal for their help in writing this post.
