Network

This chapter elaborates on how the Swarm overlay network is built on top of a peer-to-peer network protocol to form a topology that allows for the routing of messages between nodes (2.1). In 2.2, we describe how such a network can serve as a scalable distributed storage solution for data chunks (2.2.1.0) and present the logic underpinning the protocols for retrieval/download and syncing/upload (2.3).

2.1 Topology and routing

This section sets the scene (2.1.1) for the overlay network of Swarm by making explicit the assumptions about the underlay network. 2.1.2 introduces the overlay address space and explains how nodes are assigned an address. In 2.1.3, we present the Kademlia overlay topology (connectivity pattern) and explain how it solves routing between nodes. In 2.1.4, we show how nodes running the Swarm client can discover each other, bootstrap, and then maintain the overlay topology.

2.1.1 Requirements for underlay network

Swarm is a network operated by its users. Each node in the network is supposed to run a client complying with the protocol specifications. On the lowest level, the nodes in the network connect using a peer-to-peer network protocol as their transport layer. This is called the underlay network. In its overall design, Swarm is agnostic of the particular underlay transport used as long as it satisfies the following requirements:

Addressing

Nodes are identified by their underlay address.

Dialling

Nodes can initiate a direct connection to a peer by dialing them on their underlay address.

Listening

Nodes can listen to other peers dialing them and can accept incoming connections. Nodes that do not accept incoming connections are called light nodes.

Live connection

A node connection establishes a channel of communication, indicating that the remote peer is online and accepting messages until explicitly disconnected.

Channel security

The channel provides identity verification and implements encrypted and authenticated transport resisting man-in-the-middle attacks.

Protocol multiplexing

The underlay network service can accommodate several protocols running on the same connection. Peers communicate the protocols with the name and versions that they implement, and the underlay service identifies compatible protocols and starts up peer connections on each matched protocol.

Delivery guarantees

Protocol messages have guaranteed delivery, i.e. any delivery failures due to network problems prompt direct error responses. The sequence in which messages are delivered is guaranteed within each protocol, and ideally, the underlay protocol provides prioritisation. If protocol multiplexing takes place on the same transport channel, framing is likely implemented to prevent long messages from blocking higher-priority ones.

Serialisation

The protocol message construction supports arbitrary data structure serialisation conventions.

The libp2p library can provide all the needed functionality and is the designated underlay connectivity driver in the specification.¹

2.1.2 Overlay addressing

While clients use the underlay address to establish connections to peers, each node running Swarm is additionally identified with an overlay address. It is this address that determines which peers a node will connect to and also directs the way messages are forwarded. The overlay address is assumed to be stable as it defines a node’s identity across sessions and ultimately affects which content is prioritised for storage in the node’s local storage.

The node’s overlay address is derived from an Ethereum account by hashing the corresponding elliptic curve public key with the bzz network ID using the 256-bit Keccak algorithm. The inclusion of the bzz network ID is rooted in the fact that there can be multiple Swarm networks (e.g. test net, main net, or private Swarms). It serves to ensure that the same address cannot be used across different networks. Assuming any sample of base accounts are independently selected, the resulting overlay addresses are expected to have a uniform distribution in the address space of 256-bit integers. It is important to derive the address from a public key, as it allows the nodes to issue commitments associated with an overlay location using cryptographic signatures that are verifiable by third parties.

Using the long-lived communication channels of the underlay network, Swarm nodes form a network with quasi-permanent peer connections. The resulting connectivity graph can then realise a particular topology defined over the address space. The overlay topology chosen is called Kademlia: It enables communication between any two arbitrary nodes in the Swarm network by providing a strategy to relay messages using only underlay peer connections. The protocol that describes how nodes share information with each other about themselves and other peers is called ’hive’. How nodes use this protocol to bootstrap the overlay topology is discussed in 2.1.4.

It is crucial that the overlay address space encompasses the full range of 256-bit integers. One central concept in Swarm is proximity order (PO), which quantifies the relatedness of two addresses on a discrete scale.² Given two addresses, $x$ and $y$, $\mathit{PO}(x,y)$ counts the matching bits of their binary representation starting from the most significant bit up to the first one that differs. The highest proximity order is therefore 256, designating the maximum relatedness, i.e. where $x=y$.

2.1.3 Kademlia routing

Kademlia topology can be used to route messages between nodes in a network using overlay addressing. It has excellent scalability as it allows for universal routing such that both (1) the number of hops and (2) the number of peer connections are always logarithmic to the size of the network.

In what follows, we show the two common flavours of routing: iterative/zooming and recursive/forwarding. Swarm’s design crucially relies on the latter, forwarding flavour, which sets it apart as a less common approach compared to the more prevalent iterative flavour found in much of the peer-to-peer literature and used in most other implementations (see Maymounkov and Mazieres 2002, Baumgart and Mies 2007, Lua et al. 2005). To provide a comprehensive understanding, we will walk the reader through both approaches to reveal their idiosyncrasies.

Iterative and forwarding Kademlia

Let $R$ be an arbitrary binary relation over nodes in a network. Nodes that are in relation $R$ with a particular node $x$ are called peers of $x$. Peers of $x$ can be indexed by their proximity order (PO) relative to $x$. The equivalence classes of peers are called proximity order bins, or just bins for short. Once arranged in bins, these groups of peers form the Kademlia table of the node $x$ (see Figure 2.1).

