3 ms·

You haven't taken into account the resources required to do so. 1) Open ports, alredy rules out a large part of those millions 2) Willingness to sacrifice ban

You haven't taken into account the resources required to do so. 1) Open ports, alredy rules out a large part of those millions 2) Willingness to sacrifice bandwidth for something that will still take a long time to populate a large enough database when run on a home ISP connection 3) The average user will stop using it when too much UDP crashes the router 4) The "Crawling BitTorrent DHTs for Fun and Profit" paper only takes into account the Vuze-only DHT 5) A completely distributed torrent database system with a pretty nice search function like Tribler alredy exists and doesn't seem to be that popular.

the8472 10y ago
I am using "does this approach work if every node in the network behaves like this" as a yard stick to gauge whether some p2p node is a good implementation. You're not just running the software on your own machine, you're running in a network with everyone. If the network would fail if a specific implementation becomes dominant then it's badly engineered. But that's just the point where harm becomes obvious. That doesn't mean there's no harm when they're only a minority of nodes. They're still making things less efficient for other nodes, drain resources or might make lookups more unreliable. This might make the network less attractive for end-users for example. So the extrapolation simply helps making an already-present net drain on the network resources more apparent.
- belorn 10y ago
  Could you explain the harm in a bit more details? How many false identities (that don't respond) is needed to flood the routing table and cause a noticeable impact, and further, to completely make a resources inaccessible? Are we talking about 1:1 for each fake vs real, 10^2:1, or does it more or less need to fill up limited resources such as memory or network?
  - the8472 10y ago
    I'm not sure if you have understood my argument. The precise ratio at which it becomes noticeable or at which things start breaking down is not relevant to gauging whether an implementation is well-behaved or not. Fundamentally a p2p network can only work if averaged over the nodes the following holds: resources consumed <= resources provided. If everyone tries to consume more than they provide (possibly zero) then the network does not work. This can be extended a bit further by also looking at whether some node behavior impacts how much other nodes consume. Ultimately means selfish nodes are harmful to the network on a fundamental level. They simply cannot satisfy that inequality. Even a single misbehaving node will inflict an - admittedly miniscule - amount of harm on the network. It's akin to stealing a dollar from your wallet, it probably won't even impact your day. And just like stealing dollars gets worse and worse as you take more of them from people the noticeable impact in a network gets worse and worse as the fraction of misbehaving nodes increases. It starts with wasting everyone's bandwidth (metered internet!), then increases the latency of lookups because you need to visit more hops and then less strict implementations start to fail lookups. The most strict, defensive implementations gradually failing more and more of their lookups is just the last and most visible kind of harm. To give a more concrete example, I have observed utorrent and libtorrent DHT implementations having polluted routing tables near their home buckets since they don't sanitize fake nodes aggressively enough. This adds maybe a dozen entries to their routing tables, it's not much. But any lookup coming their way will experience significantly increased latency because the terminal phase of a lookup should be exhaustive, so an implementation has to try all the bogus entries. There are counter-measures of course, but they increase implementation complexity and result more maintenance traffic than otherwise necessary. Those fake nodes come from only a few thousand IPs and yet they cause a negative impact for everyone because they have indirect effects. So in the real world the impact depends on a) fraction of bad nodes b) aggressiveness of bad nodes (not all bad behavior has the same impact) c) implementation quality of those who are trying to be good citizens.
    - belorn 10y ago
      Lets compare this to a similar decentralized p2p network, the World Wide Web. If every node where a search engine and used web spiders we would fill up all bandwidth and web server resources (memory, cpu) with spider requests. Selfish nodes like google can and sometimes cause services to go down because of too aggressive behavior. Yet the network (and people who operative websites) do accept some amount of crawlers, and don't compare it to stealing a dollar from our wallet (even if power+bandwidth+man power could easily equal to just that). The cost of crawlers should normally not cause any actually latency issues since web servers operative in very parallel way, utilize multiple cpu cores, and bandwidth are generally wide enough (and not metered). This is why I asked if there is real impact. In theory web spiders are extremely aggressive and non-scaling nodes, but in practice they are mostly background noise and have no impact on the service quality. In the cases they do impact we have blacklists (robot.txt) for just that purpose. As such the real world impact of non-scaling World Wide Web nodes is minimal. You describe in the concrete example that there is currently a few dozen fake entries and that they cause increased latency in some implementations. A) is there any measurements and B), do it run parallel C), do the fake entries get higher priority than real nodes?
      - the8472 10y ago
        > Lets compare this to a similar decentralized p2p network, the World Wide Web. Horribly horribly flawed analogy. You can't compare a DHT (or most p2p networks for that matter) and the web. The web is barely decentralized and mostly client-server, not peer-to-peer while a DHT is distributed, not just decentralized. The traffic characteristics are dramatically different. The client-server architecture alone already assumes that there is an asymmetry, that there are resource-providers and resource-takers. That is the opposite of how Kademlia is designed. Additionally the web is very different from a game-theoretic perspective. Each node is responsible for its own content, so it can make cost-benefit tradeoffs for itself. In a p2p network for Node A stores on B for C to retrieve data node B has no direct incentives to store anything at all, they only exist indirectly if B is interested in the network operating smoothly, this means fairness is far more important since otherwise nodes can become disincentivized from participating in the network. Anyway, web crawlers are not a violation of any web standard. Aggressive DHT indexing on the other hand as discussed here is not merely aggressive, it blatantly violates specs in ways that are obviously detrimental to other nodes. If we wanted to compare it to something web-tech it would be like randomly choosing http servers and then flooding them with slow-read attacks and spoofed HTTP headers for... uhm... bandwidth testing purposes or some other reason which the server operators have no interest in. > and don't compare it to stealing a dollar from our wallet (even if power+bandwidth+man power could easily equal to just that). So you acknowledge the equivalence but then dismiss it anyway without further arguments? > A) is there any measurements yes > B) do it run parallel? I don't understand your question. > C) do the fake entries get higher priority than real nodes? Priority by which metric? There is no explicit priority in kademlia, but many operations involve relative ordering of nodes, the fake nodes one can be closer to the destination, yes, which is what slows down the lookups.

