Theory of blockchains (and some applications)
Back in June, I attended the first IACR Summer School on Blockchain Technologies. Cryptocurrency experts from around the world gathered on a small Greek island to impart their wisdom to students, and discuss the following intriguing questions (among others):
- What are the problems that a blockchain solves?
- What are the essential features of blockchains that enable solving these problems?
- Can we do it better? How?
- What are the problems that blockchains do not solve?
- What else can we use these ideas for?
Several months later, I’ve finally quit procrastinating and put together a post summarizing some of the interesting topics discussed. It is intended to be neither comprehensive nor representative of the breadth of talks at the summer school; it simply comprises some bite-size summaries of topics that I happened to write about, with a bias towards the theoretical underpinnings of Bitcoin/blockchains. (I also mention some related work that I learned about independently.) The full summer school program, including slides from all the talks, is available online.
The ability of Bitcoin’s blockchain to achieve consensus is considered by some to be one of its most powerful features. Technologists and entrepreneurs alike seem excited by the potential of blockchains to address problems in diverse new domains including personal insurance, land registry, and others. But before we get too excited: what’s consensus? In fact, it has a precise technical definition stemming from decades of research in theoretical computer science.
The consensus problem is a famous problem in the field of distributed computing which is deceptively simple to state. When many parties are communicating over a network, and some fraction of the parties may crash or behave maliciously, how can all the (honest and not crashed) parties agree on a common value? Surprisingly, this simple task can be very hard or even impossible, depending on the type of protocol and network you have.
The consensus problem (sometimes also called the Byzantine Generals problem) was first proposed more than three decades ago. In asynchronous networks (i.e., networks where messages may be transmitted with variable delays), a classic result from 1982 showed it is unsolvable by any deterministic protocol if even one party is faulty. Even for randomized protocols, in the setting where the malicious parties can change over time, only very inefficient protocols were known for twenty-some years, until a recent breakthrough that gave an expected-polynomial-time protocol that works as long as no more than a 1/500 fraction of parties are faulty.
And yet, in some sense, Bitcoin efficiently solves the consensus problem on the world’s biggest asynchronous network: the Internet. Everyone in the Bitcoin network agrees on a common value: namely, the blockchain that records all transactions that happened in Bitcoin since its beginning. How can this be? Well, Bitcoin is designed for robustness in the presence of profit-seeking parties (“Bitcoin miners”) who do not try to disrupt the protocol in arbitrary ways, but will only behave in ways that are likely to increase their profit. In game theory, such parties are known as rational agents. Analyses of the stability and consensus properties of Bitcoin (e.g., Satoshi Nakamoto’s original paper) and other cryptocurrencies all depend on the assumption that parties in the network behave rationally. Since rational behavior is a subset of all possible (adversarial) behavior, this assumption restricts the behavior of bad parties, and therefore allows for protocols that achieve some strong properties (such as agreement) which are impossible in the case of truly adversarial behavior.
The Bitcoin “backbone”
This recent paper aims to distill the core features of the Bitcoin protocol that are important for achieving consensus. They call these core features the “Bitcoin backbone”: they formally define a Bitcoin backbone protocol and analyze and prove desirable properties of this protocol under well-defined model settings. The properties they prove include
- common prefix (i.e., the blockchains maintained by honest players will share a large common prefix) and
- chain quality (i.e., the blockchain contains at least a certain fraction of blocks contributed by honest miners, with overwhelming probability).
Decoupling the incidental protocol features of Bitcoin from those that really matter for achieving its core goals is a great idea, and the work of Garay et al. made a pioneering step in this direction. Their analysis is done in a fairly restricted model, however, which is in several respects far from the reality of cryptocurrencies on the Internet: for example, among the simplifying assumptions made are that the network is synchronous and that the number of parties (miners) is fixed.
This research direction has been developing further, towards achieving rigorous analyses in other, sometimes more realistic models. Ultimately, developing a model that is both complex enough to capture “most” relevant aspects of a real-world system and yet simple enough to allow for rigorous analysis would involve striking a very elusive balance between the idealized world of theory and the chaotic world of real systems. Theory for theory’s sake can be beautiful; that said, I think it’s worth remembering that formal analyses of blockchains are fundamentally trying to usefully model an observed phenomenon, rather than an end unto themselves. It will be interesting to see where this goes.
Building things based on the blockchain
A recently popular perspective is to view the blockchain as a tool — a means to an end, rather than an end in itself — and to consider what interesting functionalities can be achieved assuming that a blockchain infrastructure such as Bitcoin already exists.
Before diving in deeper, I want to draw a distinction between two similar-sounding concepts. Building cryptography based on the blockchain is different from using blockchains (primarily) for a purpose other than Bitcoin/cryptocurrency. Many of Bitcoin’s desirable properties depend crucially on the assumption that participants are rational and seek to maximize their monetary gain. This, in turn, hinges on the cryptocurrency that is inherent in the Bitcoin mining infrastructure. It is thus intriguingly unclear whether “removing the cryptocurrency aspect” from the Bitcoin blockchain design can be a useful approach to building other (cryptographic) tools that leverage desirable properties of Bitcoin.
A perhaps more straightforward question to ask is: can we build better cryptographic tools by using Bitcoin’s blockchain? That is, we’re not seeking to adapt the Bitcoin protocol itself. Instead, we’re asking:
Given that Bitcoin exists, can we do certain tasks more efficiently and/or securely?
The answer seems to be yes, for a number of tasks not limited to:
- Fair multi-party computation
- Securely outsourcing computations to the cloud
- Verifiable lotteries
Fair computation. Multiple recent papers in this direction have shown how to bypass a long-standing impossibility result in secure multi-party computation by using Bitcoin (and invoking the assumption that participants behave to maximize monetary gain). The impossibility result says roughly the following: if Alice and Bob have inputs x and y respectively, and they want to run a secure protocol to compute the output of some function z=f(x,y) on their inputs, then it is impossible to guarantee that both Alice and Bob will learn z. The intuition is that it is not possible to guarantee that Alice and Bob learn z at exactly the same moment, and whoever learns z first could quit as soon as they learn it, thereby “running away with the answer” before the other person learns it. This can be very undesirable in certain settings: e.g., if Alice and Bob have pooled their knowledge of the stock market and z is the resulting investment advice.
In a nutshell, the recent research has taken the approach of using Bitcoin to incorporate a penalty (implemented by a clever combination of Bitcoin scripts / smart contracts) for “running away with the answer,” thereby incentivizing rational participants to complete the protocol such that all parties learn the answer.
Secure outsourcing. People and companies are storing increasing amounts of data not on their own computers and disk drives, but on the “cloud,” which means that the data is physically stored somewhere else and entrusted to an external entity’s care (e.g., entrusted to Google, Apple, Amazon, etc.). More and more, not only is data being stored elsewhere, but it’s also being computed on elsewhere. That raises questions of privacy (who gets to see the data while it’s being computed on?) and authenticity (how can I be sure that the computation was performed correctly if I didn’t run it myself?). “Do the computation yourself if you’re so worried” is not a satisfactory answer: cloud computation offers many advantages that society would like to reap, and in some cases (e.g., scientific/medical research involving big data), performing computations oneself may be prohibitively costly or time-consuming. One approach to this problem is verifiable computation, in which the cloud is required produce a short, easily-checkable proof that a computation was performed correctly. (It’s important that the proof is short and easily checkable, since we’re interested in keeping the client’s workload minimal.) A recent alternative proposal has suggested using monetary penalties, implemented via cryptocurrencies and smart contracts, to incentivize correctness of cloud computations.
Verifiable lotteries. Many common processes require randomness, and sometimes there are high stakes involved: lotteries with monetary prizes are an obvious example; others include the “random” choice of children to be admitted to oversubscribed public schools, applicants for subsidized housing, or ballots to be examined in a post-election audit.
How can we be sure that these processes are really random? Truly unpredictable randomness can be essential towards achieving fairness, reducing corruption and institutional bias, and preserving the integrity of democratic processes.
One approach is to try to guarantee randomness by physical processes: drawing lottery tickets blindfolded out of a well-shaken hat, for example. But such processes can be rigged, and it’s even harder to win the confidence of people who can’t be physically present. In an ideal world, we would like to have a universally trusted third party who sits in a tower isolated from world events, and spends all day rolling fair dice and announcing the outcomes (in a way that is unforgeable and visible to everyone in the world). Given that this seems a slightly tall order, a number of more practical proposals have arisen, involving the “extraction” of randomness from empirically hard-to-predict data sources such as detailed weather patterns, radioactive decay, closing prices of stocks, or the Bitcoin blockchain. A recent paper gives a formal treatment of using the blockchain for publicly verifiable randomness. Of course, if you run a lottery with high enough stakes based on the blockchain, attackers will be incentivized to attack the blockchain in order to manipulate the outcome: accordingly, the paper includes an analysis of how high the stakes would have to be (around $10,000) for such attacks to be a rational concern.
I’m curious about the limits of what’s possible and what’s not in a world where blockchains exist. Hopefully I’ve provoked your curiosity too.
The author of this post is a Ph.D. student in cryptography at MIT (CSAIL), and a member of the Digital Currency Initiative at the MIT Media Lab. Many thanks to the Digital Currency Initiative and the summer school sponsors for jointly supporting my trip to the summer school!