Persistence · The Book of Swarm

In this chapter, we focus on data persistence, i.e. the ways of ensuring that content remains available on Swarm. We introduce error coding schemes that can provide cross-neighbourhood redundancy to secure availability against churn, albeit at the cost of increased storage overhead. In particular, erasure codes (5.1) and entanglement codes provide redundancy optimised for documents with different access patterns. Additionally, we introduce the notion of local pinning in 5.2, allowing users to mark specific content as "sticky" in their Swarm local storage. We will discuss how this local pinning can help achieve global persistence across the network through the concept of stewardship. We define a missing chunk notification protocol, which allows content maintainers to ensure that their published content is restored in case some chunks are garbage collected. This restoration is facilitated by proxying retrieval through selected content pinners.

In Section 5.3, we discuss how an immutable chunk store can support user-controlled deletion of content.

5.1 Cross-neighbourhood redundancy: erasure codes and dispersed replicas

First, in 5.1.1, we introduce erasure codes. We then walk through in 5.1.2 how they are applied to files in Swarm. In 5.1.3, we present a construct that enables cross-neighbourhood redundancy for singleton chunks that completes erasure coding. Finally, in 5.1.4, we explore systematic codes that facilitate various retrieval strategies of erasure-coded files, while preserving random access capabilities.

5.1.1 Error correcting codes

Error correcting codes are widely utilised in the context of data storage and transfer to ensure data integrity even in the face of a system fault. Error correction schemes define how to rearrange the original data by adding redundancy to its representation before upload or transmission (encoding ) so that it can correct corrupted data or recover missing content upon retrieval or reception (decoding ). The different schemes are evaluated by quantifying their strength (tolerance, in terms of the rate of data corruption and loss) as a function of their cost (overhead, in terms of storage and computation).

In the context of computer hardware architecture, synchronising arrays of disks is crucial to provide resilient storage in data centres. In erasure coding, in particular, the problem can be framed as follows: How does one encode the stored data into shards distributed across the disks so that the data remains fully recoverable in the face of an arbitrary probability that any one disk becomes faulty? Similarly, in the context of Swarm’s distributed immutable chunk store, the problem can be reformulated as follows: How does one encode the stored data into chunks distributed across neighbourhoods in the network so that the data remains fully recoverable in the face of an arbitrary probability that any one chunk is not retrievable?¹

Reed-Solomon coding (RS) (Bloemer et al. 1995, Plank and Xu 2006, Li and Li 2013) is the father of all error correcting codes and also the most widely used and implemented.² When applied to data of $m$ fixed-size blocks (message of length $m$ ), it produces an encoding of $m + k$ codewords (blocks of the same size) in such a way that having any $m$ out of $m + k$ blocks is enough to reconstruct the original data. Conversely, $k$ puts an upper bound on the number of erasures allowed (number of blocks unavailable) for full recoverability, i.e., it expresses (the maximum) loss tolerance.³ $k$ is also the count of parities, quantifying the data blocks added during the encoding on top of the original volume, i.e., it expresses storage overhead. While RS is, therefore, optimal for storage (since loss tolerance cannot exceed the storage overhead), it has high bandwidth demands⁴ for local repair processes.⁵ The decoder needs to retrieve $m$ chunks to recover a particular unavailable chunk. Hence, ideally, RS is used on files which are supposed to be downloaded in full,⁶ but it is inappropriate for use cases needing only local repairs.⁷

When using RS, it is customary to use systematic encoding, which means that the original data forms part of the encoding, i.e., the parities are actually added to it.

5.1.2 Erasure coding in the Swarm hash tree

Swarm uses the Swarm hash tree to represent files. This structure is a Merkle tree (Merkle 1980), whose leaves are the consecutive segments of the input data stream. These segments are turned into chunks and are distributed among the Swarm nodes for storage. The consecutive chunk references (either in the form of an address or an address and an encryption key) are written into a chunk on a higher level. These so-called packed address chunks (PACs) constitute the intermediate chunks of the tree. The branching factor $b$ is chosen so that the references to its children fill up a full chunk. With a reference size of 32 or 64 (hash size 32) and a chunk size of 4096 bytes, $b$ is 128 for unencrypted, and 64 for encrypted content (see Figure 5.1).

Figure 5.1: The Swarm tree is the data structure encoding how a document is split into chunks.

