Pages:
Author

Topic: Re: Proof of stake instead of proof of work - page 7. (Read 6968 times)

donator
Activity: 1218
Merit: 1079
Gerald Davis
snip

https://nxtforum.org/general/how-does-nxt-fix-the-nothing-at-stake-problem/msg22882/#msg22882

Quote
Hehe, so sad D&T is not registered on this forum. Could anyone ask him the following:


Alice wants to attack the blockchain.
She owns private keys of 400 accounts totalling to 75% of the stake.
She is planning to rewrite the history from block 5'000.
Legit chain is at block 5'300 (less than 720).
Cumulative difficulty at block 5'000 is 8'000'000.
Cumulative difficulty at block 5'300 is 9'000'000.
How many SHA256 operations in average it's necessary to do to find a branch where cumulative difficulty at block 5'300 is at least 9'000'001?
Hint: Blocks from 5'000 to 5'300 were forged by 100% of the stake..

You can register to answer him directly on that forum  


Yeah when the thread is filled with insults before a countering view is even posted I don't really see the point.  Still the example is flawed.  There is no assumption that all of Alice's "old coins" would be contributing to the stake.  100% of the money supply isn't being used for forging it isn't a valid assumption that 100% of the coins she sold would be used as well.  Still it is possible depending on how much stake Alice had and how much of it ends up supporting the main chain she might not be able to sell all of the coins.  The attacker may only have reduced amount at risk rather than nothing at risk scenario.
donator
Activity: 1218
Merit: 1079
Gerald Davis
True. So, how do new Bitcoin nodes handle this issue?

Simple the longest chain is the best chain.  The behavior is deterministic.  It doesn't matter if a node is online, offline, or newly created, all nodes select the longest.  There is only an issue where nodes select a chain based on criteria that can't be known to all nodes (i.e. chain A is shorter but it is the best chain because it came first and chain B is longer but came second and they differ by more than 720 blocks).


True.

New nodes would need to make sure they are on the legit chain.

But well, how do "Bitcoin" nodes? <<< I mean having a client looking like Bitcoin and feeling like Bitcoin does not necessarily mean it is the real Bitcoin network you are on, right?

Best is probably a better term than "legit" it is possible the best chain is the one created by an attacker (in both PoS & PoW) however the consensus system is limited to picking the best chain.  The chain built from the genesis block which is the longest is the best chain.  Any new node is relying on an assumption that other nodes are using the same selection criteria.  If all nodes are using the same selection criteria (and it is deterministic and uniform across all nodes) they will all end up selecting the same chain as the "best" one.

Quote
It always comes down to that: costs. And I am with you: the costs for maintaining several PoS chains are significantly smaller than maintaining several PoW chains. However, I doubt 720 block to be sufficiently long enough to do any damage.

If it can be done once it can be done again.  An attacker would be foolish to limit it to a single attack.  If merchants are limited to waiting for 719 confirmations to ensure they aren't double spent then the attacker has done a good job of damaging the utility of the coin.  The ability to fork offline clients is just an added bonus to add to the chaos.  If your node goes offline you can't be assurance that you are on the same chain as other nodes.
sr. member
Activity: 364
Merit: 250
☕ NXT-4BTE-8Y4K-CDS2-6TB82
Then the network can be attacked by hard forks.  New nodes (or nodes temporarily offline) will see a reorg of greater than 720 blocks as valid and be permanently forked from the nodes who were online and saw the reorg as invalid because it was too deep.

True. So, how do new Bitcoin nodes handle this issue?

One doesn't need to buy the coins in any period of time.  One could take years to acquire the coins.

Sorry, that was my mistake. I meant, first ( buying 51% of all PoS tokens ) and then ( selling 51% of all PoS within 720 block ) are both ambitious goals each and even more ambitious done together.

The clock starts from the point of the reorg which can be just prior to selling the coins.  One doesn't even need to buy coins they only need to buy the history of coins.  A private key which at one point had unspent outputs worth x coins but today has no unspent outputs ("zero  balance address") has no direct value to the owner but to an attacker it has value in attacking the network.

