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