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

Closed
nathan-at-least opened this Issue May 6, 2015 · 7 comments

Projects

None yet

5 participants

@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).

@c-geek
Member
c-geek commented May 6, 2015

First, thanks for your interest. We do not have yet the documents you are asking for.

However, I can answer to your attack proposal: imagine a max distance of 3. So, all your bridge identities must be at a maximum of 2 from all others members, which means either direct or indirect (1 step) links to all members. If we think about a WoT of 1.000 members, which is not that much, it means quite a lot of signatures (maybe you know how many?). This is kind of a first protection.

Also, the newly introduced identities would be at a 3 step distance from existing identities. They cannot act as bridge entities to metastasize the community.

But more importantly at this point, we could ask ourselves if such a currency, where most of its members are corrupted and accept to simply burst their money because someone asked them to do so, may exist. We could even ask ourselves what would be the value of such currency. Which men would accept a currency he knows it can explode at any moment because most of its members wants the death of the currency? Would that currency had any value considering it is completely infected and promised to collapse?

So to me, the cost of conditions of your attack are either:

  • too expensive for an existing healthy currency
  • of no interest for a currency that has no value, since members know this currency is ready to collapse

I am giving you this number of maxStep = 3 on purpose. maxStep = 1 would mean any member is directly linked to all members. Very strong currency, but definitely limited in size. Same for maxStep = 2, even if we can probably start to have community size of hundred of members (either because we have a lot of links, or because the the maxStep rules activates only for those with a minimum number of links). maxStep = 3 gives us an other order of magnitude, but we still have the distance protection if we need it.

I'm sorry I cannot give you more number, proofs and stuff. But we do not have that much energy and knowledge yet.

@nathan-at-least

Thanks for the response!

I still worry, though, that in the attack scenario I outlined the Sybil identities would be able to metastasize. Suppose, as you suggest, it is difficult to create K bridge identities with a maximum distance of maxStep - 1 = 2 in a 1000 member system. If so, this is a good protection.

However as soon as those K bridge nodes achieve that state, they may create an unbounded number of Sybil nodes, correct? For example, all K sign the first Sybil identity, S0, then they sign the next one, S1, etc... All of the Sybil identities are maxStep = 3 distance, and they have K signatures, so they pass the heuristic.

If this is correct, then the security depends on preventing K malicious identities from achieving a distance of maxStep - 1 from all other nodes. That seems difficult to predict. One thought is that an analysis tool could show how many identities have a max distance of maxStep - 1 or less.

Imagine for a group currency of 1000 identities, there happen to be 20 "candidate identities" that have maximum distance of maxStep - 1 = 2. This means, if my proposed attack is feasible, that any 3 out of 20 identities may generate as many fake identities as they wish. That seems fragile. If a 1000 identity group has 200 such candidate identities, this seems much much more fragile. If there are known to be less than K = 3 candidate nodes, then we know the whole group currency is safe from such Sybil attacks.

I don't have any data either, but my intuition is that for a network of 1000, it's actually easy to get a max distance of 2 from all other nodes. Just befriend all of the "power nodes".

One way to get some real life data is to analyze the PGP web of trust. I believe, however, that this is misleading, because that web of trust is not designed to prevent Sybil attacks. Instead it is designed to allow any participant to measure graph distance to any other participant.

I haven't studied this problem before in depth, so I apologize for not offering any helpful suggestions beyond "let's analyze and document this security carefully".

Edits: Grammar and introducing "candidate identity" terminology for clarity.

@daira
daira commented May 7, 2015

It seems to be that this heuristic is too dependent on getting the maxStep parameter exactly right:

  • if maxStep is one step higher than it needs to be, then obtaining the K bridge identities required for the attack will be easy.
  • if maxStep is one step lower than it needs to be, then it will be too difficult for legitimate nodes to join the network.
@c-geek
Member
c-geek commented May 7, 2015

I still worry, though, that in the attack scenario I outlined the Sybil identities would be able to metastasize.

You are right. I had in mind the fact the Sybil newcomers would not be able to become candidate identities. But yes, of course, your bridge nodes alone allow for metastasizing.

Actually, your scenario is even wrong, because distance rule implies K = 1. So you only need one bridge to pass the distance rule.

However, this has to be mitigated for several reasons.

First is: a given identity cannot make more than one link every M minutes, M being the average time to validate a new block. Typically 10 minutes. That's a protocol rule to avoid massive intrusion and blocks' heaviness. Given your scenario, it means a 6*24 = 144 new Sybils a day. It is a lot, even for 100k members communities (> 50k Sybils a year). Maybe this rule could be strengthened to divide this links quantity by a 100 factor for example (a maximum of 1 signature accepted/day). 500 Sybil a year for 100k members seems acceptable to me. We both understand that human communities does not grow up by a 10 factor in a single day. A limit of signature by day would be an acceptable rule. Thanks for this one.

Second is: it actually is very difficult to be at a distance 2 from any member of the graph. Imagine: for 1000 members, it means that such an individual has 10 links to him having each 100 exact different links to them. This typically is a pure pyramidal scheme. If such a thing occurs, it would have been done on purpose. We could however imagine that "candidate identities" are not exactly at a 2 distance from all the members, but a part of it. You now have to find combinations to pass the rule. The wider the community, the harder it is to find these candidates. This does not seem te be an easy task ..

Furthermore, you said:

Just befriend all of the "power nodes".

I would argue that, if you want to protect yourself, then just do not link with people too close to the maxStep - 1 distance. By your unique, individual decision, you can protect against Sybils.

To me, this problem seems to complexify exponentially while community grows.

Anyway, thanks a lot for your suggestions and ideas. Do not hesitate to go further in the potential flaws you see :-)

@c-geek
Member
c-geek commented May 7, 2015

@daira Indeed, a maxStep = 6 would probably allow for worldwide currencies. But Sybil attack becomes extremely likely.

That's why I do not really see more that maxStep = 4, for the simple reason we do not need a common currency for too large communities. After a given level, it seems preferable to simply have another currency, with different people. Would that be only for trust reasons.

And when I say maxStep = 4, I mean combined with other rules. Just like maxStep = 3 is maybe possible, but not as the unique rule. It needs combination with links expiracy, delay between each new link, delay between link replays, etc.

FYI, here is an interesting document about links between community sizes and maxStep parameter, combined with a minimumLinksCount parameter: http://en.wikipedia.org/wiki/Table_of_the_largest_known_graphs_of_a_given_diameter_and_maximal_degree?oldformat=true

@c-geek c-geek added the docs label May 16, 2015
@c-geek c-geek added this to the Horizon milestone Dec 9, 2015
@M5oul M5oul added the WoT label May 12, 2016
@c-geek
Member
c-geek commented Jul 6, 2016 edited
@c-geek c-geek closed this Jul 6, 2016
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment