CLIQUE ALGORITHM — PROOF OF AUTHORITY CONSENSUS
PERMISSIONED BLOCKCHAIN
Before moving on, is necessary to introduce the concept of permissioned or consortium blockchain as a particular kind of blockchain where the participants of the systems need a sort of permission in order to join the network. Imagine this as a set of known companies that are building up a closed blockchain environment in order to exchange assets among them. We can’t let anyone enter in our network since our market and environment is closed and must be kept under control.
This is a little bit against the openness and anonymity of the blockchain movement but as often happen with technology, this is adjusted in order to fit for business and enterprises purposes.
The key thing of this closed systems, is that the anonimity and the decentralisation is relaxed because each node of the system is well known and is well localized, but this is not that bad. The governance factor of the system for example is really high since a closed number of parties can vote and handle the decision about the system, where this unfortunately can be totally different in a public environment where community is virtual and not so defined.
CONSENSUS
If the properties and the structure of the system change in a closed environment, the consensus algorithm changes too. As a matter of fact, there is no need to provide resiliency against Sybil Attacks or DDos nor to provide a strong anonimity-driven algorithm such as PoW or PoS.
This is why in closed blockchain systems, a new consensus algorithm has been defined, the Proof of Authority (PoA).
PROOF OF AUTHORITY (PoA)
Here, a predefined set of known parties, called authorities keeps and maintains the blockchain acting as a sort of “miners” or validators (sewers in this case) so at any point in time the set of validators is defined and public and a not random based algorithm can be used in order to choose the next validator or the leader who is going to propagate his block.
This lead in having systems where a simple leader rotating algorithm can be performed among the whole set of authorities at any point in time, where, dividing time into steps, each step has a single leader who will be in charge of propagating the block for that step.
Source
The topic of today is on focusing on one of this PoA algorithm that actually is the common one, the Clique algorithm, which is used by default by the go-lang ethereum client, Geth.
A particular focus will be spent on the BFT or Byzantine Fault Tolerant property of this algorithm which is one of the most important criteria of a consensus algorithm.
Briefly, a consensus algorithm is said to be BFT if it is designed in order to functioning and return a correct value even in the presence of a certain number of Byzantine users inside the system, where Byzantine means users that can be corrupted, malicious, or faulty, in one word, users which you can’t rely on. This kinds of algorithms are slower but more robust compared to the easiest ones FT (Fault Tolerant) which basically might not return the correct value in presence of even a single byzantine node on the system.
The most famous BFT algorithm is called PBFT, that is common to be a little bit slower since it requires 3 messages for each step/round before agreeing on a single value, but we will see that even Clique is BFT and is much faster.
CLIQUE
First of all, Clique is embedded inside Geth client for Ethereum, so it is designed in order to follow the mechanisms of the Ethereum blockchain. For example the Clique is based on epochs, where each epoch is defined by a special sequence of blocks and every time a new epoch starts a special TRANSITION BLOCK is broadcasted containing mainly the set of authorities who are going to participate in consensus for that epoch.
Step and Leader are calculated following a certain formula something that basically use the modulo operator among the number of authorities in order to have an unique leader for each round.
The Byzantine flavour of the algorithm comes now into account, since in Clique for each step there is not just one “leader” which might be byzantine and hence unreliable.
So for each step there is no just one leader but few authorities are allowed to publish and broadcast too their blocks together with the leader of that particular round. The leader formula allows each authority to send a block only every (N/2 +1) blocks so for each step N-(N/2+1) authorities are allowed to propose a block. This, again, is designed in order to backup the leader if it might be faulty/malicious, sending for each round at least one block.
I know, this can lead to forks since more than one block can be propagated per round, but fear not, the algorithm is designed in order to cooperate with the GHOST protocol of Ethereum chain where the canonical path of the chain is the one with the highest summed score.
Note that Clique assigns for each round a score to each block, where the leader has the highest score of the round and if two blocks are propagated in a single round, the one with the lowest score will be discarded.
In order to better understand how does this work and why this is byzantine tolerant we have to define that for each step, N-(N/2+1) authorities (leader counted) are allowed to propose their blocks, but among them, everyone except the leader will propagate its block only after a random time delay in order to avoid deterministic or sistematics forks.
So if the leader is up, it broadcast its block with the highest score, else, one among the round selected authorities will shoot its block, likely the one with the lowest random time delay.
PERFORMANCES
For each round, there is at most N-(N/2+1) blocks propagated (in the worst case scenario) or just one message by the leader in the best case scenario. The blocks received by nodes are automatically committed so the latency is 1 and they eventually will adjust the main path of their local blockchain if an high scored block comes up.
So this is not properly BFT but is much faster and provides an eventual consistency mechanism thanks to the GHOST PROTOCOL.
Sources:
https://eprints.soton.ac.uk/415083/2/itasec18_main.pdf
https://github.com/ethereum/EIPs/issues/225
https://medium.com/poa-network/proof-of-authority-consensus-model-with-identity-at-stake-d5bd15463256
