elective-stereophonic
elective-stereophonic
Nxt Forging Algorithm: Simulating Approach  
Please login or register.

Login with username, password and session length
Advanced search  

News:

Latest Nxt Client: Nxt 1.11.15

Pages: 1 ... 10 11 [12]  All

Author Topic: Nxt Forging Algorithm: Simulating Approach  (Read 30660 times)

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: Nxt Forging Algorithm: Simulating Approach
« Reply #220 on: October 24, 2014, 02:41:06 pm »

It's like looking over God's shoulder.

Oh, thank you for the reminder, I was going to give you another bitcoinpaul!
Logged

Brangdon

  • Hero Member
  • *****
  • Karma: +229/-25
  • Offline Offline
  • Posts: 1389
  • Quality is addictive.
    • View Profile
Re: Nxt Forging Algorithm: Simulating Approach
« Reply #221 on: October 25, 2014, 11:58:52 am »

Patch is ready!
Cool. I notice your sample output includes predictions for NXT-4GSE-75S2-TVVP-3N2YV and NXT-R3V3-2S79-F3ZM-BVXKZ, which are both 5% accounts that never forge. If you kept track of which accounts failed to forge, the predictions could be more accurate further into the future.
Logged

Brangdon

  • Hero Member
  • *****
  • Karma: +229/-25
  • Offline Offline
  • Posts: 1389
  • Quality is addictive.
    • View Profile
Denial of Service attacks
« Reply #222 on: October 25, 2014, 12:25:55 pm »

I have been thinking about Denial of Service attacks. Someone with the ability to DoS 1% of nodes probably wouldn't have much effect if they picked those nodes at random, but the transparency of forging allows them to target the nodes that are most likely to forge next. This has been known since the beginning, but it might be interesting to model it quantitatively. I imagine it would delay block processing by some few seconds.

Those would be hostile attacks from outsiders. I am getting concerned about DoS attacks from the network on itself; that is, from greedy forgers.

Suppose Alice predicts that she will not forge any of the next 10 blocks, and that the next block will be forged by Bob. She also notices that if Bob fails to forge, then Charlie will forge it instead, and she is then predicted to forge one of the other 9 blocks. Alice has a financial incentive to DoS Bob and prevent him forging. If she tries and fails, it costs her no NXT. Slasher algorithms, that penalise accounts for failing to forge, will not deter her because they will punish Bob. The DoS attack happens off-chain, so network has no way of knowing who launched it. They might suspect Charlie, but it could be anyone who benefits more in the new chain. Alice has nothing to lose by trying.

Whoever forges next, there will always be someone else who benefits if they didn't, so someone will always have an incentive to DoS the next forger. If ever forgers become motivated by transaction fees rather than by network security, are we going to drown in Denial of Service attacks inflicted, not by outsiders, but by the community on itself?
Logged

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: Denial of Service attacks
« Reply #223 on: October 25, 2014, 01:12:56 pm »

I have been thinking about Denial of Service attacks. Someone with the ability to DoS 1% of nodes probably wouldn't have much effect if they picked those nodes at random, but the transparency of forging allows them to target the nodes that are most likely to forge next. This has been known since the beginning, but it might be interesting to model it quantitatively. I imagine it would delay block processing by some few seconds.

Those would be hostile attacks from outsiders. I am getting concerned about DoS attacks from the network on itself; that is, from greedy forgers.

Suppose Alice predicts that she will not forge any of the next 10 blocks, and that the next block will be forged by Bob. She also notices that if Bob fails to forge, then Charlie will forge it instead, and she is then predicted to forge one of the other 9 blocks. Alice has a financial incentive to DoS Bob and prevent him forging. If she tries and fails, it costs her no NXT. Slasher algorithms, that penalise accounts for failing to forge, will not deter her because they will punish Bob. The DoS attack happens off-chain, so network has no way of knowing who launched it. They might suspect Charlie, but it could be anyone who benefits more in the new chain. Alice has nothing to lose by trying.

Whoever forges next, there will always be someone else who benefits if they didn't, so someone will always have an incentive to DoS the next forger. If ever forgers become motivated by transaction fees rather than by network security, are we going to drown in Denial of Service attacks inflicted, not by outsiders, but by the community on itself?

A host accepting transactions not necessarily is the host that forges blocks. A successful DDoS will likely lead to empty blocks, not to their absence.
Logged

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Re: Nxt Forging Algorithm: Simulating Approach
« Reply #224 on: November 17, 2014, 04:14:25 pm »

Some comments about the andruiman&kushti's paper (took me looooong time, sorry!):


p.3: when you write τ3, it's a bit misleading (it's hard to figure out immediately that you meant footnote here).

pp.4-5: actually, for any positive non-degenerate random variable X it holds that 1/EX < E(1/X) (it's a consequence of the Jensen's inequality), I think it's worth mentioning here.

