Dynamic graph models inspired by the Bitcoin network-formation process

Abstract

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.