Bitcoin Forum
November 24, 2017, 07:07:30 PM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 3 4 5 6 7 8 9 »  All
  Print  
Author Topic: Nothing-at-Stake & Long Range Attack on Proof-of-Stake (Consensus Research)  (Read 14992 times)
kushti
Full Member
***
Offline Offline

Activity: 173


View Profile
December 18, 2014, 05:12:37 PM
 #1

Paper on different attacks related to multibranching forging is published by Consensus Research https://github.com/ConsensusResearch/articles-papers/blob/master/multistrategy/multistrategy.pdf

TL/DR version and consequences:

- multibranch forging gives measurable possibility to earn more fees. I guess Nxt should not ignore it in long-term as the profitable activity will be implemented by somebody sooner or later

- there's no long-range attack against a blockchain V. Buterin described, only short-range. The short-range attack doesn't allow double-spending but gives multibranching forger possibility to earn more fees in singlebranch environment by producing few blocks in a row. However producing few blocks in a row could be an issue too (e.g. evil forger may postpones orders submissions etc) but not critical at the moment.

- not explicitly stated in the paper but easily derived, a long delay between blocks not only annoying but also a security problem as it's the moment for short-range attack could happens

- we have formally defined nothing-at-stake attack(again, using Buterin's informal definition) and made initial simulations. We haven't included their results in paper as they are seems to be too raw, but I can reveal them here: N@S attack could happens only in short-range, e.g. for within 20 blocks for 10% stake, so with 30 confirmations we haven't observed the successful attack. Also please note the attack has pretty unpredictable nature for attacker, so he can hardly enforce it, even in theory(in practice it's even harder to get it done properly). The correlation with stake size is still the open question, but it's nearly impossible to attack a proof-of-stake currency with "1% stake even" as stated by Buterin

- the N@S simulation tool is published also https://github.com/ConsensusResearch/MultiBranch  so feel free to make your own experiments



-----------------------------

Consensus Research is the micro-group of two researchers working on Proof-of-Stake consensus algorithm investigation at the moment. We're raising funds via NXT Assets Exchange ( https://trade.secureae.com/#5841059555983208287 ), have own GitHub https://github.com/ConsensusResearch/ and subforum on NXT forum: https://nxtforum.org/consensus-research/ , also check my personal blog please http://chepurnoy.org/



Ergo Platform. Part-time IOHK Research. Previously Nxt core dev / SmartContract.com cofounder.
1511550450
Hero Member
*
Offline Offline

Posts: 1511550450

View Profile Personal Message (Offline)

Ignore
1511550450
Reply with quote  #2

1511550450
Report to moderator
The Bitcoin network protocol was designed to be extremely flexible. It can be used to create timed transactions, escrow transactions, multi-signature transactions, etc. The current features of the client only hint at what will be possible in the future.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1511550450
Hero Member
*
Offline Offline

Posts: 1511550450

View Profile Personal Message (Offline)

Ignore
1511550450
Reply with quote  #2

1511550450
Report to moderator
Damelon
Legendary
*
Offline Offline

Activity: 1078



View Profile
December 18, 2014, 10:15:28 PM
 #2

Nice to see some research on N@S, instead of claims without backup.

Would be nice to see some discussion going over this. Smiley

Member of the Nxt Foundation | Donations: NXT-D6K7-MLY6-98FM-FLL5T
Join Nxt Slack! https://nxtchat.herokuapp.com/
Founder of Blockchain Workspace | Personal Site & Blog
jonald_fyookball
Legendary
*
Offline Offline

Activity: 1260


Core dev leaves me neg feedback #abuse #political


View Profile
December 19, 2014, 12:04:21 AM
 #3

I don't have the time/energy to fully digest what the paper
is saying, but the conclusions of the author seem to say that
Nothing at stake is a real problem that hasn't been solved.