Node $x$ has a saturated Kademlia table if there is a $0\le d_x\le \mathit{maxPO}$ called the neighbourhood depth such that (1) the node has at least one peer in each bin up to and excluding proximity order bin $d_x$ and (2) all nodes at least as near as $d_x$ (called the nearest neighbours) are peers of $x$. If each node in a network has a saturated Kademlia table, then we say that the network has Kademlia topology.

Let $R$ be the "is known to" relation: $y$ "is known to" $x$ if $x$ has both overlay and underlay addressing information for $y$. In iterative Kademlia routing, the requestor node iteratively extends the graph of peers that are known to it. Using their underlay address, the requestor node will contact the peers that they know are nearest the destination address for peers that are further away (commonly using UDP). On each successive iteration, the peers become at least one order closer to the destination (see Figure 2.3). Because of the Kademlia criteria, the requestor will eventually discover the destination node’s underlay address and can then establish direct communication with it. This iterative strategy³ critically depends on the nodes’ ability to find peers that are currently online. In order to find such a peer, a node needs to collect several candidates for each bin. The best predictor of availability is the recency of the peer’s last response, so peers in a bin should be prioritised according to this ordering.

Swarm uses an alternative flavour of Kademlia routing, first described in Heep (2010) and then expanded on and worked out by Trón et al. (2019b). Here, a recursive method is employed, whereby the successive steps of the iteration are "outsourced" to a downstream peer. Each node recursively passes a message to a direct peer at least one proximity order closer to the destination. Thus, routing using this approach simply means relaying messages via a chain of peers which are ever closer to the destination, as shown in Figure 2.3.

In this way, Swarm’s underlay transport offers quasi-stable peer connections over TCP with communication channels that are kept alive. These open connections can then be used as $R$ to define another notion of a peer. The two criteria of healthy Kademlia connectivity in Swarm translate as: For each node $x$, there exists a neighbourhood depth $d_x$ such that (1) node $x$ has an open connection with at least one node for each proximity order bin up to but excluding $d_x$, and (2) is connected to all the online nodes that are at least as near as $d_x$. If each node in the network has a saturated Kademlia table of peers, then the network is said to have Kademlia topology. Since connected peers are guaranteed to be online, the recursive step consists solely of forwarding the message to a connected peer strictly closer to the destination. We can call this alternative forwarding Kademlia.

In a forwarding Kademlia network, a message is said to be routable if there exists a path from sender to destination through which the message can be relayed. In a mature subnetwork with Kademlia topology every message is routable. If all peer connections are stably online, a thin Kademlia table, i.e. a single peer for each bin up to $d$, is sufficient to guarantee routing between nodes. In reality, however, networks are subject to churn, i.e. nodes are expected to go offline regularly. In order to ensure routability in the face of churn, the network needs to maintain Kademlia topology. This means that each individual node needs to have a saturated Kademlia table at all times. By keeping several connected peers in each proximity order bin, a node can ensure that node dropouts do not damage the saturation of their Kademlia table. Given a model of node dropouts, we can calculate the minimum number of peers needed per bin to guarantee that nodes are saturated with a probability that is arbitrarily close to 1. The more peers a node keeps in a particular proximity order bin, the more likely that the message destination address and the peer will have a longer matching prefix. As a consequence of forwarding the message to that peer, the proximity order increases more quickly, and the message ends up closer to the destination than it would with less peers in each bin (see also Figure 2.4).

With Kademlia saturation guaranteed, a node will always be able to forward a message and ensure routability. If nodes comply with the forwarding principles (and that is ensured by aligned incentives), the only case when relaying could possibly break down is when a node drops out of the network after having received a message but before it managed to forward it.⁴

An important advantage of forwarding Kademlia is that this method of routing requires a lot less bandwidth than the iterative algorithm. In the iterative version, known peers are not guaranteed to be online, so finding one that is available adds an additional level of unpredictability.

Sender anonymity

Sender anonymity is a crucial feature of Swarm. It is important that peers further down in the request cascade can never know who the originator of the request was, because requests are relayed from peer-to-peer.

The above rigid formulation of Kademlia routing would suggest that if a node receives a message from a peer and that message and peer have a proximity order of $0$, then the recipient would be able to conclude that the peer it received the message from must be the sender. If we allow light node Swarm clients, i.e. clients that due to resource constraints do not keep a full Kademlia saturation but instead have just a local neighbourhood, then even a message from a peer in bin $0$ remains of ambiguous origin.

Bin density and multi-order hops

As a consequence of logarithmic distance and uniform node distribution, the population of peers exponentially increases as we move further away from a particular node. This means that unless the number of required connections in a bin doubles as bins increase in distance from the node, shallower bins will always allow more choice of nodes for potential connection. In particular, nodes have a chance to increase the number of connections per bin in such a way that peer addresses maximise density (i.e., in proximity order bin $b$, the subsequent bits of peer addresses form a balanced binary tree). Such an arrangement is optimal in the sense that for a bin depth of $d$, nodes are able to relay all messages so that in one hop the proximity order of the destination address will increase by $d$ (see Figure 2.4).

Factoring in underlay proximity

It is expected that as Swarm clients continue to evolve and develop, nodes may factor in throughput when they select peers for connection. All things being equal, nodes physically closer to each other tend to have higher throughput, and therefore will be preferred in the long run. This is how forwarding Kademlia is implicitly aware of the underlay topology (Heep 2010).

