Analysing the google attack


#82

I thought this might be some food for thought. Not sure if this will instigate any ideas…

mods: please move if you think it is off-topic.


#83

This is an excellent point, thanks for wording it so eloquently.

I would like to present an equivalent perspective for ‘joining should be easier not harder’ but from the opposite direction: ‘gaining power here should not make it easier to gain more power there’.

This is why bitcoin mining kinda sucks. It became a race to ASIC and the leader got more advantage over second and third place, which they used to increase their lead further and so on. I’m not sure there’s any way to avoid this, but I think the hueristic ‘joining should be made easier not harder where possible’ is a good start to prevent snowballing benefits to leaders.

Thanks for making this point though. it’s never about absolutes it’s about balance. We should consider the drawbacks of making it easy to join, not just the benefits. I guess my bias is clearly toward identifying the drawbacks!

It affects the network because the vault will eventually become an elder if it hangs around long enough, and it knows it will be an elder ‘somewhere close’ to where it currently lives (due to neighbourhood-based relocation).

So the attacker is targeting ‘recursive neighbourhoods’ rather than a specific section. The thing is, the degree of recursion is low so the attacker will always stay relatively close to where they start.

This is a clever idea. Gets the vault far away from the neighbourhood but retains the benefit of helping the section most in need.

I feel the same way. I won’t ramble here but this ties in with biomimicry (or in this case sociomimicry?) and my views on economic inequality in society today. We should be targeting a minimum-level-for-all rather than equality-for-all. This is a bit of a hobby-horse of mine so I’ll leave it at that!

The word that comes to mind is ‘efficiency’ and this is where bitcoin and blockchains have dropped the ball bigtime. If it isn’t efficient then one of the big points of difference is lost.

That’s awesome!


#84

Some more things to ponder along these lines in this RFC topic just posted. A bit too technical for here but definitely related.


#85

Glad you’re pushing this.

If this was my area, and I was contributing here, this is exactly the ideal I would push for and try to protect.

Even if the network is slightly slower at the beginning or something, at least it’s properly decentralised, which it needs to be to change the world.

Glad these discussions are happening, would be nice if they happened years ago but all good let’s do what we can!


#86

I think this is what we all aim for :wink:

They did and will for years to come :smiley: :smiley: This story never ends, but we need to just polish these small bits off to allow launch, but it never ends and is always interesting.


#87

Looking forward to the day every MS, Apple, Google, Amazon etc each have a “Routing Maintenance and RD” division :slight_smile:


#88

I agree that pow can be easily defeated (GPU, FPGA, or even ASICs). I can see alternatives that replace the offline key generation with some kind of interactive process that involves the existing network. There are schemes for cooperative key generation, “proof of wait”, or some other network-interactive process that either delays or randomizes the calculation of the target section for new vaults. I’ve already seen some suggested. Whatever works, just keep your black hat always on and look for the weakest link worth attacking.

Edit: but remember to KISS.


#89

Have a read of @mav’s proposal. I think it satisfies the KISS https://forum.safedev.org/t/secure-random-relocation/1321


#90

@neo yes! Was just reading it. Looks good.


#91

This work you are doing @mav is great to follow, and the code for these simulations have been a real joy to work with.

I’ve re-implemented the google attack simulation in c#, straight off from your repository.
I did not get it 100% right though (see bottom for some details on results). Have never coded a single line in golang, but it has more or less all to do with lacking knowledge of other things I would say.
I know for certain when I have to introduce some non-existing logic to avoid error, that I did not get it right…

So, I have a couple of questions:

1. What prefix is supposed to be returned when parent() and sibling() is called on empty prefix?

Some notes about workarounds I did.

Empty prefix would have 0 bits, right? So these two would first of all try to access index -1 when empty prefix is passed in. (For a while I wondered if go allows same kind of indexing as python, but seems it does not.)
So, here I have obviously missed something.
Trying a simple workaround, I would have to return empty prefix as parent, and sibling.

What it results in, is that when empty prefix section should merge, and has more than one section, line 93 in network.go will always be true, and we will remove the empty prefix (then again on line 109), then on line 111 the empty prefix section will be added again, with a duplicate list of original nodes in the section. So, not good.

Taking a step back, maybe the thing is that empty prefix is not supposed to ever return true on line 85? But when looking at the conditions it wouldn’t make sense, since it just validates on count nodes with age > 4 and having more than one section. These should both apply to also the first section.

When setting condition if (section.Prefix.Key != parentPrefix.Key) for adding back the parent prefix, then I actually got to the reporting, and reached fairly close to your numbers.

