The artifact consists of two parts, the former containing the source code for probabilistic simulations and the latter a prototype implementation of the protocol.

Simulations for Asymptotically Optimal Message Dissemination with Applications to Blockchains

We here provide the necessary source code to reproduce the simulation results presented in the paper Asymptotically Optimal Message Dissemination with Applications to Blockchains.
The Python script sim.py can reproduce all the data underlying the probabilistic simulations shown in the paper.

Prerequisites

To run the simulation script, ensure you have Python 3.x installed with the following packages:

• NumPy
• tqdm

These can be installed via pip by running:

pip install numpy tqdm

Additionally, one must ensure that the script can write to the RESULT_PATH. By default, this folder is set to results, and it is created if it does not already exist.
By adjusting the variable NUMBER_OF_CORES the number of cores that the simulation script utilizes can be adjusted. By default, all available CPU cores are used.

Usage

The probabilistic simulations come with a very simple command line interface allowing to specify the number of repetitions for each data point and the figure for which data should be simulated.

To run the probabilistic simulations go to the folder where sim.py is located and execute the command:

python sim.py <number_of_repetitions> <figure_number>

where <number_of_repetitions> should be replaced with the desired number of repetitions for each data point and <figure_number> should be replaced with the desired figure number (an integer between 1 and 10) from the ePrint version of the paper (a map between figure numbers appearing in the ePrint version and the Eurocrypt version can be found here). We suggest to use 1000 repetitions for experimentation and 100000 repetitions to reproduce the results of the paper.

Note that the same experiments produce the underlying data for several figures. Therefore the following figure numbers (following the ePrint numbering) produce the same files and outputs:

• 1 and 10
• 2, 3, 4, and 5
• 6 and 7

Obtaining the Figures in the Eurocrypt Version of the Paper

Figures 1 and 2 from the Eurocrypt paper correspond to figures 1 and 10 in the ePrint version. As explained above, the corresponding simulations can be run by executing the command

python sim.py <number_of_repetitions> 1

or python sim.py <number_of_repetitions> 10, which produces the same results. How to obtain the corresponding figures from the outputs is explained in the sections below.

Figure 1 (Eurocrypt numbering)

The simulations produce 9 files in total where each file contains the columns Error rate and Pr. party communication in MB that correspond to the data points for a particular line in Figure 1.

The 3 files for the protocol FFlood are named:

./results/FF-n-4096-r-<number_of_repetitions>.csv 
./results/FF-n-8192-r-<number_of_repetitions>.csv 
./results/FF-n-16384-r-<number_of_repetitions>.csv

The 6 files for the protocol ECFlood(d) are named:

./results/FFFloodAmplifier-n-4096-d-8-mu-25-r-<number_of_repetitions>.csv 
./results/FFFloodAmplifier-n-8192-d-8-mu-25-r-<number_of_repetitions>.csv 
./results/FFFloodAmplifier-n-16384-d-8-mu-25-r-<number_of_repetitions>.csv
./results/FFFloodAmplifier-n-4096-d-20-mu-10-r-<number_of_repetitions>.csv 
./results/FFFloodAmplifier-n-8192-d-20-mu-10-r-<number_of_repetitions>.csv
./results/FFFloodAmplifier-n-16384-d-20-mu-10-r-<number_of_repetitions>.csv

Figure 2 (Eurocrypt numbering)

The output files are not needed to reproduce this figure. Instead, parameters output to the terminal need to be used to plot the per-party communication complexity as a function of the message length for the respective functions.

For FFlood the function to plot is:

FFlood_per_party_communication(msg_length) = degree * msg_length

For the respective number of parties, the script produces 3 outputs of the following form for FFlood

Best parameter that made FF-n-<number_of_parties> not fail is degree = <d>

From these outputs, the best degree ensuring that all simulations succeeded can be read and used in the above function to obtain the lines for FFlood in Figure 2 (Eurocrypt numbering).

For ECFlood the function that should be plotted is (Eq (11) in the Eurocrypt version replacing the total number of shares minus the number of tolerated erasures with the total number of shares times the fraction of shares needed for reconstruction):

ECFlood_per_party_communication(msg_length) = number_of_shares * degree * (ceil(msg_length / (reconstruction_fraction * number_of_shares)) + 257 * ceil(log2(number_of_shares)) + 256)

For the respective number of parties, the script produces 6 outputs of the following form for ECFlood

Best parameters that made FFFloodAmplifier-n-<number_of_parties>-d-<degree>-mu-<number_of_shares> not fail is reconstruction_fraction = <reconstruction_fraction>

From these outputs, the best reconstruction threshold ensuring that all simulations succeeded for the respective combinations of degree and number of shares, can be read and used in the above function to obtain the lines for ECFlood in Figure 2 (Eurocrypt numbering).

Mapping between ePrint and Eurocrypt figure numbers

Below is a mapping between the figure numbers.

Eurocrypt	ePrint
1	1
2	10

All other figures appearing in the ePrint version do not appear in the Eurocrypt version.

Prototype Implementation of the WeakFlood2Flood Protocol

We here provide a simple prototype implementation in C++ of the protocol WeakFlood2Flood from the paper Asymptotically Optimal Message Dissemination with Applications to Blockchains. The purpose of this prototype is to bound the computational overhead of the protocol. It has not been optimized and tested thoroughly and should not be used in production.

The prototype uses Reed-Solomon codes from the Schifra library
and implements a simple accumulator based on SHA256 Merkle trees using the merklecpp library.

Prerequisites

To compile the code on Linux, one needs to install:

• GCC with C++17 Support
• libssl-dev
• libtbb-dev

Configuration

The file wf2f.cpp defines three constants at the top that can be modified to test the performance of the protocol in different scenarios:

• NUM_SHARES defines into how many shares the sender splits the message. This corresponds to the parameter µ in the paper and is initially set to 10.
• MAX_DELETIONS defines the parameter of the error correcting code determining how many of the shares can get lost without preventing reconstruction. It corresponds to the parameter ϱ in the paper and is initially set to 2.
• MSG_LENGTH defines the number of bytes the sender wants to disseminate. It is initially set to 1024 * 1024, i.e., a 1 megabyte message is assumed.

Compiling

To compile the code, execute

g++ -std=c++17 -O3 wf2f.cpp -lcrypto -ltbb

Usage

The compiled code can be executed in the command line and does not take any arguments.

The program first generates a message consisting of MSG_LENGTH random bytes and executes the sender protocol of WeakFlood2Flood to obtain a vector of NUM_SHARES packets that are to be disseminated using a WeakFlood protocol.
Next, MAX_DELETIONS random packets are chosen and their accumulated values are set to the hash of the empty string, to simulate corrupted packets.
Finally, the receiver protocol of WeakFlood2Flood is executed on the obtained packets. The obtained message is then compared to the original one to determine whether it would have been received successfully.

The program outputs the times to execute the sender and receiver protocols, respectively, and whether the correct message was decoded. Note that the WeakFlood subprotocol is not implemented, i.e., no messages are actually send over a network. This program thus only measures the computational overhead of WeakFlood2Flood over an assumed WeakFlood protocol.