2.1.4 Bootstrapping and maintaining Kademlia topology

This section discusses how a stable Kademlia topology can emerge. In particular, it outlines the exact bootstrapping protocol that each node must follow to reach and maintain a saturated Kademlia connectivity. Nodes joining a decentralised network are supposed to be initially naive, potentially initiating connection via only a single known peer with no prior knowledge. For this reason, the bootstrapping process needs to include an initial step that helps naive nodes to begin exchanging information about each other. This discovery process is called the hive protocol.

Bootnodes

Swarm has no distinct node type or operation mode for bootnodes. This means that naive nodes should be able to connect to any node on the network and bootstrap their desired connectivity. In order not to overburden any single node, electing one particular node as an initial connection should be avoided, and the role of being a bootnode for the newly connecting naive nodes should ideally be distributed among participant nodes. This is achieved either with an invite system, or a centralised bootnode service running a public gateway that responds to an API call with the bzz address of a randomly chosen node among online peers.

Once connected to a node in the network, the hive protocol kicks in and the naive node begins to learn about the bzz addresses of other nodes, and thus it can start bootstrapping its connectivity.

Building up connections

Initially, each node begins with zero as their saturation depth. Nodes keep advertising their saturation depth to their connected peers as it changes. When a node $A$ receives an attempt to establish a new connection from a node $B$, she notifies each of her other peers about $B$ connecting to her only in the case that each peer’s proximity order relative to the connecting node $A$ is not lower than that peer’s advertised saturation depth. The notification is always sent to a peer that shares a proximity order bin with the new connection. Formally, when $y$ connects to $x$, $x$ notifies a subset of its connected peers. A peer $p$ belongs to this subset if $\mathit{PO}(x,p)=\mathit{PO}(x,y)$ or $d_p\le \mathit{PO}(y,p)$. The notification takes the form of a protocol message and includes the full overlay address and underlay address information.⁵

Mature connectivity

After a sufficient number of nodes are connected, a bin becomes saturated and the node’s neighbourhood depth can begin to increase. Nodes keep their peers up to date by advertising their current depth if it changes. As their depth increases, nodes will get notified of fewer and fewer peers. Once the node finds all their nearest neighbours and has saturated all the bins, no new peers are to be expected. For this reason, a node can conclude a saturated Kademlia state if it receives no new peers for some time.⁶ Instead of having a hard deadline and a binary state of saturation, we can quantify the certainty of saturation by considering the time elapsed since the arrival of the most recent new peer. Assuming stable connections, eventually each node online will get to know its nearest neighbours and connect to them while keeping each bin up to $d$ non-empty. Therefore each node will converge on the saturated state. To maintain a robust Kademlia topology in the face of changing peer connections, it is crucial to include multiple peers within each proximity order bin. This prevents the node from regressing to a lower saturation state, even when there are no new nodes joining the network.

2.2 Swarm storage

In this section, in 2.2.1, we first show how a network with quasi-permanent connections in a Kademlia topology can support a load balancing, distributed storage of fixed-sized data blobs. In 2.2.1.0, we detail the generic requirements on chunks and introduce actual chunk types. Finally, in 2.2.5, we turn to redundancy by neighbourhood replication as a first line of defense against node churn.

2.2.1 Distributed immutable store for chunks

In this section, we discuss how networks using Kademlia overlay routing are a suitable basis on which to implement a serverless storage solution using distributed hash tables (DHTs). Then we introduce the DISC⁷ model, Swarm’s narrower interpretation of a DHT for storage. This model imposes some requirements on chunks and necessitates ’upload’ protocols.

As is customary in Swarm, we provide a few resolutions of this acronym, which summarise the most important features:

• decentralised infrastructure for storage and communication,
• distributed immutable store for chunks,
• data integrity by signature or content address,
• driven by incentives with smart contracts.

From DHT to DISC

Swarm’s DISC shares many similarities with widely known distributed hash tables. The most important difference is that Swarm does not keep track of where files are to be found, instead it actually stores pieces of the file itself directly with the closest node(s). In what follows, we review DHTs, as well as dive into the similarities and differences with DISC in more detail.

Distributed hash tables use an overlay network to implement a key–value container distributed over the nodes (see Figure 2.5). The basic idea is that the keyspace is mapped onto the overlay address space, and the value for a key in the container is to be found with nodes whose addresses are in the proximity of the key. In the simplest case, let us say that this is the single closest node to the key that stores the value. In a network with Kademlia connectivity, any node can route to a node whose address is closest to the key, therefore a lookup (i.e. looking up the value belonging to a key) is reduced simply to routing a request.

DHTs used for distributed storage typically associate content identifiers (as keys/addresses) with a changing list of seeders (as values) that can serve that content (IPFS 2014, Crosby and Wallach 2007). However, the same structure can be used directly: in Swarm, it is not information about the location of content that is stored at the node closest to the address, but the content itself (see Figure 2.6).

Constraints

The DISC storage model is opinionated about which nodes store what content and this implies the following restrictions:

fixed-size chunks

Load balancing of content is required among nodes and is realised by splitting content into equal-sized units called chunks (see 2.2.1.0).

syncing

