ZLB: A Blockchain to Tolerate Colluding Majorities

In general, consensus cannot be solved if an adversary controls a third of the system. Yet, blockchain participants typically reach consensus “eventually” despite an adversary controlling a minority of the system. Exceeding this $\frac{1}{3}$ cap is made possible by tolerating transient disagreements, where distinct participants select distinct blocks for the same index, before eventually agreeing on the same block. Until now, no blockchain could tolerate an attacker controlling a majority of the system. In this paper, we present Zero-Loss Blockchain ZLB, the first blockchain that tolerates an adversary controlling more than half of the system. ZLB is an open blockchain that combines recent theoretical advances in accountable Byzantine agreement to exclude undeniably faulty replicas. Interestingly, ZLB does not need a known bound on the delay of messages but progressively reduces the portion of alive but corrupt replicas below $\frac{1}{3}$, and reaches consensus. Geo-distributed experiments show that ZLB outperforms HotStuff that cannot tolerate $n/3$ faults and is almost as fast as the scalable Redbelly Blockchain.

I. Introduction

Blockchain systems [59] promise to track ownership of assets without a central authority and thus rely heavily on distributed nodes agreeing on a unique block at the next index of the chain. An attacker can exploit a disagreement to double spend by simply inserting conflicting transactions in competing blocks.