Consensus formation on heterogeneous networks

Edoardo Fadda, Junda He, Claudio J. Tessone, Paolo Barucca

TL;DR

This paper reveals that the physical structure of a peer-to-peer network is a silent kingmaker in blockchain consensus. By modeling mining and block propagation across different network types, the authors demonstrate that "central" nodes—those with the shortest average distance to everyone else—possess a massive competitive advantage, often winning the race to validate a block even if they start significantly later than their peers.

What Problem Does This Paper Address?

In the world of Proof-of-Work (PoW) blockchains like Bitcoin, consensus is often treated as a pure race of computational "hash power." However, once a miner finds a solution, they must broadcast it to the rest of the network. If two miners find a solution at nearly the same time, a "fork" occurs, and the network must eventually choose one version of history over the other.

Most theoretical models of this process assume that information travels instantly or that the network is "well-mixed" (meaning every node is more or less equally connected). This paper tackles the reality: real-world networks are heterogeneous. Some nodes are hubs, while others are on the periphery. The authors ask: How much does your physical position in the network graph help you win the consensus race, and can a "well-placed" node beat a "faster" node?

Methods

The researchers built a minimalistic, discrete-time network model to simulate the interplay between mining (finding a block) and propagation (spreading it).

  • Mining: Modeled using an exponential distribution of "mining times," which is the standard mathematical approach for PoW.
  • Propagation: Information travels along the shortest paths of the network graph.
  • Network Topologies: They tested three distinct types of networks to see how structure influences outcomes:
  • Erdős-Rényi (ER): A purely random network where connections are distributed uniformly.
  • Stochastic Block Model (SBM): A network with "communities" or clusters, mimicking real-world social or regional groupings.
  • Barabási-Albert (BA): A "scale-free" network where a few "hubs" have many connections, while most nodes have few (similar to the actual internet or the Bitcoin overlay network).
  • Metric of Interest: Closeness Centrality, which measures how "close" a node is to all other nodes in the network.

Datasets

As a theoretical and simulation-based study, the paper does not use a training "dataset" in the machine learning sense. Instead, it uses:

  • Synthetic Network Ensembles: Generated graphs with $|V| = 1000$ nodes and an average degree of 8 (matching the default max_connections settings in the Bitcoin protocol).
  • Empirical Calibration: The authors used historical data from Bitcoin, Ethereum, Litecoin, and Dogecoin (specifically block creation times and median propagation delays) to calibrate their model parameters and ensure their simulations reflected reality.

Key Insights and Ideas

  • Centrality is a "Time Machine": High closeness centrality acts like a head start. In a competitive fork, the node that can reach the majority of the network first wins. A central node can effectively "erase" the time advantage of a peripheral node that mined its block earlier.
  • The "Hub" Advantage in Scale-Free Networks: In Barabási-Albert networks, the advantage is extreme. Because these networks have highly connected hubs, a central node can win the consensus race even if it broadcasts its block several time steps ($\Delta t$) after a peripheral node.
  • Community "Stickiness": In the Stochastic Block Model, forks tend to be more persistent. If a block is mined within a dense community, it takes over that cluster very quickly, making it harder for a competing block from a different community to displace it.
  • Validation of the Model: The authors' mathematical derivation for the probability of forks ($C(\Delta)$) yielded a 1.45% fork rate for Bitcoin, which is remarkably close to the historically observed value of 1.69%.

Key Results

  • Winning Probability: In all network types, as closeness centrality increases, the probability of winning a fork increases significantly.
  • Resilience to Delay: In scale-free (BA) networks, nodes in the top quantiles of centrality maintained a non-negligible win rate even when they were 2 or 3 steps behind in the broadcast race. In contrast, in random (ER) networks, being even one step late resulted in a much sharper drop in win probability.
  • Network Diameter: The researchers found that for a network of 1000 nodes with an average degree of 8, the "effective" propagation time ($t^*$) is roughly 4 steps. This small diameter is what allows central nodes to exert such a strong influence over the entire system.

Limitations and Future Work

  • Honest vs. Strategic Behavior: The current model assumes nodes follow the protocol (broadcasting immediately). It doesn't fully account for "selfish mining" where a node might strategically withhold a block.
  • Static Topology: Real peer-to-peer networks are dynamic; nodes join and leave (churn), and connections change. This study uses static snapshots.
  • Computational Power: While the main results assume equal mining power per node, the authors provide an appendix for heterogeneous power. Future work could explore the "double whammy" of a node having both high hash power and high network centrality.
  • Beyond PoW: The authors suggest this framework should be applied to Proof-of-Stake (PoS) and voting-based systems (like Stellar or Ripple), where network position might be even more critical for security and liveness.

Summary updated

Abstract

Reaching consensus—a macroscopic state where the system constituents display the same microscopic state—is a necessity in multiple complex socio-technical and techno-economic systems: their correct functioning ultimately depends on it. In many distributed systems—of which blockchain-based applications are a paradigmatic example—the process of consensus formation is crucial not only for the emergence of a leading majority but for the very functioning of the system. We build a minimalistic network model of consensus formation on blockchain systems for quantifying how central nodes—with respect to their average distance to others—can leverage on their position to obtain competitive advantage in the consensus process. We show that in a wide range of network topologies, the probability of forming a majority can significantly increase depending on the centrality of nodes that initiate the spreading. Further, we study the role that network topology plays on the consensus process: we show that central nodes in scale-free networks can win consensus in the network even if they broadcast states significantly later than peripheral ones.
BibTeX
@inproceedings{fadda2022consensus,
  author = {Edoardo Fadda and Junda He and Claudio J. Tessone and Paolo Barucca},
  title = {{Consensus formation on heterogeneous networks}},
  booktitle = {EPJ Data Sci},
  year = {2022},
  url = {https://openreview.net/forum?id=uXK6tcHe1g},
}

Loading related content...

Figure