Note that on the right edge of the hash tree, the last chunk of each level may be shorter than 4K: in fact, unless the file is exactly $4 \cdot b^{n}$ kilobytes long, there is always at least one incomplete chunk. Importantly, it makes no sense to wrap a single chunk reference in a PAC, so it is attached to the first level where there is open chunks. Such "dangling" chunks will appear if and only if the file has a zero digit in its $b$ -ary representation.

During file retrieval, a Swarm client starts from the root hash reference and retrieves the corresponding chunk. Interpreting the metadata as encoding the span of data subsumed under the chunk, it decides that the chunk is a PAC if the span exceeds the maximum chunk size. In case of standard file download, all the references packed within the PAC are followed, i.e., the referenced chunk data is retrieved.

PACs offer a natural and elegant way to achieve consistent redundancy within the swarm hash tree. The input data for an instance of erasure coding is the chunk data of the children, with the equal-sized bins corresponding to the chunk data of the consecutive references packed into it. The idea is that instead of having each of the $b$ references packed represent children, only $m$ would, and the rest of the $k = b - m$ would encode RS parities (see Figure 5.2).

The chunker algorithm that incorporates PAC-scoped RS encoding would work as follows:

1.: Set the input to the actual data level and produce a sequence of chunks from the consecutive 4K segments of the data stream. Choose $m$ and $k$ such that $m + k = b$ is the branching factor (128 for unencrypted, and 64 for encrypted content).
2.: Read the input one chunk at a time. Count the chunks by incrementing a counter $i$ .
3.: Repeat Step 2 until either $i = m$ or there’s no more data left.
4.: Use the RS scheme on the last $i \leq m$ chunks to produce $k$ parity chunks resulting in a total of $n = i + k \leq b$ chunks.
5.: Concatenate the references of all these chunks to result in a packed address chunk (of size $h \cdot n$ of the next level) of the level above. If this is the first chunk on that level, set the input to this level and spawn this same procedure from Step 2.
6.: When the input is consumed, signal the end of input to the next level and quit the routine. If there is no next level, record the single chunks as the root chunk and use the reference to refer to the entire file.

Figure 5.2: The Swarm tree with extra parity chunks using

m = 112

out of

n = 128

RS encoding. Chunks

P_{0}

through

P_{15}

are parity data for chunks

H_{0}

through

H_{111}

on every level of intermediate chunks.

This pattern repeats itself all the way down the tree. Thus, hashes $H_{m + 1}$ through $H_{127}$ point to parity data for chunks pointed to by $H_{0}$ through $H_{m}$ . Since parity chunks $P_{i}$ do not have children, the tree structure does not have uniform depth.

5.1.3 Incomplete chunks and dispersed replicas

If the number of file chunks is not a multiple of $m$ , it is not possible to proceed with the last batch in the same way as the others. We propose that we encode the remaining chunks with an erasure code that guarantees at least the same level of security as the others.⁸ Overcompensating, we still require the same number of parity chunks even when there are fewer than $m$ data chunks.

This leaves us with only one corner case: it is not possible to use our $m -out-of- n$ scheme on a single chunk ( $m = 1$ ) because it would amount to $k + 1$ copies of the same chunk. The problem is that copies of the same chunk all have the same hash and therefore are automatically deduplicated. Whenever a single chunk is left over ( $m = 1$ ) (i.e., the root chunk itself), we would need to replicate the chunk in a way that (1) ideally, the replicas are dispersed in the address space in a balanced way, yet (2) their addresses can be known by retrievers who ideally only know the reference to the original chunk’s address.

Our solution uses Swarm’s special construct, the single owner chunk (SOC; see 2.2.3). Replicas of the root chunk are created by making the chunk data the payload of a number of SOCs. The addresses of these SOCs must be derivable from the original root hash following a deterministic convention shared by uploaders and downloaders.

The address of a SOC is the hash of its ID and the Ethereum address of its owner. In order to create valid SOCs, uploaders need to sign the SOC with the owner’s identity, therefore the owner of the SOC must be a consensual identity with their private key publicly revealed. ⁹

The other component of the address, the SOC ID, must satisfy two criteria: (1) it needs to match the payload hash up to 31 bytes and (2) it must provide the entropy needed to mine the overall chunk into a sufficient number of distinct neighbourhoods. (1) is added as a validation criterion for the special case of replica SOCs, while (2) takes care that we can find replicas uniformly dispersed within the address space. This construct is called dispersed replica:

