Nxt Forum

Please login or register.

Login with username, password and session length
Advanced search  

News:

Latest Nxt Client 1.11.10 - NEW RELEASE: Ardor 2.0.6e TestNet - The Ignis ICO is over!! Ardor genesis snapshots will happen in the last week of December

Pages: [1] 2 3 ... 12  All

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

kushti

  • Core Dev
  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
  • Karma: +184/-5
Nxt Forging Algorithm: Simulating Approach
October 17, 2014, 07:16:02 pm

Unfortunately, after very good mthcl's paper "Math of Nxt forging" Nxt community didn't make significal progress in Proof-of-Stake research. So me and friend of mine andruiman (having writing phd in math) decided to make some research of Nxt forging algo aiming to improve it.

While I am working with code as developer andruiman is doing math behind. I started with converting forging part of NRS code into model and described it in "Inside a Proof-of-Stake Cryptocurrency" series pt. 1 & pt. 2. andruiman went deeper into math with the model  and we're happy to publish some results now:

https://www.scribd.com/doc/243341106/nxtforging-1

For those who won't or can't read academic-like papers, here are some results we got:

1. Even in theory average delay between blocks is ~1.9 min not 1
2. mthcl's proposal is better than original algorithm though its delays distribution allows small intervals more likely and sometimes allows large intervals
3. We have own pool-in-nodes proposal which distribution looks like much more gaussian and concentrated around the desirable average = 1 min
4. We're going to make our model complex for further investigations. We're going to investigate pool-in-nodes proposal as well and think about other possible ways to improve forging

We would be happy to receive feedback & contributions

P.S. andruiman's wallet is NXT-L892-ZKXZ-2JJY-AD9JV . He will post here soon
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

gs02xzz

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 1101
    • View Profile
  • Karma: +56/-12


+1. Thanks!
Nxt Mission is to commercialize the crypto technology and build new commerce and society.

bitcoinpaul

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 3093
  • Karmageddon
    • View Profile
  • Karma: +589/-588

very cool!
Like my Avatar? Reply now! NXT-M5JR-2L5Z-CFBP-8X7P3

LiQio

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 673
    • View Profile
    • NxtLoader for Windows
  • Karma: +50/-5

...
For those who won't or can't read academic-like papers, here are some results we got:
...

That would be me - appreciate your work (and the TL;DRs) big time  :)
NxtLoader for Windows | VPS 178.33.203.157 | NXT-7LUC-22LJ-5WJ4-22222

valarmg

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 1779
    • View Profile
  • Karma: +178/-57

Fantastic! Do you plan to integrate these improvements into the core? Avoiding those occasional super long gaps between blocks (which mcthl's adjustment claimed to do) would certainly be beneficial. Or is it still considered the case that there's no point making a change with Transparent Forging around the corner?
NXT-CSED-4PK5-AR4V-6UB5V

Sebastien256

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 2796
  • ^LOOK UP^ = Nxt community!
    • View Profile
  • Karma: +168/-24

is this possible to download without facebook? Thanks, keeep up the good work kushti
Please drop your ideas concerning Nxt and/or NRS in this topic -> List of feature request for Nxt and/or NRS (with the full list in OP).

valarmg

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 1779
    • View Profile
  • Karma: +178/-57

So pool-in-nodes method means that there are several subblocks found and the subblocks are combined to form one block. Interesting. What does that mean in terms of transactions-per-second? Does the fact that several nodes have to combine improve or disimprove the ability of the network to handle high loads?

Is this subblock method something that could be combined with transparent forging to improve it?
NXT-CSED-4PK5-AR4V-6UB5V

Come-from-Beyond

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 4014
    • View Profile
  • Karma: +793/-671

1. Even in theory average delay between blocks is ~1.9 min not 1

Heh, I already refuted this twice but this urban legend keeps popping up. Post assumptions the theory is based on and I'll point which ones shouldn't be applied for the real world scenario. :)

