Figure out how to (and whether to) deal with asynchronous messaging

[oskarth]

Does asynchronous messaging fit at this protocol layer? If it does, how should it be provided for? Study prior art and trade-offs.

Store-and-forward a la Whisper mailservers have a bunch of empirical drawbacks:

• requires high availability from individual nodes
• privileged specialized node
• trusted relationship leaking metadata / spam surface (direct TCP connection)
• unclear messaging guarantees (masquerades as Reliable Delivery but often really meh Best Effort)

Distributed State solutions would be worth looking into.

Raw notes:

• One approach is to punt this problem to data sync layer. Not clear that it is a necessary component of AC layer.
• Another example is Briar requiring two entities to both be online.
• One idea is to use Aggregation Points (Xolotl, lake mixnet) as providers similar to Loopix, presumably with less HA guarantees.

[robertkiel]

I would say that asynchronous messaging fits very well at this protocol layer because when combining messaging with an incentivation layer we can get this nearly for free.

Pros for asynchronous messaging through incentivations

• Support for asynchronous messaging would make this protocol applicable for decentralised applications that run on peoples smartphones / smartwatches / IoT devices
• Binding incentivations to (successful) forwarding of messages would allow some delivery guarantees like "Money is paid to the relayers if, and only if, the message reached its destination"

Cons

• Messaging won't be for free

[oskarth]

Contrasting naive mailservers vs my understanding of multiple aggregation points idea.

One way to provide async mesaging is to have "relay nodes" acts as mailboxes for end nodes. A naive solution to this would be Whisper's mail servers. There are a few problems with this approach:

1. Not decentralized - it's a single point of failure and requires constant uptime aka High Availability.
2. Not reliable. It gives the illusion of reliability, but lack of acks and network issues means inconsistent state, etc.
3. Not privacy preserving - direct TCP connection to receiver.
4. Operator overhead. Because mailserver is essentially an ad hoc database, node operator needs to care about things like disk space/health, etc.
5. Not incentivized. There's no reason to run a mailserver, and there are no good ways of measuring what it means to do so honestly.

