elective-stereophonic
elective-stereophonic
The Paper on Long-Range attack & Nothing-at-Stake
Please login or register.

Login with username, password and session length
Advanced search  

News:

Latest Nxt Client: Nxt 1.11.15

Pages: [1] 2  All

Author Topic: The Paper on Long-Range attack & Nothing-at-Stake  (Read 12207 times)

kushti

  • Board Moderator
  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
The Paper on Long-Range attack & Nothing-at-Stake
« on: December 18, 2014, 11:24:30 am »

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

- had 2-hours long conversation with andruiman yesterday. Probably we have elegant(not Slasher  ;D) solution to make consensus algorithmically enforced(like proof-of-work has) but a lot of experiments needed
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

neoranga

  • Jr. Member
  • **
  • Karma: +5/-0
  • Offline Offline
  • Posts: 34
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #1 on: December 18, 2014, 11:50:25 am »

Thanks for all the very worthy work, I go to read the final paper now but also thanks for the summary ;)
Logged

Mexxer

  • Hero Member
  • *****
  • Karma: +32/-20
  • Offline Offline
  • Posts: 653
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #2 on: December 18, 2014, 12:00:49 pm »

Awesome work! :)
Logged
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬  ▄▀▀▀▀▀▀▀▀▄  ▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬●  nimirum  ●▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬
▬▬▬ ◖ENDING CENSORSHIP ONLINE◗  ◖ ICO OPEN NOW◗ ▬▬▬

valarmg

  • Hero Member
  • *****
  • Karma: +178/-57
  • Offline Offline
  • Posts: 1766
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #3 on: December 18, 2014, 12:34:44 pm »

Exciting stuff, great to see such in-depth analysis of PoS. Would love to get input from such guys as Vitalik Buterin and Peter Todd and PoW specialists. Especially if you figure out the "solution to make consensus algorithmically enforced". Be good to get PoS specialists like Sunny King and Rat4 involved in the conversation too.

The paper is really well written and surprisingly understandable. (surprising because it so also very technical)

Did you address what Buterin calls weak subjectivity? The idea that if someone joins the network cold, they need to be told the branch to forge on. If someone got the keys to empty genesis accounts with a large % of forging power, could that person forge an alternative chain and fool those who enter the network cold?

You didn't mention checkpoints either, are they not important under this model?
« Last Edit: December 18, 2014, 01:12:28 pm by valarmg »
Logged
NXT-CSED-4PK5-AR4V-6UB5V

ThomasVeil

  • Hero Member
  • *****
  • Karma: +183/-11
  • Offline Offline
  • Posts: 1400
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #4 on: December 18, 2014, 12:48:44 pm »

Fantastic!
Consensus = Best Asset :D

Do I get the following right (since I want to add citations to the NXT wikipedia article)?
This is about transparent forging - which is called multibranch since it's a specific implementation. As such the paper defines N@S but the security results are mostly about transparent forging so don't apply to the current NXT blockchain.
You refer to the current chain as "Single-branch". And it is in fact more secure vs. N@S?
Logged
ARDOR-BPV3-837M-QZTQ-9DQ69  oxpal.com

coinomat

  • Hero Member
  • *****
  • Karma: +214/-18
  • Offline Offline
  • Posts: 1520
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #5 on: December 18, 2014, 01:04:32 pm »

Great! I have a feeling that all nothing-at-stake stuff has as much validity as hash collisions and such, that is theoretically possible but in reality highly (maybe even in mathematical sense) improbable.
Logged
Time to go further

andruiman

  • Jr. Member
  • **
  • Karma: +34/-1
  • Offline Offline
  • Posts: 37
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #6 on: December 18, 2014, 01:08:47 pm »

Fantastic!
Consensus = Best Asset :D

Do I get the following right (since I want to add citations to the NXT wikipedia article)?
This is about transparent forging - which is called multibranch since it's a specific implementation. As such the paper defines N@S but the security results are mostly about transparent forging so don't apply to the current NXT blockchain.
You refer to the current chain as "Single-branch". And it is in fact more secure vs. N@S?

