Author Topic: Consensus on the list of delegates  (Read 35107 times)

0 Members and 1 Guest are viewing this topic.

Offline bytemaster

If the attacker cannot get 101 delegates in then his network will only be "half power" at 51% and will never be able to get to 100% power without buying the stake.
The honest minority will be able to include votes that can get honest delegates elected in.. if they can only get 10 more honest delegates in then it will be a 51% chain vs a 59% chain.
Lastly if it is clear there is an attack, and it would be, then it would be TRIVIAL to release a universally accepted hard fork that simply reset the vote on the offending delegates to 0.

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 Come-from-Beyond

  • Full Member
  • ***
  • Posts: 113
    • View Profile
In the scenarios discussed in this thread, I define an "evil delegate" from the perspective of a stakeholder as a delegate who the stakeholder has noticed is not including valid transactions into the blockchain in a reasonable amount of time.

Other transactions may be prioritized and occupy all available space in blocks. Unconfirmed transactions can be lost in void. An eclipse attack may be conducted against one of the delegates... Rating grinding attack becomes much easier if you decide to distinguish delegates.

Offline Troglodactyl

  • Hero Member
  • *****
  • Posts: 960
    • View Profile
I assumed that people will update their votes to make sure they can get all 100 evil delegates replaced by good ones so that the honest chain can take over.

Now we need something to distinguish bad and good delegates.

The voters always have to distinguish between delegates who serve their interests and delegates who do not.  That's the whole point of voting.  This sort of scenario makes it pretty clear, as delegates excluding valid votes clearly do not serve the interests of the shareholders.

Offline Gentso1

  • Hero Member
  • *****
  • Posts: 931
    • View Profile
  • BitShares: gentso
I assumed that people will update their votes to make sure they can get all 100 evil delegates replaced by good ones so that the honest chain can take over.

Now we need something to distinguish bad and good delegates.
http://bitsharesblocks.com/delegates

This will at give you some basic information on the delegate.

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
I assumed that people will update their votes to make sure they can get all 100 evil delegates replaced by good ones so that the honest chain can take over.

Now we need something to distinguish bad and good delegates.

In the scenarios discussed in this thread, I define an "evil delegate" from the perspective of a stakeholder as a delegate who the stakeholder has noticed is not including valid transactions into the blockchain in a reasonable amount of time. Then, "good delegate" from the perspective of a stakeholder is a delegate that this stakeholder suspects will not be an "evil delegate".

If 100 of the current top 101 delegates are colluding to not include any transactions that take votes away from them and/or vote for delegates other than them, then eventually consensus will be reached by some collection of BTS stakeholders (the "Participating Stakeholders") that this set of delegates (the "Bad Delegates") include members that are each considered to be an "evil delegate". Once the collective BTS stake held by the "Participating Stakeholders" has reached a percentage of BTS greater than the approval rating of the delegate in the "Bad Delegates" with the highest approval rating, it becomes possible (assuming the stakeholders in the "Participating Stakeholders" group collectively can come to an agreement on the 100 "good delegates" that they vote on to replace the 100 "evil delegates")  for the last remaining delegate in the top 101 ranks that is not in the "Bad Delegates" (the "Single Honest Delegate") to initiate the process I described here to recover from the attack. Even if the replacement process that "Participating Stakeholders" choose is as simple as to not vote for the "Bad Delegates" and vote for the next 100 delegates in the ranks that are known to have not been "evil delegates" in the past, then eventually (even if it takes a few iterations) all the delegates who will choose to become "evil delegates" will be exhausted leaving only delegates that do not choose to become "evil delegates", at the very least for a long period of time starting from when they get elected.
« Last Edit: February 03, 2015, 01:44:59 pm by arhag »

Offline Come-from-Beyond

  • Full Member
  • ***
  • Posts: 113
    • View Profile
I assumed that people will update their votes to make sure they can get all 100 evil delegates replaced by good ones so that the honest chain can take over.

Now we need something to distinguish bad and good delegates.

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
So, if a single good delegate can create his own chain and eventually cause it to be the longest chain and repair the network, what prevents a single attacker delegate from taking over?  Could the attacker delegate create extra false transactions which vote it additional attacker delegates, and take over that way?

