Topic: Nothing-at-Stake & Long Range Attack on Proof-of-Stake (Consensus Research) - page 6. (Read 15424 times)

please elaborate on the details of the bounty
writing a white-paper quality explanation is a time consuming task

I will elaborate on the idea against nxt.
But that link you sent regarding PPC is not about practical impossibility of N@S. It's only about practical impossiblity of the particular attack that the writer describes. This was proven by my attack on APEX. Also, it has some flaws:
is wrong, if you mine your chain in private and publish it only when it has accumulated more work than the main chain then you can attempt this after every block.
is also wrong: 1% gives you about 20% chance of a block. 5% guarantees success.

I wasn't able to connect to any peers.  You have any better luck?

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

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

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

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?

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.

I just performed this type of attack in APEXcoin. Please see here: https://bitcointalksearch.org/topic/cleanup-ill-attack-some-coins-i-owned-apexcoin-for-90-blocks-897493
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.

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

This solution is already implemented in BitShares, though called something different (TaPoS):
https://bitcointalksearch.org/topic/transactions-as-proof-of-stake-white-paper-354573

It isn't and never was:


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

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.

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

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.

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

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://bitcointalksearch.org/topic/m.10158797

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

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

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 !