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!