Let us assume $c$ is the content-addressed chunk we need to replicate; $n$ is the number of bits of entropy available to find the nonces that generate $2^{k}$ perfectly balanced replicas; initialise a chunk array $ρ$ of length $2^{k}$ and start with $n$ -bit integer $i = 0$ and replica counter $C = 0$ .

1.: Create the SOC ID by taking $addr (c)$ and changing the last byte (at index position 31) to $i$ .
2.: Calculate the the SOC address by concatenating ID $i d$ and owner $o$ ¹⁰ and hash the result using the Keccak256 base hash $a_{i} := H (i d \oplus o)$ , and record $c_{i} = SOC (i d, o, c)$ .
3.: Calculate the bin this hash belongs to by taking the $k$ -bit prefix as big-endian binary number $j$ between $0 \leq j < 2^{k}$ .
4.: If $ρ [j]$ is unassigned, then let $ρ [j] := c_{i}$ and increment $C$ .
5.: If $C = 2^{k}$ , then quit.
6.: Increment $i$ by one, if $i = 2^{n}$ , then quit.
7.: Repeat from Step 1.

With this solution, we are able to provide an arbitrary level of redundancy for the storage of data of any length. ¹¹

Then, depending on the strategy, the downloader can choose which address to retrieve the chunk from. The obvious choice is the replica closest to the requesting node’s overlay address.

5.1.4 Prefetching strategies for retrieval

When downloading, systematic per-level erasure codes allow for different prefetching strategies:

NONE = direct with no recovery; frugal: No prefetching takes place, RS parity chunks are ignored if present. Retrieval involves only the original chunks, no recovery.
DATA = prefetching data but no recovery; cheap: Prefetching data-only chunks, RS parity chunks are ignored if present, no recovery.
PROX = distance-based selection; cheap: For all intermediate chunks, first retrieve $m$ chunks that are expected to be the fastest to download (e.g., the $m$ closest to the node).
RACE = latency optimised; expensive: Initiate requests for all chunks within the scope (max $m + k$ ) and will need to wait only for the first $m$ chunks to be delivered in order to proceed. This is equivalent to saying that the $k$ slowest chunk retrievals can be ignored, therefore this strategy is optimal for latency at the expense of cost.

All in all, strategies using recovery can effectively overcome the occasional unavailability of chunks, be it due to faults such as network contention, connectivity gaps in the Kademlia table, node churn, overpriced neighbourhoods, or even malicious attacks targeting a specific neighbourhood.

Similarly, given a typical model of network latencies for chunk retrieval, erasure codes in RACE mode can guarantee an upper limit on retrieval latencies.¹²

5.2 Data stewardship: pinning, reupload and recovery

This section introduces the notion of pinning, i.e. a method to protect locally sticky content from being removed through the garbage collection routines of its storage nodes (5.2.1). In 5.2.2, we discuss how content pinners can play together to pin content for the entire network globally. Section 5.1 defines a recovery protocol that downloaders can use to notify storers of missing chunks belonging to content they are responsible for pinning globally. With such on-demand repair and the uninterrupted download experience it enables, recovery implements a poor man’s persistence measure that can ensure the network-wide availability of specific chunks without requiring the financial outlay of insurance.

5.2.1 Local pinning

Local pinning is the mechanism that makes content sticky and prevents it from being garbage collected. It anchors the content only in the node’s local storage to enable local persistence of data and speedy retrieval. The pinning process operates at the level of individual chunks within the client’s local database and exposes an API for users to pin and unpin files and collections in their local node (see 6.1.4).

In order to pin all the chunks comprising files, clients need to maintain a reference count for each chunk. This count is incremented when a chunk is pinned and decremented when the chunk is unpinned. As long as the reference count remains non-zero, the chunk is considered to be part of at least one pinned document and is therefore immune to garbage collection. Only when the reference count returns to zero—meaning the chunk has been unpinned for every time it was previously pinned—does it become eligible for garbage collection again.

Local pinning can be thought of as a feature that allows Swarm users to mark specific files and collections as important, and therefore not removable. Pinning a file in local storage will also make it perpetually accessible for the local node, even without an internet connection. As a result, using pinned content for the storage of local application data enables an offline-first application paradigm, with Swarm seamlessly managing network activity upon re-connection. However, if a chunk is not within the node’s area of responsibility, local pinning alone is not enough to ensure the chunk’s availability to other nodes, in a general sense. This limitation arises due to the pinner not being in the Kademlia neighbourhood where the chunk is meant to be stored and subsequently searched for when requested using the pull-sync protocol. In order to provide this functionality, we must implement a second half of the pinning protocol.

