Topic: Multibranch forging approach (Read 8626 times)

andruiman · November 25, 2014, 07:53:18 pm

Hi Community!

We are happy to present our first paper on the research of multibranch forging in the PoS systems.
The paper is available here: https://www.scribd.com/doc/248208963/Multibranch-forging
and in the repository https://github.com/ConsensusResearch/articles-papers

The correspondent source code will be uploaded there in a few days.

We will be pleased with your comments and suggestions.

kushti · November 25, 2014, 08:51:10 pm

TL/DR version:

1. We made executable simulation of multibranch forging
2. We think multibranch forging properties are like a lot Transparent Forging properties
3. Multibranch forging results are looking much better than single-branch: nice Gaussian distribution around unit. In practice it means e.g. 1 min average gap with max. 4 mins gap max in very rare cases.
4. Computational efforts still an open question, with big prediction depth we are getting proof-of-work instead of proof-of-stake again.
5. Some things in our executable model are proved formally with the help of Coq theorem prover. E.g. it's proven formally our that our forging trees are balanced right

P.S. With multibranch forging it's easy to define & show nothing-at-stake problem. Next paper will be about that
P.P.S. Also our understanding of consensus in proof-of-stake networks is much deeper now, after playing with simulations(we have another one, Nxt-like, which will be presented soon as well)

valarmg · November 25, 2014, 09:07:34 pm

Fantastic.

What (in layman's terms) would you say the advantages of multibranch over using the single branch (with mcthl's improvements)?

Any thoughts on: https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity/ ? Or is that the subject for the next paper?

Come-from-Beyond · November 25, 2014, 09:16:42 pm

ELI5, multibranching is similar to TF with forgers who try to increase number of forged blocks?

mhps · November 26, 2014, 09:27:43 am

Since all POS coins have similar concern on nothing-at-stake so I ask it here.

I had some thoughts on what happens if many nodes put blocks on multiple branches (I called them alt-chains) at www peercointalk.org index.php?topic=2743.msg24350#msg24350 but never find anyone to think about the scenario seriously until now. I'm glad to see code and simulation along these thoughts. I am not familiar with transparent forging or the Coq language so I have some difficulty understand the paper fully. Can someone confirm that

* if only a few people forge on multiple blocks it is hopeless to gain significant advantage because few people extend the non-main branches you extend.

* if there is a significant fraction of nodes forge on multiple blocks, with many branches growing, because the number of branches grow exponentially, everyone are forced to drop braches at some point. As described in my post, the consensus-finding becomes POW.

benjyz · November 26, 2014, 09:44:32 am

Thanks for this work. Looking forward to try the code. On Linux Coq can be installed like this: sudo apt-get install coq coqide

I'm looking for a way to model latencies and Lamport partial order. I will try and see if I can do this with Coq and Haskell. I'll make a separate thread about this some day.

Btw, is it easy to convert latex into markdown these days? haven't used latex in a while. If you upload the raw files I could create a Pull-request if I have something.

benjyz · November 26, 2014, 09:52:11 am

Quote from: valarmg on November 25, 2014, 09:07:34 pm

Fantastic.

What (in layman's terms) would you say the advantages of multibranch over using the single branch (with mcthl's improvements)?

Any thoughts on: https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity/ ? Or is that the subject for the next paper?

Ethereum is based on the idea of state-machines and trees, which is fundamentally not how block-chains work. Block-chains are all about relative information and how information is spread across nodes.

I'm hopeful this project can improve the general understanding of these problems. If we have some good formal methods that will be a big improvement in the field.

andruiman · November 26, 2014, 11:16:35 am

Quote from: mhps on November 26, 2014, 09:27:43 am

Can someone confirm that

* if only a few people forge on multiple blocks it is hopeless to gain significant advantage because few people extend the non-main branches you extend.

* if there is a significant fraction of nodes forge on multiple blocks, with many branches growing, because the number of branches grow exponentially, everyone are forced to drop braches at some point. As described in my post, the consensus-finding becomes POW.