Quote
As we have all the algorithms developed to simulate N@S attack we
present result in the separate paper along with possible ways to resist it.
Giving some results now we present not the full picture of the problem. Fol-
lowing this section it is reasonable to get the impression that this problem
actually matters
and we concentrate to possible solutions at the moment....


...The open question for the future work are: (1) the PoS consensus depen-
dence on the measure function (2) the ways to avoid N@S attack if any (3)
the optimal confirmation length investigation (4) the optimal multibranch
depth investigation.

Yurizhai
Hero Member
*****
Offline Offline

Activity: 686



View Profile
December 19, 2014, 12:16:09 AM
 #4

Jordan Lee has claimed to have solved nothing at stake in version 0.4.0 of the Nu network. Vitalik comments on it. Is that strategy mentioned in the paper?
https://discuss.nubits.com/t/proof-of-stake-and-weak-subjectivity/716/3

jonald_fyookball
Legendary
*
Offline Offline

Activity: 1260


Core dev leaves me neg feedback #abuse #political


View Profile
December 19, 2014, 12:23:25 AM
 #5

Jordan Lee has claimed to have solved nothing at stake in version 0.4.0 of the Nu network. Vitalik comments on it. Is that strategy mentioned in the paper?
https://discuss.nubits.com/t/proof-of-stake-and-weak-subjectivity/716/3



Vitalik's comment on Jordan Lee's 'solution':

Quote
What they've figured out is a way of discounting double-votes from scoring, not disincentivizing people from making them



Yurizhai
Hero Member
*****
Offline Offline

Activity: 686



View Profile
December 19, 2014, 12:25:48 AM
 #6

Jordan Lee has claimed to have solved nothing at stake in version 0.4.0 of the Nu network. Vitalik comments on it. Is that strategy mentioned in the paper?
https://discuss.nubits.com/t/proof-of-stake-and-weak-subjectivity/716/3



Vitalik's comment on Jordan Lee's 'solution':

Quote
What they've figured out is a way of discounting double-votes from scoring, not disincentivizing people from making them




And then goes on to say:
Quote
So, the system still relies on weak subjectivity, so it's basically just another security deposit-like mechanism that as far as I can see has exactly the same properties.
jl777
Legendary
*
Offline Offline

Activity: 1162


View Profile WWW
December 19, 2014, 12:56:41 AM
 #7

I don't have the time/energy to fully digest what the paper
is saying, but the conclusions of the author seem to say that
Nothing at stake is a real problem that hasn't been solved.

Quote
As we have all the algorithms developed to simulate N@S attack we
present result in the separate paper along with possible ways to resist it.
Giving some results now we present not the full picture of the problem. Fol-
lowing this section it is reasonable to get the impression that this problem
actually matters
and we concentrate to possible solutions at the moment....


...The open question for the future work are: (1) the PoS consensus depen-
dence on the measure function (2) the ways to avoid N@S attack if any (3)
the optimal confirmation length investigation (4) the optimal multibranch
depth investigation.
My understanding is that the more severe long range attack does not exist and even the short range attack is quite difficult to achieve. Also with more confirmations, the required attacking stake keeps going up. And if it requires actual stake to do a N@S attack, then there is definitely something at stake!

So by definition this paper is very close to proving that when properly done PoS cannot be attacked with nothing.

Of course if you throw enough resources to buy 51% (or probably 30%) of any PoS, you can do all sorts of nasty things to it. just like if you are able to control 51% (or is it 33% due to minority attacks) of mining power, you can do all sorts of nasty things to a PoW. Dont want to get into a discussion about how likely it is for anybody to obtain 51% of PoW mining power or 51% of a PoS currency, as the point of this thread is about Nothing at Stake attack.

OK, maybe just a little. Mining power costs are not coupled to the PoW coin, so you can simply buy arbitrary amounts of mining hardware with the limit only being the manufacturing capacity of the vendors. Certainly a mass buy will raise the cost of the mining hardware due to the increased demand, but surely not more than 2x and only until the manufacturers start making new production runs. [this is totally ignoring the logistics cost of some "special" team to infiltrate three mining operations, let us stay within the laws for this discussion]

Now let us imagine you are wanting to buy 51% of a PoS currency. What would happen to the price? What would the cost be? Maybe if you are patient, over time you can accumulate a large amount of anything, but any meaningful inflow of capital into a market will necessarily increase the price. will it be 2x or 20x or 200x by the time 51% is obtained? of course, depends on the coin, but the fact that there is a feedback loop to the cost for any financial attacker provides some level of protection.

If there is no attack without anything at stake, then it seems that something is at stake, which is the point of PoW right? to have a cost. Seems like you need to have a significant stake and fancy algos and computing resources to conduct a short range attack, which is thwarted by having more confirmations.

At the high level, it seems that both PoW and properly implemented PoS are able to require capital investment to obtain the coins. I am actually a PoW/PoS agnostic, I just want the coin to be secure and the small number of mining pools that control BTC mining output worry we far more than someone doing a N@S attack.

The days of just declaring PoS as impossible should be behind us. We now have academics with equations, so let the debate be resolved by logic and math, instead of rhetoric.

Clearly any crypto if improperly used will be vulnerable https://bitcointalk.org/index.php?topic=581411.0 and the first implementation of PPC PoS had a coinage vulnerability, but that does not mean that all PoS is flawed. Now what happens if 90% of BTC miners stopped? Like after a multipool abandons a coin after a diff adjustment, the blocktimes will slow down, a lot. This is not an attack scenario, but a real possibility if this bear market continues for another 6 months. With BTC diff readjustments 2000+ blocks, how long will things be in slow motion and if it slows to the point where all the blocks are full and it overflows, then what happens?

So, there are potential problems with all such things and the ideal algo has yet to be made. Ideally the best ideas from PoW can be combined with the best ideas of PoS.

James

http://www.digitalcatallaxy.com/report2015.html
100+ page annual report for SuperNET
jl777
Legendary
*
Offline Offline

Activity: 1162


View Profile WWW
December 19, 2014, 12:57:45 AM
 #8

Jordan Lee has claimed to have solved nothing at stake in version 0.4.0 of the Nu network. Vitalik comments on it. Is that strategy mentioned in the paper?
https://discuss.nubits.com/t/proof-of-stake-and-weak-subjectivity/716/3



Vitalik's comment on Jordan Lee's 'solution':

Quote
What they've figured out is a way of discounting double-votes from scoring, not disincentivizing people from making them




And then goes on to say:
Quote
So, the system still relies on weak subjectivity, so it's basically just another security deposit-like mechanism that as far as I can see has exactly the same properties.
Hopefully Vitalik can comment on the Consensus Research paper.

http://www.digitalcatallaxy.com/report2015.html
100+ page annual report for SuperNET
jonald_fyookball
Legendary
*
Offline Offline

Activity: 1260


Core dev leaves me neg feedback #abuse #political


View Profile
December 19, 2014, 01:30:14 AM
 #9

  And if it requires actual stake to do a N@S attack, then there is definitely something at stake!
 

You don't seem to understand what the Nothing at stake problem is about.

(Yes, obviously you need to own coins, but you could attack and then
sell your coins.)

Nothing at stake refers to the fact that the best strategy is
forging on multiple chains at the same time.

The conundrum is that PoS really seeks "free"
security.  Would be nice to have a secure
network that establishes distributed consensus
without security costs, but is it feasible?

One of the biggest arguments in favor of
proof of work is that it costs more to attack
the network than to participate in its security.


 

jonald_fyookball
Legendary
*
Offline Offline

Activity: 1260


Core dev leaves me neg feedback #abuse #political


View Profile
December 19, 2014, 01:36:42 AM
 #10


 
Quote
I don't have the time/energy to fully digest what the paper
is saying, but the conclusions of the author seem to say that
Nothing at stake is a real problem that hasn't been solved.

Maybe you ought to go ahead and fully digest what the paper is saying before proceeding.
 
Why would I do that when