5.2.2 Global pinning

If a chunk is removed due to garbage collection by storers in its designated neighbourhood, local pinning in nodes elsewhere in the network cannot independently retrieve it. In order for pinning to aid global network persistence, two challenges must be addressed:

global pinners need to be notified when a chunk belonging to the content they have pinned is missing, so they can re-upload it,
chunks that are garbage collected but globally pinned must remain retrievable, ensuring uninterrupted downloads for users.

One naive way to achieve this is to periodically check for pinned chunks in the network and re-upload the contents if they are not found. However, this method involves a lot of superfluous retrieval attempts, has immense bandwidth overhead, and ultimately provides no reduction in latency.

An alternative, reactive way is to organise notifications to the pinner which are somehow triggered when a user attempts to access the pinned content but encounters an unavailable chunk. Ideally, the downloader would send a message to the pinner that triggers two actions: (1) the re-upload of the missing chunk, and (2) the delivery of the chunk in response to the downloader’s request.

Fallback to a gateway

Let us assume that a set of pinner nodes have locally pinned the content and our task is to allow fallback to these nodes. In the simplest scenario, we can set up the node as a gateway (potentially load-balancing to a set of multiple pinner nodes): Users learn of this gateway if it is included in the manifest entry for the file or collection. If the user is unable to download the file or collection from the Swarm due to a missing chunk, they can simply resort to the gateway and find all chunks locally. This solution benefits from simplicity and therefore is likely to be the first milestone towards achieving global persistence.

Mining chunks to pinners’ neighbourhoods

A more sophisticated solution, albeit with more complexity, involves the publisher organising the chunks of a file in a way that they all fall within the neighbourhood of the pinner (or of any pinner node in the set). In order to do this, the publisher needs to find an encryption key for each chunk of the file so that the encrypted chunk’s address matches one of the pinners on at least their first $d$ bits, where $d$ is chosen to be comfortably larger than that pinner’s likely neighbourhood depth.¹³

These solutions can achieve persistence, but they also reintroduce a degree of centralisation and place the burden of maintaining and controlling server infrastructure on publishers. Additionally, they suffer from the usual drawbacks of server-client architecture, namely decreased fault-tolerance and the likelihood of compromised performance due to more concentrated requests. These solutions also fail to address the question of content distribution to pinner nodes and neglect privacy considerations. For these reasons, although the low-level pinning API is provided for Swarm users, it is a less desirable alternative to the incentivised file insurance system, which is seen as the gold standard. As such, use cases should be carefully evaluated to ensure that they would not benefit from the enhanced privacy and resilience provided by the incentivised system.

5.2.3 Recovery

In the following section, we outline a simple protocol for notifying pinners about the loss of a chunk. Pinners can then react by (1) re-uploading the lost chunk to the network and at the same time (2) responding to the notifier by delivering to them the missing chunk.

When replicas of a chunk are distributed among willing hosts (pinners), downloaders who cannot locate a particular chunk can fall back to a recovery process by requesting it from one of these hosts using the missing chunk notification protocol called prod. As usual, the resolutions of this acronym capture the properties of the protocol:

protocol for recovery on deletion: A protocol between requestor and pinners to orchestrate chunk recovery after garbage collection. The process is triggered by downloaders when they fail to retrieve a chunk.
process request of downloader: Recovery hosts continuously listen for potential recovery requests from downloaders.
provide repair of DISC: Prod provides a service to repair the Swarm DISC in the event of data loss.
pin and re-upload of data: Hosts pin the data and re-upload it to its designated area upon receiving a recovery request.
prompt response on demand: If the requestor demands a prompt direct response, the host will post the missing chunk using a recovery response envelope along with the required postage stamp.

Recovery hosts

Recovery hosts are pinners who voluntarily provide pinned chunks for the purpose of recovery. These pinners have explicitly indicated their willingness to take on this task to the publisher and to have downloaded all the relevant chunks and have pinned them in their local instance.

To advertise their publication as globally pinned or repairable, publishers gather the overlay addresses of these volunteering recovery hosts. In fact, it is sufficient to collect just the prefixes of the overlay with a length greater than Swarm’s depth. These partial addresses are referred to as recovery targets.

Publishers will advertise the recovery targets for their content to data consumers via a feed called a recovery feed. Consumers can track this feed following a convention that constructs the topic using a simple sequential indexing scheme.

