The problem of Byzantine consensus has been key to designing secure distributed systems. Although it is well known that both safety and liveness are at risk as soon as n/3 Byzantine processes fail, very few works attempted to characterize precisely the faults that produce safety violations from the faults that produce termination violations.We present a new lower bound on the solvability of the consensus problem by distinguishing deceitful faults violating safety and benign faults violating termination from the more general Byzantine faults, in what we call the Byzantine-deceitful-benign fault model. We show that one cannot solve consensus if n≤3t+d+2q with t, d, and q are Byzantine, deceitful, and benign processes. We show that this bound is tight by presenting the Basilic class of consensus protocols that solve consensus when n>3t+d+2q. These protocols differ in the number of processes from which they wait to receive messages before progressing.

Then, we build upon the Basilic class in order to present Zero-Loss Blockchain (ZLB), the first blockchain that tolerates an adversary controlling more than half of the system, with up to less than a third of them Byzantine. ZLB is an open blockchain that combines recent theoretical advances in accountable Byzantine agreement to exclude undeniably faulty processes. Interestingly, ZLB does not need a known bound on the delay of messages but progressively reduces the portion of faulty processes below 1/3, and reaches consensus. Geo-distributed experiments show that ZLB outperforms HotStuff and is almost as fast as the scalable Red Belly Blockchain that cannot tolerate n/3 faults. These works extend our recent results on the rational model with TRAP, providing safety and liveness even in the presence of a majority of non-rational, faulty participants.

The works presented in this talk comprise three publications, at AsiaCCS’22, CSF’23, and DSN’24 (best paper award)