[1] Byzantine Agreement: binary to multivalued

Extending Binary Byzantine Agreement To Multivalued Byzantine Agreement — Russell TURPIN and Brian A. COAN. (1984)

The original paper can be found here.

Preface

Hi there! This is the first article of the 3 Minutes Blockchain Paper series. The series has the solid aim of explaining and introducing a variety of academic papers in the scope of blockchain to readers who are interested to dive in.

The content is targeting readers with any background, yet will get into technical details from time to time, since this is a paper intro. Enjoy. :)

Background

Binary Byzantine Agreement

An algorithm for a group of Byzantine generals to agree on a common decision: attack or retreat, in spite of that fact that some treacherous generals are messing around with the consensus. [story]

Muhammed Al-Fatih and the Conquest of Constantinople

Multivalued Byzantine Agreement with HIGH COST

The cost of extending a binary Byzantine agreement algorithm to multivalue is too expensive when the transmission cost is very high. The larger the size of the value domain, the higher the cost. (E.g. transmitting value in range 0~3 doubles the cost of transmitting range 0~1)

Solution in brief

The paper devises a two rounds mechanism for a distributed peer-to-peer network to reach consensus on a value with arbitrary value domain V, that has its transmission cost significantly reduced and took place only in the first round.

Requirements

  • P: The total number of the participated processes
  • T: The upper bound of the number of the adversaries / faulty processes

→ Require P > 3T

Two rounds mechanism

First Round

  • Each process broadcasts its initial value (the value it wants to send a vote to) to every other process.

Second Round

  • Each process broadcasts a bit indicating whether it wants to send a message or not (null).

Third round and subsequent:

  • Follow the chosen binary algorithm

States of process

Perplexed

  • Somebodies disagree with me. In particular, in the first round, more than (1/2)*(P-T) initial value is different from mine.

Content

  • Not perplexed at all.
https://www.emojirequest.com/

Local variables of process j

There are two arrays v[] and p[] indexed by process ID and a Boolean value alert.

  • v(j): initial value of process j
  • v(i): initial value of process i
  • p(j): TRUE when this process is perplexed
  • p(i): TRUE when somebody (E.g. process i) indicates that it’s perplexed
  • alert: the indicator of applying the default value or not

Proof of correctness

Claims to be proved

  • Claim (1): all correct processes should get the same final result.
    AND
  • Claim (2): the final result equals common initial value when all correct processes start with identical initial value.

Proof of (2): easier

  • all correct process has the same value
  • → no correct process is perplexed
  • → they are contented and happy
  • → final result = initial values of everyone

Proof of (1): harder

alert = TRUE

  • all correct processes select the default value
  • → final result = default values

alert = FALSE

  • a subset contains the majority of correct processes (more than (1/2) * (P + T))
  • → each content process has the majority initial value
  • → at least T + 1 processes are correct and contented
  • → each perplexed process with p(j) is false for all content process
  • → everyone takes the contented value from the majority
  • → final result = initial values of the majority
All of them reach the multivalued Byzantine agreement!

Summary

This paper has proposed and succinctly demonstrates a two rounds mechanism to extend the binary Byzantine Agreement to multivalued. The proofs have deduced the correctness of the mechanism, which necessitates minimum requirements and local setups from the side of the participants.

Everything in layman’s terms (skip all and read this)

A group of voters want to vote for candidates they like, but they need to reach an agreement eventually. They are in a community which each of them can only communicate to another individual at a time to tell that person their own choice. However, some voters are tricky, who might tell different person a different choice of candidate. The tricky voters aim at making the community completely break into segments of voters who believe everyone has reach agreement on one candidate, but in fact, no. Lastly, the name of the candidates are extremely long, so they want to avoid speaking the name every time.

The solution is to allow a two rounds communication procedure. In the first round, each voter tell everyone one by one of their choice, and note down others choices. In the second round, they tell each others whether their notes have come to a conclusion: if not, they are perplexed and give up their choice or choose the default candidate (e.g. the candidate last year), if yes, they remain confident and content, and keep their choice as the final result. That’s it! They only speak of the long name once in the first round, and can finally reach agreement under the restrictions and harassment of vicious voters.

Thank you

Your comments and suggestions are most welcomed! I hope the series can continue to encourage people to start reading some cool and fundamental research before they jump right into piles of white-papers and can’t tell the quality. It could be a good start for us!