There must be a process whereby chunks get to where they are supposed to be stored, no matter which node uploads them (see 2.3.2).

plausible deniability

Since nodes do not have a say in what they store, measures should be employed that serve as the basis of legal protection for node operators. They need to be able to plausibly deny knowing (or even being able to know) anything about the chunks’ contents (see 2.2.4).

garbage collection

Since nodes commit to store any data close to them, there needs to be a strategy to select which chunks are kept and which are discarded in the presence of storage space constraints.

Chunks

Chunks are the basic storage units used in Swarm’s network layer. They are an association of an address with content. Since retrieval in Swarm (2.3.1) assumes that chunks are stored with nodes close to their address, fair and equal load balancing requires that the addresses of chunks should also be uniformly distributed in the address space, and have their content limited and roughly uniform in size.

When chunks are retrieved, the downloader must be able to verify the correctness of the content given the address. Such integrity translates to guaranteeing uniqueness of content associated with an address. In order to protect against frivolous network traffic, a third party of forwarding nodes should be able to verify the integrity of chunks using only local information available to the node.

The deterministic and collision-free nature of addressing implies that chunks are unique as a key–value association: If there exists a chunk with an address, then no other valid chunk can have the same address; this assumption is crucial as it makes the chunk store immutable, i.e. there is no replace/update operation on chunks. Immutability is beneficial in the context of relaying chunks as nodes can negotiate information about the possession of chunks simply by checking their addresses. This plays an important role in the stream protocol (see 2.3.3) and justifies the DISC resolution as a distributed immutable store for chunks.

To sum up, chunk addressing needs to fulfill the following requirements:

deterministic

To enable local validation.

collision-free

To provide integrity guarantee.

uniformly distributed

To deliver load balancing.

In the current version of Swarm, we support two types of chunks: content addressed chunks and single owner chunks.

2.2.2 Content addressed chunks

A content addressed chunk is not assumed to be a meaningful storage unit, i.e. they can be just blobs of arbitrary data resulting from splitting a larger data blob, a file. The methods by which files are disassembled into chunks when uploading and then reassembled from chunks when downloading are detailed in 4.1. The data size of a content addressed Swarm chunk is limited to 4 kilobytes. One of the desirable consequences of using this small chunk size is that concurrent retrieval is available even for relatively small files, reducing the latency of downloads.

Binary Merkle tree hash

The canonical content addressed chunk in Swarm is called a binary Merkle tree chunk (BMT chunk). The address of BMT chunks is calculated using the binary Merkle tree hash algorithm (BMT hash). The base hash used in BMT is Keccak256, properties of which such as uniformity, irreversibility, and collision resistance all carry over to the BMT hash algorithm. As a result of uniformity, a random set of chunked content will generate addresses evenly spread in the address space, i.e. imposing storage requirements balanced among nodes.

The BMT chunk address is the hash of the 8-byte span and the root hash of a binary Merkle tree (BMT) built on the 32-byte segments of the underlying data (see Figure 2.8). If the chunk content is less than 4k, the hash is calculated as if the chunk was padded with all zeros up to 4096 bytes.

This structure allows for compact inclusion proofs with a 32-byte resolution. An inclusion proof is a proof that one string is a substring of another string, for instance, that a string is included in a chunk. Inclusion proofs are defined on a data segment of a particular index, see Figure 2.9. Such Merkle proofs are also used as proof of custody when storer nodes provide evidence that they possess a chunk (see 3.4). Together with the Swarm file hash (see 4.1.1), they allow for logarithmic inclusion proofs for files, i.e., proof that a string is found to be part of a file.

2.2.3 Single owner chunks

With single owner chunks, a user can assign arbitrary data to an address and attest chunk integrity with their digital signature. The address is calculated as the hash of an identifier and an owner. The chunk content is presented in a structure composed of the identifier, the payload, and a signature attesting to the association of identifier and payload (see Figure 2.10).

content

payload

32 bytes arbitrary identifier

65 bytes $⟨r,s,v⟩$ representation of an EC signature (32+32+1 bytes),

an 8-byte little-endian binary of uint64 chunk span,

maximum 4096 bytes of regular chunk data.

address

Keccak256 hash of identifier + owner account.

The validity of a single owner chunk is checked with the following process:

1.

Deserialise the chunk content into fields for identifier, signature, and payload.

2.

Construct the expected plain text composed of the identifier and the BMT hash of the payload.

3.

Recover the owner’s address from the signature using the plain text.

4.

Check the hash of the identifier and the owner (expected address) against the chunk address.

Single owner chunks offer a virtual partitioning of part of the address space into subspaces associated with the single owner. Checking their validity is actually an authentication verifying that the owner has write access to the address with the correct identifier.

As suggested by the span and the length of the payload, a single owner chunk can encapsulate a regular content addressed chunk. Anyone can simply reassign a regular chunk to an address in their subspace designated by the identifier (see also 4.4.4).

It should be noted that the notion of integrity is somewhat weaker for single owner chunks than in the case of content addressed chunks: After all, it is, in principle, possible to assign and sign any payload to an identifier. Nonetheless, given the fact that the chunk can only be created by a single owner (of the private key that the signature requires), it is reasonable to expect uniqueness guarantees because we hope the node will want to comply with application protocols to get the desired result. However, if the owner of the private key signs two different payloads with the same identifier and uploads both chunks to Swarm, the behaviour of the network is unpredictable. Measures can be taken to mitigate this in layer (3) and are discussed later in detail in 4.3.3.