**Figure 5.3:** The process of notifying about a missing chunk is similar to that of targeted chunk delivery. Here, a downloader mines the identifier to match their own address, i.e. a self-notification. If downloader $D$ encounters a missing chunk (a request times out), they send a recovery request to one of several neighbourhoods where there is a possibility of finding the missing chunk. If the recovery request is successful, $D$ receives a response in the form of a single owner chunk that wraps the missing chunk. The chunk is also re-uploaded to the appropriate location within the network.

Recovery request

Once the recovery host’s overlay targets are revealed to the downloader node, the downloader should "prod" one of the recovery hosts by sending them a recovery request whenever a missing chunk is encountered. This instance of targeted chunk delivery (see 4.4.4) is a public unencrypted Trojan message that contains at least the address of the missing chunk (see Figure 5.4).

In order to create a recovery request, a downloader needs to (1) create the payload of the message (2) find a nonce that, when prepended to the payload, produces a content address that matches one of the recovery targets indicated by the publisher. The matching target indicates that push-syncing the chunk will send it to the recovery host’s neighbourhood associated with that target prefix.

If the targeted recovery host is online, they will receive the recovery request, extract the address of the missing chunk, retrieve the corresponding chunk from their locally pinned storage, and re-upload it to the network with a new postage stamp.

Recovery response envelope

A recovery response envelope is used to enable recovery hosts to promptly and directly respond to the originator of the recovery request, without incurring additional costs or computational burdens. It is a form of targeted chunk delivery response (see 4.4.4), which is an addressed envelope construct that remains neutral to the poster but fixed for the content. The request message includes the necessary components for prospective posters to create the valid targeted chunk delivery response: an identifier with a signature that verifies the association between the identifier and the missing chunk hash. The identifier is chosen so that the address of the single owner chunk (the hash of the ID with the owner account) falls into the requestor’s neighbourhood and is automatically delivered by the network’s push-sync protocol implementation.

**Figure 5.5:** Recovery response is a single owner chunk that wraps the missing chunk. Anyone in possession of the headers and the chunk data is able to construct a valid single owner chunk and send it to the downloader for free.

If the targeted recovery host is online, they receive the recovery request and extract the missing chunk address, identifier, and signature from the recovery response. After retrieving the corresponding chunk pinned in their local storage, they can proceed to create the recovery response. To create the recovery response, the recovery host combines the hash of the identifier and the payload hash to form the plain text of the signature. The signature received in the recovery request allows her to recover the public key of the requestor. Using this public key, they are able to calculate the requestor’s address and finally, by hashing the requestor’s address with the identifier, obtain the address of the single owner chunk. It is beneficial to attach a postage stamp to the request, which can be sent along with the recovery response. Requestors have the ability to cover the Swap costs associated with returning the chunk, compensating the global pinner. This scheme enables downloaders to intelligently cover the operating costs of nodes through micro-payments, thus ensuring the availability of data throughout the network.

5.3 Dream: deletion and immutable content

The increasing digitisation of data and the widespread use of cloud services have amplified concerns surrounding the privacy and control of personal information like never before. In response, regulators often impose requirements on removability without recognising that it is virtually impossible to make material once seen become unseen. However, the reality is that entities operating infrastructure that underpins digital publishing have control over the technology that serves the content and can implement "removal" by denying access. This centralised gate-keeping approach may seem appealing from a regulatory standpoint, as it can be thought of as an instrument of law enforcement. Although such interventions rarely address the breach of unrealistic privacy rights, the gate-keeper still provides a well-defined responsible party with the effective course of action: not serving censored content. While this gives the unwary a phony sense of security, it only exemplifies the larger issue of censorship: publishing platforms possess the technological means to filter content, and centralised control makes it more affordable to exert influence over the content. What starts out as sensible measures of content curation gradually transforms into extant censorship. This is all the more problematic with social platforms that have gained quasi-monopolistic status as a result of network effects. Due to the high costs associated with switching platforms, innocent content creators increasingly find themselves ’deplatformed’. Similarly, the ability to identify hosts and deny access to content through legal means gives powers to be the means to infringe on freedom of speech.

In the decentralised paradigm of web 3, there is no longer a single operating entity controlling the publishing platform or the hosting infrastructure. This renders the cost of censorship infeasible. And yet, the potential permanent exposure of personal data remains a significant concern for most individuals. Therefore, there is a need for novel solutions that can restore the sense of security that centralised gate-keepers purportedly represent.

5.3.1 Deletion and revoking access

