Slides from my talk @ SF Bitcoin Devs Hackathon (titled "Proof-of-Stake and its Improvements") http://www.slideshare.net/AlexChepurnoy/proofofstake-its-improvements-san-francisco-bitcoin-devs-hackathon
Any good criticisms there?
Topic: Nothing-at-Stake & Long Range Attack on Proof-of-Stake (Consensus Research) - page 2. (Read 15441 times)
March 26, 2015, 02:56:59 AM
Any good criticisms there?
March 25, 2015, 08:45:01 PM
Slides from my talk @ SF Bitcoin Devs Hackathon (titled "Proof-of-Stake and its Improvements") http://www.slideshare.net/AlexChepurnoy/proofofstake-its-improvements-san-francisco-bitcoin-devs-hackathon
March 20, 2015, 06:36:51 PM
My comment on Poelstra's rewrite of PoS impossibility article https://www.reddit.com/r/Bitcoin/comments/2zpmlj/expanded_rewrite_of_distributed_consensus_from/cplj4ug
March 19, 2015, 02:34:10 AM
Quote
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
March 18, 2015, 04:06:10 PM
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!
Quote
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?
March 18, 2015, 03:00:25 PM
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!
March 09, 2015, 07:19:16 PM
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
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
February 25, 2015, 03:54:31 PM
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.
February 25, 2015, 07:28:46 AM
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.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?
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
February 25, 2015, 06:54:05 AM
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..
February 25, 2015, 06:40:08 AM
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.
February 25, 2015, 06:05:55 AM
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
and you seem genuinely interested so the following applies to Nxt POSLongest 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.
?
February 25, 2015, 12:43:52 AM
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. ...
and you seem genuinely interested so the following applies to Nxt POSLongest 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.
February 25, 2015, 12:32:13 AM
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. ...
and you seem genuinely interested so the following applies to Nxt POSLongest 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)
February 24, 2015, 09:34:19 PM
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. ...
and you seem genuinely interested so the following applies to Nxt POSLongest chain rule with highest difficulty applies in Nxt too. ...
Please explain to me difficulty in POS?
February 24, 2015, 06:27:30 PM
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
and you seem genuinely interested so the following applies to Nxt POSLongest 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
February 24, 2015, 12:33:02 PM
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..
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..
February 23, 2015, 07:39:47 PM
Hi Kushti
Do you plan to write these findings...
https://bitcointalksearch.org/topic/m.10152632
... up into a 4th paper?
Or shall I just add the link to the post to the 'Nxt Whitepaper' thread?
Do you plan to write these findings...
https://bitcointalksearch.org/topic/m.10152632
... 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.
February 23, 2015, 07:27:06 PM
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... February 23, 2015, 07:16:34 PM
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.
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.
Jump to: