Practical Byzantine Fault Tolerance (PBFT): Key Ideas

All images are from the presentations available in the References section. The keynotes have been collected from the original paper “Practical Byzantine Fault Tolerance” by Miguel Castro and Barbara Liskov, which is available here.

Byzantine faults: Occur when a faulty process can behave arbitrarily and maliciously, potentially colluding with other faulty processes to disrupt the system.

Consensus: The process through which nodes in a network agree on a common decision even in the presence of these failures.

Motivation: The motivation for studying Byzantine Fault Tolerance (BFT) arises from our increasing reliance on critical infrastructure services running on computers, which can fail due to software errors, failures, or malicious attacks. The solution to this problem is replication.

Replication algorithm:

• Masks a fraction of faulty replicas
• High availability if replicas fail “independently”
• Software replication allows distributed replicas

Figure 1: Why state machine replication can help [2]

Assumptions

· A wrong assumption was replicas failed by stopping or omitting steps, but in reality, Byzantine faults allow faulty replicas to behave arbitrarily.

· Another assumption was about synchrony, which means assuming bounds and delays between process time to take actions and deliver messages. Solution: Asynchrony — PBFT (Safety & Liveness).

· Another assumption is considering bound on faults, which is incorrect because it’s challenging to detect Byzantine faults, especially since faults may not be independent. The proposed solution involves abstraction and proactive recovery.

Algorithm

All replicas can fail if at most “f” fails in the window. Moreover, in optimal we should have 3f+1 total replicas. The goals include:

· Safety (Linearizability): The service behaves as if there is a single correct centralized service that never failed. In other words, all non-faulty replicas agree on sequence number requests that commit locally.

· Liveness: Clients eventually receive replies to their requests— allow the system to make progress when primary fails (only for liveness we will need an eventual synchrony or time bounds). The PBFT uses exponential back-off to make sure at least 2f+1 non-faulty replicas share the same view if replicas are unable to execute a request.

State machine replication:

• Deterministic replicas start in the same state
• Replicas execute the same requests in the same order
• Correct replicas produce identical replies

Figure 2: Overview of Practical Byzantine Fault Tolerance (PBFT) [2]

View: This is an integer, replicas go through a sequence of increasing views, primary replica “i” is designated based on (i = v mod N), and other replicas are backups.

Primary: Pick the correct ordering

Backups: Ensure the primary behaves correctly (certify correct ordering), trigger view change if the primary is faulty

Quorums and Certificates

Quorums: A set of replicas that is big enough to overlap with the next set of replicas to carry out the next operation. In this system, quorums have to have at least 2f+1 replicas. Consider the below example image of one failure among three correct replicas. When you consider the below quorums and replicas (A and B) you will notify when you consider 2f+1 replicase in each quorum they will intersect in f+1 replicas which also guarantees the quorums always intersect in at least one non-faulty replica. That is why it guarantees that whatever happens in an earlier operation can be reflected in a later operation (you propagate the truth in the one non-faulty replica).

Quorum Certificate: A set of identical messages that a replica accumulates from a quorum agreeing on the same statement. Algorithm steps are justified by certificates.

Figure 3: Quorums should intersect in at least one correct replica

Normal Case

• Three phases algorithm — pre-prepare, prepare, and commit — to ensure requests are processed in a consistent order
• Messages are signed
• Replicas store messages using logs
• In the pre-prepare phase, the primary assigns a sequence number n to request m in view v. The condition “in the view” is important because it ensures that a faulty primary cannot stop a replica by sending a faulty pre-prepare message multiple times.
• All the backups process the messages in the order of sequence numbers
• If backup i accepts the pre-prepare message, it will enter the prepare phase and multicast the prepare message to all other replicas. It will add both messages (pre-prepare message received and prepare message sent) to its log.

Figure 4: Pre-prepare and Prepare phases of PBFT

• All the replicas should receive one pre-prepare message and 2f prepares from different backups corresponding pre-prepare. (2f+1 votes from primary + non-faulty replicas) matching prepare message to allow sign message (certificate) quorum (Shown in the above figure as prepared). Besides that, it is shown no P-certificates with the same view and sequence number for different requests. (How?)

Figure 5: Why no such two different requests with the same P-certificates [2]

• Commit phase: We have stored P-certificates stored at quorums but no one knows about it. We have to commit a message, to say that I have a proper certificate by multicasting message.

Figure 6: Commit phase of PBFT

Request Execution

• The protocol is operating asynchronously, so there can be many messages in the process of being processed. When you find it is ok to request sequence number x, you will wait at that point until in case number x-1 and all lowest hadn’t been done yet.
• Each replica sends a reply to the client.
• Client collects replies from replicas, return result appears in at least f+1 replies.

Figure 7: The logic behind why the client needs to collect at least f+1 same answers

View Change