andruiman

  • Jr. Member
  • **
  • Offline Offline
  • Posts: 37
    • View Profile
  • Karma: +34/-1

Thank you guys!

It's pleasure for me to participate in so prospective community. Special thanks to kushti who invited me here.
I hope our work will be useful to realize some of the PoS crypto-currencies capabilities.

Definitely we have a lot of plans to implement based on a mix of formal approach + simulation + hi-level prototyping
which help us to reveal the interiors of the PoS networks. 

kushti

  • Core Dev
  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
  • Karma: +184/-5

Fantastic! Do you plan to integrate these improvements into the core? Avoiding those occasional super long gaps between blocks (which mcthl's adjustment claimed to do) would certainly be beneficial. Or is it still considered the case that there's no point making a change with Transparent Forging around the corner?

Transparent forging has nothing in commons with long gaps issue if it's just about next forger(s) to be known. Maybe some modifications in forging algo are also have been included in "Transparent Forging" plan, but I can't make any assumptions without knowing details.

Core improvement is our final goal for sure. A lot of work to be done though. So I think it's not about 1.4.0 but 1.5.0 in best case :)

is this possible to download without facebook? Thanks, keeep up the good work kushti

Try https://www.pdfhost.net/index.php?Action=Download&File=a334054b38bd358d38f8f439f552c453 (click on the little gray link)



Heh, I already refuted this twice but this urban legend keeps popping up. Post assumptions the theory is based on and I'll point which ones shouldn't be applied for the real world scenario. :)

Have you read the articles? Probably not. It's all there.
« Last Edit: October 17, 2014, 08:17:10 pm by kushti »
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

Come-from-Beyond

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 4014
    • View Profile
  • Karma: +793/-671

Have you read the articles? Probably not. It's all there.

No, of course, I don't use FB. I'll read it after pirated version become available and reply later.

Come-from-Beyond

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 4014
    • View Profile
  • Karma: +793/-671

Guys, could anyone upload the article to Mega, please?

kushti

  • Core Dev
  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
  • Karma: +184/-5

Have you read the articles? Probably not. It's all there.

No, of course, I don't use FB. I'll read it after pirated version become available and reply later.

1. Start with Inside Proof-of-stake series pt. 1 & pt. 2
2. pdfhost link again(it was in the message you replied to) https://www.pdfhost.net/index.php?Action=Download&File=a334054b38bd358d38f8f439f552c453
3. The paper is viewable without FB login, just scroll down  :)
« Last Edit: October 17, 2014, 08:45:57 pm by kushti »
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

youyou

  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 472
    • View Profile
  • Karma: +44/-46

Guys, could anyone upload the article to Mega, please?

cannot, not ready to make my coming out to my family, friends and Mark Zukerberg  :-\

andruiman

  • Jr. Member
  • **
  • Offline Offline
  • Posts: 37
    • View Profile
  • Karma: +34/-1

So pool-in-nodes method means that there are several subblocks found and the subblocks are combined to form one block. Interesting. What does that mean in terms of transactions-per-second? Does the fact that several nodes have to combine improve or disimprove the ability of the network to handle high loads?

Is this subblock method something that could be combined with transparent forging to improve it?

The concept of pool-in-nodes just reflects to the idea of "if several nodes do the block in some known time in average but with tails, why not to sum their efforts on smaller tasks and get the result with tails suppressed". How to load the subblocks without losing the consistence we investigate now.

Come-from-Beyond

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 4014
    • View Profile
  • Karma: +793/-671

1. Start with Inside Proof-of-stake series pt. 1 & pt. 2
2. pdfhost link again(it was in the message you replied to) https://www.pdfhost.net/index.php?Action=Download&File=a334054b38bd358d38f8f439f552c453
3. The paper is viewable without FB login, just scroll down  :)

"Unable to open the document". A direct answer on my question would save a lot of bytes...

kushti

  • Core Dev
  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
  • Karma: +184/-5

"Unable to open the document". A direct answer on my question would save a lot of bytes...

