<jupyter_start><jupyter_text>Forking ExperimentsThis notebook contains some experimental results from running several network simulations that can help us to understand how some settings and parameters affect the network's throughput (more specifically on the chain forks evolution) under a Proof of Stake v3 proposing mechanism.But before showing the experimental results, we'll introduce some basic calculations to see what the theory tells us and have a better idea of which kind of questions we're trying to answer.  Simplest case: 0-delayGiven any arbitrary target spacing (average time between blocks), which in our case is 16s, and 0 delay, two variables control the probability of having forks:  - The numer of staked coins.  - The time granularity used to compute block hashes.**Some assumptions:**  - There's no delay, once a block is created, it arrives immediately to all the nodes in the network.    Although it's intuitive to expect that higher delays could lead to higher number of forks, we'll    assume for now that there's no delay to have a better intuition on how other factors could affect    the outcome.  - All coins have the same denomination and each proposer holds one single coin, this is a strong (and not realistic) assumption, but not very problematic.  - The difficulty adjustment mechanism is good enough to keep empirical probabilities close enough to the desired ones.  - Given that the delay is 0, and that we have a fork choice rule, the "weakest" forks are rapidly discarded and the nodes don't try to build chains on top of them.**Some definitions:**  - $C$ : number of staked coins  - $T$ : target spacing, or expected average time between blocks  - $m$ : in $T$ seconds a node will be able to try $m$ hashes.  - $P\left(C,m,k\right)$ : Probability that a coin gives us the ability to propose during a period of $k\frac{T}{m}$ seconds when there are $C$ staked coins, the target spacing is $T$ and a node can try to propose every $\frac{T}{m}$ seconds.  - $\mathsf{P}$ : $P\left(C,m,1\right)$.  - $F\left(C,m,k\right)$ : Probability of having at least one fork during a period of $k\frac{T}{m}$ seconds when there are $C$ staked coins, the target spacing is $T$ and a node can try to propose every $\frac{T}{m}$ seconds.  - $\mathsf{F}$ : $F\left(C,m,1\right)$.  - $\mathbb{F}$ : $F\left(C,m,m\right)$.   **Some calculations:**The probability of having at least one fork for a given instant is $1$ minus the probability of not having any block proposal, minus the probability of having exactly $1$ block proposal:$$\mathsf{F} = 1 - \mathsf{P}\left(1 - \mathsf{P}\right)^{C-1} - \left(1 - \mathsf{P}\right)^C = 1 - \left(1 - \mathsf{P}\right)^{C-1}$$The probability of having at least one fork during $T$ seconds is:$$\mathbb{F} = 1 - \left(1-\mathsf{F}\right)^m$$We want to find expressions that depend on $C$ and $m$, so let's start doing some substitions:$$\frac{1}{m} = 1 - \left(1-\mathsf{P}\right)^C \implies \mathsf{P} = 1-\left(1-\frac{1}{m}\right)^{\frac{1}{C}}$$and hence$$\mathsf{F} = 1 - \left(1-\mathsf{P}\right)^{C-1} = 1 - \left( 1 - \left( 1 - \left( 1 - \frac{1}{m}\right)^{\frac{1}{C}}\right)\right)^{C-1} = 1 - \left(1-\frac{1}{m}\right)^{\frac{C-1}{C}}$$therefore$$\mathbb{F} = 1 - \left(1-\mathsf{F}\right)^m = 1 - \left( 1 - \left( 1 - \left( 1 - \frac{1}{m}\right)^{\frac{C-1}{C}}\right)\right)^m = 1 - \left(1-\frac{1}{m}\right)^{m\frac{C-1}{C}}$$As we can see, when the number of coins ($C$) is big enough, the probability of having at least one fork every $T$ seconds is $1-\left(1-\frac{1}{m}\right)^m$, which is a decreasing function of $m$; and $\lim_{m\to\infty}1-\left(1-\frac{1}{m}\right)^m = 1-e^{-1}$.We can take a look on $\mathbb{F}$ seeing what happens when $m$ is very large. The probability of having forks every $T$ seconds is $1-e^{-1+\frac{1}{C}}$, which makes sense: the more proposers, the higher the probability of having forks (and having just one proposer gives us a probability equal to $0$).From this we know that, having negligible delay, it's worth to have a large $m$ parameter, but we still face a fundamental limit that we can't cross, some amount of forking is inevitable. This tells us that, having a target spacing of 16s we'll see a fork approximately every 25.31s in average.  More convoluted casesTODO  Now, let's code<jupyter_code># Because we use part of Unit-e's functional tests framework, we have to set some global properties
import test_framework.util as tf_util

