Security of PARSEC outside of SAFE integration

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

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.

9 Likes

Haha I just asked this about 10 minutes ago :joy:

Great minds

7 Likes

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 :grinning:

18 Likes

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. (?)

11 Likes

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 :slight_smile:

18 Likes

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.

7 Likes

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.

5 Likes

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.

12 Likes

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.

6 Likes

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.)

6 Likes

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.

11 Likes

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 ā€¦)

6 Likes

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.

4 Likes

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 :wink:

11 Likes

What about Bitcoin tolerating 49% bad actor?

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.

17 Likes

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?

3 Likes

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.

18 Likes

I understand, we have patience :wink:
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).

@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.

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

7 Likes