Tse Lab

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


  • 12:30:   Registration / coffee & snacks
  • 1:00:     Welcome
  • 1:10-2:25:     Session 1 (Chair: David Tse)
    • 1:10:     Aggelos KiayiasLedger consensus with dynamic availability - From Bitcoin to OuroborosRecording
    • 1:35:     Christian CachinBeyond Asymmetric Byzantine Quorum SystemsRecording
    • 2:00:     Ari JuelsFair Transaction Ordering: Why and HowRecording
  • 2:25:     Coffee break (20min)
  • 2:45-4:25:     Session 2 (Chair: Joachim Neu)
    • 2:45:     Dawn SongScaling Blockchains with EVM-native Interactive Fraud ProofsRecording
    • 3:10:     Alexander SpiegelmanDAG Meets BFT - The Next Generation of BFT ConsensusRecording
    • 3:35:     Dahlia MalkhiMaximal Extractable Value (MEV) Protection on a DAGRecording
    • 4:00:     Mohammad AlizadehDispersedLedger: High-Throughput Byzantine Consensus on Variable Bandwidth NetworksRecording
  • 4:25:     Coffee break (20min)
  • 4:45-6:00:     Session 3 (Chair: Sreeram Kannan)
    • 4:45:     David TseBitcoin-Enhanced Proof-of-Stake Security: Possibilities and ImpossibilitiesRecording
    • 5:10:     Oren KatzChallenges in consensus protocols for Validity RollupsRecording
    • 5:35:     John AdlerProof-of-Stake in the Model of AccountabilityRecording
  • 6:00-8:00:     Dinner reception


  • 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.