PARSEC The Release of the Code

parsec

#1

Following the release of the PARSEC Whitepaper on the 24th May and a decent amount of buzz online, the MaidSafe team are now excited to reveal the release of the code behind PARSEC. As mentioned at the time, we’ve been working round the clock to deliver on the promise of the White Paper and we’re delighted to get to this point of successfully releasing working code after only a few weeks.

The Protocol for Asynchronous, Reliable, Secure and Efficient Consensus is, as far as we’re aware, the world’s first asynchronous, byzantine fault tolerant consensus mechanism and from today you can download it yourself free!

As you’ll know if you’ve been following the evolution of the SAFE Network for any length of time, a commitment to open source software is a fundamental part of our DNA and this release reinforces the point. PARSEC is a key advancement for the the SAFE network but we hope that the benefits from the work that we’ve carried out will travel far beyond the Network alone. Creating consensus and reliably communicating truths are fundamental challenges for all decentralised projects and our hope is that many others will be able to benefit from the work that we’ve carried out and the code that we’re releasing today.

PARSEC allows decentralised networks to reach agreement on a series of events, actions or activities in a secure and reliable manner that is not only highly asynchronous but also Byzantine Fault Tolerant. In other words, the Network is mathematically guaranteed to reach consensus (provided no more than one-third of nodes are malicious or unresponsive for whatever reason). You can now read the whitepaper and download the code directly from GitHub. As always we welcome comment, discussion and collaboration. We are excited to see what more can come from PARSEC.

As a reminder, everything is being released under a GPLv3 Licence (with linking exception)) so there’s nothing to stop you downloading the code. In fact, we’re actively encouraging you to go and do just that. The more the merrier!

For more information check out the Medium post and give it a clap if you like what you see.

@dugcampbell has also created this short video to help give you an overview of PARSEC and the new release.


SAFE Network Dev Update - July 12, 2018
#2

From the README

Soak testing has been performed for tens of thousands of run without errors

Upcoming Features

Perform measurements of Transactions Per Second in simulated network
Use setup that can be compared with competing consensus protocols

Exciting times, cant wait for the comparison. Let’s just assume it will blow folks minds!

MAIDSAFE you are a beast!!


#3

Accompanying video is great. I think a lot of people will appreciate this. Hope to see more visual content like this.


#4

If you are following along with the tutorial and its been a while since you last used rust, remember and do
rustup update

to avoid screens of depressing errors.
Then hopefully you will get lots of green and this kind of thing

     Running target/release/deps/integration_tests-d5aca3cbe4e016bc

running 7 tests
Writing dot files in "/tmp/parsec_graphs/ZwRkgS/test_multiple_votes_before_gossip"
Writing dot files in "/tmp/parsec_graphs/ZwRkgS/test_minimal_network"
Writing dot files in "/tmp/parsec_graphs/ZwRkgS/test_duplicate_votes_before_gossip"
Writing dot files in "/tmp/parsec_graphs/ZwRkgS/test_multiple_votes_during_gossip"
Writing dot files in "/tmp/parsec_graphs/ZwRkgS/test_faulty_third_never_gossip"
Writing dot files in "/tmp/parsec_graphs/ZwRkgS/test_faulty_third_terminate_concurrently"
Writing dot files in "/tmp/parsec_graphs/ZwRkgS/test_faulty_third_terminate_at_random_points"
test minimal_network ... ok
test duplicate_votes_before_gossip ... ok
test multiple_votes_before_gossip ... ok
test multiple_votes_during_gossip ... ok
test faulty_third_never_gossip ... ok
test faulty_third_terminate_concurrently ... ok
test faulty_third_terminate_at_random_points ... ok

test result: ok. 7 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

   Doc-tests parsec

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

#5

Great news!!

Fabulous video, @dug!!


#6

Very well done, you guys have such a excellent momentum and are moving in warp speed, one parsec per second. :smiley: The light in the end of the tunnel is becoming brighter every second. This is a very happy day too celebrate this milestone. Keep on going super ants rock stars! :sunglasses:


#7

Great speaking @dugcampbell so good speaking off the dome. Production and sound quality were up, kudos!


#8

Very nice – keep up the great work


#9

Very nice video and explanation. All the major points ticked off. More of this sort of thing please! Keep the momentum going.


