A fresh attempt for Classification
Part 2 — The four Dimensions for the taxonomy: 1. Consensus protocols
This article is the second part of the bigger story about Distributed Decentralized Systems. We will publish a new article once a week following the order from the Table of Content. For the first part click the link.
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)
Table of Content for Part 2:
II. The four Dimensions for the taxonomy
II — 1. Consensus Protocols
II — 1.1 Generation of Single Consensus Protocols
II — 1.1.1. 1st Family: The Classical Consensus Protocols
II — 1.1.2. 2nd Family: The Nakamoto Consensus Protocol
II — 1.2. Generation of Hybrid Consensus Protocols
II — 1.2.1. 1st Family: Avalanche by Metastability
II — 1.2.2. 2nd Family: Meshcash by Tortoise and Hare
@HelixFoundation — All rights reserved
II — The four Dimensions for the taxonomy
Taxonomy comes from the term “taxon” which means a group of organisms [Tasca & Tessone 2019]. In our case, taxonomy encompasses the classification of DDS protocols or projects. This is different from an ontology which would be more focused on the study of the types, properties, and interrelationships of the components and events that characterize a blockchain system¹. However, we at times will take the liberty² to mix ontological aspects with taxonomy, e.g. interrelationships of similar projects.
II — 1. Consensus Protocols
When storage or computation is distributed, it is divided into parts and occurs across multiple servers or nodes (‘parallelized’), offering efficiencies and higher resilience over using just a single node. A distributed process may still rely on a central coordinator to act as an authoritative source of records, e.g., in IOTA³, or is decentralized, e.g., in Ethereum⁴.
When a process is decentralized, multiple nodes are again in use — but in this case, the process is typically replicated across the various nodes, which are generally controlled by different entities.
An ideal distributed computing system has the ability to remain operational even in the presence of unreliable components whereby there is no or just imperfect information about whether a component is faulty. Faults may originate from imperfect information, latency, hardware failures, or adversaries, and may originate from either unintentional error or malicious behavior.
– What does Consensus mean
Consensus⁵ is the mechanism of writing entries to the distributed ledger, adhering to a set of rules that all participants of the consensus enforce when an entry containing transactions is validated. Thus, the consensus is one of the most important goals to be achieved when many distributed computers share the same task and resources — and shouldn’t be confused with Sybil mechanisms such as PoW (Proof of Work), which we explain in the next chapter.
– What does Decentralized Consensus mean
As explained in [Tasca & Tessone, 2019], “in a blockchain, consensus can be based on “rules” (that determine, e.g., which transactions are allowed and which are not) or on the history of “transactions” (which allows users to determine who owns what). The decentralized consensus on transactions governs the update of the ledger by transferring the responsibilities to local nodes which independently verify the transactions and add them to the most cumulative computation throughput (i.e., the “longest chain” rule). There is no integration point or central authority required to approve transactions and set rules.”.
– What is a Protocol
A protocol determines how a distributed decentralized system will function and how it will operate.
Protocols have been an important research topic for the last 40 years to find efficient solutions. In the field of distributed systems there used to be only two existing families of consensus protocols in the original settings, i.e. “single protocol approaches”. Later, the approach to combine the best ideas from each protocol and to come up with hybrid protocols became more popular. Based on this evolution, we prefer to categorize the protocols initially at the level of their generation (single or hybrid), and then within each generation to different “families”.
II — 1.1. Generation of Single Consensus Protocols
II — 1.1.1. 1st Family: The Classical Consensus Protocols
– Paxos Algorithm
Chronologically, the first family is the classical consensus protocols. Advantages of this protocol are various, including quick finality and quick guarantees about the committed transactions. The legendary Paxos-Algorithm is actually the oldest consensus mechanism, invented by Leslie Lamport in 198⁹⁶.
It is often said in consensus science that there is only one consensus algorithm and it is Paxos. This is, on the one hand, a statement of the significance of the Paxos algorithm for the field and, on the other hand, a reflection of the universal foundation of consensus protocols, which is in every case “Paxos-like” [Howard, Malkhi, Spiegelman, 2016]. Especially RAFT and Viewstamper Replication (VSR) fall directly into this category. However, there is a significant drawback with these protocols as they are meant to be executed in non-adversarial settings, i.e. only tolerating crash failures when processes stop without warning. They are not resistant to Byzantine failures [SoK, 2017].
– Byzantine⁷ Fault Tolerance
Blockchains have been described as “trust machines” [Casey & Vigna 2018] on account of the way they reduce counterparty risk through the decentralization of responsibility over a shared database. Traditionally, consensus protocols tolerant of malicious behavior were known as Byzantine Fault Tolerant (BFT) consensus protocols [Buchman, 2016]. BFTs belong like Paxos to the first family of the classical consensus protocols.
Also, the famous “practical Byzantine Fault Tolerance” (pBFT), which we explain below, can be understood as an extension of the Paxos/VSR family and uses a progression of views and a unique leader within every view⁸ [Cachin & Vukolić, 2017].
BFT implements a form of State Machine Replication⁹ [Lamport, 1978] that allows replication of services that perform arbitrary computations provided they are deterministic, that is, replicas must produce the same sequence of results when they process the same sequence of operations. BFT provides both safety¹⁰ and liveness¹¹– properties assuming no more than (n-1)/3 replicas are faulty over the lifetime of the system [Castro & Liskov, 2002].
Generally, the “Byzantine” problem concerns a network of nodes with all-to-all connectivity, with some nodes being honest and some being adversarial, i.e., can behave arbitrarily, even maliciously and send different data to different peers or refuse to send data altogether. Each of these nodes has some “input”, potentially different for each one, and they want to agree on a common view. The “input” can be the set of new transactions to confirm in the case of bitcoin, for example.
– Difference between BFT (Byzantine Fault Tolerance) and BA (Byzantine Agreement) Protocols¹²
The canonical problems in the space, which are equivalent to each other (if you can solve one, you can solve the other), are formulated as follows:
The Byzantine Agreement Problem. A group of nodes needs to agree on some value. The protocol needs to (a) terminate within finite time, (b) have all honest nodes reach the same result, and © the result reached must match the input of one of the nodes.
The Byzantine Generals Problem. A group of nodes has a designated “leader” called a “general”. The leader has an input value and the rest of the nodes need to agree on a value. The protocol needs to (a) terminate within finite time, (b) have all honest nodes reach the same result, and © if the leader is honest, then the value agreed by everyone should be the leader’s value. These problems can be modified to allow for less connectivity or to allow for failures that are not byzantine (i.e., do not allow for malicious intelligence, just failure that isn’t trying to subvert the system actively). You can also add digital signatures to the mix to make the problems easier.
In bitcoin’s case, the problem solved is a harder variant; anonymous Byzantine agreement. In this case, the number of parties can change arbitrarily and the parties do not know who is sending each message. The solution to this is to use Proof-of-Work.
The key difference between BA and BFT is that, while the BA is used to refer to the specific problem of reaching consensus about a decision under byzantine settings, BFT refers to designing any generic protocol (not necessarily requiring agreement), for example, the Byzantine Generals protocol, for solving a problem under byzantine faults, i.e., faults that are malicious. The generic problem of BFT and the problem of BA are equivalent — if you have an agreement, you can be fault-tolerant; and if you are fault-tolerant you can reach an agreement.
– The FLP Impossibility
The problem of consensus is solvable in a synchronous setting where processes can proceed in simultaneous steps. In particular, the synchronous solution is resilient to faults where processors crash and take no further part in the computation. Informally, synchronous models allow failures to be detected by waiting for one entire step length for a reply from a processor and presuming that it has crashed if no reply is received.
This kind of failure detection is impossible in an asynchronous setting where there are no pre-arranged time limits a processor might take to complete its work and then respond with a message. Therefore, it is not possible to say whether a processor has crashed or is simply taking a long time to respond.
Thus, there is no distributed algorithm that solves the consensus problem in an asynchronous environment. This particular result is known as the ‘FLP Impossibility’¹³.¹⁴
– BFT Variants¹⁵
Asynchronous Byzantine Fault Tolerant (aBFT) algorithms are similar to Nakamoto’s Bitcoin in that they allow for agreement amongst many different parties. Also, there are asynchronous versions of Paxos and [practical] pBFT algorithms implemented in some systems [Cachin & Vukolić, 2017].
The pBFT (practical Byzantine Fault Tolerant) was actually introduced in 1999 and was considered suitable for use in asynchronous networks, though it does, in fact, make weak synchrony assumptions which can be violated by a careful adversary. Basically, the protocol works as follows: pBFT proceeds through a series of views, where each view has a proposer, known as a primary, that is selected in round-robin order. The primary receives requests from clients, assigns them a sequence number, and broadcasts a signed pre-prepare message to the other processes containing the view and sequence numbers. Replicas accept the pre-prepare message if they have not already accepted one for the same view and sequence numbers, assuming the message is for the current view and signed by the correct primary [Buchman, 2016]. These protocols normally confirm transactions in a constant O(1) of round trips. Because they are asynchronous, there is no need to wait for any apriori set block interval or synchronous round; they run as fast as the network delivers messages. Problem with aBFT: these algorithms are not suitable for truly permissionless environments due to scalability issues. They also decrease the number of attackers that PoW blockchains can tolerate from ½ of the network to ⅓. Thus, when the algorithms’ assumptions are not fulfilled (on the number of adversarial nodes, or on the availability of honest nodes) many nodes tend to shut down. In other words, they lack strong Liveness guarantees when their assumptions are violated [Koticha, 2018].
II — 1.1.2. 2nd Family: The Nakamoto Consensus Protocol
– Nakamoto Protocol
A decade later, in 2009, the second family of consensus protocols was introduced — The Nakamoto Protocol, which solved major drawbacks of the classical consensus mechanism, e.g., the quadratic communication costs [O(n²)] among the participating nodes. However, it was at the cost of performance, scalability¹⁶, throughput and wastefulness of energy¹⁷. Also, in contrast to other BFT algorithms, the Nakamoto consensus is probabilistic, meaning that the algorithm validates a new entry by utilizing the whole history of previous entries. Most of today’s Blockchains, e.g. Bitcoin, Ethereum, fall into this category. For instance, in Bitcoin, a writer validates a transaction by considering the whole blockchain and includes then the transaction into a new block. As soon as this block gets referenced by six blocks, it is confirmed, since the probability that the second chain of six blocks reference each other but not this block is low then [Ballandies et al. 2018]. As IOTA also uses Nakamoto, even with DAG as the data structure vs sequentially chained blocks, it is still probabilistic and entry is confirmed when it is referenced by a significant number of new entries.
The Nakamoto protocol refers to the set of rules that govern the consensus mechanism and ensures its trustless nature. It can be broken down into three parts: Block Selection, Incentive Structure, PoW.
Nakamoto Block Selection:
As opposed to the pBFT, which has no mining and blocks are selected to be added to the chain by the leader and need to be approved by at least ⅔ of the other nodes, in Nakamoto consensus, there is no voting process to determine the block leader. Instead, it utilizes a cryptographic puzzle predicated on incrementing a nonce in the block until the correct value that represents the block’s hash and the required zero bits for the beginning of the nonce are reached.
The block selection process specifically refers to the “lottery” process for miners competing to win the block reward for mining the next block. The block is then propagated by the miner across the network to the other mining nodes who implicitly vote to accept the block as valid by adding the block to the longest chain. The process is random and the leader cannot be predicted. The only way to win the lottery is by contributing hashing power to the network in hopes of winning. If not, the expended energy becomes a sunk cost, adding to the incentive structure of mining. [https://blockonomi.com/nakamoto-consensus/ ].
– Conflict Resolution Rule in Protocols
The conflict resolution rule determines how disputes regarding competing or conflicting versions of valid records are being resolved and depends on the consensus algorithm in use. For instance, Bitcoin resolves a temporary split caused by two competing valid blocks at equal height by choosing the block on the branch that carries most cumulative PoW (longest-chain rule). Tezos¹⁸, for example, adapts the longest chain rule for PoS, defining the ‘weight’ of a block as the number of ‘endorsements’ it receives from randomly-selected record producers. Alternative resolution rules involve the unanimous agreement of all record producers or passing a certain quorum threshold [Rauchs et al. 2018].
Nakamoto Incentive Structure:
The deflationary nature Nakamoto is using, see Bitcoin, creates an iterated game theory model where cooperation among individuals within the network is optimal through aligned interests driven by deflation in the long-term. In other words, miners are incentivized to validate and secure the network honestly, as the reward they receive for mining a block is Bitcoin. If the value of Bitcoin drops or the network becomes affected, it also affects their bottom line [https://blockonomi.com/nakamoto-consensus/].
(Role of) PoW in Nakamoto:
Actually, being a Sybil attack prevention mechanism, the “Proof of Mechanisms” play a distinctive “double” role in the Nakamoto consensus. We explain this phenomenon in the next section and therefore defer here.
II — 1.2. Generation of Hybrid Consensus Protocols
– Is there a need for another Type of Consensus
There are two main bottlenecks of classic blockchains:
1) Throughput: Existing blockchains as employed by major crypto-currencies (e.g., Bitcoin or Ethereum) require flooding the whole network with all the transactions. As a consequence, these blockchains do not scale well to handle a large transaction volume. For instance, Bitcoin and Ethereum can handle less than 10 transactions/second.
2) Confirmation times: The security of Nakamoto’s blockchain protocol requires the block-time to be significantly larger than the maximum network latency¹⁹; this is why in Bitcoin, new blocks of transactions get mined every 10 minutes, and a transaction is only considered confirmed once it has been incorporated in a block and there are 5 subsequent blocks following it; thus, it takes on average one hour for a transaction to be confirmed (with high confidence). While Ethereum uses a smaller block-time, the average confirmation time still remains relatively high |approximately 13 minutes. [Pass & Shi]. These long confirmation times hinder many important applications, especially in the emerging Machine Economy with IoTs.
Since Nakamoto, countless R&D projects have been initiated as variations from the first two consensus families. However, the greatest challenge for DLTs remained: how to achieve the speed of BFT algorithms and the robustness of Nakamoto consensus while avoiding wasteful computational resources. Those efforts led to new protocol frameworks – e.g., Algorand, SnowWhite, Cosmos are making use of both worlds: They all try to be permissionless, scalable to a large number of nodes, “asynchronous”. Users do not need to wait for a single block interval because a fast-path is responsive “immediately”.
II — 1.2.1. 1st Family: Avalanche by Metastability
Avalanche, for example, is a new family of consensus protocols, combining the best of former both protocol families and inspired by gossip [communication] algorithms gaining its safety through a deliberately metastable mechanism. Specifically, the Avalanche system operates by repeatedly sampling the network at random intervals and steering the correct nodes towards the same outcome [Snowflake to Avalanche].
II — 1.2.2. 2nd Family: Meshcash by Tortoise and Hare
MeshCash, another new framework for cryptocurrency protocols that combines a novel, proof-of-work based, permissionless byzantine consensus protocol (the tortoise) that guarantees eventual consensus and irreversibility, with a possibly-faulty but quick consensus protocol (the hare). The construction is modular, allowing any suitable “hare” protocol to be plugged in. The combined protocol enjoys best of both worlds’ properties: consensus is quick, if the hare protocol succeeds, but guaranteed even if it is faulty. Unlike most existing PoW based consensus protocols, MeshCash’s tortoise protocol does not rely on leader-election (e.g., the single miner who managed to extend the longest chain). Rather, it uses ideas from asynchronous byzantine agreement (aBFT) protocols to gradually converge to a consensus [Bentov et al.].
We consider Avalanche and Meshcash as a “cutting-edge generation” family of consensus protocols based on either hybrid combination of best-of-breed approaches, i.e., unite desirable properties from classical BFT and derivatives such as “hare” and “tortoise” in MeshCash — or based on novel consensus mechanisms such as “metastable equilibrium” in Avalanche. Also, we treat them as a family of protocols with a considerable novelty, because both of them allow for the incorporation of DAGs (Directed Acyclic Graphs) data structures in their protocols. For example, MeshCash-based protocols replace the notion of a blockchain with a mesh, a layered DAG, that provides irreversibility and economic finality.
Further, as opposed to the simpler chain topology, the mesh is “race-free”, i.e., it guarantees a fair share of the rewards to the honest integrator nodes, regardless of the actions of others.
The idea of using the DAG allows multiple blocks to coexist in parallel, while the rewards are still shared proportionally to the work performed. This offers several mitigating factors for the risks that Bitcoin faces [Bentov et al.].
The first practical instantiations of this general paradigm are currently being developed: for example, HelixMesh [Helix 2019] is one of the most interesting implementations as it provides a technical exposition of the HelixMesh protocol and the underlying DAG-based transaction ledger. The HelixMesh is based on the double-consensus MeshCash framework and the Snowball protocol of the Avalanche family. Further, HelixMesh plans to use an innovative process — called cryptographic sortition²⁰. The main advantage of HelixMesh over existing BFT consensus protocols is a high degree of flexibility: the protocol can be deployed in both permissionless and permissioned environments. Moreover, virtually any BFT consensus is suitable for the off-chain layer of the HelixMesh. As a result, the liveness vs safety tradeoffs are not dictated by the protocol itself but may be adjusted based on the particular use-case requirements. This makes the HelixMesh a robust blueprint for IoT-sourced distributed ledgers.
– Attributes of consensus
The three key attributes of consensus are Type of Protocol, Permission (write and validator permissions) and Fee [Ballandies et al. 2018].
– Type of Protocol
A major criterion is whether the consensus is deterministic — if the consensus is found in a guaranteed finite amount of time — or probabilistic — if consensus is found with some uncertainty. In the blockchain setting, finality is the affirmation that all well-formed blocks will not be revoked once committed to the blockchain. When users transact, they want to be confident that once their transactions go through, the transactions cannot be arbitrarily changed or reversed. For example, in current Nakamoto consensus-based systems, if a malicious actor is able to accumulate 51% of mining power, they can conduct a double spend attack. These protocols offer probabilistic finality, while others, such as Paxos or pBFT-based protocols (e. g, Tendermint) guarantee absolute finality — i.e., they are deterministic–, in which a transaction is considered finalized as soon as it is included in a block and added to the blockchain.
– Permission
Permission illustrates who is allowed to write to (or validate entries in) the distributed ledger, thus, the attribute “Permission” plays an important role in the Decentralization of the system.
The Write permission: illustrates who is allowed to write entries to the distributed ledger. The characteristics are private if participation is restricted or public otherwise. The Bitcoin consensus mechanism is public — it allows everyone having the computing power to participate. On the other hand, the consensus mechanism of e.g Ripple, Hyperledger, Corda is private — it has a few trusted institutions, which perform consensus, and hence not everyone can participate.
The Validate permission: shows who is allowed to validate claims before they are written to the distributed ledger. The characteristics are: private if participation is restricted and public otherwise. In Bitcoin, the writers validate claims for correctness, utilizing the proof, before they write them to a block, hence the validator permission is also public. In contrast, in IOTA [Popov, 2018] a central entity, the Coordinator, validates transactions before they are collected in an entry and then written to the DAG, claims the research by [Ballandies et al. 2018]. However, our analysis indicates that all transactions are validated and written to the Tangle by full-nodes, so anyone can read/write. The Coordinator simply issues a milestone transaction.
– Fee
The Fee shows whether participants of the consensus (writers and validators) are paid a fee for writing new entries to the distributed ledger. The characteristics are yes and no. In contrast to Bitcoin²¹, where writers/ validators are rewarded with fees, in IOTA the writers and validators receive no fees. In Ripple, no fees are rewarded to the consensus participants, although the actors have to pay a fee [Ballandies et al. 2018].
– Conclusion
BFT protocols sound ideal to replace Nakamoto consensus in blockchains. However, in practice, they do not scale well to a large number of nodes when handling a permissionless consensus setup [Pass & Shi, 2017]. Paxos is also permissioned and centralized. On the other hand, Nakamoto is permissionless and decentralized but does NOT scale and wastes energy. Thus, 2019 and 2020 will likely see the development of a few new hybrid protocols or interchangeable Sybil mechanism projects.
References:
Ballandies, M. C., Dapp, M. M., Pournaras, E. (2018) Decrypting Distributed Ledger Design — Taxonomy, Classification and Blockchain Community Evaluation [Accessed: 30 October 2018].
Bentov, I., Hubáček, P., Moran, T., Nadler, A., — Tortoise and hares consensus: the meshcash framework for incentive-compatible, scalable cryptocurrencies.
Buchman, E. (2016) — Tendermint: Byzantine Fault Tolerance in the Age of Blockchains
Casey, M. J., Vigna, P. (2018) The Truth Machine — The Blockchain and Future of Everything — St. Martin’s Press — New York in Feb 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
Cachin, C., & Marko Vukolić, M. (2017) — Blockchain Consensus Protocols in the Wild, 2017, IBM Research — Zürich
Helix, (2019) — HelixMesh Protocol, V 1.0, April 5th, 2019 — Helix Cognitive Computing Team. Available at www.hlx.ai
Howard, H., Malkhi, D., Spiegelman, A., (2016) — Flexible Paxos: Quorum Intersection Revisited
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)
Pass, R. & Shi, E., (2017) — Cornell University 2017 — Rethinking Large-Scale Consensus
Popov, S., (2018) — The Tangle — 2015, then updated October 1, 2017. Version 1.3 and recently April 30, 2018. Version 1.4.3 https://assets.ctfassets.net/r1dr6vzfxhev/ 2t4uxvsIqk0EUau6g2sw0g/45eae33637ca92f85dd9f4a3a218e1ec/iota1_4_3.pdf.
Rauchs, M. et al. (2018) — DISTRIBUTED LEDGER TECHNOLOGY SYSTEMS — A Conceptual Framework. University of Cambridge — Judge Business School
SoK, (2017) — SoK: MetaAnalysis of Alternative Consensus Protocols for Blockchains https://github.com/Mechanism-Labs/MetaAnalysis-of-Alternative-Consensus-Protocols/blob/master/MetaAnalysis.pdf
Tasca, P., Tessone, C. J., (2019) — A Taxonomy of Blockchain Technologies: Principles of Identification and Classification. Ledger Journal. LEDGER VOL 4 (2019) 1–39 ISSN 2379–5980 (online) — DOI 10.5195/LEDGER
¹ See for a simple introduction, e.g. [Seibold & Samman [2016]
² For a more rigorously separated notion of taxonomy and ontology, see [Tasca & Tessone, 2019] in Taxonomy of Blockchain Technologies in references.
³ IOTA is secured by a heavily distributed form of PoW. The state of the ledger is maintained by so-called full nodes. The IoT devices are envisioned to function as light nodes; they are expected to connect to the full nodes, create & sign transactions, and compute a PoW in a distributed fashion. The current state of IOTA the cryptocurrency falls short of this vision — the transactions are also validated by the centralized Coordinator node(s) [Elsts, 2018].
⁴ https://github.com/ethereum/wiki/wiki/Ethereum-White-Paper
⁵ In the literature, “consensus” means traditionally only the task of reaching agreement on one single request (i.e., the first one), whereas “atomic broadcast” provides agreement on a sequence of requests, as needed for state-machine replication. But since there is a close connection between the two (a sequence of consensus instances provides atomic broadcast), the term “consensus” more often actually stands for atomic broadcast, especially in the context of blockchains. We adopt this terminology here and also use “transaction” and “request” as synonyms for one of the messages to be delivered in the atomic broadcast.
⁶ Lamport presents the imaginary story of a government parliament on an ancient Greek island named Paxos, where the absence of any number of its members, or possibly all of them, can be tolerated without losing consistency. Unfortunately, the setting as a Greek parable made the paper difficult for most readers to comprehend. An attempt by Lamport to submit to a journal led to a rejection by the peer-review, until a decade later it finally got published scientifically as of May 1998:
“The Part-Time Parliament”. ACM Transactions on Computer Systems. 16 (2): 133169 doi:10.1145/279227.279229. For all TL; DR’s, I refer to the simplified explanation of the Paxos algorithm: http://harry.me/blog/2014/12/27/neat-algorithms-paxos/ and to [Lamport, 2001].
Later, Leslie Lamport, with Barbara Liskov, received the Turing Award, the Nobel Prize in Computer Science.
⁷ The term Byzantine was used due to the similarity of the problem to that faced by generals of the Byzantine army attempting to coordinate themselves to attack Rome using only messengers, where one of the generals may be a traitor.
⁸ In a system with n nodes pBFT tolerates f < n/3 Byzantine nodes, which is optimal.
⁹ … wherein a deterministic state machine is replicated across a set of processes, such that it functions as a single state machine despite the failure of some processes. The state machine is driven by a set of inputs, known as transactions, where each transaction may or may not, depending on its validity, cause a state transition and return a result. More formally, a transaction is an atomic operation on a database, meaning it either completes or doesn’t occur at all, and can’t be left in an intermediate state. The state transition logic is governed by the state machine’s state transition function, which maps a transaction and the current state to a new state and a return value. The state transition function is also sometimes referred to as application logic [Buchman, 2016].
¹⁰ Safety is the property that ensures honest participants don’t agree on two conflicting things (blocks, in this case). We use safety as a synonym for both finality and agreement [SoK 2017]. That is, once a block is finalized, the canonical chain will always contain that block in the future. In other words: all non-faulty processes agree on the same output. If we can guarantee safety, we can guarantee that the system as a whole will stay in sync. We want all nodes to agree on the total order of the transaction log, despite failures and malicious actors. A violation of safety means that we end up with two or more valid transaction logs. Further, Safety and Security do not have the same meaning. Safety protects from randomness (e.g., hit by lightning), or from the aftereffects of events (accidents). Security protects from malicious intent of a driven, adaptable and malicious adversary.
¹¹ Liveness is the property that ensures something is eventually agreed upon by honest participants. Liveness is the same thing as termination [SoK, 2017]. In other words: every non-faulty node eventually decides on some output value. In a blockchain setting, liveness means the blockchain keeps growing by adding valid new blocks. Liveness is important because it’s the only way that the network can continue to be useful — otherwise, it will stall. Liveness is also the property of speed, characterized by low latency.
Safety and Liveness are inversely proportional — This means that for any additional liveness gained in a protocol, it must sacrifice on safety, i.e., if you want more speed in a distributed system, your system becomes less secure.
¹² Contributed by
¹³ by Fischer, Lynch, and Patterson in 1985, presented in their seminal short paper:
“Impossibility of Distributed Consensus with One Faulty Process” (http://cswww.cs.yale.edu/homes/arvind/cs425/doc/fischer.pdf),
¹⁴ Source: https://www.the-paper-trail.org/post/2008-08-13-a-brief-tour-of-flp-impossibility/
¹⁵ When talking about variants of BFT the Tendermint — Paper can serve as a good source: https://arxiv.org/pdf/1807.04938.pdf
¹⁶ The scalability is also a major issue in BFT
¹⁷ In Nakamoto the agreement is on a sequence of blocks, while on BFT the agreement is on a single value! This fact makes a direct comparison and analogies with BFT in general difficult.
¹⁸ Tezos whitepaper: https://tezos.com/static/white_paper-2dc8c02267a8fb86bd67a108199441bf.pdf
¹⁹ Latency describes the rule of message propagation in the network. See also the FLP impossibility paragraph in this paper, where synchronous and asynchronous communications are briefly explained as the key methods influencing the latency.
²⁰ Algorand uses an innovative process — called cryptographic sortition — to securely and unpredictably elect a set of voters from the network periodically. These voters are responsible for reaching consensus through a Byzantine Agreement (BA) protocol on one block per time, guaranteeing an overwhelming probability of linearity of the blockchain [Conti, Gangwal, Todero, 2019] and
https://www.coindesk.com/scalable-blockchain-consensus-turing-award-winner-thinks-hes-got-solution
²¹ Technically, zero-fee transactions can be accepted as well, there’s no mandatory fee at the protocol level. But transaction with fees picked up faster. The main source of rewards in Bitcoin is still coin-based rewards, not transaction fees.
