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

[Daedelus]

Bump. Testcoin with modified forging algo is still in development. Kushti will have more time after release of version 1.5 of Nxt.

[1715285502]

1715285502

[Daedelus]

Bump. Testcoin with modified forging algo is still in development. Kushti will have more time after release of version 1.5 of Nxt.

is that for the challenge to break a nxt clone? if so, why modify the forging algo? would a straight clone not be the best candidate so as to acquire the most accurate results?

Two separate projects. CynicSOB still thinks he can break Nxt and is still trying AFAIK. Kushti is testing improvements that could be adopted by Nxt, all being well.

[Daedelus]

Further research published into Nothing at Stake- "tails switching":

We have updated our github repository https://github.com/ConsensusResearch/ForgingSimulation with a new version of the PoS simulation haskell code.
It now included two branches, master - for the single branch classical Nxt based code and "multibranch-experimental" - for the multibranch forging simulation. Recently
new algorithm for regulating tails switching effect is proposed and implemented. With it, a possibility of the N@S attack becomes also regulated as we now can introduce deducible  parameter of confirmations needed to stabilize recent blocks tails. The idea of regulating is straightforward - from time to time the node "forgets" almost all the branches and prolong only those whose cumulativeDifficulty measure is above some retargeting threshold. This threshold changes discretely, starting from 0. Unlike the Bitcoin difficulty param, the threshold always grows as the best block cumulativeDifficulty exceeds the previous threshold+delta. So nodes work as multibranch almost all the time, but sometimes becomes "single-branch" for a short time (one tick). This approach allows to have all the multibranch benefits and also get the network with regulating convergence. With a certain confirmation number  calculated, we can propose the strong resistance to the N@S as the long tails switching become very-very unlikely after the confirmations. We'll present the N@S simulation results ASAP.

There are more possible regulation procedures, for sure. Basing on the idea that sometimes nodes switch to the single-branch behavior one can introduce any verifiable quasi-random algorithm to do this. The proposed is the simple but efficient one, however more complicated algos (e.g. based on some nice hashes) could  secure the system more likely.

