Why bootstrapping a peer-to-peer network without a directory is a mathematical utopia

I’ve spent the last few weeks testing mesh LoRa hardware (Meshtastic nodes mostly).

On a Meshtastic mesh, discovery is almost free. Radio is a broadcast medium : a node transmits once and every other node within range hears it. There’s nothing to guess, no address space to search. The only constraint is the proximity of each node.

At the same time, I’m interested in peer-to-peer networks over the Internet and the transposition does impose quite a few constraints. There’s no “radio range” on IP : two hosts a few meters apart and two hosts on opposite sides of the planet are equally reachable (or equally invisible actually) to each other. Reachability over the Internet is not a physical proximity constraint, it’s a function of knowing an address that could be almost anything. Discovery becomes more about random guessing than a search within the area.

In a centralized network, peer discovery is easy : a directory, a tracker or a central authority tells where the network nodes are. But that comes at a cost : a single point of failure. For a network whose purpose is to resist censorship, a central server is an obvious target : block the directory’s IP address and the entire network disappears. The promise of total decentralization is that peer discovery becomes as resilient as the network itself. A fully decentralized network has no central authority and delegates peer discovery to the peers themselves. But a node’s ability to find another node with no intermediary is limited by two basic constraints : the size of the address space (the IP adress space) and how long nodes stay reachable. On the Internet, none of these constraints can be guaranteed.

Let’s dig into it.

#The address space

For an IPv4 network, the global address space is the set of all 32-bit binary vectors :

The total number of addressable addresses is:

Let $n$ be the number of active nodes belonging to the peer-to-peer network at a given time $t$. Define the network’s density $\delta$ as the probability that a uniformly randomly sampled address belongs to the set of active peers:

This is a simplified model : it assumes that peers are uniformly distributed across the IPv4 address space and that any address belonging to a peer is directly reachable. In practice, NAT, firewalls, ports, routing and service availability make the real situation even more complex.

Searching for a peer by random sampling can be modeled as a geometric distribution, where each query is an independent Bernoulli trial with success probability $p = \delta$. The expected number $E[X]$ of queries needed to make first contact is :

For a network starting up with $n = 100$ peers :

Now let $v$ be the scan rate (queries on the address space per second). The average discovery time $T$ is:

Assuming a (very) optimistic scan rate of $v = 10^3$ requests per second :

So, brute-force discovery of a single node on an authority-free network takes close to 12 hours. For a network that already has 100 peers running.

For a very new network of just $n = 2$ peers, the theoretical discovery time increases to roughly … 24.9 days ! And on a IPv6 adress space, it completely stops being a practical number at all : $\approx 5.4 \times 10^{27}$ years (390 quadrillion times the current age of the universe).

#The problem : addresses change

The scale of the address space alone would be a solvable engineering problem (well, you could, in principle, scan forever). But peers can’t scan forever, because the addresses they’re scanning for don’t stay put. DHCP lease duration isn’t fixed : it varies by router vendor, ISP and network type, but a reasonable working approximation would be between 7 to 14 days.

Take $T = 14$ days (1,209,600 seconds) as an upper bound. The total number of scan attempts a peer can realistically make in that window is :

Each discovery attempt is a Bernoulli trial with two outcomes : hit or miss. The probability of exactly $k$ hits is :

with :

• $S = 1.2096 \times 10^{9}$ trials,
• $p = \dfrac{1}{4\,294\,967\,296} \approx 2.33 \times 10^{-10}$, the probability of a hit on any given attempt.
  
  

By the Poisson limit theorem ($S \to \infty$, $p \to 0$), the binomial distribution $B(S,p)$ converges to a Poisson distribution $P(\lambda)$ with $\lambda = Sp$ :

The probability of finding at least one peer ($X \ge 1$) over the whole lease window is :

A peer has roughly a 1-in-4 chance of ever finding another peer on IPv4 over an entire DHCP lease and that’s the very best case, assuming :

• the searching peer dedicates 100% of its time and bandwidth to scanning, continuously, for the full 14 days, at $v = 10^3$ requests/second
• nodes being searched for keep their IP for at least 14 days.

None of these assumptions are realistic.

That’s why fully decentralized networks aren’t really fully decentralized. Bitcoin comes with hardcoded seed nodes and DNS seeds. BitTorrent leans on trackers. Tor has directory authorities. I2P has reseed servers. Pure peer-to-peer discovery is almost impossible when the address space is so large and constantly changing. These authorities, trackers and hardcoded nodes are needed for decentralization to work at all.

So, a fully peer-to-peer network with no authority, as sexy as it is, would be almost utopian over the Internet.