Explain Byzantine Generals Problem? Show the working of pBFT?

The Byzantine Generals Problem asks how loyal parties can reach agreement when some participants may be traitors sending conflicting messages; PBFT solves it in practice for \(n \ge 3f + 1\) replicas through pre-prepare, prepare and commit phases.

The problem (Lamport, Shostak and Pease, 1982). Several divisions of the Byzantine army surround a city. Generals communicate only by messengers and must agree on a common plan (attack or retreat). Some generals may be traitors who send different messages to different generals. Requirements:

• All loyal generals decide on the same plan.
• A small number of traitors cannot make the loyal generals adopt a bad plan (if the commander is loyal, every loyal general follows his order).

With oral (unsigned) messages, agreement is possible only if fewer than one-third are traitors, i.e. \(n \ge 3f + 1\). With 3 generals and 1 traitor, a loyal lieutenant cannot tell whether the commander or the other lieutenant is lying.

In a blockchain, the generals are nodes, the plan is the next block, and traitors are faulty or malicious nodes.

Working of PBFT (Castro and Liskov, 1999). There are \(n = 3f + 1\) replicas; one is the primary (leader), the rest are backups.

1. Request: the client sends a request to the primary.
2. Pre-prepare: the primary assigns a sequence number \(n\) in view \(v\) and multicasts PRE-PREPARE\((v, n, d)\) with the request digest \(d\).
3. Prepare: each backup that accepts it multicasts PREPARE\((v, n, d, i)\). A replica is prepared when it has the pre-prepare and \(2f\) matching prepares from others.
4. Commit: each prepared replica multicasts COMMIT. When a replica has \(2f + 1\) matching commits, it executes the request.
5. Reply: replicas send the result to the client, which accepts it after \(f + 1\) identical replies.

Client  --req-->
Primary  --pre-prepare--> all
Replicas --prepare--> all  (wait for 2f)
Replicas --commit-->  all  (wait for 2f+1)
Replicas --reply--> Client (wait for f+1)

View change: if the primary is faulty or too slow, backups time out and elect the next primary (\(p = v \bmod n\)).

Example: with \(n = 4\), \(f = 1\): one faulty node can be tolerated; prepares needed = 2, commits needed = 3.

Pros/cons: immediate finality and low energy, but \(O(n^2)\) messages, so it suits small permissioned networks.