1. In the multibranch forging the "main" chain doesn't exist in common vision. However if all use the same tree balancing algorithm it is algorithmically defined. But that is no hope that this definition would satisfy everybody in a general case. So if only few nodes (with insignificant stake) use tree forging they unlikely get some benefits from this as their blocks will not be accepted by the rest of network. But if they can in some time create better chain than the "main" chain they will win. As the tree longest chain grows ~twice faster than the single "main" chain that should be taken more seriously. We will dedicate another research to the behavior of heterogeneous network with different strategies in nodes.

2.Yes, you are right. However with the same Blocktree structure nodes can always get the algorithmically defined consensus. A problem is that trying to find the best chain in advance (to get more fee or whatever) nodes will try to forge as many blocks and as deep as they can, consuming power. However if they like, they can get a consensus at any time. The multibranch PoS is going to PoW because of concurrency - not solidarity.

andruiman · November 26, 2014, 11:28:23 am

Quote from: Come-from-Beyond on November 25, 2014, 09:16:42 pm

ELI5, multibranching is similar to TF with forgers who try to increase number of forged blocks?

Yes, actually there could be applied different measures on branches to choose the best. In our simulation we use the unit measure that is cumulative weight
of a chain is equal to its length. So we separate the forging on two phases: (1) building blocks and (2) choosing a branch. When building blocks nodes share them in a tree-like way and that is "transparency", when choosing the branch they use their strategy which generally speaking can be selected independently.

Come-from-Beyond · November 26, 2014, 11:45:00 am

Quote from: andruiman on November 26, 2014, 11:28:23 am

Yes, actually there could be applied different measures on branches to choose the best.

BTW, I've heard that cryptocoins with cumulative difficulty measured as SUM(1/baseTarget_i²) are more stable (consensus-wise) than ones with SUM(1/baseTarget_i) and SUM(1/baseTarget_i³). Just a rumor, but still...

mhps · November 26, 2014, 12:24:41 pm

Thanks for the explanation.

kushti · November 26, 2014, 02:39:45 pm

Quote from: valarmg on November 25, 2014, 09:07:34 pm

What (in layman's terms) would you say the advantages of multibranch over using the single branch (with mcthl's improvements)?

It's not ready for being implemented, we need to solve hard questions around consensus first. In best case we'll beat Nothing-at-Stake concerns

Quote from: valarmg on November 25, 2014, 09:07:34 pm

Any thoughts on: https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity/ ? Or is that the subject for the next paper?

Funny thing, we're writing about similar things under different names(”consensus in acting” / ”consensus in vision”) independently from Vitalik

Quote

The procedure of blocks generating in the PoS systems is called forging.
The difference between PoW and PoS systems arises when we think of what
block to build. Actually each account running a node in the network is
generally speaking free to choose what to do - the only thing we can claim
from it is to follow a certain protocol to belong to a certain CC network. In
the PoW systems there exist the most powerful branch and nodes choose to
build a block on the top of the last block in this chain because they cannot
build on several branches with the same computational power. That is a
way to create a network consensus - roughly speaking, an account (or node)
who decided to build a block in other place should be more powerful or lucky
than all the nodes who decided to build a ”right-placed” block and therefore
the winning strategy is most probable to act as others. The latter could be
called ”consensus in acting” when doing the same things will benefit sides in
getting the result. The weaker form of consensus can be called ”consensus
in vision” when we get the same result doing theoretically different things or
even more weak - the peers can potentially have different network data (”the
intermediate result”) which is nevertheless equally interpreted.

Regarding Slasher / Slasher 2.0, we're pretty sceptical about those tricky hacks now. What if some nodes will avoid using it? Why to try to punish for multibranch forging at all?

kushti · November 26, 2014, 04:44:52 pm

Quote from: benjyz on November 26, 2014, 09:44:32 am

Thanks for this work. Looking forward to try the code. On Linux Coq can be installed like this: sudo apt-get install coq coqide

I'm looking for a way to model latencies and Lamport partial order. I will try and see if I can do this with Coq and Haskell. I'll make a separate thread about this some day.

Btw, is it easy to convert latex into markdown these days? haven't used latex in a while. If you upload the raw files I could create a Pull-request if I have something.

1. We'll publish linux (and maybe windows) executable as well as sources, so there's no need to install Coq & Haskell if you want just to play with forging model and change parameters in properties file. However if you want to go deeper, Haskell needed at least (& Coq if you want to play with proofs). Haskell could be installed with 'sudo apt-get ghc'

