Consensus 28/32 or 8/8?


#61

I’m pretty confident @tfa is right here - that’s how I understood it too


#62

Ok, I’ll have to go back and read it again. This changes my concept of things.


#63

My fault for not being clear, the current notion is 50% of Elders age and >50% of Elders, all subject to change but good to start somewhere and reason from there.


#64

Yes a common misconception of random distributions is that its a even disruption. Off the cuff I would have said about 15-16% (half of the even distribution), and the figures show 12%

This means adding and getting 13.6% new nodes added as elders which will give you the 12% in the end. Maybe add an aux graph that shows the number (%age) of the increase in the number of elders required to get there. This to me is the more realistic figure since that is what an attacker would be looking to achieve. In other words the attacker sees 88000 elders and they see that they need to get 12000 of their nodes as elders. And obviously this assumes no one else has their nodes added as elders in the meantime.

Of course this doesn’t mean its a case of throwing 12000 new nodes (13.6%) of the 88000 elder node strong network will get you 12% of elders. Each section will limit the number of new nodes it has at any one time. Will this create a more even distribution of new nodes and consequentially in most cases more even distribution elders rather than random distribution???

For disruption or taking over the section there has to be coordination between the bad actor nodes. These bad actor nodes have to be good nodes till they get to be elders and then only when enough are elders can they cause disruption or take over. This requires coordination since if they act bad too early then the other elders will kick them out. They need to know when there is enough bad actor nodes in order to disrupt/take over AND act bad together (or at least vote against kicking out the other ones)

This means a single attacker or group of attackers have to be in agreement as to goal and timing for the disruption or takeover and have at least one section with 33+% or 67+% and more importantly have coordination of their bad nodes. Otherwise they will fail. If one of the attackers has less than 33+% and starts an attack then the others will kick out those elders.

Not quite. There will be disruptions across neighbouring sections but not necessarily bad. Yes its bad as in if a person loses a finger.

Also you need to distinguish between a section being disrupted and a section being taken over. If a section is disrupted then the network will have troubles for a while, if a section is taken over then a portion of the safecoin is taken over by the attacker and the data stored in that section can be corrupted/changed/destroyed.

So yes its a really bad situation and one that would see confidence in the network drop. But it doesn’t necessarily mean the network is bad. It is not a “complete trust” between sections. Each section still has to follow the protocol or else the other sections will not listen. This would be another level of attack and much harder to coordinate.

That is my understanding too.

@tfa, thanks for the graphs. Great work again

It will be interesting to see the figures from alpha 3 & 4 as average rate of adding new nodes till they become elders with the section splitting occurring. This will give us a better indication as to how many nodes an attacker (group?) needs to add and how many will become elders in what time frame.

EDIT: Also @tfa what do you think will happen when new nodes in a section is limited and this has the effect of more evenly distributing new (attacker) nodes across the network’s sections. This would have a carry on effect of the attacker nodes distribution as they become elders. Off the cuff I’d say this will cause a more even distribution than the random one you graphed above. Obviously then a more targetted attack would be needed and I thought about graphing the attack where you target a section. But the unknowns (new nodes/section and how fast to age) made it nonsensical before alpha 3 &/or 4


#65

I’m still not clear on this.

Am I understanding the ratios-and-consequences as below correctly?

  • 1/3 elders in a section to disrupt decisions on section membership (parsec)
  • 2/3 elders in a section to control decisions on section membership (parsec)
  • 1/2 elders in a section to control decisions on data content (quorum for close group consensus)
  • ?/? nodes? in a section to disrupt/control secure messaging between sections

Primary source for this is available in RFC-0045 - Node Ageing - Consensus Measurement

“A group consensus will require >50% of nodes and >50% of the age of the whole group.”

As David says, this is not the final say by any stretch but it’s the current state of thinking.

Is this influenced more by the ‘disallow rule’ than by the groupsize? Splitting and merging is affected mainly by groupsize, but the total section size depends a lot on how many young vaults are allowed to join, which is primarily determined by disallow rule… or not?


#66

Correct

It seems the current notion, which seems is not PARSEC is as you state in your post - BUT all subject to change :wink:

PARSEC rfc is pretty clear that 2/3 of elders (referred to as 2N/3) must agree for consensus


#67

Confirmation of my figures with R statistical package which implements the generalized birthday paradox and gives similar results:

  • 11.7% ratio of malicious elders to disrupt one section
  • 31.9% ratio of malicious elders to control one section

