The sideways view

Imagine a world where some pairs of whom want to talk to each other—each person has a unique n-bit identity (e.g. 64-bit strings), and wants to send a message to someone with a particular identity. The number of people is ballpark exp(n), I’m imagining ~10 billion.

We’ll start with a graph G, where people know how to talk to their neighbors and each vertex has degree poly(n). For simplicity, I’ll assume that G is random to make life easy, but I think results for random graphs could probably be extended to any graph with low conductance.

Can we route arbitrary global communication in time poly(n)? In this post I’ll describe four variants of that problem, one which is well-understood and three that I think are good open problems.

(I won’t worry about authentication or encryption, we can handle those independently if people already know the public key of whoever they want to talk to, which is not our responsibility.)

I’ll talk about routing problems, but if we could route then I think we could build a distributed hash table. In general routing seems like a key building block for many P2P services.

I’ll talk about theoretical problems because I think these are nice theoretical problems and I like theory. I’m not claiming that these are particularly important problems for designing practical P2P systems.

I think these problems are open, but am not confident. If you think one of them is solved, please let me know.

1. An easy problem

Suppose that people are represented by IP addresses—if you know someone’s IP address you can talk to them, and people originally know the IP addresses of their neighbors in G. But you don’t know the IP address of the person you want to talk to.

Slightly more formally, people have two operations:

• Send(x, m) — try to send the message m to the user with IP x.
• Receive(y) — listen for a message from the user with IP y. If they’ve sent you any messages, returns the first one you haven’t seen, otherwise returns ⊥.

(Receive is a separate operation because otherwise it’s unclear what happens if a user receives more than poly(n) messages; we could instead just drop messages after the first poly(n) but then DoS will become a problem.)

This problem is solved by existing P2P systems. There are different algorithms (usually presented as algorithms for distributed hash tables), but I think this is the simplest approach and that others rest on a similar core:

• Of your 32 neighbors in G, about 16 of them will share the first bit of their ID. This forms a new graph G’, of people who share the same first bit.
• Ask each of your neighbors in G’ to connect you with a random one of their neighbors in G’. This gives us a new graph G(1), which has degree 32 and in which all neighbors share the first bit. Moreover, everyone knows the IP address of their neighbors.
• Repeat this process using G(1) in place of G, to obtain a new graph G(2). Keep going until we get down to a prefix length where there are <32 people who share that prefix, who then all know each other.
• When you want to route a message to someone who shares the first n’ bits of their ID with you, find a neighbor in G(n‘) who has the same n’+1th bit as the recipient. Pass the message along to them, and have them do the same. This will reach its destination in about n/2 steps.

2. Denial-of-service resistance

This algorithm is vulnerable to denial-of-service from a 1/n fraction of users. Is there an alternative routing protocol that works as long as 50% of people are honest?

The DoS attack works as follows: maintain a “shadow” copy of the real overlay network. Malicious nodes participate both in the real network (where they represent >>1/n of all nodes) and in the shadow network (where they represent 100% of all nodes). Whenever a malicious node routes a message, they move it from the real network into the shadow network. By the time a message reaches its destination, it is essentially guaranteed to be in the shadow network.

I don’t think that any algorithm is known for this problem, or even for thwarting relatively simple DoS attacks, which I find quite striking.

To make the problem possible, you need to assume that the user with ID x can authenticate themselves somehow, e.g. by having an associated private key. Without this, a malicious user can just impersonate the person I want to talk to.

3. Local communication

In problems #1 and #2, I assumed that you can talk to anyone whose address you know. In some sense this is cheating, by using existing routing infrastructure. I’m interested in the very theoretical question of how you would build such infrastructure in a hostile world.

For a harder problem that may more accurately capture the low-level routing problem, users are only allowed to send or receive messages from their neighbors in G—if I want to get a message to someone further away, we need to figure out how to route it.

Even if everyone is honest, I don’t know how to route in poly(n) time in this model and I think it’s an open problem. (You can get sub-exponential time by adapting existing P2P algorithms, but not polynomial.)

I find this a very natural and appealing problem, and I’m surprised it hasn’t been solved. I suspect that if you could solve this problem in a random graph G you could probably solve it with routing times depending on the conductance of of the graph (or the conductance of the graph of honest users, in the next section), which is the best you could hope for.

4. Denial-of-service resistance for local communication

We can combine problems #2 and #3, routing in fixed infrastructure with a constant fraction of malicious users.