Consensus 28/32 or 8/8?

Not so sure this is naive at all. If we take a network of one section then this holds true. This is the starting point I was trying to get to.

So the statistical thing about the birthday paradox will mean we need to consider more sections and look at it a bit different IMO. We are looking at a situation where there could be lots and lots of nodes trying to join and with the birthday paradox in play then we are saying an attacker who had 13% of all nodes wanting to join. The chance they all join the same section is what we are looking at here, so X sections against where they join. This is where the bday paradox situation arises.

Assuming you agree with the above then we have a few considerations to make. If we ignore infants and adults as well as node age (to take time and effort out of the attack vector) and have lots of sections then you can carry out such statistical analysis. I do agree with that.

So PARSEC is a single section network as described in the paper/rfc etc. This does hold that it is secure against 1/3 bad actors. That is how these papers work AFAIK, assume a single static network with no changes and there you go. PARSEC for an apples to apples comparison of other consensus algorithms does this. It goes a little further to show a common/concrete coin to deal with adversaries trying to stall consensus.

Then back to the bigger question I think you are raising, assuming no node age and a population of nodes to join a network. If we restart the network X times (say 3226 times as per your example) then we probably can say that given an equal chance of joining there may be a 99% probability a 13% holder of nodes could disrupt a section.

I hope I am on track here @tfa Are you in agreement so far?

9 Likes

In my mind PARSEC was a protocol within a section. You made me doubt about this, so I looked for some confirmations and found these ones:

  • first sentence of RFC:

    In this RFC, we propose an algorithm which will allow a section of network nodes to reach consensus on the validity and order of network events by voting on events and using a gossip protocol to disseminate these votes amongst themselves.

  • node states in routing/src/data_chain/node_state.rs which is linked from the topic in dev forum

/// The state of a node in a given section as voted for by the other elders in that section.
#[derive(Serialize, Deserialize, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy, Debug)]
pub enum State {
    /// Node has been accepted to this section as an elder.  May have been relocated here, or may
    /// have come back via a merge or via a promotion from adult.
    ElderLive,
    /// Node has disconnected.  Can rejoin here once in order to be relocated.
    ElderOffline,
    /// Node has been accepted to this new section (indicated by `to`) as a result of a section
    /// splitting.
    ElderSplitTo {
        /// The section prefix after splitting.
        to: Prefix,
    },
    /// Node has been demoted to non-elder due to an older node being made `Live` here and
    /// displacing this one.
    ElderDemoted,
    /// Node has been chosen to be relocated to another section.
    ElderRelocated,
    /// Node was marked as `ElderOffline` and has rejoined here.  Only one rejoin attempt is
    /// allowed.
    ElderRejoined,
    /// Node has been accepted here as a non-elder via a relocation, a merge or a demotion.
    NonElderLive,
    /// Node has disconnected.  Can rejoin here once in order to be relocated.
    NonElderOffline,
    /// Node has been accepted to this new section (indicated by `to`) as a result of a section
    /// splitting.
    NonElderSplitTo {
        /// The section prefix after splitting.
        to: Prefix,
    },
    /// Node has been chosen to be relocated to another section.
    NonElderRelocated,
    /// Node was marked as `NonElderOffline` and has rejoined here.  Only one rejoin attempt is
    /// allowed.
    NonElderRejoined,
}

Clearly, the protocol is for reaching consensus within a section and so the birthday paradox is applicable.

3 Likes

It really is crossing a lot of perhaps confusing lines to think/state that. I suspect we are talking at cross-purposes. Our code for sure will consider sections, let’s call that sharding.

So the process we are taking is

  1. White-paper plus RFC for a static permissioned network (i.e. no churn or sections). This is where we are today in papers, but not code as that has progressed much further.

  2. White-paper for dynamic membership of a network (or a single section in a single section network). This is currently being worked on. Hopefully to be published very soon.

  3. White-paper for full sharding (many section networks with dynamic membership and secure message relay). Published last.

You are sort of considering point 3 using the info we have provided in point 1, if that makes sense.

For SAFE we would have to look at point 3 plus node age, penalties, and safecoin.

I really think what you are doing is valuable, but it is just a bit confusing right now. A few years back we considered the birthday paradox quite a bit when nodes restarted direct onto the network with a “random” id, This is the case you are currently looking at, but we do need to factor in all the other parts.