First, notice that any reference to removal of information in the sense of erasing it from all physical storage devices is both unenforceable and impractical. Even the most rigorous data protection audits do not require the erasure of offending data from backup tapes. In general, the tacit assumption is that information ordered to be removed should become inaccessible through typical precedented methods of access.

In what follows, we formulate the strongest meaningful definition of deletion applicable to decentralised storage systems and offer a construction that implements it. Importantly, this approach is purely technical, focusing on the capabilities and costs of primary actors, rather than relying on procedural measures that impose obligations on intermediaries to respect the rights of primary actors.

The primary actors in this context are the uploaders who wish to share content by granting read access to a number of parties, called downloaders. Granting access is defined as providing a canonical reference to the content, allowing the system to eventually retrieve the complete information that is intended to be disclosed. Any party that is privileged to access this information is able to store, re-code, and potentially disseminate it. This provides a myriad of ways to make the content accessible at any later point in time, bypassing any process that would qualify as deletion or removal of access. There is, by definition, no protection possible against such adversity. As a consequence, any legally sound notion of deletion (retrospective revocation of access) is meant to be interpreted in a narrower sense: the viability to replay the same access method at a lower cost than the full cost of storing the content.¹⁴

Let us now define deletion as a scheme for uploading content with access revocation, meeting the following requirements:

Specialisation: The uploader is able to choose at the time of publishing a specialised construct¹⁵ allowing retrospective revocation of access.
Sovereignty: The uploader is the sovereign owner of the data and is in sole possession of the means to revoke access from any party that was previously granted access.¹⁶
Security: After the revocation of access, a grantee is unable to access the content using the same reference or any other cue shorter than the deleted content.¹⁷

Note that regularly uploaded content may be forgotten: if nobody pays for storing it and the content is not accessed frequently, the chunks constituting it will be garbage collected. However, chunks with expired postage stamps cannot be regarded as reliably deleted in order to satisfy the requirements of sovereignty and security.

5.3.2 Construction

The goal of this section is to arrive at a formal construction of a DISC-based revocable access model. We will restrict our scheme to chunks, the fundamental fixed-sized storage units of Swarm’s DISC model. The proposed dream construct implements a deletable content storage and access model that fulfills the requirements of specialisation, sovereignty, and security. The use of the word ’dream’ alludes to the somewhat unexpected finding that such a construct is even possible in the immutable DISC model. On top of this, as customary in Swarm, it serves as a mnemonic acronym, resolving to the 5 dream attributes expressing requirements of access control.

D – deniable: The dream key serves as a one-time pad for decryption. Since multiple content chunks (in fact any arbitrary content) can use the same dream pad, the key’s association to any content is plausibly deniable.
R – revocable: Access granted through dream keys is revocable. Revoking access from all parties, including oneself, is considered as deletion.
E – expirable: The scheme allows for one-time use, i.e., the key can only be retrieved once.
A – addressable: Access can be granted to a neighbourhood, where only clients operating a node within a particular an overlay address range are able to access the content.
M – malleable: The construct is resilient to churn and dynamic changes in network size; it is reusable across independent grantees and upgradeable.

The scheme is built on top of DISC’s APIs and can be implemented entirely as a second-layer solution. Despite its rich feature set, the scheme does not use complex cryptography, but instead leverages the interplay of various component subsystems.

Assume we have a pseudo-random deterministic function that generates a longer (e.g., chunk-sized = 4K) sequence $c$ from a key-sized (32 byte) generator $g$ .¹⁸

The central construct called a dream is a chunk-sized one time pad which acts as a decryption key for the deletable content. The dream chunk is collectively created by a set of nodes following a network protocol. Each node in the sequence of participating peers receives a piece of data and combines it as input with data from their reserve to produce an output, which is then sent to the neighbourhood of the next node in the chain. As long as each node in the chain performs the same calculation and forwards the same result, the same one-time pad can be generated, enabling the retrieval and reading of the deletable content.

The insight here is that retrieving a deletable chunk’s references involves calculations using a set of immutable chunks controlled by the uploader. The uploader’s ability to change this underlying set holds the key to providing the necessary mutability required by any notion of deletion.

Let $b$ be the batch ID (a 32-byte hash) of a postage batch owned by $U$ , and let $Chunks (γ, b, p)$ stand for all chunks stamped by $b$ at block $γ$ in the bucket designated by the pivot $p$ . Define $\bar{χ} (γ, b, p)$ as the chunk stamped by batch $b$ in the bucket designated by $p$ older than $γ$ whose address is closest (has minimal XOR distance) to pivot $p$ .

