Beyond 51% attacks: Precisely characterizing blockchain achievable resilience
A central question in the security of blockchains is what percent of validators adversaries can control while the blockchain remains safe and live. Is it 50%? 33%? Or, as Vitalik Buterin has written, 99%? A great deal rests on the answer. If there is a way to achieve resilience even against adversaries that control almost all of a blockchain’s security-critical resource, why do almost all deployed blockchains content themselves with less?
The answer to what percentage is right depends on how clients are modeled. Are the clients sleepy or always-on? Are they silent or communicating? Can validators be sleepy too? And is the network synchronous or partially synchronous? In a new paper, we (with Dionysis Zindros of Common Prefix, and David Tse of Stanford University and BabylonChain) systematize models for consensus across these four dimensions. Being systematic about the nature of clients allows us to tightly characterize the achievable safety and liveness resiliences with matching possibilities and impossibilities for each of the sixteen models. We’re able to unify folklore and earlier results, and fill gaps left in the literature with new protocols and impossibility theorems.
One of our key takeaways is that when clients in a blockchain system can communicate reliably (that is in particular, if clients can forward messages they receive to each other — which is the case for many blockchains that use gossip-style peer-to-peer networking) then the system can remain safe even if the adversary controls all of the blockchain’s security-critical resource.
State-machine replication: Background
State-machine replication (SMR) consensus protocols are the backbone of blockchain systems. These protocols provide a mechanism with which the blockchain’s parties can reach consensus on an order in which to execute incoming transaction requests. Think of this as every party at every point in time outputs a sequence of transactions that it considers confirmed, and then executes those transactions in that order. By executing transactions in the same order, each party effectively runs a replica of the state machine of the blockchain’s execution engine. An SMR consensus protocol is secure if it provides two properties: safety, meaning that transactions are confirmed in the same order across honest parties and across time (i.e., one party’s confirmed transaction sequence is a prefix of any other’s, or vice versa); and liveness, meaning that honest transaction requests are eventually included in every party’s confirmed transaction order.
The SMR consensus protocols used in blockchains must be Byzantine-fault tolerant (BFT), that is, they should provide each security property even if a fraction of the parties behave adversarially. The adversary fraction of validators, the parties tasked with reaching consensus, up to which safety and liveness can be guaranteed — whether that’s 33%, 50%, or Vitalik’s 99% — are called safety resilience and liveness resilience of the protocol, respectively.
So what’s the tolerable percentage of malicious validators?
The question, then, is: What is the best possible safety/liveness resilience any blockchain protocol could hope to achieve? Is it 33%, 50%, or 99%? Decades ago, researchers showed that the answer depends on the reliability of the communication network connecting validators of the blockchain: If the network is guaranteed to deliver messages between honest validators within a short period of time (we call this setting synchronous), then higher resiliences can be achieved than if the network may suffer from outages like network partitions where network delay can become quite large (a setting called partial synchrony). This explains some of the conundrum — namely, the difference of 33% and 50% resilience between some protocols.
But the answer also critically depends on the modeling details of clients. Client modeling assumptions determine the extent to which 99% resilience can be achieved.
But first, what are clients? Blockchains comprise not only validators — active participants in the consensus protocol, such as stakeholders in a proof-of-stake blockchain. There are also clients. While they do not actively contribute to consensus, they represent the users of the system, who, for instance, may run wallet software and monitor the chain for payments and ship merchandise in response. The characteristics of those clients matters a lot: Are these clients sleepy — occasionally taking a prolonged break from following the chain, or always on? Are they silent, or can they communicate with other clients? Speaking of sleepiness: Can validators be sleepy, too? The answers to these questions determine if and how 99% resilience can be achieved.
In our new paper, we systematize models for BFT SMR consensus across four dimensions: sleepy/always-on clients, silent/communicating clients, sleepy/always-on validators, and network synchrony/partial-synchrony. We then tightly characterize the achievable safety and liveness resiliences with matching possibility results and impossibility results for each of the resulting sixteen models. This means that for every safety/liveness resilience pair, we either show a protocol that achieves it, or we prove mathematically that there cannot be any protocol that achieves it. The following figure summarizes the results (cf Figure 1 in the paper to understand which regions of which plot are new or found in earlier works, respectively).
Specifically, the figure shows the safety/liveness resilience pairs achievable or unachievable for each of the models considered. The liveness resilience is on the horizontal axis, and the safety resilience is on the vertical axis. Blue shaded regions are resilience pairs that are achievable, and red shaded regions are the ones that aren’t. Earlier works have focused on the first and last row (sleepy silent clients and always-on communicating clients), and on the left and right columns (classical synchronous and partially synchronous networks, both with always-on validators). For instance, the classic 50% and 33% results are shown in sub-figures (a) and (c), respectively, while Vitalik Buterin’s 99% result is found in sub-figure (j). Our contributions are in the second and third row (always-on silent clients and sleepy communicating clients) as well as the middle column (sleepy validators). (In the four remaining scenarios corresponding to partial synchrony with sleepy validators: No resilience can be achieved in these settings due to the availability-finality dilemma, so the respective plots would be all red, and are omitted in the figure.)
The upshot? When clients in a blockchain system can communicate, which is the case for many blockchains that use gossip-style peer-to-peer networking, then safety/liveness resilience can be increased beyond 50% under some circumstances — for example, in sub-figure (g), with synchronous, always-on validators and sleepy but communicating clients, one of the resiliences (safety or liveness) can be increased to 99% while retaining 50% for the other resilience (liveness or safety). This is an example of how we can build on folklore with more careful analysis, and combine 50% with 99%.
If you want to know more, check out the paper on IACR ePrint.
***
Joachim Neu is a postdoc Research Associate at a16z Crypto Research. Previously, he earned a PhD at Stanford, advised by David Tse. His current research focus is blockchain-era consensus and decentralized-systems security. His broader interests include distributed computing and systems, applied cryptography, and networking and communications.
Srivatsan Sridhar is a PhD student at Stanford University, advised by David Tse, and a senior researcher at BabylonChain. He has also held internships with Mysten Labs, Protocol Labs, and Subspace Labs.
Ertem Nusret Tas is a PhD student in Electrical Engineering at Stanford University, working under the supervision of David Tse. He has also held internships with Celestia, BabylonChain, and a16z crypto research.
***
The views expressed here are those of the individual AH Capital Management, L.L.C. (“a16z”) personnel quoted and are not the views of a16z or its affiliates. Certain information contained in here has been obtained from third-party sources, including from portfolio companies of funds managed by a16z. While taken from sources believed to be reliable, a16z has not independently verified such information and makes no representations about the current or enduring accuracy of the information or its appropriateness for a given situation. In addition, this content may include third-party advertisements; a16z has not reviewed such advertisements and does not endorse any advertising content contained therein.
This content is provided for informational purposes only, and should not be relied upon as legal, business, investment, or tax advice. You should consult your own advisers as to those matters. References to any securities or digital assets are for illustrative purposes only, and do not constitute an investment recommendation or offer to provide investment advisory services. Furthermore, this content is not directed at nor intended for use by any investors or prospective investors, and may not under any circumstances be relied upon when making a decision to invest in any fund managed by a16z. (An offering to invest in an a16z fund will be made only by the private placement memorandum, subscription agreement, and other relevant documentation of any such fund and should be read in their entirety.) Any investments or portfolio companies mentioned, referred to, or described are not representative of all investments in vehicles managed by a16z, and there can be no assurance that the investments will be profitable or that other investments made in the future will have similar characteristics or results. A list of investments made by funds managed by Andreessen Horowitz (excluding investments for which the issuer has not provided permission for a16z to disclose publicly as well as unannounced investments in publicly traded digital assets) is available at https://a16z.com/investments/.
The content speaks only as of the date indicated. Any projections, estimates, forecasts, targets, prospects, and/or opinions expressed in these materials are subject to change without notice and may differ or be contrary to opinions expressed by others. Please see https://a16z.com/disclosures for additional important information.