Science and Engineering of Consensus

An affiliated workshop of The Science of Blockchain Conference 2023

Sponsored by:            

Recordings: https://www.youtube.com/playlist?list=PL4XSNxeZhdqCWdKKNSBJp0Q7Fsjzcrr97

Previous year’s workshop: https://tselab.stanford.edu/workshop-sbc22/

• When? Sunday, August 27, 2023. 12:30-8pm PT.
• Where? Stanford University campus, Sapp Center for Science Teaching and Learning building, room STLC111. Stanford, CA, USA.
  Nearby parking: Roth Way Garage. More parking.
• Registration: Attendance is free, but registration is mandatory.
  Update 26-August-2023: Regular registration closed.
  
• Livestream: To avoid “Zoom-bombing”, we ask attendees to input their email address here https://stanford.zoom.us/meeting/register/tJ0lfu2qqj4qHN0a8mE2DdgxxLVbyldbslN6 to promptly receive the Zoom meeting details via email.
• Contact: Workshop organized by Stanford Tse Lab. For questions, contact Joachim Neu, Srivatsan Sridhar, or David Tse.

Program

• 12:30:   Registration / coffee & snacks
• 1:00:     Welcome
• 1:05–2:20:     Session 1 (Chair: David Tse)
  • 1:05:     Elaine Shi — Oblivious RAM: from Theory to Large-Scale Deployment — Recording
  • 1:30:     Ed Felten — BoLD: Bounded Liquidity Delay in a Rollup Challenge Protocol — Recording
  • 1:55:     David Tse — Bitcoin Staking — Recording
  • 2:20:     Aviv Zohar — Speculative DoS Attacks in Ethereum — Recording
• 2:45:     Coffee break
• 3:10–4:25:     Session 2 (Chair: Joachim Neu)
  • 3:10:     Aniket Kate — Building Asynchronous Systems for a Simple Honest Majority Using a Chain of Integrity — Recording
  • 3:35:     Peter Gaži — Fait Accompli Committee Selection: Improving the Size-Security Tradeoff of Stake-Based Committees — Recording
  • 4:00:     Vitalik Buterin (remote) — Properties of Consensus in Theory and in Practice — Recording
• 4:25:     Coffee break
• 4:50–6:05:     Session 3 (Chair: Srivatsan Sridhar)
  • 4:50:     Kartik Nayak — The Espresso Sequencer: HotShot Consensus and Tiramisu Data Availability — Recording
  • 5:15:     Sreeram Kannan — StakeSure: Proof of Stake Mechanisms with Strong Cryptoeconomic Safety — Recording
  • 5:40:     David Mazières — Issued Assets Require Proof of Agreement — Recording
• 6:05:     Goodbye
• 6:10–8:00:     Reception

Abstracts

• Vitalik Buterin — Ethereum Foundation
  TBD (remote)
  TBD

• Ed Felten — Princeton University & Offchain Labs
  BoLD: Bounded Liquidity Delay in a Rollup Challenge Protocol
  Optimistic rollup protocols, if not designed carefully, suffer from delay attacks, where an adversary sacrifices stakes to delay confirmation of correct results. These attacks are more consequential on rollups built on a Layer 1 system with weak censorship resistance, such as Ethereum, because the attacker can exploit the generous deadlines offered to possibly-censored parties. We describe delay attacks against prior rollup protocols; present the design of BoLD, the first rollup challenge protocol providing a near-constant upper bound on delay; and describe an implementation of the protocol for Arbitrum.

• Peter Gaži — Input Output Global
  Fait Accompli Committee Selection: Improving the Size-Security Tradeoff of Stake-Based Committees
  We study the problem of committee selection in the context of proof-of-stake consensus mechanisms or distributed ledgers. These settings determine a family of participating parties, each of which has been assigned a non-negative “stake”, and are subject to an adversary that may corrupt a subset of the parties. The challenge is to select a committee of participants that accurately reflects the proportion of corrupt and honest parties, as measured by stake, in the full population. The trade-off between committee size and the probability of electing a committee that over-represents corrupt parties is a fundamental factor in security and efficiency considerations for proof-of-stake consensus, as well as committee-run layer-two protocols.
  We propose several new committee selection schemes that improve upon existing techniques by adopting low-variance assignment of certain committee members that hold significant stake. These schemes provide notable improvements to the size–security trade-off arising from the stake distributions of many deployed ledgers.

• Sreeram Kannan — University of Washington & EigenLayer
  StakeSure: Proof of Stake Mechanisms with Strong Cryptoeconomic Safety
  As of June 15, 2023, Ethererum, which is a Proof-of-Stake (PoS) blockchain has around 410 Billion USD in total assets on chain but has only ~33 Billion USD worth of ETH staked in securing the underlying consensus of the chain. A preliminary analysis might suggest that as the amount staked is far less (11x less) than the value secured, the Ethereum blockchain is insecure and “over-leveraged” in a purely cryptoeconomic sense. In this work, we investigate how Ethereum, or, more generally, any PoS blockchain can be made secure despite this apparent imbalance. Towards that end, we attempt to formalize a model for analyzing the cryptoeconomic safety of PoS blockchain, which separately analyzes the cost-of-corruption, the cost incurred by an attacker, and the profit-from-corruption, the profit gained by an attacker. We derive sharper bounds on profit-from-corruption, as well as new confirmation rules that significantly decrease this upper-bound. Finally, we present a new “insurance” mechanism, STAKESURE, for allocating the slashed funds in a PoS system, that has several highly desirable properties: solving common information problem in existing blockchains, creating a mechanism for provably safe bridging, and providing the first sharp solution for automatically adjusting how much economic security is sufficient in a PoS system. Finally, we show that the system satisfies a notion of strong cryptoeconomic safety, which guarantees that no honest transactor ever loses money, and creates a closed system of Karma, which not only ensures that the attacker suffers a loss of funds but also that the harmed parties are sufficiently compensated.

