fpc-sim: A Go repository from IOTA

A simulator for testing the IOTA FPC module

About ◈ Design ◈ Getting started ◈ Supporting the project ◈ Joining the discussion

About

This repository is where the IOTA Foundation's Research Team simulates tests on the Fast Probabilistic Consensus (FPC) protocol to study attack strategies on different kinds of network topologies.

By making this repository open source, the goal is to allow you to run your own simulations and get involved with development.

To find out more details about FPC, see the following:

The Fast Probabilistic Consensus simulator by Dr. Andreas Penzkofer
Consensus in the IOTA Tangle - FPC by Dr. Sebastian Mueller
FPC-BI: Fast Probabilistic Consensus within Byzantine Infrastructures by Dr. Serguei Popov and Dr. William J. Buchanan
Simulations of the FPC by Dr. Sebastian Mueller

Design

Fast Probabilistic Consensus (FPC) is one of the proposed consensus algorithms in Coordicide (the removal of the IOTA Coordinator).

In FPC, nodes vote on whether they like or dislike a transaction. This vote is represented by a 1 or 0. When all honest nodes reach the same voting opinion, consensus is reached.

In the simulation, nodes can be either honest or adverse. Honest nodes query the opinion of a random set of other nodes (defined in a k parameter) and set their own opinion to the majority opinion.

To simulate an attack on the protocol, you can set a strategy for the adversary nodes in the Adv_Strategy parameter.

Nodes vote in rounds. You can define the average opinion of the honest nodes (defined in the p0 parameter) for the initial round. For example, if p0=0.9, the honest nodes will have a 90% majority of 1 opinions when the simulation starts. As a result consensus should be reached on the value 1. If p0=0.2, the honest nodes will have an 80% majority of 0. As a result, consensus should be reached on the value 0.

For a given round each node calculates the average opinion of k randomly queried nodes and this value is denoted as eta. If eta is larger than the threshold, the opinion of that node is set 1, or 0 otherwise. The threshold is between [a,b] in the first round, and between [beta,1-beta] in the following rounds. For a given node the protocol terminates if the node has the same opinion for l (but at least l+m) consecutive rounds. Unless the round is the last one (defined in maxTermRound), in which case the simulation stops with a termination failure.

Prerequisites

To complete this guide, you need to have at least version 1.13 of Go installed on your device.

To check if you have Go installed, run the following command:

go version

Getting started

To get started, follow these steps to build and run the simulator.

Clone the repository

git clone https://github.com/iotaledger/fpc-sim.git

Build the executable file
```
cd fpc-sim
go build -o sim
```
You can also use the build tool to cross-compile the binary files for other architectures.
If you're using Windows, add the .exe file extension to the sim file
Run the simulation
```
./sim
```

A progress bar displays the simulation's progress across the entire parameter space. When the progress bar reaches 100%, the simulator has finished for all parameter settings.

Examining the data

To analyse the results of the simulation, read the .csv files in the data directory:

AgreementRate: Rate at which all honest nodes conclude with the same opinion
IntegrityRate: Rate at which all honest nodes conclude with the same opinion and the final opinion is the same as the original majority
TerminationRate: Rate at which all honest nodes conclude before maxTermRound
MeanTerminationRound: Average round when FPC terminated
MedianTerminationRound: Median round when FPC terminated
TerminationRound: How many rounds are necessary to complete FPC (Histogram)
MeanLastRound: Mean last round across all nodes
LastRoundHisto: Histogram of nodes' individual termination rounds
OnesProportion: The proportion of 1s after the protocol terminates
OnesPropEvolution: Evolution of the 1s proportion
EtaEvolution: Histogram of honest eta's for each round

Now that you have data, you can run one of the Python scripts to visualize the data in a graph.

Visualizing the data

To generate graphs of the data, run the provided Python script.

You must have Python and PIP installed to run this script. The script generates graphs in .eps files, so to view the graphs, you also need an application that can open these files.

