> It is quite small because bittorrent needs to use some peer source. If you're not using the DHT you're using a tracker. The same information that can be obtained from the DHT can be obtained from trackers. So there's no novel information leakage introduced by the DHT.

Replacing a tracker with a DHT trades having one server with all peer and chunk knowledge with N servers with partial peer and chunk knowledge. If the goal is to stop unwanted eavesdroppers, then the choice is between (1) trusting that a single server that knows everything will not divulge information, or (2) trusting that an unknown, dynamic number of servers that anyone can run (including the unwanted eavesdroppers) will not divulge partial information.

The paper I linked up the thread indicates that unwanted eavesdroppers can learn a lot about the peers with choice (2) by exploiting the ways DHTs operate. Heuristics can slow this down, but not stop it. With choice (1), it is possible to fully stop unwanted eavesdroppers if peers can trust the tracker and communicate with it confidentially. There is no such possibility with choice (2) if the eavesdropper can run DHT nodes.

> That's not what I said. Relying on a DHT for some parts, such as bootstrap and discovery is still... well... relying on it, for things it is good at.

> Well yes, but these limits arise naturally anyway since A stores data for B on C and you can't really incentivize C to manage anything more than small bits of data.

Thank you for clarifying. Would you agree that reliable bootstrapping and reliable stead-state behavior are two separate concerns in the application? I'm mainly concerned with the latter; I would never make an application's steady-state behavior dependent on a DHT's ability to keep data available. In addition, bootstrapping information like initial peers and network settings can be obtained through other channels (e.g. DNS servers, user-given configuration, multicasting), which further decreases the need to rely on DHTs.

