Tse Lab

Blockchains & Decentralized Systems

Bitcoin is the first system to achieve consensus at the global scale using blockchain as its underlying technology. Its success has spurred a new wave of imagination and ideas across all disciplines. However, the current blockchain technology cannot support many of these ideas due to its poor performance and we are working on blockchain technology which obtains high performance in all the dimensions (throughput, latency, storage, computation, communication etc).

Security of proof-of-stake Ethereum

The design of next generation proof-of-stake Ethereum brings various security and performance challenges. We devise attacks and security analyses to support ongoing Ethereum research and development efforts.

One might desire an ideal blockchain protocol to simultaneously provide liveness under dynamic participation, safety under temporary network partitions, and accountability to punish adversarial behavior. Yet, various impossibility results show that no single ledger can have all these properties, each of which is a desideratum for a global consensus layer such as Ethereum. Supported by a gift from the Ethereum foundation, we propose problem formulations and protocol constructions that reconcile these desiderata using multiple nested ledgers. This provides a formal framework to reason about the design landscape for next generation proof-of-stake Ethereum. We also analyze the security of and devise attacks on existing protocols such as Gasper, the Ethereum 2 beacon chain protocol, to highlight attack vectors and spur security enhancements of Ethereum.

Key Publications

Other Resources

Press

Error correcting codes for blockchains

Error correcting codes have manifold applications to enhance security and performance of blockchain systems. We use codes to improve the resilience-overhead tradeoff in consensus and rollups.

Often, a system made from various components fails as soon as one of the components fails, for example when a large file is chunked up and each chunk is stored in a different storage server. As soon as one of the storage servers fails, it is not possible to recover the whole file anymore. Error correcting codes can be used to increase the resilience to component failures at the expense of injecting a bit of overhead. Supported by a gift from Input-Output Global (IOG), we explore applications of this paradigm in the blockchain context. For example, error correcting codes have been used in Verifiable Information Dispersal, which we refine to speed up consensus or to improve the resilience/overhead tradeoff of off-chain data storage in Validium rollups.

Key Publications

  • “DispersedLedger: High-Throughput Byzantine Consensus on Variable Bandwidth Networks”, Lei Yang, Seo Jin Park, Mohammad Alizadeh, Sreeram Kannan, David Tse, USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2022, arXiv 2110.04371
  • “Information Dispersal with Provable Retrievability for Rollups”, Kamilla Nazirkhanova, Joachim Neu, David Tse, arXiv 2111.12323

Resolving the availability-finality dilemma in consensus

Internet-scale blockchains should operate under dynamic participation and temporary network partitions, but no protocol can simultaneously guarantee progress and consistency in this setting. Our goal is that every end-user can choose a side of this dilemma, obviating a system-wide determination.

The CAP theorem says that no blockchain can be live under dynamic participation and safe under temporary network partitions. To resolve this availability-finality dilemma, we formulate a new class of flexible consensus protocols, ebb-and-flow protocols, which support a full dynamically available ledger in conjunction with a finalized prefix ledger. This way, end-users can choose whether to favor liveness or safety, obviating a system-wide determination by the protocol designer as is common in existing protocols. Gasper, the current candidate for Ethereum 2.0, aims to achieve the ebb-and-flow property, but we have found an attack under standard network models. As an alternative, we present provably secure ebb-and-flow protocols based on black-box composition of off-the-shelf dynamically available and BFT protocols.

Key Publications

Consensus layer protocols to achieve physical limits

Consensus is at the core layer of every blockchain design and therefore optimizing this layer is paramount for high performance. Since blockchains run on physical networks, our goal is use all the available physical resources to achieve high performance.

Transaction throughput, confirmation latency and confirmation reliability are fundamental performance measures of any blockchain system in addition to its security. In a decentralized setting, these measures are limited by two underlying physical network attributes: communication capacity and speed-of-light propagation delay. Existing systems operate far away from these physical limits. In this work we introduce Prism, a new proof-of-work blockchain protocol, which can achieve 1) security against up to 50% adversarial hashing power; 2) optimal throughput up to the capacity C of the network; 3) confirmation latency for honest transactions proportional to the propagation delay D, with confirmation error probability exponentially small in CD; 4) eventual total ordering of all transactions. Our approach to the design of this protocol is based on deconstructing the blockchain into its basic functionalities and systematically scaling up these functionalities to approach their physical limits.

Key Publications

  • “Prism Removes Consensus Bottleneck for Smart Contracts”, Gerui Wang, Shuo Wang, Vivek Bagaria, David Tse, Pramod Viswanath, Crypto Valley Conference, 2020, arXiv 2004.08776, Source code, Video
  • “Everything is a Race and Nakamoto Always Wins”, Amir Dembo, Sreeram Kannan, Ertem Nusret Tas, David Tse, Pramod Viswanath, Xuechao Wang, Ofer Zeitouni, Forthcoming in ACM Conference on Computer and Communications Security (CCS’20), 2020, arXiv 2005.10484
  • “Prism: Scaling Bitcoin by 10,000x”, Lei Yang, Vivek Bagaria, Gerui Wang, Mohammad Alizadeh, David Tse, Giulia Fanti, Pramod Viswanath, 2019, arXiv 1909.11261, Source code
  • “Proof-of-Stake Longest Chain Protocols Revisited”, Xuechao Wang, Govinda Kamath, Vivek Bagaria, Sreeram Kannan, Sewoong Oh, David Tse, Pramod Viswanath, 2019, arXiv 1910.02218
  • “Deconstructing the Blockchain to Approach Physical Limits”, Vivek Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, Pramod Viswanath, 2018, Accepted for ACM CCS 2019, arXiv 1810.08092, Slides, YouTube

State-channel layer protocols

On top of scalable consensus layer protocols, so called layer-2 protocols further enhance throughput, latency and privacy of blockchain systems.

Undisclosed channel balances and mismatched transaction fees cause delays and failures on some payment paths in payment-channel networks. For atomic transfer schemes, these straggling paths stall the whole transfer. We show that the latency of transfers reduces when redundant payment paths are added. This frees up liquidity in payment channels and hence increases the throughput of the network. We devise Boomerang, a generic technique to be used on top of multi-path routing schemes to construct redundant payment paths free of counterparty risk.

Key Publications