Interesting point. So, if you find many somebodies who would be willing to sell their historical passphrases...

The attack isn't limited to 720 blocks.  It just means the attacker will be unable to re-org all nodes.

True.

New nodes would need to make sure they are on the legit chain.

But well, how do "Bitcoin" nodes? <<< I mean having a client looking like Bitcoin and feeling like Bitcoin does not necessarily mean it is the real Bitcoin network you are on, right?

So, new nodes need to verify anyway no matter if PoW or PoS. Is that correct?

However by making a re-org of longer than 720 blocks (if you are right about a lack of centralization) the network can be forked permanently which is equally disruptive and quite a feat for an attack with no cost or risk.

Still the point that you moved the goal posts is good enough for me.  I think you do now see that someone can attack the network without cost or risk which was the point you refuted.  You have now moved to how difficult it would be to acquire that stake which is a totally different argument. 

I see where your are coming from and tend to agree, if I would not substitute 'difficult' by 'expensive'.

It always comes down to that: costs. And I am with you: the costs for maintaining several PoS chains are significantly smaller than maintaining several PoW chains. However, I doubt 720 block to be sufficiently long enough to do any damage.
hero member
Activity: 644
Merit: 500
snip

https://nxtforum.org/general/how-does-nxt-fix-the-nothing-at-stake-problem/msg22882/#msg22882

Quote
Hehe, so sad D&T is not registered on this forum. Could anyone ask him the following:


Alice wants to attack the blockchain.
She owns private keys of 400 accounts totalling to 75% of the stake.
She is planning to rewrite the history from block 5'000.
Legit chain is at block 5'300 (less than 720).
Cumulative difficulty at block 5'000 is 8'000'000.
Cumulative difficulty at block 5'300 is 9'000'000.
How many SHA256 operations in average it's necessary to do to find a branch where cumulative difficulty at block 5'300 is at least 9'000'001?
Hint: Blocks from 5'000 to 5'300 were forged by 100% of the stake..

You can register to answer him directly on that forum 
donator
Activity: 1218
Merit: 1079
Gerald Davis
720 confirmations are maintained by each node separately. Maybe, we have a different notion of centralization but that is what I would call decentralized.

Then the network can be attacked by hard forks.  New nodes (or nodes temporarily offline) will see a reorg of greater than 720 blocks as valid and be permanently forked from the nodes who were online and saw the reorg as invalid because it was too deep.  Non deterministic behavior of nodes is something to be avoided, to achieve consensus all nodes must reach the same conclusions on which chain is the "best".

Buying 51% of the stake AND selling it SUCCESSFULLY within a timeframe of 720 blocks seems, well, ambitious.

The attacker has no limit on how long it takes to acquire the coins.  The clock starts from the point of the reorg which can be just prior to selling the coins.  So if attacker has x+1 coins where the network stake is 2x at block y he can start the attack chain from there.  He now has 720 blocks in which to record the sale/transfer of the coins for material gain and produce a longer chain.

The attacker isn't limited to buying "valid" coins, just the "history" of coins that a private key had in the past.  A private key which at one point had unspent outputs worth x coins but today has no unspent outputs ("zero  balance address") has no direct value to the owner but to an attacker it has value in attacking the network.  "Hey large coin holders I will buy your empty wallets based for 0.1% of the coins they had as of block y".

The attack isn't limited to 720 blocks.  A reorg of longer than 720 block is possible it just once be accepted by the entire network.  Permanently forking the network is still a powerful attack, especially for one which has no cost or risk.

The fact that you are moving the goal posts from "the history can't be used" to "this would be hard" (so is a 51% PoW attack) is good enough for me.  I think you do now see that someone can attack the network without cost or risk which was the point you refuted as false.  How difficult it would be to acquire that stake which is a totally different argument. 
sr. member
Activity: 364
Merit: 250
☕ NXT-4BTE-8Y4K-CDS2-6TB82
Even the security from 720 confirmations is due to rolling checkpoints which is a centralized protection.  Without it, it would be worse.

720 confirmations are maintained by each node separately. Maybe, we have a different notion of centralization but that is what I would call decentralized.

