[1999.2]Practical Byzantine Fault Tolerance

pbft.txt

It uses only one message round trip to execute read-only operations and two to execute read-write operations.

Survives in asynchronous networks.

Messages contain public-key signatures, message authentication codes, and message digests produced by collision-resistant hash functions.

<m>sign(i): message m signed by node i.

D(m): digest of message m.

R: set of replicas.

views: The replicas move through a succession of configuration.

1. A client sends a request to invoke a service operation to the primary
2. The primary multicasts the request to the backups
3. Replicas execute the request and send a reply to the client
4. The client waits for f + 1 replies from different replicas with the same rsult; this is the result of the operation.

<REQUEST,o,t,c>sign(c): A client c requests the execution of state machine operation o. Timestamp t is used to ensure exactlyonce semantics for the execution of client requests.

<REPLY,v,t,c,i,r>sign(i): v is the current view number, t is the timestamp of corresponding request, i is the replica number, and r is the result.

When the primary receives a client request, it starts a three-phase protocol to atomically multicast the request to the replicas.

pre-prepare: <<PRE_PREPARE,v,n,d>sign(p), m>: v view, m mseeage, d digest.

prepare: backup i multicasting a <PREPARE,v,n,d,i>sign(i) to all other replicas and adds both messages to its log.

commit: Replica i multicasts a <COMMIT,v,n,D(m),i>sign(i) to the other replicas when prepared(m,v,n,i) becomes true.

view-change: triggered by timeouts.

<VIEW-CHANGE,v+1,n,C,P,i>sign(i) to all replicas.

<NEW-VIEW,v+1,V,O>sign(p) to all other replicas.

use message authentication codes.

NFS, BFS.