Topic: Know you ENEMY / Your weaknesses - find robust ways to counteract (Read 114 times)
thoughts?
December 10, 2018, 10:42:44 AM
How can you build a new blockchain architecture with increase in throughput and decrease in energy expenditure?
Article written by Felix Crisan - original link here: https://medium.com/elrondnetwork/elronds-design-rationale-12eb194bf485
Note: Throughout this article by proposer we’ll refer to a node/entity in the network that is in charge at a specific time of proposing a new block, while validator(s) will designate the nodes/entities that are responsible with validating the block put forward by the proposer, thus effectively “vouching” for the proposer.
The two problems that Elrond tries to solve from the get-go are increase in throughput — achievable through sharding and decrease in energy expenditure — achievable through moving from a proof-of-work based consensus to a proof-of-stake consensus. Each of these two prongs require different aspects to be taken into consideration when designing the architecture and components around it. The PoS aspect needs working around all (most?) common issues in PoS systems — thus incentivising rational behavior. The sharding aspect needs mechanisms to reach agreements inside each smaller part of the network (shard) as well as agreement between participants in a transaction that spans more shards. And all these need to also take into consideration the potential Byzantine (adversarial) behavior.
Before anything let’s detail a common approach when talking about blockchains based on proof-of-stake: everybody tends to measure time with two units; the obvious one called block time (the interval between two successive blocks) but also a higher order one called epoch or era. From this point of view the interval required to generate a specific number (X) of blocks is an era (thus always era = X * block time).
Know your enemy…
All PoS blockchains, in existence today or merely theorized, use crypto-economic incentives to ensure that behaviour of people (as their network personas represented by nodes) follows an expected pattern — nodes get rewarded for doing good things (for the network) and they get punished for doing bad things. While in some cases, this carrot-and-stick approach over-emphasises one side of the equation (i.e. there are cases where there are no punishments for adversarial behaviour), most of the times these two sides are balanced. Also worth noting that punishments are largely related to a stake that each node locks in for a predefined period (normally multiple epochs). The adversarial behaviour in absence of this locked stake that the node can lose (in part or entirely) is called Nothing-at-stake attack.
Another type of adversarial behaviour related to locked stakes involves a node being part of the “decision” process, then dropping off from this process and retrieving his stake. Some time after these events, using the credentials associated with the stake (i.e. keys), the node/entity can try to “forge” a different history (either itself, or by providing these credentials to a malicious party); thus transforming the attack into a delayed nothing at stake, usually named Long-range attack. From this point of view, referring to the terms outlined in the previous article, it’s important that stake unlocking takes place only after the blocks proposed or validated by the node in discussion are finalized.
In some types of Long-range attacks performed in blockchains that implement penalties (in principal those with liveness targets) publishing this alternative history might give the impression that some of the nodes have not performed their duties and thus get (unfairly) punished. This type of adversarial behaviour is called Stake-bleeding attack [SB].
Last, but certainly not least, we can have situations where nodes are isolated from the network by adversaries, that ‘feed’ them a distorted view of reality (e.g. only relay transactions from their ‘friends’ and censor legitimate transactions). These types of attacks are called eclipse-attacks.
…but also know your weaknesses to counteract
As outlined previously, PoS systems have to cover a few weaker points when dealing with adversaries, two of the most important being:
* External: The DoS-ing (or otherwise impairing) of the current validator(s) or current proposer so that they are not able to communicate with the rest of the nodes and can’t take decisions. This obviously affects the liveness capabilities of the blockchain, but can also affect the security (thus leading to unpredictable results).
* Internal: Nodes (identities or entities) that are chosen at a specific step to take on one of the ‘official’ roles for the next step(s) can behave in an adversarial manner (e.g. proposing invalid blocks, refusing to participate in collective signing procedures etc).
If you remember from the previous article, three types of sharding were described — network, transaction and state. We’ve opted to do state sharding and, as a response to these two particular problems just outlined, we’ve came up with two concepts which we’ve named Secure Proof of Stake and Adaptive State Sharding.
A Novel Approach to adversarial behaviour through Robust Adaptivity
Everyone’s intuition tells that the longer in advance an adversary knows about the proposer node and/or validator nodes — starting from the node identity but maybe also their ‘network coordinates’ — the more damage this adversary can inflict on the node (and, by extension, to the network). An even worse scenario is if, by knowing long in advance who is going to be responsible of a particular block proposal, the adversary can collude with the said proposer (or validator) so they propose (or validate) invalid blocks (e.g. allowing a double spend or minting coins out of thin air — not unlike what central banks do today :-D). As a result it’s desirable to know a node’s role for a specific step (block) as little in advance as possible.
To resolve this conundrum we’ve taken the following approach: we use the current block signature as a randomness source and based on that we pick a/ current proposer and b/ current validator set. One way this can be achieved is that everyone eligible runs a Verifiable Random Function (VRF) on the current block hash and comes up with a random number (and a proof that the random number was correctly generated by the chosen VRF). The random numbers are arranged (say low to high) and the first one (producer of the smallest number) is the proposer, the next N are the validators. In this way, while the proposer can pick a particular block, they won’t be able to tell which of the other consensus participants will obtain a maybe smaller random number on the next step.
To make things even more difficult for byzantine nodes we’ve also devised a process whereby from time to time (say each epoch) a part of the shard nodes are reassigned to different shards, without anyone in the network being able to tell in advance what node will be reassigned and, moreover, to which shard will it be moved. The reassignment process can be, again, the result of running a VRF.
The particularity we’ve employed in designing our carrot-and-stick mechanisms is that besides rewards and slashing each node will have a rating that represents the view of the network on the said node’s behaviour. Playing by the rules will increase (up to a limit) the node’s rating, while adversarial behaviours will decrease it. This rating will be combined with the node’s stake when computing stake related probabilities — i.e. in the end a weight on the user’s stake. Positive ratings will act as if the node’s stake is bigger than the actual stake, while negative ratings will have the same effect as lowering the node’s stake. Actual rewards and punishments could also be affected by this rating (thus a positive behaviour would benefit a node more, in the long run, than a negative one, assuming the same stake to start with)
Takeaways
In conclusion — we set to build this new blockchain architecture by finding the optimal (we think) mechanisms through which we:
Incentivise good behavior — by asking entities that want to “play” to “put the money where the mouth is”, while at the same providing rewards for being part of the consensus mechanism
Minimise bias-ability of certain decisions and participants’ exposure to attacks by taking some decisions (shard assignment, group and leader elections) based on a randomness source (block and node signatures).
Eliminate (or at least drastically reduce probabilities of) collusion by shuffling nodes in shards from time to time, also changing roles inside a shard
References
[SB] https://eprint.iacr.org/2018/248.pdf, “Stake-Bleeding Attacks
on Proof-of-Stake Blockchains”
[LRA] https://blog.cosmos.network/consensus-compare-casper-vs-tendermint-6df154ad56ae “Consensus Compare: Casper vs. Tendermint”
Article written by Felix Crisan - original link here: https://medium.com/elrondnetwork/elronds-design-rationale-12eb194bf485
Note: Throughout this article by proposer we’ll refer to a node/entity in the network that is in charge at a specific time of proposing a new block, while validator(s) will designate the nodes/entities that are responsible with validating the block put forward by the proposer, thus effectively “vouching” for the proposer.
The two problems that Elrond tries to solve from the get-go are increase in throughput — achievable through sharding and decrease in energy expenditure — achievable through moving from a proof-of-work based consensus to a proof-of-stake consensus. Each of these two prongs require different aspects to be taken into consideration when designing the architecture and components around it. The PoS aspect needs working around all (most?) common issues in PoS systems — thus incentivising rational behavior. The sharding aspect needs mechanisms to reach agreements inside each smaller part of the network (shard) as well as agreement between participants in a transaction that spans more shards. And all these need to also take into consideration the potential Byzantine (adversarial) behavior.
Before anything let’s detail a common approach when talking about blockchains based on proof-of-stake: everybody tends to measure time with two units; the obvious one called block time (the interval between two successive blocks) but also a higher order one called epoch or era. From this point of view the interval required to generate a specific number (X) of blocks is an era (thus always era = X * block time).
Know your enemy…
All PoS blockchains, in existence today or merely theorized, use crypto-economic incentives to ensure that behaviour of people (as their network personas represented by nodes) follows an expected pattern — nodes get rewarded for doing good things (for the network) and they get punished for doing bad things. While in some cases, this carrot-and-stick approach over-emphasises one side of the equation (i.e. there are cases where there are no punishments for adversarial behaviour), most of the times these two sides are balanced. Also worth noting that punishments are largely related to a stake that each node locks in for a predefined period (normally multiple epochs). The adversarial behaviour in absence of this locked stake that the node can lose (in part or entirely) is called Nothing-at-stake attack.
Another type of adversarial behaviour related to locked stakes involves a node being part of the “decision” process, then dropping off from this process and retrieving his stake. Some time after these events, using the credentials associated with the stake (i.e. keys), the node/entity can try to “forge” a different history (either itself, or by providing these credentials to a malicious party); thus transforming the attack into a delayed nothing at stake, usually named Long-range attack. From this point of view, referring to the terms outlined in the previous article, it’s important that stake unlocking takes place only after the blocks proposed or validated by the node in discussion are finalized.
In some types of Long-range attacks performed in blockchains that implement penalties (in principal those with liveness targets) publishing this alternative history might give the impression that some of the nodes have not performed their duties and thus get (unfairly) punished. This type of adversarial behaviour is called Stake-bleeding attack [SB].
Last, but certainly not least, we can have situations where nodes are isolated from the network by adversaries, that ‘feed’ them a distorted view of reality (e.g. only relay transactions from their ‘friends’ and censor legitimate transactions). These types of attacks are called eclipse-attacks.
…but also know your weaknesses to counteract
As outlined previously, PoS systems have to cover a few weaker points when dealing with adversaries, two of the most important being:
* External: The DoS-ing (or otherwise impairing) of the current validator(s) or current proposer so that they are not able to communicate with the rest of the nodes and can’t take decisions. This obviously affects the liveness capabilities of the blockchain, but can also affect the security (thus leading to unpredictable results).
* Internal: Nodes (identities or entities) that are chosen at a specific step to take on one of the ‘official’ roles for the next step(s) can behave in an adversarial manner (e.g. proposing invalid blocks, refusing to participate in collective signing procedures etc).
If you remember from the previous article, three types of sharding were described — network, transaction and state. We’ve opted to do state sharding and, as a response to these two particular problems just outlined, we’ve came up with two concepts which we’ve named Secure Proof of Stake and Adaptive State Sharding.
A Novel Approach to adversarial behaviour through Robust Adaptivity
Everyone’s intuition tells that the longer in advance an adversary knows about the proposer node and/or validator nodes — starting from the node identity but maybe also their ‘network coordinates’ — the more damage this adversary can inflict on the node (and, by extension, to the network). An even worse scenario is if, by knowing long in advance who is going to be responsible of a particular block proposal, the adversary can collude with the said proposer (or validator) so they propose (or validate) invalid blocks (e.g. allowing a double spend or minting coins out of thin air — not unlike what central banks do today :-D). As a result it’s desirable to know a node’s role for a specific step (block) as little in advance as possible.
To resolve this conundrum we’ve taken the following approach: we use the current block signature as a randomness source and based on that we pick a/ current proposer and b/ current validator set. One way this can be achieved is that everyone eligible runs a Verifiable Random Function (VRF) on the current block hash and comes up with a random number (and a proof that the random number was correctly generated by the chosen VRF). The random numbers are arranged (say low to high) and the first one (producer of the smallest number) is the proposer, the next N are the validators. In this way, while the proposer can pick a particular block, they won’t be able to tell which of the other consensus participants will obtain a maybe smaller random number on the next step.
To make things even more difficult for byzantine nodes we’ve also devised a process whereby from time to time (say each epoch) a part of the shard nodes are reassigned to different shards, without anyone in the network being able to tell in advance what node will be reassigned and, moreover, to which shard will it be moved. The reassignment process can be, again, the result of running a VRF.
The particularity we’ve employed in designing our carrot-and-stick mechanisms is that besides rewards and slashing each node will have a rating that represents the view of the network on the said node’s behaviour. Playing by the rules will increase (up to a limit) the node’s rating, while adversarial behaviours will decrease it. This rating will be combined with the node’s stake when computing stake related probabilities — i.e. in the end a weight on the user’s stake. Positive ratings will act as if the node’s stake is bigger than the actual stake, while negative ratings will have the same effect as lowering the node’s stake. Actual rewards and punishments could also be affected by this rating (thus a positive behaviour would benefit a node more, in the long run, than a negative one, assuming the same stake to start with)
Takeaways
In conclusion — we set to build this new blockchain architecture by finding the optimal (we think) mechanisms through which we:
Incentivise good behavior — by asking entities that want to “play” to “put the money where the mouth is”, while at the same providing rewards for being part of the consensus mechanism
Minimise bias-ability of certain decisions and participants’ exposure to attacks by taking some decisions (shard assignment, group and leader elections) based on a randomness source (block and node signatures).
Eliminate (or at least drastically reduce probabilities of) collusion by shuffling nodes in shards from time to time, also changing roles inside a shard
References
[SB] https://eprint.iacr.org/2018/248.pdf, “Stake-Bleeding Attacks
on Proof-of-Stake Blockchains”
[LRA] https://blog.cosmos.network/consensus-compare-casper-vs-tendermint-6df154ad56ae “Consensus Compare: Casper vs. Tendermint”
Jump to: