Nothing-at-Stake & Long Range Attack on Proof-of-Stake (Consensus Research)

[kushti]

My comment on Poelstra's rewrite of PoS impossibility article https://www.reddit.com/r/Bitcoin/comments/2zpmlj/expanded_rewrite_of_distributed_consensus_from/cplj4ug

[1714939677]

1714939677

[1714939677]

1714939677

[1714939677]

1714939677

[1714939677]

1714939677

[kushti]

Slides from my talk @ SF Bitcoin Devs Hackathon (titled "Proof-of-Stake and its Improvements") http://www.slideshare.net/AlexChepurnoy/proofofstake-its-improvements-san-francisco-bitcoin-devs-hackathon

[Este Nuno]

Slides from my talk @ SF Bitcoin Devs Hackathon (titled "Proof-of-Stake and its Improvements") http://www.slideshare.net/AlexChepurnoy/proofofstake-its-improvements-san-francisco-bitcoin-devs-hackathon

Any good criticisms there?

[kushti]

Any good criticisms there?

Got some good questions & feedback. Love Sunday meetups much more than others 

[Daedelus]

I guess no one has any found any fatal flaws in this research then?

What are the next steps Kushti, were you planning on testing a modified algo in a test coin?

[kushti]

I guess no one has any found any fatal flaws in this research then?

What are the next steps Kushti, were you planning on testing a modified algo in a test coin?

No any critical flaws found in Nxt-like proof-of-stake. On other hand, no any strict formalization made yet as well.

So there are two things to be done:

1. Formalized model showing Nakamoto's property could be met in proof-of-stake with contribution to multiple forks allowed(in other cases there are other problems with formalization). Simulations show the property is seems to be met, thanks to cumulative difficulty working more or less ok as fork selector function(btw, PoS coins with longest chain rule have problems here, at least).
I'm now talking with guys much more skilled in CS/math about possibility of the truly formal framework.

2. Practical contributions to Nxt / other projects around. Nxt's algo seems to be pretty safe, though block delays distribution is needed to be better(closer to average value). It will reduce or mb even eliminate incentive to contribute to multiple forks(by trying to do private branch attacks, then share private forks, then we have majority of forgers having multiple-branch forging with N@S possible as result in such environment). I hope some improvements will be made in 1.7/1.8.

And yeah, "test coin"(don't like "coin" word here, I would like to call it "experimental blockchain engine for hackers"). Making some changes now, so it will be possible to switch Qora's PoS to Nxt's by changing 1 line of code(and introduce other consensus models easily). Then yeah, multiple branching will be introduced in Scorex. Some non-consensus things will be tested as well, e.g. Bill White's scalability proposal etc.

[kushti]

Switching from Qora's to Nxt's algo with 1 line change is implemented, having a lot of fun by playing with both algos.

[allwelder]

I guess no one has any found any fatal flaws in this research then?

What are the next steps Kushti, were you planning on testing a modified algo in a test coin?

No any critical flaws found in Nxt-like proof-of-stake.

Glad to hear this.

Thanks,kushti.

[Daedelus]

I guess no one has any found any fatal flaws in this research then?

What are the next steps Kushti, were you planning on testing a modified algo in a test coin?

No any critical flaws found in Nxt-like proof-of-stake. On other hand, no any strict formalization made yet as well.

So there are two things to be done:

1. Formalized model showing Nakamoto's property could be met in proof-of-stake with contribution to multiple forks allowed(in other cases there are other problems with formalization). Simulations show the property is seems to be met, thanks to cumulative difficulty working more or less ok as fork selector function(btw, PoS coins with longest chain rule have problems here, at least).
I'm now talking with guys much more skilled in CS/math about possibility of the truly formal framework.

2. Practical contributions to Nxt / other projects around. Nxt's algo seems to be pretty safe, though block delays distribution is needed to be better(closer to average value). It will reduce or mb even eliminate incentive to contribute to multiple forks(by trying to do private branch attacks, then share private forks, then we have majority of forgers having multiple-branch forging with N@S possible as result in such environment). I hope some improvements will be made in 1.7/1.8.

And yeah, "test coin"(don't like "coin" word here, I would like to call it "experimental blockchain engine for hackers"). Making some changes now, so it will be possible to switch Qora's PoS to Nxt's by changing 1 line of code(and introduce other consensus models easily). Then yeah, multiple branching will be introduced in Scorex. Some non-consensus things will be tested as well, e.g. Bill White's scalability proposal etc.

Bump  

Any news on the truly formal framework formalization?

Or the "experimental blockchain engine for hackers"?

P.S. Bill white plans to contact you about Scorex when he has time...

[fish731]

I guess no one has any found any fatal flaws in this research then?

What are the next steps Kushti, were you planning on testing a modified algo in a test coin?

No any critical flaws found in Nxt-like proof-of-stake. On other hand, no any strict formalization made yet as well.

So there are two things to be done:

1. Formalized model showing Nakamoto's property could be met in proof-of-stake with contribution to multiple forks allowed(in other cases there are other problems with formalization). Simulations show the property is seems to be met, thanks to cumulative difficulty working more or less ok as fork selector function(btw, PoS coins with longest chain rule have problems here, at least).
I'm now talking with guys much more skilled in CS/math about possibility of the truly formal framework.

2. Practical contributions to Nxt / other projects around. Nxt's algo seems to be pretty safe, though block delays distribution is needed to be better(closer to average value). It will reduce or mb even eliminate incentive to contribute to multiple forks(by trying to do private branch attacks, then share private forks, then we have majority of forgers having multiple-branch forging with N@S possible as result in such environment). I hope some improvements will be made in 1.7/1.8.

And yeah, "test coin"(don't like "coin" word here, I would like to call it "experimental blockchain engine for hackers"). Making some changes now, so it will be possible to switch Qora's PoS to Nxt's by changing 1 line of code(and introduce other consensus models easily). Then yeah, multiple branching will be introduced in Scorex. Some non-consensus things will be tested as well, e.g. Bill White's scalability proposal etc.

Will you be integrating the finished thing into Qora before Nxt to see how it performs on a main net?

[kushti]

Bump  

Any news on the truly formal framework formalization?

Or the "experimental blockchain engine for hackers"?

P.S. Bill white plans to contact you about Scorex when he has time...

1. No major news in the field of truly formal proof-of-stake description. It's the question of months at least probably(btw, good formal framework describing proof-of-work appeared only in second half of 2014, 5+ years after Nakamoto's paper which is pretty informal).

2. Just made pre-announcement https://bitcointalk.org/index.php?topic=1060567


P.S. Communicating with the awesome guy Bill regularly

Will you be integrating the finished thing into Qora before Nxt to see how it performs on a main net?

Nope. And Nxt will got some evolutional improvements, not radical. as radical changes seems to be not much needed at all. Qora's algo needs for some other improvements, I would like not to disclose the details here though.

[Peter R]

Formalized model showing Nakamoto's property could be met in proof-of-stake…

Kushti, what exactly do people mean when they say "Nakamoto's property"?  Can you link me to somewhere that gives a precise definition for this term?

1. No major news in the field of truly formal proof-of-stake description. It's the question of months at least probably(btw, good formal framework describing proof-of-work appeared only in second half of 2014, 5+ years after Nakamoto's paper which is pretty informal).

Any links you can share for "good formal framework describing proof-of-work"?

[kushti]

Formalized model showing Nakamoto's property could be met in proof-of-stake…

Kushti, what exactly do people mean when they say "Nakamoto's property"?  Can you link me to somewhere that gives a precise definition for this term?

1. No major news in the field of truly formal proof-of-stake description. It's the question of months at least probably(btw, good formal framework describing proof-of-work appeared only in second half of 2014, 5+ years after Nakamoto's paper which is pretty informal).

