Science and Engineering of Consensus
An affiliated workshop of The Science of Blockchain Conference 2022
Sponsored by: 
Recordings: https://www.youtube.com/playlist?list=PL4XSNxeZhdqBBgqqokIdK4PcyPSl6t0rQ
Program
- 12:30: Registration / coffee & snacks
- 1:00: Welcome
- 1:10-2:25: Session 1 (Chair: David Tse)
- 1:10: Aggelos Kiayias — Ledger consensus with dynamic availability - From Bitcoin to Ouroboros — Recording
- 1:35: Christian Cachin — Beyond Asymmetric Byzantine Quorum Systems — Recording
- 2:00: Ari Juels — Fair Transaction Ordering: Why and How — Recording
- 2:25: Coffee break (20min)
- 2:45-4:25: Session 2 (Chair: Joachim Neu)
- 2:45: Dawn Song — Scaling Blockchains with EVM-native Interactive Fraud Proofs — Recording
- 3:10: Alexander Spiegelman — DAG Meets BFT - The Next Generation of BFT Consensus — Recording
- 3:35: Dahlia Malkhi — Maximal Extractable Value (MEV) Protection on a DAG — Recording
- 4:00: Mohammad Alizadeh — DispersedLedger: High-Throughput Byzantine Consensus on Variable Bandwidth Networks — Recording
- 4:25: Coffee break (20min)
- 4:45-6:00: Session 3 (Chair: Sreeram Kannan)
- 4:45: David Tse — Bitcoin-Enhanced Proof-of-Stake Security: Possibilities and Impossibilities — Recording
- 5:10: Oren Katz — Challenges in consensus protocols for Validity Rollups — Recording
- 5:35: John Adler — Proof-of-Stake in the Model of Accountability — Recording
- 6:00-8:00: Dinner reception
Abstracts
- Aggelos Kiayias — University of Edinburgh and IOG
Ledger consensus with dynamic availability - From Bitcoin to Ouroboros
Blockchain protocols like the Bitcoin blockchain continuously organise
transaction input in the form of a ledger so that participating nodes reach consensus about
an ever extending common prefix of transactions. An essential requirement for such protocols is to
satisfy safety and liveness in the presence of an adversary despite the fact that
honest participants are dynamically available with participation patterns that may even
be adversarially influenced. In this talk we will review basic design principles and tools for
such protocols, including proof of work and proof stake, we will give an overview of the
Ouroboros family of protocols, and we will discuss the applications of such protocols
in the general context of deploying large scale information technology systems.
- Christian Cachin — University of Bern
Beyond Asymmetric Byzantine Quorum Systems
The trust assumptions behind voting-based consensus are captured by quorum
systems. Traditionally, all involved processes adhere to a global,
symmetric failure model, which is often expressed through the number of
faulty processes. Motivated by applications to blockchains, more flexible
trust assumptions have recently been considered. With asymmetric trust, a
process is free to choose which other processes it trusts and which ones
might collude against it.
We review generalized and asymmetric trust and illustrate some recent
developments. First, we describe randomized consensus protocols with
asymmetric trust. Then we look at a model with multiple (possibly
overlapping) groups of processes, each with their own trust assumptions,
quorum systems, and protocols. We show how to let the process groups work
together by composing two or more quorum systems. Third, we describe steps
to generalize the model of asymmetric trust to permissionless systems. The
latter paves the way to a common understanding of the trust models inherent
in Federated Byzantine Quorum Systems (as used by Stellar), Personal
Byzantine Quorum Systems (Losa et al., DISC 2019), and Asymmetric Byzantine
Quorum Systems.
The talk is based on joint work with Orestis Alpos, Giuliano Losa, and Luca
Zanolini.
- Ari Juels — Cornell Tech and IC3
Fair Transaction Ordering: Why and How
Consensus protocols ensure agreement on a definitive ordering of transactions. They do not, however, protect against adversarial tampering with such ordering. In fact, an industry worth hundreds of millions of dollars a year has mushroomed around opportunities to profit from transaction-order manipulation on public blockchains. These opportunities are often referred to as miner-extractable value (MEV).
In this talk, I’ll explain what MEV is and why it is important. I’ll describe protocols, such as the recently developed Themis scheme, that can protect against many harmful forms of MEV. These protocols ensure transaction ordering that is fair, i.e., that limits adversarial influence. They involve enhancement of existing consensus schemes and can enforce rigorous notions of fair transaction ordering with small performance overhead.
- Dawn Song — UC Berkeley
Scaling Blockchains with EVM-native Interactive Fraud Proofs
In this work, we aim to design a new Optimistic Rollup (ORU) that (1)
provides efficient dispute resolution, (2) maximizes EVM
reuse for simplicity, and (3) mitigates barriers to client diversity.
To fulfill these requirements, we propose an interactive
fraud proof system native to the EVM. In particular, we
outline an approach for constructing an efficiently verifiable
one-step proof directly over the state transition resulting from
the execution of a single EVM instruction. We present an
implementation of this approach in Specular, an ORU which
leverages an off-the-shelf EVM implementation—modified
minimally to support one-step proof generation. We
demonstrate efficient dispute resolution under an EVM-native design.
Our approach is the first ORU which supports L2 client diversity natively
and intrinsically respects EVM semantics.
- Alexander Spiegelman — Aptos Labs
DAG Meets BFT - The Next Generation of BFT Consensus
In this talk, I will present the recent development in the theory and practice of directed acyclic graph-based (DAG-based) Byzantine Fault Tolerance (BFT) consensus, which is currently being implemented by several Blockchain companies, e.g., Aptos, Celo, Mysten Labs, and Somelier.
Specifically, I will talk about how Narwhal decouples data from meta to build a highly efficient DAG, and then I will explain how we can locally (with zero communication overhead) totally order the nodes of the DAG by using DAG-Rider/Tusk/Bullshark.
This talk is based on three papers:
DAG-Rider: All You Need Is DAG (PODC 2021). [I. Keidar, E. Kokoris-Kogias, O. Naor, A. Spiegelman],
Narwhal&Tusk (EuroSys 2022 Best paper award) [G. Danezis, E. Kokoris-Kogias, A. Sonnino, A. Spiegelman],
Bullshark (To appear at CCS 2022) [A. Spiegelman, N. Giridharan, A. Sonnino, E. Kokoris-Kogias]
- Dahlia Malkhi — Chainlink Labs
Maximal Extractable Value (MEV) Protection on a DAG
Many cryptocurrency platforms are vulnerable to Maximal Extractable Value (MEV) attacks, where a malicious consensus leader can inject transactions or change the order of user transactions to maximize its profit. \
A promising line of research in MEV mitigation is to enhance Byzantine Fault Tolerant (BFT) consensus protocols by new functionalities, like hiding transaction contents, such that malicious parties cannot analyze and exploit them until they are ordered. An orthogonal line of research demonstrates excellent performance for BFT protocols designed around Directed Acyclic Graphs (DAG). They provide high throughput by keeping high network utilization, decoupling transactions’ dissemination from their metadata ordering, and encoding consensus logic efficiently over a DAG representing a causal ordering of disseminated transaction blocks.
This talk explains how we can combine these two advances. We introduce a DAG-based protocol called Fino, that integrates MEV-resistance features into DAG-based BFT without delaying the steady spreading of transactions by the DAG transport and with zero message overhead. The scheme operates without secret share verifiability or recoverability, and in the happy path, works in microseconds latency avoiding costly threshold encryption.
Joint work with Pawel Szalachowski, Chainlink Labs.
- Mohammad Alizadeh — MIT
DispersedLedger: High-Throughput Byzantine Consensus on Variable Bandwidth Networks
The success of blockchains has given rise to large-scale deployments of Byzantine fault tolerant (BFT) consensus protocols over wide area networks. A central feature of such networks is variable communication bandwidth across nodes and across time. Bandwidth variability creates stragglers that slow down the progress of standard BFT protocols. In this talk, I will present DispersedLedger, an asynchronous BFT protocol that provides near-optimal throughput over variable bandwidth networks. The core idea of DispersedLedger is to enable nodes to propose, order, and agree on blocks of transactions without having to download their full content. To achieve consensus, nodes merely download a small fraction of a proposed block, allowing them to agree that the block is available within the network and unmalleable. Then, asynchronously, each node downloads the agreed-upon blocks at its own pace. I’ll describe DispersedLedger’s design and evaluation, including experiments on a geo-distributed Internet deployment in which DispersedLedger achieves 2x better throughput and 74% better latency than state-of-the-art asynchronous protocols.
- David Tse — Stanford University, BabylonChain
Bitcoin-Enhanced Proof-of-Stake Security: Possibilities and Impossibilities
Bitcoin is the most secure blockchain in the world, but consumes an immense amount of energy. Proof-of-Stake chains are energy-efficient, but face several fundamental security issues: susceptibility to non-slashable long-range safety attacks, non-accountable transaction censorship and stalling attacks and difficulty to bootstrap PoS chains from low token valuation. We propose a new protocol Babylon, where an off-the-shelf PoS protocol uses Bitcoin as an external source of trust to resolve these issues. An impossibility result justifies the optimality of Babylon. Our results shed light on the general question of how much security a PoS chain can derive from an external trusted chain by only making succinct commitments to the trusted chain.
- Oren Katz — StarkWare
Challenges in consensus protocols for Validity Rollups
Validity Rollups are one of the leading scalability solutions for Blockchain, providing a scalable layer (L2) on top of the base chain. Decentralization of this L2 comes with its own set of considerations wrt its consensus protocols, some simplifying the problem (e.g. the reliance on L1 for some aspects), some complicating it (e.g. the existence of both sequencers and provers as separate players in the protocol). The talk will discuss these issues and some of StarkNet’s plans for solving them.
- John Adler — Celestia
Proof-of-Stake in the Model of Accountability
Traditional academic distributed consensus design relies on a correct majority of replicas in order to guarantee availability and consistency. In a decentralized context however, there is an additional constraint: replicas must be accountable to protocol users. We explore gotchas in designing decentralized consensus protocols when it comes to accountability.