Thank you! Actually the current implementation of Nxt is single-branch however the principle of the network allows to be the multibranch, so it is not hardcoded to be singlebranch for a arbitrary participant. So the security of the Nxt is the same as for its multibranch implementation, even more - from our current vision the security of total multibranch network is higher than for its singlebranch approximation. N@S can be more easily executed for the system with low level of branching (cause it's cheaper) than for the system with high level of  branching.

As for TF - multibranching is definitely a kind of implementation, but we see there additional important properties which allow to stabilize the block rate and effectively resist to a number of attacks. 
Logged

Fatih87SK

  • Hero Member
  • *****
  • Karma: +127/-36
  • Offline Offline
  • Posts: 2206
    • View Profile
Logged

andruiman

  • Jr. Member
  • **
  • Karma: +34/-1
  • Offline Offline
  • Posts: 37
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #8 on: December 18, 2014, 01:29:01 pm »

Exciting stuff, great to see such in-depth analysis of PoS. Would love to get input from such guys as Vitalik Buterin and Peter Todd and PoW specialists. Especially if you figure out the "solution to make consensus algorithmically enforced". Be good to get PoS specialists like Sunny King and Rat4 involved in the conversation too.

The paper is really well written and surprisingly understandable. (surprising because it so also very technical)

Did you address what Buterin calls weak subjectivity? The idea that if someone joins the network cold, they need to be told the branch to forge on. If someone got the keys to empty genesis accounts with a large % of forging power, could that person forge an alternative chain and fool those who enter the network cold?

You didn't mention checkpoints either, are they not important under this model?

Thank you! If I understand you correctly that is the same we called "Hidden multibranch" attack, so we think that it is practically impossible to build a chain better than the rest of the network. The key things are the measure function and baseTarget validation procedure. So alone forger should have very significant stake (around 25%+) to produce a better chain. However a short range attacks are still possible due to the block delays in the "best" chain if the rest of the network remains singlebranch and the attacker does multibranching. The easiest opposition is to be multibranch for the network itself.

We do not use checkpoints in the model as we hope the solution could be achieved using the correct block measure function. I suggest however that in practice they could be used to stabilize the branching for hard cases.
Logged

valarmg

  • Hero Member
  • *****
  • Karma: +178/-57
  • Offline Offline
  • Posts: 1766
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #9 on: December 18, 2014, 01:48:55 pm »


Thank you! If I understand you correctly that is the same we called "Hidden multibranch" attack, so we think that it is practically impossible to build a chain better than the rest of the network. The key things are the measure function and baseTarget validation procedure. So alone forger should have very significant stake (around 25%+) to produce a better chain. However a short range attacks are still possible due to the block delays in the "best" chain if the rest of the network remains singlebranch and the attacker does multibranching. The easiest opposition is to be multibranch for the network itself.

We do not use checkpoints in the model as we hope the solution could be achieved using the correct block measure function. I suggest however that in practice they could be used to stabilize the branching for hard cases.

Ok, so someone can't just throw a load of computing power with a relatively small stack and generate a viable branch. (Good, sick of hearing bitcoiners tell me that's easy.)

I'm thinking specifically of an attack whereby an attacker tracks down a number of the people who were part of the initial genesis block of Nxt. They manage to buy the addresses used, now empty of current Nxt and worthless to the owners, and manage to hold the addresses of a large amount of historical Nxt. (Say 70%+). They start forging a new chain using this 70%, fastforwording through blocks, faking checkpoints and maybe faking transaction volume until this new chain catches up with real chain. Now, to someone already on the main chain, they aren't going to mistake this new chain for the real chain. But when someone joins the network for the first time, could they be fooled into thinking that the new chain is the real one?






« Last Edit: December 18, 2014, 02:14:12 pm by valarmg »
Logged
NXT-CSED-4PK5-AR4V-6UB5V

Damelon

  • Administrator
  • Hero Member
  • *****
  • Karma: +792/-54
  • Offline Offline
  • Posts: 2314
    • View Profile
    • Nxt Inside
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #10 on: December 18, 2014, 02:08:26 pm »

Have you put this on /r/cryptocurrency yet?
Would be good to at least have it there as reference material :)
Logged
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

andruiman

  • Jr. Member
  • **
  • Karma: +34/-1
  • Offline Offline
  • Posts: 37
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #11 on: December 18, 2014, 02:21:45 pm »

I'm thinking specifically of an attack whereby an attacker tracks down a number of the people who were part of the initial genesis block of Nxt. They manage to buy the addresses used, now empty of current Nxt and worthless to the owners, and manage to hold the addresses of a large amount of historical Nxt. (Say 70%+). They start forging a new chain using this 70%, fastwording through blocks, faking checkpoints and maybe faking transaction volume until this new chain catches up with real chain. Now, to someone already on the main chain, they aren't going to mistake this new chain for the real chain. But when someone joins the network for the first time, could they be fooled into thinking that the new chain is the real one?