But all of this gave a whole lot of warnings like:
Split has vault that doesn't match extended prefix
and
No prefix for xorname

And this actually leads to next question:

2. Do you have 0 warnings in your latest version?
I’m guessing you do.

Additional note.

Similarly to indexing problem in parent() and sibling(), method renameWithPrefix in line 33 in vault.go, would when I re-implement, get problem if prefix.bits is longer than vault name bit length. I cannot tell if this is due to expectation that prefix passed in shall never be longer, or that SetBit would allow out of range indexing or if I got something else wrong there. My workaround was to put a condition on vault name bit length being equal or longer. So, another source of outcome warp there.


Some results when running the above.

As would be expected by all the above, the results are quite warped too. They look fairly similar, except that this is for the non-targeted attack, which gives results close to those of your targeted attacks.
Additonally the hops are 0 and 1 only.

Google Attack

Targeted  Recursive  NetSize  Test 1     2     3     4  | Avg. Pct
      No        Yes     100k    4219  5883  2184  5842  | 4.4

Distribution of nodes and adults:

Test 1
age  vaults
  1  1468
  2  19113
  3  52377
  4  26276
  5  3442
  6  431
  7  92
  8  20
  9  6

    adults  sections
         9        23
        10        38
        11        56
        12        14
        13        15
        14        12
        15        16
        16        10
        17        11
        18        11
        19        7
        20        6
        21        9
        22        3
        23        6
        24        5
        25        4
        26        2
        27        2
        28        2
        29        1
        30        2
        31        1
        32        2
        33        2
        43        2
        51        1
        57        1
Test 2
    age  vaults
      1  1400
      2  19737
      3  52822
      4  26463
      5  3334
      6  439
      7  90
      8  28
      9  2
     10  3
     11  2

adults  sections
    9         24
    10        31
    11        44
    12        19
    13        16
    14        13
    15        11
    16         5
    17        13
    18         7
    19        10
    20         7
    21         7
    22         7
    23         6
    24         5
    25         6
    26         3
    27         2
    28         3
    29         3
    30         1
    31         3
    33         1
    34         2
    35         1
    38         1
    39         1
Test 3
age  vaults
  1  1138
  2  18437
  3  52255
  4  26027
  5  3286
  6  423
  7  92
  8  20
  9  4
 11  1

adults  sections
     9        34
    10        26
    11        52
    12        12
    13        10
    14        10
    15        8
    16        10
    17        6
    18        10
    19        7
    20        7
    21        16
    22        9
    23        8
    24        2
    25        2
    26        8
    27        1
    28        4
    29        2
    30        1
    31        1
    34        1
    37        1
    43        2
Test 4
age  vaults
  1  1481
  2  19111
  3  52856
  4  26978
  5  3418
  6  470
  7  91
  8  28
  9  7
 10  1
 11  1

adults  sections
     9        29
     10       32
     11       53
     12       14
     13       9
     14       9
     15       11
     16       11
     17       7
     18       11
     19       14
     20       6
     21       9
     22       6
     23       5
     24       4
     25       9
     26       3
     27       3
     28       4
     29       2
     30       3
     31       2
     33       1
     35       1
     43       1
     48       1

Repo here, but as mentioned above, not quite right yet:


#92

This is very cool!

The empty prefix should be returned.

You have identified an error in my code because I don’t check for this boundary condition (see prefix.go sibling() L49 and prefix.go parent() L56). But I’ve not encountered the error so these two methods have never been called on the empty prefix during my simulations.

This should never happen since the empty section can only exist as one section on the network. When it splits into prefix 0 and 1 all future vaults will join one of those two sections. Those two sections may merge back into the empty section but in that case there is only one section on the network again so no further merges are possible.

There can never be the empty prefix and some other prefix on the network at the same time.

A new node should only be valid for one section on the network at any time. If that’s not true there is a problem with the split / merge simulation code somewhere.

eg if a network has sections for the empty prefix and prefix 0 simultaneously it means a vault with name 0... would match both the empty prefix and prefix 0 which is not a valid state for the network to be in.

I do not see any warnings.

There should never be a prefix longer than the vault name length (vault name length is constant at 256 bits). This would mean there’s approx 2^256 sections in the network which is pretty massive.


#93

Thanks a lot for the answers! l will see if I can steer it right when I have some more time later this week.

Aha, yes I strongly suspected this was a path that should not be valid, since you would have most likely noticed it otherwise.

Aah, of course… As soon as there is a split the parent does not exist, until there is a merge.
It was when adding attackers that it happened. Anyway, I will come back when I’ve looked deeper again.

OK. Good, then I know I need to be at 0 warnings too.

OK, this gives me a clue on what might be wrong.

Thanks again!


#94

OK, I’m back :slight_smile:
I had an semi-unexpected situation as our son decided to arrive a little bit early (all is well), so had some other things to attend to last weekend :slight_smile:

But, now I have sat down again with the code, and so seems like things got steered a bit closer to expected results.
I hope to soon be able to join @tfa in his research of various parameter and config tweaks for the network. I will need to look into the differences in his simulation code base. It will be great fun to start come up with new metrics and angles as well as derive conclusions from the results.

Anyhow, back to the GoogleAttack.
The problems from initial version has been fixed:

  • There are no warnings
  • There is no calling sibling() and parent() on empty prefix
  • No merge try on empty prefix
  • Prefix bit length is never longer than vault name bit length.

Additionally, the attack vault % for non-targeted attack is now aligned with expected results.

Remaining problems:

  • NeighBourhoodHops still only have 0 and 1 hops, so this differs from your results.

Results for GoogleAttack simulation
Targeted: No
Disallow rule: No
Network size: 100k nodes
Seed: 1

111370 attacking vaults added to own a section
211370 vaults after attack
2802 sections after attack
52,69 percent of total network owned by attacker

Relocation

TotalDepartures: 2066377
TotalJoins: 2277747
TotalMerges: 13140
TotalRelocations: 1655241
TotalSplits: 15817

Section size
Here we have one maxima at 48 vaults (81 sections) and one at 106 vaults (190 sections).

Section size

size count percent

15       1   0,036
16       1   0,036
18       2   0,071
19       2   0,071
20       1   0,036
21       1   0,036
22       4   0,143
23       4   0,143
24       5   0,178
25       5   0,178
26      11   0,393
27       7   0,250
28       9   0,321
29      14   0,500
30      19   0,678
31      26   0,928
32      26   0,928
33      36   1,285
34      27   0,964
35      30   1,071
36      25   0,892
37      39   1,392
38      45   1,606
39      42   1,499
40      46   1,642
41      60   2,141
42      56   1,999
43      49   1,749
44      57   2,034
45      77   2,748
46      53   1,892
47      71   2,534
48      81   2,891
49      57   2,034
50      44   1,570
51      49   1,749
52      52   1,856
53      37   1,320
54      49   1,749
55      43   1,535
56      24   0,857
57      29   1,035
58      25   0,892
59      17   0,607
60      22   0,785
61      21   0,749
62      12   0,428
63      10   0,357
64      10   0,357
65       9   0,321
66       9   0,321
67       3   0,107
68       7   0,250
69       5   0,178
70       8   0,286
71       4   0,143
72       2   0,071
73       3   0,107
74       2   0,071
75       4   0,143
76       4   0,143
78       2   0,071
79       2   0,071
80       2   0,071
81       5   0,178
82       2   0,071
83       1   0,036
84       1   0,036
86       2   0,071
88       1   0,036
89       2   0,071
90       2   0,071
91       1   0,036
92       1   0,036
93       1   0,036
94       2   0,071
95       3   0,107
96       2   0,071
97       5   0,178
98       2   0,071
99       6   0,214
100     12   0,428
101     18   0,642
102     23   0,821
103     50   1,784
104     97   3,462
105    160   5,710
106    190   6,781
107    164   5,853
108    126   4,497
109     66   2,355
110     48   1,713
111     43   1,535
112     39   1,392
113     26   0,928
114      9   0,321
115     15   0,535
116     18   0,642
117     10   0,357
118     14   0,500
119     11   0,393
120      8   0,286
121     11   0,393
122     11   0,393
123      7   0,250
124      9   0,321
125      8   0,286
126      3   0,107
127      4   0,143
128      3   0,107
129      4   0,143
130      1   0,036
131      6   0,214
132      2   0,071
133      4   0,143
134      4   0,143
135      2   0,071
136      4   0,143
137      3   0,107
138      1   0,036
139      4   0,143
140      2   0,071
141      1   0,036
143      4   0,143
144      1   0,036
145      2   0,071
146      1   0,036
148      3   0,107
14      2   0,071
151      1   0,036
155      1   0,036
156      1   0,036
160      1   0,036
163      1   0,036
165      1   0,036
167      1   0,036
170      1   0,036
191      1   0,036
202      1   0,036

Age

Most common age is 3, with 77123 vaults.

