Security of PARSEC outside of SAFE integration

[fergish]

@JPL originated a great topic that relates Security of PARSEC related to the SAFE Network:

Security features of SAFE - a summary

On learning about PARSEC a few people have jumped in to question its vulnerability to a Sybil attack. Those in the know have pointed out that this would indeed be an issue were it not for other features such as node aging which make this sort of attack much more difficult. Security is maximised by having an interlocking set of features each covering the others’ vulnerabilities – strength in depth. I thought it might be helpful to list all the security features of SAFE and how they combine to war…

This is a great discussion, but it brings up a really good point as relates to other open-source use of PARSEC in other projects.

The is a voiced concern about security of the protocol from sybil and google attacks, etc. The above thread weighs in on that form the perspective of SAFE. But beyond that, what are the security implications for other applications that don’t have the depth of security integration that SAFE has?

I really don’t know, and think it bears address from those who know enough to discuss it.

[whiteoutmashups]

Haha I just asked this about 10 minutes ago

Great minds

MaidSafe Dev Update - May 24, 2018 - Introducing PARSEC

Hmm but isn’t PARSEC only applicable to SAFE? Not nano or IOTA or anything else, because they don’t have node ageing etc to secure it enough so it can work? Or do those projects have other things Instead, to fill in that gap? Else it seems that other projects with less of these security measures couldn’t be safe enough to use something like PARSEC

[pierrechevalier83]

I don’t think there is a general answer that’s applicable to everyone, but many ~Blockchain~ crypto projects have their own way of doing things with some consensus algorithm in the backend. Sometimes, it’s broadcast based, sometimes it uses leaders, so it only works on permissioned networks. Sometimes it has strong synchrony assumptions. Often it only provides probabilistic guarantees. I think these projects could often replace the “consensus” part of their algorithms because PARSEC is probably much more efficient or secure or less synchronous than whatever they are using now. How they mitigate Sybil attacks etc., they probably already have an answer for that since they managed to somehow make it work with the (probably) inferior consensus algorithms they used. I hope this makes sense, and also if anyone knows more about IOTA, etc., I would be interested in hearing what they do in particular

[fergish]

Hm . . . I though I had some grasp on this stuff, but I’m finding that grip slipping.

Let’s see if we can define the terms carefully, and see if we can tease anything out. Following are my best attempts to describe the elements involved. If we can hone these and agree on the terms for conversation, it may help be able to talk about this by more people.

---

transaction: any change of state ordered by a valid client. In the case of a token, this is credit/debit. In the case of a document, this would be delete/put/? changing the content by someone with controlling cryptographic keys.

consensus algorithm or mechanism: A means of arriving at a canonical (authoritative) agreement on the ordering of valid actions/transactions on a network. Validity of those is ensured by cryptographic keys, so that that is, in itself, not a part of the algorithm. The validity part is handled separately, except in regard sequence, since the sequence of add/delete, credit/debit affects the validity (i.e., a PUT inserting a word must arrive before a DELETE removing it for the sequence to be valid, even if both are properly signed validated cryptographically. Likewise with a credit needing to arrive prior to a debit).

Because, on a distributed network, information arrives at different nodes in different sequences (due to messaging lags, physical distances, etc.) the “true” sequence has to be sorted out and agreed upon. In most blockchain protocols, the sequence is fixed by the node (miner) that wins the proof of work challenge, or is designated by some other mechanism (as delegated proof of stake, etc.). This adds up to rotating central clearinghouse actors maintaining on common ledger, essentially requiring all participants to process and maintain a record of ALL transactions.

asynchronous consensus protocol or mechanism: this is any scheme by which much smaller sets of nodes validate the cryptographic validity of transactions and report the sequence as they experience it. The sequence is then agreed upon by interplay between nodes, and then finalized by whatever exact mechanics.

---

I’m sure there are other terms which, if we clearly define usage, will help, but that’s a start. Once these are laid out, perhaps then a restatement of where PARSEC fits into other settings might become more useful. (?)

[pierrechevalier83]

Good idea! It makes sense to try and set the vocabulary right.