\begin{array}{rcl} \bar{χ} & : & Γ \times Batches \times Segment \mapsto Chunks \\ \bar{χ} (γ, b, p) & \overset{def}{=} & \underset{c \in Chunks (γ, b, p)}{\arg \min} χ (p, Address (c)) \end{array}

If batch $b$ is underutilised, a bucket designated by $p$ may not contain any chunks belonging to the batch bucket. As a result, there will not be a chunk closest to $p$ , rendering the $\bar{χ}$ function undefined in such cases.

Let us now define the OTP update function $Δ (γ, b)$ for batch ID and input address $p$ as follows:

\begin{array}{rcl} Δ & : & Γ \times Batches \mapsto Chunks \mapsto Chunks \\ Δ (γ, b) & : & Chunks \mapsto Chunks \\ Δ (γ, b) (c) & \overset{def}{=} & G [4 K] (Address (\bar{χ} (γ, b, c))) \end{array}

Since uniformity depth of batches is intended to be greater than the nodes’ storage depth, it is expected that all chunks in a batch bucket designated with $p$ are present in the reserve of every node within the neighbourhood designated by $p$ .

However, if Swarm grows and there are nodes whose storage depth is higher than the uniformity depth of the batch, then the neighbourhood designated by $p$ may not contain all the chunks in the bucket, thus compromising the computability of the OTP update function.

Nevertheless, if two conditions are met, namely: 1) the bucket of batch $b$ designated by $p$ is not empty and 2) the neighbourhoods include one or more buckets, then the update function is computable by any storer node within the neighbourhood designated by $p$ .

Since the update function can be applied to its own output, we can define the dream path as follows:

\begin{array}{rcl} Π (b, g) & \overset{def}{=} & c_{0}, \dots, c_{n} \in Chunks {n} \\ c_{i} & \overset{def}{=} & {\begin{cases} G [4 K] (g) & if i = 0 \\ Δ (b, c_{i - 1}) & otherwise \end{cases} \end{array}

The dream path function is a pseudo-random generator that is defined by finite recursion. A dream is a particular pairing of a generator and a one time-pad, which serve as the input and output of a dream path. Given a dream path of length $n$ and grantee overlay address $a$ , along with a batch $b$ with a uniformity depth of $d$ , the uploader needs to find the generator $g$ such that the $n$ -th chunk of the dream path falls within $a$ ’s neighbourhood (i.e., $PO (a, address (c_{n - 1})) \geq d$ ).

\begin{array}{rcl} dream (b, n, a) & \subset & Keys \times Chunks \\ ⟨ g, k ⟩ & \in & dream (b, n, a) \\ ⟺ \\ k = Π (b, g) [n] \land \\ PO (a, H_{bmt} (k)) \geq d \end{array}

The uploader is able to construct the dream pad, which also allows them to calculate $k$ given $g$ . Since $H (k)$ is uniform, the chance of $PO (a, H (k)) \geq d$ is 1 in $2^{d}$ .

Now we can turn to the definition of a dream, which is a network protocol based access method that is deniable, revocable, expirable, addressable, and malleable. In order for downloaders to calculate the dream pad, they must rely on the network, where each recursive step is calculated by a node in the neighbourhood designated by the respective input chunk’s address.

In order to guarantee the correct termination, the following criteria must be fulfilled:

all buckets of batch $b$ designated by $p_{0}, \dots, p_{n - 1}$ must be non-empty
the uniformity depth of the batch must remain higher than the storage depth of nodes in the neighbourhoods designated by $p_{0}, \dots, p_{n - 1}$ .
the output of each step, produced by a node in the neighbourhood designated by $p_{i}$ , must be sent to the neighbourhood designated by $p_{i + 1}$ .
nodes in the neighbourhoods along each hop of the dream path (designated by $p_{0}, \dots, p_{n - 1}$ ) must be incentivised to compute the OTP update and forward the resulting output chunk to the next neighbourhood.

Let us define a network protocol called dream. Participants in the protocol listen to single owner chunks that wrap the input. We assume that they extract the batch identifier $b$ , and the payload CAC $c$ as parameters to the OTP update function. They calculate the output pad, wrap it as a dream chunk, and send it to the network towards the address of the output chunk. This allows the destination neighbourhood to calculate the next step. If the protocol is followed up to $n$ steps, then the target node receives $k = c (n)$ at address $a$ .

We now turn to the construction of dream chunks. Uploader $U$ wishes to grant downloader $D$ (at overlay address $a$ ) revocable access to content chunk $C$ . $U$ chooses a postage batch $b$ it owns, ensuring that it is not completely filled. Additionally, $U$ chooses a step-count $n$ and a depth $d$ . $U$ creates a dream generator $⟨ g, k ⟩ \in dream (b, d, n, a)$ , then calculates the "ciphertext" $C^{'} = C ⊻ k$ and uploads it to Swarm, obtaining $r = H (C^{'})$ as parity reference. Now $U$ creates the dream reference as $ref (C) = ⟨ r, b, g ⟩$ which can be given to the downloader grantee $D$ .¹⁹