p.4: I think, the "right" way for obtaining the law of H is writing the balance equation and solving it analytically (if possible) or numerically. Anyhow, it would be interesting to compare that with your simulations.

p.5: didn't understand the point of calculating E(p1/p2). The result is around 32 log 2 ≈ 22.  What's the meaning of that? How is it related to the original model? At least, it is clear that the expected blocktime is not that big.

pp.6-7: first, km is some unclear random entity, and later it seems to become the total forging balance kind of without warning the reader.

p.7: by the way, the approach on top of this page resembles much the NEM forging algo, correct?

p.8: a general remark: IMHO, it is much more important to control the "shape" (i.e., tails etc.) of the distribution of H, than its expectation. The latter can be easily adjusted just by changing constants.

p.9: didn't understand the sentence "So if we naively put ... to be proportional ...". There is in fact inverse dependence between the account's balance and its time to next block.

p.9: I'm almost sure that the mean blocktime is currently around 1.9 just because the current BaseTarget adjustment algorithm is not well designed.

p.11: a TeX/notational advice: it's better to write e.g. p \sim U[0;1] when you talk about random variables and their distributions.

p.13: yes, in theory it would be nice to be able to take an average that way; my concern is that in practice it would lead to a forking hell if you try to decrease the time between the sub-blocks too much.


« Last Edit: November 17, 2014, 04:20:44 pm by mthcl »
Logged

andruiman

  • Jr. Member
  • **
  • Karma: +34/-1
  • Offline Offline
  • Posts: 37
    • View Profile
Re: Nxt Forging Algorithm: Simulating Approach
« Reply #225 on: November 17, 2014, 05:03:04 pm »


Some comments about the andruiman&kushti's paper (took me looooong time, sorry!):


p.3: when you write τ3, it's a bit misleading (it's hard to figure out immediately that you meant footnote here).

pp.4-5: actually, for any positive non-degenerate random variable X it holds that 1/EX < E(1/X) (it's a consequence of the Jensen's inequality), I think it's worth mentioning here.

p.4: I think, the "right" way for obtaining the law of H is writing the balance equation and solving it analytically (if possible) or numerically. Anyhow, it would be interesting to compare that with your simulations.

p.5: didn't understand the point of calculating E(p1/p2). The result is around 32 log 2 ≈ 22.  What's the meaning of that? How is it related to the original model? At least, it is clear that the expected blocktime is not that big.

pp.6-7: first, km is some unclear random entity, and later it seems to become the total forging balance kind of without warning the reader.

p.7: by the way, the approach on top of this page resembles much the NEM forging algo, correct?

p.8: a general remark: IMHO, it is much more important to control the "shape" (i.e., tails etc.) of the distribution of H, than its expectation. The latter can be easily adjusted just by changing constants.

p.9: didn't understand the sentence "So if we naively put ... to be proportional ...". There is in fact inverse dependence between the account's balance and its time to next block.

p.9: I'm almost sure that the mean blocktime is currently around 1.9 just because the current BaseTarget adjustment algorithm is not well designed.

p.11: a TeX/notational advice: it's better to write e.g. p \sim U[0;1] when you talk about random variables and their distributions.

p.13: yes, in theory it would be nice to be able to take an average that way; my concern is that in practice it would lead to a forking hell if you try to decrease the time between the sub-blocks too much.

Thank you very much. We will go through your comments and give an answer shortly:)
Logged

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: Nxt Forging Algorithm: Simulating Approach
« Reply #226 on: November 20, 2014, 10:26:54 am »

p.9: I'm almost sure that the mean blocktime is currently around 1.9 just because the current BaseTarget adjustment algorithm is not well designed.

Then a question arises:

- Why BCNext chose 720 blocks as a point of no return for blockchain reorg? Not 1440 (that logically follows from 1-min blocks).  :)


PS: It's not a rhetorical question, it would be really interesting to see a possible chain of reasoning that would lead to 720-block history rewriting limit if the person doesn't know that the mean blocktime is 2 min in case of "lazy" forgers.
Logged

abctc

  • Hero Member
  • *****
  • Karma: +148/-13
  • Offline Offline
  • Posts: 1396
    • View Profile
Re: Nxt Forging Algorithm: Simulating Approach
« Reply #227 on: November 20, 2014, 10:44:54 am »

- Why BCNext chose 720 blocks as a point of no return
- hmmm...  He chose a point of no return measured in blocks, not in minutes. So the time between blocks is irrelevant.
Logged
Welcome to the Nxt generation of crypto!   Magis quam Moneta (More than a Coin)
"Do not worry, it is an attack" (c) Jean-Luc

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: Nxt Forging Algorithm: Simulating Approach
« Reply #228 on: November 20, 2014, 10:51:49 am »

- hmmm...  He chose a point of no return measured in blocks, not in minutes. So the time between blocks is irrelevant.