The single attacker delegate can only potentially make his fork the longest chain if he actually has enough stake in his control to vote in 101 new delegates. Without that his chain will be disregarded by everyone. So let's say the single attacker delegate was voted into rank 101 (currently require 8.23% approval). In order to replace delegates ranked 1 to 100 with his sockpuppet delegates he would need a higher percentage of stake than the approval of the delegate at rank 1 (currently 18.59%). But if the attacker already had 18.6% stake, he wouldn't need to trick people to vote for him into rank 101. He could have just voted in all 101 of his attack delegates at once. This is a traditional stake attack, not a delegate attack.

This means that the good chain can recover in at most 51 minutes after collecting all the valid (non-expired) transactions that vote out the 100 bad delegates and replace them with 100 good ones.

What if only 99 delegates will be voted-out on the honest chain? Or someone votes-out the honest delegate on the hostile chain?

I assumed that people will update their votes to make sure they can get all 100 evil delegates replaced by good ones so that the honest chain can take over. If they were only able to get 99 delegates replaced then the honest chain isn't able to win. Which means the voting stakeholders are stuck on the corrupted chain until enough stakeholders join them to push all 100 evil delegates out. Considering that the evil delegates are censoring transactions, eventually enough stakeholders should be motivated to take away any votes they have for the evil delegates and vote for good delegates for the purpose of returning chain operation back to normal.

I also assumed that the 100 delegate attackers do not control enough stake to replace the last remaining honest delegate (since that would be a stake attack and not an attack where they trick stakeholders into voting for the evil delegates or an attack where 100 delegates for some reason decide to collude to be evil). If they do not control enough stake they cannot vote the remaining honest delegate out of their chain (which gives them their 1 block per round disadvantage). If they do control enough stake to replace the last remaining delegate, then I view that as no different than the attack I described above when responding to Ander. Even if the last remaining honest delegate is at rank 101, they would still need to control 8.24% of all the BTS stake (currently) to fully take over the network (at least until stakeholders hard fork). It is difficult to obtain that much stake, especially when you realize that the stakeholders are likely to destroy, within the hard fork chain, any stake voting for the 101 evil delegates in the main chain. In that case, you can think of the attackers buying up 8.24% of BTS as giving a donation to the remaining 91.76% of stakeholders to compensate them for the burden of having to do a hard fork.

Finally, there is a chance that all 101 stakeholder-voted delegates spontaneously decide to collude together and become evil (or an attacker is able to convince stakeholders to vote all 101 of their sockpuppets into the top 101 ranks). In that case, they can take control of the network (at least until stakeholders hard fork) even without having any BTS stake. But the probability of this happening is incredibly low. And again, the way that the stakeholders recover is through the hard fork procedure (which I described here).

We'll get two chains of the same power => double-spending made for free.

As I explained before, I believe (I appreciate if devs will confirm this) that the longest chain metric is only valid if the fork point is less than 16*101 blocks (roughly 4 hours) from the head block. I explained how even if there is one honest delegate it is possible for the good chain to become the longest chain (thus resolving the attack) before this reorganization limit is reached. What this means is that in these very rare scenarios of hostile delegate attacks in which the good chain is able to fight back against the attack after a few rounds, the transactions included as old as 4 hours ago will need to be moved over to the new (good) chain. So there is a potential for double spend to occur for those transactions specifically.

In these incredibly rare situations, someone who gave away goods/services less than 4 hours after confirming the transaction that paid them in the blockchain could be at risk of a double spend. Big deal. The risk is so incredibly low, plus you likely have other means (legal) of deterring an attacker from attempting this. If it is a really big transaction with no other deterrence available to protect from double spends (say a crypto/crypto exchange with an anonymous counterparty for a very large sum of money) it is probably best to design the transactions (escrow, atomic cross chain trades) so that either party can back out after 1 day, and to actually wait at least half a day before actually finalizing the transaction. But for regular transactions with merchants, it is a non-issue.

« Last Edit: February 03, 2015, 10:29:55 am by arhag »