#10

Who can edit the Medium article? The link to the pdf has %29 at the end and people using the link are getting a 404 error.


#11

The offending URL “http://docs.maidsafe.net/Whitepapers/pdf/PARSEC.pdf)” The %29 is the closing parenthesis.


#12

Thanks @upstate @JPL - link now updated :slight_smile:


#13

This was great, very clear and concise. Well done Dug!


#14

As thrilled as everyone here :grinning:

Sorry to be that guy, but maybe I spotted a few small typos:

  1. The “where” may need to be removed in this sentence:

We have Dynamic Membership — a way in which where nodes are assigned to and re-assigned between different groups on the Network.

  1. A full stop is missing at the end of this sentence:

So if you want more info on any of these, start by downloading the SAFE Network Primer and getting stuck into the Forum

It could also be good to add an hyperlink on the word “Forum”.

  1. Missing full stops in the sentences:

the best performance of any asynchronous consensus algorithm in the world

If a network achieves ABFT, it means its nodes are guaranteed (mathematically) to reach consensus

  1. The s in forwards might need to be removed here:

We feel we’ve made a big step forwards with this mechanism

  1. A closing bracket is missing at the end of this sentence:

One final thing to be aware of. PARSEC is being released under a GPL v3 licence (with linking exception.

  1. Missing ‘is’ between ‘that’ and ‘designed’:

The Protocol for Asynchronous Reliable Secure and Efficient Consensus (PARSEC) is a consensus mechanism that designed to work on a global permissionless distributed Network.


#15

While the rest of the crypto world is patting each other on the back, proclaiming that blockchain is the greatest thing since sliced bread, you guys already have the sandwich made! It is so amazing seeing this unstoppable momentum, seeing the Safe net coming to life right before my very eyes. We are picking up speed with every turn. History is being made. On ward!


#16

Congratulations on being so careful with the text, Maidsafe is well taken care of!

May I suggest one thing too?,

… be aware of ( : ) instead of (.)

( : ) colon in portuguese means explanation ahead, whilst (.) fullstop separates ideas…

English is not my language…excuse my interference…


#17

Morning! Thanks for these, great to have a community who are so dedicated. I have updated these now :slight_smile:


Pre-Dev-Update Thread! Yay! :D
#18

Congratulations Pierre, Fraser, Qi Ma; I’ve been following development and have been using the example for a while to write this post. Really cool seeing this development happening out in the open and so actively and professionally.

The RFC and whitepaper explained parsec by starting with the fundamental building blocks and then combining them into the final result. In contrast, this post looks only at the high-level output of the algorithm and then picks out interesting details to investigate so we can better understand the inner workings of the algorithm from the top down.

Running the example simulation of parsec (thanks Fraser), there are some interesting talking points. Mostly I just wanted to explore the example so here it is. Hopefully it provokes some discussion and experiments.

Brief Description

The example creates a simulation with a specific number of undecided network events (eg vaults joining, departing etc) and a specific number of peers who must reach consensus on which events are genuine and their order.

In this simulation the term ‘round’ is used a lot and it means ‘a set of communications’ (ie gossips), as the comment in source code explains:

[In this round] Each peer will send a request and handle the corresponding response. For each peer, there is also a chance that they will vote for one of the transactions if they haven’t already done so.

Peers each vote for a random network event (ie declare they think that event is genuine) roughly every once every three rounds. In this simulation there are no malicious events to deal with or adversarial peers.

In each round every peer also engages in gossip to progress their current view of the overall voting.

I think the frequency of casting new votes is critical to the efficiency of the simulation, and in this example the average of one vote every 3 rounds is what dominates all the following results. In real life votes would be cast immediately upon validation, so this simulation is artificially slow in reaching consensus. But it gives interesting insights into the algorithm anyhow.

Initial Conditions

The following observations are from running the example with these settings:

cargo run --example=basic --features=dump-graphs -- --peers=5 --events=10
Using RNG seed: Some([3046582725, 1303372263, 4262207032, 2761586907])

First Partially Stable Block

Is ‘partially stable block’ the right phrase to use here? There’s a lot of definitions in RFC-0049 PARSEC Definitions but I wasn’t sure how to label the state when a block is stable in some peers but not all peers.

Gossip Round 011
================
Votes:
  Alice: [hN1C4, Qv0uw, DbyK2, sYBgs, R79u1, SiiUl, 33aLa]
  Bob:   [Qv0uw, sYBgs, hN1C4, gV9OD, 33aLa, DbyK2]
  Carol: [Qv0uw, 33aLa, R79u1, tbIMU, SiiUl, gV9OD]
  Dave:  [Qv0uw, hN1C4, DbyK2, gV9OD, R79u1]
  Eric:  [YvM0O, 33aLa, tbIMU, sYBgs, gV9OD]
Stable Blocks:
  Alice: []
  Bob:   []
  Carol: []
  Dave:  []
  Eric:  [Qv0uw]

Each client has between 5 and 7 votes for blocks that are not stable at this point. This is interesting because it gives some indication of the ‘uncertainty’ and how much ‘available but undecided territory’ there may be to manage in real life. I think in real life it will depend on the rate of new network events vs gossip rate, but it’s good to see there isn’t too much ‘ambiguous’ state needing to be managed.

Why does Eric have stable block Qv0uw but not have a vote for it? It’s not until seven rounds later in Round 018 that Eric has a vote for this block. The block as seen by Eric must have a supermajority of votes by other peers, so maybe Eric’s vote is unimportant regarding the stability of the block from Eric’s perspective. The idea of ‘perspective of each peer’ and how it may differ between peers is an important one.

First Fully Stable Block

Gossip Round 013
================
Votes:
  Alice: [hN1C4, Qv0uw, DbyK2, sYBgs, R79u1, SiiUl, 33aLa, YvM0O, gV9OD]
  Bob:   [Qv0uw, sYBgs, hN1C4, gV9OD, 33aLa, DbyK2, tbIMU]
  Carol: [Qv0uw, 33aLa, R79u1, tbIMU, SiiUl, gV9OD]
  Dave:  [Qv0uw, hN1C4, DbyK2, gV9OD, R79u1, 33aLa]
  Eric:  [YvM0O, 33aLa, tbIMU, sYBgs, gV9OD, hN1C4]
Stable Blocks:
  Alice: [Qv0uw]
  Bob:   [Qv0uw]
  Carol: [Qv0uw]
  Dave:  [Qv0uw]
  Eric:  [Qv0uw]

Two rounds later all nodes have one stable block. In the intervening Round 012 there are 3 nodes with stable blocks. Round 013 is the first one where all nodes have a stable block.

Additional Stable Blocks

Gossip Round 018
================
Votes:
  Alice: [hN1C4, Qv0uw, DbyK2, sYBgs, R79u1, SiiUl, 33aLa, YvM0O, gV9OD]
  Bob:   [Qv0uw, sYBgs, hN1C4, gV9OD, 33aLa, DbyK2, tbIMU, YvM0O, SiiUl]
  Carol: [Qv0uw, 33aLa, R79u1, tbIMU, SiiUl, gV9OD, hN1C4, YvM0O]
  Dave:  [Qv0uw, hN1C4, DbyK2, gV9OD, R79u1, 33aLa, sYBgs, tbIMU, SiiUl, YvM0O]
  Eric:  [YvM0O, 33aLa, tbIMU, sYBgs, gV9OD, hN1C4, SiiUl, Qv0uw]
Stable Blocks:
  Alice: [Qv0uw, 33aLa, gV9OD, hN1C4]
  Bob:   [Qv0uw]
  Carol: [Qv0uw]
  Dave:  [Qv0uw]
  Eric:  [Qv0uw]

The stable blocks don’t change for another 5 rounds, but in Round 018 Alice adds 3 stable blocks all at once. Then in the next round, Round 019, all the other nodes do too. This is a sudden increase in stable blocks, which is different to the idea of blockchain where each block generally is added sequentially one at a time.

It also means the concept of blockchain orphans is not directly applicable to the stable block list. It’s interesting to see the difference to blockchain and there’s a lot of work ahead to build a new vernacular around the behaviour of parsec blocks. Discussions will need to both pull from existing blockchain language and at the same time push away from blockchain ideas. It’s going to be interesting seeing that unfold.

Final Outcome

Gossip Round 026
================
Votes:
  Alice: [hN1C4, Qv0uw, DbyK2, sYBgs, R79u1, SiiUl, 33aLa, YvM0O, gV9OD, tbIMU]
  Bob:   [Qv0uw, sYBgs, hN1C4, gV9OD, 33aLa, DbyK2, tbIMU, YvM0O, SiiUl, R79u1]
  Carol: [Qv0uw, 33aLa, R79u1, tbIMU, SiiUl, gV9OD, hN1C4, YvM0O, sYBgs, DbyK2]
  Dave:  [Qv0uw, hN1C4, DbyK2, gV9OD, R79u1, 33aLa, sYBgs, tbIMU, SiiUl, YvM0O]
  Eric:  [YvM0O, 33aLa, tbIMU, sYBgs, gV9OD, hN1C4, SiiUl, Qv0uw, R79u1, DbyK2]
Stable Blocks:
  Alice: [Qv0uw, 33aLa, gV9OD, hN1C4, sYBgs, tbIMU, SiiUl, YvM0O, DbyK2, R79u1]
  Bob:   [Qv0uw, 33aLa, gV9OD, hN1C4, sYBgs, tbIMU, SiiUl, YvM0O, DbyK2, R79u1]
  Carol: [Qv0uw, 33aLa, gV9OD, hN1C4, sYBgs, tbIMU, SiiUl, YvM0O, DbyK2, R79u1]
  Dave:  [Qv0uw, 33aLa, gV9OD, hN1C4, sYBgs, tbIMU, SiiUl, YvM0O, DbyK2, R79u1]
  Eric:  [Qv0uw, 33aLa, gV9OD, hN1C4, sYBgs, tbIMU, SiiUl, YvM0O, DbyK2, R79u1]

The simulation takes 26 rounds to resolve and all nodes have all ten blocks stable and in the same order as each other. Very cool!

Scalability

When the number of events increases or the number of nodes increases, does the algorithm get slower or faster or stay the same?

For all these tests the seed used is --seed=1,1,1,1 where 1 is the test number.

Scaling Events

The prior test took an average of 2.6 rounds per stable block.

The tests are run with the following command:

cargo run --example=basic --features=dump-graphs -- --peers=5 --events=E --seed=N,N,N,N

and results in the average number of rounds per stable block (RPSB):

Peers Events Test1   2   3   4   5 | AvgRPSB
    5     10    40  40  33  27  38 |     3.6
    5     20    77  75  69  60  64 |     3.4
    5     40   105 120 121 142 126 |     3.1
    5    100   272 300 296 306 287 |     2.9

Having many blocks in limbo seems to improve the efficiency of each round, but is pretty-much about 3 rounds to create a stable block (for 5 peers). There’s a lot of room for further exploration here.

It’s worth pointing out that removing the artificial constraint of one vote every three rounds and replacing it with a vote every single round gave much faster consensus (~1.1 rounds per stable block instead of ~3 rounds).

Scaling Peers

Peers Events Test1   2   3   4   5 | AvgRPSB
    5     10    40  40  33  27  38 |    3.56
   10     10    42  34  33  38  35 |    3.64
   20     10    37  37  37  39  38 |    3.76

There seems to be a small increase in the number of rounds per stable block as the number of peers increases. In SAFE this effect should be virtually unobservable since there’s a fairly low number of peers in each section. Again it’s around an average of 3 rounds to form each stable block.

Performance

In the Upcoming features there’s an item “Benchmark and optimise the code” so it’s not really something I will do in detail here just yet, but the average time per stable block on a stock 2018 intel i7-7700 @ 3.6 GHz is 1.6s (5 peers 10 events).

This is not a good indicator of real world performance for many reasons, but it’s at least some sort of comparison point for the future. I’m really excited to see what maidsafe do in this area. I’ve already noticed a bit of behaviour that indicates ‘pre-optimised-code’ so I know real life will be much more exciting than this simulation.

Summary

Stable blocks are formed reliably regardless of how many peers or how many events are involved. The rate of consensus is slower than expected in real life because of the artificial delay in casting votes, but is also very fast due to the efficiency of the gossip algorithm.

Once again, congratulations maidsafe for all the work on this awesome algorithm.


#19

I always appreciate your posts and the way you show the numbers. It just seems to click with the way I think and learn. Thank you.


#20

Agreed - I wish I had properly read this before I started experimenting. Would have saved me a fair bit of head scratching time.