Author Topic: Worst Case Scenario Contingency Planning  (Read 2438 times)

0 Members and 1 Guest are viewing this topic.

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
Here is another idea for a contingency plan. What if users could put their client into an emergency mode by setting a particular Owner Key to become a temporary unelected benevolent dictator replacing all the elected delegates in slots 1 to 101. Users would have to come to a consensus on which Owner Key to use through discussion and URL sharing. This would create a fork, so users would need to be aware to not use the network for value transfer to other individuals during the state of emergency because their chosen fork may become invalidated. They would only use it to transfer their stake to themselves in order to change their votes. The benevolent dictator would only be there to let these transactions go through until order was restored. If the dictator wasn't so benevolent and was also censoring transactions or refusing to give up control, people could always tell their client to switch the Owner Key to someone else (and people would have to come to a consensus again). Obviously this wouldn't work in a 51% attack (the hard fork with purging is needed for that), but it would be ideal for cases where all 101 delegate keys were compromised or honest users were tricked into voting for all 101 malicious delegates. When enough revoting has occurred to replace the top 101 highest approval delegates with delegates users think they can trust, the benevolent dictator can declare the state of emergency over and get replaced by the top 101 delegates ranked by the new approval rating. The network and clients can then continue from there as normal.

This way only in the case of a 51% stake attack do we actually have to resort to a fork where we purge balances (and thus risk destroying money held by innocent users who got tricked into voting for bad delegates).

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
It has been pointed out that the weakest part of DPOS is that once someone controls 51 delegates they can never be fired unless they consent because they could filter any transaction that votes for someone other than themselves.    There are several ways to gain control of 51 delegates:

Wait, why 51? Shouldn't it be 101? I thought if even 1 delegate was honest, then people could (slowly) vote all the dishonest delegates out. The honest delegate would gather all the valid transactions that the other 100 were ignoring, and add them to the blockchain on his turn (once every 16.8 minutes).

Now, if the attackers buy up 51% of the stake, then yes they can easily get all 101 delegates in their control.

<edit>
Okay, I think I almost get it now. Bytemaster, please let me know if I understand correctly so far. If there was 1 honest delegate with 100 dishonest delegates, the delegate would create a block with valid transactions and add it to the chain created by the dishonest delegates, because it needs to follow the consensus rules. But the dishonest delegates could break the rules and just ignore the honest delegate's block. They can pretend as if they never saw the block and build off one of the dishonest delegate's block instead. Because the honest delegate is following the rules to avoid breaking consensus (creating forks), he is forced in the next round to build off the longest chain which excludes his block. Therefore he cannot get the consensus chain to include his blocks with legitimate transactions for long enough to change the approval rating of the delegates. Thus the dishonest delegates maintain control.


