Eclipse robust DHT using expected ID distribution

[Stebalien]

It may be possible to make a DHT robust against eclipse attacks by using expected distribution of node IDs.

In a DHT, nodes are expected to be evenly distributed around the node ID space. In a DHT with an active eclipse attack, one would expect a large cluster of node IDs around the target key.

Instead of using K as the bucket size, one could use expected ID distribution. For example, in a network with 10K nodes, one would expect:

• 1 node to share logtwo(10,000) = 13 at least bits.
• 2 nodes to share at least 12 bits.
• ...
• 20 nodes to share at least 8-9 nits (logtwo(network size) - logtwo(K))

So, instead of putting to the closest 20 peers, you'd calculate the expected network size (e.g., by asking other peers how close their neighbors are and assuming a uniform network), then put to all peers sharing the expected number of bits (in this case, 8).

[raulk]

Sounds plausible. And there is literature covering probabilistic methods to estimate network size precisely based on a reasoning similar to yours; your proposal is using that same measurement to layer detect anomalies. @yiannisbot?

[dirkmc]

Could you clarify a couple of points in the proposal:

Instead of using K as the bucket size, one could use expected ID distribution

Do you mean that the bucket size would be based on the size of the network, rather than being a constant?

1 node to share logtwo(10,000) = 13 at least bits.

I'm not clear on which nodes share the bits here. Are you saying that given a random key, we can expect that probabilistically approximately one node's peer ID will share 13 bits with that key?

you'd calculate the expected network size (e.g., by asking other peers how close their neighbors are and assuming a uniform network)

I think a node can roughly calculate this based on the distribution of peer IDs of its closest neighbours (ie the closest K peer IDs in its routing table) without needing to ask neighbours.

then put to all peers sharing the expected number of bits (in this case, 8).

Are you saying here that:

• in the case of an eclipse attack, there will be many nodes clustered around a particular key
• in a network of 10k nodes with uniformly distributed peer IDs, we should expect about 20 nodes to share 8 bits with the target key
• so instead of putting to the 20 closest nodes (which may all be malicious nodes), put to all nodes which share 8 bits with the key (even if there are eg 100 of them)

Not sure if I'm understanding the above correctly?

[aschmahmann]

I think there may be something interesting here with estimating network size.

If IIUC two issues with this proposal are:

1. We can get eclipsed by a network timeout anyway since we may have to query a huge number of nodes if we're being eclipsed
2. We can get eclipsed unless the number of peers returned from a FindNode/Value query is unbounded. However, if it is unbounded then we can get DoS'd by a huge return message from FindNode/Value.

---

Another approach taken by I2P for this problem is to combine DHT keys with dates to make it more difficult to eclipse a particular target (source). IIUC in I2P a node's KadID is hash(KadID||yyyyMMdd) which makes it difficult to eclipse a particular target. If we wanted to keep our routing tables stable we could leave KadIDs the same, but make the Kad keys hash(key||yyyyMMdd).

If creating new Kad peers is very cheap (e.g. no problem recreating the same peers every day) then I2Ps strategy doesn't help, but it may be useful to us if we start making KadID creation and maintenance more expensive.

[Stebalien]

@dirkmc

Instead of using K as the bucket size, one could use expected ID distribution.

Not exactly. My description isn't quite accurate as I'm not suggesting we actually change K.

I'm suggesting we use K and the network size to figure out the expected key distribution. Basically, what's the expected XOR distance X from any given key such that we'd expect K nodes to fall within that range.

Once we calculate X, we'd:

1. Remain connected to all nodes within X of our ID.
2. Put and get k/v pairs to/from all peers with IDs where (k XOR ID) <= X.

If the network is operating correctly, we'd expect to have K peers within XOR distance X and we'd expect to put/get to/from K peers.

I'm not clear on which nodes share the bits here. Are you saying that given a random key, we can expect that probabilistically approximately one node's peer ID will share 13 bits with that key?

Yes.

I think a node can roughly calculate this based on the distribution of peer IDs of its closest neighbours (ie the closest K peer IDs in its routing table) without needing to ask neighbours.

Unless that node is being eclipsed. There are two eclipse attacks:

1. Eclipse a peer to cut them off from the network. For this case, we need to look at how close are peers' neighbors are to them.
2. Eclipse a key to control it. For this case, we can just look at how close our peers are.

Are you saying here that:

Yes. Of course, this does mean that an attacker could force other nodes to do a bunch of work. However, they should have to do a proportional amount of work and they shouldn't be able to actually hide anything.

---

@aschmahmann

We can get eclipsed by a network timeout anyway since we may have to query a huge number of nodes if we're being eclipsed

We'd dial all the final peers in parallel. But yes, this could lead to a lot of work.

We'd likely need audit/score peers to detect misbehavior. I wonder if we could abuse relays and ephemeral libp2p nodes to anonymously verify that our peers are behaving correctly.