This explanation also ignores what we are talking about when it comes to history attack.  If at block x the attacker has 51% of the active stake the attacker can then sell his stake and thus the attacker has no cost, he no longer has any coins but as of block x he did so he can reorg from that point.   The attack can be done with no cost or risk based on the fact that in the past the attacker did have sufficient resources to perform the attack.

Buying 51% of the stake AND selling it SUCCESSFULLY within a timeframe of 720 blocks seems, well, ambitious.
legendary
Activity: 1302
Merit: 1008
Core dev leaves me neg feedback #abuse #political



If I have a rig (or more accurately a massive mining farm that is a majority of the hashing power) I have incurred a cost and I am taking a risk by executing an attack.  The difference with PoS is that an attack can be executed without cost or risk.  That would only be true for PoW if I could build a farm, then sell it, and then somehow execute an attack after the sale with the farm I don't have.  It was tongue in cheek to show that since PoW can't be exploited by history, I can't perform an attack with no cost of risk

No, you do not. Because you are anonymous and you can do it over and over again because nobody can punish you for publishing these blocks.
 


With PoW, it costs energy to do all those hashes, and you also incur the opportunity cost of not using your resources to do honest mining.
donator
Activity: 1218
Merit: 1079
Gerald Davis
The problem of finding a fork that is stronger than the legit one is well explained by Come-from-Beyond here: https://nxtforum.org/bitcoin2014-btc-foundation-conference-amsterdam-(may-15-17)/technical-questions-need-answering-from-amsterdam/msg22489/#msg22489

Imagine that the adversary have several accounts. He can build different blockchains with different sequences of blocks. Every branch will have different cumulative difficulties. The attack will be successful only if he manages to find a branch with difficulty higher than the difficulty of the legit chain. It's a problem of finding an extremum (optimization). None of the methods (gradient method, etc.) except exhaustive search over all possible combinations could be used for that coz Nxt uses SHA256. So we get classical "find the nonce a-la Bitcoin" game here.

That is for an attacker with less than half the stake.  That isn't a 51% attack, that isn't what is being discussed.

Quote
An attack with more than 50% of the stake (TF is off)

It's quite expensive to purchase 51% of all forging power. Now with Leasing it's more affordable but max depth of chain reorg is 720 blocks. So a successful attack is possible only after a successful sybil attack (to get control over 51% of active stake). Paranoid merchants should wait for 720 confirmations.

Even the security from 720 confirmations is due to rolling checkpoints which is a centralized protection.  Without it, it would be worse.  This explanation also ignores what we are talking about when it comes to history attack.  If at block x the attacker has 51% of the active stake the attacker can then sell his stake and thus the attacker has no cost, he no longer has any coins but as of block x he did so he can reorg from that point.   The attack can be done with no cost or risk based on the fact that in the past the attacker did have sufficient resources to perform the attack.
sr. member
Activity: 364
Merit: 250
☕ NXT-4BTE-8Y4K-CDS2-6TB82
The problem of finding a fork that is stronger than the legit one is well explained by Come-from-Beyond here: https://nxtforum.org/bitcoin2014-btc-foundation-conference-amsterdam-(may-15-17)/technical-questions-need-answering-from-amsterdam/msg22489/#msg22489

Imagine that the adversary have several accounts. He can build different blockchains with different sequences of blocks. Every branch will have different cumulative difficulties. The attack will be successful only if he manages to find a branch with difficulty higher than the difficulty of the legit chain. It's a problem of finding an extremum (optimization). None of the methods (gradient method, etc.) except exhaustive search over all possible combinations could be used for that coz Nxt uses SHA256. So we get classical "find the nonce a-la Bitcoin" game here.
sr. member
Activity: 364
Merit: 250
☕ NXT-4BTE-8Y4K-CDS2-6TB82
Because the network follows a longest chain is valid rule?  If it doesn't then you are relying on a node knowing that an alternate chain came "later" and not all nodes will no that.  As I already pointed out up thread imagine you are a new node, you connect to the network and receive two competing chains A & B.  A is longer.  Which chain do you use?  If you use A and other nodes use B that is a problem (isolation attack and network fork due to non deterministic chain selection).  If they are choosing B over A because they "saw it first" there is no way for you to confirm that or even know that.  

