Prime: Byzantine Replication Under Attack

Overview

Prime is a Byzantine fault-tolerant replication engine that provides meaningful performance guarantees even after some of the replication servers have been compromised. Like previous Byzantine fault-tolerant replication protocols, Prime guarantees Safety (consistency of the correct replicas) and Liveness (the eventual execution of each update) as long as no more than f out of 3f+1 replicas are compromised and the network is sufficiently stable. Unlike previous protocols, Prime additionally provides a stronger performance guarantee, which we call Bounded-Delay. Bounded-Delay limits the amount of performance degradation that can be caused by malicious servers. Intuitively, Prime forces any leader that remains in power to meet a threshold level of performance, where the threshold is a function of the message delays between the correct servers in the system, which cannot be arbitrarily increased by the malicious servers.

Prime supports proactive recovery, diversity, and state transfer. Prime servers can be periodically rejuvenated to clean potentially undetected intrusions from the system. The MultiCompiler described here can be used to diversify the code layout of Prime servers in order to increase the resiliency of the system. The MultiCompiler uses a 64-bit random number to generate different variants of an application. A different version of a Prime server can be generated after each rejuvenation. In this way, if an adversary attacks all the servers in parallel, the probability to defeat more than f servers is low. After rejuvenation, a Prime server also validates the contents of the state on the disk with the help of other correct replicas and recovers a clean copy of the state if necessary. Subsequently, the rejuvenated replica collects all the client updates necessary to catch up and resume the execution. The state and update transfer protocols are guaranteed to meet Safety because they are coordinated by a quorum of correct replicas.

Prime can be configured to make use of Spines, an overlay network developed at Johns Hopkins (see www.spines.org). Spines offers an intrusion-tolerant network service that can be used to protect communication between the Prime replicas. Spines can be deployed in both local-area and wide-area environments and includes tools for emulating wide-area topologies in local-area networks and placing bandwidth and latency constraints on the links between servers.

Prime was created at Johns Hopkins University by Yair Amir, Jonathan Kirsch, John Lane, and Marco Platania.

Special thanks to Brian Coan for major contributions to the design of the Prime algorithm, and Jeff Seibert for major contribution to the View Change protocol.

Software

A version of Prime suitable for evaluating the performance of the protocol in both fault-free and under-attack executions can be downloaded here. The code was written in C and runs on Linux. Prime was tested with version 3.5 of the MultiCompiler, which is included in the Prime software package. Please refer to the MultiCompiler website for further releases.

Releases

  • Version 2.0 - September 17, 2014
  • Version 1.1 - December 07, 2013
  • Version 1.0 - May 04, 2010

Funding

Partial funding for Prime research was provided by the Defense Advanced Research Projects Agency (DARPA) and the National Science Foundation (NSF). Prime is not necessarily endorsed by DARPA or the NSF.

License

Prime may be freely used and distributed under some conditions. Please review the license agreement for more details.

Publications

Distributed Systems and Networks Lab
Computer Science Department, Johns Hopkins University
207 Malone Hall
3400 North Charles Street
Baltimore, MD 21218
TEL: (410) 516-5562