Protocol: Anonymous Communication requirements and brief update

Since last week we’ve started sketching out a requirements doc for anonymous communication protocol as one of the layers. See below for the latest there, and please provide feedback. We also met with Web3 Foundation and Validity Labs, who have been looking into creating such a protocol themselves, probably based on a mixnet style approach. We’ll be working more closely with them as a joint initiative to specify requirements, threat models and components, initially at

Anonymous Communication Protocol requirements


NOTE: This whole document is tentative. Some suggestions might be misguided, naive or plain wrong. All errors in it belong to Oskar.

The purpose of an anonymous communication (AC) protocol is to ensure metadata isn’t leaked when messages are communicated between peers. It deals with how messages are transported, and not what is in them.

An overarching principle is to keep things as simple as possible, and try to factor out subproblems to separate layers as much as possible. When in doubt, leave it out.


Metadata that we want to protect are:

1. Sender Anonymity (who sent a message?)
2. Receiver Anonymity (who read a message?)
3. Sender-Receiver Unlinkability (who is talking to whom?)

Primary consideration in threat model is:

  • Global Passive Adversary resistant (GPA, insight into whole network)

Some consideration should also be given to a global active attacker (GAA), in additional to local/remote attacks. For example, it might be reasonable to detect GAA, but not be fully GAA resistant. A more complete threat model with respect to capabilities should be provided, see Briar for example.

Participation Anonymity is less important. This is most likely to be a factor in terms of Censorship Resistance (deep packet inspection, traffic morphing), which is important but currently not of primary concern for this specific protocol. This may change depending on protocol layering.

(Anonymous replies is also less important, but it’s a nice to have. E.g. Alice sends to Bob and Bob replies w/o know anything about who Alice is).

The Anonymity Trilemma [XXX] states that there’s a fundamental trade-off between Strong Anonymity on one hand and Low Latency / Low Bandwidth Overhead on the other. Additionally there’s a forth dimension, User Distribution, whereby an increased number of users in the system increases the anonymity set.

This design consideration, in addition to general user adoption concerns, has two implications:

4. Reasonable Latency (<5s, to allow for instant messaging (see XXX, Nielsen usability))
5. Reasonable Bandwidth (not specified, mobile data plan in undeveloped countries)

Since The User of the protocol could equally be someone with a limited data plan as someone publishing sensitive information under a nom de plume, it is desirable that the protocol accommodates the following property:

6. Adaptable Anonymity (adjustable resource consumption)

One could imagine a message being sent/received based on three parameters: chosen anonymity set, latency and bandwidth. The feasability of this approach is untested, and may differ for sender, receiver, and unlinkability. As an example, PSS provides a form of sliding Receiver Anonymity scale using partial addressing.

Update: this might be a misguided notion, see Signal’s design philosophy, point 1 and 3.

Additionally, the protocol should be:

7. Scalable (up to, say, ~1M active nodes)

Resource consumption should grow gracefully with the number of users. I.e. the guarantees around latency, bandwidth etc should be provided even up to ~1M nodes. Counterexamples: naive DC-nets and Whisper, which both exhibit quadratic scaling behavior. Another counter example are mixnetworks with latency on the order of minutes as you get up to to a sizable network size.

There may be more specific throughput requirements, but this underspecified for now.

Finally, this should be a peer-to-peer decentralized protocol:

8. No Specialized Services (pure p2p)

Any node should be able to do any job in the system. A specific node may choose to only operate with a subset of capabilities (say, for resource consumption reasons), but this is up to that node. Example: light node operation, taking advantage of Desktop/server different performance profile compared to mobile (intermittent connectivity, bandwidth).

Things that are explicitly out of scope

  • Trust Establishment - provenance of long term keys to some known identity
  • Conversational Security - authentication, confidentiality, integrity, perfect
    forward secrecy.

Additionally, see below for other things that may be out of scope at this layer.


What about Incentives?

The Protocol will be used in conjunction with Ethereum and similar technologies. There’s also a strong need for incentive-compatible designs. This means it is useful to consider incentives and payment mechanisms as the protocol layer. However, an ideal protocol suite should be layered and have a clear separation of concern. This means there’s a simple design with minimal dependencies. As inspiration, see Bittorrent economics paper (pdf), which is a separate protocol layer that people can choose to use or not to get better quality of service (request and choking).

What about Message Reliability?

The protocol should do Best Effort Delivery. Reliable Delivery can be provided on top, similar to TCP/IP (or BSP/BTP for Briar), to accommodate things like:

  • Guaranteed Message Delivery
  • Message Ordering
  • And possibly: Asynchronous Messaging (some protocols deal with it at this layer, so this may or may not be desirable)

Depending on the specifics of the reliability mechanism, throughput etc, this may have consequences for the above Reasonable Latency requirement. The Reasonable Latency requirement outlined above is for End to End messaging.

How to deal with Network Spam?

  • One approach is to use a Friend-to-Friend (F2F) network. This is what Briar and Secure Scuttlebutt (SSB) does.
  • For open DHT-based, another approach is to rely on proof of work like Whisper.
    This isn’t very practical for mobile / resource restricted devices, and appears to have limited usability.
  • More approaches are likely possibly, such as traditional rate limiting, basic peer reputation, payments, etc.
  • Global network attacks more relevant here than a specific node. What does this imply for a DHT?

How to deal with Asynchronous Messaging?

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

Do these requirements make sense? Is something missing or overly specified? Also see

1 Like

Just a side note: this isn’t really feasible on mobile. If we want to target mobile, we should consider everyone being mostly offline, with occasional very short sparks of online activity.