Still it doesn't need to be 10,000 blocks.  A 51% attack can be accomplished with a reorg of any length.

So, you are talking about two different things:

1) new nodes

2) existing nodes


Both handle things differently.


If I have a rig (or more accurately a massive mining farm that is a majority of the hashing power) I have incurred a cost and I am taking a risk by executing an attack.  The difference with PoS is that an attack can be executed without cost or risk.  That would only be true for PoW if I could build a farm, then sell it, and then somehow execute an attack after the sale with the farm I don't have.  It was tongue in cheek to show that since PoW can't be exploited by history, I can't perform an attack with no cost of risk

No, you do not. Because you are anonymous and you can do it over and over again because nobody can punish you for publishing these blocks.


The network can't punish the bad guy.

It can because the consensus power is known to the network entirely. Existing nodes know who is going to generate the next block and therefore will not accept any derivations or re-orgs especially not those coming from ages ago.


The whole point is that PoS, the bad guy can attack without cost or risk.  How exactly does a PoS punish an anonymous entity who no longer has anything at risk and can attack you with no cost.

No cost/risk = depends on how the network punishes him. Distributing his coins, removing his coins, whatever. Because the consensus power lies within the network, the network can decide what to do if a bad guy tries to bring it down.

If that were true that checkpoints wouldn't be needed.   There is no PoW "problem".  There is a limitation that both PoS and PoW share and that is the security model only works if the attacker has less than half of the resource.  An attacker can buy computing power and an attacker can buy a stake neither are closed systems.

It is THE PoW problem. The network CANNOT simply punish bad guys. How could it? The consensus power lies outside of the control of the network.
donator
Activity: 1218
Merit: 1079
Gerald Davis
Not that I need some attention, but I would like to have answers to my questions.
I would have thought that they would be self evident by now.

Let me restate my question. Why should a node 100000 blocks ahead accept a blockchain re-organisation?

Because the network follows a longest chain is valid rule?  If it doesn't then you are relying on a node knowing that an alternate chain came "later" and not all nodes will know that.  As I already pointed out up thread imagine you are a new node, you connect to the network and receive two competing chains A & B.  A is longer.  Which chain do you use?  If you use A and other nodes use B that is a problem (isolation attack and network fork due to non deterministic chain selection).  If they are choosing B over A because they "saw it first" there is no way for you to confirm that or even know that.  

Still it doesn't need to be 10,000 blocks.  A 51% attack can be accomplished with a reorg of any length.

Um, well no. I can't mine using computing power I no longer have (but did have at one point in the past).

Our mining rigs destroy themselves? I doubt it.

If I have a rig (or more accurately a massive mining farm that is a majority of the hashing power) I have incurred a cost and I am taking a risk by executing an attack.  The difference with PoS is that an attack can be executed without cost or risk.  That would only be true for PoW if I could build a farm, then sell it, and then somehow execute an attack after the sale with the farm I don't have.  It was tongue in cheek to show that since PoW can't be exploited by history, I can't perform an attack with no cost of risk

Quote
However, the huge advantage of PoS is: the network controls the consensus power and the network can punish the bad guys. I would call this the PoW problem as the consensus power can easily be introduced from outside without any control whatsoever.

The network can't punish the bad guy.  The whole point is that PoS, the bad guy can attack without cost or risk.  How exactly does a PoS punish an anonymous entity who no longer has anything at risk and can attack you with no cost.  If that were true that checkpoints wouldn't be needed.   There is no PoW "problem".  There is a limitation that both PoS and PoW share and that is the security model only works if the attacker has less than half of the resource.  An attacker can buy computing power and an attacker can buy a stake neither are closed systems.
sr. member
Activity: 364
Merit: 250
☕ NXT-4BTE-8Y4K-CDS2-6TB82
Because it is invalid.   PoS DOES rely on checkpoints for security reasons to prevent a reorg.  Bitcoin could remove checkpoints from the code right now and no reorg attack becomes possible.  No PoS based system can do so.  They would instantly be vulnerable to the "PoS problem" without checkpoints.

You try to avoid my question from above:

Let me restate my question. Why should a node 100000 blocks ahead accept a blockchain re-organisation?
donator
Activity: 1218
Merit: 1079
Gerald Davis
Exactly.  The only "solution" is absolute centralized checkpoints which prevent reorgs prior to the checkpoint.   PoS proponents often bring up that Bitcoin uses checkpoints however they are not necessary to enforce the security of the blockchain.  Case in point the oldest checkpoint is more than 5 months old, and a 5 month reorg would destroy Bitcoin.  Checkpoints are used by Bitcoin to prevent an attacker for wasting the resources of bootstrapping nodes as a DOS attack by feeding them spoofed chains.  There is no requirement that they be centralized.  Different clients could use different checkpoints at different block heights and it would work just as well. 

Why on earth could one not use this argument for PoS as well?

Because it is invalid.   PoS DOES rely on checkpoints for security reasons to prevent a reorg.  Bitcoin could remove checkpoints from the code right now and no reorg attack becomes possible.  No PoS based system can do so.  They would instantly be vulnerable to the "PoS problem" without checkpoints.
sr. member
Activity: 364
Merit: 250
☕ NXT-4BTE-8Y4K-CDS2-6TB82
Exactly.  The only "solution" is absolute centralized checkpoints which prevent reorgs prior to the checkpoint.   PoS proponents often bring up that Bitcoin uses checkpoints however they are not necessary to enforce the security of the blockchain.  Case in point the oldest checkpoint is more than 5 months old, and a 5 month reorg would destroy Bitcoin.  Checkpoints are used by Bitcoin to prevent an attacker for wasting the resources of bootstrapping nodes as a DOS attack by feeding them spoofed chains.  There is no requirement that they be centralized.  Different clients could use different checkpoints at different block heights and it would work just as well. 

Why on earth could one not use this argument for PoS as well?
sr. member
Activity: 364
Merit: 250
☕ NXT-4BTE-8Y4K-CDS2-6TB82
Not that I need some attention, but I would like to have answers to my questions.

Okay, I got that. However, calling it a problem is a rather bold claim. I would call it a property of PoS.
It is more than a "property" it is an as of yet unresolved problem.  There is no security in PoS unless it is resolved.

Let me restate my question. Why should a node 100000 blocks ahead accept a blockchain re-organisation?

Quote
(No matter if PoS or PoW)

Um, well no. I can't mine using computing power I no longer have (but did have at one point in the past).

Our mining rigs destroy themselves? I doubt it.

Quote
How would want to be on that fork anyway? In doing so, they would destroy every single bit of confidence in that very cryptocurrency.

The cost to the attacker is absolutely zero.  If he can gain anything more than zero he has everything to gain and nothing to lose.   It would destroy confidence in the PoS currency you are correct especially when it happens over and over and over without end.  That is why it is the Pos problem.

Well, as I said this is true for PoS and PoW. Trying to destroy would definitely diminish confidence in the cryptocurrency as such no matter if PoS or PoW.

Your statement about 'no cost' is true as well.

However, the huge advantage of PoS is: the network controls the consensus power and the network can punish the bad guys. I would call this the PoW problem as the consensus power can easily be introduced from outside without any control whatsoever.
legendary
Activity: 1302
Merit: 1008
Core dev leaves me neg feedback #abuse #political
donator
Activity: 1218
Merit: 1079
Gerald Davis
Wow, thanks DaT..  for getting me all paranoid.  I guess this is avoided in PoW by difficulty weighting.  In other words, if I say here take a look at my big chain 400,000 blocks also starting from the same satoshi genesis that I produced in 1 hour falsifying timestamps, this is longer than the current chain use me!   a node would say:  yeah great, but the difficulty was 0.001 the whole time that is not really a longer chain than our current BTC chain.  At least, I sure hope that's in the code.

It is.  The phrase "longest chain" is just used because "chain with the largest sum of the difficulty of the blocks in the chain selected among all valid chains" becomes a lot to write.  It is trivial for nodes to make this selection because difficulty is encoded in the block header and validated at the time the blockheader is validated.  Nodes simply sum the difficulty of the blocks in the chain and compare it to other chains to pick the "longest".