Age of Vaults
age  vaults
1      9027
2     40912
3     77123
4     43030
5     20261
6     10303
7      5539
8      2796
9      1438
10      625
11      249
12       61
13        6

Most common number of adults is 11, with 609 sections or 21.7% of all sections having this number of adults.

Adults in Sections
adults  sections
9       141
10      331
11      609
12      219
13      162
14      128
15      143
16      144
17      139
18      133
19      133
20      116
21      95
22      96
23      64
24      55
25      32
26      18
27      19
28      10
29      5
30      5
31      1
32      2
35      1
36      1

Prefix Balance

length  count
11      1296
12      1502
13         4

Questions

I’m not sure about the section size distribution, and if this is aligned with your results @mav.
Additionally, I wonder what could cause the remaining discrepancy with regards to neighbourhood hops.
Would there be anything else that seems to be off with the results?


#95

Kurt makes good points. This isn’t the 1990s. Most computers owned by regular people are behind the ISP’s firewall and can’t act as servers listening on a port. They can effectively become servers by piggybacking off servers on the Internet, which are required to keepalive a TCP connection. Or they can periodically poll for stuff. So they might not be available in real time but in every other respect these vaults can act as vaults.

Scuttlebutt project talks about this: https://www.scuttlebutt.nz/stories/design-challenge-avoid-centralization-and-singletons.html

Also it is not unreasonable to suppose that a lot of the vaults will be hosted on AWS or a virus may infect some servers, or a sybil attack may happen over time.


#96

Where is the CURRENT infrastructure for the SAFE network coming from?

It’s usually pretty difficult to have the initial infrastructure not controlled by a single entity. At Qbix we have an installed base of about 50,000 users running Calendar on Mac 24/7. We may be able to contribute this additional infrastructure if they opt in.


#97

Vaults for the alpha2 test network is run on DigitalOcean exclusively by Maidsafe. I don’t know how many instances or what size droplets.

Alpha3 will allow vaults at home (routing nodes, not full vaults) so all sorts of hardware and operator behaviours will be put to the test.


#98

Also the protocol used by SAFE will not be affected by ISPs banning servers on the traditional ports for them. My ISP, and they are strict, only ban servers on Web and email ports by blocking those ports. Although you can ask for them to be opened ever since they include uploads in the monthly quota, the ban was basically released.

For SAFE though, they can pass through firewalls, not just ISP server blocks, by the protocol used. So as long as the firewall is not a whitelist and allows normal traffic through then SAFE can operate.

Also SAFE does not have servers. So I can only assume you meant NODES, and they are simply sending packets and receiving them. The hole punching allows the communications to appear as outgoing with responses, thus not blocked by NATs and normal firewalls that allow typical traffic. (That includes the GFC)


#99

I really meant servers. I define a server as any program listening on a port. To listen on a port, you sometimes need to have permission from the ISP. Some ISPs block every port unless you ask them to open one.

However, a node can still operate if it can connect to other nodes, it simply opens a long-lived connection via a request. What I am saying, however, is that before doing this, the node cannot listen for requests, and after doing this, requests to the node must be routed through the nodes it is connected to. Which is what Kademlia does anyway.


#100

This is a major major aspect of going to market, btw.

Most companies which talk about “decentralized” blockchains wind up deploying all the infrastructure, so you have to trust that they are running the software you see on github. It’s quite “centralized” in a “control” sense.

And to invite other people to join the network (e.g. bitcoin miners) you have to reward them somehow. I guess farming is that way, but until SAFEcoin is developed you’ll want another way to do it. Bittorrent did it by making computers which downloaded software also seed that same software to others. You can’t really do that because you have Churn and Kademlia. So instead, perhaps for every X amount that a computer downloads, they have to also store and serve that amount for the network? And the SAFEcoin will offset this imbalance (e.g. pay to only download and not host).


#101

So do you ask permission to listen in on the ports that UDP (stateless) will respond to? The ISP has no way to know if a response is expected on that UDP port you sent a packet on 1 second before ?

What you describe is the ISP running their customers behind NATs. I don’t have experience with such ISPs, nor can give you an example of such a one. Do you know of such a one?

SAFE has developed its own “hole punching” protocol that will allow NODEs to communicate without the need to “listen” on ports in the traditional sense. This was important to develop since your home router would stop packets sent to ports like you described. So the issue is more basic than any ISP doing it, it is your own router that has to be traversed without opening up ports.

There are whole topics on this. Basically it is a stated goal of MAIDsafe that the SAFE network will be free for the world to access and get information. The reward structure for farmers is (will be) designed to compensate fairly the farmers.