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 12206 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)

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 #20 on: December 18, 2014, 05:04:53 pm »

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

Knowledge of Wallmart account is enough to reject all fake chains.


EC is the kind of singlebranch enforcement, I guess like e.g. Slasher, but more reasonable for me. Further investigation here is needed though.

This is a tough task because pure math won't be enough. An expert in Economics would be handy.
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 #21 on: December 19, 2014, 07:24:52 am »

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

Knowledge of Wallmart account is enough to reject all fake chains.

You mean some big stakeholder and transaction generator (a "Wallmart') will try to follow the single branch as there's economic incentive? That could be true, but too many assumptions around.
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 #22 on: December 19, 2014, 07:51:06 am »

You mean some big stakeholder and transaction generator (a "Wallmart') will try to follow the single branch as there's economic incentive? That could be true, but too many assumptions around.

Agree, economic clustering may not work in a decentralized environment (this mentioned in one of the parts of BCNext's plan), these two things look contradicting each other. A lot of work for future researches.
Logged

valarmg

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

Buterin discussed the paper in this thread if either kushti or andruiman want to reply: http://www.reddit.com/r/Bitcoin/comments/2pvt1e/proof_of_work_proof_of_stake_and_the_consensus/

Logged
NXT-CSED-4PK5-AR4V-6UB5V

Fatih87SK

  • Hero Member
  • *****
  • Karma: +127/-36
  • Offline Offline
  • Posts: 2206
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #24 on: December 20, 2014, 08:02:14 pm »

Logged

benjyz

  • Hero Member
  • *****
  • Karma: +71/-4
  • Offline Offline
  • Posts: 508
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #25 on: December 21, 2014, 09:37:52 am »

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).

VB's LRA/N@S formulation is a different one. He defined it in the reddit thread yesterday as

Quote
Attacker goes to all of the participants in the genesis sale, and offers them $5 in exchange for their private keys. Note that every participant can take their funds and move them to a new account, so there is no security risk from participating.

This is nonsense (as I'm used to from VB). Why would anyone sell their private keys? How to even know who the investors where? I mean even if one has the genesis accounts what does one do with them? The stake today is not the stake at the beginning. So LRA in this formulation is no problem at all - and here my entropy argument applies. It is/should not be not possible to re-write history like that. Nxt also has a re-write limit active to prevent LRA.
Logged

jl777

  • Hero Member
  • *****
  • Karma: +718/-123
  • Offline Offline
  • Posts: 6170
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #26 on: December 21, 2014, 10:13:40 am »

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).

VB's LRA/N@S formulation is a different one. He defined it in the reddit thread yesterday as

Quote
Attacker goes to all of the participants in the genesis sale, and offers them $5 in exchange for their private keys. Note that every participant can take their funds and move them to a new account, so there is no security risk from participating.

This is nonsense (as I'm used to from VB). Why would anyone sell their private keys? How to even know who the investors where? I mean even if one has the genesis accounts what does one do with them? The stake today is not the stake at the beginning. So LRA in this formulation is no problem at all - and here my entropy argument applies. It is/should not be not possible to re-write history like that. Nxt also has a re-write limit active to prevent LRA.
combined with the EMP attack is the only way I can see this attack to work.

James

Logged
There are over 1000 people in SuperNET slack! http://slackinvite.supernet.org/ automatically sends you an invite

I am just a simple C programmer

Roiman

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

Great read, thanks...
The N@S does seem like the Byzantine Generals Problem (double spend)
without the PoW there is the problem of node selection to confirm blocks.
centralisation can fix (whats the point) or hallmakerked/prime/trusted nodes can be used 
but bad actors could manipulate the system.
selection of nodes seems to be the essential question to answer but many alternatives have flaws.
i like the idea of a timestamp on the blockchain with some data that cant be manipulated  like
lotto/sports results.
thought the fee with the PoT assisted  with avoiding  attacks?
Logged

HassenBlasques

  • Jr. Member
  • **
  • Karma: +37/-0
  • Offline Offline
  • Posts: 32
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #28 on: January 03, 2015, 09:19:01 am »

This is a tough task because pure math won't be enough. An expert in Economics would be handy.

Hello, I am an economist, teaching a course concerning cryptocurrencies at University of Economics in Prague. I would gladly try to help if you explain me deeper the economic task in it.
Logged
NXT: NXT-EVPU-KNB6-TAYK-8UUZR
UniversityProject: NXT-7AC4-Z4SS-UNXK-DX42X

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 #29 on: January 03, 2015, 09:52:43 am »

Hello, I am an economist, teaching a course concerning cryptocurrencies at University of Economics in Prague. I would gladly try to help if you explain me deeper the economic task in it.

As it's known, economy tends to cluster, this is why big cities like New York were formed. Protection against long-range attacks on Nxt is based on assumption that Nxt economy will form a single cluster and the legit chain can be chosen easily by analyzing ratio of transactions made by big players of the cluster.

The question: is the assumption correct or economy based on decentralized technologies doesn't cluster?
Logged

HassenBlasques

  • Jr. Member
  • **
  • Karma: +37/-0
  • Offline Offline
  • Posts: 32
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #30 on: January 04, 2015, 05:05:40 pm »

I read both the papers concerning Multibranch forging and PoS forging algorithms and I do not understand some points:

I don't get how multiple branches can carry the same information. Even if all the branches included the same transactions and malicious attacks were impossible, there still will be differences in the accounts that forged particular blocks and e.g. in the amounts of money on these accounts (because of the fees). What do I miss? A single public ledger (be it blockchain or "blocktree") must always carry single, common information, otherwise it's worthless.

"We showed that in comparison with single-branch strategy the multibranch one is more efficient in terms of the number of generated block (and therefore the fee rewarded)"
- Why should this be true? The fees are not dependent on the number of generated blocks but on the number of transactions that are included in the blocks. A transaction usually has a cause and that is more or less given and independent on the way blockchain (or "blocktree") works. Faster generation of blocks only potentially increases the velocity of money but I'm not confident that it would really make a difference.

If there shall be some big fish like Walmart, they will be much more interested in the stability of the cc as its payment gate than it should look for the fees that are rather irrelevant. If there should be a purpose for Nxt, it barely is making money in fee schemes. Once the net is important or even vital for a major economic player, the player acts in accordance with common interest of the net's users (for he does not want them-the customers-to leave). In case a multibranch system is more effective, a rational behavior would be for Walmart to forge that way instead of trying to earn as many fees as possible.

Decentralized system doesn't mean that it does not cluster. Clustering is natural because it is advantageous. Clusters are advantageous because they a) decrease costs for their members, b) utilize the positive externalities produced by the strong members. Decentralized systems cannot exclude the (market) power of certain agents. Decentralization means that no agents are given extra rights over the others. In other words, decentralized systems are more flexible and the trust is distributed to every single agent (node). Still a trust to Walmart would be incomparably higher and its "gravity" would probably attract a decisive majority of other agents.

Anyway, I can see no reason, why such a cluster would mean that there will be a single-branch. The "Walmart" could run multiple-branches itself, as I tried to point out above.
Logged
NXT: NXT-EVPU-KNB6-TAYK-8UUZR
UniversityProject: NXT-7AC4-Z4SS-UNXK-DX42X

andruiman

  • Jr. Member
  • **
  • Karma: +34/-1
  • Offline Offline
  • Posts: 37
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #31 on: January 07, 2015, 02:43:38 pm »

I don't get how multiple branches can carry the same information. Even if all the branches included the same transactions and malicious attacks were impossible, there still will be differences in the accounts that forged particular blocks and e.g. in the amounts of money on these accounts (because of the fees). What do I miss? A single public ledger (be it blockchain or "blocktree") must always carry single, common information, otherwise it's worthless.

We offer to distinguish the common data and common vision. Generally speaking it is not necessary for accounts to keep the same data to act equally (or equivalently). The main purpose of the blocktree structure is to implement what actually exists. The current Nxt protocol can deal with branches by rolling back blocks, we offer to do it in more natural way keeping the whole tree structure.  There is an inspiring analogue from physics - where are observable and unobservable values, e.g. quantum psi-function with unobservable argument for exp, or vector magnetic potential - all those example leads to very powerful calibration theory and are fundamental property of the nature (as we believe :). In economics this principle also can be applied as we know from the Quantum Finance studies. I spent some of my life to the intellectual property appraisal (math methods) and ready to conclude that the monetary value  of the objects is not observable unless we do a particular transaction, which we can treat as a quantum measurement. The great example could be also taken from the robotics where the pioneering works of S. Thrun gave the probabilistic approach to the self-localization problem as opposite to deterministic.

The same principles we are implementing here through the blocktree structure giving the possibility to maintain maybe different underlying data with the equivalent reasoning.   
Logged

andruiman

  • Jr. Member
  • **
  • Karma: +34/-1
  • Offline Offline
  • Posts: 37
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #32 on: January 07, 2015, 02:48:14 pm »

"We showed that in comparison with single-branch strategy the multibranch one is more efficient in terms of the number of generated block (and therefore the fee rewarded)"
- Why should this be true? The fees are not dependent on the number of generated blocks but on the number of transactions that are included in the blocks. A transaction usually has a cause and that is more or less given and independent on the way blockchain (or "blocktree") works. Faster generation of blocks only potentially increases the velocity of money but I'm not confident that it would really make a difference.

You are right. But that statement is given about the comparison with single-branch forging, i.e. multibranch account can effectively forge more blocks and get proportionally more fee than a single-branch within the same time interval and ceteris paribus.
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 #33 on: January 14, 2015, 04:00:27 pm »

Made a post summarizing known claimed attacks on proof-of-stake (BitcoinTalk) https://bitcointalk.org/index.php?topic=897488.msg10152632#msg10152632
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

Daedelus

  • Hero Member
  • *****
  • Karma: +230/-12
  • Offline Offline
  • Posts: 3280
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #34 on: April 15, 2015, 12:49:01 pm »

@Hassen

I'm not sure which answer you gave to CfB's question  ;D

Is a decentralized economy likely to cluster as the centralized economy is seen to do?

I thought you were saying decentralized economies were likely cluster but then your last line cast doubt in my mind.
Logged
NXT: NXT-4CS7-S4N5-PTH5-A8R2Q

Roiman

  • Jr. Member
  • **
  • Karma: +11/-0
  • Offline Offline
  • Posts: 79
    • View Profile
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #35 on: April 15, 2015, 01:16:27 pm »

I don't get how multiple branches can carry the same information. Even if all the branches included the same transactions and malicious attacks were impossible, there still will be differences in the accounts that forged particular blocks and e.g. in the amounts of money on these accounts (because of the fees). What do I miss? A single public ledger (be it blockchain or "blocktree") must always carry single, common information, otherwise it's worthless.

We offer to distinguish the common data and common vision. Generally speaking it is not necessary for accounts to keep the same data to act equally (or equivalently). The main purpose of the blocktree structure is to implement what actually exists. The current Nxt protocol can deal with branches by rolling back blocks, we offer to do it in more natural way keeping the whole tree structure.  There is an inspiring analogue from physics - where are observable and unobservable values, e.g. quantum psi-function with unobservable argument for exp, or vector magnetic potential - all those example leads to very powerful calibration theory and are fundamental property of the nature (as we believe :). In economics this principle also can be applied as we know from the Quantum Finance studies. I spent some of my life to the intellectual property appraisal (math methods) and ready to conclude that the monetary value  of the objects is not observable unless we do a particular transaction, which we can treat as a quantum measurement. The great example could be also taken from the robotics where the pioneering works of S. Thrun gave the probabilistic approach to the self-localization problem as opposite to deterministic.

The same principles we are implementing here through the blocktree structure giving the possibility to maintain maybe different underlying data with the equivalent reasoning.
never thought of it like that. like a wave of possibility or Schrodinger cat, its not measurable until its measured.
I agree which would encourage different branches.
also i would think clusters form naturally, in a decentralized world there are still cities, companies, organizations, on a roulette table there are clusters of red and black, colors on a bird its nature.
think this makes it easier to visualize decentralized
Logged

allwelder

  • Hero Member
  • *****
  • Karma: +196/-13
  • Offline Offline
  • Posts: 1867
  • NxtChina.org
    • View Profile
    • NxtChina.org
Re: The Paper on Long-Range attack & Nothing-at-Stake
« Reply #36 on: December 29, 2015, 07:07:02 am »

You mean some big stakeholder and transaction generator (a "Wallmart') will try to follow the single branch as there's economic incentive? That could be true, but too many assumptions around.

Agree, economic clustering may not work in a decentralized environment (this mentioned in one of the parts of BCNext's plan), these two things look contradicting each other. A lot of work for future researches.
This means Nxt will be like BTS with centralized super NODE?
Logged
NxtChina |Weibo |Twitter Donation welcomed:NXT-APL9-66GU-K8LY-B3JJJ
Pages: 1 2 [All]
 

elective-stereophonic
elective-stereophonic
assembly
assembly