> About DHTs in general, you can easily make reverse lookups difficult or impossible by hashing the keys (bittorrent doesn't because the inputs already are hashes), you can obfuscate lookups by making them somewhat off-target until they're close to the target and making data-lookups and maintenance lookups indistinguishable. You can further add plausible deniability by by replaying recently-seeing lookups when doing maintenance of nearby buckets.

I'm not quite sure what you're saying here, but it sounds like you're saying that a peer can obfuscate lookups by adding "noise" (e.g. doing additional, unnecessary lookups). If so, then my reply would be this only increases the number of samples an eavesdropper needs to make to unmask a peer. To truly stop an eavesdropper, a peer needs to ensure that queries are uniformly distributed in both space and time. This would significantly slow down the peer's queries and consume a lot of network bandwidth, but it would stop the eavesdropper. I don't know of any production system that does this.

> If the goal is to stop unwanted eavesdroppers, then the choice is between (1) trusting that a single server that knows everything will not divulge informatio

In practice trackers do divulge all the same information that can be gleaned from the DHT and so does PEX in a bittorrent swarm. Those are far more convenient to harvest.

> I'm not quite sure what you're saying here, but it sounds like you're saying that a peer can obfuscate lookups by adding "noise" (e.g. doing additional, unnecessary lookups).

That's only 2 of 4 measures I have listed. And I would mention encryption again as a 5th. The others: a) Opportunistically creating decoys by having others repeat lookups they have recently seen as part of their routing table maintenance b) storing data in the DHT in a way that requires some prior knowledge to be useful, which will ideally result in the only leaking information when the listener could obtain the information anyway if he has that prior knowledge.

There's a lot you can do to harden DHTs. I agree that naive implementations are trivial to attack, but to my knowledge it is possible to achieve byzantine fault tolerance in a DHT in principle, it's just that nobody has actually needed that level of defense yet, attacks in the wild tend to be fairly primitive and only succeed because some implementations are very sloppy about sanitizing things.

> To truly stop an eavesdropper, a peer needs to ensure that queries are uniformly distributed in both space and time.

Not quite. You only need to increase the number of samples needed beyond the number of samples a peer is likely to generate during some lifecycle, and that is not just done by adding more traffic.

> Would you agree that reliable bootstrapping and reliable stead-state behavior are two separate concerns in the application?

Certainly, but bootstrapping is a task that you do more frequently than you think. You don't just join a global overlay once, you also (re)join many sub-networks throughout each session or look for specific nodes. DHT is a bit like DNS. You only need it once a day for a domain (assuming long TTLs), and it's not exactly the most secure protocol and afterwards you do the heavy authentication lifting with TLS, but DNS is still important, even if it you're not spending lots of traffic on it.

> In practice trackers do divulge all the same information that can be gleaned from the DHT and so does PEX in a bittorrent swarm. Those are far more convenient to harvest.

I'm confused. I can configure a tracker to only communicate with trusted peers, and do so over a confidential channel. The tracker is assumed to not leak peer information to external parties. A DHT can do neither of these.

> That's only 2 of 4 measures I have listed. And I would mention encryption again as a 5th. The others: a) Opportunistically creating decoys by having others repeat lookups they have recently seen as part of their routing table maintenance b) storing data in the DHT in a way that requires some prior knowledge to be useful, which will ideally result in the only leaking information when the listener could obtain the information anyway if he has that prior knowledge.

Unless the externally-observed schedule of key/value requests is statistically random in time and space, the eavesdropper can learn with better-than-random guessing which peers ask for which chunks. Neither (a) nor (b) address this; they simply increase the number of samples required.

> There's a lot you can do to harden DHTs. I agree that naive implementations are trivial to attack, but to my knowledge it is possible to achieve byzantine fault tolerance in a DHT in principle, it's just that nobody has actually needed that level of defense yet, attacks in the wild tend to be fairly primitive and only succeed because some implementations are very sloppy about sanitizing things.

First, no system can tolerate Byzantine faults if over a third of its nodes are hostile. If I can Sybil a DHT, then I can spin up arbitrarily many evil nodes. Are we assuming that no more than one third of the DHT's nodes are evil?

Second, "nobody has actually needed that level of defense yet" does not mean that it is a sound decision for an application to use a DHT with the expectation that the problems will never occur. So the maxim goes, "it isn't a problem, until it is." As an application developer, I want to be prepared for what happens when it is a problem, especially since the problems are known to exist and feasible to exacerbate.

> Not quite. You only need to increase the number of samples needed beyond the number of samples a peer is likely to generate during some lifecycle, and that is not just done by adding more traffic.

I'm assuming that peers are arbitrarily long-lived. Real-world distributed systems like BitTorrent and Bitcoin aspire to this.

> Certainly, but bootstrapping is a task that you do more frequently than you think. You don't just join a global overlay once, you also (re)join many sub-networks throughout each session or look for specific nodes. DHT is a bit like DNS. You only need it once a day for a domain (assuming long TTLs), and it's not exactly the most secure protocol and afterwards you do the heavy authentication lifting with TLS, but DNS is still important, even if it you're not spending lots of traffic on it.

I take issue with saying that "DHTs are like DNS", because they offer fundamentally different data consistency guarantees and availability guarantees (even Beehive (DNS over DHTs) is vulnerable to DHT attacks that do not affect DNS).

Regardless, I'm okay with using a DHT as one of many supported bootstrapping mechanisms. I'm not okay with using it as the sole mechanism or even the primary mechanism, since they're so easy to break when compared to other mechanisms.

> I'm confused. I can configure a tracker to only communicate with trusted peers, and do so over a confidential channel. The tracker is assumed to not leak peer information to external parties. A DHT can do neither of these.

But then you are running a private tracker for personal/closed group use and have a trust source. If you have a trust source you could also run a closed DHT. But the bittorrent DHT is public infrastructure and best compared to public trackers.

> I'm assuming that peers are arbitrarily long-lived. Real-world distributed systems like BitTorrent and Bitcoin aspire to this.

Physical machines are. Their identities (node IDs, IP addresses) and the content they participate in at any given time don't need to be.

> If I can Sybil a DHT, then I can spin up arbitrarily many evil nodes.

This can be made costly. In the extreme case you could require a bitcoin-like proof of work system for node identities. But that would be wasteful... unless you're running some coin network anyway, then you can tie your ID generation to that. In lower-value targets IP prefixes tend to be costly enough to thwart attackers. If an attacker can muster the resources to beat that he would also have enough unique machines at his disposal to perform a DoS on more centralized things.

> Are we assuming that no more than one third of the DHT's nodes are evil?

Assuming is the wrong word. I think approaching BFT is simply part of what you do to harden a DHT against attackers.

> Second, "nobody has actually needed that level of defense yet" does not mean that it is a sound decision for an application to use a DHT with the expectation that the problems will never occur.

I haven't said that. I'm saying that simply because this kind of defense was not yet needed nobody tried to build it, as simple as that. Sophisticated security comes with implementation complexity, that's why we had HTTP for ages before HTTPS adoption was spurred by the snowden leaks.

> Neither (a) nor (b) address this; they simply increase the number of samples required.

(b) is orthogonal to sampling vs. noise.

> I'm not okay with using it as the sole mechanism or even the primary mechanism, since they're so easy to break when compared to other mechanisms.

What other mechanisms do you have in mind? Most that I am aware of don't offer the same O(log n) node-state and lookup complexity in a distributed manner.

> But then you are running a private tracker for personal/closed group use and have a trust source. If you have a trust source you could also run a closed DHT. But the bittorrent DHT is public infrastructure and best compared to public trackers.

You're ignoring the fact that with a public DHT, the eavesdropper has the power to reroute requests through networks (s)he can already watch. With a public tracker, the eavesdropper needs vantage points in the tracker's network to gain the same insights.

If we're going to do an apples-to-apples comparison between a public tracker and a public DHT, then I'd argue that they are equivalent only if:

(1) the eavesdropper cannot add or remove nodes in the DHT; (2) the eavesdropper cannot influence other nodes' routing tables in a non-random way.

> This can be made costly. In the extreme case you could require a bitcoin-like proof of work system for node identities. But that would be wasteful... unless you're running some coin network anyway, then you can tie your ID generation to that. In lower-value targets IP prefixes tend to be costly enough to thwart attackers. If an attacker can muster the resources to beat that he would also have enough unique machines at his disposal to perform a DoS on more centralized things.

Funny you should mention this. At the company I work part-time for (blockstack.org), we thought of doing this very thing back when the system still used a DHT for storing routing information.

We had the additional advantage of having a content whitelist: each DHT key was the hash of its value, and each key was written to the blockchain. Blockstack ensured that each node calculated the same whitelist. This meant that inserting a key/value pair required a transaction, and the number of key/value pairs could grow no faster than the blockchain.

This was not enough to address data availability problems. First, the attacker would still have the power to push hash buckets onto attacker-controlled nodes (it would just be expensive). Second, the attacker could still join the DHT and censor individual routes by inserting itself as neighbors of the target key/value pair replicas.

The best solution we came up with was one whereby DHT node IDs would be derived from block headers (e.g. deterministic but unpredictable), and registering a new DHT node would require an expensive transaction with an ongoing proof-of-burn to keep it. In addition, our solution would have required that every K blocks, the DHT nodes would deterministically re-shuffled their hash buckets among themselves in order to throw off any encroaching routing attacks.

We ultimately did not do this, however, because having the set of whitelisted keys growing at a fixed rate afforded a much more reliable solution: have each node host a 100% replica of the routing information, and have nodes arrange themselves into a K-regular graph where each node selects neighbors via a random walk and replicates missing routing information in rarest-first order. We have published details on this here: https://blog.blockstack.org/blockstack-core-v0-14-0-release-....

> Assuming is the wrong word. I think approaching BFT is simply part of what you do to harden a DHT against attackers.

If you go for BFT, you have to assume that no more than f of 3f+1 nodes are faulty. Otherwise, the malicious nodes will always be able to prevent the honest nodes from reaching agreement.

> I haven't said that. I'm saying that simply because this kind of defense was not yet needed nobody tried to build it, as simple as that. Sophisticated security comes with implementation complexity, that's why we had HTTP for ages before HTTPS adoption was spurred by the snowden leaks.

Right. HTTP's lack of security wasn't considered a problem, until it was. Websites addressed this by rolling out HTTPS in droves. I'm saying that in the distributed systems space, DHTs are the new HTTP.

> What other mechanisms do you have in mind? Most that I am aware of don't offer the same O(log n) node-state and lookup complexity in a distributed manner.

How about an ensemble of bootstrapping mechanisms?

* give the node a set of initial hard-coded neighbors, and maintain those neighbors yourself.

* have the node connect to an IRC channel you maintain and ask an IRC bot for some initial neighbors.

* have the node request a signed file from one of a set of mirrors that contains a list of neighbors.

* run a DNS server that lists currently known-healthy neighbors.

* maintain a global public node directory and ship it with the node download.

I'd try all of these things before using a DHT.

EDIT: formatting

> You're ignoring the fact that with a public DHT, the eavesdropper has the power to reroute requests through networks (s)he can already watch.

But in the context of bittorrent that is not necessary if we're still talking about information leakage. The tracker + pex gives you the same, and more, information than watching the DHT.

> we thought of doing this very thing back when the system still used a DHT for storing routing information.

The approaches you list seem quite reasonable when you have a PoW system at your disposal.

> have each node host a 100% replica of the routing information, and have nodes arrange themselves into a K-regular graph

This is usually considered too expensive in the context of non-coin/-blockchain p2p networks because you want nodes to be able to run on embedded and other resource-constrained devices. The O(log n) node state and bootstrap cost limits are quite important. Otherwise it would be akin to asking every mobile phone to keep up to date with the full BGP route set.

> assume that no more than f of 3f+1 nodes are faulty. Otherwise, the malicious nodes will always be able to prevent the honest nodes from reaching agreement.

Of course, but for some applications that is more than good enough. If your adversary can bring enough resources to bear to take over 1/3rd of your network he might as well DoS any target he wants. So you would be facing massive disruption anyway. I mean blockchains lose some of their security guarantees too once someone manages to dominate 1/2 of the mining capacity. Same order of magnitude. It's basically the design domain "secure, up to point X".

> I'm saying that in the distributed systems space, DHTs are the new HTTP.

I can agree with that, but I think the S can be tacked on once people feel the need.

> How about an ensemble of bootstrapping mechanisms?

The things you list don't really replace the purpose of a DHT. A dht is a key-value store for many keys and a routing algorithm to find them in a distributed environment. What you listed just gives you a bunch of nodes, but no data lookup capabilities. Essentially you're listing things that could be used to bootstrap into a DHT, not replacing the next layer services provided by a DHT.

> This is usually considered too expensive in the context of non-coin/-blockchain p2p networks because you want nodes to be able to run on embedded and other resource-constrained devices. The O(log n) node state and bootstrap cost limits are quite important. Otherwise it would be akin to asking every mobile phone to keep up to date with the full BGP route set.

Funny you should mention BGP. We have been approached by researchers at Princeton who are interested in doing something like that, using Blockstack (but to be fair, they're more interested in giving each home router a copy of the global BGP state).

I totally hear you regarding the costly bootstrapping. In Blockstack, for example, we expect most nodes to sync up using a recent signed snapshot of the node state and then use SPV headers to download the most recent transactions. It's a difference between minutes and days for booting up.

> Of course, but for some applications that is more than good enough. If your adversary can bring enough resources to bear to take over 1/3rd of your network he might as well DoS any target he wants. So you would be facing massive disruption anyway.

Yes. The reason I brought this up is that in the context of public DHTs, it's feasible for someone to run many Sybil nodes. There's some very recent work out of MIT for achieving BFT consensus in open-membership systems, if you're interested: https://arxiv.org/pdf/1607.01341.pdf

> I mean blockchains lose some of their security guarantees too once someone manages to dominate 1/2 of the mining capacity. Same order of magnitude. It's basically the design domain "secure, up to point X".

In Bitcoin specifically, the threshold for tolerating Byzantine miners is 25% hash power. This was one of the more subtle findings from Eyal and Sirer's selfish mining paper.

> The things you list don't really replace the purpose of a DHT. A dht is a key-value store for many keys and a routing algorithm to find them in a distributed environment. What you listed just gives you a bunch of nodes, but no data lookup capabilities. Essentially you're listing things that could be used to bootstrap into a DHT, not replacing the next layer services provided by a DHT.

If the p2p application's steady-state behavior is to run its own overlay network and use the DHT only for bootstrapping, then DHT dependency can be removed simply by using the systems that bootstrap the DHT in order to bootstrap the application. Why use a middle-man when you don't have to?

> If the p2p application's steady-state behavior is to run its own overlay network and use the DHT only for bootstrapping, then DHT dependency can be removed simply by using the systems that bootstrap the DHT in order to bootstrap the application. Why use a middle-man when you don't have to?

It seems like we have a quite different understanding how DHTs are used, probably shaped by different use-cases. Let me see if I can summarize yours correctly: a) over time nodes will be interested or have visited in a large proportion of the keyspace b) it makes sense to eventually replicate the whole dataset c) the data mutation rate is relatively low d) access to the keyspace is extremely biased, there is some subset of keys that almost all nodes will access. Is that about right?

