With the question of the Byzantine default, we touch one of the main problems that face decentralized networks relying on a blockchain.
When computers are organized in networks, there are mainly two types of defaults: the default of a computer for purely material reasons (” fail Crash “) or the fact that a computer communicates incorrect information to the other computers of the network, in a deliberate way or not.
This last case is known as the ” Byzantine failure “. The question that arises is to know up to which number of ill-intentioned members, it is possible to have trust in a consensus mechanism and thus in the good health of a decentralized network.
In a decentralized network, the purpose of a consensus mechanism is to ensure that all members agree on the order of the addition of the transactions to the shared database, i.e the blockchain.
It is possible to reach an honest consensus in spite of the existence of malicious members whose objective is to harm the network by preventing it from reaching this consensus. When a certain number of members cannot be trusted, a consensus cannot be securely reached and the order of transactions added to the database is not certain anymore. If this happens this is the end of the network because no transactions cannot be exchanged between the members anymore.
Many of the solutions that have been devised over the last twenty years to solve this issue also know as the « Byzantine default problem », are widely used nowadays to develop consensus protocols that meet the expectations of blockchain applications.
1 – The problem of the Byzantine generals:
The example of the “Byzantine Generals” is has been used to illustrate the “Byzantine default” and to better understand the difficulties faced by a decentralized network to reach consensus.
The problem of Byzantine generals was first imagined by Leslie Lamport, Robert Shostak, and Marshall Pease in their 1982 essay, and is intended to illustrate the communication and understanding problems (voluntary or not) that may arise between different members or nodes of the same network.
You must imagine a group of generals directing the Byzantine army encircling an enemy city and whose objective is to carry out a coordinated attack. To do this, the leading general decides the time of the beginning of the assault and orders his messenger to carry the information to other generals. Each general must pass on the information he receives to the other generals so that they all have the same information and launch the attack at the same time. If they do not attack at the same time, they are sure to lose the battle.
The problem arises when one or more generals are malicious and decide to transmit information that is not correct such as advancing the attack by one hour. The consequence is that some of the generals will attack at a certain time and the other party an hour later.
Transposed into computer science, each general represents a computer of the network and the time of attack, the order of the transactions on the ), it is necessary to set up algorithms that will reach a common answer despite the malicious members, that is to say if we take our example, to agree on a single moment to attack the city.
2 – The proposed solutions
The algorithms of the Byzantine Generals better known as “Byzantine Fault Tolerance Algorithms” (“BFT”) are highly sought after because they guarantee to maintain security properties on a network as long as a certain number of “f” nodes are not failing.
This approach of the consensus system implies that the identity of each member is known, which requires the existence of a centralized entity in charge of the management of this data. From this point of view, the protocols based on a BFT algorithm are more adapted to “private” blockchain models or requiring permission (“permission blockchains”) and offer a much greater resistance to attacks.
This type of protocol has the advantage of the finality of its consensus which means that a block added to the blockchain cannot be questioned (by a separate fork). This is not the case with the mechanism of the Proof of Work where two blocks can be added at the same time to the blockchain creating two competing chains.
With BFT it is not possible to create a “fork” on the blockchain, which permit to align execution and confirmation of transactions and thus accelerate considerably their realization.
3 – Practical Byzantine fault tolerance: the example of Hyperledger
The protocol of “Practical Byzantine Fault Tolerance” (“PBFT”) was presented for the first time in an essay by Miguel Castro and Barbara Liskov published in 1999. This protocol has the huge advantage of being able to perform tens of thousands of transactions per second, which is, of course, a must to be applicable to large networks.
The algorithm maintains security properties as long as less than one-third of the nodes or replicas are corrupted.
The basic communication pattern under the PBFT protocol is realized in several steps:
- REQUEST: The client sends a message including its service request to the main server.
- PRE-PREPARE: The primary server assigns a number to this request and sends a PRE-PREPARE message to the other servers (members).
- PREPARE: Each server sends each of the other servers a message of “PREPARE”.
- COMMIT: Each server sends each of the other servers a message of “COMMIT”.
- REPLY: Once a sufficient number of servers agree on the order of the request, each server sends its response to the client.
If the client does not receive a response after a certain period of time, it retransmits a request to all the replicas that transmit it to the main server. If it does not implement this request in a given period, the replicas will consider that the main server is missing and will start a “change of view” to all servers. When enough replicas have started a “change of view”, they are able to receive the next request using a different primary server.
The performance of the PBFT has been significantly improved through the use of “message authentication code” (MAC) that allows authentication of different servers rather than using digital signatures.
This system is therefore both fast and efficient but also decoupled from any form of participation in the network (unlike Proof-of Stake), which allows small members to participate in the regulation of the network.
A major problem, however, is that PBFT-based systems require all parts of the network to agree on an exact list of participants. Indeed, leaving the open network would put him at risk of a so-called « Sybil attack », during which an attacker can create a significant number of nodes in order to dominate the system since decisions are made if the vote reaches a threshold (or certain quorum).
The Practical Byzantine Fault Tolerance is therefore particularly suitable for closed blockchain networks requiring identification and validation of each member.
4 – The Hyperldger Consensus:
1 – The customer creates a transaction and sends it to a peer in charge of the submission (“submitting peer”) of his request. The “submitting peer” can here be compared to the main server that we have described above.
2 – The “submitting peer” prepares a transaction and sends it to the peers in charge of approving new transactions or activating existing transactions (“endorsing peer”). These “endorsing peer” can be compared to “replicas” also mentioned above.
3 and 4 – The “submitting peer” then collects the approval and submits the transaction to the service of consensus (“consensus service”).
5 – The “consensus service” then distributes the transaction to the members of the network who will verify that it contains no error.
5 – The Ripple Ledger Consensus Process: Probability Based Voting
In a very basic way, Ripple can be considered as creating a network of people or entities that claim credit authorizations from each other.
A server (called the “s”), which is an entity that has access to the Ripple Server Protocol and therefore participates in the implementation of the consensus (unlike the Ripple Client Software that can only make transactions), has a “Unique Node List” or “UNL” (literally a “single node list”). Only the vote of Servers contained on this list of participants is taken into account to reach the consensus. It is therefore a subset of the members of the network which, when taken collectively, is considered by “s” to be trustworthy. Note that the server “s” is not obliged to trust a server individually.
Concretely, the Ripple Protocol consensus consensus algorithm (“RPCP”), takes place every second in several steps:
- Each server gathers all the valid transactions it received before the beginning of the consensus process in a batch called “candidate group” (“set candidates”) that it then makes public.
- Each server then groups all the candidate groups of all the list servers on its “Uniq Node List” and votes on the accuracy of each of these transactions.
- Transactions that receive a minimum percentage of vote are selected for the next vote, if there is one. Transactions that do not meet the required percentage are rejected and add to the next “group of candidates”.
- The last vote requires that each transaction has a minimum of 80% of the vote of all the servers of the UNL, otherwise the transaction can not be added to the register (“Ledger”). This means that as long as 80% of the servers on the UNL are honest, no fraudulent transaction can be approved.
6 – Stellar Consensus Protocol (“SCP”): the Federated Byzantine Agreement
SCP is developed to deal with the problem of “Byzantine Default”, leading to consensus without having to obtain the consent of all members of the network. This is an important difference with other Byzantine fault resistant systems that require the consent of network nodes to achieve this.
More precisely, SCP proceeds in 4 phases in the same way as protocols like Paxos. The nodes of the network exchange a series of polls to confirm and finally accept a value. For that, it determines a minimum quorum, ie a minimum number of members of the network having to vote to obtain an agreement. Each node chooses one or more parts of quorum (“quorum slice”) and included in each part of the nodes in which it has confidence. Each of these quorum shares will then intersect each other.
To reach an agreement, the SCP protocol relies on a property called “the intersection of quorums”.
The idea behind this concept is that each node that is honest has a network topology strong enough to reach a consensus. For this, we assume that if we remove the nodes that are malicious and the nodes that depend on it and that the intersection of the quorum is maintained, then the topology of the network is strong.
