I. Mitigating Frontrunning (aka MEV) in Blockchains

Transaction-order-manipulation attacks have become extremelycommon in public blockchains such as Ethereum, costing hundreds of millions of dollars. In these blockchains, a miner can unilaterally determine the order of transactions inside a block, and this ordering is not checked by other users, leaving room for the miner to manipulate the order for its own benefit. This gap is also evident from existing security results for permissionless blockchains. As prime examples, the breakthrough work of Garay et al. and Pass et al. showed the security properties of consistency and liveness for Nakamoto’s seminal proof-of-workprotocol. However, consistency and liveness do not provide any guarantees on the relationship between the order in which transactions arrive into the network and the finalized order in the ledger.

As a solution, a recent paper by Kelkar et al. introduced a third useful property for consensus protocols: (transaction)-order-fairness, which proposes a strong relationship between the transaction arrival order and their order in the ledger. Their model was limited to the classical (permissioned) setting however, where the set of protocol nodes is fixed a priori, and does not fit well for permissionless environments where order-manipulation attacks have been most prominent. In this work, we initiate the investigation of order-fairness in the permissionless setting and design two protocols that realize this new property addition to standard requirements of consistency and livenesss. The key insight behind our protocols in providing order-fairness is that a miner can no longer unilaterally determine ordering and proposals from many miners are combined in a fair way to construct the finalized ordering. As a simple but unexpected corollary, we show that any fair ordering protocol achieves a powerful zero-block confirmation property, through which honest transactions can be securely confirmed even before they are included in any block.

Relevant Publications

• Mahimna Kelkar, Soubhik Deb, Sishan Long, Ari Juels, Sreeram Kannan. 2022. Themis: Fast, Strong Order-Fairness in Byzantine Consensus.
• Mahimna Kelkar, Soubhik Deb, Sreeram Kannan. 2022. Order-Fair Consensus in the Permissionless Setting. In arXiv.

I. Dynamic Availability and Unpredictability in PoS Blockchains

An important feature of Proof-of-Work (PoW) blockchains is full dynamic availability, allowing miners to go online and offline while requiring only 50% of the online miners to be honest. Existing Proof-of-Stake (PoS) such as Ouroboros and Snow White, Proof-of-Space and related protocols are able to achieve this property only partially, either requiring the additional assumption that adversary nodes are online from the beginning and no new adversary nodes come online afterwards, or use additional trust assumptions for newly joining nodes. We propose a new PoS protocol PoSAT which can provably achieve dynamic availability fully without any additional assumptions. The protocol is based on the longest chain and uses a Verifiable Delay Function for the block proposal lottery to provide an arrow of time.

The security analysis of the protocol draws on the recently proposed technique of Nakamoto blocks as well as the theory of branching random walks. An additional feature of PoSAT is the complete unpredictability of who will get to propose a block next, even by the winner itself. This unpredictability is at the same level of PoW protocols, and is stronger than that of existing PoS protocols using Verifiable Random Functions.

Relevant Publications

• Soubhik Deb, Sreeram Kannan, David Tse. 2021. PoSAT: Proof-of-Work Availability and Unpredictability, without the Work. In the Financial Cryptography and Data Security 2021.

II. Optimal latency and throughput in blockchains

The concept of a blockchain was invented by Satoshi Nakamoto to maintain a distributed ledger for an electronic payment system, Bitcoin. In addition to its security, important performance measures of a blockchain protocol are its transaction throughput, confirmation latency and confirmation reliability. 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 blockchain protocol, which can provably 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 the bandwidth-delay product 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.

Relevant Publications

• Vivek Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, Pramod Viswanath. 2019. Prism: Deconstructing the Blockchain to Approach Physical Limits. In the ACM Conference on Computer and Communications Security 2019.

I. Efficient Peer-to-Peer Network Design for Blockchains

A key performance metric in blockchains is the latency between when a transaction is broadcast and when it is confirmed (the so-called, confirmation latency). While improvements in consensus techniques can lead to lower confirmation latency, a fundamental lower bound on confirmation latency is the propagation latency of messages through the underlying peer-to-peer (p2p) network (in Bitcoin, the propagation latency is several tens of seconds). The de facto p2p protocol used by Bitcoin and other blockchains is based on random connectivity: each node connects to a random subset of nodes. The induced p2p network topology can be highly suboptimal since it neglects geographical distance, differences in bandwidth, hash-power and computational abilities across peers.

We present Perigee, a decentralized algorithm that automatically learns an efficient p2p topology tuned to the aforementioned network heterogeneities, purely based on peers' interactions with their neighbors. Motivated by the literature on the multi-armed bandit problem, Perigee optimally balances the tradeoff between retaining connections to known well-connected neighbors, and exploring new connections to previously-unseen neighbors. Experimental evaluations show that Perigee reduces the latency to broadcast by 33%. Lastly Perigee is simple, computationally lightweight, adversary-resistant, and compatible with the selfish interests of peers, making it an attractive p2p protocol for blockchains.

Relevant Publications

• Bowen Xue, Yifan Mao, Shaileshh Bojja Venkatakrishnan, Sreeram Kannan. 2022. Goldfish: Peer selection using Matrix completion in unstructured P2P network. Under review at Financial Cryptography and Data Security 2022.
• Yifan Mao, Soubhik Deb, Shaileshh Bojja Venkatakrishnan, Sreeram Kannan, Kannan Srinivasan. 2020. Perigee: Efficient Peer-to-Peer Network Design for Blockchains. In the ACM Symposium on Principles of Distributed Computing 2020.

I. Coding theory for blockchains

Today's blockchains do not scale in a meaningful sense. As more nodes join the system, the efficiency of the system (computation, communication, and storage) degrades, or at best stays constant. A leading idea for enabling blockchains to scale efficiency is the notion of sharding: different subsets of nodes handle different portions of the blockchain, thereby reducing the load for each individual node. However, existing sharding proposals achieve efficiency scaling by compromising on trust - corrupting the nodes in a given shard will lead to the permanent loss of the corresponding portion of data. We observe that sharding is similar to replication coding, which is known to be inefficient and fragile in the coding theory community.

In this paper, we demonstrate a new protocol for coded storage and computation in blockchains. In particular, we propose PolyShard: "polynomially coded sharding" scheme that achieves information-theoretic upper bounds on the efficiency of the storage, system throughput, as well as on trust, thus enabling a truly scalable system. We provide simulation results that numerically demonstrate the performance improvement over state of the arts, and the scalability of the PolyShard system. Finally, we discuss potential enhancements, and highlight practical considerations in building such a system.

Relevant Publications

• Songze Li, Mingchao Yu, Chien-Sheng Yang, Amir Salman Avestimehr Sreeram Kannan, Pramod Viswanath. 2020. CPolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously. In the IEEE Transactions on Information Forensics and Security 2020.
• Mingchao Yu, Saeid Sahraei, Songze Li, Salman Avestimehr Sreeram Kannan, Pramod Viswanath. 2020. Coded merkle tree: Solving data availability attacks in blockchains. In the Financial Cryptography and Data Security 2020.
• Songze Li, Saeid Sahraei, Mingchao Yu, Salman Avestimehr, Sreeram Kannan, Pramod Viswanath. 2019. Coded State Machine - Scaling State Machine Execution under Byzantine Faults. In the ACM Symposium on Principles of Distributed Computing 2019.