The number of classes (= number of days in a year) is the number of sections (numbers of elders / section size), in my example: 100000 / 31.


#68

Previous results were with 99% probability. With 50% probability, the results are worse:

qbirthday(prob = 0.5, classes = 100000/31, coincident = 11)
[1] 9320
qbirthday(prob = 0.5, classes = 100000/31, coincident = 21)
[1] 27430

For example, the first result means that the attacker needs to own 9320 nodes in a network of 100000 nodes to have a 50% probability to disrupt one section.


#69

Great figures, tfa!

I do wonder what number is ideal here though. We have had recent reports of 50% attacks on small POW chains, but for Bitcoin, 50% seems utterly unachievable. The question must boil down to not one of percentages but to absolute cost in a traditional sense (e.g. dollars).

Obviously, we all want maximum security for minimal cost, but we all have our price and level of security that we find desirable.

Anyway, just wanted to mention this. We can never achieve absolute security and 50% is as arbitrary as 10%. I suppose it very much depends ‘of what’.


#70

Well - in which time span 50%? - does it mean an attacker will statistically be in possession of a group 50% of the time? Then how many nodes would it take me to be in possession of a group for 1% of the time? (that would be roughly 15 minutes each 24 hours - should be enough to perform a powerful attack)


#71

Isn’t this a miss application of the class paradox.

What those results are telling you is to have (prob 0.5, classes 365, coincident 2) you need a class size of 23 students

And for (prob 0.99 classes 3226, coincident 11) then you need a class size of 11796. Meaning a school_class_room with 11796 children to have ANY 11 children with the same birthdate if there were 3226 days in a year. OR section with 11796 elders to have 11 aligned bad actors

This is not saying you have 11 aligned bad actor elders in a section with 31 elders.


#72

I agree with this:

But I don’t understand that:

You seem to associate class with section. Let’s avoid "class” term because it is ambiguous. This is what you tried to do with school_class_room term but let’s talk about sets instead and use the following terms:

Standard birthday paradox Safe network
People Elders
Year Network
Day Section
A year with 365 days A network with 3226 sections
People with the same birthday Elders in the same section

The result of:

qbirthday(prob = 0.5, classes = 365, coincident = 2)
[1] 23

Means that in a set of 23 people you have 50% probabilities to have at least 2 people with the same birthday.

In the same way, the result of:

qbirthday(prob = 0.99, classes = 3226, coincident = 11)
[1] 11769

Means that in a set of 11769 elders you have 99% probabilities to have at least 11 elders in the same section.

Note: A possible explanation of the slight differences between my Excel file and the R package is that I suppose that each section has exactly 31 elders, whereas the qbirthday function doesn’t make this assumption, which is a better model of reality.


#73

I’ll have another look when I am fresh. Late here. But in any case the birthday paradox is still not correct probability to use for this as it does not have the constraints that sections do.

And I see you even point it out.

But it is not a better model. Because it allows for sections to have 1000 elders or 5 elders. Your Excel file is a better approximation for the very reason that it models sections better. If you could add constraints to the birthday paradox then maybe.

Anyhow better to stick to the more accurate model.

And I agree that it is woefully small amounts when viewed on its own. But we know the network doesn’t allow the random distribution of new nodes to sections already.

  • new nodes can only join a section if allowed.
    • once a section has 1 new nodes (currently) and likely to be increased slightly when the section sizes increase, then it rejects any more from joining.
    • This means bad actor nodes will end up being evenly distributed across the sections rather than randomly because they need to find a section that will accept them. Not sure if that will mean restarting and trying again of if the code automatically relocates multiple times.
  • new nodes will eventually progress to be elders as sections grow and split.
    • this will still mean in general with different timings that these bad actor nodes grow up into elders at similar rates which maintains the even distribution.
  • So an analysis of random distributions while informative is made invalid by this severe limiting of how many new nodes a section will have at any one time.
  • Also a major assumption is that these bad actor nodes are added at the same time the other nodes that end up being the other around 90000 elders.

#74

I am not sure my model is better but anyway in the end the figures remain similar and more importantly, I don’t see them as blocking.

A relative percentage doesn’t matter, what is important is the concrete numbers of vaults an attacker must maintain during a long time before they become elders. And this will be reasonably possible only during the beginning of the network.

Also, the situation can be improved by choosing an even greater section size. For example, with a network with 99968 elders, 1562 sections and a section size 64, the figures become:

Consensus 22/64

qbirthday(prob = 0.5, classes = 1562, coincident = 22)
[1] 15055

(which means 15055 elders are needed to disrupt one section)

Consensus 43/64

qbirthday(prob = 0.5, classes = 1562, coincident = 43)
[1] 38185

(which means 38185 elders are needed to control one section)

Notes:

  • I think a 50% probability is enough for an attacker because he just has to wait a little more if he is unlucky after the long delay for his vaults to become elders.

  • I tend to choose a section size of type 3N+1, for a blocking minority N+1 and a control majority 2N+1. It is the optimal choice for me.


#75

hmhmmm - tried to go with some calculations too … not sure if i don’t have a very stupid mistake there … but here we go

(there is an interactive html print as well in the repo showing the result)

is roughly what my calculations suggest :thinking:

(and for the record - with my estimations the numbers don’t change a lot with groupsize 64)

…well…but to perform this attack you need to maintain not only a constantly high percentage of elders … you need to have roughly that amount of total global node count since all nodes are aging … and if you only have that percentage of elders you’d soon no longer have the targeted share …so we are talking about having 10/35% of nodes in the early days + maintaining 10% of global network size constantly

ps: well - but results like this probably were to be expected with only a needed 2/3 majority :thinking: that’s why maidsafe wen’t with the 28/32 in the beginning wasn’t it?

28/32 needed for consensus:

pps:
okay … so … if you want to get a share of 35% of the elders … you need to do:

  1. add 35% of nodes … and if there’s 32 elders in 200 nodes per group you would be required to
  2. wait until the network has grown to ~6 times the size it is when you started the attack until your nodes would become elders … to maintain your share
  3. you should expand to 6* the nodes you already added in the process (so 2x of what the network size was when you started the attack)

… looks more benefitial to me to add 100% node count of current network size once you start the attack and to hope for a time windows where a major proportion of your nodes become elders and you have a >40% share of elders …

(now the question is … will you manage to add 100% of nodes … because of the join-rate-limit you won’t be the only one trying … so you need to outnumber others who want to join the network …)


#76

well i kept thinking about this a bit … and thought of the ‘watcher’ proposal and then i thought ‘what would happen if one randomly selected other group would check on a group on a regular basis and could nuke that group somehow if it would be bad (or have it re-checked if suspicious and nuked if the others agree)’

of course that would introduce additional complexity in the system (and obviously my calculation has an error…) but what i did was just adding the scenario with a re-check (just multiplying the initial probability of controling a group with the probability of controlling a randomly selected other group as well):

that would push the chances for a sucessfull conquering (realistically) to somewhere ~50% network share

though my calculations are wrong :innocent: this indicates that a checkup by another group would largely increase stability agains bad actors conquering the whole thing (disruption still would be the same - but not sure if that would be a problem if a disrupted section just could get kicked out of the network [as long as nobody tries to just get half the network kicked out to overload the rest of the network with data…])

especially when doing the calculation with 100 000 000 elders instead of 100 000 elders a re-check would have a large influence

(on the other hand i probably should first get my numbers right before making other statements … that drop with the re-check in the end doesn’t make sense …)

[but it totally makes sense that if the network selects who checks on a group the probability of success suddenly is again highly dependent of the probability of being in control of one group … no matter how far off from the average probability the network happens to be locally]


#77

Your curves are nice but I am afraid there is an error in your calculations.

I suppose that x is the fraction of bad nodes and y the fraction of bad sections. If that’s right, then it is not possible that about 13% of bad nodes disrupt 100% of sections (because for that you need much more than 33% of bad nodes).

Edit: see clarifications from @riddim


#78

well - i’m sure there is an error on my calculations but it’s not a this obvious one …

y is the probability of having at least one bad section
(so its 1-[probability-of-all-secions-are-good])


#79

Sorry for that.

But then your results are very similar to mine. So, what is the error about them?


#80

the drop when we head above 90% network control … but when i look at my calculation of the probability for controlling a section … i do a sum there over the probability of [having 1-X good actors] in a group … if you get to 100% chances for a node being good is 0 (still everything below 100% control should look different i would have expected :thinking: ) … i should probably do a loop for having bad nodes and rethink …

okay - changed that loop … not entirely sure why i don’t end up with 0.5 probability at the [more than 15-> 16 out of 32] for half of the network in my control …

but the larger picture didn’t change a lot (100k elders again)