Yes, I think that in the pure abstract system (without some magic hardcoded, nodes ratings etc) it could be possible to find a better chain doing multibranching with 70% of stake (or even less) than ~100% singlebranching. However IMO it is quite easy to resist it by the concrete design.
Logged

neoranga

  • Jr. Member
  • **
  • Karma: +5/-0
  • Offline Offline
  • Posts: 34
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #12 on: December 18, 2014, 02:27:34 pm »


Thank you! If I understand you correctly that is the same we called "Hidden multibranch" attack, so we think that it is practically impossible to build a chain better than the rest of the network. The key things are the measure function and baseTarget validation procedure. So alone forger should have very significant stake (around 25%+) to produce a better chain. However a short range attacks are still possible due to the block delays in the "best" chain if the rest of the network remains singlebranch and the attacker does multibranching. The easiest opposition is to be multibranch for the network itself.

We do not use checkpoints in the model as we hope the solution could be achieved using the correct block measure function. I suggest however that in practice they could be used to stabilize the branching for hard cases.

Ok, so someone can't just throw a load of computing power with a relatively small stack and generate a viable branch. (Good, sick of hearing bitcoiners tell me that's easy.)

I'm thinking specifically of an attack whereby an attacker tracks down a number of the people who were part of the initial genesis block of Nxt. They manage to buy the addresses used, now empty of current Nxt and worthless to the owners, and manage to hold the addresses of a large amount of historical Nxt. (Say 70%+). They start forging a new chain using this 70%, fastforwording through blocks, faking checkpoints and maybe faking transaction volume until this new chain catches up with real chain. Now, to someone already on the main chain, they aren't going to mistake this new chain for the real chain. But when someone joins the network for the first time, could they be fooled into thinking that the new chain is the real one?

I understood this problem is mostly fixed with the Economic Clustering: each transaction has a signed reference to a previous transaction/block in the chain history so it can't be reused when rebuilding a hidden branch from scratch because referenced hashes will never match. If a new node starts and sees this rebuilt fake branch none of the recent transactions will match any other node.
At least this is how I imagined it will work.
Logged

benjyz

  • Hero Member
  • *****
  • Karma: +71/-4
  • Offline Offline
  • Posts: 508
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #13 on: December 18, 2014, 02:29:04 pm »

Comment on the long-range attack analysis

A (long-range) attack would mean something out of the ordinary occurs. If one imagines just the table of all balances of accounts and how it progresses overtime, entropy of the changes are usually very low (after genesis and weeks thereafter). A drafting of another chain
would mean that entropy is extremely high, basically re-writing the whole table. I think such chains could be easily detected by including
such a measure. Any alternative chain with such high entropy change should be rejected in principle, and therefore long-range attacks could be excluded, almost by default. In a way such a counter-measure would be like check- pointing, but organic without a decision to be made. This is, as I understand, the idea behind Economic Clustering, in a different variant.

I can make a more fully proposal with code examples in the coming weeks.
Logged

benjyz

  • Hero Member
  • *****
  • Karma: +71/-4
  • Offline Offline
  • Posts: 508
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #14 on: December 18, 2014, 02:34:37 pm »

I understood this problem is mostly fixed with the Economic Clustering: each transaction has a signed reference to a previous transaction/block in the chain history so it can't be reused when rebuilding a hidden branch from scratch because referenced hashes will never match. If a new node starts and sees this rebuilt fake branch none of the recent transactions will match any other node.
At least this is how I imagined it will work.

Yes, that is my understanding as well. As explained in the post above, I think long-range attack is impossible because entropy change would be too high. It is a sane default for a blockchain system to impose some rules whether to chain "re-writes". However such rules should be algorithmic. I'd add that in reality there is no such thing as "hidden" chain. There is longest chain which has to be accepted by default through the algorithm. Crafting of a chain is not really possible (nobody can make up balances just like that). So the N@S descriptions have been in wrong with regards to these problems, IMO. Results of this paper are roughly the similar I think.
Logged

andruiman

  • Jr. Member
  • **
  • Karma: +34/-1
  • Offline Offline
  • Posts: 37
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #15 on: December 18, 2014, 03:06:50 pm »

