Earendil: an uncensorable decentralized network (1/3)

The coolest thing I'm currently working on at Mel is probably Earendil, a prototype decentralized, type-II censorship resistant communication and payment network, which will be a foundational building block in Mel's off-chain composable ecosystem.

Functionally, Earendil lets any two computers on the internet cheaply and privately send each other either data or money — it's essentially "Tor plus Lightning Network". But it has a very distinct design goal: strong type-II censorship resistance, or ban resistance. Not only should Earendil be unable to block particular users or payments, it attempts to resist attempts by external attackers to shut down access entirely. In fact, Earendil is supposed to work even if an adversary like the Great Firewall of China controls the entire Internet.

But as I've previously touched on, that's really hard. Current approaches to ban resistance assume some trusted operator from the "free world" helping users evade local censors, which doesn't work for decentralized networks that don't trust the security of any part of the global Internet.

In a series of three blogposts, I will try to sketch out Earendil's attempt at cracking decentralized ban-resistance. Technical descriptions can be found the Earendil docs — these posts are more of an attempt to explain the logic behind the various design decisions.

For this particular post, we'll focus on the network architecture of Earendil, which is a composition of modern protocol obfuscation with a confederal topology very loosely inspired by both Tor-like onion routers and Freenet-like "friend-to-friend" networks.

Future posts will discuss the incentive model of Earendil, which is based on micropayments over a Mel-based payment channel network, as well as the vast field of use cases a general ban-resistant transport enables within the Mel ecosystem.

A "toy" example: gossip

First off, is it even possible to make a decentralized network ban-resistant? None of the usual suspects — Tor, I2P, Nym, cryptocurrencies — has decentralized ban resistance out of the box.

Fortunately, there actually is a sort of decentralized network that's quite easy to make ban-resistant — a friend-to-friend gossip network:

• Every user has a few trusted friends, most of which are honest
• Users do not know anything about the network other than their immediate friends
• Users join the network by being manually invited by one or more friends
• Anyone can broadcast a message to all participants by sending it to all their friends. Every user is programmed to repeat any incoming messages to all their friends, ensuring that all messages are gossipped to all participants.

Making this network ban-resistant only requires one thing: every user must have some ban-resistant way to reach their immediate friends. And as long as enough friend-to-friend connections stay online, the censor cannot stop broadcast connectivity.

"Pairwise" ban resistance is easier than building a global ban-resistant network — even in extreme environments like a totalitarian state with no Internet access, we often still have ban-resistant friend-to-friend channels (e.g. "sneakernet") that allow "gossip" to spread.

In fact, it's straightforward to implement trusted-friend ban resistance in cyberspace using modern obfuscated protocols. Typically in these protocols, there's some sort of connection secret that allows trusted clients to unobservably connect to a server, but if this secret ever leaks, the obfuscation would fail. For instance, if we use the ScrambleSuit obfuscation protocol:

• Every user knows the IP addresses and ScrambleSuit "cookies" of a few trusted friends
• Users do not know the connection information of anyone else
• Users are invited by a trusted friend giving them their address and cookie
• As long as enough friend-to-friend links remain undiscovered that the network remains connected, gossip cannot be stopped

This would let us construct a decentralized, ban-resistant network that only supports broadcasting messages.

Fast routing

But a network that only supports broadcast isn't very useful outside of already broadcast-based applications like blockchains. With only broadcast, user-to-user communication would require very inefficiently broadcasting every message and having users ignore all messages not addressed to them.

To avoid that, we need to efficiently route a message from one user to another without spamming it to everyone.

When I was designing Earendil, my first attempt was to turn to small-world routing. There's quite a bit of prior work on routing messages in an unstructured network where every node only knows their immediate neighbors. There is even a paper by the developers of Freenet that tackles exactly the friend-to-friend situation where nobody is allowed to learn about any non-friends at all.

Unfortunately, small-world routing performs poorly compared to traditional peer-to-peer routing algorithms (e.g. classical DHTs) that don't try to hide nodes from non-friends. Intuitively, traditional algorithms organize all the nodes into a network-wide structure that enables packets to quickly "find their way" to the right destination, while small-world routing needs the packet to somewhat blindly stumble across the network, hoping to find the destination. The system outlined in the Freenet paper, for instance, achieves a meager 50-80% success rate for routing messages to the right destination, which is difficult to accept for a general-purpose communication channel.

At this point, I realized that we didn't need a strict friend-to-friend network for ban resistance. As long as only friends of a node knew the secret connection information that must not leak to the censor (e.g. IP address and ScrambleSuit cookie), it's fine to reveal other information about the network to help routing.

In particular, efficient routing is possible if every node knows the entire node graph: what nodes are there (identified by public key or similar opaque identifier), as well as which nodes are friends of which nodes, which itself can be easily distributed through gossip.

Sending a packet from Alice to Zachary then simply involves:

1. Alice finds the shortest path from her to Zachary in the network, by running something like Dijkstra's algorithm on the relay graph. She discovers it's "Alice, Bob, Charlie, ... , Yvonne, Zachary".
2. Alice sending a packet to Bob on the path after herself, with a header attached that contains the path "Charlie, ...., Zachary".
3. Every node forwards the packet to the first node listed in the header and  "peels off" the first element of the header. For example, when Charlie receives the message, it'll contain the header "David, Emily, Frank, ..., Zachary", so Charlie forwards to David the same message with the header "Emily, Frank, ..."
4. Zachary eventually receives the message.

Earendil uses a variant of this very system, which uses onion routing to actually hide everything but the next hop to every intermediary.

Confederal scaling

One limitation is that the node graph cannot become too large. If we have more than something around 100,000 nodes, routing and especially gossipping the graph itself would slow down.

But we certainly wish to scale beyond 100,000 users. This is done by embracing a two-tier, confederal architecture:

• We distinguish relays, which are larger, high-uptime servers providing infrastructure for other users by forwarding messages, from clients which are lightweight and can only be the ultimate sender and receiver of messages. We assume that the vast majority of users are clients.
• We only gossip the relay graph: which relays there are, and relay-relay "friendships". Relay-client friendships are not gossipped.
• The routing algorithm outlined above would then allow a client to route a packet, one-way, to a relay. We use a trick called "reply blocks" (borrowed from systems like I2P and Sphinx) to enable relays to send messages back to clients. A client can then communicate with another client by appointing a "rendezvous" relay to forward messages between them.

As an aside, 100,000 is certainly enough relays to route any reasonably sized network — if we assume each has a 1 Gbps network link (modest for servers), Earendil will have a total capacity around 100 Tbps, around 10% of the total international bandwidth usage of the Internet.

To be continued...