2. We would like to see Haskell (& Coq) guys contributing. We'll pay bounties for interesting work done.

3. There's also another simulation of single-branch Nxt-like forging. Will be published within next few days as well. Latency will be added to it at some point, but first release without modelling of it.

4. We can put Latex sources in repo if that matters

P.S. for those who want to get into Coq, there's amazing book about http://www.amazon.com/Interactive-Theorem-Proving-Program-Development/dp/3540208542/ref=sr_1_1?ie=UTF8&qid=1417020126&sr=8-1&keywords=coq+theorem+proving . Some knowledge of Lambda Calculus / type theory needed in prior, there's wonderful & solid book on both topics: http://www.amazon.com/Types-Programming-Languages-Benjamin-Pierce/dp/0262162091/ref=sr_1_1?s=books&ie=UTF8&qid=1417020248&sr=1-1&keywords=types+and+programming+languages&pebp=1417020249340

mhps · November 27, 2014, 12:16:30 am

Quote from: kushti on November 26, 2014, 02:39:45 pm

In best case we'll beat Nothing-at-Stake concerns
...
Regarding Slasher / Slasher 2.0, we're pretty sceptical about those tricky hacks now. What if some nodes will avoid using it? Why to try to punish for multibranch forging at all?

This is a record of peercoin community's effort to eliminate possibility of forging (called minting for peercoin) multiple chains simultaneously:
www peercointalk.org/index.php?topic=3621.0 (can't post external link. has to doctor the url)
As Jordan Lee commented, the solution is much more elegant than those proposed in Vitalik Buterin's blog.

edit:spelling

andruiman · November 27, 2014, 07:21:40 am

Quote from: kushti on November 26, 2014, 04:44:52 pm

4. We can put Latex sources in repo if that matters

done

kushti · November 27, 2014, 12:20:40 pm

Quote from: Come-from-Beyond on November 26, 2014, 11:45:00 am

BTW, I've heard that cryptocoins with cumulative difficulty measured as SUM(1/baseTarget_i²) are more stable (consensus-wise) than ones with SUM(1/baseTarget_i) and SUM(1/baseTarget_i³). Just a rumor, but still...

You will have the possibility to check this pretty soon by changing slightly source of an executable simulation tool, just change second line of

Quote

cumulativeDifficulty :: BlockChain -> Double
cumulativeDifficulty chain = sum(map (\bl -> 1.0 / (fromIntegral $ baseTarget bl)) chain

with

Quote

cumulativeDifficulty chain = sum(map (\bl -> 1.0 / (fromIntegral $ baseTarget bl)**2 ) chain)

or

Quote

cumulativeDifficulty chain = sum(map (\bl -> 1.0 / (fromIntegral $ baseTarget bl)**3 ) chain)

kushti · November 27, 2014, 06:54:57 pm

Finally, our MultiBranch Forging Simulation Tool is open-sourced! https://github.com/ConsensusResearch/MultiBranch

For now, executable file & Haskell sources to produce it are published. Coq sources with proofs will be published soon as well.

Happy experiments!

benjyz · November 27, 2014, 07:38:56 pm

To run I 1) installed haskell, then 2) cabal, then 3) cabal update and then cabal install ConfigFile. Then 4) ./compile.sh and 5) run the multibranch binary and it worked.

Haskell book:
http://book.realworldhaskell.org/read/

kushti · November 28, 2014, 03:18:06 pm

Coq sources have been published! https://github.com/ConsensusResearch/MultiBranch

kushti · November 28, 2014, 04:44:21 pm

Quote from: mhps on November 27, 2014, 12:16:30 am

This is a record of peercoin community's effort to eliminate possibility of forging (called minting for peercoin) multiple chains simultaneously:
www peercointalk.org/index.php?topic=3621.0 (can't post external link. has to doctor the url)
As Jordan Lee commented, the solution is much more elegant than those proposed in Vitalik Butterin's blog.

Thanks a lot, we'll take a look into it. And I agree, all Proof-o-Stake currencies share N@S concern. Even more, they share much more. So it will be cool to share research efforts as well.

News:

Author Topic: Multibranch forging approach (Read 8626 times)