1. Again, the paper is viewable without FB login, just scroll down  :)
2. https://mega.co.nz/#!MJoRnByZ!9i6cZ89SvgtafIAVdlyuJEyqmNAPnvysxF6BCIKjePA
3. Ain't you drunk now? Seems you can read only one line of any message. If so better take rest :)
4. There's no so simple answer to your question for sure.
« Last Edit: October 17, 2014, 09:40:59 pm by kushti »
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

Come-from-Beyond

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 4014
    • View Profile
  • Karma: +793/-671

"Unable to open the document". A direct answer on my question would save a lot of bytes...

1. Again, the paper is viewable without FB login, just scroll down  :)
2. https://mega.co.nz/#!MJoRnByZ!9i6cZ89SvgtafIAVdlyuJEyqmNAPnvysxF6BCIKjePA
3. Ain't you drunk now? Seems you can read last line of every message only. If so better take rest :)
4. There's no so simple answer to your question for sure.

Previous link seems to be bugged, Mega worked perfectly as usually. I'm curious what makes people to use any other file hosting except Mega...

Come-from-Beyond

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 4014
    • View Profile
  • Karma: +793/-671

4. There's no so simple answer to your question for sure.

Aye, I can't find the assumptions. It's hard to see how correct a model is without knowing the assumptions it's based on.

Some notes:

1. Forging algo intentionally rewards non-split stake, it would be interesting to see pros and cons compared to absolutely fair algo.
2. Consequences of having a "transparent" forging are not taken into account, this means that analysis of a completely stochastic process is useless for the real world. Forgers can "look" into the future and skip/rearrange turns (use GetNextBlockGenerators API call to predict the future). Greedy forgers (not related to fees) make the algo to generate blocks with 60 sec interval.
3. Difficulty used to be manipulated by setting block timestamp to a later value making the gaussian bell symmetrical (at least rational forger would try to keep it symmetrical). This was used as a trap but removed later.

kushti

  • Core Dev
  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
  • Karma: +184/-5

As I'm completely incapable of understanding what is written here, I have a stupid question concerning 1)
Does 1min per block = 1.9min per block in reality means that if NXT would be set up to create a block every 31.57s, we'd get an average of 1 block per minute?

1 block per 1.9 minutes




Aye, I can't find the assumptions. It's hard to see how correct a model is without knowing the assumptions it's based on.

Some notes:

1. Forging algo intentionally rewards non-split stake, it would be interesting to see pros and cons compared to absolutely fair algo.
2. Consequences of having a "transparent" forging are not taken into account, this means that analysis of a completely stochastic process is useless for the real world. Forgers can "look" into the future and skip/rearrange turns (use GetNextBlockGenerators API call to predict the future). Greedy forgers (not related to fees) make the algo to generate blocks with 60 sec interval.
3. Difficulty used to be manipulated by setting block timestamp to a later value making the gaussian bell symmetrical (at least rational forger would try to keep it symmetrical). This was used as a trap but removed later.

1. Look at part 2 first(https://nxtforum.org/general/inside-a-proof-of-stake-cryptocurrency/). There you can find a prototyping code being used(some simplifications made but having no big effort I guess. You can compare prototyping code with NRS implementation). The paper is describing its assumptions clearly enough.
2. Seems our theory has good correspondence with practice as we don't see ~1 min average gap in "real world"
3. Can't get #2 at all.
    a) Do you have good description of "transparent forging" with implementation plan?
    b) How can user API call predicts network future? From investigating its source code that sounds like absurd.
    c) In distributed environment any predictions is subject to inconsistency. You cant' beat CAP theorem for forgers list
    d) How (inconsistent) knowledge about future could affects hit & target distribution?

4.  I'm going to make executable simulation of forging process. "Transparent forging" (and any rules about it) could be taken in account easily. Results will be soon and time will show average gap for "real world"  :)
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)
Pages: [1] 2 3 ... 12  All