Author Topic: How Do Bitshares DACs Solve The "Nothing At Stake" Problem  (Read 4938 times)

0 Members and 1 Guest are viewing this topic.

Offline AsymmetricInformation

  • Full Member
  • ***
  • Posts: 67
    • View Profile
    • Truthcoin
Re: How Do Bitshares DACs Solve The "Nothing At Stake" Problem
« Reply #15 on: August 03, 2014, 11:25:20 pm »
What do you mean when you say "Nope"? This is the long-range NaS as described by everyone I could find who wrote about it.

Which of the 6 steps do you disagree with?

Step 4... they tell their computer to build a completely different blockchain history....

Their computer could only produce 1 block every 110 seconds and thus their chain would be 1% the length of the real history.   Unless you controlled enough shares to completely change the 101 delegate slate to one you control you will never be able to create a longer chain.

At t= -12 years, yes this may be the case. But, I assume the protocol has something in place if delegates miss blocks, and so blockchains that contain missed-blocks can continue without the protocol collapsing. As the attacker re-writes history, he will eventually manipulate 'who becomes a delegate' in his fake chains. Once he controls the delegates, he can hit 100% of the blocks for the next 12 years. Because legitimate blocks are sometimes missed accidentally, his chain might be longer after 12 years (although it would have an easily-detectible "era" of 1% delegate-participation).

And this is highly sensitive to the setup. If someone knew certain "old" private keys (key to something that held a lot of BTS funds 12 years ago, or was a delegate 12 years ago), or made certain preparation transactions, it can just get much easier. These are the long run NaS problems, and I'm not sure they can be solved by using protocol rules. PoW is more Physics than it is Computer Science or Game Theory. But perhaps attacks can be made to be prohibitively difficult.

Offline toast

  • Hero Member
  • *****
  • Posts: 4001
    • View Profile
  • BitShares: nikolai
Re: How Do Bitshares DACs Solve The "Nothing At Stake" Problem
« Reply #16 on: August 04, 2014, 12:13:12 am »
How does he manipulate who becomes the delegate? He cannot forge votes

Sent from my SCH-I535 using Tapatalk

Do not use this post as information for making any important decisions. The only agreements I ever make are informal and non-binding. Take the same precautions as when dealing with a compromised account, scammer, sockpuppet, etc.

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
Re: How Do Bitshares DACs Solve The "Nothing At Stake" Problem
« Reply #17 on: August 04, 2014, 12:28:32 am »
At t= -12 years, yes this may be the case. But, I assume the protocol has something in place if delegates miss blocks, and so blockchains that contain missed-blocks can continue without the protocol collapsing. As the attacker re-writes history, he will eventually manipulate 'who becomes a delegate' in his fake chains. Once he controls the delegates, he can hit 100% of the blocks for the next 12 years. Because legitimate blocks are sometimes missed accidentally, his chain might be longer after 12 years (although it would have an easily-detectible "era" of 1% delegate-participation).
But delegates have limited powers, so there is a limit to how much history can be re-written. They can only filter out legitimate transactions. They cannot grow a small group of delegates into 100% of delegate control, unless they already had the legitimate stake to pull it off in the first place (but that is a different attack, the so-called 51% attack that all consensus systems suffer from).

Let us instead assume that 98 former delegates, who were all delegates at the same time at t = -1 week, come together to pull off a double-spend attack on some victim. I am assuming that they do not have enough stake available at t = -1 week to vote all of their fake delegates into the 101 active delegate slots. They have to deal with only being able to sign 98% of the blocks in their fake blockchain history. Let us also assume that the victim is synchronizing the blockchain starting from the genesis block on a new computer, and that the victim's internet connection is completely controlled by the attackers. Obviously I am setting up an extreme example here. Now, if the attacker presents the fake blockchain history to the victim, will the victim's client accept it? Since at t = -1 week, 3 delegates all simultaneously started missing all of their blocks until the present (t=0), the client will find this blockchain history extremely suspicious (despite the fact that average delegate participation over this period is 97%) and will warn the user that he is likely under attack. It may be possible that those 3 delegates all suddenly disconnected from the network and even after a week the shareholders of the DAC just haven't bothered to vote them out yet, but it is incredibly unlikely that it is safer to assume the user is under attack. The user can now use out-of-band methods to figure out if he is on the correct chain or not. If it was in fact an unusual event, he can snapshot past that point to let the client continue without complaining.

So that was a pretty extreme example that would not be successful. What about an even more extreme example. What if all 101 former delegates who were all delegates at the same time at  t = -1 week, now decide to collude together and do a double-spend attack since they are fired and no longer have anything at stake? In this case, if someone is synchronizing the block chain starting from a time t < -1 week and their internet access is completely compromised, they might accept the fake blockchain and thus be vulnerable to a double-spend attack. But this is an incredibly unlikely situation. You need 101 delegates who used to be active delegates at the same time to collude together to attack a potential victim, AND do a man-in-the-middle attack on the victim's internet connection, AND hope the last time the victim had synchronized with the network was before the first colluding delegate got fired.

Offline bytemaster

Re: How Do Bitshares DACs Solve The "Nothing At Stake" Problem
« Reply #18 on: August 04, 2014, 12:30:33 am »
What do you mean when you say "Nope"? This is the long-range NaS as described by everyone I could find who wrote about it.

Which of the 6 steps do you disagree with?

Step 4... they tell their computer to build a completely different blockchain history....

Their computer could only produce 1 block every 110 seconds and thus their chain would be 1% the length of the real history.   Unless you controlled enough shares to completely change the 101 delegate slate to one you control you will never be able to create a longer chain.

At t= -12 years, yes this may be the case. But, I assume the protocol has something in place if delegates miss blocks, and so blockchains that contain missed-blocks can continue without the protocol collapsing. As the attacker re-writes history, he will eventually manipulate 'who becomes a delegate' in his fake chains. Once he controls the delegates, he can hit 100% of the blocks for the next 12 years. Because legitimate blocks are sometimes missed accidentally, his chain might be longer after 12 years (although it would have an easily-detectible "era" of 1% delegate-participation).

And this is highly sensitive to the setup. If someone knew certain "old" private keys (key to something that held a lot of BTS funds 12 years ago, or was a delegate 12 years ago), or made certain preparation transactions, it can just get much easier. These are the long run NaS problems, and I'm not sure they can be solved by using protocol rules. PoW is more Physics than it is Computer Science or Game Theory. But perhaps attacks can be made to be prohibitively difficult.

Actually the protocol does not have any way to regenerate delegates except for the 5% inactivity fee which will slowly remove votes and the corresponding balances over time.   It would take a very long time and the attacker would still require a large enough stake to vote themselves in.   During this long period of time there would be a lot of missed blocks.

The only time the network cannot "heal" is if the top 101 delegates are all taken out at once.   
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 AsymmetricInformation

  • Full Member
  • ***
  • Posts: 67
    • View Profile
    • Truthcoin
Re: How Do Bitshares DACs Solve The "Nothing At Stake" Problem
« Reply #19 on: August 04, 2014, 02:53:31 am »
In long range NaS, the attacker has access to many private keys that used to own BTS (some assume 51% stake worth). With this he can control 100% of the delegates, at the cost only of recovering old private keys that are no longer in use. This may cost very little, as old private keys are not worth much to their previous owners, but the attacker can buy them (and check that he is getting what he paid for) and use them to attack the network. Over time, the number-of-old-private-keys increases drastically, as does the stake-of-old-key, the age-of-key, and the potential-attack-damage. So over 50 years or so this might be a problem.

If he cannot ever accumulate 51% worth of old-private-key, (it appears to me based on my current understanding) in dpos he can still eventually control 100% of the delegates with <51% old-stake by selectively broadcasting valid tx and controlling certain few addresses and ex-delegate accounts. For example, the normal network history might have some individuals rise from #107 and #108 up to #97 and #98, displacing my delegate at position #99. If I control the alternative chain, I can instead avoid brodcasting the tx that bumps my delegate.