We can get eclipsed unless the number of peers returned from a FindNode/Value query is unbounded.

You're right, the closest peers to a key would need to return all peers within X (xor distance) of the key. And we would need to set an upper limit.

Another approach taken by I2P for this problem is to combine DHT keys with dates to make it more difficult to eclipse a particular target (source). IIUC in I2P a node's KadID is hash(KadID||yyyyMMdd) which makes it difficult to eclipse a particular target.

I'm not sure how well that works unless I don't know the key; I believe this defense is trying to defend against that case. That is, when the day changes, I can simply create 20 nodes close to the key. Peers close to that key will accept me because I'm the closest.

[dirkmc]

@Stebalien thanks for clarifying. Some details to be worked out but this seems like a good lead for how to mitigate against eclipse attacks while using linear defense resources.

Do I understand correctly that the query also needs to get values from all the peers with the common prefix (eg if there are 100 peers in the 8 bits of common prefix range, it needs to get values from all 100 peers)?

In the case of an IPNS-like system which fetches a certain number of values (eg 16) an attacker could still flood the target key's neighbourhood with enough sybils to have a high chance of shutting out legitimate nodes, is that right?

[aschmahmann]

I'm not sure how well that works unless I don't know the key; I believe this defense is trying to defend against that case. That is, when the day changes, I can simply create 20 nodes close to the key. Peers close to that key will accept me because I'm the closest.

I think this sort of defensive may help if creating and/or maintaining peers in the network is expensive enough that creating enough peers to eclipse the network within a 1 day period is too expensive. We're certainly not there yet, but we could potentially utilize PoW KadID generation and/or some reputation system based on continuous availability to help here.

In the case of an IPNS-like system which fetches a certain number of values (eg 16) an attacker could still flood the target key's neighbourhood with enough sybils to have a high chance of shutting out legitimate nodes, is that right?

Good news, we shouldn't need to deal with this system for much longer. Generally there are two types of DHT Get queries, those that abort early and those that actually locate the k closest peers. If you decide to save resources by aborting early then the eclipse will hurt you, but you could decide to not abort early and then this will be less of an issue. Moving IPNS away from early aborts by default seems like the smart move and is my current plan for libp2p/go-libp2p-kad-dht#436.

[Stebalien]

Do I understand correctly that the query also needs to get values from all the peers with the common prefix (eg if there are 100 peers in the 8 bits of common prefix range, it needs to get values from all 100 peers)?

Yes.

In the case of an IPNS-like system which fetches a certain number of values (eg 16) an attacker could still flood the target key's neighbourhood with enough sybils to have a high chance of shutting out legitimate nodes, is that right?

Yes but we're dropping that feature. Instead, we're continuing till we "terminate" the query. In this case, termination would mean talking to all nodes with the common prefix.

[yiannisbot]

@Stebalien: the following paper is proposing something very similar to what you're suggesting. They assume a fixed network size (of 4M in their case), so size estimation is not an issue for them, although they acknowledge that if network size fluctuates a lot, a size estimation technique needs to be in place.

They detect DHT attacks by comparing the abnormal peer ID distribution introduced around the targeted entry to the theoretical IDs distribution. After defining the theoretical distribution, they use the Kullback-Leibler divergence to detect anomalies. Certainly interesting read.

• Efficient DHT attack mitigation through peers’ ID distribution, 2010

[yiannisbot]

Sounds plausible. And there is literature covering probabilistic methods to estimate network size precisely based on a reasoning similar to yours; your proposal is using that same measurement to layer detect anomalies. @yiannisbot?

@raulk: Regarding measurement of network size, there are generally two approaches as far as I have seen.

1. The distance to the nearest neighbours in the routing table can be used as a network size estimate as it correlates with the network size [1] [2].
2. Measurement [8] or signalling (e.g., for DHT self-stabilisation [3], [4]). In this second category probabilistic approaches can be used to model inaccuracies [5]. Gossiping has also been proposed as an optimisation to self-stabilisation to avoid extensive signalling [6] [7].

[1] Controlling the Cost of Reliability in Peer-to-Peer Overlays - page 31-42
[2] Estimating Network Size from Local Information
[3] RFC3763: Self-Tuning Distributed Hash Table (DHT) for REsource LOcation And Discovery (RELOAD)
[4] RFC6940: REsource LOcation And Discovery (RELOAD) Base Protocol
[5] Measuring Large-Scale Distributed Systems:
Case of BitTorrent Mainline DHT
[6] A Self-stabilizing Network Size Estimation Gossip Algorithm for Peer-to-Peer Systems
[7] Decentralized Schemes for Size Estimation in Large and Dynamic Groups
[8] A Scalable Algorithm to Monitor Chord-based P2P Systems at Runtime