[p2p-hackers] Re: Byzantine Quorum Systems

[Zooko O'Whielacronx]

Hello Nick, Brad, et al.

"The Sybil Attack" by John Doceur puts the question in the p2p context:

http://citeseer.ist.psu.edu/douceur02sybil.html

This paper can be lossily compressed as: "Your scheme can handle up to 
K malicious nodes.  My attacker can bring K+1 malicious nodes to the 
party.".

It is an excellent paper because it is very general and it requires p2p 
designers to think explicitly about the issue.

The argument in "The Sybil Attack" is valid -- if you accept its 
premises, then you must accept its conclusion.  However, there is one 
premise which is implicit in this paper and in most related research 
which ought to be challenged.

This implicit premise is that a connection between two node arises ex 
nihilo.  That is: for any three nodes A, B, and C, A has (at the start) 
no information about how B differs from C.  This assumption is 
obviously key to the whole issue.  It is also obviously wrong!

In practice the opposite is often true: for any three nodes A, B, and 
C, A often has information distinguishing B from C.  This is because A 
has been introduced to B somehow, and that introduction gave A 
information.  (Likewise with A's introduction to C.)

In sum, The Sybil Attack beats Byzantine techniques, but fortunately 
that doesn't matter because both of those ideas are set in an idealized 
world in which an unbounded number of indistinguishable peers are 
introduced to one another ex nihilo, with the introductions conveying 
no information.  Rather that struggle vainly to overcome The Sybil 
Attack in that idealized world, I suggest designing distributed systems 
that are secure only when bootstrapped with useful introductions.

I don't know whether that kind of design can accomodate "The Napster 
Setting", in which a large number of strangers want to be automatically 
introduced in order to trade files.  I suspect that it *can*, but I 
also think that this isn't the only interesting setting for p2p 
designs, and other settings may be even more amenable to designs which 
use the information from introductions.

Regards,

Zooko