Offline tonyk

  • Hero Member
  • *****
  • Posts: 3308
    • View Profile
Re: How Do Bitshares DACs Solve The "Nothing At Stake" Problem
« Reply #20 on: August 04, 2014, 03:25:14 am »

I can see a real trouble looming for DPOS after 500 years…


or was it delegates going to Guantanamo tomorrow?
Lack of arbitrage is the problem, isn't it. And this 'should' solves it.

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
Re: How Do Bitshares DACs Solve The "Nothing At Stake" Problem
« Reply #21 on: August 04, 2014, 07:20:08 am »
If he cannot ever accumulate 51% worth of old-private-key, (it appears to me based on my current understanding) in dpos he can still eventually control 100% of the delegates with <51% old-stake by selectively broadcasting valid tx and controlling certain few addresses and ex-delegate accounts. For example, the normal network history might have some individuals rise from #107 and #108 up to #97 and #98, displacing my delegate at position #99. If I control the alternative chain, I can instead avoid brodcasting the tx that bumps my delegate.

You need nearly all of the top 101 delegates under your control at the same point in time in the blockchain history in order to continue the fake history in a way that could appear plausibly legitimate to your victim's client. If you do not have nearly all of the top 101 delegates under your control at the same point in time, you cannot continue the history for long enough (without making it obviously apparent that it is an attack) to gain control of all of the top 101 delegates.

Let me explain with an example. Time t = 0 is when the DAC begins building on the genesis block. One year later, at t = 1, we have the following delegate ranking. There are 101 good delegates in the top 101 spots: good-delegate-1, good-delegate-2, ..., good-delegate-101. They each have 20% approval. The next 101 slots are filled by your evil delegates: evil-delegate-1, ..., evil-delegate-101. They each have 2% approval, all from the 2% stake you control. The next 101 slots are filled by 101 other good delegates, good-delegate-102 to good-delegate-202,  each with only 1% approval. Over the course of the next year, from t = 1 to t = 2, stakeholders start moving away their votes from good-delegate-1 ... good-delegate-101 to good-delegate-102 ... good-delegate-202. This is a slow process in which one good delegate is replaced by the other good delegate one at a time. In fact, stakeholders vote according to the following peculiar pattern. They first take all of their votes away from good-delegate-k (1 <= k <= 101) and vote for the null slate, allowing one of your evil delegates to briefly get into spot 101. Then, they use that stake to vote for good-delegate-(k+101), who replaces your evil delegate on the active delegate list. At no time do you have more than one of your evil delegates as an active delegate in the true blockchain. Can you fork off of a snapshot of the blockchain between t=1 and t=2 and generate a plausible fake blockchain that gives all of your evil delegates the top 101 slots by cleverly filtering out certain transactions?

The answer is no. You may think that you can just filter out all of the transactions that change their vote from the null slate to good-delegate-(k+101), but keep the transactions that changed the vote from good-delegate-k to the null slate in the first place. If you could do this, you would end up with all of your evil delegates in the top 101 slots with 2% approval, and the rest of the good delegates at lower slots with either 1% approval or less. But you cannot do this, because you did not have nearly all of your evil delegates simultaneously in the top 101 slots at any point in time.  The first time you would need to filter out one of these problematic transactions, you would be forced to filter out all of the blocks produced by good delegates after that point (otherwise the hash link would be broken). Now you might think you can just quickly fill in all of the transactions that change the vote to the null slate into one of the blocks produced by your delegate, so that you can have all of your evil delegates take over the next round. Not only would this look incredibly suspicious, but the conditions needed to pull this off are incredibly improbable. In practice, there will be many other transactions that those unvoting transactions depend on. You can't just stuff all of them into one block, you want to disperse them over multiple sequential blocks. However, since you do not control nearly all of the active delegates yet, you need to wait multiple rounds before you can fit all of those prerequisite transactions and the unvoting transactions that finally give you full control of all the delegates. But how many rounds of mostly missed blocks would that result in? It would be highly suspicious behavior that the client could warn user about. But if this is not satisfying enough, there is another measure that can be taken to be extra cautious. We can bring back TaPOS on top of DPOS. The transactions do not need to reference the previous block, they can reference a block well enough in the past that is well establish. The point is that TaPOS would make it impossible to even include those unvoting transactions in your fake blockchain.