With two types of chunks, integrity is linked to collision-free hash digests, derived from either a single owner and an arbitrary identifier attested by a signature or directly from the content. This justifies the resolution of the DISC acronym as data integrity through signing or content address.

2.2.4 Chunk encryption

Chunks should be encrypted by default. Beyond client needs for confidentiality, encryption has two further important roles. (1) Obfuscation of chunk content by encryption provides a degree of plausible deniability; using it across the board makes this defense stronger. (2) The ability to choose arbitrary encryption keys together with the property of uniform distribution offer predictable ways of mining chunks, i.e., generating an encrypted variant of the same content so that the resulting chunk address satisfies certain constraints, e.g. is closer to or farther away from a particular address. This is an important property used in (1) price arbitrage (see 3.1.2) and (2) efficient utilisation of postage stamps (see 3.3).

Chunks shorter than 4 kilobytes are padded with random bytes (generated from the chunk encryption seed). The full chunk plaintext is encrypted and decrypted using stream cipher; XOR with a PRNG seeded with the corresponding symmetric key. In order not to increase the attack surface by introducing additional cryptographic primitives, the stream cipher of choice is using Keccak256 in counter mode, i.e. hashing together the key with a counter for each consecutive segment of 32 bytes. In order to allow selective disclosure of individual segments that are part of an encrypted file, yet leak no information about the rest of the file, we add an additional step of hashing to derive the encryption key for a segment within the chunk. This scheme is easy and cheap to implement in the (EVM), lending itself to use in smart contracts containing the plaintext of encrypted Swarm content.

The prepended metadata encoding the chunk span is also encrypted as if it was a continuation of the chunk, i.e. with counter 128. Encrypted chunk content is hashed using the BMT hash digest just as unencrypted ones are. The fact that a chunk is encrypted may be guessed from the span value, but apart from this, in the network layer, encrypted chunks behave in exactly the same way as unencrypted ones.

Single owner chunks can also be encrypted, which simply means that they wrap an encrypted regular chunk. Therefore, their payload and span reflect the chunk content encryption described above, the hash signed with the identifier is the BMT hash of the encrypted span and payload, i.e. the same as that of the wrapped chunk.

2.2.5 Redundancy by local replication

It is important to have a resilient means of requesting data. To achieve this, Swarm implements the approach of defence in depth. In the case that a request fails due to a problem with forwarding, one can retry the request with another peer. Alternatively, to guard against these occurrences, a node can initiate concurrent retrieve requests right away. However, such fallback options are not available if the single last node that stores the chunk drops out from the network. Therefore, redundancy is of major importance to ensure data availability. If the closest node is the only storer of the requested data and it drops out of the network, then there is no way to retrieve the content. This basic scenario is handled by ensuring that each set of nearest neighbours hold replicas of each chunk that is closest to any one of them, duplicating the storage of chunks and therefore providing data redundancy.

Size of nearest neighbourhoods

If the Kademlia connectivity is defined over storer nodes, then in a network with Kademlia topology there exists a depth $d$ such that (1) each proximity order bin less than $d$ contains at least $k$ storer peers, and (2) all storer nodes with proximity order $d$ or higher are actually connected peers. In order to ensure data redundancy, we can add to this definition a criterion that (3) the nearest neighbourhood defined by $d$ must contain at least $r$ peers.

Let us define neighbourhood size ${\mathit{NHS}}_x(d)$ as the cardinality of the neighbourhood defined by depth $d$ of node $x$. Then, a node has Kademlia connectivity with redundancy factor $r$ if there exists a depth $d$ such that (1) each proximity order bin lower than $d$ contains at least $k$ storer peers ($k$ is the bin density parameter, see 2.1.3.0), and (2) all storer nodes with proximity order $d$ or higher are actually connected peers, and (3) ${\mathit{NHS}}_x(d)\ge r$.

We can then take the highest depth $d^{\prime }$ such that (1) and (2) are satisfied. Such a $d$ is guaranteed to exist and the hive protocol is always able to bootstrap it. As we decrease $d^{\prime }$, the number of distinct neighbourhoods grow proportionally, so for any redundancy parameter not greater than the network size $r\le N={\mathit{NHS}}_x(0)$, there will be a highest $0<d_r\le d^{\prime }$ such that ${\mathit{NHS}}_x(d_r)\ge r$. Therefore, redundant Kademlia connectivity is always achievable.

For a particular redundancy, the area of the fully connected neighbourhood defines an area of responsibility. The proximity order boundary of the area of responsibility defines a radius of responsibility for the node. A storer node is said to be responsible for (storing) a chunk if the chunk address falls within the node’s radius of responsibility.

It is already instructive at this point to show neighbourhoods and how they are structured, see Figure 2.12.

Redundant retrievability