5.3.3 Correctness, security and privacy

Retrieval

$D$ , in possession of a dream chunk reference as $⟨ r, b, g ⟩$ calculated by $U$ as $ref (C)$ , constructs $p = G [4 K] (g)$ , wraps it as a dream chunk, and sends it to Swarm. When $D$ it receives the dream chunk for $b$ , it extracts payload $k$ .

$D$ retrieves the parity chunk $C^{'}$ using reference $r$ and then decodes $C = C^{'} ⊻ k$ . The retrieval process is trivially correct as long as:

1.: The parity chunk $C^{'}$ is retrievable via normal retrieval methods.
2.: The dream protocol is followed by cooperating nodes.
3.: The batch bucket bottom remains unchanged for the neighbourhoods along the dream path.

Deletion

We are now turning to access revocation, which is equivalent to deleting content by revoking all access.

Uploader $U$ had granted $D$ (at address $a$ ) access to $C$ through the dream reference $⟨ r, b, g ⟩$ . $U$ revokes $D$ ’s access by uploading extra chunks to batch $b$ such that $\bar{χ}$ changes.

As long as there is at least one honest neighbourhood walked by the protocol, such that the nearest chunk to pivot $p$ from batch $b$ changes, downloader $D$ will no longer be able to retrieve content $C$ .

To prove this, first let us assume that there is a bucket designated by some $p_{i}$ on the dream path such that the $\bar{χ}$ for the bucket has changed since the uploader constructed the dream. When the participating node in the neighbourhood designated by $p_{i}$ calculates the OTP update function, the result will be completely different and the dream chain will not terminate.

Privacy

The reference does not leak any information about the step-count or the neighbourhoods involved. Neither are the participants in the protocol aware of their position in the chain or any details about the other neighbourhoods, except for the immediate next one to which they are push-syncing their chunk.

The construction of the dream reference is deniable. Beside our sensitive content $C$ , let us consider $A$ , any uncontroversial content chunk. When producing $C^{'}$ , the owner also produces $A^{'} = A ⊻ k$ and uploads it. When asked about $k$ , producing $A$ makes the denial of other content, including $C$ , more plausible.

Resolution of attacks

A powerful adversary could potentially infiltrate every neighborhood of Swarm and archive all information that has ever been uploaded (even without being able to decipher it). They could also keep logs of what has been uploaded in what order, which would allow it to serve up deleted content on demand. But there is a huge price on such indiscriminate archiving of all Swarm’s content, and that is the only way to reliably defeat the dream construction.

We now turn to the discussion how to calibrate the step-count in relation to the security model. Let us assume a network-wide neighbourhood infiltration rate of $\frac{1}{2}$ , meaning that half of the neighbourhoods in the network is assumed to be malicious and colluding.

When access is revoked, the owner uploads new chunks in each neighbourhood along the dream path. Given a particular dream chain, however, if even a single neighbourhood on the dream path is honest, they will respect the newly arrived chunks and divert the dream path, preventing it from terminating with the grantee.

Thus, for a breach of access to happen, all neighbourhoods must be malicious. In our security model, a neighbourhood is malicious with uniform and independent probability. For an overall infiltration rate of 1 out of $k$ , the chance of all neighbourhoods on a given random dream path being malicious is $k^{- n}$ . For a security requirement of success rate of $σ$ "nines", where the error rate is less than $10^{- σ}$ , we can formulate the requirement as

\frac{1}{k^{n}} < \frac{1}{10^{- σ}}

Now, expressing $k$ as $10^{κ}$ , taking the logarithm of both sides and multiplying by $- 1$ , we get

n > \frac{σ}{κ}

With one in every 10 neighbourhoods being malicious, the dream path must have as many hops as the number of nines expressing the success rate.²⁰