Project Spotlight: Maidsafe and PARSEC Part 2

This is Part 2 in a 3 part series on PARSEC, the Protocol for Asynchronous, Reliable, Secure and Efficient Consensus as designed by Maidsafe. Part 1 can be found here. This was first published on FlatOutCrypto.

Part 1 looked at what PARSEC was attempting to achieve and why, as well as defining a number of key terms. Part 2 will look at a key part of PARSEC — how information is shared across the network.

Gossiping and Asynchronous Binary Agreements

Two major concepts underpinning PARSEC are the Gossip Protocol (GP) as a means of transmitting information and Asynchronous Binary Byzantine Agreement. These two concepts together allow the PARSEC network to reach an irreversible consensus at a point in time, something that a blockchain can never achieve (whilst it can come close to 100% certainty, the blockchain can be rolled back with sufficient hashpower — although the further back to go, the more power required). It also enables the network to do so with a greater throughput than blockchain.

The Gossip Protocol

You can find a run through of a GP in my look at Virtual Voting and Hashgraph here, but it is essentially a way that nodes on a network can find out information (network events) from other nodes. In contrast to PoW, where transactions are created and then get bundled up into one block which the miners then validate, a GP allows transactions to constantly be occurring nonstop and for said transactions to be confirmed in near instant speeds. It achieves this as follows:

1. Nodes gossip by selecting another node at random to transmit event history to (the number of nodes they select varies by the implementation)
2. The receiving node adds any new information it has not yet seen to its own ledger history
3. When a node receives a request, it creates a new event and sends a response back. This creates a verifiable datalog called a gossip graph. Each gossip graph contains (except in specific circumstances):
4. The data being transmitted
5. The self-parent (the hash of another gossip event created by the same node)
6. The other-parent (a hash of another gossip event created by a different node)
7. The Cause for creation which can either be a Request for information, a Response to another node’s request, or an Observation. An observation is when a node creates a gossip event to record an observation that the node made themselves.
8. Creator ID (public key)
9. Signature — signing the above information
10. The sum of this information is known as a gossip event. Every gossip event gets added to each nodes gossip graph. Think of the gossip graph as a collation of all the different gossip events received
11. Nodes ‘virtually’ vote on observations seen. Each node analyses the gossip graph and if they believe that it has a record of an event which should go next in the chain then it casts a vote as such
12. A node then counts votes for an event and decides which event should be the next one in order
13. Once a set number of nodes (a supermajority) have voted for an event then the block is considered valid and ready to enter the consensus protocol to reach consensus

Instead of a transaction being submitted for approval and a period elapsing whilst it is confirmed, this structure allows for a transaction to spread across the network via this gossip. While not all members will have the exact version of new events at all times, they will eventually attain the same set of data by constantly gossiping amongst themselves until they all match. This fits in with our previously stated definition of an asynchronous network.

This method allows nodes to establish event relationships/history. Again, to simplify:

• Node A sends Transaction 1 to Node B
• Node B relays the receipt of T1 to Node C, who in turn relays to Node D, E and F (for this example let us assume they are all observers, a term I will detail shortly)
• Node A then sends Transaction 2 to Node F, who in turn relays to Node B, G and H
• Despite still not knowing about T1, Node G and H will be able to know that T2 came after T1 because Node B saw both T1 and T2 and will have stored that event order in its ledger

This happens on a grand (and fast) scale, with nodes constantly requesting information (sync requests) from other nodes and then determining if any new blocks should be added. The self-parent and other-parent are what prevent tampering (because they are signed and related to other gossip events)

GP’s are used in multiple forms of computing, and are well suited to the large distributed decentralised networks DLTs comprise. They are useful because they are:

• Fast and scalable — Even if there are millions of nodes they can continue to be effective, as each node only gossips with a small selection of other nodes and so the network does not get slowed down by a need for all nodes to communicate with all other nodes)
• Decentralised — There are no leaders or trusted parties determining what gossip being spread is correct; it is the responsibility of all nodes on the network to generate and spread said information
• Fault tolerant — Malicious nodes cannot stop a transaction from being processed as it is broadcast to nodes across the network
• Energy efficient — Nodes don’t compete in the same way miners do in PoW — instead all nodes are producing all events at the same time, so no events are discarded

How do we calculate the order using the Gossip Protocol?

The GP is how information spreads across the network — but how do we make sure it is correct, in the right order and that malicious actors aren’t simply verifying incorrect events quicker than honest actors can to manipulate the order? This is breaking down points 5–7 from the previous section.

It gets a little dense here as there are a lot of terms to define so I’m going to break it down into chunks:

“To be able to order blocks, we need first to have some blocks that can be ordered.”

Self-explanatory.

“As mentioned above, the gossip events may contain votes for network events. A gossip event which sees events created by a supermajority of nodes that contain votes for a given network event is said to see a valid block, and we will call such gossip events block-votes.”

Supermajority = more than 2/3 of nodes. So essentially, over 2/3 of the network must vote for a given gossip event for it to be considered valid.

“The first gossip event which strongly sees block-votes created by a supermajority of nodes is said to be an observer. The block-votes don’t need to see the same valid block — in fact, it is the case when they see different valid blocks that is the most interesting. However, they do have to only refer to blocks that haven’t been appended to the ordered set yet.”

I find Rajarshi Mitra’s definition of ‘strongly sees’ and the illustrative diagrams Leemon Baird uses in Hashgraph Consensus easier to digest than the one in the whitepaper. They are referring to Hashgraph but, terminology aside, it is the same:

1. There must be multiple routing points that go from a gossip event to the other gossip event in question
2. The path needs to pass a supermajority (over 2/3)

So there has to be multiple routing points to get there e.g. Gossip Event A is seen by Gossip Event B and C. Gossip Event B and C are seen by Gossip Event D. Gossip Event D strongly sees Gossip Event A as it has two routes to get there (through either B or C). These multiple routes must go through > 2/3 of the members.

“An observer implicitly carries a list of N meta-votes. Every meta-vote is just a binary value denoting whether a corresponding node’s block-vote is to be taken into account when determining the order. An observer meta-vote votes true on a node if it can strongly see a block-vote by that node.”

A meta vote is when a node answers the question “Does my oldest observer (observer having been defined above) strongly see an interesting gossip event created by the node I am looking at”. The binary value is true or false.

“Every node is being meta-voted on, hence there are N meta-votes, and since an observer strongly sees a supermajority of block-votes, by definition, at least 2/3 of them are true.”

Each vote happens almost instantly, but the voting process is endless.

“Meta-votes reduce the problem of Byzantine agreement about the order to that of binary Byzantine agreement, which has been solved previously[2].”

This takes a little explanation.

The difference between Byzantine agreement and binary Byzantine agreement is that it reduces the problem from any events to just a binary one (e.g. 0 or 1, true or false). This is far simpler, because it becomes a 50/50 decision.

It does this because meta-votes change the question to a true/false state — it is simply that it is true if the oldest observer has strongly seen an interesting gossip event created by the node I am looking at, or false if not.

Once a true vote is cast, it means that all honest nodes will also eventually be guaranteed to strongly see the gossip event.

“The algorithm described in [2] has some shortcomings, though, the most significant of which is the need for a common coin, a primitive which may require synchronicity and/or a trusted third party for efficient creation or setup. The algorithm presented here works without such a requirement.”

This refers to the concrete coin mentioned in the introduction, which I will come onto now in Part 3.

Disclaimer: I do not hold MAID and have no plans to buy. If you enjoyed this article then please follow me @FlatOutCrypto