All of these issues, and possibly more, are things we have empirically run into at Status. Exploring Multiple Aggregation points idea (from https://github.com/burdges/lake/blob/master/Xolotl/papers/Xolotl-1-intro.tex), which expand Loopix centralized provider idea:

1. Receiver can select multiple aggregation points for replication.
2. Acks are partially provided for at provider level and feedback is given to sender. However, acks are still not end-to-end, likely leading to problems. This can be mitigated by employing layers of acks (is this really a good idea?). See https://en.wikipedia.org/wiki/End-to-end_principle
3. By employing SURBs (single-use reply blocks) metadata isn't leaked from receiver.
4. Similar concerns. Using decentralized storage primitives like IPFS/Swarm might be desirable, but unclear what this would look like.
5. TBD - lots of considerations.

[burdges]

Contrasting naive mailservers vs my understanding of multiple aggregation points idea.

One way to provide async mesaging is to have "relay nodes" acts as mailboxes for end nodes. A naive solution to this would be Whisper's mail servers. There are a few problems with this approach:

As I said on riot, we can use something like this as a milestone, but doing so requires distributing SURBs directly from receivers to senders, so their connections can be broken, and they must use the contact discovery process for reconnection. We'll eventually want flexibility in the contact discovery layer, so we should move to aggregation points and contact points before doing that.

Not decentralized - it's a single point of failure and requires constant uptime aka High Availability.
Not reliable. It gives the illusion of reliability, but lack of acks and network issues means inconsistent state, etc.

Agreed.

Not privacy preserving - direct TCP connection to receiver.

Yes, there are more attacks but if you still use SURBs then it's not the worst. If you do not use SURBs but instead share your own node id and the list of nodes to whom you connect then yes that kinda sucks, but again maybe that helps as a development milestone.

Operator overhead. Because mailserver is essentially an ad hoc database, node operator needs to care about things like disk space/health, etc.

A priori, aggregation points sound less disk heavy than email servers because users should delete messages they received successfully when supplying more SURBs. We might make this heavy again for multiple device support though. I donno if devices could sync among themselves like riot/matrix. Aggregation points could expire even unreceived messages after some long time.

Not incentivized. There's no reason to run a mailserver, and there are no good ways of measuring what it means to do so honestly.

Right, we can reward node operators with "secret shopper" cover traffic built by staked node using VRFs, but rewarding storage over an extended period sounds much harder.

All this applies to aggregation points too though, so I'll create a new issue on rewarding aggregation points.

All of these issues, and possibly more, are things we have empirically run into at Status. Exploring Multiple Aggregation points idea (from https://github.com/burdges/lake/blob/master/Xolotl/papers/Xolotl-1-intro.tex), which expand Loopix centralized provider idea:

As you see, I'm strongly in favor of asynchronous messaging / store-and-forward. :)

Receiver can select multiple aggregation points for replication.

Yes, multiple aggregation points improve our reliability over node availability. Importantly, receivers can change their aggregation points without even telling their contacts, just giving different SURBs to their contact points, which lets them respond to changes in aggregation point reliability.

Acks are partially provided for at provider level and feedback is given to sender. However, acks are still not end-to-end, likely leading to problems. This can be mitigated by employing layers of acks (is this really a good idea?). See https://en.wikipedia.org/wiki/End-to-end_principle

I think store-and-forward needs these kind of "middle acks". I'm fine with acks from the recipient to sender too, but maybe I'd use SURBs embedded in the message for those, and other quick replies, not another message.

Right now. messagers like Signal, WhatsApp, etc. provide both acks with their two checkmarks, but using SURBs embedded in the message will make the second "received ack" checkmark less reliable for sendrs who go offline lots.

Similar concerns. Using decentralized storage primitives like IPFS/Swarm might be desirable, but unclear what this would look like.

We'll want an attachment scheme that works inside the mixnet, but once attachments get too large they should go into a decentralized storage layer, along with a warning to savvy users that security is reduced.

[oskarth]

To clarify above comment, the point of using Whisper's naive mailserver example was not to suggest it as a solution, but to showcase how terrible it is and to discover how something like your aggregation points might solve some of the issues. The third alternative, which I probably should've made more explicit, is to not deal with async state in communication protocol, and instead punt this problem to a different layer.

---

General hypothesis: storage and communication are separate (and hard) things, and the more we can disentangle them and reuse existing solutions, the better. Here's a sketch / PoC for what async messaging as a separate layer/component might look like (as a thought experiment):

Use case: Alice and Bob chatting, one goes offline, privacy preserving.

Using Swarm Feeds (https://swarm-guide.readthedocs.io/en/latest/usage.html#feeds) as an example. Other solutions, such as IPFS etc, are also possible. What they have in common is that they focus on decentralized, robust, (incentivized) storage, as opposed to communication (what this protocol is about). A Swarm feeds is owned and writeable by a keypair, and readable by anyone. They have a topic attached to them.

In its most naive form, Alice would have a topic 'alice-bob'. When Alice goes offline, Bob would request this feed. Of course, this is not privacy preserving at all. If instead the topic is kept a secret, one could imagine a ratcheting-like scheme where Alice keeps track of Bob's last ACKed topic. When Bob comes online, he would query Alice's 'alice-bob-secret-topic-x' through the mixnet. This appears to me (probably wrong) to be privacy-preserving (sender/receiver anonymity, unlinkability). It would not provide participant anonymity for Alice, but it isn't clear to me that this is a requirement.

What this would look like for something like group chat or public chat is unclear (Nucypher proxy-rencryption might be interesting here, as well as Tribler's Dispersy BloomFilter sync). This would also enable things like message history (messages are merkle trees and can be queried by timestamp) and trivial multidevice sync.

[cammellos]

The third alternative, which I probably should've made more explicit, is to not deal with async state in communication protocol, and instead punt this problem to a different layer.

Just a minor note, if that is the decision we go for, it is important that the layer does not heavily rely on e2e synchronous communication (i.e. some form of handshake, time based sessions, etc) otherwise it would possibly make building asynchronous communications on top (or below) quite complicated.

[burdges]

I opened a separate issue on feeds in #14 which describes doing feeds with a mixnet. We should glance over academic work that designs anonymous publish-subscribe systems though.