But I still am not sure why the threshold has to be 51. If there were 2 honest delegates in sequential order for a given round, the second honest delegate could build off the first and create a chain which is longest chain at that moment. If three dishonest delegates create blocks building on the chain as if the honest delegates' blocks didn't exist, then they would reclaim the longest chain. But before that time (30 seconds after the second honest delegate's block) wouldn't all online clients notice that the dishonest delegate was breaking the rules by not building on the longest chain, and therefore reject the block as invalid? Or would the clients accept it because it is a plausible condition that can arise from network issues? But then the question is how many blocks that the clients have seen but the delegates ignored would the clients tolerate as missing in the consensus chain? It can't be too many, because transactions aren't actually confirmed until you can commit to a particular fork, and DPOS can confirm transactions quickly. So let's say the threshold is 2 blocks. This means all the dishonest delegates would essentially be firing themselves if they did not build the chain off the honest delegate's blocks (which they can assume all the online clients saw). If they decide to fire themselves by doing this, then block production rate drops to 1.98% and the honest delegates are the only ones in control (although slowly). If they are forced into building the chain off the honest delegates then the honest delegates can get enough transactions in to eventually change the approval rating of the dishonest delegates.

So, if I understood all of the above correctly, it means that with just 2 honest delegates it could be possible for the network to recover (it would just take a really long time to do it). How long would it take? Assuming the order of every round is truly random, we need to calculate the probability that 2 out of the 101 delegates are in sequential order. This probability is p = (99 + 1) * 2! * 99! / 101! = 0.0198. The probability of having k of these favorable rounds after n rounds is given by the binomial distribution. The cumulative distribution function is F(k; n, p) = P(X <= k) = I_{1-p}(n-k, k+1). But we are interested in probability of more than k favorable rounds which is P(X > k) = 1 - P(X <= k) = 1 - F(k; n, p) = 1 - I_{1-p}(n-k, k+1). Let's assume that a value of k=2 is sufficient. This will get 4 blocks in the blockchain which can be crammed with the transactions that move the most stake away from the dishonest delegates and to honest delegates. After more honest delegates enter the picture, it just becomes easier to get more honest delegates in. We want to know what is minimum value of n that will give a P(X > k) that is greater than 90% (reasonable guarantee to occur). The answer is n = 268. Unfortunately, that would take 3 days. So what is the right number of minimum delegates we need to get the DAC under control in a reasonable time frame? That requires more combinatorics and probability analysis than I feel like doing right now. Maybe later. Or maybe one of you on the forum is a mathematician who would love to figure it out.

But is my analysis even correct? Is having two honest delegates in sequential order enough to get their blocks in the consensus blockchain? It would be nice to have a more detailed description of DPOS documented than what is currently available in the wiki.


<edit2>
An edit within an edit! More speculating in the dark. I think I finally got it. But it would be really great to get some clarity from people who already fully know the answer to this.

So thinking about it more, I realize that it doesn't matter what the online clients see. It is what offline clients can come to a consensus on. In order to prevent forks, the online clients need to decide which chain to use with only the information that would be available to offline clients not the superior information they know while online (the exception to this is that they can use whatever information they want to direct the users' funds for voting purposes). Using my above example, if two honest delegates build a chain off each other only to be later replaced as longest chain by the three dishonest delegates that come after it, then a client logging in after that moment will see that the dishonest chain is the longest chain and use that. The offline clients have no way of knowing whether certain delegates hit their time slot or not when they were offline. The honest delegates need to play by the rules that only allows them to fully commit to a chain that offline users would be able to verify is legitimate using only information available from that chain and any other candidate chains that can be supplied by the network (at least for short time resyncs). This means clients just coming online cannot ask other online clients that were supposedly online during the time of the dispute which chain is the correct one. This is because the clients cannot trust any other clients (Sybil attack). The only trust a client can have is in the rules of the chain and the delegates that were legitimately elected at the time according to the rules of the chain.

In the case of re-synchronizing from a medium period of time of being offline, the client can rely on risk analysis of the blockchain that supposedly follows the rule in order to warn the user if he is likely under a fake blockchain history attack. For example, say the private keys of 100 delegates who were simultaneously active at some past time t were compromised/purchased by an attacker. But because one delegate key was not compromised, the fake chain created by the attacker is forced to contain missing blocks by the same uncompromised delegate for too many consecutive rounds. This is highly suspicious blockchain activity since it would be expected that users would have voted out the delegate with so many consecutive missing blocks in a reasonable time-frame if this was in fact a copy of the true chain that was built in a live environment. This can then allow the user assume he is under attack, disregard the chain, and instead rely on his social web of trust to determine a legitimate recent snapshot. If TaPOS is also used, then the only way the attackers can rewrite the blockchain history to vote out that uncompromised delegate in the fake chain is if they have under their control a large enough stake at time t to increase the approval rating of another controlled delegate above the approval rating of the uncompromised delegate, which remains fixed to the value it was at time t. If honest delegates have high approval ratings, this is very difficult to do since it requires either compromising/buying the private keys of holders of a significant percentage of stake at time t or actually having legitimately bought by time t a significant percentage of the stake. Long-range Nothing-at-Stake attacks are even less of an issue because users know to always resync from a trusted block stored on their computer (or trusted block hash) that is not too old. If the block they can trust is too old (say older than 6 months) or they want to regenerate the blockchain from genesis, then in order to be extra cautious they need provide a trusted checkpoint obtained from their social web of trust to the client or better yet download a more recent version of the client with a snapshot built-in from a source they trust.

