# 1. Introduction

After a round of discussions on the [Waku-Codex FURPS](https://github.com/waku-org/pm/pull/328/files), we can now attempt at describing a strawman approach for further discussion.

Waku is, at its core, a low-throughput, broadcast-like, best-effort ephemeral message routing protocol offering strong privacy guarantees such as publisher and receiver anonimity over large groups ($k$-anonimity). At its simplest, nodes in Waku -- named relays -- self-organize into a randomized mesh and gossip over it.

The gist of it is simple: if messages are always broadcast over a group with sender and receiver obscured, then no node in the network -- with the exception of the sender and the receiver -- can tell which members of the group posted the message, or which ones were meant to receive it. Adversaries would need to be able to observe the entire group and their message traffic to identify senders, and receivers are impossible to identify[^1]. The larger the group, the harder this gets.

**Delay tolerance.** _Ephemeral and best effort_ means that relays will by default keep a message around for a very limited time; i.e., as little as the underlying gossipsub[^2] implementation was configured to keep them. If peers join the routing mesh after a relay is done forwarding a message; e.g., more than tens of minutes after the message is first received by the relay, then they will likely not be able to get it.

Because purely ephemeral messages are of limited usefulness, a lot of the extensions made to Waku over the years are meant to improve delay tolerance; i.e., the ability of the network to tolerate long delays in routing while ensuring delivery. We will discuss those, their shortcomings, and how Codex might help to address those in in Sec 2.

**Message size.** Because Waku is a broadcast channel, transmitting large files requires significant resources. This is particularly true in chat apps, where every single piece of content exchanged between pairs of communicating parties would be retransmitted across the entire network. For that reason, publish rates in Waku are severely constrained[^9]: publish rates within a shard are constrained to $266$ messages-per-second, for the entire shard, and maximum message sizes are of $150\text{kB}$, but Waku expects a $4\text{kB}$ average message size to make things work.

This means that the total content capacity for a shard is about $6\text{MBps}$. Needless to say, this would get used up very quickly if applications started to chunk large content as messages and use Waku to disseminate them. A Waku-based chat app like Status, therefore, requires a separate channel for transmitting such types of content. In Section 3, we will discuss how Codex could be used to address this problem, together with shortcomings and open questions.

# 2. Improving Delay Tolerance

Waku has been extended in different ways to overcome routing failures under increased delays. Some of these extensions are done at the app-level; i.e., above Waku, while others have been added to the routing layer itself. We discuss those next.

## 2.1. Existing Mechanisms

**MVDS.[^3]** MVDS is an application-level protocol used by Status to ensure end-to-end chat message delivery. It is _application level_ because it does not operate at the Waku routing layer - it is implemented on top of it.

MVDS assumes multicast communication in which a sender $p$ wishes to reliably communicate a set of messages $M = \{m_1, \cdots, m_k\}$ to a set of receivers $R = \{r_1, \cdots, r_s\}$.

MVDS assumes that:

1. $p$ knows the pseudonymns of each of the recipients in $R$;
2. $p$ maintains a message cache $C \subseteq M$ in which it keeps all messages in $M$ until it is sure that every recipient in $R$ has received it.

It then works as a standard data exchange protocol over Waku's broadcast channel. MVDS works in epochs[^4]. At every epoch[^5], $s$ broadcasts $M$ using Waku. Presumably, the recipients in $R$ can identify such messages. Each recipient, then, upon receiving the message, sends a batched `ACK` message containing the message identifiers in $M$ it has not seen so far.

Since the `ACK` messages are sent over Waku, those are also broadcast. This means that if the broadcast group has size $k$, the number of messages that needs to be passed around is $O(k|M|)$, as opposed to $O(k)$ for a simple two-phase like protocol.

The amount of traffic will be larger if nodes in $R$ are not all online, as MVDS will apparently just keep retransmitting. This is obviously not an efficient protocol, and expecting to implement long-history message synchronization in a chat app with something like this would not be reasonable.

**Store Node Protocol.** A Waku network might contain _store nodes_[^6], which act by actively listening to messages in the network and placing them into a local database, which can then be used to service queries. Store nodes run a synchronization protocol with other storage nodes to make sure gaps due to storage node outage or routing failures are backfilled.

The exact method with which other nodes in the network recover potentially lost messages from store nodes is left somewhat open, but one option is running periodic, time-ranged queries[^7]. Store nodes are _not_ meant for long-term storage, however, and their operation is currently centralized.

**Scalable Data Sync (SDS).** SDS can be seen as an evolution over MVDS. It adds a Lamport timestamp and a short causal history to each message so that a receiving node can figure out, transitively, if it is missing causally preceding messages. Receivers can then _ask_ for the missing bits, which is more efficient than the previous ACK-based retransmission of MVDS. It also guarantees causal ordering, which might be useful for things like chat apps.

Since detecting missing messages requires knowledge about what the tip of a causal chain is, nodes periodically broadcast empty "sync" messages which contain only causal information. SDS can in principle allow nodes to request messages to one another, or directly to store nodes. It does not, however, in itself solve the problem of persistent longer-term storage for applications.

I also suspect SDS would probably be slow when synchronizing large message histories given the need to transitively follow the happens-before relationship and issue history queries to nodes as one traverses the causal graph breadth-first.

## 2.2. Codex as Archival Nodes

Although store nodes could be scaled or decentralized, keeping a large decentralized fleet of nodes synchronized with store sync[^8] could turn out to be expensive. Store sync is also not meant for whole-database synchronization, but for papering over transient routing faults or short store node outages.

Our experience building Codex also reveals that efficently and durably storing mutable data is a lot harder than doing so with static data. Since messages are immutable and the set of messages in a Waku network can be seen as an add-only set, one can envision an archival service which stores immutable slices of that set by means of a simple "pack-and-publish" archival service.

The idea is depicted in Fig. 1: we run an "archival" app together with a local Waku and a local Codex node. The archiver uses the Waku node to listen in on the messages in the network, and buffers them locally. Periodically, or when a given set size is met, messages can be tarred into an archive and published to the local Codex node. The archival app then publishes a "new archival" message onto a special "archival" topic, and the nodes interested in doing the archiving download it.

<div style="display: flex; justify-content: space-around; align-items: center">
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/rkMXbzKweg.png" width=80$/>
<p>(a) Archival app node.</p>
</div>
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/HkX-bfFwge.png" width=80%/>
<p>(b) Basic archival flow.</p>
</div>
</div>

**Figure 1.** Archival service.

### Open Issues

**Archivist election.** Publishing an archive is in some ways similar to building a block. If we want some level of redundancy in archivers, then we need to appoint an "archivist". This could be done manually, or we could have some self-organising way of doing it, like slicing time into loosely-synchronized epochs and appointing an archivist per epoch (blockchain-style).

If two archivists end up publishing an archive for the same epoch, other archival nodes can simply download the archive that got to them first. Since this is not a blockchain, it would be okay to have different archival holders with different archives for the same epoch.

**Archival incentives.** If we assume honest but rational archival nodes, those need to be incentivised or they might not download, store, or serve data. If we consider dishonest archival nodes, then it would be easy for a rogue archivist to simply withhold all the messages for an epoch and poison the whole archive, like a block proposer in a blockchain. A mechanism for archival integrity is likely required here.

Another option would be allowing each archival node create its own view of the archive for an epoch, and then allow nodes to download those as they see fit. This would reduce bandwidth efficiency, as you can no longer swarm, but would allow suspicious historical bundles to be discarded and re-downloaded from a separate node.

**Efficiency.** Replication is wasteful. Erasure coding and parititioning can lead to much higher space efficiency than full replication at equivalent fault tolerance (assuming random decorrelated faults). This might be a useful optimization. Repair would likely be required in these cases for underrepresented partitions, as would a mechanism for estimating partition availability in the network. Under churn, however, active repair can become intractable.

**Privacy.** Unless we change approach, archival nodes can easily identify one another during the download process. App clients restoring historical information will also be identified by archival nodes when they connect to download it. Nodes serving DHT lookups can identify the node looking content up, and might eventually figure out that those are archival lookups. While libp2p does support mixnets, it is unclear whether this would present a usable choice in terms of performance and reliability.

# 3. Transmitting Larger Files

As with message routing, large file transfer has an easy case, when both sender and receivers are online, and a harder case, when which they are not.

**When both sender and receiver are online.** A simple way to use Codex for transmitting large files in this case is by uploading a file to the sender's local node and then providing the file's CID to the intended recipients, via Waku. They can then download the file directly from the sender via Codex. This is akin to using Codex as a replacement to a direct TCP connection.

**When sender and receivers are not online at the same time.** In this case, the involvement of a third-party becomes mandatory. For groups and communities, we might be able to disseminate the content by just applying the same strategy as before, as long as the sender and _some_ receiver are online at the same time, and we can assume that receivers are willing to provide the content to one another.

Since Waku meshes are randomized, if even a small percentage of group peers is online at a time, we can still expect the message and the content to propagate as the group should be temporally connected -- assuming no recipient deletes the content from their local nodes. Of course, overlap between pairs of online peers must be large enough so that the transfer can actually complete.

If we cannot expect sender and receivers to be temporally connected over a group, then we must involve third-parties to make that happen, and incentivizing such parties becomes key.

### Open Issues

**Third-party incentivization.** Although we can assume groups might be incentivized to propagate content, if there are no uptime incentives for nodes then delivery is not guaranteed. Indeed, group size and availability characteristics ultimately decide whether delivery is successful or not, and this is beyond the control of the system.

Incentives to be online and to provide the content are therefore required to increase chances of success, with some sort of reputation or slashing system likely required, particularly in the case in which we must involve third parties that do not belong to the group of recipients.

**Scalability.** In Codex, each node holding a piece of content $c$ needs to advertise itself as a provider for $c$ in the DHT. This means load in the DHT increases as the number of indexed pieces of content in the network increases. WhatsApp users, for instance, share almost $7$ billion photos a day[^11].

[^1]: Except for very small groups (e.g. size $2$), in which identifying the sender automatically identifies the receiver.
[^2]: https://github.com/libp2p/specs/blob/master/pubsub/gossipsub/gossipsub-v1.0.md
[^3]: https://rfc.vac.dev/vac/2/mvds
[^4]: I'm assuming epochs are not synchronized across nodes but that is not stated in the spec.
[^5]: Assuming MVDS in _batch mode_.
[^6]: https://docs.waku.org/guides/js-waku/store-retrieve-messages
[^7]: https://github.com/waku-org/specs/blob/master/standards/application/p2p-reliability.md#store-based-reliability
[^8]:
[^9]: https://docs.waku.org/research/research-and-studies/capped-bandwidth
[^10]: DHT scaling formulations: https://hackmd.io/tzafQHRgRfKcKAfQ-xBm3Q
[^11]: https://www.cooby.co/en/post/whatsapp-statistics