One of the most difficult dilemmas in blockchains, or any distributed computing system, can be summed up by referring to an allegory of Byzantine generals. This was popularized by an American computer scientist named Leslie Lamport, who is famously known for receiving a Turing Award for improving the quality of distributed systems.

The allegory was used as an analogy to address the conditions regarding consensus problem in computer systems. In short, the story goes like this– Every Byzantine general, who are dispersed throughout randomly displaced camps, must unanimously agree on a decision to attack or retreat the night before the battle. Since the camps are displaced few and far between, the message is sent back and forth by a courier.

Now, there are a number of negative outcomes to this scenario as a result of communication. Since the camps are dispersed geographically, it can be quite difficult to form a consensus in a timely manner. Moreover, forged messages can be sent by an ill willed general to conflate the other generals, leading to a total failure. Similar to this allegory, blockchain poses a similar problem, where majority of participants in the distributed network must all agree on the same decision to execute a task to prevent different outcomes.

According to Leslie Lambert’s paper on Byzantine general problem, the number of participants requires more than three times the number of traitors in order to continue operation on the distributed network. Since the publication of this seminal paper, series of algorithms were made to tackle the consensus problem. Among them, Paxos protocol is among the most well-known consensus protocol, which helped make significant progress in maintaining the complex behavior of decentralized network as well as laying the groundwork for various cryptocurrencies.

By studying the various protocols (also known as practical BFT), we can further gain insights in improving the existing algorithms in the blockchain space. To put it tritely, it can be divided into two broad categories: one is by dividing N nodes of participants into arbitrary groups and second method is improving unanimous voting method.

Social choice theory, also called strategic voting theory, is a concept under game theory which studies the behavior of collective decisions people make when participating in a plurality-rule election. Most scholars in this field of research are mathematicians and economists, which borrows many elements in welfare economics and voting theory. The most famous theorem in welfare economics is arrow impossibility theorem, which states:

“it is impossible to have one social welfare function that satisfies a certain set of “apparently reasonable” conditions”

This impossibility theorem has been researched independently by the two mathematicians, Gibbard and Satterswaite, which later set a precedent in social choice theory. The Gibbard — Satterswaite theorem is as follows.

“If there are at least three possible outcomes, then every strategy-proof (or non-manipulable) voting procedure is dictatorial.”

In voting theory, the word dictatorial refers to a player with a veto power. When this is applied to the golden share it allows to outvote all the others in specific situations. It is an important research field of social choice theory.

The problem with the Gibbard-Satterswaite theorem is that it is difficult to apply it to the consensus process because the voting result is based on ordinality of the outcome, therefor can only be applied in deterministic settings. However, Hylland, a Norwegian mathematician, reinterpreted the problem in the form of a Random Dictatorship. A stochastic dictator is selected via randomized selection of voters equipped with a veto power, where the voting results can be expressed in cardinal numbers. Hylland’s theorem is as follows:

“In a civilized society, a voting procedure in which a dictator is randomly selected (veto) cannot be manipulable.”

Applying the results of Hylland’s theorem to BFT, we can derive a following theorem (SymSensus Theorem).

“Participants of voters cannot not reap any benefits by manipulating the consensus process when the primary node (“stochastic dictator”) creates a block in the BFT consensus, where there is veto power”

When this theorem is applied to the SymVerse consensus, it only takes half the time to achieve consensus compared to the existing pBTF algorithms. The method is to randomly allot a ‘veto’ group in the consensus algorithm. The following procedure is shown below:

Participants in the consensus process are divided into two groups: A and B. A group comprises of (n/3)+1 nodes. Group A has only the right to vote, which all show a unanimous result. The primary nodes, which are randomly selected from the rest of the nodes from group B, are given the right to create blocks. Members of both group A and group B participate in the decision-making process to approve or reject the a newly proposed block.

Where existing pBFT protocols require a consensus quorum of (2n/3)+1 of votes, participants of group B only require a quorum of n/3 of nodes to reach the consensus. Moreover, Symverse consensus can greatly increase its speed, since group A has a shorter consensus time than group B’s and only requires the majority of votes to advance the chain.

Hylland extends this result to non-deterministic cases. SymVerse applies cornerstone theorems from game theory and social choice to create a consensus algorithm in which the randomly selected block producer has no possibility to profit through manipulation.

[References]

● Lambert, L., “Generalized Consensus and Paxos” Microsoft Research Technical Report MSR-TR-2005–33 , 15 March 2005.

● Lambert, L., “Fast Paxos”, Distributed Computing 19, 2 , October 2006. pp.79–103.

● Lambert, L, Danny Dolev, Marshall Pease, and Robert Shostak “The Byzantine Generals” in Concurrency Control and Reliability in Distributed Systems, Bharat K. Bhargava, editor, Van Nostrand Reinhold (1987) pp. 348–369.

 Moulin, H. The Strategy of Social Choice. Series: Advanced textbooks in economics, 18. North-Holland: Amsterdam, The Netherlands. 1983.

● Peleg, B. Game Theoretic Analysis of Voting in Committees, Cambridge University Press, Cambridge, 1984.

● Hylland, A. “Strategy proofness of voting procedures with lotteries as outcomes and infinite sets of strategies,” mimeo. 1980.

● Sen, A. “The Gibbard random dictatorship theorem: a generalization and a new proof,” SERIEs 2, 515–527, 2011.


SymVerse Community Official links

Official Site: https://www.symverse.com/ 
Telegram (ENG): https://t.me/SymVerse 
KakaoTalk (KOR): https://open.kakao.com/o/ggsgzhab (password:0110) Medium: https://medium.com/symverse 
Steemit (KOR): https://steemit.com/@symverse 
Facebook (KOR): https://www.facebook.com/symverse 
Twitter: https://www.twitter.com/symverse 
Youtube: https://www.youtube.com/channel/UCB8hrWAeXmHIdN5u3zv-brA