In my case this is very different. Node turnover is high (mean life time <24h), data is volatile (mean lifetime <2 hours), nodes are only ever interested in a tiny fraction of the keyspace (<0.1%), nodes access random subsets of the keyspace, so there's little overlap in their behavior. The data would become largely obsolete before you even replicated half the DHT unless you spent a lot of overhead on keeping up with hundreds of megabytes of churn per hour and you would never use most of it.

So for you there's just "bootstrap dataset" and then "expend a little effort to keep the whole replica fresh". For me there's really "bootstrap into the dht", "maintain (tiny) routing table" and then "read/write random access to volatile data on demand, many times a day".

This is why the solutions you propose are no solutions for a general DHT which can also cope with high churn.

> It seems like we have a quite different understanding how DHTs are used, probably shaped by different use-cases. Let me see if I can summarize yours correctly: a) over time nodes will be interested or have visited in a large proportion of the keyspace b) it makes sense to eventually replicate the whole dataset c) the data mutation rate is relatively low d) access to the keyspace is extremely biased, there is some subset of keys that almost all nodes will access. Is that about right?

Agreed on (a), (b), and (c). In (a), the entire keyspace will be visited by each node, since they have to index the underlying blockchain in order to reach consensus on the state of the system (i.e. each Blockstack node is a replicated state machine, and the blockchain encodes the sequence of state-transitions each node must make). (d) is probably correct, but I don't have data to back it up (e.g. because of (b), a locally-running application node accesses its locally-hosted Blockstack data, so we don't ever see read accesses).

> In my case this is very different. Node turnover is high (mean life time <24h), data is volatile (mean lifetime <2 hours), nodes are only ever interested in a tiny fraction of the keyspace (<0.1%), nodes access random subsets of the keyspace, so there's little overlap in their behavior. The data would become largely obsolete before you even replicated half the DHT unless you spent a lot of overhead on keeping up with hundreds of megabytes of churn per hour and you would never use most of it.

Thank you for clarifying. Can you further characterize the distribution of reads writes over the keyspace in your use-case? (Not sure if you're referring to the Bittorrent DHT behavior in your description, so apologies if these questions are redundant). For example:

* Are there a few keys that are really popular, or are keys equally likely to be read?

* Do nodes usually read their own keys, or do they usually read other nodes' keys?

* Is your DHT content-addressable (e.g. a key is the hash of its value)? If so, how do other nodes discover the keys they want to read?

* If your DHT is not content-addressable, how do you deal with inconsistent writes during a partition? More importantly, how do you know the value given back by a remote node is the "right" value for the key?

> Not sure if you're referring to the Bittorrent DHT

I am, but that's not even that important because storing a blockchain history is a very special usecase because you're dealing with an append-only data structure. There are no deletes or random writes. Any DHT used for p2p chat, file sharing or some mapping of identity -> network address will experience more write-heavy, random access workloads.

> Are there a few keys that are really popular, or are keys equally likely to be read?

Yes, some are more popular than others, but the bias is not strong compared to the overall size of the network. 8M+ nodes. Key popularity may range from 1 to maybe 20k. And such peaks are transient, mostly for new content.

> Do nodes usually read their own keys, or do they usually read other nodes' keys?

It is extremely unlikely that nodes are interested in the data for which they provide storage.

> Is your DHT content-addressable (e.g. a key is the hash of its value)?

Yes and no, it depends on the remote procedure call used. Generic immutable get/put operations are. Mutable ones use the hash of the pubkey. Peer address list lookups use the hash of an external value (from the torrent).

> * If your DHT is not content-addressable, how do you deal with inconsistent writes during a partition? More importantly, how do you know the value given back by a remote node is the "right" value for the key?

For peer lists it maintains a list of different values from multiple originators, the value is the originator's IP, so it can't be easily spoofed (3-way handshake for writes). A store adds a single value, a get returns a list.

For mutable stores the value -> signature -> pubkey -> dht key is checked.