Can Poisoning Peer to Peer Networks Work? 391
andrewchen writes "Can poisoning peer to peer networks really work? Business 2.0 picked up my research paper from Slashdot
and wrote an article about it. In my paper, I argue that P2P networks may have an inherent "tipping point" that can be triggered without stopping 100% of the nodes on the network, using a model borrowed from biological systems. For those who think they have a technical solution to the problem, I outlined a few problems with the obvious solutions (moderation, etc.)."
Poisoning is not possible (Score:1, Interesting)
For example , lets take a net of 2^n nodes, and lets say 80% of which have been poisoned
take, for example, IRC - splits will never kill it (while I am saying splits I really reffer to poisoning, ofcourse).
Another example is the iraqui internet during the golf war. it didn't came down. why ? because when using distributed networks (such as P2P and the net itself) the resistability is just plane great.
Obvious technical solution take 2 (Score:3, Interesting)
So, um... how about this... If it's a standard file, such as, say, the deviance rip of neverwinter nights, or the new MPEG of Two Towers, then it should always have the same checksum.
Somebody somewhere needs to maintain a website with these checksums on. Then there's no dependence on the person who you're pulling the file from.
Obviously doesn't work for random porn videos (although it would for more popular ones... which might also tell you whether they're any good).
And there's nothing illegal about it.
Problems?
faked hashes (Score:3, Interesting)
The problem faked hashes can be addressed using trees of checksums rather than just a simple checksum although a workable implementation would require embedding into the P2P protocol.
The idea is you break the file up into smallish sized blocks (100k or so) and generate a hash for each one of these. For each 8 first level hashes, you feed them into a crypto hash function to generate a second level hash. For each 8 second level hashes... you generate a third level hash. This allows a continuous (per 100k blocks) proof that the content is valid... The size of the proof grows with the log of the content so it is not much of a problem.
Shameless plug... (Score:1, Interesting)
The network will be a semi-server-centered with a design similar to the NeoModus Direct Connect network.
The basic new idea is to reward users who share information by giving them more access to the network.
Hopefully this will make the network somewhat self-moderating since users sharing undesirable content will not rise in network status.
As I said, the project is still in the design-phase with a preliminary protocol spec just finished.
If you would like more details or contribute to the project, visit:
Bitpeddler project page [sourceforge.net]
or
Bitpeddler homepage (with design/protocol spec) [sourceforge.net]
Re:The easiest solution to fix poisoning... (Score:2, Interesting)
A blocking system can't work fast enough.
Re:Simple! (Score:4, Interesting)
Or, maybe, a "licence":
Having distributed content together with such licenses (or hired someone to do so), it might be a bit harder for the labels to defend copyright claims for individual songs.
Actually checksums should work. (Score:3, Interesting)
Although this idea works for newsgroups and some other centralized services, it does not with P2P. Basically, it comes down to the fact that you must trust whomever is actually doing the checksumming, or else they can just lie and publish false checksums. In the case of P2P networks, the checksumming is done by the same person you want to figure out if you can trust! As far as I know, this is an unresolvable problem.
Actually, the checksums should still work I believe, in much the same way that file sizes work now. Consider the reason the files that are being injected are set to the same size as the real file; the purpose is to mask these files to the naked eye. Checksums could be used for the same purpose.
The reason for this is because as people find good files they will tend to keep them while deleting the bad files. Sure if we only get 1 result back then we don't know one way or other, but if we have 10 results back and 8 of the 10 of the same checksum, we can assume those 8 are the good files.
Of course the problem with this is that a great many people don't bother to delete bad files after downloading, but should the poisoning become too much of a problem we can entice more people to clean up their shared files by way of the client interface.
All in all, I think this would combat poisoning very well.
block checksum (Score:3, Interesting)
To bad I am so late in posting this...
Two Problems (Score:2, Interesting)
I see two problems with this idea.
-or-
Re:it's already poisonned by users (Score:2, Interesting)
Searching on Kazaa yesterday for LOTR - The Two Towers (yes, I know, I'm such a pirate), I found about 4 files of 800MB - 1 GB in size. They all said, "Incomplete" or "Does not Work" in the filename.
It's not just that these files exist and don't work, but that people have them and just don't care. With HDs getting so large, who can blame them, either? Even a gig here and there isn't hurting most people.
So, I decided to download one of them and see. The Kazaa description was "LOTR - The Two Towers." The filename was "Eight-Legged Freaks Part 1 of 2." The actual file, upon some A/V work on my part, turned out to be several hours of audio from a trailer for The Scorpion King.
I mean, Jesus. Sorry if it's a little off-topic.
There is a business model that works (Score:3, Interesting)
MD5 Hash (Score:2, Interesting)
Re:Easy to fix, really. (Score:2, Interesting)
This proposed solution, or most any solution based upon moderation, has a few serious flaws. First of all, the use of public key encryption would require some sort of central authority to both assign moderator status to select members of the P2P network, and to distribute the keys to the masses. In the case of the Gnutella network, this could be said to be both the antithesis of the network model, as well as being relatively impossible to enforce - with the disjointed nature of the Gnutella network, it is conceivable that segments of the network would not be visible to a logged in moderator. In fact, to insure moderator coverage, moderator status would have to be given to a statistically high number of individuals. Second, the creation of the central authority necessary to administer this proposed 'solution' would give organizations like the RIAA and MPAA easy and - from their point of view - logical individuals to target in their foolhardy quest for the Copyright Grail.
Perhaps a means of voluntary moderation could be accommodated in the Gnutella protocol itself. 'Karma' could be built up on a network node based upon many criteria, which could include positive feedback from peers, etc. By writing moderation into the protocol itself, client developers could implement these features at their own discretion. The idea of moderation would then be put to the test of software natural selection.
Comparisons to the War on Drugs (Score:4, Interesting)
1. Randomly selecting and litigating against users engaging in piracy
2. Creating fake users that carry (incorrectly named or damaged files)
3. Broadcasting fake queries in order to degrade network performance
4. Selectively targeting litigation against the small percentage of users that carry the majority of the files
This mostly summarizes the war on drugs and the government's strategy against alcohol prohibition in the 1920's. Neither worked and the countermeasures are simple and straight forward.
A "directed" web of trust, objective quality measurement, and knowledge compartimentalization defeat the above strategy. The countermeasure of creating large numbers of mutally trusting attackers doesn't work when trust "flow" is taken into account. The keys to such a system are:
1) trust is assymetric
2) nodes define and change who they trust based on their own assessments
3) Nodes protect their knowledge of the web of trust
To see how this works, consider the cops and the drug dealers. The fact that the cops all trust each other does not result in the drug dealers trusting them. When a dealer is compromised, no matter how high up the chain it goes, trust shifts to rivals. Even when a kingpin falls, lines of trust will still exist that aren't compromised.
Drug dealing is not as popular as file sharing, is substantially more damaging to peoples lives and society, and has motivated levels of funding that are not matchable by publicly traded firms (who must demonstrate at least mid-range ROI). Despite all of these advantages, the war on drugs has been a dismal failure. The bottom line is that the internet makes distribution of content a commidity, where it was formerly a task of enormous complexity and value add. Economics will determine the rest, unless the US adopts and maintains a totalitarian government.
Ya can't beat evolution (Score:2, Interesting)
Re:Distributed trust and peer review (Score:3, Interesting)
You can send out a bad copy once, but if well-known and trusted copies already exist on the network you are not going to be able to replace these with bad copies, the self-verification does not prevent the single-point attack you describe, it prevents the propogation of this attack throughout the network. If an attacker serves up bad files (ones that do not match the SHA1 hash advertised) then the downloader should treat the host as malfunctioning and query a more reliable source. The downloading agent does not need to unpack the file and see what is inside, it just checks the SHA1 hash and then can simple assume that there was a transmission error and try another source. Eventually the malicious node will be trimmed from everyone else's peer list and a new node identity will have to be generated and the game starts again.
This single attack costs the attacker as much as it does the downloader (and you can bet the RIAA is paying more per MB of data sent than someone downloading the data via a DSL or cable modem line) and a few simple changes to the system like favoring trusted peers (ones who have not given you mismatched hash/payload data) as the first nodes to query and only moving down the local reputation food chain if you need to expand your query or search for alternate sources. Unless an attacker can pretend to be a vast majority of the nodes in the system it is not going to be able to make this attack scale-up in the manner you suggest.
There is a difference between an attack that works on a single download and an attack that would be viable for a network-wide assault. The case you and Mr. Chen bring up here is clearly in the first category, an inconvenience for individual users but not something that will be a significant problem for the network as a whole.
Moderation and peer reputation require some method of recording "ratings" of users on the network. Something not present in the current Gnutella network. But if implemented, it would have to be distributed as well. This means that there, at some point, must be a blind trust between clients to complete these "ratings". That blind trust will lead to poisioning of the ratings system and make it worthless.
"Ring of trust" simply does not work in a distributed environment that is truly open to anyone. Closed distributed environments, or virtually closed environments within an open environment would be the only way. However new users would not be able to enter them and that is how Gnutella keeps itself alive.
Which is why I think that things like Raph Levien's work in reputation systems (and actually coding up working examples of such a system, see refs below) are rather attractive because they solve this specific problem in a rather elegant fashion and make such simplistic attacks much more difficult and expensive to pull off. [Here's a quick hint: Have you ever noticed that most people seem to care about Roger Ebert's opinion rather than yours when it comes to what movies to go see? This is because distributed trust system can deal with voter flooding attacks by limiting how much influence comes from untrusted sources.]
You seem to think, Mr. McCoy, that there are obvious solutions. Yet you really don't present any nor do you present any existing real-world examples.
One of the problems I addressed in the original paper was the fact that it was poorly researched in certain aspects. It seems that everyone is too lazy to actually do any research these days, but since spending five minutes doing google searches on various terms related to reputation systems seems to be too much work for either you or Mr. Chen, here is a quick summary of a few minutes work (although I selected papers that I am familiar with after google returned a hit).
1) For starters look at Google itself. Google is the single biggest distributed reputation system in the internet. That is what a pagerank is, the "repuation" of a particular link for a particular subject using link count as the voting mechanism. It can be attacked and subverted on a small scale as various Google-juicing experiments prove, but it is also very effective at filtering out these attacks (see some of the Scientology google-juicing wars to see how hard it is to really influence a massively distributed reputatioon system implemented my people who know how to pick the best ideas from current research and invent a few of their own.
2) EBay seller rankings. These can also be attacked and tweaked, but even when money is involved (making the incentive for dishonest behavior very high, much more so than any p2p system will ever have to deal with) EBay manages to keep fraud to a manageable level and recent research into seller/buyer identity-blinding and reputation cluster filtering can make the seller ranking system even more attack-resistant.
3) Amazon buyer ratings and recommendations. Yet another example of a real-world distributed trust management system.
4) Advogato [advogato.org] is a community forum site that implements some of Raph's Ph.D. work in reputaitons and distrubted trust management to create a flow-constrained reputation system that has some very good attack-resistance characteristics. Raph has been running Advogato using his distrubted trust metric for several years now.
5) Pattie Maes' agents group at MIT [mit.edu], specifically the Yenta reputation clustering system but just about everything to come out of this group is a source of good ideas and practical research in this area.
6) Check out some of the available research bibliographies (like this [umich.edu]) and places like citeseer for other research in the subject.
One thing you will notice about these real-world examples is that none of the systems tries to be "perfect", just good enough to get the job done.