Byzantine failure an arbitrary deviations of a process, which makes it the hardest failure to solve. BFSP deals with Compromised Servers, for Compromised Clients we use Authentication and Authorization.
-
Suppose you have N replicas, f of which might crash, which is non-Byzantine failure, what quorum size Q do you need to guarantee liveness and safety?
Liveness: (e.g. avoiding stuck states) There must be a non-failed quorum Hence: Q <= N - f
Safety:
Any two quorums must intersect at one or more nodes, otherwise, two quorums could independently accept operations, which is "quorum intersection"
Hence: 2Q - N > 0
So: N < 2Q <= 2(N - f) Note highest possible f: N < 2N-2f; f < N/2 And if N = 2f + 1, smallest Q is 2Q > 2f + 1; Q = f + 1
- Now say we throw in Byzantine failures, with N nodes, f of which might experience Byzantine failure, what quorum size Q do we need in Byzantine setting?
```{python}
Liveness:
Q <= N - f, as failed nodes might not reply
Safety:
Quorum intersection must contain one non-faulty node
Idea:
out of f+1 nodes, at most one can be faulty, since f could be malicious
Hence: 2Q - N > f
So: N + f < 2Q <= 2(N - f)
Hence: 3f < N; f < N/3
And if N = 3f + 1, then Q_min = 2f + 1
-
Extend the system to allow for more than (n-1)/3 failures over its lifetime?
Detect failed replicas using proactive recovery:
- recover the system periodically, no matter what;
- makes bad nodes good again
Practical Byzantine Fault Tolerance provides a replication based reliable protocol to a computation even in the presence of Byzantine faults. A client transmit a request, wait for k replies, conclude that the answer is a true answer.
PBFT is a state machine replication protocol,
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 1 replies from different replicas with the same result
- Normal Case Operation
NCP does not rely on ordered message delivery, therefore it is possible for a replica to commit requests out of order. This does not matter since it keeps the preprepare, prepare, and commit messages logged until the corresponding request can be executed, operation doesn't execute until prepared(m, v, n, i) is TRUE for f+1 non-faulty replicas. Client then accept result after 2f+1 matching tentative replies.
- Garbage collecting the message log and make periodic checkpoints
Broadcast <CHECKPOINT, n, d, i>, where d = digest of state, when 2f+1 signed CHECKPOINTs received, delete all messages below sequence number of stable checkpoint.
- View changes
When client doesn't get an answer, broadcasts message to all replicas
broadcast <VIEW-CHANGE v+1, n, C, P, i>
C is 2f+1 signed checkpoint messages for last stable checkpoint
P = {P_m} where each P_m is signed PRE-PREPARE + 2f signed PREPARES
P is set of all PREPAREd messages since checkpoint + proof that the messages really are prepared
When primary of view v+1 sees 2f signed VIEW-CHANGE messages from others
New primary broadcasts <NEW-VIEW, v+1, V, O>
V is set of at lesat 2f+1 VIEW-CHANGE messages (including by new primary)
O is a set of pre-prepare messages, for operations that are after last stable checkpoint, appear in the set P of one of the VIEW-CHANGE messages.O also contains dummy messages to fill in sequence number gaps
Replicas may optain any missing state from each other
(e.g., stable checkpoint data, or missing operation, since reissued pre-prepare messages only contain digest of request)
-
What happens if primary creates incorrect O in NEW-VIEW message?
Might send null requests for operations that prepared. Other replicas can compute O from V, and can reject NEW-VIEW message
-
What happens if primary sends different V's to different backups?
Still okay, because any committed operation will be in 2f+1 VIEW-CHANGE msgs of which f+1 must be honest, so at least one member of V will have operation. So new primary cannot cause committed operations to be dropped. Only operations for which client has not yet seen the answer
-
??? : an attacker might steal compromised replica's keys, with how many replicas will BFS work reasonably well?