Topic: Consensus Research 2015 (Read 6020 times)

kushti · « **on:** January 16, 2015, 12:39:52 pm »

We didn't lose time during the holidays, and happy to publish recent news & our plans for 2015!

After a lot of research made & few papers published we're understanding attacks on proof-of-stake pretty well. The summary from the BTT topic (https://bitcointalk.org/index.php?topic=897488.msg10152632#msg10152632)

Quote

1. Short-range attack - attacker can offer better chain started few blocks behind current canonical chain. The attack is possible at the moment, the only likely outcome though is just gathered fees increase for an attacker. In our simulations this kind of attack is possible mostly when a long delay occurs due to low target. By the way, the attack has positive aspect for network, as it shorten delays average between blocks. So attacker gets extra fees for a good job done Grin

2. Long-range attack - attacker can start fork hundreds or thousands blocks behind current chain. From our investigations the attack isn't possible.

3. Nothing-at-stake attack - not possible at the moment! Will be possible when a lot of forgers will use multiple-branch forging to increase profits. Then attacker can contribute to all the chains(some of them e.g. containing a transaction) then start to contribute to one chain only behind the best(containing no transaction) making it winner. Previous statements on N@S attack made with assumption it costs nothing to contribute to an each fork possible and that makes N@S attack a disaster. In fact, it's not possible at all to contribute to each fork possible, as number of forks growing exponentially with time. So the only strategy for a multibranch forger is to contribute to N best forks. In such scenario attack is possible only within short-range e.g. with 25 confirmations needed 10% attacker can't make an attack. And attack is pretty random in nature, it's impossible to predict whether 2 forks will be within N best forks(from exponentially growing set) for k confirmations. So from our point of view the importance of the attack is pretty overblown.

4. History attack - attacker can buy whale's private key for $5 and build alternative story. Solved with some checkpoints now, located behind max rollback possible, so the solution is not so scary in terms of centralization etc.

There are also issues we want to resolve e.g. long delays. So we have no any deadly threat, but several annoying issues.

From playing a lot with simulation tools we realized most of problems will be less important with a better measure(than just cumulative difficulty). andruiman finished a new paper with a simple but working proposal, will be sent to investors very soon. Even with singlebranching pos better measure would be very helpful. Then we'll play with more complicated proposals, including proof-of-stake + proof-of-activity hybrid.

Papers & articles
andruiman has the nice plan for next papers to be published:

1. Comprehensive analysis of the blockchain measure influence on the multibranch forging convergence

2. Theoretical physics and abstract math analogues and inspiration for the world of CC economy (mostly philosophical stuff)

3. Proof-of-Stake "algebra" and its formal Coq specifications (with publishing in truly scientific journals)

SCOREX

