Reasoning about Byzantine Fault Tolerance

BFT consensus is essential for Tor, Bitcoin, & other cryptocurrencies
BFT consensus lets have consistent sytems when
  • Some of the computers are controlled by the adversary
  • The network is acting against us
Without BFT,
  • An attacker could force Tor users onto attacker controlled routes
  • An attacker could trick a user user into thinking Bitcoin had been transferred
History
Bitcoin is special. Demonstrated the possibility of consensus at Internet scale.

New protocols are appearing at an increasing rate

How do you tell if these things are secure? What does secure even mean?

Reading BFT paper is really hard. Every paper describes a complicated state machine.
Let's talk about BFT in different terms.
Pretend you are peer. You are looking for evidence that a message from the network is safe to accept.
Peers must evaluate the messages they recieve for evidence of the following.
  • Was the message created by an authorized user?
  • Do other peers see the same message as I am?
  • Is the equal or better competition to this message?
Interpreting BFT proposals in this fashion provides a baseline.
Liveness vs Safety
I'm going to focus on safety.
Let's Explore How Several Consensus Protocols produce this evidence.
  • Bitcoin's Proof of Work
  • Tendermint
  • Honeybadger
Every Protocol has safety limits when exceeded the evidence becomes meaningless.
Consensus protocols must provide 3 kinds of evidence to achieve basic safety.
  • Proof of correct block generation
  • Proof of block distribution
  • Proof of uniqueness
Proof of Work/ Nakamoto Consensus (2008)
by Satoshi Nakamoto
Consensus in a slide.
  • Manipulate free values in a block of message until bignum(hash(block)) < threshold
  • If when peer find a competing block at a given height, compare the total of the bignums and choose the smallest
Anonynmous consensus. There is no PKI for consensus particpants.
Evidence of correct message generation.
Translated in to a number the block header hash is below the threshold.
Evidence of network broadcast.
As future new correct blocks are generated, users become inceasingly confident that a block was disseminated.
Evidence of competing messages.
As total work in a chain increases, it become difficult but no impossible for another chain to exist.
Safety: 51% of hashing power is honest.
Tendermint (2014)
by Jae Kwon
Consensus in a slide.
  • Leader for a time segment is deterministically psuedo randomly selected
  • Blocks becomes valid after 2/3rds of validators have signed the block as correct
Simplicity is Tendermint's main virtue.
Evidence of correct message generation.
Block generated by the deterministically elected leader
Evidence of network broadcast.
Witness signatures from 2/3rd of validator network
Evidence of competing messages.
2/3rds of the network must collude to generate a competing message
Honeybadger (2016)
By Andrew Miller et al.
Consensus in a slide `
  • Generate a threshold descryption key.
  • Send a encrypted tx, key share and sig to other validators.
  • When a validator can decrypt a block, blockcast for witness signatures
  • Acccumulate 2/3rds of witness signatures
Asynchrony
Leaderless consensus through the Asynchonous Common Set
Evidence of correct message generation.
Threshold decryption of transaction shares.
Evidence of network broadcast.
Witness signatures from 2/3rd of validator network
Evidence of competing messages.
2/3rds of the network must collude to generate a competing message
The need to produce evidence that peers can evaluate leads to many similarities between consensus algorithims

Discussion of attacks or blockchain systems in general