We do primary change because of timeouts or primary misbehaving (receiving f+1 view change messages). If the timer expires at v, the backup starts a view change to move the system to view v+1. Although, we need to ensure that replicas stay in the same view long enough to progress. If malicious replicas can make you move quickly that can lead to impede progress. Plus, we need to prevent some kinds of Denial-of-Service attacks. Backup starts a timer when it receives a request, and the timer is not already running. The timer is stopped when the request is executed and restarts when a new request comes. On timer expiry, a backup stops accepting messages except:

1. View-change

2. New-view

3. Checkpoint

The idea behind the safety view change is that you only execute a request if you have a commit certificate (for the request with a specific request number). We want to make sure that we will never get commit certificates with the same sequence number in different requests across any view. We also know if a replica got a committed certificate, then went ahead and executed the request it got a certificate from a quorum and if we go and take any other quorum it’s going to intersect at least one correct replica and that correct replica is going to have a prepared certificate for that same request in some view and sequence number. So basically, when we change the view, we’re going to take a quorum and ask what do you know and we’re going to use these prepare certificates to decide which request we need to repropose with a certain sequence number in the new view to keep things consistent with the past views.

When the primary has a timeout it multicast a view-change message to all the replicas along with v+1, the sequence number of the last stable checkpoint n, a set of 2f+1 valid checkpoint messages proving the correctness of checkpoint, a set like P containing messages initiated in previous view v with higher sequence number and has not yet committed (because after view change is done, we should take care of these request messages). The view change is initiated after receiving 2f view change messages.

Figure 8: View change protocol establish [2]

Figure 9: New primary in v+1 introduced [2]

Figure 10: New view message [2]

Figure 11: Proof of View change safety [2]

View Change Without Signatures

Figure 12: Illustrates how each replica denotes a message with the vector of MACs [2]

• Why do we need this? Because of fast authentication.
• How? Use MAC instead of DS (Digital Signatures) because MAC is 1000x faster than public key.
• Problem with MAC? It's weaker than signatures (MAC proves to the receiver that it sent a message but cannot prove authenticity to others).

Solution:

We know in normal cases we get messages received from the quorum. The problem is in view change. Here, P is for P-certificates we collected (we know we have) but cannot prove to others and Q is for any prepare / pre-prepare message if I was primary. Here we need a new type of message called VIEW_CHANGE_ACK message. It is going to be used when a new primary asks the quorum if the view change message is sent by a specific replica in the quorum or not. It’s going to replace verifying signatures on view change messages.

Figure 13: New view change protocol [2]

Figure 14: New view change protocol [2]

Figure 15: Supporting claims with view change without signature [2]

The problem here is Incorrect claims may be supported.

Figure 16: A false supporting claim must be resolved with wait [2]

The solution is to wait for correct replicas (There are 2f+1 correct replicas that do not lie so the new primary waits for the 2f+1 view change message without conflicting claims about prepared requests).

Garbage Collection

As we have collected all the sequence numbers from the beginning, we should have garbage collection. Here we need to make sure that the amount of state that we use is bounded such that if denial of service doesn’t allow you to progress you never have to throw away the state that you don’t need lighter because after the denial of service goes away you want to be able to make progress.

Figure 17: Garbage collection

Periodically checkpoint state (K), every K sequence numbers and multicast that checkpoint and replicas are going to collect these checkpoints from the quorum again like before and we call checkpoint with an S-certificate a stable checkpoint so S-certificate (h, checkpoint) is 2f+1 checkpoint messages. When that happens, we can truncate the messages from the log. We use an efficient checkpoint creation using incremental digests with the Merkle tree.

Optimization

1. Digest replies

• Only one replica sends the result in the reply message
• Other replicas send result digests
• Change the replica designated to send the result on retransmission
• Balances bandwidth utilization across replicas

2. Optimistic execution

• Execute prepared requests (after getting a P-certificate)
• Rollback execution of uncommitted requests in view changes
• Clients must collect 2f+1 matching replies
• Can piggyback commits in pre-prepares and prepares

3. Read-only optimization

• Read-only operations executed in the current state
• Clients must collect 2f+1 matching replies
• Retransmit request as read-write if this fails

4. Separate request transmission

• The client doesn’t need to send a message with the primary and the primary relays it
• The client can send it to everybody and the primary sends a digest along with the messages
• Increase parallelism
• Reduce the cost of processing pre-prepare message

5. Batching

• Run algorithm on a batch of requests
• The amortized cost across the batch
• Use sliding window to minimize impact on latency
• Significantly improves throughput

Performance Evaluation

Figure 18: Modeling real-world performance evaluation of the PBFT [6]

References:

1. https://pmg.csail.mit.edu/papers/osdi99.pdf [Practical Byzantine Fault Tolerance]

2. https://www.youtube.com/watch?v=Q0xYCN-rvUs

3. https://www.youtube.com/watch?v=Uj638eFIWg8

4. https://www.youtube.com/watch?v=R4qpq0zDnyw

5. https://www.youtube.com/watch?v=BphPtmY1J9U

6. https://www.youtube.com/watch?v=Jj6hVs1SF3E