Install the dependencies
```
pip install dash numpy matplotlib
```
For a single-vector-parameter input, edit the output setting in the plot.py file to read the correct csv column
```
python plot.py
```

The script provides two figures:

The termination, agreement, and integrity rate
The mean last round for all nodes, as well as the mean round at which the protocol terminated

Note: The total message complexity in the network can be approximated by the mean last round times the quorum size k times the number of nodes.

For 2-vector-parameter inputs, edit the output setting in the file to read your chosen csv columns
```
python plot2D.py
```

The script provides plots with the termination, agreement, and integrity rate as a heat map of the input vectors.

For a single-parameter input (no vector), enable the enableSaveEta parameter in the input.txt file and run:
```
python plot_eps.py
```

In every round the number of non-finalized honest nodes are counted that have taken on a given eta value and the result is stored in a slice of histograms (EtaEvolution). This data is used to output a heatmap of the eta's evolution with time.

Parameters

These parameters affect how the simulated network behaves. As a result, changing these paramters has an affect on how long the network takes to reach a consensus.

A description and functionality of some of the parameters is provided in the blog that accompanies the release of this code.

To change any of these parameters, edit them in the input.txt file.

Parameter	Type	Description
`nRun`	int	Number of runs for each simulation. Each run is a new voting object and it can be, for example, understood as a new transaction.
`N`	int	Number of nodes
`a`	float64	Lower threshold limit in the first round
`deltaab`	float64	Difference between a and and upper first threshold limit b [0.5 < a ≤ b < 1], [deltaab < 1-a ]
`beta`	float64	Threshold limits in the subsequent rounds [0 ≤ beta ≤ 0.5]
`p0`	float64	Proportion of nodes that have initial opinion 1, or 0 otherwise [0 ≤ p0 ≤ 1]
`q`	float64	Proportion of adversaries [0 ≤ q < 1]
`k`	int	Amount of nodes each node queries
`enableQueryk0`	bool	Allow nodes to finalize in first round
`k0`	int	Amount of nodes each node queries in the first round if nodes get finalized then
`m`	int	The cooling-off period
`l`	int	The required consecutive rounds for a node to finalize its opinion
`maxTermRound`	int	Maximum number of rounds before terminating the protocol
`Adv_Strategy`	int	The adversary strategy: the available strategies are shown at the bottom of the readme
`enableWS`	bool	Enable Watts-Strogatz graph
`deltaWS`	float64	Watts-Strogatz parameter - Proportion of network that can be queried [0 ≤ deltaWS < 1]
`gammaWS`	float64	Watts-Strogatz paramter - Rewiring probability [0 ≤ gammaWS < 1]
`rateRandomness`	float64	Average rate at which a random number is created (see this blog post for more details)
`etaAgreement`	float64	Proportion of nodes ignored for agreement failure
`enableSaveEta`	bool	Save etas; this does not work if a vector input is provided
`enableExtremeBeta`	bool	Experimental: beta switches between min and max threshold
`enableRandN_adv`	bool	Turn nodes adversarial with probability q, otherwise assign by index
`enableZipf`	bool	add Mana distribution to honest nodes, adversary distributes mana equally between nodes
`sZipf`	float64	Zipf distribution parameter

Adversary's strategies

The simulator supports the following strategies:

Strategy 1: cautious, always send the opposite of the initial majority, determined by p0
Strategy 2: cautious, send the minority of the honest nodes of the previous round
Strategy 3: berserk, adversary tries to delay the process by splitting the opinions
Strategy 4: berserk, adversary tries to delay the process in maximizing the uncertainty
Strategy 5: berserk, try to keep the median of the eta's close to 1/2

Supporting the project

If you want to contribute to the code, consider posting a bug report, feature request or a pull request.

See the contributing guidelines for more information.

Joining the discussion

If you want to get involved in the community, need help getting started, have any issues related to the repository or just want to discuss blockchain, distributed ledgers, and IoT with other people, feel free to join our Discord.