Yes, that is my understanding as well. As explained in the post above, I think long-range attack is impossible because entropy change would be too high. It is a sane default for a blockchain system to impose some rules whether to chain "re-writes". However such rules should be algorithmic. I'd add that in reality there is no such thing as "hidden" chain. There is longest chain which has to be accepted by default through the algorithm. Crafting of a chain is not really possible (nobody can make up balances just like that). So the N@S descriptions have been in wrong with regards to these problems, IMO. Results of this paper are roughly the similar I think.
Maybe I do not get the message fully, so sorry in this case.

From the current vision I do not see any connection between long range attack and N@S in the formulations given in the paper. We define the long range attack as a possibility to produce a better chain alone by some account (well, it can contain the same transactions and other stuff, so the balance entropy approach  can pass it). The result, attacker can potentially get, is e.g. about the rewarded fee or slight manipulation of transactions - not critical. However from our investigation the long range attack is quite difficult to execute.

The N@S attack in our formulation is about double spending - nothing hidden at all. The concurrent chains are almost the same and I do not see any statistical measures to distinguish between them. The only difference between them is two transactions included separately.  The solution could lie in algorithmically defined and community accepted blockchain measure function which allows not to jump from the confirmed(!) chain to another.  Unlikely it can be based on the statistical properties.
« Last Edit: December 18, 2014, 03:09:05 pm by andruiman »
Logged

kushti

  • Board Moderator
  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #16 on: December 18, 2014, 03:12:31 pm »

Ok, so someone can't just throw a load of computing power with a relatively small stack and generate a viable branch. (Good, sick of hearing bitcoiners tell me that's easy.)

I'm thinking specifically of an attack whereby an attacker tracks down a number of the people who were part of the initial genesis block of Nxt. They manage to buy the addresses used, now empty of current Nxt and worthless to the owners, and manage to hold the addresses of a large amount of historical Nxt. (Say 70%+). They start forging a new chain using this 70%, fastforwording through blocks, faking checkpoints and maybe faking transaction volume until this new chain catches up with real chain. Now, to someone already on the main chain, they aren't going to mistake this new chain for the real chain. But when someone joins the network for the first time, could they be fooled into thinking that the new chain is the real one?

Yeah, such an attack is possible at the moment and will lead to network partitioning. For now the problem could be solved with checkpoints, but proposals we've discussed yesterday will solve this problem in an elegant way as well. It's too early to reveal the details though.
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #17 on: December 18, 2014, 03:17:34 pm »

So the security of the Nxt is the same as for its multibranch implementation, even more - from our current vision the security of total multibranch network is higher than for its singlebranch approximation. N@S can be more easily executed for the system with low level of branching (cause it's cheaper) than for the system with high level of  branching.

Finally. I was always saying to N@S scaremongers that ability to forge multiple chains is an advantage, not a disadvantage. Now I can point them to a proof.
Logged

valarmg

  • Hero Member
  • *****
  • Karma: +178/-57
  • Offline Offline
  • Posts: 1766
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #18 on: December 18, 2014, 03:49:07 pm »


I understood this problem is mostly fixed with the Economic Clustering: each transaction has a signed reference to a previous transaction/block in the chain history so it can't be reused when rebuilding a hidden branch from scratch because referenced hashes will never match. If a new node starts and sees this rebuilt fake branch none of the recent transactions will match any other node.
At least this is how I imagined it will work.

Economic Clustering is an idea that may fix the problem I mentioned, but it hasn't been fully explored or implemented. Looks like it may not be needed now.

Quote
Yeah, such an attack is possible at the moment and will lead to network partitioning. For now the problem could be solved with checkpoints, but proposals we've discussed yesterday will solve this problem in an elegant way as well. It's too early to reveal the details though.
Logged
NXT-CSED-4PK5-AR4V-6UB5V

kushti

  • Board Moderator
  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #19 on: December 18, 2014, 04:52:57 pm »


I understood this problem is mostly fixed with the Economic Clustering: each transaction has a signed reference to a previous transaction/block in the chain history so it can't be reused when rebuilding a hidden branch from scratch because referenced hashes will never match. If a new node starts and sees this rebuilt fake branch none of the recent transactions will match any other node.
At least this is how I imagined it will work.

Economic Clustering is an idea that may fix the problem I mentioned, but it hasn't been fully explored or implemented. Looks like it may not be needed now.

How could that helps? A new node will download a valid fake chain with valid fake transactions with properly filled EC fields.

EC is the kind of singlebranch enforcement, I guess like e.g. Slasher, but more reasonable for me. Further investigation here is needed though.
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)
Pages: [1] 2  All
 

elective-stereophonic
elective-stereophonic
assembly
assembly