Monday, May 4th, 2020

From the Inside: Proofs, Consensus, and Decentralizing Society

In 1972, NASA chartered a team of scientists to design a flyable SIFT (software implemented fault tolerance) computer that could demonstrate the feasibility of an integrated function, fault-tolerant computer in commercial aviation. SIFT deployed replicated computers to overcome failures via majority voting, giving birth to the fundamental problem of reaching consensus among a network of computers. The SIFT team wanted a catchy story to exemplify the consensus problem, and it came up with an army of Byzantine generals coordinating an attack. To this day, the Byzantine generals problem models the core ingredient of reliability in distributed systems, and the term Byzantine fault tolerance (BFT) is used for capturing arbitrary faults.

Fast-forward to 2008, when an author publishing under the name Satoshi Nakamoto proposed the creation of a global cryptocurrency, Bitcoin, that relies on the Byzantine generals problem for maintaining a history of digital payments. The requirements here in scalability and functionality far exceed anything ever envisioned before. Furthermore, the Nakamoto solution to the Byzantine generals problem harnesses economic behavior to drive network participants to cooperate. Thus, the new field of crypto-economic systems was born.

The crux of the crypto-economic systems disruption is the enablement of programmable financial resources without trusting any centralized service. Three disciplines jointly contribute to automated decentralized trust: cryptography, distributed computing, and economics.

The Fall 2019 Simons Institute program on Proofs, Consensus, and Decentralizing Society brought together cross-domain experts from cryptography, distributed computing, and economics to discuss the mechanisms that bring parties to implement automated decentralized solutions.

Cryptographic schemes that enable parties to interact securely
Crypto-economic systems enable automated business-to-business interaction with payments integrated as part of the digital interaction. This brought increased attention to mechanisms that enable secure interaction among untrusted parties.

A core notion that underlies secure interaction between untrusted parties is a proof system. Loosely speaking, proofs enable an untrusted party to send some derivation of confidential information without giving up control completely over the information. For example, in a zero-knowledge proof, a party proves possession of a secret without leaking any of the secret bits. A hiding commitment is a proof that binds a secret to a value without leaking any secret bits, so that the secret can later be verified. There are many other proof scenarios.

Many proof techniques in cryptography were originally conceived as purely theoretical methods. Pioneering work such as Fairplay demonstrated two decades ago that end-to-end SMPC (secure multi-party computation) across a wide interconnect is within the realm of possibility, at least on a small scale. Tremendous advances have been made since then in SMPC and other methods such as probabilistically checkable proofs, zero knowledge, and oblivious RAM. Some of these advances have already brought to production methods such as zero-knowledge proofs. The exploration of practicality enhancements continues to thrive and receives additional boost from crypto-economic systems.

The first workshop of the semester, Probabilistically Checkable and Interactive Proof Systems, was co-organized by Omer Paneth, Ron Rothblum, and Justin Thaler and took place the week of September 23 to 27, 2019. The workshop was devoted to probabilistically checkable proofs, interactive proofs, zero-knowledge proofs and arguments, and their applications. Topics of interest included both the theoretical foundations of such proof systems and research efforts devoted to practical efficiency. A major goal of the workshop was to bring together researchers studying proof systems from all points on the “foundations vs. practice” spectrum.

Distributed protocols that implement coordination among parties
Distributed consensus is a core abstraction in which a set of nodes, some of which may exhibit crash or Byzantine faults, aim to reach agreement on the state of some system or a log of events. Due to the recent interest in decentralized cryptocurrencies and their applications, distributed consensus has received heightened attention from both the cryptocurrency and academic communities. From the communities’ joint efforts at deploying consensus on an Internet scale, we have achieved a new leap in our understanding of consensus. We also understand the new challenges that have come with the large-scale and decentralized nature of the deployments — challenges that were not there classically when we considered reaching consensus among three nodes on a spaceship or among a dozen nodes within a single organization.

The second workshop of the semester, Large-Scale Consensus and Blockchains, took place from October 22 to 25, 2019, and was co-organized by Dahlia Malkhi (Calibra) and Elaine Shi (Cornell University).

The workshop brought together researchers interested in distributed consensus, including representatives of the distributed systems, cryptography, and economics communities. The workshop was structured as a mix of keynotes and research presentations. It began with a day featuring four distinguished keynote talks: Barbara Liskov on the genesis of BFT consensus and on current atomic cross-chain transactions, Christian Cachin on decentralized trust models and Stellar, Maurice Herlihy on guarantees of cross-chain transactions, and Tal Rabin on managing threshold cryptography in decentralized settings. The following two days were filled with research talks by students, faculty, and industry researchers. The last day was dedicated to cross-disciplinary works on blockchain/consensus and game theory.

Mechanisms that incentivize parties to cooperate
The crypto-economic disruption goes deeper than the libertarian Bitcoin vision of digital money without government. This necessitates deep study into various societal aspects of the disruption.

Many studies cross several domains, including computer science, market design, and game theory. For example, various works over the past few years provide game theory analysis of Nakamoto consensus safety. Other works include empirical studies of financial activity in the Bitcoin and Ethereum networks, e.g., transaction front-running and arbitrage. In the future, more work will be needed to understand the foundations of mechanisms that govern decentralization of Nakamoto consensus and/or new consensus algorithms.

Crypto-economic systems could have a potentially vast impact on the very fabric of economics and society. It is essential to understand the responsibilities that the technology bears concerning customer protection and the prevention of bad usage, such as terrorist activity. Much more cross-domain work will incorporate law, economics, and computer science considerations in order both to identify the gaps that this disruption has created and to innovate to help society understand and embrace it.

The final workshop of the semester, Blockchain in Society: Applications, Economics, Law, and Ethics, was co-organized by Abhi Shelat, Helen Nissenbaum, and Peter Van Valkenburgh and took place from November 18 to 22, 2019. The workshop was devoted to questions concerning technical, economic, legal, and ethical implications of recent advances in consensus, blockchain data structures, and zero-knowledge proofs.

Related articles