Classification of Consensus Protocols

From Consensus Wiki

The consensus classification proposed here applies specifically to crypto-networks and blockchain technology.

This classification uses known protocol models, network characteristics and software design criteria.
A clear classification may help better understand blockchain technology and its future direction, as researchers and companies are engaged in solving its known performance problems (scalability, throughput, cost and efficiency).

Performance criteria are not used for this consensus protocol classification. Network performance claims can be found on each individual network's site.

Basic Terminology

A blockchain network such as the Bitcoin network, is a set of computers communicating through the Internet for the purpose of maintaining a verifiable and immutable copy of the same blocks of data (the blockchain) on their local memory. These computers are called the nodes (or full nodes) of the network.

The more specific term crypto-network indicates that its data is protected by encryption mechanisms both during transmission and when stored by the nodes.

A consensus protocol is that mechanism used to guarantee that exactly the same blockchain is replicated on each node of the network.

The blockchain is a sequence of identical blocks of information, replicated on each node of a particular network, protected against change by verifiable encoding mechanisms. Any type of information may be recorded on the blockchain, including simple currency transactions, smart securities or other application specific data.
Although the blockchain is a common concept, there are as many physical blockchains as there are networks. That is, each network maintains its own blockchain.

The security protocols are those mechanisms used to guarantee the security of the network, protecting it from malicious attacks or failures not handled by the communication network.

Consensus Protocols

As mentioned, the main objective is to maintain the same blockchain replica in all active full nodes. Consensus protocols include the functionality that determines the exact composition of a block of transactions.

Each transaction must be received at least once by each node, but the resulting blocks of transactions may be assembled differently by each node.

A Bit of Theory

The Byzantine Generals problem and the theory behind fault tolerant networks (e.g. CAP theorem) can be found in the literature. The protocols that have been proposed in practice make use of limitations and assumptions that make these protocol work in specific real environments, without necessarily providing availability of the same information to all nodes at all times.

For example, some nodes may lose information, because they are too busy, too slow to receive or because of other reasons, and may have to re-synchronize at a later time.

Even allowing for such temporary inconsistencies in data availability and practical means for information recovery, consensus protocols require the following attributes, to maintain a consistent blockchain:

  1. Termination: Every correct active full node eventually must decide what is the composition of the next block, or sequence of blocks, to be added to the blockchain.
  2. Convergence: A timeout can be set so that an arbitrary percentage of the correct active full nodes terminate the consensus process within the allotted period.
  3. Agreement: No two correct active full nodes may decide to add a different block, or sequence of blocks, to the current blockchain.
  4. Validity/Integrity: If the majority of the correct active full nodes agree that a certain block B is the next valid block in the blockchain sequence, then no other node can decide to add a block different from B.

De-centralized networks generally use a leader-based consensus mechanism (Raft/Paxos model), where one leader node is elected, selected, or randomly chosen according to some criteria or proof. The leader node assembles and broadcasts the block to every other node of the network. Given the asynchronous nature of these protocols, they create forks. Thus, the guarantee that each node has a stable replica of the blockchain can be given only after a certain time has elapsed.

According to the attributes mentioned above and more specifically the block Validity/Integrity requirement, leader-based consensus protocols cannot guarantee the integrity of the blockchain without trusting the current leader node.
While all full nodes participate in the election, selection or competition to become the leader, they do not participate in the agreement process for the composition of the block itself.

For example, with the Proof of Work (PoW) protocol, although the majority of the full nodes may assemble a block A, these nodes are never asked to agree to, and do not participate in, the composition of the block that is eventually added to the blockchain by the leader, which is likely a different block B.

The requirement that every other node must use the block prepared by one leader, independently or even in opposition to the majority opinion, cannot be classified as a form of consensus on block composition, but only as an agreement on the mechanism to select a leader.

The implication is that leader-based protocols require to place a certain amount of trust on a single node, even though this node is required to prove its processing power or some other credential.

Because of their model and their tendency towards centralization, most leader-based protocols do not achieve the goal of providing peer-to-peer interactions among users without trusted intermediaries. In addition public networks using leader-based protocols have scalability, throughput and cost problems.

However, the classification presented below includes leader-based protocols to conform to the common use of the word consensus by established networks (Bitcoin[1], Ethereum[2], EOS[3], Tezos[4], NEO[5], Stellar[6], etc.).

In contrast, peer-majority consensus protocols reach a high threshold majority agreement among peers on the actual composition of the block and guarantee that the same block is stored on every active node without broadcasting blocks. With these protocols there is no need to trust a leader node, as they do not require special classes of intermediary nodes (e.g., miners or verifiers).

Security Protocols

Generally security protocols and mechanisms are lumped in with the consensus protocols, but they should be designed, analyzed and classified separately. Security mechanisms are needed for protecting the network, not just the blockchain.
Malicious attacks may cause no apparent effect on the blockchain or on the consensus protocol.

For example:

  • A DoS attack may not influence the composition of the blockchain, but it may disrupt the network and its users in other ways.
  • A majority attacks to the network may produce a new block that is correctly obtained through consensus, even though the attacker could reap the reward of his unethical action.
  • An attacker may use a stolen private key to generate a valid transaction that cannot be detected as invalid by the consensus protocol.

The failure of a crypto-network to solve all security problems leads to open gaps that can be exploited by hackers not only at the network level (51% attack, DoS attacks, Sybil attacks, currency generation, transfer or destruction), but also by attacking the software of any application running on the network.

Classification of Consensus Protocols

Classification by Network Topology

star networkCentralized

In a centralized system or star-network that implemented a blockchain, no consensus is needed: The central system or node dictates the composition of each block.

 

De-centralizeddecebtralized network

In a decentralized network, the consensus mechanism may involve a subset of the network nodes (full nodes). Blocks may then be propagated to other nodes.

 

Distributeddistributed network

In a distributed network all nodes perform the same role. The consensus protocol involves all nodes of the network. The protocol cannot rely on intermediary nodes, special nodes or a leader node. The agreement is reached by cooperation among peer nodes, and no broadcasting of blocks is required.

 

Other Possible Classifications Criteria

Consensus protocols can also be classified according to other characteristics:

Blockchain-based or not

The ability to handle consensus about large blocks of transactions, instead of individual transactions, is one of the blockchain innovations that increases efficiency and reduces traffic.

However, some proposed consensus protocols are based on handling transactions individually, and not in blocks. Examples of consensus protocols not based on the blockchain concept are Directed Acyclic Graph (DAG) solutions (e.g.: HashGraph[7], AVALANCHE[8]).

Peer-majority or Leader-based

Peer-majority consensus protocols determine the block composition based on the block composition agreed by the majority of the nodes.

Examples of peer-majority consensus protocols are MARPLE[9] and AVALANCHE.

Broadcast based or not

A consensus can be reached by broadcasting information from node to node until all nodes have the same information (Gossip model). Examples are: AVALANCHE, Hashgraph.

Synchronous or asynchronous

Leader-based mechanisms are generally asynchronous, as the problem of deciding on a leader may introduce asynchronisms and forks (i.e. a leader is proposed and a block is distributed by one leader, but neither the leader nor the block can be confirmed until later on).

With synchronous protocols, the proposed agreement is reached by requiring a decision from all nodes at a certain specific time. No forks are created. At any one time all active nodes hold exactly the same blockchain replica.

Examples of synchronous protocols are distributed stochastic protocols (e.g., MARPLE).

Recursive or not

In recursive protocols, the proposed agreement is reached by propagating a proposed agreement recursively until a certain threshold of agreement is reached.

Stochastic or not

A protocol is stochastic when communication among nodes can happen dynamically, without a pre-defined structure or reference to their role or physical location. This property is found in currently proposed peer-majority protocols.

Most networks require specific reference to Internet URL or IP addresses, especially, but not exclusively, when the client software is downloaded from a trusted site and during node initialization.

Network Control Criteria

Public or Private

A network is public when it is not owned or operated by a particular entity or corporation. Nodes or pool of nodes may be owned by corporations, but this does not give a particular entity or partnership control over the network. When large pools of nodes of a public network are owned by a corporation, this information must be fully disclosed, or the network may be deemed as owned by a private consortium or private.

Self Governing or Federated

A network is self governing when its nodes are independent or when the network is governed through a self-regulating mechanism or poll.

A network is federated when its nodes can join the network only if authorized by some pre-defined, entity, authority or private consortium. Federated networks may use proprietary mechanisms and not necessarily consensus mechanisms to maintain their de-centralized ledger.

Un-permissioned or Permissioned

A network is un-permissioned when it is not owned by a company or a private consortium, and its nodes can participate to the verification of transactions, block assembly and blockchain maintenance without authorization by any entity or authority or other pre-determined criteria.

Classification Tables

Consensus table

Network table

See also

References