fpc-sim icon indicating copy to clipboard operation
fpc-sim copied to clipboard

verified publisher icon iotaledger
→

Metadata

Fast Probabilistic Consensus Simulator

A simulator for testing the IOTA FPC module

Discord StackExchange Apache 2.0 license Go version Go Report Card

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:

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.

  1. Clone the repository

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

  2. 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.

  3. If you're using Windows, add the .exe file extension to the sim file

  4. 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.

FPC simulator

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.

  1. Install the dependencies

    pip install dash numpy matplotlib

  2. 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.

Example graph

  1. 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.

  1. 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.

← Metadata

19
Stars
3
Forks
Watchers

Owner

verified publisher icon iotaledger

Metadata

Fast Probabilistic Consensus Simulator

Back