A chunk is said to have redundant retrievability with degree $r$ if it is retrievable and would remain so even after any $r$ nodes responsible for it leave the network. The naive approach presented so far requiring the single closest node to keep the content can be interpreted as degree zero retrievability. If nodes in their area of responsibility fully replicate their content (see 2.3.3), then every chunk in the Swarm DISC is redundantly retrievable with degree $r$. Let us take the node $x$ that is closest to a chunk $c$. Since it has Kademlia connectivity with redundancy $r$, there are $r+1$ nodes responsible for the chunk in a neighbourhood fully connected and replicating content. After $r$ responsible nodes drop out, there is just one node remaining which still has the chunk. However, if Kademlia connectivity is maintained as the $r$ nodes leave, this node will continue to be accessible by any other node in the network, and therefore the chunk is still retrievable. Now, for the network to ensure that all chunks remain redundantly retrievable with degree $r$, the nodes comprising the new neighbourhood formed due to the reorganising of the network must respond by re-syncing their content to satisfy the protocol’s replication criteria. This is called the guarantee of eventual consistency.

Resource constraints

Let us assume then that (1) the forwarding strategy that relays requests along stable nodes and (2) the storage strategy that each node in the nearest neighbourhood (of $r$ storer nodes) stores all chunks whose addresses fall within their radius of responsibility. As long as these assumptions hold, each chunk is retrievable even if $r$ storer nodes drop offline simultaneously. As for (2), we still need to assume that every node in the nearest neighbour set can store each chunk. Realistically, however, all nodes have resource limitations. With time, the overall amount of distinct chunks ever uploaded to Swarm will increase indefinitely. Unless the total storage capacity steadily increases, we should expect that the nodes in Swarm are able to store only a subset of chunks. Some nodes will reach the limit of their storage capacity and therefore face the decision whether to stop accepting new chunks via syncing or to make space by deleting some of their existing chunks.

The process that purges chunks from their local storage is called garbage collection. The process that dictates which chunks are chosen for garbage collection is called the garbage collection strategy. For a profit-maximizing node, it holds that it is always best to garbage-collect the chunks that are predicted to be the least profitable in the future and, in order to maximize profit, it is desired for a node to get this prediction right (see 3.3). So, in order to factor in these capacity constraints, we will introduce the notion of chunk value and modify our definitions using the minimum value constraint:

In Swarm’s DISC, at all times, there is a chunk value $v$ such that every chunk with a value greater than $v$ is both retrievable and eventually (after syncing) redundantly retrievable with degree $r$.

This value ideally corresponds to the relative importance of preserving the chunk that uploaders need to indicate. In order for storer nodes to respect it, the value should also align with the profitability of a chunk and is therefore expressed in the pricing of uploads (see 3.3.4).

2.3 Push and pull: chunk retrieval and syncing

In this section, we demonstrate how chunks actually move around in the network: How they are pushed to the storer nodes in the neighbourhood they belong to when they are uploaded, as well as how they are pulled from the storer nodes when they are downloaded.

2.3.1 Retrieval

In a distributed chunk store, we say that a chunk is an accessible chunk if a message is routable between the requester and the node that is closest to the chunk. Sending a retrieve request message to the chunk address will reach this node. Because of eventual consistency, the node closest to the chunk address will store the chunk. Therefore, in a DISC distributed chunk store with healthy Kademlia topology, all chunks are always accessible for every node.

Chunk delivery

For retrieval, accessibility needs to be complemented with a process to have the content delivered back to the requesting node, preferably using only the chunk address. There are at least three alternative ways to achieve this (see Figure 2.13):

direct delivery

The chunk delivery is sent via a direct underlay connection.

routed delivery

The chunk delivery is sent as message using routing.

backwarding

The chunk delivery response simply follows the route along which the request was forwarded, just backwards all the way to the originator.

Firstly, using the obvious direct delivery, the chunk is delivered in one step via a lower-level network protocol. This requires an ad-hoc connection with the associated improvement in latency traded off for worsened security of privacy.⁸ Secondly, using routed delivery, a chunk is delivered back to its requestor using ad-hoc routing as determined from the storer’s perspective at the time of sending it. Whether direct or routed, allowing deliveries routed independently of the request route presupposes that the requestor’s address is (at least partially) known by the storer and routing nodes. Consequently, these methods disclose information that can identify the requestor. However, with forwarding–backwarding Kademlia this is not necessary: The storer node responds back to their requesting peer with the delivery, while intermediate forwarding nodes remember which of their peers requested what chunk. When the chunk is delivered, they pass it on back to their immediate requestor, and so on until it eventually arrives at the node that originally requested it. In other words, the chunk delivery response simply follows the request route back to the originator (see Figure 2.14). Since it is the reverse of the forwarding, we can playfully call this backwarding. Swarm uses this option, which makes it possible to disclose no requestor identification in any form, and thus Swarm implements completely anonymous retrieval.

Ensuring requestor anonymity by default in the retrieval protocol is a crucial feature that Swarm insists upon. This feature aims to safeguard user privacy and enables censorship-resistant access.

The generic solution of implementing retrieval by backwarding as depicted in Figure 2.15 has further benefits relating to spam protection, scaling and incentivisation, which will be discussed in the remainder of this section.

Protection against unsolicited chunks

In order to remember requests, the forwarding node needs to allocate resources that come with a certain cost (they occupy space in memory). The requests that are not followed by a corresponding delivery should eventually be garbage collected, so there needs to be a defined time period during which they are active. Downstream peers also need to be informed about the timeout of this request. This makes sense, since the originator of the request will want to attach a time-to-live duration to the request to indicate how long it will wait for a response.