New paper on tails switching effect had been publicly released (https://github.com/ConsensusResearch/articles-papers/tree/master/switching). However the results of the simulations presented in the paper have been already renewed by the simulation software at https://github.com/ConsensusResearch/ForgingSimulation/tree/multibranch-experimental with the proposed threshold algorithm. As expected the algorithm allows to have confirmation number parameter deducible from the system constants and prevents the prolongation of similar branches. With it the resistance to the N@S becomes feasible and measurable! The results of N@S simulation + switching tails length distribution are coming.

[kushti]

Please keep in mind that kushti only used his own simulation model.
I'm very interested to see real world tries on the  Nxt testnet. I imagine that the attack is more complex there because network topology and latency, behaviour of peers,  etc.

The attack is more complex, right... for an attacker. Any non-determinism helps winning chain, that's pretty clear from our simulations(especially Nxt-like model https://github.com/ConsensusResearch/ForgingSimulation).

And for real-world-like testing, we're going to release own 100% Proof-of-Stake proto-CC https://nxtforum.org/general/kushti%27s-topic/msg157355/#msg157355 . We'll release attacking scripts as well, so everyone please join to try to crack proof-of-stake.

[Daedelus]

nxt fudding has pretty much stopped entirely since all these academic papers came out.. nice job..

All I have seen is trying to twist the definition of "Nothing at Stake" to try and keep it alive (Kushti's rationalisation in his summary was a list of "N@S definitions so far" rather than thoughtful proposals)  . Of these twists I've seen, none are POS specific and POW have it's own versions. GMaxwell warned Bill White off of using POS, so I pointed him to this research but he has made no comment as yet...

[kushti]

Hi Kushti 

Do you plan to write these findings...

https://bitcointalk.org/index.php?topic=897488.msg10152632#msg10152632

... up into a 4th paper?
Or shall I just add the link to the post to the 'Nxt Whitepaper' thread?

Last paper was about "tails switching". And now we're working on the several things simultaneously:
1. Better blockchain measure(than cumulative difficulty). Should lower number of confirmations needed to consider an attack impossible.
2. Proof-of-Stake + Proof-of-Activity hybrid simulation (paper on PoW + PoA http://eprint.iacr.org/2014/452.pdf)
3. Formal (yeah, truly formal) definition of some cryptocurrency properties. Probably next paper will be about that, as code is mostly ready here(definitions + lemmas/theorems with proofs made in Coq interactive theorem prover).
4. SCOREX to try research findings in almost-real world environment.

[spartacusrex]

Hi there,

Can I clear up a few questions floating around ? Not sure if there are answers or not.. So just thought I'd ask outright..

When connecting to a POS network, a bootstrap number must be collected from a trusted source ? Say a recent block hash from the current valid chain. (You may already have one, but I'm referring to either NEW users or users reconnecting after a non-negligent period of time)

Once you have connected to the Network, it seems that everything runs smoothly. That's great! 

Now, if you have connected to an INVALID / BOGUS POS network, when someone on the actual valid network connects to me and says 'Hey - THIS is the valid Network' there is no way for me to know which network is valid ? (Based on looking solely at the 2 POS chains in contention) I would need to ask someone I trust ? There may of course be 100's of competing chains, all saying ' I'm the valid chain! ' not just 2.

It seems that long range / short range attacks are a non-event ATM, but the current troubling aspect, for me at least, is the inability to rectify connecting to a bogus network at start up. If that is the case ?

What I mean is, in a POW network I can look at various chains, and see that one has more work than the other. Simple. Even if I do connect to the wrong network, I can always tell when I see the real thing. In POS I cannot ?

I do not see this as an ' IT'S BROKEN if this is the case ', but I do think this is a 'fundamental' issue that troubles many of us..

It would appear analogous to The Silk Road's Onion address changing every week, and having to re-find the valid address, or risk using an FBI honey pot trap. Yes obviously I can ask my friends what address they use, assuming they have used the site in the last week or so, but anyone who has tried to find that particular TOR address, knows that it is not 100% straight forward.. Does that make sense ?

be gentle.. 

[Daedelus]

You weren't frothing at the mouth in your post so there is no reason why anyone else should be   and you seem genuinely interested so the following applies to Nxt POS

Longest chain rule with highest difficulty applies in Nxt too. Nxt is pretty much the same as bitcoin if you imagine each Nxt as a mini mining rig. The current solution to joining the network after a break or initially is the yet to be implemented Economic Clustering feature. The idea being, to complete a transaction you both have to be on the same chain. So everyone joining would look to an entity (or two or ten) that makes a lot of activity I.e. a store, exchange etc. This is where the economy clusters around. Everyone has the incentive to be on the same chain, as otherwise their transactions are void so number of forks should tend towards 0. I believe Vitalik refers to this concept as Weak Subjectivity whrn he wrote about it in his blog.

In theory, if 51% the network nodes and passing around garbage chains then as long as people stick to the economic cluster (which I believe will be automated but don't quote me) then the attack will be resisted (a lot of garbage floating around though). I believe this is what led BCNext to believe Nxt was 90%+ resistant to attack. And the garbage chain would still have to have a higher block height and difficulty to stand a slim chance of a shred of success, which I think Kushti and Anduiman have shown is very very unlikely.

Kushti will correct me if I am wrong  

[Hueristic]

You weren't frothing at the mouth in your post so there is no reason why anyone else should be   and you seem genuinely interested so the following applies to Nxt POS

Longest chain rule with highest difficulty applies in Nxt too. ...

Please explain to me difficulty in POS?

[LiQio]

You weren't frothing at the mouth in your post so there is no reason why anyone else should be   and you seem genuinely interested so the following applies to Nxt POS

Longest chain rule with highest difficulty applies in Nxt too. ...

Please explain to me difficulty in POS?

TL;DR cumulative difficulty is higher the larger the total amount of stake that forged the chain


More information:
Formula see here: https://wiki.nxtcrypto.org/wiki/Whitepaper:Nxt#Cumulative_Difficulty

"A cumulative difficulty value is stored as a parameter in each block, and each subsequent block derives its new difficulty from the previous blocks value. In case of ambiguity, the network achieves consensus by selecting the block or chain fragment with the highest cumulative difficulty."

"In Nxt higher difficulty of a branch means that this particular branch was forged by owners of a larger amount of coins."
(Come-from-Beyond)

[Hueristic]

You weren't frothing at the mouth in your post so there is no reason why anyone else should be   and you seem genuinely interested so the following applies to Nxt POS

Longest chain rule with highest difficulty applies in Nxt too. ...

Please explain to me difficulty in POS?

TL;DR cumulative difficulty is higher the larger the total amount of stake that forged the chain


More information:
Formula see here: https://wiki.nxtcrypto.org/wiki/Whitepaper:Nxt#Cumulative_Difficulty

"A cumulative difficulty value is stored as a parameter in each block, and each subsequent block derives its new difficulty from the previous blocks value. In case of ambiguity, the network achieves consensus by selecting the block or chain fragment with the highest cumulative difficulty."

"In Nxt higher difficulty of a branch means that this particular branch was forged by owners of a larger amount of coins."
(Come-from-Beyond)

IC, Whichever chain has more coins is considered more difficult. Weird way of expressing that. I would think it would be refereed to as heavier. Thx for the explanation.

[spartacusrex]

You weren't frothing at the mouth in your post so there is no reason why anyone else should be   and you seem genuinely interested so the following applies to Nxt POS

Longest chain rule with highest difficulty applies in Nxt too. Nxt is pretty much the same as bitcoin if you imagine each Nxt as a mini mining rig. The current solution to joining the network after a break or initially is the yet to be implemented Economic Clustering feature. The idea being, to complete a transaction you both have to be on the same chain. So everyone joining would look to an entity (or two or ten) that makes a lot of activity I.e. a store, exchange etc. This is where the economy clusters around. Everyone has the incentive to be on the same chain, as otherwise their transactions are void so number of forks should tend towards 0. I believe Vitalik refers to this concept as Weak Subjectivity whrn he wrote about it in his blog.

In theory, if 51% the network nodes and passing around garbage chains then as long as people stick to the economic cluster (which I believe will be automated but don't quote me) then the attack will be resisted (a lot of garbage floating around though). I believe this is what led BCNext to believe Nxt was 90%+ resistant to attack. And the garbage chain would still have to have a higher block height and difficulty to stand a slim chance of a shred of success, which I think Kushti and Anduiman have shown is very very unlikely.

Kushti will correct me if I am wrong  

ok. The highest difficulty being the 'Chain with the most Stake involved' is nice for sorting out chain forks on the valid chain. But I don't think that helps with the 'bootstrap' scenario, as an attacker can fake as much stake as he wants on his 'fake' chain. 'Fake as much Stake'.. lol..

Also - the Economic Clustering, which as I understand it involves putting the hash of a previous block that must be on any chain this txn  is added to, does indeed help reach consensus on the valid chain. But again an attacker could fake as much or as little activity as he wanted on his fake chain. Thus in a bootstrap scenario, I'm not sure that helps either.

?

[achimsmile]

ok. The highest difficulty being the 'Chain with the most Stake involved' is nice for sorting out chain forks on the valid chain. But I don't think that helps with the 'bootstrap' scenario, as an attacker can fake as much stake as he wants on his 'fake' chain. 'Fake as much Stake'.. lol..

In crypto, a stakeholder has to prove that he has the private key to his stake when he wants to do a transaction. You can't insert a fake block where everyone sends their coins to you, because transactions need to be signed with private keys. The NRS would detect and ignore such a block.

But this is not what you want to do, you want newbies to see a complete fake chain.
Because each block contains information about the previous block, and you need to sign transactions with the private key of the account owner, you would need to alter history all the way back to the genesis block and create a new one where you have the private keys for creating a fake chain.

Since GENESIS_BLOCK_ID = 2680262203532249785L and all initial transactions from genesis account are hardcoded in Genesis.java, I don't see how the attacker could succeed. All he could do is create a Nxt clone.

[spartacusrex]

Since GENESIS_BLOCK_ID = 2680262203532249785L is hardcoded in Genesis.java, I don't see how the attacker could succeed. All he could do is create a Nxt clone.

Yes I see. Thanks.  In effect, the 'bootstrap number' I've been talking about, is now 'PART OF THE PROTOCOL'. 

Although - if the initial stake holders ever sold their private keys once those accounts were empty, or lost / hacked / QC cracked, then maybe you could cause a little heart ache..

[achimsmile]

Yes I see. Thanks.  In effect, the 'bootstrap number' I've been talking about, is now 'PART OF THE PROTOCOL'.

Welcome. Indeed, it's been part of it from the beginning.

Although - if the initial stake holders ever sold their private keys once those accounts were empty, or lost / hacked / QC cracked, then maybe you could cause a little heart ache..

This is not possible because of checkpoints in the client. A newbie with a clean NRS downloading the blockchain from scratch would still reject the fake blockchain.
Quote from nxtforum.org:

Kushti has proved (and no one has produced any counter evidence) that the long range attack (Kushti's definition: Long-range attack - attacker can start fork hundreds or thousands blocks behind current chain) isn't possible.

As you say, you put the checkpoint in after 720 blocks had passed so it was behind the decentralised rolling checkpoints.

So why put the second checkpoint in at all? 'Just in case', maybe similar to having two deadbolts on your door?

It is just in case indeed (and I have 4 locks on my door, not two). It is to prevent history rewriting attack where somebody buys no longer used early stakeholder accounts to build a complete alternative blockchain, regardless of what the theory says if such attack is possible or not.

A practical use of such checkpoint would be also if people provide for download a full copy of the blockchain, ending just before the checkpoint, then a node starting with such a copy and passing the checkpoint can be sure that blockchain is the same that other nodes running 1.4.8 or later use, up to the checkpoint at least. When downloading a compressed archive of the full database, a rescan is also needed if one wants to be sure that all tables containing account balances, assets and so on are populated correctly, but the checkpoint at least guarantees that the transactions up to it are the same.

it is refreshing to have such civil discussions here on btt for a change

[valarmg]

Since GENESIS_BLOCK_ID = 2680262203532249785L is hardcoded in Genesis.java, I don't see how the attacker could succeed. All he could do is create a Nxt clone.

Yes I see. Thanks.  In effect, the 'bootstrap number' I've been talking about, is now 'PART OF THE PROTOCOL'. 

Although - if the initial stake holders ever sold their private keys once those accounts were empty, or lost / hacked / QC cracked, then maybe you could cause a little heart ache..

True. But it would be a lot of work for an attacker to get these historical keys, create a new chain that seemed to have a greater cumulative difficulty, fake all the timestamps and rolling checkpoints, and then they'll only fool newcomers to the Nxt blockchain with no one to tell them which is the correct one.

By the time someone attempts such at attack, there may be other protections in place. I know that Consensus Research are looking into options.

[Daedelus]

CynicSOB still hasn't convinced any of his theory and has yet to put his attack into practice yet, one day soon hopefully!

I'm being cryptic about issue #2 because I don't want to reveal the fruits of my work without knowing if there is going to be a bounty and because I want to test if it applies against other coins.

But #1 should be easy to understand. Detailed instructions:
1) Gather 20% of staking weight and do not forge (yet)
2) at block height H send a tx to a victim on the main chain (to be included in block H+1)
3) fork to a private chain at block height H. A private chain is a chain that is the same as the main chain until block H but then stops listening to new blocks or new tx. It also stops publishing found blocks
4) create a new tx that would conflict with the one in step 2 and put it in your private chain.
5) forge your private chain with your 20% weight, ignoring other people's blocks. After your tx has 10 confirmations, and your victim accepted the tx you made in step 2, publish your chain. There is a 1 in 1000 chance that yours will have more cummulative difficulty. In that case, your fork is accepted and you have successfully double spent.
6) profit!

Of course, this should be optimized so you do step 2 only if you know that you'll succeed.

So, not multiple branch forging: only a private branch in parallel to the main chain. It's a short-range attack not directly related to what has been described as N@S.

Your chance to make successful attack is negligible even compared to 1/2^10 (~0.1%) chance. Here's why:
1. After "switching off' the network we can consider two networks then, one yours with 0.2*X forging stake and others with 0.8*X.
2. As last common block is generated by X stake, retargeting is needed for both networks.
3. But retargeting is limited, next target value could be within 0.5x...2x of previous
4. So others network will retarget smoothly and yours not, so your cumulative difficulty(which is sum(1/baseTarget) will be worse.

And I see no way to know that you'll succeed in prior.

Simulation of such attack could be done very quickly with our tool https://github.com/ConsensusResearch/ForgingSimulation, Haskell knowledge is needed though. I bet andruiman already did such things, but has to ask him, we started with such things in November so I've forgotten

[kushti]

Will have a talk about Proof-of-Stake and our work around it @ SF Bitcoin devs meetup on Sunday http://www.meetup.com/SF-Bitcoin-Devs/events/221241204/?fromEmail=221241204&rv=ea1 . Feel free to join and ask questions!

[Come-from-Beyond]

Will have a talk about Proof-of-Stake and our work around it @ SF Bitcoin devs meetup on Sunday http://www.meetup.com/SF-Bitcoin-Devs/events/221241204/?fromEmail=221241204&rv=ea1 . Feel free to join and ask questions!

An innovative approach for proof-of-stake consensus improvement will then be presented.

Are there any details already available or it will be a surprise?

[kushti]

An innovative approach for proof-of-stake consensus improvement will then be presented.

Are there any details already available or it will be a surprise?

Well, that will be about allowing multiple branches as described in our papers. It seems the Valley people are still discussing deposits / fines to "improve" Proof-of-Stake, so our ideas will be pretty innovative to them, I guess