Regarding multiple-branch forging, it seems promising in theory, but there are some questions regarding effective implementation. As Nxt core is pretty bold these days(40+K lines of code), I worked during few weekends on Qora code simplification. Started with original 24K I have 9K now with 3K in Scala and 6K in Java. Finally I'll have a coin prototype with no production quality but in just 5-6K lines of Scala code. I've chosen SCOREX name for that(SCala&qORa-based blockchain-driven network for EXperiments). So we will use it for experimental multiple-branch implementation, and will invite enthusiasts to set up nodes for the experiment(>10 nodes are enough I guess). Later well-tested results will be incorporated into Nxt core(or not in case of failed experiment

SCOREX also will be outsourced for other researchers need(to make cryptocurrency-related experiments quick to implement).

youyou · « **Reply #1 on:** January 16, 2015, 12:55:01 pm »

on what distrib of linux did you run your forging simu? i tried to compile it under Linux Mint but looks like some GHC packages are missing.

kushti · « **Reply #2 on:** January 16, 2015, 01:38:09 pm »

Quote from: youyou on January 16, 2015, 12:55:01 pm

on what distrib of linux did you run your forging simu? i tried to compile it under Linux Mint but looks like some GHC packages are missing.

which ones? please send me your error message, I'll help with fixing.

youyou · « **Reply #3 on:** January 16, 2015, 06:57:54 pm »

Code: [Select]

simulation.hs:7:18:
    Could not find module `Data.Random.List'

kushti · « **Reply #4 on:** January 17, 2015, 03:08:24 pm »

Quote from: youyou on January 16, 2015, 06:57:54 pm

Code: [Select]
simulation.hs:7:18: Could not find module `Data.Random.List'

Fixed code itself, so please pull last changes

kushti · « **Reply #5 on:** January 21, 2015, 05:03:46 pm »

New paper sent to the investors(having >= 10K assets) http://www.mynxt.info/blockexplorer/details.php?action=ac&ac=4148195338447719647 . The paper will be publicly available few days later

andruiman · « **Reply #6 on:** January 23, 2015, 02:28:03 pm »

We have updated our github repository https://github.com/ConsensusResearch/ForgingSimulation with a new version of the PoS simulation haskell code.
It now included two branches, master - for the single branch classical Nxt based code and "multibranch-experimental" - for the multibranch forging simulation. Recently
new algorithm for regulating tails switching effect is proposed and implemented. With it, a possibility of the N@S attack becomes also regulated as we now can introduce deducible parameter of confirmations needed to stabilize recent blocks tails. The idea of regulating is straightforward - from time to time the node "forgets" almost all the branches and prolong only those whose cumulativeDifficulty measure is above some retargeting threshold. This threshold changes discretely, starting from 0. Unlike the Bitcoin difficulty param, the threshold always grows as the best block cumulativeDifficulty exceeds the previous threshold+delta. So nodes work as multibranch almost all the time, but sometimes becomes "single-branch" for a short time (one tick). This approach allows to have all the multibranch benefits and also get the network with regulating convergence. With a certain confirmation number calculated, we can propose the strong resistance to the N@S as the long tails switching become very-very unlikely after the confirmations. We'll present the N@S simulation results ASAP.

There are more possible regulation procedures, for sure. Basing on the idea that sometimes nodes switch to the single-branch behavior one can introduce any verifiable quasi-random algorithm to do this. The proposed is the simple but efficient one, however more complicated algos (e.g. based on some nice hashes) could secure the system more likely.

andruiman · « **Reply #7 on:** January 23, 2015, 02:44:20 pm »

One of the next step of investigation I propose strict formalization of the PoS systems with algebraic approach and Coq specification. It can be considered as a standard for such systems and even published in IEEE or whatever. So I'd like to ask the community to share opinions of such initiative. So the idea is to create a triangle: standard (i.e. spec) -> reference implementation -> production implementations. Nxt IMO is the best platform to start as it has very open community.

(Also the most detailed description of the different measures influence on the multibranch forging is on the way. That will be given to show some difficulties to prevent the branching behavior to diverge - e.g. it cannot be predictable for one branch to be better than the current best in some steps! and as far as I understand at the moment the only way to stop the switching is to stop branching

for a short while).

Come-from-Beyond · « **Reply #8 on:** January 23, 2015, 03:17:55 pm »

I'd like to see how a quantum computer could simplify prediction.

andruiman · « **Reply #9 on:** February 04, 2015, 02:52:02 pm »

Quote from: andruiman on January 23, 2015, 02:28:03 pm

We have updated our github repository https://github.com/ConsensusResearch/ForgingSimulation with a new version of the PoS simulation haskell code.
It now included two branches, master - for the single branch classical Nxt based code and "multibranch-experimental" - for the multibranch forging simulation. Recently
new algorithm for regulating tails switching effect is proposed and implemented. With it, a possibility of the N@S attack becomes also regulated as we now can introduce deducible parameter of confirmations needed to stabilize recent blocks tails. The idea of regulating is straightforward - from time to time the node "forgets" almost all the branches and prolong only those whose cumulativeDifficulty measure is above some retargeting threshold. This threshold changes discretely, starting from 0. Unlike the Bitcoin difficulty param, the threshold always grows as the best block cumulativeDifficulty exceeds the previous threshold+delta. So nodes work as multibranch almost all the time, but sometimes becomes "single-branch" for a short time (one tick). This approach allows to have all the multibranch benefits and also get the network with regulating convergence. With a certain confirmation number calculated, we can propose the strong resistance to the N@S as the long tails switching become very-very unlikely after the confirmations. We'll present the N@S simulation results ASAP.

There are more possible regulation procedures, for sure. Basing on the idea that sometimes nodes switch to the single-branch behavior one can introduce any verifiable quasi-random algorithm to do this. The proposed is the simple but efficient one, however more complicated algos (e.g. based on some nice hashes) could secure the system more likely.

New paper on tails switching effect had been publicly released (https://github.com/ConsensusResearch/articles-papers/tree/master/switching). However the results of the simulations presented in the paper have been already renewed by the simulation software at https://github.com/ConsensusResearch/ForgingSimulation/tree/multibranch-experimental with the proposed threshold algorithm. As expected the algorithm allows to have confirmation number parameter deducible from the system constants and prevents the prolongation of similar branches. With it the resistance to the N@S becomes feasible and measurable! The results of N@S simulation + switching tails length distribution are coming.

ThomasVeil · « **Reply #10 on:** February 08, 2015, 11:49:58 pm »

Maybe you can send your papers to the guy the coindesk article writes about. I don't know if he only wants peer reviewed stuff - or only Bitcoin. But I can imagine he would be interested.

Daedelus · « **Reply #11 on:** February 16, 2015, 01:50:33 pm »

Quote from: andruiman on February 04, 2015, 02:52:02 pm

Quote from: andruiman on January 23, 2015, 02:28:03 pm
We have updated our github repository https://github.com/ConsensusResearch/ForgingSimulation with a new version of the PoS simulation haskell code.
It now included two branches, master - for the single branch classical Nxt based code and "multibranch-experimental" - for the multibranch forging simulation. Recently
new algorithm for regulating tails switching effect is proposed and implemented. With it, a possibility of the N@S attack becomes also regulated as we now can introduce deducible parameter of confirmations needed to stabilize recent blocks tails. The idea of regulating is straightforward - from time to time the node "forgets" almost all the branches and prolong only those whose cumulativeDifficulty measure is above some retargeting threshold. This threshold changes discretely, starting from 0. Unlike the Bitcoin difficulty param, the threshold always grows as the best block cumulativeDifficulty exceeds the previous threshold+delta. So nodes work as multibranch almost all the time, but sometimes becomes "single-branch" for a short time (one tick). This approach allows to have all the multibranch benefits and also get the network with regulating convergence. With a certain confirmation number calculated, we can propose the strong resistance to the N@S as the long tails switching become very-very unlikely after the confirmations. We'll present the N@S simulation results ASAP.

There are more possible regulation procedures, for sure. Basing on the idea that sometimes nodes switch to the single-branch behavior one can introduce any verifiable quasi-random algorithm to do this. The proposed is the simple but efficient one, however more complicated algos (e.g. based on some nice hashes) could secure the system more likely.

New paper on tails switching effect had been publicly released (https://github.com/ConsensusResearch/articles-papers/tree/master/switching). However the results of the simulations presented in the paper have been already renewed by the simulation software at https://github.com/ConsensusResearch/ForgingSimulation/tree/multibranch-experimental with the proposed threshold algorithm. As expected the algorithm allows to have confirmation number parameter deducible from the system constants and prevents the prolongation of similar branches. With it the resistance to the N@S becomes feasible and measurable! The results of N@S simulation + switching tails length distribution are coming.

Nice. I will cross post to BTT.

colin012 · « **Reply #12 on:** February 16, 2015, 05:37:36 pm »

There are ways of doing history attacks without any NXT that are still reasonably possible. No need to buy a key. It would be difficult to do but still possible. I don't want to go into detail because I don't want to give anyone ideas. But the solution is more nodes

Daedelus · « **Reply #13 on:** March 01, 2015, 02:11:31 pm »

You might be aware already but just in case... dated 21st Jan 2015.

https://download.wpsoftware.net/bitcoin/alts.pdf

Quote

In its initial incarnation, NXT was susceptible to a trivial stake-grinding attack (to be described below)
and could not achieve any consensus.

Not sure it is worth your time, he has obviously not attempted to understand Nxt (and I think you already covered it in your research) but thought I'd flag it up

Edit: I don't think they have attempted to understand or even acknowledge your research, it just seems a rehash of the POS.pdf 'paper'

Quote

Intuitively, it seems impossible to obtain distributed consensus without provably consuming some resource outside of the system, but there is no rigorous argument for this claim.

Sound familiar?

Come-from-Beyond · « **Reply #14 on:** March 01, 2015, 02:31:57 pm »

Quote from: Daedelus on March 01, 2015, 02:11:31 pm

Quote
Intuitively, it seems impossible to obtain distributed consensus without provably consuming some resource outside of the system, but there is no rigorous argument for this claim.

Sound familiar?

That guy is right IMO. Consensus is impossible without consuming some resource outside of the system. What he missed though is that physical time is resource too. Forging "consumes" time of the outside world, this is why blocks from the future are rejected.

Daedelus · « **Reply #15 on:** March 01, 2015, 02:43:34 pm »

Seems legit to me. I would say email him feedback but I don't think you'd have the motivation as/and I doubt he would listen. I guess time is critical to this 'thermodynamic world' he keeps bamboozling people with, otherwise a heat loss graph would only have one axis if time doesn't exist.. but then isn't time an illusion... *brain reboots*

kushti · « **Reply #16 on:** March 02, 2015, 08:45:20 am »

Quote from: Daedelus on March 01, 2015, 02:11:31 pm

You might be aware already but just in case... dated 21st Jan 2015.

https://download.wpsoftware.net/bitcoin/alts.pdf

Unfortunately, the new version of Adam's treatise is just slightly more detailed than previous. Again, no any proofs, just some thoughts.

Quote

In its initial incarnation, NXT was susceptible to a trivial stake-grinding attack (to be described below)
and could not achieve any consensus. Since becoming closed-source while spamming technically-
illiterate claims at popular conferences, it has fallen out of scope of this document

Daedelus · « **Reply #17 on:** March 26, 2015, 10:19:31 am »

"The NeuCoin white paper just released - rebutting all “nothing at stake” objections to proof-of-stake"

https://nxtforum.org/general-discussion/neucoin's-40-page-white-paper-rebuts-all-nothing-at-stake-objections/

koubiac · « **Reply #18 on:** March 26, 2015, 12:08:31 pm »

Hi everybody,

Thanks Daedelus for providing the link.

Kushti, I've been reading your work for some time, and I think it's great you're publicly addressing the flaws of anti-PoS papers (reddit.com/r/Bitcoin/comments/2zpmlj/expanded_rewrite_of_distributed_consensus_from/ )

The community definitely needs more of this type of communication.
We’d love to get some feedback from you on the white paper in general.

In particular, we’re interested in whether PoS can not only “keep clients in consensus over time if they were in consensus at an earlier time" but also allow to “trustless bootstrap” or “trustless update” after a node has been offline for a significant period.
This is an area of research for us, what do you guys think about this at NXT?
IMO these kind of issues are way smaller than the ones bitcoin is facing but it's something to keep in mind considering the fact that people like Andrew Poelstra seem to have an issue with this
(reddit.com/r/Bitcoin/comments/2zpmlj/expanded_rewrite_of_distributed_consensus_from/cplardu )

Come-from-Beyond · « **Reply #19 on:** March 26, 2015, 01:32:28 pm »

Quote from: koubiac on March 26, 2015, 12:08:31 pm

This is an area of research for us, what do you guys think about this at NXT?

I think that we should come to a consensus on the definitions first. This issue became a serious obstacle to comfortable academic discussions. Maybe I'll write a whitepaper on this.

News:

Author Topic: Consensus Research 2015 (Read 6020 times)