Topic: Nxt Forging Algorithm: Simulating Approach (Read 21334 times)

kushti · 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

gs02xzz · October 17, 2014, 07:30:09 pm

+1. Thanks!

bitcoinpaul · October 17, 2014, 07:32:45 pm

very cool!

LiQio · October 17, 2014, 07:42:31 pm

Quote from: kushti on October 17, 2014, 07:16:02 pm

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

valarmg · October 17, 2014, 07:44:21 pm

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?

Sebastien256 · October 17, 2014, 07:52:05 pm

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

valarmg · October 17, 2014, 07:56:36 pm

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?

Come-from-Beyond · October 17, 2014, 07:56:47 pm

Quote from: kushti on October 17, 2014, 07:16:02 pm

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 · October 17, 2014, 08:06:57 pm

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 · October 17, 2014, 08:14:16 pm

Quote from: valarmg on October 17, 2014, 07:44:21 pm

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

Quote from: Sebastien256 on October 17, 2014, 07:52:05 pm

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)

Quote from: Come-from-Beyond on October 17, 2014, 07:56:47 pm

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.

Come-from-Beyond · October 17, 2014, 08:19:19 pm

Quote from: kushti on October 17, 2014, 08:14:16 pm

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 · October 17, 2014, 08:20:35 pm

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

kushti · October 17, 2014, 08:25:36 pm

Quote from: Come-from-Beyond on October 17, 2014, 08:19:19 pm

Quote from: kushti on October 17, 2014, 08:14:16 pm
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

youyou · October 17, 2014, 08:28:34 pm

Quote from: Come-from-Beyond on October 17, 2014, 08:20:35 pm

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 · October 17, 2014, 08:34:35 pm

Quote from: valarmg on October 17, 2014, 07:56:36 pm

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 · October 17, 2014, 09:23:48 pm

Quote from: kushti on October 17, 2014, 08:25:36 pm

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 · October 17, 2014, 09:37:34 pm

Quote from: Come-from-Beyond on October 17, 2014, 09:23:48 pm

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

Come-from-Beyond · October 17, 2014, 09:40:13 pm

Quote from: kushti on October 17, 2014, 09:37:34 pm

Quote from: Come-from-Beyond on October 17, 2014, 09:23:48 pm
"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 · October 17, 2014, 10:09:58 pm

Quote from: kushti on October 17, 2014, 09:37:34 pm

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 · October 17, 2014, 10:44:15 pm

Quote from: bcdev on October 17, 2014, 10:09:34 pm

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

Quote from: Come-from-Beyond on October 17, 2014, 10:09:58 pm

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"

News:

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