Nothing-at-Stake & Long Range Attack on Proof-of-Stake (Consensus Research)

[kushti]

Couldnt we have reference NXT nodes that a new node queries to find the right chain?

Sounds too centralized. However, only initial part of history could be downloaded(e.g. first 100K or 200K blocks in case of Nxt), as its irreversible anyway. And that's  equivalent to checkpoints.

Btw, I think the importance of history attack is overestimated and its solved though in pretty rough way.

[Daedelus]

Congratulations Kushti on an apparently flawless paper 

[Daedelus]

This paper has been added to the thread Nxt Papers: Whitepapers, Academic and Economic at https://bitcointalk.org/index.php?topic=847868

[kushti]

To summarize the discussion, known claimed attacks on proof-of-stake distributed consensus algorithm(and concrete implementations) at the moment:

1. Short-range attack  - attacker can offer better chain started few blocks behind current canonical chain. The attack is possible at the moment, the only likely outcome though is just gathered fees increase for an attacker. In our simulations this kind of attack is possible mostly when a long delay occurs due to low target. By the way, the attack has positive aspect for network, as it shorten delays average between blocks. So attacker gets extra fees for a good job done  

2. Long-range attack - attacker can start fork hundreds or thousands blocks behind current chain. From our investigations the attack isn't possible.  

3. Nothing-at-stake attack - not possible at the moment! Will be possible when a lot of forgers will use multiple-branch forging  to increase profits. Then attacker can contribute to all the chains(some of them e.g. containing a transaction) then start to contribute to one chain only behind the best(containing no transaction) making it winner.  Previous statements on N@S attack made with assumption it costs nothing to contribute to an each fork possible and that makes N@S attack a disaster. In fact, it's not possible at all to contribute to each fork possible, as number of forks growing exponentially with time. So the only strategy for a multibranch forger is to contribute to N best forks. In such scenario attack is possible only within short-range e.g. with 25 confirmations needed 10% attacker can't make an attack. And attack is pretty random in nature, it's impossible to predict whether 2 forks will be within N best forks(from exponentially growing set) for k confirmations. So from our point of view the importance of the attack is pretty overblown.

4. History attack - attacker can buy whale's private key for $5 and build alternative story. Solved with some checkpoints now, located behind max rollback possible, so the solution is not so scary in terms of centralization etc.


If you know any other kind of attack, please add. Please note IPO properties of a concrete coins etc isn't related to proof-of-stake distributed consensus problems.

And Consensus Research is going to work on better proof-of-stake prototyping & implementation !

[Tobo]

How about the Sybil attack? I know that the Sybil attack may be not unique to PoS?

[r0ach]

4. History attack - attacker can buy whale's private key for $5 and build alternative story. Solved with some checkpoints now, located behind max rollback possible, so the solution is not so scary in terms of centralization etc.

HOW is that solved???  Centralized checkpoints = not decentralized currency. 

[ArticMine]

Stake does not equal exposure:

Consider for example a pirateat40 style "trust" on a POS coin. The "trust" has a very significant stake combined with a very significant short exposure, and consequently a vested interest in the collapse of the currency, and can vote the stake accordingly. https://en.bitcoin.it/wiki/Pirateat40. POS rewards the creators of ponzi schemes.
 
A variant of this is an exchange gone bad. Again the exchange operator controls a massive stake via customer deposits but no exposure, and if fraud occurs creating a fractional reserve. The exchange has a vested interest in the collapse of the currency in order to cover losses and can vote the stake accordingly.

Buying the currency while at the same time selling a greater amount on a derivatives market, creating a large stake with a short exposure and vested interest in the collapse of the currency. Again the stake can be voted accordingly.

Need I go on ...

Cross posted from https://bitcointalk.org/index.php?topic=924725.msg10158797#msg10158797

[r0ach]

4. History attack - attacker can buy whale's private key for $5 and build alternative story. Solved with some checkpoints now, located behind max rollback possible, so the solution is not so scary in terms of centralization etc.

HOW is that solved???  Centralized checkpoints = not decentralized currency. 

rolling checkpoints are not centralized

So where's the whitepaper on how you created decentralized checkpoints?

[Daedelus]

4. History attack - attacker can buy whale's private key for $5 and build alternative story. Solved with some checkpoints now, located behind max rollback possible, so the solution is not so scary in terms of centralization etc.

HOW is that solved???  Centralized checkpoints = not decentralized currency. 

