Byzantine Replication for Trustworthy Systems

This project seeks to reduce the complexity of building systems that are both fault tolerant and secure. Reasoning about such systems is hard and, to compound the challenge, fault-tolerance and security do not integrate nicely---for instance, the very replication that improves data integrity and availability against faults, harms confidentiality because it offers an attacker the opportunity to break into the least protected of the replicas. Because the Byzantine failure model encompasses arbitrarily faulty behavior---and therefore models, as special cases, nodes that misbehave because they are either executing upon faulty hardware, or running buggy software---Byzantine fault tolerance (BFT) has the potential of serving as the single key that opens both the fault-tolerance and security coffers.

To advance this agenda, we have developed solutions that significantly improve the capabilities and reduce the cost of Byzantine fault tolerant techniques by revisiting Byzantine replication protocols from first principles. In particular, we have focused on:

Selected Technical Highlights

In our paper:

we present a new quorum-based algorithm that provides the abstraction of an atomic register using a provably minimal set of 3f + 1 storage nodes. Prior art achieved this lower bound only when the data being stored was self-verifying, i.e. data that could not be undetectably altered by a faulty server (such as data that have been digitally signed): with generic data, implementing even the much weaker safe register abstraction required 4f + 1 nodes. Our result proves that, surprisingly, generic data can be stored as efficiently as self-verifying data both in terms of consistency guarantees and number of replicas.

To reduce the costs of Byzantine state machine replication, we propose in

a new architecture that separates both logically and physically the responsibility of reaching agreement on the sequence of state machine commands to be executed from the actual execution of these commands. This separation yields two key advantages.

First, it reduces replication costs: by assigning the task of producing a total ordering of commands to a cluster of simple, inexpensive, and application-independent agreement nodes, we can reduce the number of the expensive and application-specific state machines in the execution cluster from 3f + 1 to 2f + 1. Second, it suggests an approach that addresses efficiently, for the first time, the challenge of preventing Byzantine state machines from leaking confidential information to Byzantine clients: inserting a privacy firewall between the agreement and execution clusters lets the state machines in the execution clusters continue to access the service state in the clear, but filters out, before they can reach a client. any responses that could not have been produced by a correct state machine replica.

Because agreement nodes are inexpensive, it becomes possible to use them more liberally. In

we use this flexibility to derive the first asynchronous Byzantine consensus protocol that, in the common case, achieves consensus in just two communications steps, and prove that our protocol is optimal both in the number of steps, and in the number of agreement nodes it requires (5f+1).

To reduce the cost and simplify th design of Byzantine fault tolerant state machine replication, we propose in

to allow replicas to respond to a client's request without first running an expensive three-phase commit protocol to reach agreement on the order in which the request must be processed. Instead, they optimistically adopt the order proposed by the primary and respond immediately to the client. Replicas can thus become temporarily inconsistent with one another, but clients detect inconsistencies, help correct replicas converge on a single total ordering of requests, and only rely on responses that are consistent with this total order. This approach allows Zyzzyva to reduce replication overheads to near their theoretical minima.

Please see the following list of relevant publications for our latest papers-we will add short descriptions of Zyzzyva and SafeStore in the near future.

Relevant Journal Publications:

Relevant Conference Publications:

Faculty

Students

Alumni

External collaborators

Sponsors

This material is based upon work supported by:

Back to Lorenzo Alvisi's Home page.