... so CAP theorem is disproven? This would imply that linearizable distributed transactions (in less byzantine networks) would be possible beyond what CAP enables. Or are they relying on availability assumptions?
Protocol for Asynchronous, Reliable, Secure and Efficient Consensus [pdf]
11–20 of 22 posts
Re: Protocol for Asynchronous, Reliable, Secure and Efficient Consensus [pdf]
#12Without proof-of-work, what protects consenus from the sybil attack? As I understood, after quick scan of the paper, consensus is achieved by simple majority vote. So if I setup 10,000 docker containers running malicious nodes, I could take over the network and forge any blocks I want. What I am missing?
They mention 1/3 of the nodes. How much of a weakness is this?
How does that prevent me from pretending to be any number of nodes I want; including, but by no means limited to, over 1/3 of the nodes? (Maybe you should first do a quick search to learn what a Sybil attack actually is?) They can shore this up by having some kind of Sybil attack prevention elsewhere, but given their statements about proof-of-work here it seems unlikely they would, for example, add proof-of-work elsewhere. It might be, based on skimming some blog post I found if theirs, that the goal of this is to help them shore up a proof-of-stake algorithm to deal with byzantine failures? That would be interesting, but is a more involved scheme then than just this part, and I actually don't think that is what they are doing either (as the connection in that blog post is mostly me reaching for something that works, not a direct connection made by the authors).
Re: Protocol for Asynchronous, Reliable, Secure and Efficient Consensus [pdf]
#13Without proof-of-work, what protects consenus from the sybil attack? As I understood, after quick scan of the paper, consensus is achieved by simple majority vote. So if I setup 10,000 docker containers running malicious nodes, I could take over the network and forge any blocks I want. What I am missing?
Rewarded POW has been an incredible defense against attack, including Sybil in bitcoin and POW derivatives. It has drawbacks though and therefore we now see a lot of research into revising older algorithms and enhancing these. This paper does that with a binary consensus algorithm and an adapted concrete coin (as opposed to a common coin/ threshold signature scheme)
There are many consensus algorithms that are not POW and they work perfectly fine, we cite some in the paper. Many require trusted nodes etc. and that is not so great, however, the work in this field of distributed consensus is increasingly popular. If you duckduckgo for BFT or PBFT algorithms and derivations you will find plenty. This one is very asynchronous and requires no trusted setup phase or threshold signature mechanism, making it an attractive choice.
In its plain form, as described then if you managed to get over 1/3 nodes on the network you could defeat consensus. Its use in SAFE is for valid voting nodes and then you would a much larger proportion than 1/3 of the network. Not only that, but they would have to be online and well behaved for longer than the existing network nodes. It is then much more expensive than a 1/3 attack.
Hope that helps.
Re: Protocol for Asynchronous, Reliable, Secure and Efficient Consensus [pdf]
#14Refreshing to see a maidsafe submission here on HN.
Re: Protocol for Asynchronous, Reliable, Secure and Efficient Consensus [pdf]
#15Earlier quoted context omitted.
They mention 1/3 of the nodes. How much of a weakness is this?
How does that prevent me from pretending to be any number of nodes I want; including, but by no means limited to, over 1/3 of the nodes? (Maybe you should first do a quick search to learn what a Sybil attack actually is?) They can shore this up by having some kind of Sybil attack prevention elsewhere, but given their statements about proof-of-work here it seems unlikely they would, for example, add proof-of-work else…
For SAFE Network, this is handled, I believe. Other networks that implement PARSEC will need to address it in some similar way.
In the case of SAFE, you can generate as many nodes as you want, but they must be valid nodes (doing the work that the network asks of them) for a long time before being promoted to a status that allows them to participate in consensus of a section. Any misbehavior on their part results in demotion or failure to be promoted. So each node would need to be a legitimate contributor to the network, with all that that entails, before being promoted to a status where their later misbehavior would matter. You would be creating real nodes, that used real bandwidth and real CPU resources and did real work that benefits the network, in order to infiltrate your evil nodes into the network. So, not an insubstantial cost to you.
Your nodes will be assigned into sections randomly, so it will be very difficult for you to manage to get multiple nodes with voting status, into a single section, and staggeringly difficult to get enough such that your nodes constitute 1/3rd of that section. Of course, exactly how difficult depends on network size (number of sections).
Finally, even once a node is assigned into a particular section, it will be reassigned to another random section at some interval, further decreasing your ability to take over a particular section.
Re: Protocol for Asynchronous, Reliable, Secure and Efficient Consensus [pdf]
#16Earlier quoted context omitted.
How does that prevent me from pretending to be any number of nodes I want; including, but by no means limited to, over 1/3 of the nodes? (Maybe you should first do a quick search to learn what a Sybil attack actually is?) They can shore this up by having some kind of Sybil attack prevention elsewhere, but given their statements about proof-of-work here it seems unlikely they would, for example, add proof-of-work else…
For SAFE Network, this is handled, I believe. Other networks that implement PARSEC will need to address it in some similar way. In the case of SAFE, you can generate as many nodes as you want, but they must be valid nodes (doing the work that the network asks of them) for a long time before being promoted to a status that allows them to participate in consensus of a section. Any misbehavior on their part results in d…
> Finally, even once a node is assigned into a particular section, it will be reassigned to another random section at some interval, further decreasing your ability to take over a particular section.
Doesn't that on the flipside also mean that given enough time your malicious nodes will end up in the same section, allowing for a take over of that section?
Re: Protocol for Asynchronous, Reliable, Secure and Efficient Consensus [pdf]
#17Earlier quoted context omitted.
For SAFE Network, this is handled, I believe. Other networks that implement PARSEC will need to address it in some similar way. In the case of SAFE, you can generate as many nodes as you want, but they must be valid nodes (doing the work that the network asks of them) for a long time before being promoted to a status that allows them to participate in consensus of a section. Any misbehavior on their part results in d…
> Finally, even once a node is assigned into a particular section, it will be reassigned to another random section at some interval, further decreasing your ability to take over a particular section. Doesn't that on the flipside also mean that given enough time your malicious nodes will end up in the same section, allowing for a take over of that section?
Yes, I believe that there is a non-zero probability that could happen, just as there is a non-zero probability that all the air molecules in the room you are in, which are bouncing around randomly, may all end up in the other corner of the room and suffocate you.
Since all nodes change sections randomly, like air molecules, they should remain randomly distributed, provided the network size is large enough. For a small network though, one can imagine you could get lucky eventually. Like other decentralized networks, security and size are related.
Re: Protocol for Asynchronous, Reliable, Secure and Efficient Consensus [pdf]
#18No noises from the big names in crypto yet. I guess many are carefully going through it and preparing their questions and concerns. Peer-review can't come quickly enough. I can't wait to see how the world responds to this. Have MaidSafe really managed to pull this off?! I mean, WOW, if they have! Fingers crossed.
Re: Protocol for Asynchronous, Reliable, Secure and Efficient Consensus [pdf]
#19Earlier quoted context omitted.
For SAFE Network, this is handled, I believe. Other networks that implement PARSEC will need to address it in some similar way. In the case of SAFE, you can generate as many nodes as you want, but they must be valid nodes (doing the work that the network asks of them) for a long time before being promoted to a status that allows them to participate in consensus of a section. Any misbehavior on their part results in d…
> Finally, even once a node is assigned into a particular section, it will be reassigned to another random section at some interval, further decreasing your ability to take over a particular section. Doesn't that on the flipside also mean that given enough time your malicious nodes will end up in the same section, allowing for a take over of that section?
As the network grows it becomes increasingly harder to do so, especially since you need to add increasing amounts of resources (bandwidth, disk space, and some cpu, for the proof-of-resource) to your attack.
This is not too dissimilar to what happens with CPU-only PoW consensus networks. Easy to attack in the beginning but less so as the network grows.
It will be interesting to see how the SAFE network will be bootstrapped. I'm sure there will be a significant number of malicious players waiting in line to disrupt it early on.
If it works, and I believe it can, IMHO this network will be one of the most important developments in decentralised systems in the past decade.
Re: Protocol for Asynchronous, Reliable, Secure and Efficient Consensus [pdf]
#20A good point from the forum.
“Now PARSEC won’t be used in SAFE to let the entire network communicate and come into global consensus like for example Bitcoin does, instead PARSEC will be used by many small sections of the network to reach “local” consensus for the corresponding section of the network. The obvious attack vector here is to join one section with many nodes of your own to hijack that particular section. The idea is to make this attack infeasible by having the network occasionally relocate nodes (when they age/rank up), so an attacker doesn’t have control over in what sections of the network its nodes are located. If this idea works as well in practice as it does in theory, attacking a section is about as hard as attacking the entire network (all the sections).”
So proof-of-work is inherently resistant to sybil attacks while PARSEC on its own isn’t, so to tell the story properly the random but deterministic relocating of nodes needs to be included.