Offline Come-from-Beyond

  • Full Member
  • ***
  • Posts: 113
    • View Profile
This means that the good chain can recover in at most 51 minutes after collecting all the valid (non-expired) transactions that vote out the 100 bad delegates and replace them with 100 good ones.

What if only 99 delegates will be voted-out on the honest chain? Or someone votes-out the honest delegate on the hostile chain? We'll get two chains of the same power => double-spending made for free.

Any game that allows a minority to win can be used for malicious things...

Offline Come-from-Beyond

  • Full Member
  • ***
  • Posts: 113
    • View Profile
How does NXT fix this 51% problem ?

Nxt doesn't have delegates. A briber have to pay to almost everyone.

Offline Ander

  • Hero Member
  • *****
  • Posts: 3506
    • View Profile
  • BitShares: Ander
Thanks arhag!


So, if a single good delegate can create his own chain and eventually cause it to be the longest chain and repair the network, what prevents a single attacker delegate from taking over?  Could the attacker delegate create extra false transactions which vote it additional attacker delegates, and take over that way?
https://metaexchange.info | Bitcoin<->Altcoin exchange | Instant | Safe | Low spreads

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
See here: https://github.com/BitShares/bitshares/blob/master/libraries/blockchain/chain_database.cpp#L900

Yup, it appears to be like I originally assumed. Which means that when it is time for the fired delegate to sign the block, they have the option of doing so. Not sure whether the default client is set up to do it or not (probably does), but it is not like we can rely on that anyway since the delegate can just turn block production off as soon as they are fired. So the assumption should be that if in the very first block of a round all other 100 delegates lose rank in the top 101, then worst case there will be 100 missing blocks until the next round.

Of course my assumption was that the 1 honest delegate waits until they can produce a block in the last four blocks of a round so that they can avoid that 100 block starting disadvantage. The recovering mechanism I discussed in this post should work fine with the way the delegate updating is done in the current code. I don't really think the code needs to be changed.

What is far more important is that blocks not have hard size limitations that make them invalid blocks if they exceed that size. That way all of the vote update transactions could be stuffed in the single honest delegate's block. Each transaction can still have a max size to prevent abuse.