rolling checkpoints are not centralized

So where's the whitepaper on how you created decentralized checkpoints?

The network won't accept reorgs deeper than 720 blocks so block 721 back from the current block is the rolling checkpoint. That's how it is done, though there isnt a whitepaper.

There is a general Nxt whitepaper, I can get the link if you haven't seen it.

[r0ach]

4. History attack - attacker can buy whale's private key for $5 and build alternative story. Solved with some checkpoints now, located behind max rollback possible, so the solution is not so scary in terms of centralization etc.

HOW is that solved???  Centralized checkpoints = not decentralized currency. 

rolling checkpoints are not centralized

So where's the whitepaper on how you created decentralized checkpoints?

The network won't accept reorgs deeper than 720 blocks so block 721 back from the current block is the rolling checkpoint. That's how it is done, though there isnt a whitepaper.

There is a general Nxt whitepaper, I can get the link if you haven't seen it.

Kind of hard to keep up with what exactly NXT is and whether it works or not:

As far as I know at least the first version of NXT's PoS is a direct clone of PPC's with some modifications, appeared lacking a good understanding of the security involved in PPC's PoS.

[go1111111]

So where's the whitepaper on how you created decentralized checkpoints?

The basic idea is what Vitalik talks about in his blog post on weak subjectivity: https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity/

It is decentralized in that if you've been away from the network for the past 720 (or whatever # of) blocks, when you come back online you have to ask someone or some set of people which chain is the real one. So if you know your best friend has been keeping a node online, you can ask him, or you can ask Vitalik, or you can ask Gavin Andressen, or you can ask some combination of any # of people you want -- the choice is up to you.

[achimsmile]

Kind of hard to keep up with what exactly NXT is and whether it works or not:

As far as I know at least the first version of NXT's PoS is a direct clone of PPC's with some modifications, appeared lacking a good understanding of the security involved in PPC's PoS.

It isn't and never was:

After thinking about the mining algorithm I came to conclusion that original proof-of-stake used by PPC and NVC is a bit flawed.  Bob could accumulate small amounts on different accounts during a long period of time and then attempt a 51% attack.  Artificial limits like max 90 days don't seem to work as intended.  Nxt will use a different proof-of-stake approach.

you would have to present a source code comparison between ppc and the first version of Nxt to make me think otherwise.

[alphaBar]

Regarding history attack, I will introduce in this topic another very interesting idea from NXT that is not yet implemented but could solve concerns with hidden history rebuilding, it's called Economic Clustering.

In Economic Clustering, basically, all transactions have to include a signed reference to an older block or transaction in the history, so if an attacker gets the keys of an account that used to have huge amounts of stake (those close to the genesis of the coin) and tries to reconstruct his/her own version of history in isolation it's impossible to rebuild it including the transactions of the rest of the economy and collect any of their fees, simply because the hashes of the new history will never match those included in the transactions previously broadcast.
If you already belong to the network and see the hidden branch being released your client can immediately spot the fake history as not including any transaction that you know about (from you or from a list of known companies/entities).

I see it as a social consensus: to fool the history you need to pro-actively involve a majority of the network signing the scam.

This solution is already implemented in BitShares, though called something different (TaPoS):
https://bitcointalk.org/index.php?topic=354573.0

[Daedelus]

So where's the whitepaper on how you created decentralized checkpoints?

The basic idea is what Vitalik talks about in his blog post on weak subjectivity: https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity/

It is decentralized in that if you've been away from the network for the past 720 (or whatever # of) blocks, when you come back online you have to ask someone or some set of people which chain is the real one. So if you know your best friend has been keeping a node online, you can ask him, or you can ask Vitalik, or you can ask Gavin Andressen, or you can ask some combination of any # of people you want -- the choice is up to you.

Come-from-Beyond described Economic Clustering in May when he committed it. Not sure it is quite the same idea as rolling checkpoints but it is in the same area.
https://nxtforum.org/news-and-announcements/economic-clustering/msg26267/#msg26267