• Aniket Kate — Purdue University & Supra Oracles
  Building Asynchronous Systems for a Simple Honest Majority Using a Chain of Integrity
  Current major blockchain systems involve all nodes participating in every all aspects of state machine replication, including data dissemination, ordering and execution. However, this approach does not scale for growing systems, causing slowdowns as more tasks are processed. Moreover, with rise of DeFi, GameFi, we may want to leverage the same infrastructure to also manage oracles/randomness services or to perform privacy-preserving computation. This will result in significant further reduction in the underlying blockchain’s throughput and latency. This talk focuses on using the same blockchain infrastructure more efficiently at scale.
  Although a few have put forth ideas of segregating blockchain tasks, the existing strategies still hinge on a super majority (67%) of honest nodes and all nodes participating in every task. The foundation of this work lies in a realization that, while tolerating the same faults and networking conditions, it is possible to alleviate the load on blockchain nodes for all tasks except one: ordering. We find that by effectively solving the ordering task with 67% honest nodes, a spectrum of pertinent distributed tasks (ranging from data dissemination and execution to DKG, MPC, and distributed oracles) can be addressed asynchronously, requiring only 51% honest nodes. This talk delves into the intricacies of constructing asynchronous distributed solutions using 51% honest nodes, employing a chain of integrity that only orders commitments to data/events.

• David Mazières — Stanford University
  Issued Assets Require Proof of Agreement
  

• Kartik Nayak — Duke University & Espresso Systems
  The Espresso Sequencer: HotShot Consensus and Tiramisu Data Availability
  Layer-2 (L2) rollups are popular for scaling Layer-1 (L1) blockchains. Rollups move the transaction processing off-chain, while the L1 only checkpoints the rollup state. This design leaves open the question of which transactions are rolled up and in what order. Unfortunately, all of the current rollups use their own centralized sequencers for ordering transactions. This leads to two caveats: (i) the centralized sequencer is a single point of failure, and (ii) applications from different L2 ecosystems are harder to interoperate.
  We introduce Espresso Sequencer, a decentralized network that can be shared by all of the L2 rollups. Our design consists of two key components, HotShot Consensus and Tiramisu data availability that are modularly separated to handle the two key tasks of a sequencer — ordering transactions and ensuring data availability. HotShot is an optimistically responsive, communication-efficient consensus protocol in a proof-of-stake setting that is resistant to bribing adversaries and scalable to a large number of nodes. Our layered Tiramisu data availability protocol combines the use of verifiable information dispersal and small random committees to ensure data availability with linear communication complexity. Both of our protocols allow the use of a content distribution network at the networking layer that unlocks Web2 performance in the optimistic case while still providing strong Web3 security guarantees in the pessimistic case.

• Elaine Shi — Carnegie Mellon University
  Oblivious RAM: from Theory to Large-Scale Deployment
  In this talk, I will give a brief tutorial of Oblivious RAM (ORAM). Then I will talk about how ORAM evolved from a theoretical concept to large-scale real-world deployment, and the various emerging demands and use cases of ORAM in both the blockchain community and for traditional cloud service providers. In particular, I will talk about Signal’s deployment of Path ORAM over their billion-sized database, and how ORAM allowed them to cut their 500 servers down to 6 servers.
  Finally, I will describe a new initiative to build an open-source Oblivious STL library, aiming to provide an oblivious counterpart of the standard STL library. I will describe our initial efforts at building Oblivious STL. Specifically, I will focus on how using external-memory algorithms techniques can allow us to achieve a 10-100x performance improvement over state-of-the-art implementations for hardware enclaves. In particular, while the literature on ORAM typically uses computational overhead as the performance metric, for hardware enclaves, the number of page swaps is often the dominant metric. Through the help of external-memory algorithms, we can achieve an asymptotical improvement in the number of page swaps.

• David Tse — Stanford University
  Bitcoin Staking
  Proof-of-Stake (PoS) chains are secured by capital but capital can be very expensive. Bitcoin is a Proof-of-Work chain but it is also a $600 Billion asset and most of it is idle capital. We propose the concept of Bitcoin staking which allows bitcoin holders to stake their idle bitcoins to increase the security of PoS chains and in the process earn yield. We present a Bitcoin staking protocol which allows bitcoin holders to trustlessly stake their bitcoins without bridging them to the PoS chain but yet provides the chain with full slashable security guarantees. The protocol supports fast stake unbonding to maximize the liquidity for bitcoin holders. Moreover, the protocol is designed as a modular plug-in for use on top of many different PoS consensus algorithms and provides a primitive upon which restaking protocols can be built.

• Aviv Zohar — Hebrew University of Jerusalem
  Speculative DoS Attacks in Ethereum
  Ethereum’s gas mechanism is meant to ensure that transactions do not consume computational resources without paying. We show that this mechanism is in itself insufficient to protect nodes from denial-of-service (DoS) attacks and that adversaries can target processes that require speculative transaction execution, which is often done out-of-context. We thus demonstrate how to craft malicious transactions that decouple the work imposed on blockchain actors from the compensation offered in return. We introduce three attacks: (i) ConditionalExhaust, the first conditional resource exhaustion attack against blockchain actors. (ii) MemPurge, an attack for evicting transactions from victims’ mempools. (iii) GhostTX, an attack on the reputation system used in Ethereum’s proposer-builder separation (PBS) ecosystem.