Dynamic graph models inspired by the Bitcoin network-formation process

The network formation process in the Bitcoin protocol is designed to hide the global network structure: while most of the nodes of the network can be easily discovered, the existence of an edge between two nodes is only known by the two endpoints. In [Becchetti et al., SODA2020] the authors propose a dynamic random graph model inspired by the network formation process in the Bitcoin protocol and they prove that the evolution of the graph quickly terminates and that the resulting graph is an expander, with high probability. In this paper we extend the model in [Becchetti et al., SODA2020] to obtain dynamic random graph models that evolve forever: in the first model, edges can be faulty, i.e., each edge at each round disappears with some probability; in the second one, at every round newnodes join the network according to a Poisson process and each node currently in the network disappears with certain probability; in the third one, we consider a combination of the two models above, in which edges can be faulty and nodes can join and leave the network. We run extensive simulations to measure the "flooding time" in the three models, i.e., howlong it takes a message starting at a random node to reach all, or almost all, the nodes. The simulations show that, for large ranges of the parameters of the models, the flooding time is short, i.e., compatible with a logarithmic growth, as a function of the number of nodes in the network. Our results also suggest that the default values of the network formation parameters used in the main implementation of the Bitcoin protocol seem overwhelmingly safe with respect to the stability of the network, and they might safely be tuned to reduce network traffic.