Authenticated Byzantine Fault Tolerance Without Public-Key Cryptography

We have developed a practical state-machine replication algorithm that tolerates Byzantine faults: it works correctly in asynchronous systems like the Internet and it incorporates several optimizations that improve the response time of previous algorithms by more than an order of magnitude. This paper describes the most important of these optimizations. It explains how to modify the base algorithm to eliminate the major performance bottleneck in previous systems — public-key cryptography. The optimization replaces public-key signatures by vectors of message authentication codes during normal operation, and it overcomes a fundamental limitation on the power of message authentication codes relative to digital signatures — the inability to prove that a message is authentic to a third party. As a result, authentication is more than two orders of magnitude faster while providing the same level of security.