Sending unsolicited chunks is an offence as it can lead to denial of service (DoS). By remembering a request, nodes are able to recognise unsolicited chunk deliveries and penalise the peers sending them. Chunks that are delivered after the request expires will be treated as unsolicited. Since there may be some discrepancy assessing the expiry time between nodes, there needs to be some tolerance for unsolicited chunk deliveries, but if they go above a particular (but still small) percentage of requests forwarded, the offending peer is disconnected and blacklisted. Such local sanctions are the easiest and simplest way to incentivise adherence to the protocol (see 3.2.5).

Re-requesting

There is the potential for a large proportion of Swarm nodes to not be always stably online. Such a high churn situation would be problematic if we used the naive strategy of forwarding requests to any one closer node: If a node on the path were to go offline before delivery is completed, then the request-response round trip is broken, effectively rendering the chunk requested not retrievable. Commitment to pay for a chunk is considered void if the connection to the requested peer is dropped, so there is no harm in re-requesting the chunk from another node.

Timeout vs. not found

Note that in Swarm there is no explicit negative response for chunks not being found. In principle, the node that is closest to the retrieved address can determine the absence of a chunk at that address and could issue a "not found" response. However, this is not desirable for the following reason: While the closest node to a chunk can verify its absence from its expected location in the network, nodes further away from the chunk cannot reliably conclude the same. They lack first-hand verification, and any positive evidence regarding the chunk’s retrievability obtained later can be retrospectively plausibly deniable.

All in all, as long as delivery has the potential to create earnings for the storer, the best strategy is to keep a pending request open until it times out and be prepared in case the chunk should appear. There are several ways the chunk could arrive after the request: (1) syncing from existing peers (2) appearance of a new node or (3) if a request precedes upload, e.g. the requestor has already "subscribed" to a single owner address (see 6.3) to decrease latency of retrieval. This is conceptually different from the usual server-client based architectures where it makes sense to expect a resource to be either on the host server or not.

Opportunistic caching

Using backwarding for chunk delivery responses to retrieve requests also enables opportunistic caching, where a forwarding node receives a chunk and the chunk is then saved in case it will be requested again. This mechanism is crucial in ensuring that Swarm scales the storage and distribution of popular content automatically (see 3.1.2.0).

Incentives

So far, we have shown that by using the retrieval protocol and maintaining Kademlia connectivity, nodes in the network are capable of retrieving chunks. However, since forwarding is expending a scarce resource (bandwidth), without providing the ability to account for this bandwidth use, network reliability will be contingent on the proportion of freeriding and altruism. To address this, in Section 3 we will outline a system of economic incentives that align with the desired behaviour of nodes in the network. When these profit-maximising strategies are employed by node operators, they give rise to emergent behaviour that is beneficial for users of the network as a whole.

2.3.2 Push syncing

In the previous sections, we presented how a network of nodes maintaining a Kademlia overlay topology can be used as a distributed chunk store and how Forwarding Kademlia routing can be used to define a protocol for retrieving chunks. When discussing retrieval, we assumed that chunks are located with the node whose address is closest to theirs. This section describes the protocol responsible for realising this assumption: ensuring delivery of the chunk to its prescribed storer after it has been uploaded to any arbitrary node.

This network protocol, called push syncing, is analogous to chunk retrieval: First, a chunk is relayed to the node closest to the chunk address via the same route as a retrieval request would be, and then in response a statement of custody receipt is passed back along the same path (see Figure 2.16). The statement of custody sent back by the storer to the uploader indicates that the chunk has reached the neighbourhood from which it is universally retrievable. By tracking these responses for each constituent chunk of an upload, uploaders can make sure that their upload is fully retrievable by any node in the network before sharing or publishing the address of their upload. Keeping this count of chunks push-synced and receipts received serves as the back-end for a progress bar that can be displayed to the uploader to give feedback of the successful propagation of their data across the network (see 6.1).

Statements of custody are signed by the nodes that claim to be the closest to the address. Similarly to downloaders in the retrieval protocol, the identity of uploaders can also remain hidden, hence forwarding Kademlia can implement anonymous uploads.

Another similarity is that in order to allow backwarding for responses, nodes should remember which peer sent a particular chunk. This record should persist for a short period while the statement of custody responses are expected. When this period ends, the record is removed. A statement of custody not matching a record is considered unsolicited and is allowed only up to a small percentage of all push-sync traffic with a peer. Going above this tolerance threshold is sanctioned with disconnection and blacklisting (see 3.2.5).

In this section, we described how the logistics of chunk uploads can be organised with a network protocol using Forwarding Kademlia routing with response backwarding. However, this solution is not complete until it is secured with aligned incentives: The strategy to follow this protocol should be incentivised and DoS abuse should be disincentivised. These are discussed later in detail in 3.3 and 3.1.3).

2.3.3 Pull syncing

Pull syncing is the protocol that is responsible for the following two properties:

eventual consistency

Syncing neighbourhoods as and when the topology changes due to churn or new nodes joining.

maximum resource utilisation

Nodes can pull chunks from their peers to fill up their surplus storage.⁹

Pull syncing is node-centric as opposed to chunk-centric, i.e. it makes sure that a node’s storage is filled if needed, as well as syncing chunks within a neighbourhood. When two nodes are connected, they will start syncing both ways so that on each peer connection there is bidirectional chunk traffic. The two directions of syncing are managed by distinct and independent streams. In the context of a stream, the consumer of the stream is called downstream peer or client, while the provider is called the upstream peer or server.

