Simulation Study of FPC
The IOTA Research Department Recently Published the Fast Probabilistic Consensus Simulator.
Today, we are excited to share with you the corresponding research paper on arxiv that studies various properties of the FPC. We invite you to take a look at this research paper. We also want to give you a short overview of what kind of results we have obtained.
The abstract tells us:
This paper investigates leaderless binary majority consensus protocols with low computational complexity in noisy Byzantine infrastructures. Using computer simulations, we show that explicit randomization of the consensus protocol can significantly increase the robustness towards faulty and malicious nodes.We identify the optimal amount of randomness for various Byzantine attack strategies on different kinds of network topologies.
Let’s see what all these terms mean. In the current version of IOTA, tangle consensus is achieved by the Coordinator. One core module of Coordicideis FPC, a distributed consensus protocol. Distributed consensus protocols allow networked systems to agree on a common opinion in situations in which centralized decision-making is difficult, impossible, or unwanted.
As distributed computing is inherently unreliable, it is necessary to reach consensus in noisy or Byzantine infrastructures. The latter is equivalent to the presence of malicious nodes that try to attack the protocol. The word noisy refers to nodes that may be faulty or to possible message loss.
The FPC is leaderless since it does not require an (elected) leader. An advantage of this is that every node can update its opinion locally without having to wait for the coordination of the leader. In FPC every node queries a random sample of other nodes and adopts the opinion of the majority. In the basic version, there are only two possible opinions so we speak of binary majority consensus.
Previous protocols in the class of leaderless binary majority consensus protocols are the simple majority consensus and the random majority consensus.
These protocols, however, can rarely guarantee the eventual agreement of the nodes in Byzantine infrastructure. For this reason, FPC proposes additional randomness that serves as “fog of war” for potential malicious attackers, making it at best impossible for the attacker to effectively influence the honest nodes.
The additional randomness is the key element that allows overcoming Byzantine failure. The randomness is parameterized by a parameter β; the larger β the less random the protocol. One main interest was to identify the β’s that allow the maximal proportion of adversary nodes. In the following graph, we plot the agreement rate as a function of β and the proportion of adversary nodes.
An agreement rate of 1 means that in 100% of the simulations all honest nodes eventually shared the same opinion. An agreement rate of 0.9 signifies that in 90% of the simulations all honest nodes had the same opinion and that in 10% of the cases at least two honest nodes terminated the protocol with different opinions. We see that, in the above situation, the protocol with β=0.3 allows the highest proportion of adversary nodes.
Our focus lies in the performances of the FPC in Byzantine infrastructures. For this purpose, we propose explicit adversarial strategies, which either target the integrity of the resulting opinion, the agreement of the nodes on the opinion, or the termination of the protocol altogether. Some of these strategies are also described in Consensus in the iota tangle — FPC. The performances are measured using the integrity rate, agreement rate, and termination rate.
Moreover, we investigated the dynamics of the protocol during an attack. The next graph shows the evolution of undecided nodes under several attack scenarios. We see in a) that the FPC is robust against certain malicious attackers even without the additional randomness (β=0.5). To overcome Berserk attackers, however, the additional randomness is crucial, as the comparison of b) and c) shows.
In the FPC paper, it is assumed that every node has a complete view of the network. We weaken this assumption by considering several network topologies and analyzing how the lack of complete knowledge about all other nodes affects the ability to reach consensus. You may also take a look at the previous post Fast Probabilistic Consensus Simulator for more details.
One of our main results is, therefore, well summarized in the last sentence of the abstract:
We identify the optimal amount of randomness for various Byzantine attack strategies on different kinds of network topologies.
As always, we welcome your comments and questions either here in the comments, in #tanglemath on our Discord server, or in the IOTA.cafe. You can also engage in more intense scientific collaborations with us and apply for a grant.
The author is not a member of the IOTA Foundation. He wrote this blog post in collaboration with the members of the IOTA research group.
Follow the IOTA Foundation on our official channels for the latest updates
Discord | Twitter | LinkedIn | Instagram | YouTube