Any links you can share for "good formal framework describing proof-of-work"?

Well, I meant this awesome paper https://eprint.iacr.org/2014/765.pdf . Please take a look to "The common prefix property" in the paper - it's literally the same as "Nakamoto's property".

[kushti]

Just finished constructive proof of the FLP impossibility theorem with Coq https://github.com/ConsensusResearch/flp . Hope it will  be a step to blockchain consensus formalization. Now I have a lot of other work to do but hope Coq repository with blockchain consensus formalization code(PoS-friendly) will be started someday

[Daedelus]

Kushti,

I came across a guy looking and thinking deeply about POS.

See https://bitcointalk.org/index.php?topic=1082139.msg11547314#msg11547314


It opens...

Multiple Voting in POS Cannot be Detected and It Weakens Security

... I made him aware of your work  but he seems serious and open minded so maybe you two can help each other to keep pushing the boundaries.

[kushti]

Kushti,

I came across a guy looking and thinking deeply about POS.

See https://bitcointalk.org/index.php?topic=1082139.msg11547314#msg11547314


It opens...

Multiple Voting in POS Cannot be Detected and It Weakens Security

... I made him aware of your work  but he seems serious and open minded so maybe you two can help each other to keep pushing the boundaries.

Thanks, answered there

[Daedelus]

Update:

No activity in the subforum for last months, but we continue to work! 

1. Scorex, our fully working cryptocurrency prototype, was pre-announced on BitcoinTalk. Hopefully, will be announced soon here & on BitcoinTalk. We plan to use it to check our ideas in the close-to-real-world environment. https://github.com/ConsensusResearch/Scorex-Lagonaki

2. I made alternative constructive proof of the FLP theorem with Coq: https://github.com/ConsensusResearch/flp . Hope to publish a paper about that in a peer-reviewed journal. andruiman has some Coq code done around CC transactions layer, will be published later.

3. We have some proposals on PoS improvements, preparing to publish them along with possible attack vectors, in form of blogposts and/or reviewed papers(seems we will write no non-reviewed internet papers on that).

4. We're starting to work with jl777 on research around crypto777. andruiman is starting to check its' pegging ideas.

5. More news soon


So progress is not super-fast, but we're making it

[Este Nuno]

Can anyone link me to some criticism of these claims by qualified people? I'm especially interested in a rebuttal to the claim that long range NaS attacks are not possible in the system that kushti has defined in his and his group's research.

[cynicSOB]

Can anyone link me to some criticism of these claims by qualified people? I'm especially interested in a rebuttal to the claim that long range NaS attacks are not possible in the system that kushti has defined in his and his group's research.

I think long range is not possible because rolling checkpoints. Also when downloading a new chain there is a trust system so you download from a trusted source. Rolling checkpoints are nice but create the risk of dividing the network. A fork larger than the largest allowed reorganization would not be resolved and the network would split.

I came across a guy looking and thinking deeply about POS.

See https://bitcointalk.org/index.php?topic=1082139.msg11547314#msg11547314

maybe he's thinking too deeply: he proposes an overcomplication that generates centralization and doesn't solve the problem it's supposed to solve.

[Este Nuno]

Can anyone link me to some criticism of these claims by qualified people? I'm especially interested in a rebuttal to the claim that long range NaS attacks are not possible in the system that kushti has defined in his and his group's research.

I think long range is not possible because rolling checkpoints. Also when downloading a new chain there is a trust system so you download from a trusted source. Rolling checkpoints are nice but create the risk of dividing the network. A fork larger than the largest allowed reorganization would not be resolved and the network would split.

I remember Bitcoin itself was using checkpoints at one time, not too long ago too. Haven't heard much about that in a while. Do you or anyone else know if they are still in use at all?