This is less to do with valid quorums and much more to do with the random creation of subsets of a population. It is valid but requires ignoring certain aspects of the network. In saying that it is well worthwhile to do this a bit at a time, a bit like mentioned above (the 3 steps) and add in random relocation and node age etc. IF we can analyse each step like this then it will help everyone to be clear on every step and more importantly why penalties, age, relocation etc. all matter and hopefully we can calculate how much.

6 Likes

Thinking further @tfa I suspect it is the 1/3 2/3 thing that is being confused with a birthday paradox situation. It’s not quorum, that just means you need more tries (days in year in the paradox) as a higher quorum is kinda equivalent to just requiring more birthdays in common.

I suspect that is the confusion.

So if you then look at it like this, we are onto something. So forget quorum % and consider that even with points 1, 2 and 3 in place there exists a birthday paradox if there are no other mechanisms in play. That may be easier. The Byzantine figure t in the papers (1/3) then only affects the calculation of that paradox for a given percentage probability of controlling/disturbing a section.

Sorry, all this is quite short in terms of description, I am trying to take a week or 2 on holiday, so trying to limit my forum/slack etc. time and get some headspace. I will hang around as usual though for interesting things like this and Mav’s other brainstorm topic(s) :wink:

10 Likes

well … but all the dynamic membership and penalties, age and relocation doesn’t really matter imo … an attacker would launch the attack only if he’s certain he will succeed … so he’ll behave good as long as he thinks he has a chance to succeed … and if he’s around from the beginning his chances are much higher to supply a significant amount of elders …

if you constantly keep throwing vaults at the network and keep aging those without misbehaving and just waiting for your chance… it is like throwing dice i would say who in the network is a good guy and who is one of the evil nodes … so here we go with a monte carlo simulation … 20 rounds with 100k sections … 32 elders per section and 35% network share of the attacker

image

sure - the standard-numpy-random-numbers-generator is probably not super-random … but still it meets the expectation to be successfull once in a while … (but not super-super-mega often)

ps: and sorry for distracting you from your holiday :-/

5 Likes

Agree. Parsec only defines, clearly, the percentages necessary to avoid reaching consensus or to control a section but it does not modify that, in a permissionless network, if the attacker has enough power, and patience, it will end up bothering or controlling a section.

BTW, all your calculations are consistent with those made by @mav months ago

5 Likes

For the bday paradox I am agreeing, I am really meaning that it does not make the t figure of 1/3 naive. The quorum figures are well established mathematically, however not really related to stopping the birthday paradox, a higher % quorum just makes it more difficult. I think it’s best to just say regardless of all of this if we have a network with many sections (which disjoint sections vastly reduces as pure kademlia has as many sections as addresses :wink: ) then we need mechnisms that distribute attackers as efficiently as possible and at the same time drive costs of such an attack as high as possible.

So to calculate the % an attacker needs we do need to consider

  1. The quorum
  2. Number of sections
  3. Nodes per section (you and @tfa are doing this part and brilliantly)
    Then
  4. Node age (infants, adults etc. to force time and effort to be increased by a considerable amount, i.e. an attack can be reasoned to be, if it costs the attacker X much more than any possible return then it’s more secure (never totally)).
  5. Forced relocation
  6. Targetted relocation (not allowing a node to create an address in a section, but create an address between the furthest 2 nodes in a section).
  7. Penalties (huge area as @mav poked about at a good bit, but much more to do there).
  8. I am sure I have forgotten a lot here …

After all that there is the economics (or cryptoeconomics as some say in a confusing and elitest way :wink: ) Where safecoin comes in, I prefer to keep this to way last as humans are, well humans :smiley: :smiley:

8 Likes

Okay I think I need to read about disjoint sections maybe there is details that I should be aware of…

… I even was thinking that it might make sense to release a fork of the vault software that performs this attack… So many people can try to succeed and hopefully block each other… But then again it didn’t seem to me to be the best approach …

Ps:

Problem is that you cannot identify an attacker until he attacks… But ofc you are well aware of that… Preventing someone from being able to target a specific section is essential but doesn’t prevent statistical local effects to kick in…

(and if you would need to be in control of 2 specific sections to perform such an attack that would drive the price for such an attack significantly higher than just demanding a higher % quorum I would think)

+we need to consider someone just trying to disrupt… And for the local effects to kick in on this the network share you need is not super high… So I think there needs to be a backup plan in case this happens …

I am mainly thinking loud here and hope there is/will be more than I see right now… Because if not mavs mass-vault-control software (not entirely sure if he released that… Anyway), knowing some rust and renting many servers early on for some weeks might turn out to be very beneficial …

5 Likes

