Detailed explanation of Kaspa consensus model DAG-KNIGHT: How to achieve 1/2 fault tolerance in a partially synchronized model
Original source: KasMedia
Original title: The Master of Time: How Dagknight Solved an Impossible Result Unaccountable by Bitcoin, Ethereum and Classic BFT Models
Original author: Nicholas Sismil, former head of research at Binance.US
Viewpoint: There is a well-known impossible conclusion in blockchain and distributed system theory: under an incompletely synchronized communication model, no protocol or network can achieve a 1/2 fault tolerance rate. This is a problem that no other protocol, such as Bitcoin, Ethereum, and the classic BFT model, can solve, but the consensus model DAG-KNIGHT that Kaspa will implement can. The key to solving this problem is to achieve a strong network correctness (for example, in the face of delays and other interference factors) in the process of simulating the real world, thereby becoming the master of time in the network.
In this article, I will mainly explore these issues:
1. The nature of distributed systems;
2. How to balance correctness, timeliness and fault tolerance? ;
3. Finality and dynamic availability (i.e. probabilistic finality vs. absolute finality);
4. The performance and shortcomings of Bitcoin, the classic BFT model, and Ethereum in these properties;
5. How does DAG-KNIGHT break through this impossible result and solve the shortcomings of all other protocols?
6. Finally, summarize how DAG-KNIGHT becomes the master of time and what this means for the theory of distributed systems.
Definition of distributed system
There are many definitions of distributed systems. Leslie Lamport described it this way in a 1987 communication: In a distributed system, a failure on a computer that you don't even know exists in the system can render your own computer unusable. Imran Bashir, in his book "Blockchain Consensus", defines a distributed system as a collection of anonymous computers that work autonomously together to achieve a common goal through a message passing network.
Fundamentally, the goal of a distributed system is for all of its components to agree on the overall state of the system — to reach consensus. Although Facebook, Google, Twitter, Amazon, etc. are centrally managed businesses, they all use distributed systems (as well as the World Wide Web). In this article, I will discuss the historical development of another type of distributed system, which consists of blockchains, distributed ledgers, and block directed acyclic graphs (blockDAGs).
First, we need to understand several core properties of distributed systems: correctness, timeliness, and system internal fault tolerance.
Correctness, timeliness, and fault tolerance in distributed systems
Leslie Lamport defined the concept of correctness in distributed systems in Proving Multiprocessing Correctness. He argued that a distributed system that wants to be correct must have both liveness and safety. Safety means that a decision cannot be reversed, while liveness means that a decision cannot be delayed indefinitely. In other words, safety guarantees that different honest nodes will never make different decisions, while liveness guarantees that every honest node will eventually make a decision.
As we will see, some distributed systems prefer to guarantee liveness, while others prefer to guarantee safety.
Timeliness and fault tolerance
Timeliness reflects the communication behavior model in a distributed system. The communication model includes specifications about network delays and processor delays and speeds. These specifications essentially determine the extent to which a network adversary can control message delays in the system. In other words, the communication model defines the limits of a network adversary's ability to disrupt communications.
There are three main communication models, depending on the synchronization method: (fully) synchronous, asynchronous, and partially synchronous. Each model determines the fault tolerance of the system, that is, the communication model determines whether the protocol can withstand an error rate of 1/3 or 1/2.
(Fully) Synchronous Model
In the synchronous model, there is a pre-known maximum message delay bound ∆ within which all messages must be delivered, and all participants in the network know how long it takes for a message to be delivered. Therefore, an adversary can only delay the delivery of a message by up to δ. For example, Bitcoin uses a synchronous model and operates according to the longest chain rule, which follows a maximum delay L for each block. L is constantly updated and always ensures that the block arrives in about 10 minutes, i.e., the upper limit delay ∆ is 10 minutes.
Synchronous systems are simple and provide strong positive results. However, they are too rigid to effectively simulate the real world (such as network outages and unexpectedly long attacks) without compromising security. For example, setting a long delay ∆ can provide strong positive results that represent the real world, but can lead to long timeouts and performance degradation. Conversely, setting a short delay ∆ can improve performance, but may not accurately simulate the real world, thus compromising security. In other words, if network participants overestimate delays, the system will run slower than it actually is; otherwise, the system will be less secure.
Furthermore, trying to find an ideal balance between the two is not easy. For example, if a sender broadcasts a message to two receivers, and one message arrives after ∆−ϵ and the other arrives after ∆+ϵ, then the behavior in the real world will be different from what the model expects, which will compromise the safety of the system.
Despite these issues with the synchronous model, it still achieves a maximum fault tolerance bound of 1/2. This is because we can assume that every node in the system sees every vote in a fixed amount of time to reach consensus. Specifically, if there are n nodes in the system, and f of them are faulty, we want at least f+ 1 correct nodes to have messages that outnumber the f faulty nodes. Once all messages are received, consensus is reached according to the synchronous model.
That is, if:
n ≥ f+(f+ 1)
f ≤ (n-1)/2
f < n/2
Then the maximum error tolerance reaches ½.
Asynchronous Model
The asynchronous model attempts to overcome the problems encountered by the synchronous model by not making any assumptions about network latency: there is no limit on network latency even between nodes that are operating normally. This has two advantages: first, there is no communication time limit, so asynchronous (late) messages will not accidentally compromise safety; second, since there is no fixed timeout, nodes can adapt to the actual delays in the system and still remain active.
However, this also comes with some costs. Fischer, Lynch, and Patterson proposed an impossibility theorem in their paper "The Impossibility of Distributed Consensus with One Faulty Process" that states that in an asynchronous model, even with a single faulty node, consistency cannot be guaranteed. In other words, in an asynchronous model, just one faulty node is enough to make consistency impossible.
Nevertheless, it is possible to reach consensus in t seconds under a randomized algorithm, because the probability of consensus approaches 1 exponentially as t grows. Therefore, an asynchronous consensus algorithm can only achieve a 1/3 fault tolerance rate, not a ½.
In addition, Eric Brewer proved that consistency (safety), liveness, and partition tolerance cannot coexist in asynchronous distributed systems. Partition tolerance refers to ensuring that the system can still operate during network partitions (messages between some nodes cannot be delivered). Therefore, in asynchronous systems, there is a trilemma - you must choose two of the three, safety, liveness, and partition tolerance, but not all of them.
Although the theorem applies to asynchronous model systems, network partitions still obey the asynchronous assumption and occur in all timing models. Therefore, regardless of the model used, the system must either favor liveness or safety during a network partition.
Partial Synchronization Model
There are two ways to achieve partial synchronization in the system. The first way is to use a synchronous model when the system is operating normally, and switch to an asynchronous model when a failure occurs (such as a network failure or attack). This method assumes that there is a clock that observes the global network, and the parameter ∆ specifies the maximum delay that may occur in the message during the synchronization phase. However, in the asynchronous phase, the parameter ∆ does not work, and the global stable time (GST) determines the time point when the communication model switches from synchronization to asynchronous. This version is called the GST version.
The second way is to assume that there is no known bound on message delivery, but rather an unknown finite upper bound δ that can be chosen by the network adversary. In this version, there is no GST and no switching between asynchronous and synchronous phases. Instead, messages will always be delivered within ∆ time steps, just like in the synchronous model.
It is particularly noteworthy that all partially synchronous models have a fault tolerance of 1/3. As formally proved by impossibility results in the work of Dwork, Lynch, and Stock, partially synchronous models cannot achieve a fault tolerance of 1/2.
Finality and Dynamic Availability
Historically, protocols are divided into two categories: the longest chain-based protocol and the classic BFT consensus protocol. The former uses a synchronous model and follows the Nakamoto consensus, i.e. the longest chain rule: when there is a disagreement between chains, the longest chain is selected. The latter uses a partial synchronization model, operates based on state machine replication, randomly selects validators to propose blocks, and decides whether to include blocks in the chain through multiple rounds of voting. In each round of voting, all honest and online validators vote on a specific block.
Unlike the longest chain-based protocol, the BFT consensus protocol does not rely on the length or size of the chain for block generation. BFT consensus favors security over liveness and provides absolute finality, meaning that decisions made within the system can never be reversed. However, due to its emphasis on security, the classic BFT model cannot achieve dynamic availability. Classic BFT consensus models include Tendermint, PBFT, and HotStuff models.
On the other hand, protocols based on the longest chain (including Bitcoin and its generalized version GHOST) cannot achieve absolute finality, but instead achieve probabilistic finality through dynamic availability. Dynamic availability allows nodes to join or leave the system at any time without affecting the security of the system. Therefore, dynamic availability embodies true permissionlessness - nodes are not penalized for downtime or technical failures. In addition, during network partitions or attacks, dynamically available protocols can still make decisions even if participation is low.
Many people believe that longest-chain based protocols favor liveness over safety, but this is not entirely true. This is an important point. In models where liveness is achieved probabilistically, the distinction between liveness and safety is artificial and misleading, because in models where liveness is achieved probabilistically, safety and liveness are interdependent.
One might think that absolute finality is better than probabilistic finality, but this is not the case because each model handles partitions differently. In a classic BFT consensus system, if participation is too low during a partition, the required number of participants may not be reached, and the required votes may not be completed, causing the blockchain to stagnate. However, even if the number of active participants is reduced to one, as long as there is always an honest majority, the longest chain-based system will not stop operating during a partition. On the contrary, in this case, the network output of the ledger will continue to increase, and it has the ability to automatically correct errors: even if nodes disagree initially, the network will eventually converge and reach consensus. This error correction ability is related to the strength of network security.
As Neu et al. showed, when simulating the classical BFT model and the longest chain model under the same circumstances, the ledger network output of the longest chain protocol always continues to grow under dynamic participation and network partitions, while the finality of the classical BFT protocol stagnates during low participation or partitions.
Therefore, although the classic BFT consensus model provides security and absolute finality, the cost is that the network cannot be self-healed or restored when it is interrupted. In addition, this also sacrifices the permissionless feature of the system, leading to system centralization. For example, some BFT protocols require nodes to remain online, otherwise they will be punished. A considerable number of similar rules are undoubtedly inconsistent with the design concept of decentralized networks.
Ethereum: The widespread adoption and pitfalls of PoS
Many people want to get rid of the PoW network to save electricity and hardware costs and achieve better scalability. The PoS model was originally applied in the chain blockchain model as an alternative to the Nakamoto consensus. The PoS model simulates the working process of PoW by randomly selecting stakers and granting them the right to create a single block in proportion to their stake.
However, many people don't realize that this can lead to two major problems: harmless attacks and long-range attacks.
Nothing-at-stake attacks occur when two miners create blocks at almost the same time, and the network must decide which competing chain to adopt based on the longest chain rule. In a PoW network, we will choose the longest chain with the most work - that is, the chain that has consumed the most resources external to the system economically. In PoS, choosing the right chain requires no external resources, so there is no natural opportunity cost. Since there is no opportunity cost, stakers can bet on every version of the chain, causing the security of the system to collapse. Rational stakers will expand to every possible chain they see to maximize their returns.
A long-range attack occurs when an adversary obtains the keys of past validators through bribery and rewrites the blockchain history, i.e., creates a false network history.
To address nothing-at-stake attacks, Vitalik Buterin proposed the concept of Slasher: if stakers sign blocks of the same height on two forks, they lose their block rewards. However, Vlad Zamfir and Ethan Buchman added an additional feature to Slasher - the pledge bond. In this way, nodes that clearly violate the rules will have their pledge bonds slashed instead of just giving up part of their profits, which is a greater punishment. These improvements were later incorporated into Ethereum's Gasper consensus model and proved that the value of ETH as a PoS asset is only guaranteed by mandatory pledge bonds and slashing penalties - if ETH is not locked, there is no economic value that can support Ethereum.
In other words, the value of ETH is not created through the unforgeable cost of proof of work, but is maintained by force, which is very similar to our current fiat currency system, so it cannot operate as hard currency. Bitcoin is unforgeable because it costs a lot to produce new Bitcoins through capital expenditures (such as hardware mining machines) and operating expenses (such as electricity). It is very difficult to forge Bitcoin because the forger needs to redo all the previous expensive proofs of work and the speed must exceed all the continuous proofs of work in the network.
Frankenstein: Ethereum’s Gasper
Gasper aims to rely on the design of the synchronous communication model based on the longest chain rule model and the partial synchronous communication model of the classic BFT model in the PoS network. The former is implemented through LMD GHOST (latest message driven most greedy and heaviest observation subtree), which is a generalization of the longest chain rule; the latter is implemented through Casper FFG (Friendly Finality Gadget). LMD GHOST is a variant of GHOST and is part of the inclusive protocol proposed by Sompolinsky and Zohar, the creators of the Kaspa network, in "Security of High-Speed Transaction Processing in Bitcoin". In Ethereum, LMD GHOST operates as a fork selection rule. At each fork, the validator chooses the chain with the most support (i.e., the most recent messages received) from all validators, rather than the longest chain. In the GHOST model of the PoW network, support refers to the chain with the most work. In LMD GHOST, support refers to the chain with the most votes (participants get votes weighted according to their staked ETH balance).
Ethereum also has checkpoint nodes to introduce accountability, and if validators violate the rules of the system, they will be fined, and the fine will depend on the specific violation. Casper FFG is a derivative of Vlad Zamfir's paper "Friendly Little Ghosts: A Correctly Built Blockchain Consensus Protocol". However, Ethereum decided to implement Casper as a finality gadget as an additional security layer on top of the probabilistic liveness chain, namely LMD GHOST. Therefore, Casper FFG can also ensure the security of proposed blocks during network partitions. However, since Casper FFG operates according to a partial synchrony model, finality can only be achieved when less than 1/3 of the total number of validator sets are faulty/adversarial, that is, its fault tolerance is 1/3. Since Casper FFG provides accountable security, it does not have a general, deterministic liveness itself, but provides a new, weaker form of probabilistic liveness.
As Vitalik puts it, “Trustworthy liveness means that the algorithm should not get stuck in a state where it cannot finalize anything.”
Gasper also implements weak subjective checkpoints as a measure to prevent long-range attacks. The history of the Gasper blockchain before the weak subjective checkpoint cannot be revoked, that is, if a node receives a block that conflicts with the checkpoint, it will reject the block, preventing long-range attacks. One problem with weak subjectivity is that new or rejoining nodes must trust and rely on other nodes to obtain the correct updated state of the system, which contradicts the goal of decentralization, which is to build a trustless system. Proof of Work operates according to objectivity, and new nodes can independently come to the same conclusions as the rest of the network, thus achieving a trustless system.
So while Ethereum’s Gasper combines synchronicity with partial synchronicity and liveness with safety, this comes at the expense of many other features, primarily stemming from the pursuit of mandatory proof of stake.
The main problems with PoS
First, by abandoning the realization of Nakamoto consensus, it replaces the costliness of being unforgeable with a mandatory deposit, creating a weak form of economic value. Second, it implements slashing penalties, including offline penalties. Although the offline penalty is small and may only be equivalent to the opportunity cost of missing rewards, the dynamic availability is still limited. Third, the weakly subjective verification nodes default to the existence of trust in the system. This goes against the original intention of blockchain technology.
The main problem caused by the difference between safety and liveness
Fourth, instead of improving its fork selection rule (such as LMD GHOST), Ethereum succumbed to the erroneous artificial distinction between liveness and safety in the protocol. In other words, instead of enhancing the network's self-healing ability, Ethereum used Casper FFG, a tool for the classic BFT consensus.
This leads to the fifth problem, Casper FFG can only achieve a 1/3 fault tolerance. While this is the highest fault tolerance in the partial synchronization model, it is indeed a limitation. As we will see, DAG-KNIGHT can do better.
Finally, Gasper introduces a high level of complexity that compromises the security, immutability, and ability of ETH as a currency at the base layer. This endless pursuit of complexity creates a "Frankenstein-like" system.
Summary: Bitcoin, Classic BFT, and Ethereum
Bitcoin is able to achieve high 1/2 fault tolerance, but this comes at the expense of modeling and scalability for the real world (such as Internet latency, network outages, and unexpectedly long attacks). Therefore, Bitcoin cannot be an effective medium of exchange because reducing its upper limit latency to achieve faster transaction rates would compromise its safety and security.
On the other hand, classic BFT models favor security at the expense of dynamic availability and self-healing during network partitions or attacks. In addition, since classic BFT models rely on a partially synchronous communication model, they can only achieve 1/3 fault tolerance.
Ethereum attempts to combine the advantages of the longest chain model and the classic BFT model, but the result is the creation of an unnecessary monstrous self-destructive system.
DAG-KNIGHT: LORD OF TIME
DAG-KNIGHT achieves 1/2 fault tolerance in a partially synchronous model. It is important to note that Cynthia Dwork, Dwork, Lynch, and Stock formally proved that it is impossible to achieve more than 1/3 fault tolerance in a partially synchronous model, and Shi and Pass further formalized this in their paper "Hybrid Consensus". Now, let's explain how DAG-KNIGHT does this.
First, you need to understand how GHOST-DAG works and how DAG-KNIGHT builds on it. Relevant information can be found in the subsections on Spectre, Phantom, and GHOST-DAG. I describe in detail how GHOST-DAG solves this problem in my article How to Solve the Blockchain Trilemma: The Friendship of BlockDAG and Nakamoto Consensus.
Achieving the Impossible: DAG-KNIGHT and Partial Synchronicity
DAG-KNIGHT solves the impossibility result proposed by Dwork et al. by maximizing the use of PoW. Proof of Work decouples the transaction ordering protocol from the finality protocol. The consensus model determines how transactions are ordered, such as Bitcoin's longest chain rule and DAG-KNIGHT's ordering rules, and these rules are canonical algorithms that all participants (including adversarial nodes) operate in the same way. On the other hand, the finality of transactions is a non-binding procedure that each user configures or calculates based on their local beliefs about the system.
In Bitcoin, this default time is based on the assumption α that the attacker has 10% of the total hash rate of the network, and that nodes are willing to take a risk ε < 0.1. However, nodes will also react accordingly based on their local system beliefs. For example, if a Bitcoin node believes that a malicious miner has less than 1/3 of the hash rate, then the node will confirm transactions faster than a node that believes the cap is 49%, allowing a 34% attacker to harm the former but not the latter.
Another example of a proof-of-work that decouples ordering from finality is Spectre, a DAG ordering algorithm that partially synchronizes PoW blocks. In Spectre, nodes must configure a separate parameter to specify their latency limit d, which is unknown to the rest of the system. Furthermore, each node is responsible for the d it chooses, and too inaccurate a choice could harm them. For example, if a node overestimates d, it fails to recognize irreversible transactions; if a node underestimates d, it accepts transactions too early. However, Spectre cannot achieve high liveness.
DAG-KNIGHT exploits this property of proof of work to make its transaction ordering rules indifferent to latency, while transaction finality depends on the latency upper bound configured locally by the user. It is therefore partially synchronous in this sense. Responsiveness is a key feature in the classical partially synchronous communication model, and there are two forms of responsiveness depending on how the protocol consensus model responds to latency. A strong responsiveness comes from a protocol that can confirm transactions based on the observable latency of the network. The other weak responsiveness is when the protocol runs tightly under the maximum latency currently imposed by network adversaries. DAG-KNIGHT works in the latter way and is therefore able to bypass Dwork's impossibility result.
As the DAG-KNIGHT paper states: "In KNIGHT, it is not sufficient to set an upper bound on the locally observed latency; instead, the upper bound should reflect the maximum latency that an attacker could inflict. Even if a message currently propagates perfectly within 1 or 2 seconds, if an attacker could compromise the network so that messages take at most 30 seconds to get through, a client should set D to 30 seconds."
While this may seem like a limitation, the ability to implement weak responsiveness creates the first consensus model that achieves 1/2 fault tolerance under partial synchrony, breaking the impossible result.
Breaking the Impossible: What Does It Mean?
As a generalization of the longest chain rule of the Nakamoto consensus, DAG-KNIGHT achieves dynamic availability, probabilistic finality, and self-healing capabilities. However, DAG-KNIGHT achieves finality faster than Bitcoin, and therefore security faster. That is, the probability of reorganization approaches zero faster, thus achieving finality faster. This means that 100 blocks can be generated per second, and miners receive subsidies and no-conversion-fee block rewards faster, thus becoming a completely decentralized system, making solo mining more efficient.
Unlike the classic BFT model, DAG-KNIGHT does not stop running during network partitions, while achieving the highest possible fault tolerance of 1/2, while the BFT model can only achieve 1/3. In addition, unlike Bitcoin, DAG-KNIGHT can simulate the asynchronicity of the real world, avoiding long timeouts and performance degradation while ensuring security under low latency boundaries. Therefore, Bitcoin cannot be an ideal medium of exchange because reducing its upper limit latency to increase transaction speed will compromise security and protection. DAG-KNIGHT can create the first reserve currency of the stateless future world.
Furthermore, DAG-KNIGHT implements this framework as a non-dual consensus model, rather than continually adding more layers like Ethereum's Casper FFG. DAG-KNIGHT achieves simplification by only improving the fork selection rule of its base layer, which is a big step away from the complex Ethereum-style "Frankenstein" monster. Simplification allows for faster and safer development, and DAG-KNIGHT achieves simplification through strong economic value: a. Assets based on proof of work that cannot be forged; b. Strong objectivity, which eliminates the trust problem in Ethereum's weak subjectivity model.
Finally, DAG-KNIGHT further decentralizes PoW because α, ε, and δ are determined and fixed locally by nodes, rather than by a central rule like Bitcoin’s cap delay, indirectly solving what Friedrich Hayek called the local knowledge problem. Each person has some unique information advantage that can only be most effectively exploited when decisions rely on that information. Therefore, individuals (or in our case, nodes) have unique information based on their specific circumstances at a particular time and place, and planning (especially economic planning, for Hayek, but this can also involve α, ε, and δ) is best done by individual participants in a distributed manner, because centralized planning lacks this information and cannot accurately take into account the knowledge of every individual.
Conclusion: Kaspa's future consensus model DAG-KNIGHT solves the impossible results that Bitcoin, Ethereum and the classic BFT model cannot achieve, and as a partially synchronous model, it has the highest possible fault tolerance bounds. DAGKNIGHT provides stronger security, scalability and decentralization than any other protocol. No other protocol has officially achieved such a feat, and perhaps no other protocol can do it again. Therefore, Kaspa is truly the Lord of Time.