tf_util.MAX_NODES = 500  # has to be greater than 2n+2 where n = num_nodes
tf_util.PortSeed.n = 314159  # We want reproducible pseudo-random numbers

import sys
from logging import (
    INFO,
    WARNING,
    basicConfig as loggingBasicConfig,
    getLogger
)

loggingBasicConfig(
        stream=sys.stdout,
        level=INFO,
        format='%(asctime)s - %(levelname)s - %(name)s - %(message)s'
    )
getLogger('asyncio').setLevel(WARNING)
# We do this to make easier mixing sync & async code inside Jupyter notebooks
import nest_asyncio
nest_asyncio.apply()
# Imports required to run our experiments
import pandas as pd

from asyncio import get_event_loop
from itertools import product as cartesian_product 
from pathlib import Path

from experiments.forking_simulation import ForkingSimulation
# Some constants for our experiments
simulation_time = 1200  # 20min
sample_time = 1         # 1s
graph_model = 'preferential_attachment'  # https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model

# We'll have to store the results of our simulations somewhere
current_path = Path('.').resolve()
results_path = current_path.joinpath('..').joinpath('results').resolve()
# We'll combine these values to generate many different settings for our simulations
num_proposer_nodes_values = [45]         # How many nodes will be able to propose blocks
num_validator_nodes_values = [5]         # How many nodes will be validating the blockchain
num_relay_nodes_values = [0]             # How many nodes will be just relaying blocks
target_spacings = [4, 8, 12, 16]         # Expected averate time between blocks
time_steps = [1, 2, 4, 6, 8]             # Time granularity used to generate block hashes
latencies = [0, 0.1, 0.5, 1.0]           # Block propagation delays

settings_tuples = list(cartesian_product(
    num_proposer_nodes_values,
    num_validator_nodes_values,
    num_relay_nodes_values,
    target_spacings,
    time_steps,
    latencies
))

settings_tuples = sorted([
    (
        num_proposer_nodes_values,
        num_validator_nodes_values,
        num_relay_nodes_values,
        target_spacings,
        time_steps,
        latencies
    )
    for (
        num_proposer_nodes_values,
        num_validator_nodes_values,
        num_relay_nodes_values,
        target_spacings,
        time_steps,
        latencies
    ) in settings_tuples
    
    if (
        time_steps < target_spacings and
        target_spacings % time_steps == 0
    )
])
# Let's show a summary to know how much we'll have to wait
num_settings = len(settings_tuples)
expected_time = num_settings * (30 + simulation_time)
print(f'\n\nData will be generated for {num_settings} settings tuples.')
print(f'Generating data will require {expected_time} seconds, or {expected_time/3600} hours.\n')
# In this cell we'll generate data in order to analyze it later

from ipywidgets import IntProgress, HTML, VBox
from IPython.display import display

# We'll show a progress bar to haver a better sense of progress
progress_bar = IntProgress(min=0, max=num_settings)
label = HTML()
label.value = f'0 / {num_settings}'
box = VBox(children=[label, progress_bar])
display(box)

logger = getLogger('notebook')

# We generate a dataset per settings tuple
for c, settings in enumerate(settings_tuples):
    num_proposer_nodes, num_validator_nodes, num_relay_nodes, target_spacing, time_step, latency = settings

    # Each simulation stores results in a different path
    result_directory = results_path.joinpath(
        '_'.join(str(v) for v in settings)
    ).resolve()

    # Previous data will be overwritten
    if result_directory.exists():
        for f in result_directory.glob("*.csv"):
            f.unlink()
        result_directory.rmdir()
    result_directory.mkdir(exist_ok=True)

    network_stats_filename = str(result_directory.joinpath('network.csv').resolve())
    nodes_stats_directory = result_directory

    logger.info(f'Stats dir: {nodes_stats_directory}')

    simulation = ForkingSimulation(
        loop=get_event_loop(),
        latency=latency,
        num_proposer_nodes=num_proposer_nodes,
        num_validator_nodes=num_validator_nodes,
        num_relay_nodes=num_relay_nodes,
        simulation_time=simulation_time,
        sample_time=sample_time,
        graph_model=graph_model,
        block_time_seconds=target_spacing,
        block_stake_timestamp_interval_seconds=time_step,
        network_stats_file_name=network_stats_filename,
        nodes_stats_directory=nodes_stats_directory
    )
    simulation.setup_directories()
    simulation.setup_chain()
    simulation.setup_nodes()
    logger.info(f'Lucky proposer: {simulation.proposer_node_ids[0]}')
    simulation.safe_run(close_loop=False)

    # Updating the progress bar
    progress_bar.value += 1
    label.value = f'{progress_bar.value} / {num_settings}'
    print()
