Practical Byzantine fault tolerance

TLDR

Byzantine‑fault‑tolerant algorithms are becoming increasingly important as malicious attacks and software errors grow, yet prior solutions were synchronous or too slow; this paper argues that a practical, asynchronous algorithm can address these issues with significant performance optimizations. The paper proposes a new replication algorithm that tolerates Byzantine faults. The authors present an asynchronous Byzantine‑fault‑tolerant replication algorithm with optimizations that reduce response time, and implement it in a NFS service to evaluate performance. The implemented NFS service incurs only a 3 % performance penalty compared to an unreplicated NFS.

Abstract

This paper describes a new replication algorithm that is able to tolerate Byzantine faults. We believe that Byzantinefault-tolerant algorithms will be increasingly important in the future because malicious attacks and software errors are increasingly common and can cause faulty nodes to exhibit arbitrary behavior. Whereas previous algorithms assumed a synchronous system or were too slow to be used in practice, the algorithm described in this paper is practical: it works in asynchronous environments like the Internet and incorporates several important optimizations that improve the response time of previous algorithms by more than an order of magnitude. We implemented a Byzantine-fault-tolerant NFS service using our algorithm and measured its performance. The results show that our service is only 3% slower than a standard unreplicated NFS.