Byzantine Fault Tolerance (BFT)

Abridge WIKI contents for an arbitrary sequence that I studied.

Byzantine Fault Tolerance is able to abbreviate to BFT.

Prelim.

It doesn’t matter if the below is perceived or not.

• BFT is a fault-tolerant distributed system, which is able to keep tolerable from vaudeville failures in which there are two types; a crash failure or a Byzantine failure associated with Byzantine Generals’ Problem. The level of toleration and the cognizance of the failures are both indecisive, which means they should be determined by use cases.
• Byzantine Generals’ Problem, which is recognized as the failure in BFT, is a generalized version of  Two Generals’ Problem.
• Byzantine Generals’ Problem is unsolvable that is no definite, specific solution or algorithm. There is only a tolerant method such as BFT.

Byzantine Generals’ Problem

This article is able to guide to more detailed, precise elucidation. The below is recapitulated version of details.

• Assumption
  • There is 5 generals to conquer a defensive city; for example, A, B, C, D, and E.
  • There is a possibility a few of them is a traitor.
  • They have to communicate a certain message that is described an offense time to attack simultaneously, they would be defeated when they attack separately.
• Scenario
  • General A start to send the message “Attack 9:00 am tomorrow.” to B, B would relay to C, C to D, D to E, and E to A. The method of communication is able to be diverse and various.
  • when general C is a traitor, C could fabricate the message to rewrite the time. D and E would relay the wrong message until A. The A could know there is more than one traitor.
• Problem
  • Who is the traitor(s)?
  • How to send a new message to abort the attack in this situation? The traitor could concoct this message again.
  • How to reach a consensus?

Problems could be various depending a scenario.

Paxos

The below is abridged this article, Paxos Made Simple.

• It is an algorithm to implement a fault-tolerant distributed system.
• The core algorithm, synod, is a consensus algorithm.
• It cannot handle the corrupted message, which is considered in BFT.

Consensus algorithm

• Processes propose values. –> one single value is chosen. –> processes learn the chosen value.
• 3 classes of agents; proposers, acceptors, and learners
• non-Byzantine model
  • Agents
    • operate at arbitrary speed
    • fail by stopping/restart
    • How if all agents fail after a value is chosen?
      • save the chosen value
      • redo a process
      • ignore the chosen value
  • Messages
    • be delivered as an arbitrary length, duplicated, and lost
    • be not corrupted
• Choosing value, C(v)
  • 1 acceptor
    • A proposer proposes to an acceptor –> C(v) –> processes learn
    • How if a acceptor fails during ‘C(v)’ ?
  • i acceptors (i > 1)
    • A proposer proposes to i of acceptors –> C(v) –> processes learn
    • Choose a only single value that is accepted by the majority of acceptors, which is accepted by a generalization of a majority, among proposed values by proposers.
  • A proposal (P) consists of a proposal number (n) and a value (v), P (n, v)
    • When an acceptor A accepted P(a, v), the A can accept P(b, v) with (b > a).
  • Proposer for issuing proposals
    1. A proposer chooses a new proposal number n and asks a prepare request to acceptors: Prepare(n)
    2. If responses from a majority of the acceptors are received, issue a proposal P(n, v) in which v is the value of the highest-numbered proposal among the responses or any value if no proposal.
    3. A proposer requests to accept the proposal P(n, v): Accept(P(n, v))
  • Acceptor to respond to requests of a proposer
    • An acceptor can always respond to a Prepare(n) request.
    • If an acceptor has responded to a Prepare(n) request before, the acceptor can always respond to a Accept(P(n, v)) request.
    • An acceptor can respond to a Accept(P(n, v)), even though the acceptor accepted a proposal P(n’, v) with n < n’, if it has not responded a Prepare(n) request before.
    • An acceptor must remember the highest-numbered accepted proposal and the number of the highest-numbered Prepare(n) request to be prepared for failures.
  • Algorithms
    1. A proposer’s request to a majority of the acceptors: Prepare(n)
    2. An acceptor’s response to Prepare(n):
       • if n > n’ (previous Prepare(n’)),
       • with a promise not to accept any proposals P(n”, v) with n > n”,
       • with the highest-numbered accepted proposal, if any.
    3. The proposer’s request: Accept(P(n, v))
       • v is the value of the highest-numbered proposal among responses,
       • or v is any value if no proposals among responses.
    4. An acceptor’s response to Accept(P(n, v)), and accepts:
       • if not responded to a previous Prepare(n’) with n < n’.
• Learning a chosen value, L(v)
  • A leaner must know an accepted proposal by a majority of acceptors.
  • Simple way
    • Each learner requests to all acceptors: n-request
    • Each acceptor responds to all learners: n-response
  • non-Byzantine failures
    • An acceptor –> a learner –> another learner –> …
    • How if a learner fails?
    • What if Byzantine failures?
  • General way
    • A group of learners

BFT

Early solution

• Encryption
  • Prevent to fabricate the message.
  • using public-key cryptography
    • Encrypt by private key.
    • Decrypt by public key. = cannot encrypt again.
  • using Cyclic Redundancy Check (CRC)
    • Supplement a unique check-value in the message.
    • If the message is changed, the check-value would indicate the fault.
• Atomic broadcast
  • If a hardware transmits the message at once, a different message could not be sent to each participants.
  • Further details in here.

Practical BFT (PBFT)

The below is condensed the article, Practical ByzantineFault Tolerance and Proactive Recovery. Compare with PAXOS algorithm upper.

• PBFT is a replication algorithm.
• BFS
  • BFS is BFT distributed file system, which is the real system to be made of the BFT library.