Scaling Byzantine Fault-Tolerant Replication toWide Area NetworksYair Amir, Claudiu Danilov, Danny Dolev, Jonathan Kirsch, John Lane, Cristina Nita-Rotaru,Josh Olsen, David ZageAbstract— This paper presents the first hierarchical Byzantinetolerant replication architecture suitable to systems that spanmultiple wide area sites. The architecture confines the effects ofany malicious replica to its local site, reduces message complexityof wide area communication, and allows read-only queries tobe performed locally within a site for the price of additionalhardware. A prototype implementation is evaluated over severalnetwork topologies and is compared with a flat Byzantine tolerantapproach.I. INTRODUCTIONDuring the last few years, there has been considerableprogress in the design of Byzantine tolerant replication sys-tems. The current state of the art protocols perform very wellon small-scale systems that are usually confined to local areanetworks. However, current solutions employ flat architecturesthat introduce several limitations: Message complexity limitstheir ability to scale, and strong connectivity requirementslimit their availability on wide area networks that usuallyhave lower bandwidth, higher latencies, and exhibit networkpartitions.This paper presents Steward, the first hierarchical Byzantinetolerant replication architecture suitable for systems that spanmultiple wide area sites, each consisting of several serverreplicas. Steward assumes no trusted component in the en-tire system, other than a valid mechanism to pre-distributeprivate/public keys.Steward uses a Byzantine tolerant protocol within each siteand a lightweight, benign fault tolerant protocol among widearea sites. Each site, consisting of several potentially maliciousreplicas, is converted into a single logical trusted participant inthe wide area fault-tolerant protocol. Servers within a site runa Byzantine agreement protocol to order operations locally,and agree upon the content of any message leaving the sitefor the global protocol.Guaranteeing a consistent agreement within a site is notenough. The protocol needs to eliminate the ability of mali-cious replicas to misrepresent decisions that took place in theirsite. To that end, messages between servers at different sitescarry a threshold signature attesting that enough servers at theThis work was supported in part by grant FA8750-04-2-0232 from theDefense Advanced Research Projects Agency.Y. Amir, C. Danilov, J. Kirsch and J. Lane are with Johns HopkinsUniversity, Baltimore, MD. tel: 410 516-5562, fax: 410 516-6134. {yairamir,claudiu, jak, johnlane}@cs.jhu.edu. D. Dolev is with The Hebrew Universityof Jerusalem, Jerusalem, Israel. tel: +972 2-658-4116, fax: +972 2-5-70-90-40. [email protected]. C. Nita-Rotaru, J. Olsen and D. Zage are with PurdueUniversity, West Lafayette, IN. tel: 765 496-6757, fax: 765 496-3181. {crisn,jolsen, zagedj}@cs.purdue.edu.originating site agreed with the content of the message. Usingthreshold signatures allows Steward to save the space andcomputation associated with sending and verifying multipleindividual signatures. Moreover, it allows for a practical keymanagement scheme where servers need to know only a singlepublic key for each remote site and not the individual publickeys of all remote servers.The main benefits of our architecture are:1) It reduces the message complexity on wide area ex-changes from N2(N being the total number of replicasin the system) to S2(S being the number of wide areasites), considerably increasing the system’s ability toscale.2) It confines the effects of any malicious replica to itslocal site, enabling the use of a benign fault-tolerantalgorithm over the wide area network. This improves theavailability of the system over wide area networks thatare prone to partitions, as only a majority of connectedsites is needed to make progress, compared with atleast 2f + 1 servers (out of 3f + 1) in flat Byzantinearchitectures.3) It allows read-only queries to be performed locallywithin a site, enabling the system to continue servingread-only requests even in sites that are partitioned.4) It enables a practical key management scheme wherepublic keys of specific replicas need to be known onlywithin their own site.These benefits come with a price. If the requirement is toprotect against any f Byzantine servers in the system, Stewardrequires 3f + 1 servers in each site. However, in return, it isable to overcome up to f malicious servers in each site.Steward further optimizes the above approach based on theobservation that not all messages associated with the wide areafault-tolerant protocol require a complete Byzantine orderingagreement in the local site. A considerable amount of thesewide area messages require a much lighter local site step,reducing the communication and computation cost on thecritical path.The paper demonstrates that the performance of Stewardwith 3f +1 servers in each site is much better even comparedwith a flat Byzantine architecture with a smaller system of3f + 1 total servers spread over the same wide area topology.The paper further demonstrates that Steward exhibits perfor-mance comparable (though somewhat lower) with commonbenign fault-tolerant protocols on wide area networks.The Steward system is completely implemented and iscurrently undergoing a DARPA red-team experiment to assess2its practical survivability in the face of white-box attacks(where the red team has complete knowledge of system design,access to its source code, and control of up to f replicas ineach site). We hope to be able to report on the insight gainedfrom this activity in a final version of this paper.The remainder of the paper is presented as follows. Weprovide a more detailed problem statement in Section II. Wepresent our assumptions and the service model in SectionIII. We describe our protocol, Steward, and provide a sketchfor a proof that it meets the specified safety and livenessproperties, in Sections IV and V. We present experimentalresults demonstrating the improved scalability of Steward onwide area networks in Section VI. We discuss previous workin several related research areas in Section VII. We summarizeour conclusions in Section VIII.II. BACKGROUNDOur work requires concepts from fault tolerance, Byzantinefault tolerance and threshold cryptography. To facilitate thepresentation of our protocol, Steward, we first provide anoverview of three representative works in these areas: Paxos,BFT and RSA Threshold