George Bissias (University of Massachusetts Amherst), Brian N. Levine (University of Massachusetts Amherst)

Blockchain systems are designed to produce blocks at a constant average rate. The most popular systems currently employ a Proof of Work (PoW) algorithm as a means of creating these blocks. An unfortunate limitation of all deployed PoW blockchain systems is that the time between blocks has high variance. For example, Bitcoin produces, on average, one block every 10 minutes. However, 5% of the time, Bitcoin's inter-block time is at least 40 minutes.

In this paper, we show that high variance is at the root of fundamental attacks on PoW blockchains. We propose an alternative process for PoW-based block discovery that results in an inter-block time with significantly lower variance. Our algorithm, called _Bobtail_, generalizes the current algorithm, which uses a single PoW sample, to one that incorporates $k$ samples. We show that the variance of inter-block times decreases as $k$ increases. Bobtail significantly thwarts doublespend and selfish mining attacks. For example, for Bitcoin and Ethereum, a doublespending attacker with 40% of the mining power will succeed with 53% probability when the merchant sets up an embargo of 1 block; however, when $kgeq40$, the probability of success for the same attacker falls to less than 1%. Similarly, for Bitcoin and Ethereum currently, a selfish miner with 49% of the mining power will claim about 95% of blocks; however, when $kgeq20$, the same miner will find that selfish mining is less successful than honest mining. We also investigate attacks newly made possible by Bobtail and show how they can be defeated. The primary costs of our approach are larger blocks and increased network traffic.

View More Papers

Automated Discovery of Cross-Plane Event-Based Vulnerabilities in Software-Defined Networking

Benjamin E. Ujcich (University of Illinois at Urbana-Champaign), Samuel Jero (MIT Lincoln Laboratory), Richard Skowyra (MIT Lincoln Laboratory), Steven R. Gomez (MIT Lincoln Laboratory), Adam Bates (University of Illinois at Urbana-Champaign), William H. Sanders (University of Illinois at Urbana-Champaign), Hamed Okhravi (MIT Lincoln Laboratory)

Read More

Carnus: Exploring the Privacy Threats of Browser Extension Fingerprinting

Soroush Karami (University of Illinois at Chicago), Panagiotis Ilia (University of Illinois at Chicago), Konstantinos Solomos (University of Illinois at Chicago), Jason Polakis (University of Illinois at Chicago)

Read More

Post-Quantum Authentication in TLS 1.3: A Performance Study

Dimitrios Sikeridis (The University of New Mexico), Panos Kampanakis (Cisco Systems), Michael Devetsikiotis (The University of New Mexico)

Read More

Finding Safety in Numbers with Secure Allegation Escrows

Venkat Arun (Massachusetts Institute of Technology), Aniket Kate (Purdue University), Deepak Garg (Max Planck Institute for Software Systems), Peter Druschel (Max Planck Institute for Software Systems), Bobby Bhattacharjee (University of Maryland)

Read More