In long range NaS, the attacker has access to many private keys that used to own BTS (some assume 51% stake worth). With this he can control 100% of the delegates, at the cost only of recovering old private keys that are no longer in use. This may cost very little, as old private keys are not worth much to their previous owners, but the attacker can buy them (and check that he is getting what he paid for) and use them to attack the network. Over time, the number-of-old-private-keys increases drastically, as does the stake-of-old-key, the age-of-key, and the potential-attack-damage. So over 50 years or so this might be a problem.

I am glad you recognize that even if an attacker was able to get other stakeholder's old private keys it would take many years to get enough (>51%) to create a plausible fake blockchain in order to attempt a double-spend attack. Another approach would be to aim for the private keys of old delegates. Either way, we can pretty much guarantee that users have updated their clients multiple times over this period. The client software needs to at least contain a hash of the genesis block so that it knows it is on the right chain. But every time there is a new version of the client, the developer can easily put in a recent checkpoint (a hash of a recent block) as a sanity check. That checkpoint immediately kills any attempt of attacking with a fake blockchain where the fork point is older than the checkpoint.

I think it's important to mention that having this checkpoint does not make things any more centralized or even require relying on the developer. A full audit of the code (including the checkpoint) is still possible since the auditors have a copy of the legitimate blockchain up to the point of the version upgrade, just like they would have a copy of the legitimate genesis block (or a means of determining whether the genesis block was legitimate) when doing a full audit of the first version of the code. And a regular user is always going to end up relying on other parties to determine if he is running the same program everyone else is running. Some trust is necessary. Bitcoin users need to trust their wallet developers, or trust the auditors who say that a particular version of the wallet software is safe to use (through a signed hash of the executable or source archive).
« Last Edit: August 04, 2014, 07:28:49 am by arhag »

Offline santaclause102

  • Hero Member
  • *****
  • Posts: 2486
    • View Profile
Re: How Do Bitshares DACs Solve The "Nothing At Stake" Problem
« Reply #22 on: August 04, 2014, 08:25:21 am »
Right. But not all 101, only 52...
No, you need all 101 (or something close to that), or else you will be unable to make a chain that comes to the present time without having an unusual number of missing blocks.
makes sense

Online liondani

  • Hero Member
  • *****
  • Posts: 3723
  • Inch by inch, play by play
    • View Profile
    • My detailed info
  • BitShares: liondani
  • GitHub: liondani
Re: How Do Bitshares DACs Solve The "Nothing At Stake" Problem
« Reply #23 on: August 04, 2014, 09:53:41 am »
It is impossible for DPOS to produce an alternative longer chain without collusion of 51% of the delegates.  With 51% collusion you are back to the 51% attack that all systems are subject to.

51% of individual delegates!
More individual delegates means more security! Since it will be much tougher to collude for 200 individuals instead of 30 to 100 for example...

PLEASE FIND A WAY to introduce/implement the sweat spot idea...  (because to much delegates would of course hurt the network reliability for reasons already explained)

Offline luckybit

  • Hero Member
  • *****
  • Posts: 2921
    • View Profile
  • BitShares: Luckybit
Re: How Do Bitshares DACs Solve The "Nothing At Stake" Problem
« Reply #24 on: August 04, 2014, 09:57:45 pm »
It is impossible for DPOS to produce an alternative longer chain without collusion of 51% of the delegates.  With 51% collusion you are back to the 51% attack that all systems are subject to.

51% of individual delegates!
More individual delegates means more security! Since it will be much tougher to collude for 200 individuals instead of 30 to 100 for example...

