$$
\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_s}\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 (or neighborhoods, in Swarm's terminology).

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". Stamps lose their balance as a function of time, regardless of whether or not they're in use.

To use a stamp, the uploader attaches it to a chunk. Preventing double-spending of stamps is tricky. To understand how Swarm does it, we need to look into another parameter that is passed as part of creating a batch, which is called the _uniformity depth_ $d_u$.

$d_u$ splits the identifier space into $2^{d_u}$ virtual "buckets" of size $2^{k - d_u}$. The number of buckets is made to be larger than the number of replication neighborhoods; i.e., $d_u \geq d_s$, so that complete buckets always fall within a neighborhood.

Stamping a chunk then entails submitting a signed piece of information that contains:

1. the chunk address;
2. the batch ID (available on-chain);
3. an index number $i$;
4. a signature issued by the uploader (the owner of the batch) that confirms the association between the chunk address and index $i$.

The bucket for the chunk is determined by taking the first $d_u$ bytes of its ID. Within that bucket, the index number $i$ must be unique. Since buckets are fully contained within a neighborhood (because $d_u \geq d_s$), any attempt to double-spend a stamp will be caught by the nodes in that neighborhood.

#### 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.

If we want to assume that nodes have a fixed capacity to store, say, $2^t$ chunks each, then the neighborhoods must be small enough so that data gets sharded in a way that respects that constraint (and the redundancy constraint). For $2^{d_r}$ chunks, the minimum depth that would work is $d_r - t$.

If there are not enough neighbors at that depth, then we need to solve for $k$ to figure out the maximum number of chunks that fit into the reserve. Say that $m$ is the depth at which nodes find enough neighbors, then $d_r - m = t \iff d_r = t + m$. In both cases, that depth is not $d_r$.

#### Eviction Policy

Let $b$ be a postage batch. At a given node $p$, the chunks associated to that batch stored at $p$ can be segmented in bins $P^b_{0} \cdots P^b_u$ by proximity order, in the same way we do with peers. Those are called "batch bins".

When nodes run out of space in the reserve, they evict chunks. Chunks are evicted by batch bin. The eviction process follows the following rules:

1. batch bins with lower proximity order (containing chunks farther from the node) are evicted before batch bins with higher proximity order (closer to the node); i.e., chunks that are farther away are evicted first;
2. if $P^b_{i}$ is on the reserve, then all bins $P^{b^\prime}_{i}$ for batches $b^\prime$ with higher per-chunk balances are also on the reserve; i.e., chunks belonging to batches with lower outstanding balance are evicted first.

This means that your data can get evicted at any time, without notice, if the reserve reaches capacity and another user outpays you. Since postage batch balance drains over time at a fixed rate, this will in practice reduce the length of the tenure for the chunks unless the poster increases the batch length.

It effectively makes the storage per unit time more expensive without explicitly modifying it, forcing users to adapt to market price under demand or face eviction. It also makes it harder to obtain guarantees from the system.

#### Storage Guarantees

Nodes in Swarm are incentivized to store data because they will get paid for it. There is no punishment, however, for dropping data; only for deviating from protocol. The "proof" that nodes need to provide to show that they are complying to protocol looks also somewhat weak. We will go into that next.

**Redistribution game.** Nodes are held to protocol by a game. The game is played in rounds (epochs). At the beginning of every round, a random location $a$ within the address space is publicly known (on-chain) to every node.

Nodes whose replication neighborhood contain $a$; i.e., whose first $d_s$ bits match those of $a$, are invited to submit a commitment of their reserves on-chain. This is known as the _commit_ phase.

This committment is a keccack256 hash of the first $m$ chunk addresses when transformed using the standard hmac keyed hash function where the round anchor is used as the key. In practice, this is a random permutation that depends on the anchor, and is equivalent to taking an $m$-sized random sample from the reserve.

Since it would be easy for other nodes within the neighborhood to just see that commitment being submitted and copy it, nodes combine the commitment with a unique reveal nonce, their Kademlia address, and their current storage depth ($d_s$). They then submit the keccack256 hash of those instead.

The next phase of the game, the _reveal_ phase, then begins, and nodes are asked to submit the values they have used to compute the hash submitted earlier. A _winner_ node is selected based on their stake, and the values submitted by the winner are taken to be the truth, provided they match the hash submitted earlier.

Those values are then compared to the values submitted by the other nodes, and those nodes for which they differ get slashed, as do the nodes that do not submit anything during reveal.

One of the key shortcomings I see here is that nodes are submitting addresses as proof - meaning there is nothing actually preventing them from dropping the data and still collecting rewards.

[^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.