As a side note the network also enforces the difficulty change rules. Difficulty can't be less than 1 and is recomputed every 2016 blocks.  A block with invalid difficulty is invalid.  The timestamp of the genesis block is hardcoded in clients.   To keep the difficulty at 1 would require that the time between blocks remain 10 minutes.  While an attacker can fake timestamps he can't use an incorrect difficulty. So to have a chain of 300,000 blocks @ difficulty 1 would require 3,000,000 minutes since the genesis block.  That would put block 300,000 about 6 months into the future.   As a secondary check any block more than 3 hours from the network median time so to make a valid chain which has a valid timestamp for block 300,000 would require higher than difficulty 1.   

Quote
Unfortunately stake difficulty doesn't represent real work so it can always be faked in a reorg going back to some substantial early stake as you point out to us.

Exactly.  The only "solution" is absolute centralized checkpoints which prevent reorgs prior to the checkpoint.   PoS proponents often bring up that Bitcoin uses checkpoints however they are not necessary to enforce the security of the blockchain.  Case in point the oldest checkpoint is more than 5 months old, and a 5 month reorg would destroy Bitcoin.  Checkpoints are used by Bitcoin to prevent an attacker for wasting the resources of bootstrapping nodes as a DOS attack by feeding them spoofed chains.  There is no requirement that they be centralized.  Different clients could use different checkpoints at different block heights and it would work just as well. 
donator
Activity: 1218
Merit: 1079
Gerald Davis
Maybe this is just another half-baked idea, but couldn't the PoS be implemented in such a way that once a certain number of blocks are in place, the time stamp is verified and you can't go back and build a longer chain?

This works if all nodes learn of blocks in real time as they occur. What about nodes that are offline at the time the blocks are created?  Say you are offline and when you come online you learn of two chains A & B.  A is longer.  Since you have no knowledge that B occurred "first", you use "A" as the primary chain.  However what you don't know is that most nodes are using B because it occurred "first".  The network had forked because chain selection is no longer uniform among nodes.  A new variable has been added which is not consistent for all nodes.   From this point of view a new node is very similar to an offline node except it has been offline since the genesis block.

The fact that it becomes trivially easy to fork the network is an attack in itself.  The attack can be extended to double spend for financial gain.  Isolation attacks are always a risk in p2p networks however in "longest chain wins" as the sole rule for consensus they are reasonably difficult as if the victim node connects to any non-attack node they will learn of the longer chain.   If this rule is not enforced (i.e. most of network favors "B" even though it is shorter) then an attacker can "isolate" a node coming online by simply connecting to it.  Even if the victim node is connected to other non-attack nodes it will pick A over B and be isolated from the majority of the network because the chain selection is not consistent across all nodes.   Once a node is on chain A the attacker can double spend the victim, waiting for 6, 12, 20,000 confirmations is insufficient to ensure a transaction is valid.

It is often a good idea to step back and consider WHY we use a blockchain.  The blockchain is a timestamp mechanism.  It used because no other decentralized provable timestamping system exists.   If we could prove which chain was made first we could also prove which transaction was created first.   We wouldn't even need a blockchain or confirmations.
legendary
Activity: 1302
Merit: 1008
Core dev leaves me neg feedback #abuse #political
Maybe this is just another half-baked idea, but couldn't the PoS be implemented in such a way that once a certain number of blocks are in place, the time stamp is verified and you can't go back and build a longer chain?

For example, jan 1 you spend 1.1M coins.
Jan 5th, you try to build a longest chain starting
From jan 1, but no nodes will accept it because
It's too far in the past.

This is what I meant by implementation.

I think nxt might do this with a 12 or 24 hour period.
I guess the flip side is that that is long confirmation
period.  But at least you couldn't tear down the chain
Back to the genesis block.
hero member
Activity: 784
Merit: 1000
The cost(work) it takes to produce a PoS chain, is the cost it takes to duplicate("fake") one, that's probably all there needs to be said about it.
Pages:
Jump to: