A fresh attempt for Classification

Part 1 — A Taxonomy of protocols

This article is the first part of the bigger story about Distributed Decentralized Systems. We will publish a new article once a week following the order from Table of Content.

Table of Content:

I. A Taxonomy of Protocols (Part 1)

1. Motivation

2. Scope and Context

3. The Overall Landscape

II. The four Dimensions for the taxonomy

1. Consensus Protocols (Part 2)

2. Sybil Attack Prevention Mechanisms (Part 3)

3. Data Structures in Distributed Systems (Part 4)

4. Energy Consumption (Part 5)

III. The 5th Discipline: Decentralization (Part 6)

IV. Other Important Classification Criteria (Part 7)

Designing a distributed system is always about trade-offs on transaction speed, scalability, security, energy efficiency …

Ambitions to decentralize a distributed system will add enormous complexity — ultimately leading to the greater good!

Author: Ahmet YALÇIN, May 26th, 2019 — Berlin

Acknowledgments for critical review and suggestions by
Dmitrii Zhelezov, PhD & Prof. Bhaskar Krishnamachari, PhD

@HelixFoundation — All rights reserved

I — A Taxonomy of Protocols

I — 1. Motivation

Although basically just two or three families of principally different working consensus protocols in Distributed Decentralized Systems (DDS) do exist, and just a few Sybil attack prevention mechanisms are practically considerable, there are probably over 100+ variants of different implementations in place. “Blockchain Space” is a moving target with every day evolving new projects. In addition, the ongoing R&D work in this space around the globe makes various projects and products less comparable and difficult to classify, even for experts. A systematic analysis, fair comparison and rigorous evaluation of the different design features of DDS along with their implications in performance and applications is becoming a real challenge.

The intention of this analysis is to understand the work related to a new protocol called HelixMesh and to create a basis for positioning the HelixMesh [see Helix 2019] in the DDS Landscape. Here, we focus on creating an overall general picture — a holistic and pragmatic view. With this ambition of a high-level classification of various protocols and related projects, we also hope to make the competitive landscape visible. By plotting their relative positions and by indicating their perceived added-value within the overall ecosystem, visibility can stimulate a further comparative discussion among the various projects and the community.

– Contribution

First of all, this is not a scientific paper. Here, in our attempt to show the “big picture” we benefited from direct findings of decades of research in consensus science [e.g., Lamport 1978, 1982, 2001; Castro & Liskov, 2002] and comprehensive recent studies on DDS [e.g., Pass & Shi, 2017] as well as meta-analyses of protocols [e.g., Ballandies, Dapp & Pournaras, 2018]. Our article, in the form of a simple explanatory document aimed at providing a graphical overview using a new taxonomy, provides a classification of over 25 distributed ledger systems. In our work, we tried to relate to the “most important” projects.

Nevertheless, we do not claim to cover all the relevant criteria in our analysis but rather to focus on the key aspects for the sake of simplicity. In comparison to the complex scientific related work, the taxonomy proposed here provides a rather practical overview. We use four dimensions for the classification: 1) Consensus 2) Sybil prevention 3) Data Structure 4) Energy Consumption, (i.e. environmental footprint)

I — 2. Scope and Context

In this analysis, there is no claim of a novel scientific contribution. We only provide a structured compilation from existing papers, accompanied by a graphical taxonomy (i.e., a landscape from a bird’s eye view) for the most known protocols and their corresponding projects. Although we reviewed several scientific articles and metanalyses of blockchain protocols during the last few months, our “pamphlet” is not meant to be exhaustive or complete. We are aware that there are many excellent papers which we have not referred to here. Our analysis contains a significant body of knowledge combining several extensive meta-analyses on the subject, a subtitle of our results could also be: An Attempt for a DDS Taxonomy based on Meta-analysis.

Most of the below-mentioned protocols (e.g., Avi, Blockmania, HelixMesh, Spectre, Phantom, Ghost, Fetch, Perlin, Tezos, even Ethereum Casper) are still under development and were not available as products at the time of this analysis (Q1 2019). Further, we would like to emphasize that our results are best described as a “probably correct approximation” than representing a fully verifiable broad analysis since many of these protocols/projects have moving targets or have expanded into new features.

For the scope and context of this document, here we are focusing on PUBLIC CHAIN protocols (both permissioned and permissionless) and not on PRIVATE CHAINS (like Hyperledger, Corda or Ripple). UseCases on protocols, dApps or other “simple cryptocurrency applications” are also not included in our analysis (e.g. we would consider the cryptocurrency DASH as being in this category).

– Conflict of Interest

The author is affiliated with Helix Cognitive Computing and the Helix Foundation. Regardless of this, for the purpose of this article, the author used only data collected from public (external) sources.

I — 3. The Overall Landscape

Helix versus other “Public Chains” — A Taxonomy based on a MetaAnalysis¹

Fig. Four-dimensional classification of protocols (link to the full-size image)

@Helix Foundation — All rights reserved

For additional comments of the above-mentioned protocols please refer to the Appendix

Appendix to the “Four-dimensional classification of protocols”

· Tendermint Core is a BFT protocol that can be best described as a variant of pBFT. In contrast to pBFT, where the client sends a new transaction directly to all nodes, the clients in Tendermint disseminate their transactions to the validating nodes using a gossip protocol. Tendermint’s most significant departure from pBFT is the continuous rotation of the leader. This should be compared to the expensive view change routine of pBFT which is used as a fallback [ https://github.com/tendermint/tendermint ].

· Thunderalla is Hybrid Consensus ( https://eprint.iacr.org/2016/917.pdf ), i.e. it uses BFT for choosing a block and a separate “slow” blockchain for selecting the committees. In other words, it uses the blockchain not to agree on transactions, but to agree on rotating committees which in turn execute permissioned consensus protocols to agree on transactions, proposed by the leader. The advantage here is that Thunderalla was considered being the most efficient BFT PoS framework ever in terms of liveness. Thunderalla is operating tandem, i.e. in PoW for recovery mechanism and PoS otherwise; and in both cases it uses the asynchronous pBFT. The beauty of Thunderalla lies in its simplicity, combining the responsiveness of an asynchronous algorithm, the decentralization of a blockchain, and the speed and throughput previously reserved for centralized systems [Pass & Shi].

· Following the Thunderalla paradigm, the key idea behind Thunder is to combine a “standard” blockchain, which we will refer to as the slow chain with an optimistic fast-path. The fast path is coordinated by a centralized entity referred to as the Accelerator. As longs as the Accelerator is not malicious and the network latency is low, transactions are quickly confirmed. Otherwise, the “slow’’ blockchain is used for recovery [Koticha, Z., (2018)].

· At dFinity, while first defined for a permissioned participation model, the consensus mechanism itself can be paired with any method of Sybil resistance — similar to Thunderalla — (e.g. proof-of-work or proof-of-stake) to create an open participation model. The dFinity blockchain uses a random beacon for leader selection and leader ranking. A “weight” is attributed to a chain based on the ranks of the leaders who propose the blocks in the chain, and that weight is used to select between competing chains [Timo Hanke, Mahnush Movahedi and Dominic Williams — dFinity Technology Overview Series Consensus System].

· Stellar (and of course Ripple) uses federated Byzantine agreement (FBA). FBA achieves robustness through quorum slices — individual trust decisions made by each node that together determine system-level quorums. Slices bind the system together much the way individual networks’ peering and transit decisions now unify the Internet. PoW has its famous 51% attacks. Stellar claims, that “you can flood the network with bad actors, and it doesn’t matter, as long as no-one includes them in their quorum sets”. FBA brings open membership and decentralized control to Byzantine agreement. Anyone can join. FBA determines quorums, or groups of nodes sufficient to reach an agreement, in a distributed way. Each node decides which others to trust. Different nodes don’t need to rely on the same combination of trusted participants to reach consensus. Stellar is a decentralized protocol, however, Ripple is not. Ripple is a private Blockchain. So, these two terms can be combined, private blockchains can be decentralized and public blockchains can be centralized. Ripple is currently private and centralized but moving towards private and decentralized [D. Mazieres — The Stellar Consensus Protocol: A Federated Model for Internet-level Consensus].

· Algorand — On How to elect Block Proposers and Committees: All users participate in the lottery and can win the ticket to become the block proposer or a ticket to be a member of the validating committee in round r. Every user runs its own “lottery machine” fueled with a public random seed and her/his private key. These lottery machines are verifiable random functions (VRF). They produce uniformly distributed random values and provide a non-interactive proof so that any other user knowing only the public key of the winning user can verify the outcome once the chosen lottery winner makes his ticket public. If the value of the ticket is close to some target value or threshold, this user can participate in proposing or validating blocks
[Comparison of PoS projects: Unbiased Leader Election https://blog.coinfabrik.com/comparison-of-pos-projects-unbiased-leader-election/ ].

· The Avalanche protocol is composed of four mechanisms which build upon each other and together make up the entire structural support of the DAG-based consensus tool. The four mechanisms described in the proposal are Slush, Snowflake, Snowball, and Avalanche. The network nodes sample random peers, and sufficiently many consistent consecutive queries signal a network-wide consensus. It is further amplified by the DAG structure with child transactions providing extra support for the “ancestors’’ [ https://btcmanager.com/avalanche-protocolnew-age-consensus/ ].

· Fetch’s useful proof-of-work will involve the packaging of general-purpose computing problems into PoW packages. These problems allow processing nodes with less computational power to occasionally earn block rewards. Verification of the subproblems will be carried out by nodes that “lost” the race for solving the problem with some smaller reward provided for these verification steps. Fetch will also incorporate tunable PoW difficulties in relation to transaction fee so that nodes with low computational power can earn rewards by registering low-value transactions into the ledger. This distributed computing platform will be used to train machine learning (ML) algorithms and will ensure the integrity of the network by, for example, assessing trust in the validity of transactions and the ledger itself [ https://fetch.ai/uploads/technical-introduction.pdf ].

· PHANTOM is a PoW based protocol for a permissionless ledger that generalizes Nakamoto’s blockchain to a direct acyclic graph of blocks (blockDAG). PHANTOM includes a parameter k that controls the level of tolerance of the protocol to blocks that were created concurrently, which can be set to accommodate higher throughput. It thus avoids the security-scalability tradeoff which Satoshi’s protocol suffers from. PHANTOM uses a greedy algorithm on the blockDAG to distinguish between blocks mined properly by honest nodes and those that created by non-cooperating nodes who chose to deviate from the mining protocol. Using this distinction, PHANTOM provides a robust total order on the blockDAG in a way that is eventually agreed upon by all honest nodes [ https://eprint.iacr.org/2018/104.pdf ].

· Phantom, SPECTRE, IOTA are DAG-based consensus systems, all of which are, at their core, variants of the Nakamoto consensus. This leads to two disadvantages: first, the finality is probabilistic and, most importantly, it is prone to misaligned rewards incentives (e.g. selfish mining attacks)[ https://arxiv.org/pdf/1811.07525.pdf ].

· GHOST (Greedy Heaviest-Observed Sub-Tree) as a new branch selection policy, which evaluates each chain’s weight rather than length and allows to account for stale blocks, aiming at reducing the time to converge to a consistent global state. In this context, they model the network as a directed graph G = (V; E), where the edges’ values represent the network propagation delay between adjacent nodes in V [Stifter et al 2018].

· Blockmania is a byzantine consensus protocol. Nodes emit blocks forming a directed acyclic graph (block DAG) that is subsequently interpreted by each node separately to ensure consensus with safety, liveness, and finality. The resulting system has communication complexity O(N2) even in the worst case, and very low constant factors — as compared to O(N4) for PBFT. An X-Blockmania variant has O(N) communication cost but also higher latency O (log N) [Blockmania: from Block DAGs to Consensus — DRAFT (v0.5, 25 Sept 2018) — George Danezis and David Hrycyszyn].

· IoT Chain (=ITC) adopts the main chain of PBFT consensus, the DAG network, as side chain and the multi-tier architecture to build an IoT operating system which is safe, decentralized and can support high concurrency. When applying the blockchain technology in IoT some key problems need to be solved, such as the form of consensus, quick pay on small amount and protection of data privacy. For these problems, IoT has brought up its own solutions, including PBFT, SPV, DAG, CPS cluster technology, big-data-analysis smart contract ChainCode and so on [IOT Chain Whitepaper https://iotchain.io/whitepaper/ITCWHITEPAPER.pdf].

· Tezos is a generic and self-amending crypto-ledger and can instantiate any blockchain based ledger. The operations of a regular blockchain are implemented as a purely functional module abstracted into a shell responsible for network operations. Bitcoin, Ethereum, Cryptonote, etc. can all be represented within Tezos by implementing the proper interface to the network layer. Tezos supports meta upgrades: the protocols can evolve by amending their own code. To achieve this, Tezos begins with a seed protocol defining a procedure for stakeholders to approve amendments to the protocol, including amendments to the voting procedure itself. TEZOS’ proof-of-stake mechanism is a mix of several ideas, including Slasher, chain-of-activity, and proof-of-burn [Tezos Whitepaper https://github.com/tezos/tezos-papers].

· “Ouroboros Genesis” adapts a PoS-based blockchain protocol with a novel chain selection rule. The rule enables new or offline parties to safely (re-)join and bootstrap their blockchain only from a trusted copy of the genesis block without any additional advice — such as checkpoints — or assumptions regarding past availability; i.e. such a blockchain protocol can “bootstrap from genesis without any information the genesis block. In particular, this provides the joining party a blockchain possessing all the favorable properties (e.g., a large common prefix with other honest parties) that would be guaranteed if the party had fully participated during the entire history of the protocol [Badertscher et al.: Composable Proof-of-Stake Blockchains with Dynamic Availability https://eprint.iacr.org/2018/378.pdf].

· IOTA is sometimes said to be Nakamoto because it is believed that correct transactions accumulate many children over time and gain more weight, similar to blocks in the blockchain. We, therefore, allocated IOTA in our taxonomy to the Nakamoto family.

· Hedera Hashgraph uses two special techniques (1) Gossip about Gossip and (2) Virtual Voting to achieve fast, fair and secure consensus. In a gossip protocol, after transactions, nodes share info with other elements. “Using a gossip protocol, nodes efficiently and rapidly exchange data with other nodes in the community. This automatically builds a Hashgraph data structure using the novel “gossip about gossip” protocol. This data structure is cryptographically secure and contains the history of communication in a community. Using this as an input, nodes run the same virtual-voting consensus algorithm as other nodes. The community reaches consensus on the order and timestamp without any further communication over the internet. Each event is digitally signed by its “creator” [https://www.hedera.com]. [Zamboglu, D. https://medium.com/datadriveninvestor/hedera-hashgraph-explained-c5d8ce4730a6 ].

· HelixMesh is a leaderless IoT-focused consensus protocol inspired by the MeshCash framework. Helix Cognitive Computing (www.hlx.ai), the company behind the protocol, provides a technical exposition of the HelixMesh protocol and the underlying DAG-based transaction ledger in its technical paper. The HelixMesh is based on the double-consensus MeshCash framework and the Snowball protocol of the Avalanche family. The consensus process consists of the off-chain and on-chain layers. Besides, the design of the protocol provides the ability to run either permissioned or public implementations due to the Proof-Of-Contribution abstraction which supports both classical Byzantine and PoS/PoW adversarial models. The on-chain protocol, referred to as the Tortoise protocol, runs a DAG-based consensus protocol, while the off-chain protocol, referred to as the Hare consensus, works as a finality oracle. The fast Hare consensus protocol may not terminate but if it does, it predicts the outcome of the slower Tortoise consensus run in parallel. The on-chain Tortoise protocol itself is self-contained and make all the consensus decisions only using the local state of the DAG [ https://hlx.ai/files/HelixMesh_V1_2019_04_0.pdf ].

References:

Ballandies, M. C., Dapp, M. M., Pournaras, E. (2018) Decrypting Distributed Ledger Design — Taxonomy, Classification and Blockchain Community Evaluation [Accessed: 30 October 2018].

Castro, M. & Liskov, B., (2002) — Practical Byzantine Fault Tolerance and Proactive Recovery 2002 ACM 0734–2071/02/1100–0398 — ACM Transactions on Computer Systems, Vol. 20, №4, November 2002, Pages 398–461

Helix, (2019) — HelixMesh Protocol, V 1.0, April 5th, 2019 — Helix Cognitive Computing Team. Available at www.hlx.ai

Koticha, Z., (2018) — Proof of Stake and the History of Distributed Consensus: Part 1, Nakamoto Consensus, Byzantine Fault Tolerance, Hybrid Consensus, Thunderella

Lamport, L., (1978) — Time, clocks, and the ordering of events in a distributed system” Communications of the ACM 21.7 (1978)

Lamport, L., Shostak, R., Pease, M. (1982) — The Byzantine generals problem”. ACM Transactions on Programming Languages and Systems (TOPLAS) 4.3 (1982)

Lamport, L., (2001) — Paxos Made Simple — 01 Nov 2001 — https://lamport.azurewebsites.net/pubs/paxos-simple.pdf

Pass, R. & Shi, E. — The Thunder Protocol by Thunder Research

Pass, R. & Shi, E., (2017) — Cornell University 2017 — Rethinking Large-Scale Consensus

Stifter, N., Judmayer, A., Schindler, P., Zamyatin, A._, Weippl, E., (2018) — Agreement with Satoshi — On the Formalization of Nakamoto Consensus SBA Research, Imperial College London, Christian Doppler Laboratory for Security, TU Wien

¹Note: In our classification analysis visualized in this graphic, we de-tangled the decentralization aspect of the protocols from the other four determinants. For its high importance, and also, in order to keep the representation here simple, we will introduce a second classification dedicated to “decentralization” properties of protocols.

Acronyms: [a, p, f, d] Byzantine Fault Tolerance means: Asynchronous BFT, Practical BFT, Federated BFT, Delegated BFT. For example: In a dBFT, the system is comprised of nodes, delegates (who can approve the blocks), and a speaker (who proposes the next block) — enough to protect against malicious actors within the network. It is a consensus algorithm developed with perfect finality, meaning that all transactions are 100 percent final after the first confirmation. The blockchain cannot fork with dBFT, and high-value chained transactions are trivial and executed much faster [Nikolai Kuznetsov Sep 13, 2018 — Article: “From PoS to dBFT: A Brief Review of Consensus Protocols” published in cointelegraph.com ].