Consensus research have also shown that the "Nothing-at-stake problem" (described in Vitalik's post) has been overstated. A lot. On the contrary, multibranch forging (aka mining on every chain you see) actually helps with security as you can't mine on every chain as they grow exponentially with time. You have to choose what you think are the best N chains and the results can't be predicted so the 'attack' is pretty useless.

I believe this also removes the need for Vitaliks security deposit as it makes it unnecessary as it protects against something that can't happen. It could even be damaging as it restricts the number of branches in multibranch forging so it is no longer exponentially growing in size but is finite, for practical purposes. Equal to the number of nodes in the network? Given they can only forge only 1 branch they see without being penalised. Have I understood correctly, Kushti?


All CfB's descriptions and Q&A on Economic Clustering are collated in this thread...

https://nxtforum.org/economic-clustering/cfb's-announcement-of-economic-clustering/ (you need an account to see the whitepaper section of the forum)



Here is the most recent whitepaper, though it may not have been updated with most recent features:

Nxt Whitepaper
https://www.dropbox.com/s/cbuwrorf672c0yy/NxtWhitepaper_v122_rev4.pdf

[cynicSOB]

To summarize the discussion, known claimed attacks on proof-of-stake distributed consensus algorithm(and concrete implementations) at the moment:

1. Short-range attack  - attacker can offer better chain started few blocks behind current canonical chain. The attack is possible at the moment, the only likely outcome though is just gathered fees increase for an attacker. In our simulations this kind of attack is possible mostly when a long delay occurs due to low target. By the way, the attack has positive aspect for network, as it shorten delays average between blocks. So attacker gets extra fees for a good job done  

I just performed this type of attack in APEXcoin. Please see here: https://bitcointalk.org/index.php?topic=897493.0
It was a short-range attack, but the consequences are not just more fees: I successfully double-spent.

You may want to expand this "Short-range attack" category, since there can be many different ways to achieve this.
I did it by splitting the coins and waiting for age to accumulate, and as I mention in the linked thread, I think it may be possible to do something similar in nxt.

Just like with POW, 51% guarrantees success but if you have 10% of the hashrate you will eventually have the chance to double spend. Same thing here: small stake + patience = double-spend. Only worse because in most POS coins the % of actively staked coins is low.

[cynicSOB]

you did it with a dead coin lol

its not impressive when you only do it to a dead coin. thats liek stabbing a dead deer and saying you hunted it. do it even with a nxt clone and then people will take notice.

I think it's more like stabbing a tied up deer to prove that stabs can be deadly, but let's skip the animal killing analogies please. Poor Bambi...

That's being discussed on the other thread. This doesn't directly apply to nxt becase it doesn't have coin age, but I think the attack can be adapted for it.

[EvilDave]

May I suggest NAS as the NXT clone target ?
https://bitcointalk.org/index.php?topic=523187.2060

Poor little things been dead in the water for a long time, so the code is pretty much out of date as far as current NXT code goes, but I reckon it'd be a good next step.
And I've got a couple of million NAS lying around somewhere I could lend ya........

Edit: Has there been any contact with or any sign of life from the Apexcoin devs/BlockNet crew?

[kushti]

I just performed this type of attack in APEXcoin. Please see here: https://bitcointalk.org/index.php?topic=897493.0
It was a short-range attack, but the consequences are not just more fees: I successfully double-spent.

You may want to expand this "Short-range attack" category, since there can be many different ways to achieve this.
I did it by splitting the coins and waiting for age to accumulate, and as I mention in the linked thread, I think it may be possible to do something similar in nxt.

Just like with POW, 51% guarrantees success but if you have 10% of the hashrate you will eventually have the chance to double spend. Same thing here: small stake + patience = double-spend. Only worse because in most POS coins the % of actively staked coins is low.

Could you describe attack scenario in details? After reproducing it in simulation we would like to pay you pretty good bounty

P.S. Good description on practical impossibility of N@S by JordanLee http://www.peercointalk.org/index.php?topic=2976.msg27303#msg27303

[cynicSOB]

May I suggest NAS as the NXT clone target ?
https://bitcointalk.org/index.php?topic=523187.2060

Poor little things been dead in the water for a long time, so the code is pretty much out of date as far as current NXT code goes, but I reckon it'd be a good next step.
And I've got a couple of million NAS lying around somewhere I could lend ya........

Edit: Has there been any contact with or any sign of life from the Apexcoin devs/BlockNet crew?

thanks, I'll look into it. No contact from Apex devs yet.

[EvilDave]

Hmmm....if I get some spare time I'll fire up a NAS node and see how the network looks.

I posted on the Apexcoin and BlockNet ANN threads, maybe we'll hear something from their devs about your attack.

Apexcoin ANN
BlockNet ANN