PLEASE FIND A WAY to introduce/implement the sweat spot idea...  (because to much delegates would of course hurt the network reliability for reasons already explained)

Not necessarily. It depends on the attacks. For coercion having too many individual delegates who are known would make it a lot easier to find and coerce them. If the delegates are a collective and spread out across multiple jurisdictions then it would take a globalized effort to coerce the collective of delegates. The collective if the technology allows could even share keys or use multi-sig.

Generally though you do want a lot of individual delegates involved because in other ways it does improve security. It's just a matter of what is easier to attack at the time. If for example delegates are facing political and legal attack then having the delegate be a corporation has benefits. Having it be a non-profit has benefits as well.

The idea is that the individuals should be replaceable (like batteries) but only the delegate roles are what matter to the network. The network should survive even if the individuals in those roles are corrupted, arrested, coerced, etc. The network is self healing because those delegates get fired, lessons are learned, and adaptations will take place so the same attack wont happen again.

I think the sweet spot is just the minimum amount of delegates we need to psychologically feel the network is secure. If it's not under attack it might in practice be secure with 5 delegates or less but then it's a matter of convincing a decentralization community that somehow 5 delegates can offer more security than 5 people in control of Bitcoin or Litecoin. In theory if those 5 delegates were collectives of people such as corporations then you might actually be able to do that because the ultimately security rests in the voters who can vote them out for abusing the integrity of the network.

At 101 delegates it's extremely fast. I don't see any demand for changing it to make it faster. It seems like it could scale to Visa type levels but if it required less delegates at that point in time  then the shareholders could decide. It's far better than what we have with Bitcoin.

« Last Edit: August 04, 2014, 10:09:48 pm by luckybit »
https://metaexchange.info | Bitcoin<->Altcoin exchange | Instant | Safe | Low spreads

Offline gulu

  • Full Member
  • ***
  • Posts: 121
    • View Profile
Re: How Do Bitshares DACs Solve The "Nothing At Stake" Problem
« Reply #25 on: August 05, 2014, 05:39:26 pm »
How about making the protocol such that a checkpoint is automatically added whenever there are 51 accumulative changes of delegates ?  No centralization, and now 100% safe.
BTC: 1FRsgcQELHKFY2VMFosBnyBaNxZgS4wj7x
PTS: Pf9yDYUknXShepu6YjwSEpMvm1ewNQLNgE
BTSX: gulu

Offline toast

  • Hero Member
  • *****
  • Posts: 4001
    • View Profile
  • BitShares: nikolai
Re: How Do Bitshares DACs Solve The "Nothing At Stake" Problem
« Reply #26 on: August 05, 2014, 05:41:59 pm »
How about making the protocol such that a checkpoint is automatically added whenever there are 51 accumulative changes of delegates ?  No centralization, and now 100% safe.

51 delegate signatures *is* a checkpoint. Adding a "checkpoint" at the protocol level would just be cosmetic, it has the same effect.

Having a process for changing the client to have client-side checkpoints is what you need to have "real" checkpoints.
Do not use this post as information for making any important decisions. The only agreements I ever make are informal and non-binding. Take the same precautions as when dealing with a compromised account, scammer, sockpuppet, etc.

Offline gulu

  • Full Member
  • ***
  • Posts: 121
    • View Profile
Re: How Do Bitshares DACs Solve The "Nothing At Stake" Problem
« Reply #27 on: August 06, 2014, 03:08:32 am »
How about making the protocol such that a checkpoint is automatically added whenever there are 51 accumulative changes of delegates ?  No centralization, and now 100% safe.

51 delegate signatures *is* a checkpoint. Adding a "checkpoint" at the protocol level would just be cosmetic, it has the same effect.

Having a process for changing the client to have client-side checkpoints is what you need to have "real" checkpoints.

Right, client-side checkpoint.
BTC: 1FRsgcQELHKFY2VMFosBnyBaNxZgS4wj7x
PTS: Pf9yDYUknXShepu6YjwSEpMvm1ewNQLNgE
BTSX: gulu