Analysing the google attack

Community Blog Posts
#77

I think this has to be a fundamental principle. Once you start down the path of making PoW in order to solve attacks then where does it stop.

Yes, any attacker can have a smaller number of very powerful number crunchers to solve things for the attacking NODES and since the NODES for the most part do not need the number crushing the ratio of number crunchers to NODES is small indeed. Another reason why PoW will not solve the security issue.

EDIT In times past the system was that a node joining a group (even after relocation) generated their key then the group it contacts then gives it another key thus making it harder to target a group. That seems to have changed now and is a loss in my mind. Even using a Fn of the node’s key + section data is making it easier to attack.

4 Likes
#78

Certainly but just not at the cost of the network having a negative effect facilitating the same. A balance here like everything else is key imo. Note I’m not referring to PoW or any arbitrary complication but just in general, its easier almost asking the question of how any X helps the network than what sounds nicer. Allowing everyone to join with ease while it sounds great might also not be the best for the network if these nodes didn’t help much but increase the hops for general operation. Thereby also helping prevent spam attacks and sorts…

I’m slightly confused with the targeting scenarios, so if we consider an example of a node being able to calculate where it’d be nice for it to join the network and generates the initial key accordingly to then get relocated say to a pre-calculated target Y section(if recursive relocation dst is computed too), not sure I get how this is affecting the network btw if this node still isnt an elder of the section and in this case is an infant(new node) and is going to then get relocated later on based on the churn events or so on … Lack of quorum and potential node age loss(thereby loosing elder privileges and so on if trying to restart) should still hold right? or are we discussing something else here in terms of not wanting even a single node to choose even its infant section if it so went about trying to do so?

EDIT:

Just had a chat with @dirvine there about ^^ and think I got what the discussion was about in terms of a balanced network and relocation knowledge being local based and thereby allowing a group of nodes to get relocated roughly grouped and allow for potential attacks while the nodes are ageing themselves.

While discussing that what we were thinking of is ofc see how likely such a thing would be via simulations, but for a moment if we consider it is likely and we want to avoid it even if just being safe, couple options ofcs exist wherein like the thread so far has explored use randomness to achieve the same.

So simply not have relocation based on just the section that needs a new node and range to relocate to, but also structure it such that when a relocation trigger say occurs(assuming for now its a churn event), use that Hash(churn-node-id-xor-name) as the dst section where the relocated node is being sent to, however when the rpc gets to this dst section, they can then do the balanced relocate themselves which if still happens local to them is still not hopefully deterministic from the src.

So in essence have balanced node relocation and a relocation range, however make the first hop of the relocation be based on the randomness(hash of churning node name) and then let the balance relocation kick in recursively which should hopefully spoil being able to compute rough dst locations after the initial join process.

10 Likes
#79

Thanks for your interest in all of this!

As I mentioned in another thread on the dev forum, your observation that the simulation doesn’t take off right now is entirely correct. This is because it is outdated, and doesn’t actually use the same rules as @mav’s simulation. We were aware that it needed more work, but other issues with higher priority appeared and updating the simulation has been postponed.

Since we are now ready to resume work on it, let me outline a rough plan for the nearest future here.

First, to address the problem that the initial section doesn’t split, we will modify the rule for splitting a bit. We were requiring enough elders and adults in the section, so that the new sections will each have a complete group - this will be enforced only if we already have a complete group in the current section, otherwise we will just require that the section has enough peers for both of the resulting section to have GROUP_SIZE+BUFFER peers (as opposed to peers with age > 4).

Second, and this will be a quick test - we will run our simulation to see what happens if peers join at age 4 instead of 1. I see that @mav already conducted such tests, but getting more independent results will always be beneficial :wink:

Then, when we have those results, we’ll see if we are satisfied with the way ageing works, or if we want some more changes to the rules in order to make the network operations more smooth.

16 Likes
#80

us satisfied? you’re a changed man in the new year @bart :wink: I’d suspect we certainly need additional relocation triggers even something like mutation operations being used accordingly for the same(not saying GET here cos its a free action that can get spammed too ofc) just so we dont end up with stalling sections and facilitate network growth.

11 Likes
#81

Thanks for your clarification and glad to hear what you had to say

To be clear this is what I was referring to.

There will always be a certain amount of work to do anything and the balance will mean we are not looking to PoW to solve security issues which should have a cleaner simpler solution.

One would expect of course there are minimum requirements. We just don’t want to see people joining the network but their NODE is at 50+% CPU (or GPU) just to prove they are a good guy and not an attacker. The easier is in terms of being able to use cheap hardware and SAFE using logic rather than PoW to “prove” genuine (or reduce effects of bad actors). Also that the Node is able to be farming in a reasonable time.

9 Likes
#82

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

http://www.redorbit.com/news/science/1112943343/ant-colonies-turn-unwelcome-guests-into-armies-091013/

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

6 Likes
What’s up today?
#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!

15 Likes
#84

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

12 Likes
#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!

3 Likes
#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.

12 Likes
#87

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

6 Likes
#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

3 Likes
#90

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

2 Likes
#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:

8 Likes
#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.

7 Likes
#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!

3 Likes
#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?

11 Likes
#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.

1 Like
#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.

1 Like