A) I just stated I don't have time
B) I can quote the author's own conclusions

jl777
Legendary
*
Offline Offline

Activity: 1162


View Profile WWW
December 19, 2014, 01:47:41 AM
 #11

  And if it requires actual stake to do a N@S attack, then there is definitely something at stake!
 

You don't seem to understand what the Nothing at stake problem is about.

(Yes, obviously you need to own coins, but you could attack and then
sell your coins.)

Nothing at stake refers to the fact that the best strategy is
forging on multiple chains at the same time.

The conundrum is that PoS really seeks "free"
security.  Would be nice to have a secure
network that establishes distributed consensus
without security costs, but is it feasible?

One of the biggest arguments in favor of
proof of work is that it costs more to attack
the network than to participate in its security.


 

So you obtain a stake and then magically sell the coins after you attack it. Since it would take time to accumulate enough coins to attack it, then you are doing this simply to destroy the coin. But who would buy the coins back after it is attacked successfully? Ever try to sell even 10% of a coin supply all at once? Pretty much no market can withstand such things. What would a 1 million BTC sell order do to its price?

so if N@S requires an insane millionaire to conduct it, then this madman can easily buyout the top mining pools right?

to use a wild card against one approach but not the other is not quite an objective analysis.

Now if N@S now is requiring to obtain a meaningful stake before conducting the attack then it would be fair to say:

One of the biggest arguments in favor of
proof of stake is that it costs more to attack
the network than to participate in its security.

James

http://www.digitalcatallaxy.com/report2015.html
100+ page annual report for SuperNET
jonald_fyookball
Legendary
*
Offline Offline

Activity: 1260


Core dev leaves me neg feedback #abuse #political


View Profile
December 19, 2014, 01:51:43 AM
 #12

actually you can sell your coins first and then attack...
since the nature of an attack is a re-org on the blockchain,
how would anyone know you don't own the coins that
you owned several blocks ago?  That's another aspect
of N@S.


 

Sentinelrv
Sr. Member
****
Offline Offline

Activity: 455



View Profile
December 19, 2014, 02:00:26 AM
 #13

Jordan Lee has claimed to have solved nothing at stake in version 0.4.0 of the Nu network. Vitalik comments on it. Is that strategy mentioned in the paper?
https://discuss.nubits.com/t/proof-of-stake-and-weak-subjectivity/716/3

I just wanted to comment that Sigmike (who designed this solution along with Jordan Lee) is a core developer for both NuBits and Peercoin. Sunny King has reviewed it and approved this change in Peercoin and it will be supported in the next version when it releases, which will be v0.5.
ThomasVeil
Full Member
***
Offline Offline

Activity: 220


View Profile
December 19, 2014, 02:08:36 AM
 #14


 
Quote
I don't have the time/energy to fully digest what the paper
is saying, but the conclusions of the author seem to say that
Nothing at stake is a real problem that hasn't been solved.

Maybe you ought to go ahead and fully digest what the paper is saying before proceeding.
 
Why would I do that when

A) I just stated I don't have time
B) I can quote the author's own conclusions

He asked a logical question: If you don't have time to understand it - why do you have time to comment on it?
The conclusion actually states it in very simple terms: The problem exists, but is basically theoretical, because extremely hard to realize. Notice also that they are suggesting the "multibranch" approach - which makes the attack even more unlikely.

  And if it requires actual stake to do a N@S attack, then there is definitely something at stake!
 

You don't seem to understand what the Nothing at stake problem is about.

(Yes, obviously you need to own coins, but you could attack and then
sell your coins.)

Then there is something at stake. Really... why deny it when in the next sentence you affirm it?
You attack the coin that you own. The value will likely drop - with or without a final success.

Quote
One of the biggest arguments in favor of
proof of work is that it costs more to attack
the network than to participate in its security.

So where is the difference? Buying 25% of the POS coin would not be a high cost?
In fact to buy the 51% mining power of Bitcoin would be way cheaper than buying 25% of the currency. Probably by several orders of magnitude.
jl777
Legendary
*
Offline Offline

