Document how Web-of-Trust heuristics defend against Sybil attacker.

Created by: nathan-at-least

From the FAQ:

Which are rules of Web of Trust?

Joining the Web of Trust requires to fit 3 conditions:

    an identity must gathers a minimum number of links
    an identity cannot have twice a same link for a given period
    an identity must be between [0, maxStep] distance from any other identity

Where:

    step 0 is the identity itself
    step n is an identity directly known by step n-1

This answer should link to a document which argues why these heuristics protect against Sybil attackers.

Proposed Sybil Attack:

Imagine an identity requires K links and an attacker controls K identities all of which are maxStep - 1 distance from all other identities. Let's call these K identities bridge identities. Now, the attacker can begin generating new identities rapidly. Call these Sybil identities. For each Sybil identity, the attacker signs a link from each of the K bridge identities pointing to the new Sybil identity.

Each Sybil identity has K links from the bridge identities (criterion 1). This signing happens during each period (criterion 2), and the distance from any Sybil identity to any other is maxStep because of the location of the bridge identities (criterion 3).

Is this attack feasible? If not, why not?

Whether or not this attack is feasible, a useful security model would provide a rationale for the three criteria above (or any other local heuristics or protocol security features).