Questions

1. How many replicas, and what should be the quorum size of BFT?

   1. In Paxos, we need n-f > n/2 => n > 2f => 3 nodes tolerate 1 failure node.

   2. But in PBFT, this is not possible. n-2f > f => n>3f. n = 3f+1 at least

      n=3f+1 servers, 𝑓 of which can be faulty. Unlimited clients

   3. Any two quorums must interact at the latest one honest node, quorums size = 2f+1

2. Setup:

   1. Servers and clients can sign messages with a public key and verify them with a private key.
   2. The whole system run in a view-stepped way, where each view has primary and many backups. Primary accepts a new command from the client, assigns a slot number, and then syncs to backup.
   3. Matching rule: all replicas have the same ‘n’ and D(s)
3. What if the primary is faulty?

   1. Send wrong to other backups,

      Replicas communicate with each other to ensure the commons. => need pre-prepare

   2. Send different results to the client.

      All replica sends to the client, and the client waits for the +1 matching result.

   3. Ignore clients

      View-change to switch to a new leader. No need to elect, already know who is the next.

   4. What if the faulty primary or faulty backup impersonates each other?

      Sign with PK to ensure no one can be another node.

4. What if the backup is faulty?

5. The client has access control to not faulty.

6. Basic protocols,

   1. pre-prepare

   2. prepare certificate,

      1. why need 2f+1 =>

         2f prepare from other replica and one pre-prepare from primary matching value for a single slot

         => Those form 2f+1

         => every 2f+1 must have at least one honest node interaction; the honest node cannot send different commands.

         => finally, since 2f+1 are matching, thus they must have the same ops as the honest node.

         => And the replica knows another replica has received the same value at the same slot.

      2. Can we commit now?

         No, since the replica doesn’t know if others have received 2f+1 matching prepare+pre-prepare messages.

         So we need another round of communication to tell each replica that the majority have accepted the correct value for this slot (2f+1 matching)

   3. commit certificate, why need 2f+1

      Only when the replica has prepared the certificate can it send a commit message

      => once an image receives 2f+1 prepare a certificate; it knows other all 2f+1 have prepared a certificate.

   4. The client waits for f+1 matching replies.

      No need for 2f+1 because f+1 already has a current result?

      PBFT ensures that Once the replies, the operation is committed. So as long as getting one reply from the honest node, then the answer is correct. f+1 replies contain at least one non-faulty since at most f replicas can be faulty. (f crashed nodes are not replying ?)

7. View Change

   1. Backups monitor the primary. If the primary stops are responding to pings or the backups timeout executing requests, they start a view change.

   2. All replicas send to the new primary, and the new primary then sends to all replicas with a new view change.

   3. Backup send all prepared certificates. (set P) => with which new primary can check which operation is already committed.

   4. primary send it to all replicas, including all gathered prepared certificates, with which replica can verify the primary is not faulty.

      There are also pre-prepare messages, which are used for re-executing them at the new leader’s side

8. Garbage collection

   servers periodically decide on a check-point (2f+1)

9. Safety and Liveness

   It cannot guarantee liveness, the same as Paxos.

   It cannot scale well.

   AlgoRand/HotStuff => performs better and is being used.

10. From PBFT to HotStuff, async => sync.

Introduction

Assumption

1. Run in an asynchronous distributed system

   where nodes are connected by a network.

   The network may fail to deliver messages, delay them, duplicate them, or deliver them out of order.

2. Independent node failures.

3. It uses cryptographic techniques, Signing a digest of a message and appending it to the plaintext of the message.

4. Fault node can have a strong adversary and is computation bound. It cannot break hash encrtpy,

Properties

1. Safety:

   1. Definition: Replicated service satisfies linearizability (behaves like a centralized implementation that executes operations atomically one at a time)

   2. Requires:

      1. Faulty replica f < n/3

      2. Replica runs deterministically, and they must start in the same state.

         => all non-faulty replicas agree on total order for executing requests despite failures.

      3. Faulty client: Access control

2. liveness

   It relies on synchrony to provide liveness.

   Delay is the time between the moment when a message is sent for the first time and the moment when it is received by its destination.

   View change protocol prevents primary from failure.

3. 3f + 1 nodes can use tolerant f faulty nodes. n-2f > f => n > 3f

4. Algorithms

   Refers to the above

   • client request
     • timestamp: for exactly-once semantics

   pre-prepare + prepare => to ensure the total order of the operation. (ensure each operation has a single slot. )

   committed and committed_local

5. Optimizations

---

• ← Previous Post
• Next Post →