I’m not sure I really get your definition of asynchronous consensus. In particular, I don’t see why it would have to apply to “smaller sets” of nodes.
Asynchronous consensus is consensus. What makes consensus asynchronous is the removal of any timing assumption. To be more specific, if the adversary was able to decide the time each communication (but timing must be finite and order of communications between honest nodes may not be modified) between nodes takes, that would not affect any of the two main properties of a consensus protocol: liveness and agreement.
Liveness: the protocol eventually outputs a value after a finite time.
Agreement: if a honest node decides a certain order of transactions, all honest nodes eventually decide the same order.
I will try to give a more complete answer later, when I’m in front of a computer with more time on my hands

[fergish]

Fabulous, Pierre.

I guess I skewed the asynchronous definition toward how the SAFE network handles transactions. I’ll edit and run it up the flag pole in a bit.

Now we’re in my element: definitions. Look forward to hashing it out.

[fergish]

@fergish

asynchronous consensus protocol or mechanism: this is any scheme by which much smaller sets of nodes validate the cryptographic validity of transactions and report the sequence as they experience it. The sequence is then agreed upon by interplay between nodes, and then finalized by whatever exact mechanics.

asynchronous consensus protocol or mechanism: this is any scheme by which nodes validate the cryptographic validity of transactions and report the sequence as they experience it. The sequence is then agreed upon by interplay between nodes, and then finalized by whatever exact mechanics. (see agreement and liveness below.

agreement: the purpose of agreement is to reflect truth rather than dictate it. If an honest node decides a certain order of transactions, all honest nodes eventually decide the same order.

liveness: because canonical agreement must be reached at some point for the network to continue to operate (be “alive”), the protocol eventually outputs a final value after a finite time. The length of that interval is an index of how alive and responsive the network is.

[pierrechevalier83]

I don’t know about the part of liveness where you mention “the length of that interval”.
When we speak of asynchronous protocols, there is 2 kinds of lengths of time: bounded or infinite. We say nothing of the actual time.
Liveness is a binary property: either the protocol maintains liveness or it doesn’t.
If liveness can’t be maintained in a fully asynchronous model, we add synchrony assumptions that can be more or less strong.
An example of a weak synchrony assumption is: all messages can be delayed for arbitrarily long times as long as the delays are random (i.e: not decided solely by the adversary). That’s the assumption PARSEC makes.

[fergish]

Great! I got carried away with my “making it all fit,” but the back-and-forth brings out a lot of understanding.

Thanks. I’ll tweak and resubmit, though following the whole process of getting to the best definition may be a lot more educational than the definition itself.

[fergish]

@fergish

liveness: because canonical agreement must be reached at some point for the network to continue to operate (be “alive”), the protocol eventually outputs a final value after a finite time. The length of that interval is an index of how alive and responsive the network is.

Actually, your clarifications fit great as written, with a little editing to fit.

liveness: because canonical agreement must be reached at some point for the network to continue to operate (be “alive”), the protocol eventually outputs a final value after a finite time.

When we speak of asynchronous protocols, there is 2 kinds of lengths of time: bounded or infinite. We say nothing of the actual time.

Liveness is a binary property–either the protocol maintains liveness or it doesn’t. If liveness cannot be maintained in a fully asynchronous model, we add synchrony assumptions that can be more or less strong.

An example of a weak synchrony assumption is “all messages can be delayed for arbitrarily long times as long as the delays are random (i.e: not decided solely by the adversary).” (That’s the assumption PARSEC makes.)

[ktorn]

I think the paper could use with a revision to clarify that sybil attacks are outside the scope of the protocol, with some references to existing solutions (i.e. PoR, PoW, PoS, etc). As it stands it just looks like an oversight. We know it isn’t, but outsiders don’t.

[riddim]

though the paper clearly states that it’s about the number of nodes (“that less than a third of participating nodes” in the second sentence …) not the individuals behind those nodes i tend to agree that an additional clarifying statement might be helpful … i’ve seen many people who somehow think the attack should be covered (/was missed) by the paper …

EDIT:
ps: …or maybe it doesn’t need to be written in the paper itself but somewhere ‘around it’ (because it is unambiguous in the first place … if you don’t expect this attack vector to be covered …) … and in my opinion it doesn’t make sense to really include it … if you start explaining what is not scope of something … it just doesn’t make sense … (e.g. the transport protocol is not covered as well, and if you steal everybodys network connection the network is dead too … if you just make a global shutdown for electricity safe is dead as well … mentioning what you don’t cover really doesn’t make sense at all … except in this case many people somehow think it should be covered …)

[wes]

When I first read the paper I thought “how can you just assume at least 2/3 of the group is not bad actors? What a faulty assertion in a BFT paper.”. I generally understand the working principles of SAFE, and understand how that’s possible in the context of this whole project as a unit, but that first pang of thought has stuck with me.
With that memory as context, I think it would be worth a modification / mention in the paper that "how >2/3 is achieved and maintained is discussed in ‘XXX reference paper’ " or a mention of “use your own honesty system” (PoW, w/e) or something to that effect. If you read the paper without context (an issue in itself, I know), it does sound like an oversight.

[dirvine]

@wes

“how can you just assume at least 2/3 of the group is not bad actors? What a faulty assertion in a BFT paper.”.

In the current state of the art is BFT algorithms this is the mathematical limit for the algorithm itself. I doubt you will find a BFT algorithm based on consensus within a network that is resistant to >1/3 bad actors. I am talking of current PBFT type algorithms here. Sync are a problem with a single bad actor (CAP) and the holy grail is async BFT. However the 1/3 limit is the current maths limit, until we know more

[reivanen]

What about Bitcoin tolerating 49% bad actor?

[dirvine]

It is arguable if bitcoin is a BFT and also if it is secure up to 50% (some say its only secure to 25%), but anyway, if we assume it is BFT and secure to 50% then it is way to slow for a consensus algorithm. Such algos really look at thousands of transactions per second (per shard). So we could say bitcoin is a BFT >50% byzantine node tolerant, but it is not proven mathematically to be a BFT And 50% tolerant and that is for good reason.

Semantics aside, even if it were, it is way too slow for a system that needs to record changes to data structs at any speed usable. IT is fine for a huge, slow public ledger though.

[draw]

It could be that I don’t understand it correctly and/or someone else has already done the math.
But in the case if somebody has for example 1/3 of all vaults of the complete SAFE Network, his vaults will be distributed over all the sections: so in some sections he has more than 1/3 (and can sabotage that section) and in other he has less than 1/3 and he can’t sabotage.
But what if he has for instance 10% of all vaults: which % of sections can he sabotage (statistically)?
And from what % of total sections corrupted will there be a real problem in usability of the network?

[pierrechevalier83]

This is where node ageing comes into play: you don’t only need a third of the nodes in the section. You need a third of the valid voters, so your nodes must age for sufficiently long to become elders. That means behaving correctly and providing resources to the network for a long time. I think doing the maths on the statistics is not easy right now because there are so many details that we still need to decide on with more data from the testnets (for instance: section size, how many elders per section and such). But we will design it in order to minimise the risk of a powerful actor (think NSA) being able to take the network down.

[draw]

I understand, we have patience
What I’m getting at: which (estimated) percentage of total vaults must a bad actor have to make the complete network unusable. And more specifically: one who has the patience/money to get past the node ageing and other checks. That could be the NSA.
An extra thing one could maybe do, store files with ‘parity/RAID’ , so that if one/a couple of chunks are missing, it can be recovered from the chunks which are correct. But maybe that isn’t possible (self encryption or another reason).

[neo]

@pierrechevalier83

This is where node ageing comes into play: you don’t only need a third of the nodes in the section. You need a third of the valid voters, so your nodes must age for sufficiently long to become elders.

@draw
And sections only allow a very small number of new nodes at any one time. So assuming others are joining at the same time the attacker may only be adding 1/3 of the new nodes too. So to get to 1/3 of aged nodes is going to take a long time. Then you have sections splitting before bad actor can get to 1/3 of aged nodes which complexes the issue.

Then @draw if you get 1/3 of all nodes as bad nodes, they can only cripple the section but not take it over. Then the 1/3 bad nodes have to coordinate too. It is unlikely any one bad actor is going to control 1/3 of all nodes and so what infighting is going to happen between the various bad actors that make up the group controlling the 1/3 of all nodes.

@draw

That could be the NSA

Cheaper for the NSA to infect with malware all the computers in USA and elsewhere than to setup all those nodes and coordinate them acting bad when they have 1/3 of nodes with voting rights.

Its a case that we have to be prepared to restart the network while its small and still testsafecoin if we get bad actors with lots of nodes. We restart with even more nodes privately and add people till the network is so much larger than before and see if it can outgrow whatever group. Once the network is global then I doubt any one group could have enough nodes to get to 67% in order to control sections