slightly smarter sybils avoid colocation penalty

[dominictarr]

in the report, the sybils randomly connect to peers, but not other sybils. (side note: weak move because then you'll always be on the periphery of the network)

They don't do this in a smart way, just randomly. If more than one sybil from one machine connects to the same remote peer, then they get a heavy colocation penalty.

However, if sybils are aware of what the other sybils on that instance are doing (easy to coordinate, they are on the same machine) then each sybil could ensure they never connect to the same peer.

If there are 100 publishers, and 10 sybil machines, the sybils make 100 connections from each machine, then they can connect to each publisher. The publishers all connected to 10 machines - but to 10 unique ip addresses.

fact: if mesh peers are over D_high they are pruned.
question: is there a similar limit for gossip peers?

In our test cluster, each container used is assigned 2/3 to 1.2 vCPU and 1 to 2GB of RAM. Honest nodesrun as a single peer per container and can thus use the full CPU allotment, while Sybils, which run much simpler code, are packed as multiple peers per container and share this resource.
-- report: end of section 4.1

in this test we have 1k honest peers (100 publishers and 900 lurkers) and 4k Sybls packed in just 25 containers.
--report: section 15.3
but that's just the colocation test.

the default attack degree is 100, so a single machine (160 peers) connects to 100*160=1600 peers. since there are only 1000 honest peers, they necessarily connect to some peers twice, revealing themselves.

[dominictarr]

recognising this as the birthday problem, I wrote a quick script to calculate the number of unique peers that each sybil machine will connect to, for this test.

//choose C connections to N peers
var C = 1600, N = 1000
//sample random connections, return the number of duplicates
function sample (C, N) {
  var a = []
  for(var i = 0; i < C; i++)
    a.push(~~(Math.random()*N))

  //count the number of peers connected to more than once.
  //do not count a peer connected to 3 times twice.
  var d = {} //keep duplicates in this map so we don't count them twice
  a.sort((a, b) => a - b)
  var _p, c = 0
  for(var i = 0; i < a.length; i++) {
    if(_p === a[i]) {
      if(!d[a[i]]) { d[a[i]] = true; c++ }
    }
    _p = a[i]
  }
  return c
}

//take S samples of the above, and average result
var T = 0, S = 100
for(var i = 0; i < S; i++)
  T += sample(C, N)

console.log("percent of peers detecting colocation", (T/S)/N*100)

I was surprised at the result. 47% of honest peers received more than one connection from these sybils. I thought it would be higher, because if made 1600 connections to 1000 servers then you'd have to connect to 600 twice, but then realized you can lower that number by connecting to some more than twice.

Anyway, this means that 47% of the peers will give a colocation penalty to the sybils, and probably disconnect.

the report makes it sound like this defence works really well:

he 𝑃6 parameter of the scoring function completely obliterates the attack, as most attackers obtain a negative score from the vantage point of any peer. ... As a result, a large swath of Sybils are ignored at the time of mesh formation, which results in alargely honest peer dominated mesh.

However, a slightly smarter sybil attack would make less out going connections. 1000, one two each machine. so each honest peer receive 25 sybil connections. zero colocations would be detected.

[dominictarr]

OH just saw my mistake! 100 connections times 160 sybils should be 16,000 connections. in that case 100% of peers detect the attack. it's ilke 16 connections per honest peer, just from each machine. but then 25 times - so each peer gets 400 connections.

So I don't think the colocation penalty should be removed, because it does prevent getting 400 connections per machine. but you'd still get sybil 25 connections per honest peer in an attack using the same resources. That's still more than honest peers would make, so could do some damage.

The point that's still valid though, is that the sybils should connect non-randomly. With my previous math, actually for 10 random connections, the sybils create 1600 connections, but 47% of peers notice it's an attack because they get connected to twice.
How many peers do the sybils fool? I modified the script to give me the number of peers that only get connected to once - 331! that's only 20% of 1600. so they'd end up wasting 80% of their effort!

The question is: could a better planned attack do better with less connections?