$$
\newcommand{\po}{\text{PO}}
\newcommand{\xor}{\oplus}
$$

# Swarm Incentives

#### Proximity Order (PO)
Swarm quantifies the distance between nodes $a$ an $b$ in terms of a _proximity order_ $\po(a,b)$, as opposed to the more widely known Kademlia distance. Simply put, $\po(a,b)$ represents the length of the prefix, in bits, that $a$'s and $b$'s ID share in common; e.g. if $a$'s id is $00101$ and $b$'s is $00111$, then $\po(a,b) = 3$.

The book also says, as a somewhat cryptic footnote: _proximity order is the discrete logarithmic scale of proximity, which, in turn is the inverse of normalised XOR distance_.

To see what this means, let $a$ and $b$ be two peer IDs in a Kademlia DHT, and let $u$ be the length of its ID space in bits. The Kademlia distance $d_k(a,b)$ is the integer represented by $a \xor b$, where $\xor$ is the bitwise XOR of $a$ and $b$.

If we look at $i = \lfloor \log_2 d_k(a,b) \rfloor$, this gives us the highest power of two that is smaller or equal to $d_k(a,b)$, i.e., $2^i \leq d_k(a,b) < 2^{i+1}$, which also happens to be the highest-order bit in which $a$ and $b$ differ from each other.

This means that $u - \lfloor \log_2 d_k(a,b) \rfloor$ is the number of bits in which $a$ and $b$ coincide, as they become leading zeros in $i$. In other words, $\po(a, b) = u - \lfloor \log_2 d_k(a,b) \rfloor$. We can now get to the bottom of the footnote:

$$
\begin{aligned}
\po(a, b) &= u - \lfloor \log_2d_k(a,b) \rfloor <\\
& < u - \log_2d_k(a,b) + 1=\\
&= \log_2 \frac{2^u}{d_k(a,b)} + 1 = \\
&= \log_2 \left(\frac{d_k(a,b)}{2^u}\right)^{-1} + 1 \leq\\
&\leq \po(a,b) + 1
\end{aligned}
$$

Note that $d_k(a,b)/2^u$ is the Kademlia distance normalized over $[0,1]$. The proximity order is, then, approximately the inverse of a normalized Kademlia distance, which is what the footnote says.

#### Depths
Let $N_q$ be the set of neighbors known to a peer $q$. $q$ organizes its Kademlia routing table in a series "bins" (or buckets in Kademlia terms), one bin per each distinct proximity order; i.e.:

$$
B_i = \{p \in N : \po(q, p) = i \}
$$

A _depth_ $d$ refers to all bins $B_i$ such that $i \geq d$. There are $u$ such bins; i.e., $0 \leq i < u$. A bin $B_i$ is said to be _deeper_ (_shallower_) than a bin $B_j$ iff $i > j$ ($i < j$). The deepest bin is bin $u - 1$, and the shallowest is bin $0$.

#### Replication Depth
Data in Swarm must be replicated over at least $r$ nodes to ensure enough redundancy. For a given node $p$ with neighbors $N_p$, define:

$$
N^{\geq d}_p = \left\{ q \in N_p :\ \po(p,q) \geq d \right\}
$$

i.e., $N^{\geq d}_p$ contains all neighbors from bins $B_d$ up to bin $B_{u - 1}$. In any Kademlia network with more than $r$ nodes, there should exist a depth parameter $d_s$ in which the neighbors known by healthy nodes should satistfy, for most[^1] $p$:

$$
\left|N_p^{\geq d}\right| \geq r
$$

This means that if a node $q$ always replicates its chunks at all neighbors at depth $d_s$ or deeper, then we should have that each chunk is stored at least $r$ times at the nodes closest to $p$.

#### Disjoint Replication Sets

A somewhat less trivial realization is that replicating data at a set depth puts chunks in disjoint replication sets.

The key here is the realization that Kademlia distance (and therefore proximity order) is symmetrical: if nodes $p$ and $q$ are such that $d_k(p,q) = i$, then $d_k(q, p) = i$ as well. This means that if $q$ is in bin $B_i$ for $p$, then $p$ is in bin $B_i$ for $q$. This symmetry leads to the following corollary:

**Corollary 1 .** Let $p$ and $q$ be two nodes such that $p \in N_{q}$ and $q \in N_{p}$. Then $p \in N_q^{\geq d}$ if and only if $q \in N_p^{\geq d}$.

This follows from the defintion of $N_q^{\geq d}$ and $N_p^{\geq d}$, and the symmetry noted above. What the corollary states, in other words, is that if $p$ is within replication depth for $q$, then $q$ is within replication depth for $p$, and the converse also holds true: if $p$ is _not_ within replication depth for $q$, then $q$ is _not_ within replication depth for $p$.

Now notice that "being in replication depth" of each other means that $p$ and $q$ share a common prefix of length (at least) $d_s$. It follows that there are $2^{d_s}$ such prefixes with $2^{u - d_s}$ IDs each and which define, as per Corollary 1, completely disjoint replication sets. The size of these sets should be roughly $N/2^{u - d_s}$, where $N$ is the number of nodes in the network.

#### Postage Stamp Batches and Batch Depth

Storing a paid chunk requires it to be attached to a postage stamp. Stamps are acquired in batches. The amount of stamps acquired is always a power of two; e.g., $2^k$. $k$ is referred to as the "batch depth".

#### Reserve Size and Reserve Depth
The text defines the _reserve size_ $s_r$ as the total amount of non-expired stamps (or _storage slots_ associated to such stamps) at any given time [^2].

It then defines the _reserve depth_ as $d_r = \lceil \log_2 s_r \rceil$. The text then makes a claim I cannot make sense of:

_The reserve depth is determined by taking the base 2 logarithm of the DISC reserve size and rounding it up to the nearest integer. It represents the shallowest PO at which disjoint neighbourhoods are collectively able to accommodate the volume of data corresponding to the total number of paid chunks. This assumes that nodes within the neighbourhood have a fixed prescribed storage capacity to store their share of the reserve._

At that depth, we are partitioning the ID space into $2^{d_r}$ disjoint neighborhoods, each of which will receive about $1/2^{d_r}$ of the paid chunks (assuming wlog that $s_r$ is a power of two), on average. That is $1$ chunk per neighborhood, on average. I cannot really make much sense of this number.

The statement that follows -- that this is the safe lower bound for pull-syncing -- also then ends up not making sense. In fact, it is clear that we could have a much shallower depth for pull-syncing (even zero!) and the chunks in the reserve would be stored just fine; they would just be replicated a lot more.

#### Proofs of Storage

[^1]: I say for _most_ $p$ because it seems in general hard to satisfy it for all $p$ and non-a trivial $d_s$ (i.e., $d_s > 0$), particularly under a dynamic network.

[^2]: It actually says "sum of the sizes of all non-expired batches", which I take to be the number of stamps that have been issued and are not expired at some given moment in time.