Module 5.1.1Cellular Consensus

In Cellular Consensus the voting process is modelled as a cellular automaton, where nodes can be thought of as cells that monitor the states of their neighbors and adjust their opinion accordingly. The actual consensus algorithm is extremely simple and can be summarized in 5 lines of code:

If NumberOfNeighborsPreferringTransaction(tx) > NumberOfNeighbors / 2 {
    PreferTransaction(tx)
} else {
    DislikeTransaction(tx)
}

This describes a mechanism where nodes adopt the majority opinion of their neighbors, liking or disliking a transaction based on that majority.

It is extremely fast and robust. The following animation depicts a simulation of 10,000 nodes reaching a consensus in the presence of 128 conflicting transactions (different colors represent different transactions):

In this example, the network reaches consensus in a matter of seconds.

Increasing the number of nodes affects the time taken for transactions to propagate in the network, but does not affect the time to reach a consensus. Decisions are made locally and in parallel no matter how many nodes participate in the network.

The fact that votes are always exchanged with the same neighbors can represent a route of attack. We add security by incorporating mana-based reputation in the peering process: nodes will prefer neighbors with a similar reputation. This makes it expensive for attackers to even be considered as neighbors, and adds another incentive for nodes to attain a high reputation. The network becomes increasingly secure as the amount of mana possessed by honest nodes grows naturally over time.

Gossip about Opinion: The organism’s immune system

Treating nodes as cells of a living organism enables us to implement an ‘immune system’. This secures the network against attack by forcing participants to play by the rules, and provides a greater protection than traditional measures like Sybil protection. Since all neighbors are selected randomly the process by which Shimmer reaches a consensus is highly probabilistic. But at node level, the Cellular Consensus is deterministic. This allows us to verify a node’s behavior if we know the opinion of its neighbors. Bad actors that violate the rules can therefore be detected (as demonstrated below) and evicted immediately, by any of their neighbors.

This idea can be formalized in the following protocol, which we call “Gossip about Opinion”:

  • At regular intervals, every node issues a “heartbeat” message to its neighbors. This contains its current opinion and the reason why it came to that opinion, i.e. its neighbors’ opinions in the previous round.
  • To compress the amount of exchanged data only the difference between consecutive heartbeats is sent i.e. only those transaction hashes whose ‘liked’ status has changed.
  • A node signs its heartbeat messages and opinions to guarantee authenticity.

This heartbeat serves multiple purposes:

  • It forces nodes to make regular statements and remain active members of the network.
  • It is used to synchronize opinions between neighbors, allowing nodes to update their own opinion according to the previously described rules, without the need to proactively query other nodes.
  • It allows nodes to verify that their neighbors are honest - those that violate the protocol by changing their opinion can be evicted from the network immediately. Since the messages are signed, misbehaviour can be proven by tracing malicious messages back to the nodes that issued them.

This approach has a number of compelling features that have not been seen in any other permissionless consensus mechanism: its asynchronous nature, the simplicity of its implementation, the efficiency of its message overhead, the speed at which it reaches consensus, and its attack resilience.

While emergent phenomena are very common in biological systems and have proven to work well in practice, it is extremely difficult to model them mathematically due to their inherently chaotic and complex nature. The approach’s biggest drawback is therefore the complexity of formalizing its scientific proofs. It would be necessary to thoroughly study Cellular Consensus in a testnet environment before it could be deployed on the mainnet.

Parasite-chain attacksA double spend attack on the Tangle. Here an attacker attempts to undo a transaction by building an alternative Tangle in which the funds were not spent. They then try to get the majority of the network to accept the alternative Tangle as the legitimate one.