Edit:
But if we do want to change the code to allow active delegates to be replaced mid-round (to make recovering from the attacks discussed in this thread more convenient for example), then I have a suggestion on how it could be done. So let's say the round begins with block N (where N % 101 == 1). Let's say the order of the delegates producing blocks in this round is (D1, D2, ..., D100, D101). After the first 4 blocks have been produced we are at block N+4 to be produced by delegate D5 and the remaining blocks in the round are to be produced by o=(D6, D7, ..., D100, D101) in that order as of now. Transactions included in block N+4 cause some of the delegates in the set of top 101 delegates to be replaced by another set of delegates of the same size. So let's pretend R={D2, D3, D6, D80, D101} are replaced by A={D102, D103, D104, D105, D106}. Also define a new set of safe delegates, S, which includes all of the delegates who have already produced blocks in this round as well as the delegate producing the current block and the next block (as determined by the current order). So in this case S={D1, D2, D3, D4, D5, D6}. The clients split the remaining delegate order sequence for the round into a head (h=D6) and the tail (tail = (D7, ..., D100, D101)). Take the set consisting of the delegates in tail as T. Define R' = R \ S, which in this example would be R'={D80, D101}. The cardinality of R' is the number of delegates that we can choose from A to create the set A', which is the set of delegate that need to replace the delegates in R' from the tail. Order the delegates in set A according to their approval (and in the case of ties, lexicographical ordering according to their account address), and pick the |R'| delegates with the highest approval from that list to form the set A'. In this example if we assume D102 and D104 have the highest approval rating compared to the rest in A, then A'={D102, D104}. Define T' = (T \ R') ∪ A', in this example T'={D7, D8, ..., D78, D79, D81, D82, ..., D99, D100, D102, D104}. Then create a new tail, tail', which is a sequence consisting of the elements in T' in some random order (use the current random seed as of block N+4 as the random value). I will mathematically represent this as tail' = permutation(T', get_current_random_seed()). Then prepend h to this new tail to get the sequence o' = h || tail' that defines the order of the delegates to produce the remaining blocks N+5 to N+100 (assuming no further changes to the set of active delegate). At the end of the round, the regular method for determining the new active delegates and their order is used (this way D103, D105, and D106 in this example get to be included in the following round). This procedure ensures that the next block producer remains the same even if the current block causes him to no longer be in the top 101 ranks (I think this is important for predictability and performance).

So with the above in place, the single honest delegate is in a better position for recovering from the attack from the other 100 evil delegates. No matter which block he starts the fork off from, the block disadvantage is going to be zero compared to the other evil chain. That means after the next round is complete (assuming they elect 101 new good delegates who don't miss their blocks), the good chain will become the longest chain (by just 1 block but then it will just grow from there). This means that the good chain can recover in at most 51 minutes after collecting all the valid (non-expired) transactions that vote out the 100 bad delegates and replace them with 100 good ones.
« Last Edit: February 03, 2015, 06:06:29 am by arhag »


Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
This is my understanding also, except that I don't know why offline clients would require manual intervention on resyncing.

I think you were referring to the previous version of my post which I edited to correct that mistake prior to you pressing the quote button :).

I originally was worried about whether the offline clients would automatically be able to resolve the fork or not because (I think) I remember one of the devs saying there are situations where the client will just stop at a fork and need a trusted checkpoint. I don't think this situation is one of those cases though. I think that would happen only when the client cannot trust the longest chain metric to resolve a fork between two chains because the fork occurs due to the a majority of the same set of delegates double signing blocks. Some clarification from the devs would be appreciated here. Basically, because of Nothing-at-Stake, when the client is syncing after being offline for some time (past chain reorganization limits) it cannot always rely on longest chain since they can be tricked onto a fake chain forked off by 101 delegates that simultaneously existed at some point in the blockchain history (but are now presumably fired/retired).

I did think delegates could be voted out mid-round, but it looks like you're right on that unless I'm missing something.  I think this is a bug that should be corrected, and that a delegate should not be expected to confirm a block that revokes his active delegate status by voting him out of the top 101.

I would like clarification from the devs on what happens when a delegate, who has yet to produce their block for the round, is replaced due to the transactions included in a block within that round that comes before their block. Does the old delegate still produce the block in that round and then get fired in the next round? Does the delegate that replaced him take over? How do we even determine which delegate replaced the old delegate? Or do we just consider that block to be one that will be missed?

Offline Troglodactyl

  • Hero Member
  • *****
  • Posts: 960
    • View Profile
By the way, I haven't had time to carefully read the entire 8 pages, but I think it is worth commenting on the exchange between Troglodactyl and Come-from-Beyond. This is how I understand the consensus mechanism of DPOS to work (I would appreciate any corrections in my understanding by the devs).

Let's say 100 delegates are colluding to ignore any transactions that update the votes against their favor. They are also ignoring all blocks by the remaining honest delegate. They have 100/101 = 99% delegate participation. People are creating, signing, and broadcasting transactions that changes the vote for their balance away from the evil delegates and to other honest delegates. There exists enough transactions that if included in the blockchain would cause the delegates of the next round to be 101 honest delegates. However, anytime the single honest active delegates includes these transactions, the other delegates ignore his block.

The single honest delegate can wait until a round in which he is one of the last 4 block producers (this happens approximately 4% of the time every 17 minutes, which means it would take 1.5 days for there to be a greater than 99% probability of this opportunity opening up). If the single honest active delegate builds off the longest current chain created by the other colluding 100 evil delegates and includes as many transactions as possible in his block to get as many honest new delegates to replace the other 100 evil delegates, then this honest delegate could create a fork that reaches the next round with (ideally) a set of 101 honest delegates and with anywhere from 0 to 4 blocks less than the original chain created by the 100 evil delegates (which is why clients will ignore this fork for now). In this next round, all of the (ideally) 101 honest delegates in the competing fork each create a valid block (and include other remaining vote update transactions to get the number of honest delegates in the following rounds to 101 if it isn't already). If there were in fact 101 honest delegates in this round, that means they gain a one block advantage compared to the competing fork created by the colluding 100 evil delegates. After four more rounds like this, they will have a longer chain than the chain created by the 100 evil delegates. Even if the first round of the fork does not have 101 honest delegates (because it was impossible to stuff enough transactions in a single block to replace all 100 evil delegates), realistically, it just means that a few more rounds are needed before they have the longest chain. If they can get this longest chain within 16 rounds (before the chain reorganization limit), all live clients will switch over to that new chain run by the honest set of delegates. Clients that were offline during this transition and trying to resync some time later will then (I think?) choose the longest chain which would at that point be the one run by the 101 new honest delegates and not the one by the 100 old evil delegates whose chain would keep falling further behind.

So, if my assumptions about the details of how DPOS works is true, it means that even if one honest delegate remains, it is possible for the network to recover without hard forks in a reasonable amount of time. Now if all 101 delegates are evil and colluding together, then stakeholders have to resort to the hard fork method which I discussed in my previous post.

This is my understanding also, except that I don't know why offline clients would require manual intervention on resyncing.  They should sync to the active network, and may not even be aware that a fork existed unless they are isolation attacked.

I did think delegates could be voted out mid-round, but it looks like you're right on that unless I'm missing something.  I think this is a bug that should be corrected, and that a delegate should not be expected to confirm a block that revokes his active delegate status by voting him out of the top 101.

Issue created: https://github.com/BitShares/bitshares/issues/1344

EDIT: Strikethrough response to ninja edited comments.  :P
« Last Edit: February 03, 2015, 04:41:40 am by Troglodactyl »

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
By the way, I haven't had time to carefully read the entire 8 pages, but I think it is worth commenting on the exchange between Troglodactyl and Come-from-Beyond. This is how I understand the consensus mechanism of DPOS to work (I would appreciate any corrections in my understanding by the devs).

Let's say 100 delegates are colluding to ignore any transactions that update the votes against their favor. They are also ignoring all blocks by the remaining honest delegate. They have 100/101 = 99% delegate participation. People are creating, signing, and broadcasting transactions that changes the vote for their balance away from the evil delegates and to other honest delegates. There exists enough transactions that if included in the blockchain would cause the delegates of the next round to be 101 honest delegates. However, anytime the single honest active delegates includes these transactions, the other delegates ignore his block.

The single honest delegate can wait until a round in which he is one of the last 4 block producers (this happens approximately 4% of the time every 17 minutes, which means it would take 1.5 days for there to be a greater than 99% probability of this opportunity opening up). If the single honest active delegate builds off the longest current chain created by the other colluding 100 evil delegates and includes as many transactions as possible in his block to get as many honest new delegates to replace the other 100 evil delegates, then this honest delegate could create a fork that reaches the next round with (ideally) a set of 101 honest delegates and with anywhere from 0 to 4 blocks less than the original chain created by the 100 evil delegates (which is why clients will ignore this fork for now). In this next round, all of the (ideally) 101 honest delegates in the competing fork each create a valid block (and include other remaining vote update transactions to get the number of honest delegates in the following rounds to 101 if it isn't already). If there were in fact 101 honest delegates in this round, that means they gain a one block advantage compared to the competing fork created by the colluding 100 evil delegates. After four more rounds like this, they will have a longer chain than the chain created by the 100 evil delegates. Even if the first round of the fork does not have 101 honest delegates (because it was impossible to stuff enough transactions in a single block to replace all 100 evil delegates), realistically, it just means that a few more rounds are needed before they have the longest chain. If they can get this longest chain within 16 rounds (before the chain reorganization limit), all live clients will switch over to that new chain run by the honest set of delegates. Clients that were offline during this transition and trying to resync some time later will then (I think?) choose the longest chain which would at that point be the one run by the 101 new honest delegates and not the one by the 100 old evil delegates whose chain would keep falling further behind.

So, if my assumptions about the details of how DPOS works is true, it means that even if one honest delegate remains, it is possible for the network to recover without hard forks in a reasonable amount of time. Now if all 101 delegates are evil and colluding together, then stakeholders have to resort to the hard fork method which I discussed in my previous post.
« Last Edit: February 03, 2015, 03:41:43 am by arhag »