# Now we want to load all the generated data into memory to draw some conclusions

# We'll merge all the stats collected by different nodes (and different settings) into one single dataframe
nodes_df = None
network_df = None

logger = getLogger('notebook')

network_dataframes = []
nodes_dataframes = []

for settings in settings_tuples:
    logger.info(f'Loading data for {settings}')
    
    num_proposer_nodes, num_validator_nodes, num_relay_nodes, target_spacing, time_step, latency = settings

    result_directory = results_path.joinpath(
        '_'.join(str(v) for v in settings)
    ).resolve()
    network_stats_filename = str(result_directory.joinpath('network.csv').resolve())

    # timestamps are measured in milliseconds
    network_csv = pd.read_csv(
        network_stats_filename,
        header=None,
        names=['timestamp', 'src_id', 'dst_id', 'command', 'command_size']
    )
    network_csv['num_proposer_nodes'] = num_proposer_nodes
    network_csv['num_validator_nodes'] = num_validator_nodes
    network_csv['num_relay_nodes'] = num_relay_nodes
    network_csv['target_spacing'] = target_spacing
    network_csv['time_step'] = time_step
    network_csv['latency'] = latency
    
    network_dataframes.append(network_csv)
    if network_df is None:
        network_df = network_csv
    else:
        network_df = pd.concat([network_df, network_csv])

    num_nodes = num_proposer_nodes + num_validator_nodes + num_relay_nodes
        
    for node_id in range(num_nodes):
        node_stats_filename = str(result_directory.joinpath(f'stats_{node_id}.csv').resolve())
        
        node_csv = pd.read_csv(
            node_stats_filename,
            header=None,
            names=[
                'timestamp', 'height', 
                'last_justified_epoch', 'last_finalized_epoch', 'current_epoch', 'current_dinasty'
                'mempool_num_transactions', 'mempool_used_memory',
                'peers_num_inbound', 'peers_num_outbound',
                'tip_stats_active', 'tip_stats_valid_fork', 'tip_stats_valid_header',
                'tip_stats_headers_only', 'tip_stats_invalid'
            ]
        )
        
        # We add some columns to identify the source node & the specific simulation
        node_csv['node_id'] = node_id
        node_csv['num_proposer_nodes'] = num_proposer_nodes
        node_csv['num_validator_nodes'] = num_validator_nodes
        node_csv['num_relay_nodes'] = num_relay_nodes
        node_csv['target_spacing'] = target_spacing
        node_csv['time_step'] = time_step
        node_csv['latency'] = latency
        
        node_csv = node_csv.reindex(columns=[
            'timestamp',
            'node_id', 'num_proposer_nodes', 'num_validator_nodes', 'num_relay_nodes', 'target_spacing',
            'time_step', 'latency', 'height', 'mempool_num_transactions', 'mempool_used_memory',
            'peers_num_inbound', 'peers_num_outbound', 'tip_stats_active', 'tip_stats_valid_fork',
            'tip_stats_valid_header', 'tip_stats_headers_only', 'tip_stats_invalid'
        ])
        
        nodes_dataframes.append(node_csv)

logger.info('Creating final dataframes')
network_df = pd.concat(network_dataframes)
nodes_df = pd.concat(nodes_dataframes)
nodes_df = nodes_df.sort_values(by=['timestamp', 'node_id'])
del nodes_dataframes
del network_dataframes
logger.info('Finished :)')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10105296243910106, 'fraction_numerical': 0.010136727958510137, 'mean_word_length': 3.7917921686746987, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 5, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '186725', 'license': 'MIT', 'n_tokens_mistral': 3941, 'n_tokens_neox': 3796, 'n_words': 1190, 'path': 'experiments/notebooks/real_nodes_forking_01.ipynb', 'repo_name': 'dtr-org/unit-e-experiments', 'size': '12726'}