the8472 10y ago

I am using "does this approach work if every node in the network behaves like this" as a yard stick to gauge whether some p2p node is a good implementation. You're not just running the software on your own machine, you're running in a network with everyone. If the network would fail if a specific implementation becomes dominant then it's badly engineered. But that's just the point where harm becomes obvious. That doesn't mean there's no harm when they're only a minority of nodes. They're still making things less efficient for other nodes, drain resources or might make lookups more unreliable. This might make the network less attractive for end-users for example. So the extrapolation simply helps making an already-present net drain on the network resources more apparent.

belorn 10y ago
Could you explain the harm in a bit more details? How many false identities (that don't respond) is needed to flood the routing table and cause a noticeable impact, and further, to completely make a resources inaccessible? Are we talking about 1:1 for each fake vs real, 10^2:1, or does it more or less need to fill up limited resources such as memory or network?
- the8472 10y ago
  I'm not sure if you have understood my argument. The precise ratio at which it becomes noticeable or at which things start breaking down is not relevant to gauging whether an implementation is well-behaved or not. Fundamentally a p2p network can only work if averaged over the nodes the following holds: resources consumed <= resources provided. If everyone tries to consume more than they provide (possibly zero) then the network does not work. This can be extended a bit further by also looking at whether some node behavior impacts how much other nodes consume. Ultimately means selfish nodes are harmful to the network on a fundamental level. They simply cannot satisfy that inequality. Even a single misbehaving node will inflict an - admittedly miniscule - amount of harm on the network. It's akin to stealing a dollar from your wallet, it probably won't even impact your day. And just like stealing dollars gets worse and worse as you take more of them from people the noticeable impact in a network gets worse and worse as the fraction of misbehaving nodes increases. It starts with wasting everyone's bandwidth (metered internet!), then increases the latency of lookups because you need to visit more hops and then less strict implementations start to fail lookups. The most strict, defensive implementations gradually failing more and more of their lookups is just the last and most visible kind of harm. To give a more concrete example, I have observed utorrent and libtorrent DHT implementations having polluted routing tables near their home buckets since they don't sanitize fake nodes aggressively enough. This adds maybe a dozen entries to their routing tables, it's not much. But any lookup coming their way will experience significantly increased latency because the terminal phase of a lookup should be exhaustive, so an implementation has to try all the bogus entries. There are counter-measures of course, but they increase implementation complexity and result more maintenance traffic than otherwise necessary. Those fake nodes come from only a few thousand IPs and yet they cause a negative impact for everyone because they have indirect effects. So in the real world the impact depends on a) fraction of bad nodes b) aggressiveness of bad nodes (not all bad behavior has the same impact) c) implementation quality of those who are trying to be good citizens.
  - belorn 10y ago
    Lets compare this to a similar decentralized p2p network, the World Wide Web. If every node where a search engine and used web spiders we would fill up all bandwidth and web server resources (memory, cpu) with spider requests. Selfish nodes like google can and sometimes cause services to go down because of too aggressive behavior. Yet the network (and people who operative websites) do accept some amount of crawlers, and don't compare it to stealing a dollar from our wallet (even if power+bandwidth+man power could easily equal to just that). The cost of crawlers should normally not cause any actually latency issues since web servers operative in very parallel way, utilize multiple cpu cores, and bandwidth are generally wide enough (and not metered). This is why I asked if there is real impact. In theory web spiders are extremely aggressive and non-scaling nodes, but in practice they are mostly background noise and have no impact on the service quality. In the cases they do impact we have blacklists (robot.txt) for just that purpose. As such the real world impact of non-scaling World Wide Web nodes is minimal. You describe in the concrete example that there is currently a few dozen fake entries and that they cause increased latency in some implementations. A) is there any measurements and B), do it run parallel C), do the fake entries get higher priority than real nodes?
    - the8472 10y ago
      > Lets compare this to a similar decentralized p2p network, the World Wide Web. Horribly horribly flawed analogy. You can't compare a DHT (or most p2p networks for that matter) and the web. The web is barely decentralized and mostly client-server, not peer-to-peer while a DHT is distributed, not just decentralized. The traffic characteristics are dramatically different. The client-server architecture alone already assumes that there is an asymmetry, that there are resource-providers and resource-takers. That is the opposite of how Kademlia is designed. Additionally the web is very different from a game-theoretic perspective. Each node is responsible for its own content, so it can make cost-benefit tradeoffs for itself. In a p2p network for Node A stores on B for C to retrieve data node B has no direct incentives to store anything at all, they only exist indirectly if B is interested in the network operating smoothly, this means fairness is far more important since otherwise nodes can become disincentivized from participating in the network. Anyway, web crawlers are not a violation of any web standard. Aggressive DHT indexing on the other hand as discussed here is not merely aggressive, it blatantly violates specs in ways that are obviously detrimental to other nodes. If we wanted to compare it to something web-tech it would be like randomly choosing http servers and then flooding them with slow-read attacks and spoofed HTTP headers for... uhm... bandwidth testing purposes or some other reason which the server operators have no interest in. > and don't compare it to stealing a dollar from our wallet (even if power+bandwidth+man power could easily equal to just that). So you acknowledge the equivalence but then dismiss it anyway without further arguments? > A) is there any measurements yes > B) do it run parallel? I don't understand your question. > C) do the fake entries get higher priority than real nodes? Priority by which metric? There is no explicit priority in kademlia, but many operations involve relative ordering of nodes, the fake nodes one can be closer to the destination, yes, which is what slows down the lookups.