The long-standing impossibility of reaching an agreement seems to restrict the lifespan of existing blockchains. In fact, consensus is key for replicas to decide upon a unique block to be appended to the next available index of the blockchain. Classic blockchains cope with an attacker controlling up to 1/2 of the replica power, yet they typically rely on synchrony in order to identify blocks competing for the same index and to resolve disagreements before the attacker double spends. More recent blockchains relax this synchrony assumption to completely avoid disagreements, yet an attacker can double spend as soon as they control 1/3 of n specific replicas. As a result, one may wonder whether any blockchain can avoid asset loss despite an attacker controlling a majority of the network.

In this paper, we answer this question in the affirmative by proposing the Longlasting Blockchain system, LLB, tolerating an attacker controlling more than half of the network and without assuming synchrony. LLB builds upon an accountable state machine replication that requires participants to justify important messages, so as to exclude deceitful participants in case of double spending attempts. As opposed to classic blockchains, LLB solves consensus deterministically when f < n/3 and without assuming a known bound on the delay of messages. As opposed to Byzantine fault-tolerant blockchains, it recovers from a series of disagreements by reducing eventually the number of deceitful replicas from n/3 =< f < 2n/3 to f'<n’/3 among a new set of n’ replicas. To demonstrate its effectiveness, we implement two coalition attacks and a zero loss payment application that forces replicas that misbehave to fund conflicting transactions. Finally, LLB outperforms the raw state machine replication at the heart of Facebook’s Libra by 5.6 times and achieves performance comparable to the recent Red Belly Blockchain. This shows for the first time that tolerating a majority of failures in blockchain can be achieved, and at a negligible cost.

About Alejandro Ranchal-Pedrosa

Alejandro Ranchal-Pedrosa is a PhD student at the University of Sydney under the supervision of Vincent Gramoli. His PhD focuses on Blockchain technologies’ scalability and security. His main line of work has been focused on distributed protocols, specially Blockchain technologies, from the perspective of Distributed Systems, Game Theory, and Cryptography.

This event will be conducted in English