When two nodes connect and engage in chunk synchronisation, the upstream peer offers all the chunks it stores locally in a data stream per proximity order bin. To receive chunks closer to the downstream peer than to the upstream peer, a downstream peer can subscribe to the chunk stream of the proximity order bin that the upstream peer belongs to in their Kademlia table. If the peer connection is within the nearest neighbour depth $d$, the client subscribes to all streams with proximity order bin $d$ or greater. As a result, peers eventually replicate all chunks belonging to their area of responsibility.

A pull syncing server’s behaviour is referred to as being that of a stream provider in the stream protocol. Nodes maintain a record of the time when they stored a chunk locally by indexing them with an ascending storage count known as the bin ID. For each proximity order bin, upstream peers offer to stream chunks in descending order of storage timestamp. As a result of syncing streams on each peer connection, a chunk can be synced to a downstream peer from multiple upstream peers. In order to save bandwidth by not sending data chunks to peers that already have them, the stream protocol implements a round-trip: Before sending chunks, the upstream peer presents a batch of chunks identified by their address. The downstream peer then responds with indicating which chunks from the offered batch they actually need (see Figure 2.17). Note that the downstream peer determines whether they have the chunk based on the chunk address. Thus, this method critically relies on the chunk integrity assumption discussed in 2.2.1.0.

In the context of a peer connection, a client is said to be synced if it has synced all the chunks of the upstream peer. Note that due to disk capacity limitations, nodes must impose a value cutoff, and as such, "all chunks" reads as shorthand for "all chunks having a value greater than $v$" ($v$ is a constant ranking function, the origin of which is discussed later in 3.3.3). In order for a node to promise they store all chunks with value greater than $v$, it is necessary for all its neighbours to have also stored all chunks greater than value $v$. In other words, nodes syncing inherit the maximum such value from among their storer peers.

If chunks are synced in the order they are stored, this may not result in the node always having the most profitable (most often requested) chunks. Thus it may be advisable to sync chunks starting with the most popular ones according to upstream peers and finish syncing when storage capacity is reached. In this way, a node’s limited storage will be optimised. Syncing and garbage collection are discussed further in 3.3 and 3.3.4.

To conclude this section, we show how the criteria of eventual consistency are met in a healthy Swarm. Chunks found in the local store of any node will become retrievable after being synced to their storers. This is because as long as those as peers in the network pull chunks closer to them than to the upstream peer, each chunk travels a route that would also qualify as valid a forwarding path in the push-sync protocol. If new nodes are added and old nodes drop out, neighbourhoods change, but as long as local redundancy is high enough that churn can not render previously retrievable chunks non-retrievable, neighbourhoods eventually replicate their content and redundancy is restored. Consider the unlikely event that a whole new neighbourhood is formed and the nodes that originally held the content belonging to this neighbourhood end up outside of it, resulting in a temporary unavailability of those chunks. Even in this scenario, as long as there is a chain of nodes running pull-syncing streams on the relevant bins, redundant retrievability is eventually restored.

2.3.4 Light nodes

The concept of a light node refers to a special mode of operation necessitated by poor bandwidth environments, e.g. mobile devices on low throughput networks or devices allowing only transient or low-volume storage.

A node is said to be light by virtue of not participating fully in the usual protocols detailed in the previous sections, i.e. retrieval, push syncing, or pull syncing.

A node that has restricted bandwidth environment or in whatever way has limited capacity to maintain underlay connections is not expected to be able to forward messages conforming to the rules of Kademlia routing. This needs to be communicated to its peers so that they do not relay messages to it.

As all protocols in Swarm are modular, a node may switch on or off any protocol independently (depending on capacity and earnings requirements). To give an example: a node that has no storage space available, but has spare bandwidth, may participate as a forwarding node only. Of course, while switching off protocols is technically feasible, a node must at all times take into account the fact that his peers expect a certain level of service if this is advertised and may not accept that some services are switched off and choose not to interact with that node.

Since forwarding can earn revenue, these nodes may still be incentivised to accept retrieve requests. However, if the light node has Kademlia connectivity above proximity order bin $p$ (i.e. they are connected to all storer nodes within their nearest neighbourhood of $r$ peers at depth $d$, and there is at least one peer in each of their proximity order bin from $p$ to $d$), they can advertise this and therefore participate in forwarding.

When they want to retrieve or push chunks, if the chunk address falls into a proximity order bin where there are no peers, they can just pick a peer in another bin. Though this may result in a spurious hop (where the proximity of the message destination to the latest peer does not increase as a result of the relaying), the Kademlia assumption that routing can be completed in logarithmic steps still holds valid.

A node that is advertised as a storer/caching node is expected to store all chunks above a certain value. In order to maintain consistency, they need to synchronise content within their area of responsibility, which requires them to run the pull-sync protocol. The same applies to aspiring storer nodes that come online with available storage and open up to pull-sync streams to fill their storage capacity. In the early stages of this, it does not make sense for a node to sync to other full storer nodes. However, it can still be useful for them to sync with other similar newcomer nodes, especially if storer nodes are maxing out on their bandwidth.

The crucial thing here is that for redundancy and hops to work, light nodes with incomplete, unsaturated Kademlia tables should not be considered by other peers when calculating the level of saturation of the network.