But it still makes perfect sense that a transaction can't be reversed after 24 hours in the worst case scenario (720 blocks * 2 min). Current adjusting algo limits mean blocktime in [1 min ... 2 min] interval.
Logged

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Re: Nxt Forging Algorithm: Simulating Approach
« Reply #229 on: November 20, 2014, 01:20:29 pm »

p.9: I'm almost sure that the mean blocktime is currently around 1.9 just because the current BaseTarget adjustment algorithm is not well designed.

Then a question arises:

- Why BCNext chose 720 blocks as a point of no return for blockchain reorg? Not 1440 (that logically follows from 1-min blocks).  :)


PS: It's not a rhetorical question, it would be really interesting to see a possible chain of reasoning that would lead to 720-block history rewriting limit if the person doesn't know that the mean blocktime is 2 min in case of "lazy" forgers.
If someone here is still able to ask BCNext about something, then it is you  :)

But, seriously, 12 hours is just as reasonable as 24 hours.
Logged

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: Nxt Forging Algorithm: Simulating Approach
« Reply #230 on: November 20, 2014, 01:57:37 pm »

But, seriously, 12 hours is just as reasonable as 24 hours.

Ok  :D
Logged

Brangdon

  • Hero Member
  • *****
  • Karma: +229/-25
  • Offline Offline
  • Posts: 1389
  • Quality is addictive.
    • View Profile
Re: Nxt Forging Algorithm: Simulating Approach
« Reply #231 on: November 20, 2014, 09:00:04 pm »

But it still makes perfect sense that a transaction can't be reversed after 24 hours in the worst case scenario (720 blocks * 2 min). Current adjusting algo limits mean blocktime in [1 min ... 2 min] interval.
Is there a reason the time before a deposit counts for forging needs to be double the maximum re-org time? To me it seems more logical that the former be 24 hours than the latter.
Logged

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: Nxt Forging Algorithm: Simulating Approach
« Reply #232 on: November 21, 2014, 07:47:33 am »

Is there a reason the time before a deposit counts for forging needs to be double the maximum re-org time? To me it seems more logical that the former be 24 hours than the latter.

There are 2 types of people in Nxt - users and forgers.

When we talk to users we say that "a transaction can be cancelled and it's set in stone at most in 24 hours, don't accept transaction before that". 720 blocks give these 24 hours in the worst (for the user) case.

When we talk to forgers we say that "if you skip your turn to forge then you'll be penalized for at least 24 hours, don't stop forging". 1440 blocks give these 24 hours in the best (for the forger) case.

It's all just for convenience, we observe a similar thing in Bitcoin (2016 blocks == 2 weeks, Satoshi picked this number, not 2000 nor 2048). If the mean blocktime varied in [1min ... 5 min interval] then we would have max chain reorg equal to 288 blocks.
Logged

bitcoinpaul

  • Hero Member
  • *****
  • Karma: +590/-589
  • Offline Offline
  • Posts: 3097
  • Karmageddon
    • View Profile
Re: Nxt Forging Algorithm: Simulating Approach
« Reply #233 on: November 21, 2014, 08:07:51 am »

So CfB == BCNext. Shocker.

Now paul me.
Logged
Like my Avatar? Reply now! NXT-M5JR-2L5Z-CFBP-8X7P3

Daedelus

  • Hero Member
  • *****
  • Karma: +230/-12
  • Offline Offline
  • Posts: 3280
    • View Profile
Re: Nxt Forging Algorithm: Simulating Approach
« Reply #234 on: November 21, 2014, 08:25:04 am »

You're welcome.
Logged
NXT: NXT-4CS7-S4N5-PTH5-A8R2Q

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: Nxt Forging Algorithm: Simulating Approach
« Reply #235 on: November 21, 2014, 10:04:53 am »

So CfB == BCNext. Shocker.

Really? Hm... Well, you can call me "BCNext" if you wish but I prefer you call me "Master".
Logged

bitcoinpaul

  • Hero Member
  • *****
  • Karma: +590/-589
  • Offline Offline
  • Posts: 3097
  • Karmageddon
    • View Profile
Re: Nxt Forging Algorithm: Simulating Approach
« Reply #236 on: November 21, 2014, 10:14:24 am »

Yes, master.
Logged
Like my Avatar? Reply now! NXT-M5JR-2L5Z-CFBP-8X7P3

salsacz

  • Hero Member
  • *****
  • Karma: +239/-67
  • Offline Offline
  • Posts: 1762
  • NXT-R67P-6BZ2-XWAK-8RHZR
    • View Profile
Re: Nxt Forging Algorithm: Simulating Approach
« Reply #237 on: February 06, 2015, 07:16:20 pm »

would you edit the name of the paper - nxtforging-1 to "Nxt forging algorithm: simulating approach"? thanks :D
Logged
Holidays are (almost) over, check more news at: Nxt Academy
Pages: 1 ... 10 11 [12]  All
 

elective-stereophonic
elective-stereophonic
assembly
assembly