Activity: 1162


View Profile WWW
December 19, 2014, 02:29:06 AM
 #15

actually you can sell your coins first and then attack...
since the nature of an attack is a re-org on the blockchain,
how would anyone know you don't own the coins that
you owned several blocks ago?  That's another aspect
of N@S.


 
so in several blocks you spread out your orders to sell 15% of the currency. Well I am no rocket scientist, but I would think that still you would run into some liquidity issues. Actually it might create more of a panic. Imagine a 100,000 BTC sell order, then another, then another, then another, .... That would probably be more panic creating than a single million BTC sell order.

And by selling the coins, your entire attack is based on the false chain you cleverly made so you get one shot to make it pay off.

Next you might propose to buy the coins over 6 months, conduct the attack, sell the coins over 6 months and then use a time machine to go back 6 months. But you know about the clever algos that make it so after some amount of blocks, say one day's worth that it is set in stone? So this shrinks your sell the coins and attack timeframe to a day. Spreading out the million BTC orders over a day, hmmm, still seems to be causing market meltdown and all the capital spent to acquire the coins are gone and hence something is at stake.

I think maybe you are liking the EMP attack I came up with. This one requires simultaneously taking out all the nodes of a PoS network, then get your totally made up blockchain as the only one for all the nodes to connect to. I think this EMP attack would actually work, but I think it would work with any coin PoW or PoS. also some logistical problems with finding all the nodes, obtaining the EMP's, deploying them, etc. and also you need to just convince a few of the genesis keyholders to just give them their keys to you. Oh, after that there wont be anybody with a working computer though so who will know about your false chain?

So, if we are leaving the world of the practical and believable, anything is possible. I think it is better to have some scientist types analyse the math in the consensus paper and then make some improvements.

Dont you agree?

James

http://www.digitalcatallaxy.com/report2015.html
100+ page annual report for SuperNET
jl777
Legendary
*
Offline Offline

Activity: 1162


View Profile WWW
December 19, 2014, 02:30:35 AM
 #16

i love seeing the PoS fudsters being slaughtered lol seems only the most hard core fudsters are left to fight their dwindling corner.
There is nothing wrong with PoW and actually the latest NXT lets you even create a new PoW coin with a single API command. so everything has its pros and cons and logical analysis is the way to determine the best course to take

http://www.digitalcatallaxy.com/report2015.html
100+ page annual report for SuperNET
durerus
Sr. Member
****
Offline Offline

Activity: 318



View Profile WWW
December 19, 2014, 03:08:01 AM
 #17

Great paper! I think everybody is looking forward to the scientific debate now.
jonald_fyookball
Legendary
*
Offline Offline

Activity: 1260


Core dev leaves me neg feedback #abuse #political


View Profile
December 19, 2014, 03:52:44 AM
 #18


He asked a logical question: If you don't have time to understand it - why do you have time to comment on it?

The logical answer is:  I wanted to highlight the conclusions
of the paper, since people have linked to it, misquoted it,
and misrepresented it as some kind of "debunking".

I mentioned that I don't have time to study
it deeply because I don't.   Hey, at least
I skimmed the paper... Some people
aren't even reading the paper and throwing
around their worthless opinions.  

Quote
Quote
One of the biggest arguments in favor of
proof of work is that it costs more to attack
the network than to participate in its security.
So where is the difference? Buying 25% of the POS coin would not be a high cost?

Well, for one thing, you can buy coins and sell them, or spend them, either
before or after an attack with PoS.  Secondly, if you already have coins,
you can try to double spend with them.




jl777
Legendary
*
Offline Offline

Activity: 1162


View Profile WWW
December 19, 2014, 05:04:18 AM
 #19


He asked a logical question: If you don't have time to understand it - why do you have time to comment on it?

The logical answer is:  I wanted to highlight the conclusions
of the paper, since people have linked to it, misquoted it,
and misrepresented it as some kind of "debunking".