Agreed, however there is further thought here as well. Attack time. By that I mean, if the network just lets anyone start a node and be an active voting member at any time then this attack is really a big issue. However there are 2 things to consider there.

  1. One infant per section (limits a flood of new nodes to a small extent).

  2. Only allow infants when needed.

  3. Is an area of debate. I prefer the network balances its resources verses its requirements. So like safecoin balancing, where the network encourages more vaults by making more payments in times of the network needing more space (etc.). In the same way, I feel the network should not allow new nodes to join unless it needs them. This is the debate and cost of security I feel.

Then an attacker not only needs to let his nodes age but also needs to wait in a queue to join the network. As this is not an instant join of 13% of nodes (say) then a 13% attack would be much more difficult. If the time to join was over a period, then its likely that “good” nodes will also be trying to join, so diluting an attackers army of bad nodes up front.

The downside is folk will find it harder to farm, but that is perhaps natural? (debate ensues, madness in the streets and cries of doom and destruction can be heard all over :smiley: :smiley: ) Seriously though it needs consideration. It is probably easier to loosen the security of these parts over time, but that needs evaluated.

9 Likes

The other side of this equation is also important: what is the scale of damaging actions from one malevolent section? From two, etc?

But I’d rather you had your break David than answer now. I’m just pointing out that it is part of the equation, and makes a 51% of network blockchain attack which allows the attacker complete control, a very different proposition to a 12% of network attack (assuming that’s accurate) where the attacker controls a section and has some fraction of control.

7 Likes

One section can be completely damaging if taken over, right now. There are mitigations like require chains of sections to make a safecoin etc. but I doubt these are needed.

I don’t think we have a 12% attack really, or anywhere near that, but it’s much more complex than a single figure as you see above. The bday pardox is like creating many networks from a single population and seeing a % such as 12% bad nodes can exist in one of those networks as the quorum (whatever that quorum is). So I see this much as bitcoins 25 || >50% attack where a % is not so important, the cost is though. I suspect our % is much closer to >33% (and can be way above that, but this means section chains) than it is to 12 or 13%, but the cost in terms of both time and money are important.

People consider money only as the measure, but I also consider time. I will try and explain in my clumsy way why a destruction attack (not vandalism or control) on a distributed network is easy if you can rent enough resource and kill the network. Now in our case, a botnet could be used, but if the botnet cannot have nodes that could store the data (like recent IOT attack from fridges :smiley: ) then it fails. Also if a botnet needs to run for months it becomes much more difficult as botnets get taken down, folk switch of their machines and the botnet cannot do anything about that etc.

This is my break :smiley: these convos are important to go over again and again I feel. This is a great way to explore your mind, well I feel that way anyhow :wink:

10 Likes

I know it’s nit picky, and it won’t change the numbers much, but 35% breaks the first assumption the white paper makes about PARSEC working. Needs 2/3 or more honest nodes.

1 Like

Well - with an average of 35% globally for the network we statistically manage to get locally 2/3 majority somewhere in the network … So ability to print safecoin… I wasn’t talking about ‘only disrupting the network’ - I wanted to point out that with a way less impressive share than the 2/3 majority it might be possible to do very very very bad stuff (if I’m not missing something…)

… This simple calculation ofc doesn’t consider time and money involved to get there… (and different parties trying it and blocking each other…)…

1 Like

OK that’s enlightening, and I will stop thinking that taking over one section isn’t a total disaster! Thanks David… I think :smile:

3 Likes

I see now. Looking at it from the opposite side. That makes sense. Thanks.

2 Likes

that’s the part where I’m not that sure - i have a hard time believing we are safe enough without chaining at least 2 sections …
…to get a local majority in one section is possible imho … but to get a local majority in the right 2 sections … that’s something where this effect kicks in:

absolutely no realistic chance without 50% ownership of elders … that doesn’t sound possible to me - even with initial advantage not… :roll_eyes:

6 Likes

Some of the maths is a bit over my head, but after struggling through, this thread is certainly starting to help things click for me and improve my understanding of some parts of the structure of the network, if nothing else!
Anyway, I’ll let the discussion go on. Thanks for the hard work everyone :grinning:

7 Likes

side note: an attacker would even be allowed to know which other section he would need to control for success for having this [roughly double of difficulty] - he only must not have an influence on the decision which other section the relevant one is …

1 Like

Still a bit rough but quite usable

https://github.com/iancoleman/safe_network_cloud_control

Will improve and expand on it when the next testnet comes out

10 Likes

you’re the best :slight_smile: :ok_hand: thx!

4 Likes