#  Byzantine Consensus, and PBFT

## Simple example: Two Generals

![](byzTwoG.png)

- one is a decider:
- both need to attack same time
- need to agree on:
  - time: (easy: msg and an ack)
  - agreement to attack (hard)

&nbsp;<p>
&nbsp;<p>
&nbsp;<p>
&nbsp;<p>

**Example:**
A sends to B "attack at 10".
But did B get it? Can't go unless sure.
B sends an ack,
but did A get the ack?

&nbsp;<p>
&nbsp;<p>
&nbsp;<p>
&nbsp;<p>

### Impossibility

Look at sequence of msg-ack-ack......

Assume there is some subset of i msgs that constitutes a proof, and
that both would attack.  

However, what if the last msg not delivered?
  - receiver presumably would not attack
  - sender, though, sees same msgs as the i-sequence, and so  attacks....

&nbsp;<p>
&nbsp;<p>
&nbsp;<p>
&nbsp;<p>

### Fix?
- A sends a whole bunch, assume one gets through
- A and B send and ack a while

However, *provable agreement between even two parties in asynchronous
environment not possible*.

&nbsp;<p>
&nbsp;<p>
&nbsp;<p>
&nbsp;<p>

## Two Lieutenants Problem

*Safety*:
- all loyal lieutenants make same decision
- all loyal lieutenants follow loyal general

&nbsp;<p>
&nbsp;<p>
&nbsp;<p>
&nbsp;<p>

![](byzL.png)
&nbsp;<p>
Clearly impossible for both lieutenants to always make same decision, as neither knows if the fault
  lies with the general or the other lieutenant.  **Therefore, no solution when *n = 3f*.**

&nbsp;<p>
&nbsp;<p>
&nbsp;<p>
&nbsp;<p>

![](byzL3.png)
&nbsp;<p>
Each lieutenant decides based on majority of input, done! **So *3f+1* works, at least in the case of *f=1*.**

&nbsp;<p>
&nbsp;<p>
&nbsp;<p>
&nbsp;<p>


![](byzAlb.png)
&nbsp;<p>



Byzantine faults means byzantine protocols. *3f+1* nodes needed to tolerate *f*
faults.
- (Above) showed impossibility of *3* nodes to tolerate a single fault
- Proof by contradiction:
    - Assume we have a protocol, "BYZ3", that works even if one third of its members are faulty.
    - Have *3* Byzantine generals each simulate *m* Albanian generals via the above protocol.
      - Since only one Byzantine general is faulty, the other *2m*
        generals are simulated correctly, so the situation is identical to
        having *2f* non-faulty generals and *f* faulty generals.
      - If BYZ3 is correct, this simulation will reach the correct conclusion.
      - However, there are **really** only *3* generals, meaning we have
        solved the problem for *3* generals with a single faulty node, which we
        know to be impossible. 
  - Contradiction!


## Different Problems
- Byz generals also called *byzantine broadcast*.
  - sync: *f < n-1*
  - async *f < n/3*
- Byz agreement: trying to decide the truth by quorum consensus ("sky is blue" vs "sky is red")
  - sync: *f < n/2*
  - async *f < n/3*

## Castro's proof of *3n + 1* for Byz Agreement
- must be possible to make progress w/ only *n - f* replicas (because *f* might be faulty and choose not to respond)
- however, the *f* not responding might be correct but slow (asynchrony), so there might be *f* bad responses out of the *n - f*
  - implies *(n - f - f) > f*, or *n >= 3f + 1*



# Practical Byzantine Fault Tolerence  (Castro and Liskov)

## Assumptions
- operations are deterministic
- replicas start in the same state
Means that correct replicas will return identical results.

## Differences from fail-stop consensus
- 3*f*+1 replicas instead of 2*f*+1
- 3 phases instead of two
- cryptographic signatures

**Properties**
- safety, liveness (*n >= 3f+1*)
  - can't prove both in async environment
  - safety guaranteed through protocol
  - liveness "guaranteed" with reasonable assumption on msg delays
  - performance
    - one round trip for reads
    - 2 round trips for read/write

**Independent failure modes**
- different security provisions (root passwd etc)
- different implementations  !!


**byzantine faults**
- adversary(s) can
  - coordinate faulty nodes
  - delay communication of non-faulty nodes (but not indefinitely)
- equivocation
  - saying "yes" to Larry, "no" to "Moe"
- lying about received messages
- guarantees:
  - safety and liveness (assuming only *floor(n-1/3)* faulty, *delay(t)* does not grow faster than *t* indefinitely

**cool things**
- much more robust/secure than paxos
- one extra round, at most
  - little other cost
- authenticators



![pbft normal case](pbftNormal.png)

## Phases
- *pre-prepare* and *prepare* phases order request even if primary lying
- a replica is *prepared* when:
  - has received a proper pre-prepare from primary, sig, current view
  - 2*f* "prepares" from other replicas that match it
  - Such a replica then:
    - multicasts "commit" to other replicas
  - a replica is committed-local iff:
	- *committed*, and 
    - has accepted 2*f*+1 commit msgs (possibly including it's own)
  - system is *committed* iff *prepared* true for *f*+1 replicas
    - *committed* true iff *committed-local* true for some non-faulty replica
	

## Optimizations
- Most replies to clients just hashes of authenticated proof.
  - a single replica sends entire proof
- Replicas execute once *prepared* and reply to clients before commit
  - client waits for 2*f*+1 matching replies
  - message delays down from 5 to 4
- Read-only ops send directly to all replicas
  - rep waits until prior ops committed
  - client waits for 2*f*+1 replies
- **authenticators**. Rather than public-key sig among replicas:
  - assume symmetric key between each replica pair
  - rep *r* signs by encrypting msg digest w/ each other rep
  - vector of such sigs is the **authenticator**