I mentioned that I don't have time to study
it deeply because I don't.   Hey, at least
I skimmed the paper... Some people
aren't even reading the paper and throwing
around their worthless opinions.  

Quote
Quote
One of the biggest arguments in favor of
proof of work is that it costs more to attack
the network than to participate in its security.
So where is the difference? Buying 25% of the POS coin would not be a high cost?

Well, for one thing, you can buy coins and sell them, or spend them, either
before or after an attack with PoS.  Secondly, if you already have coins,
you can try to double spend with them.




you come across as a reasonable sounding guy, maybe a bit too busy, but you are now repeating a claim that I thought I did not believe was true: https://bitcointalk.org/index.php?topic=897488.msg9884322#msg9884322

so this magical instant selling is to me nonviable, which means the N@S will cost you the amount to acquire the stake, so a lot at stake. Secondly, where is this "you can try to double spend with them" coming from? The whole debate is about how this double spending is not possible with enough blocks, rolling checkpoints, maybe even some sort of preventing of chain jumping.

If you just ignore all this and just make statements like just double spend them, it seems you are really short on time to make any coherent point. I was looking forward to some deep insight about this issue from you.

James

http://www.digitalcatallaxy.com/report2015.html
100+ page annual report for SuperNET
Damelon
Legendary
*
Offline Offline

Activity: 1078



View Profile
December 19, 2014, 05:43:19 AM
 #20

I don't have the time/energy to fully digest what the paper
is saying, but the conclusions of the author seem to say that
Nothing at stake is a real problem that hasn't been solved.

Quote
As we have all the algorithms developed to simulate N@S attack we
present result in the separate paper along with possible ways to resist it.
Giving some results now we present not the full picture of the problem. Fol-
lowing this section it is reasonable to get the impression that this problem
actually matters
and we concentrate to possible solutions at the moment....


...The open question for the future work are: (1) the PoS consensus depen-
dence on the measure function (2) the ways to avoid N@S attack if any (3)
the optimal confirmation length investigation (4) the optimal multibranch
depth investigation.

Actually, the td;dr version is:

- multibranch forging gives measurable possibility to earn more fees. I guess Nxt should not ignore it in long-term as the profitable activity will be implemented by somebody sooner or later

- there's no long-range attack against a blockchain V. Buterin described, only short-range. The short-range attack doesn't allow double-spending but gives multibranching forger possibility to earn more fees in singlebranch environment by producing few blocks in a row. However producing few blocks in a row could be an issue too (e.g. evil forger may postpones orders submissions etc) but not critical at the moment.

- not explicitly stated in the paper but easily derived, a long delay between blocks not only annoying but also a security problem as it's the moment for short-range attack could happens

- we have formally defined nothing-at-stake attack(again, using Buterin's informal definition) and made initial simulations. We haven't included their results in paper as they are seems to be too raw, but I can reveal them here: N@S attack could happens only in short-range, e.g. for within 20 blocks for 10% stake, so with 30 confirmations we haven't observed the successful attack. Also please note the attack has pretty unpredictable nature for attacker, so he can hardly enforce it, even in theory(in practice it's even harder to get it done properly). The correlation with stake size is still the open question, but it's nearly impossible to attack a proof-of-stake currency with "1% stake even" as stated by Buterin


So yes, there máy be problems with certain forms of N@S, and that needs to be researched. Research means keeping an open mind, not cherrypicking and taking out the last sentence and twisting it to mean what you want to mean.

They do nót say "Nothing at stake is a real problem that hasn't been solved." They say "We have made a simulation that produces a N@S as described and we are going to find out what it does."

Member of the Nxt Foundation | Donations: NXT-D6K7-MLY6-98FM-FLL5T
Join Nxt Slack! https://nxtchat.herokuapp.com/
Founder of Blockchain Workspace | Personal Site & Blog
Pages: [1] 2 3 4 5 6 7 8 9 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!