The attacks previously mentioned are when attackers are trying to rewrite history and present it to particular victims in order to accomplish double-spends. They are rewriting history because the attackers did not legitimately control the blockchain at the time. But what about "live attacks" where the attackers have a number of delegates under their control through means that are considered legitimate according to the rules of the chain (whether it is by compromising private keys, buying up enough stake to vote them in, tricking honest users into voting for the delegates, or a combination of the previous methods)? In live attacks, clients and delegates cannot rely on blockchain risk analysis to rule out the fork created by some dishonest delegates pretending as if the honest delegates do not exist. One can imagine a scenario where a large number of delegates dropped out (severe network issues). The medium-term fake blockchain history attacks were not a concern for even fewer delegates disappearing because clients would know that users would vote out the bad delegates in time. But this is a live attack. Users haven't had the chance to vote bad delegates out yet. To ensure offline clients coming online just now are able to maintain consensus on what the true chain is, honest delegates have to follow the consensus rules even if that means having their own blocks filtered out because of the activity of the dishonest delegates. So how many dishonest delegates are necessary to break the system? Intuitively, I would say 51 seems like the right answer because that seems like it would allow them to guarantee that they will always have the longest chain. But I have not yet been able to prove that to a sufficient degree to convince myself it is the right answer. And if delegates are following the rule where they cannot fully commit to a chain until it has at least 51 unique delegate support (so that it could not be replaced as longest chain in the event of an attack), then that is consistent with the claim that the worst case confirmation time for DPOS is 51 blocks (or 8.5 minutes). In reality, the 51 delegate attack should be so unlikely that for regular (low to medium value) transactions, one block confirmation is sufficient.
</edit2>

</edit>

In the case where they bought up the stake then any balances voting for the attackers also need to be purged.

I think that it should be possible to pre-plan for this scenario by shipping every wallet with an emergency backup-fork switch.  At any time users can simply go into advanced and enter a block number that they would like to "hard fork" and a list of misbehaving delegates for which balances should be purged. 

We can then provide a URL scheme that entirely documents the hard-fork and developers / community members can simply share the URL.  All of the honest nodes automatically switch to the new fork without anyone having to distribute new binaries.

That would be awesome.

And if someone would get tricked in voting for the attacker, their balance would also be purged?

All the more reason for shareholders to be careful about who they vote for. They have a responsibility to ensure, to the best of their ability, that the delegates they are voting for are not people who wish to harm the network. Keep in mind if I am right about all 101 delegates being necessary to shut down the network, then a hard fork is very unlikely to be necessary unless it was a 51% stake attack. In that case, the attackers don't need to try to convince honest users to vote for their delegates.

I also think in order to prevent people from taking the conservative approach and just not voting for anyone to eliminate the risk of voting for a bad delegate (which would only make the network less secure), we should follow the social consensus that in the event of a hard fork, we purge any balances that are not voting for at least 33 delegates (33 so that we can still have random voting for privacy reasons).

« Last Edit: August 07, 2014, 02:11:27 am by arhag »

Offline luckybit

  • Hero Member
  • *****
  • Posts: 2921
    • View Profile
  • BitShares: Luckybit
So it's basically a consensus coup?

Think of it as a revolution by the shareholders against the tyranny of the delegates should the delegates ever become universally corrupted.

I think it's important to at least have a way to do something similar to this. Maybe there could be a safer or better way of doing it but whatever we can do to prevent collusion and to improve upon the collusion resistance of the delegates is an idea to at least consider.

The ideal structure of the network is to have it be flexible enough to self-heal or survive all kinds of attacks. If the delegates are corrupt, hostile, etc, we still need this capability and it's a distinguishing feature which Bitcoin, Litecoin, and all PoW currencies do not have. This gives DPoS the advantage of long term resiliency.

In PoW if the miners and other critical positions are corrupt can we overthrow them? Is the network resilient enough to recover from it?

Counterparty and Mastercoin would continue to blindly rely on them no matter what and would have to resort to finding another blockchain to piggy back on.
I think a more likely scenario is the VPS's are compromised.  Most of the delegates are run on VPS's which means the system can be taken down and modified without the owner even knowing if the admin doesn't have sufficient watchdog type security systems in place. (And a copy with no changes can be made regardless of the security in place)  Any jurisdiction that is friendly with the entity trying to do a hostile take it over could be forced to allow this.  A backdoored sshd could be installed and all passwords found.  They already have a snapshot of the drive so it is trivial to just go from there.

Actually it is worse, because a snapshot of the working memory could be had on a VPS.  An attack with sufficient resources could use this memory snapshot of an unlocked wallet to proceed.

This is why it would be nice to have about 1/3 in China, 1/3 in Russia, and a 1/3 elsewhere. :)  (Or something like that...)

At one point I wrote a script that was fairly complicated and used tripwire + ssh/rsh to remotely install tripwire/execute it, then copy the results off remotely for analysis.

This is a good point but if the VPS has no way of knowing what you're doing and / or if we don't all use the same VPS then the risk is spread.

There is a slight risk but I think if that happened people would switch to a more reliable VPS. Ideal is if people run the computer themselves but realistically it's more likely the VPS is more secure than people's home computer. Suppose you have a good setup at home but your power gets shut off, your harddrive dies, or your Internet gets canceled?

VPS is a fixed cost and has great uptime.
« Last Edit: August 06, 2014, 12:16:51 am by luckybit »
https://metaexchange.info | Bitcoin<->Altcoin exchange | Instant | Safe | Low spreads

Offline luckybit

  • Hero Member
  • *****
  • Posts: 2921
    • View Profile
  • BitShares: Luckybit
It has been pointed out that the weakest part of DPOS is that once someone controls 51 delegates they can never be fired unless they consent because they could filter any transaction that votes for someone other than themselves.    There are several ways to gain control of 51 delegates:

1) SWAT team all over the world
2) Blackmail delegates
3) Buy up the stake.

In any of these events the current crop of delegates needs to be purged.   In the case where they bought up the stake then any balances voting for the attackers also need to be purged.

I think that it should be possible to pre-plan for this scenario by shipping every wallet with an emergency backup-fork switch.  At any time users can simply go into advanced and enter a block number that they would like to "hard fork" and a list of misbehaving delegates for which balances should be purged. 

We can then provide a URL scheme that entirely documents the hard-fork and developers / community members can simply share the URL.  All of the honest nodes automatically switch to the new fork without anyone having to distribute new binaries.

There might be some confusion about which URL to follow, but in most cases the attack should be very clear and the solution equally clear.  The social consensus will form and the chain can continue.   After all failure to agree is agreeing to fail.

This is a brilliant fail-safe idea.  +5%

Can't simply increasing the amount of total delegates help?  IE 1001 once the network is large enough?

This is discussed elsewhere... finding the sweet spot between cost/benefit is the challenge.  101 may be enough, 1001 may not be enough.

Perhaps an algorithm which smoothly adjusts based on the cost benefit analysis?

For example if the network could determine the efficiency of the delegates and give that a number, based on reliability, speed, and other categories, and then if the efficiency number goes below a certain level then reduce the amount of delegates who aren't pulling their fair share even if it goes below 101, but if every delegate is very fast and has a high rating then increase the amount of them until it starts having perceived effects on network?

I'm thinking something like this could be an algorithm easily and adjust according to the needs of the network rather than be a fixed number of delegates. The delegate amount would be dynamic within a certain range depending on what shareholders perceive is needed at that time. So if it's a situation where the network needs more efficiency the shareholders could opt to reduce the amount of delegates and optimize for that but if at another point in time the network is under attack then they could opt to increase decentralization to defend in real time.

I prefer if there is more decentralization but I would think if the shareholders all vote in favor of efficiency then let the network optimize for efficiency. If they vote in favor of decentralization then let it optimize in favor of decentralization. It could be an interface component with a slider which lets them set the level of efficiency vs decentralization. If the majority of the shareholders opt for decentralization then this would determine the sweet spot is toward decentralization otherwise it would be toward efficiency.

Decentralization  vs   Efficiency
9 8 7 6 5 4 3 2 1 <-0-> 1 2 3 4 5 6 7 8 9

Slider should look something like that. 0 would mean keep everything at 101 delegates. 9 would be the maximum in one direction or the other.
« Last Edit: August 06, 2014, 12:53:10 am by luckybit »
https://metaexchange.info | Bitcoin<->Altcoin exchange | Instant | Safe | Low spreads

Offline bytemaster

Can't simply increasing the amount of total delegates help?  IE 1001 once the network is large enough?

This is discussed elsewhere... finding the sweet spot between cost/benefit is the challenge.  101 may be enough, 1001 may not be enough.
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Online Brekyrself

  • Hero Member
  • *****
  • Posts: 512
    • View Profile
Can't simply increasing the amount of total delegates help?  IE 1001 once the network is large enough?

Offline Shentist

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 1601
    • View Profile
    • metaexchange
  • BitShares: shentist
@bytemaster

what technical data need a delegate computer?

Offline bytemaster

Individual compromised keys are not an issue unless it happens in bulk.   This is why I highly recommend delegates focus on real hardware.... with backup power.  Early on a home PC with backup power + DSL is probably good enough. 

This is mostly just worst-case planning and hopefully would never need to be exercised. 
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline gamey

  • Hero Member
  • *****
  • Posts: 2253
    • View Profile
I think a more likely scenario is the VPS's are compromised.  Most of the delegates are run on VPS's which means the system can be taken down and modified without the owner even knowing if the admin doesn't have sufficient watchdog type security systems in place. (And a copy with no changes can be made regardless of the security in place)  Any jurisdiction that is friendly with the entity trying to do a hostile take it over could be forced to allow this.  A backdoored sshd could be installed and all passwords found.  They already have a snapshot of the drive so it is trivial to just go from there.

Actually it is worse, because a snapshot of the working memory could be had on a VPS.  An attack with sufficient resources could use this memory snapshot of an unlocked wallet to proceed.

This is why it would be nice to have about 1/3 in China, 1/3 in Russia, and a 1/3 elsewhere. :)  (Or something like that...)

At one point I wrote a script that was fairly complicated and used tripwire + ssh/rsh to remotely install tripwire/execute it, then copy the results off remotely for analysis. 
« Last Edit: August 05, 2014, 07:28:50 pm by gamey »
I speak for myself and only myself.

Offline graffenwalder

It has been pointed out that the weakest part of DPOS is that once someone controls 51 delegates they can never be fired unless they consent because they could filter any transaction that votes for someone other than themselves.    There are several ways to gain control of 51 delegates:

1) SWAT team all over the world
2) Blackmail delegates
3) Buy up the stake.

In any of these events the current crop of delegates needs to be purged.   In the case where they bought up the stake then any balances voting for the attackers also need to be purged.

I think that it should be possible to pre-plan for this scenario by shipping every wallet with an emergency backup-fork switch.  At any time users can simply go into advanced and enter a block number that they would like to "hard fork" and a list of misbehaving delegates for which balances should be purged. 

We can then provide a URL scheme that entirely documents the hard-fork and developers / community members can simply share the URL.  All of the honest nodes automatically switch to the new fork without anyone having to distribute new binaries.

There might be some confusion about which URL to follow, but in most cases the attack should be very clear and the solution equally clear.  The social consensus will form and the chain can continue.   After all failure to agree is agreeing to fail.

Would only the transactions of the attacker get purged?

And what would happen to the balances that get purged?

And if someone would get tricked in voting for the attacker, their balance would also be purged?

Offline santaclause102

  • Hero Member
  • *****
  • Posts: 2486
    • View Profile
doesn't change your point but ....
4) mislead shareholders
5) selfish voting + an attacker providing pay back delegates
could also be a reason for 51 delegates controlled by 1 individual.
1/2 could be grouped into one category because in both cases it is necessary to know where the delegates are.

Offline Riverhead

So it's basically a consensus coup?

Offline bytemaster

It has been pointed out that the weakest part of DPOS is that once someone controls 51 delegates they can never be fired unless they consent because they could filter any transaction that votes for someone other than themselves.    There are several ways to gain control of 51 delegates:

1) SWAT team all over the world
2) Blackmail delegates
3) Buy up the stake.

In any of these events the current crop of delegates needs to be purged.   In the case where they bought up the stake then any balances voting for the attackers also need to be purged.

I think that it should be possible to pre-plan for this scenario by shipping every wallet with an emergency backup-fork switch.  At any time users can simply go into advanced and enter a block number that they would like to "hard fork" and a list of misbehaving delegates for which balances should be purged. 

We can then provide a URL scheme that entirely documents the hard-fork and developers / community members can simply share the URL.  All of the honest nodes automatically switch to the new fork without anyone having to distribute new binaries.

There might be some confusion about which URL to follow, but in most cases the attack should be very clear and the solution equally clear.  The social consensus will form and the chain can continue.   After all failure to agree is agreeing to fail. 



For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.