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

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