詳解Kaspa共識模型DAG-KNIGHT：如何在部分同步模型中實現1/2的容錯率
原文來源：KasMedia
原文標題：THE MASTER OF TIME: HOW DAGKNIGHT SOLVES AN IMPOSSIBILITY RESULT UNACHIEVABLE BY BITCOIN, ETHEREUM AND CLASSICAL BFT MODELS
原文作者：Nicholas Sismil，前 Binance.US 上幣部門研究負責人
觀點：在區塊鏈和分散式系統理論中存在著一個廣為人知的一個著名不可能結論：在一個不完全同步的通訊模型下，任何協議或網路都無法實現1/2 的容錯率。這是比特幣、以太坊和經典BFT 模型等其他任何協議都無法解決的問題，但是 Kaspa 將實現的共識模型 DAG-KNIGHT 可以。解決這個問題的關鍵在於在模擬現實世界的進程中實現一種極強的網路正確性（例如在面對延遲和其它幹擾因素時），從而成為網路中的時間之主。
在本文中，我將主要探討這些問題：
1. 分散式系統的本質；
2. 如何平衡正確性、時效性和容錯率？ ；
3. 最終性與動態可用性（即機率最終性vs. 絕對最終性）；
4. 比特幣、經典BFT 模型和以太坊在這些屬性上的表現及其不足；
5. DAG-KNIGHT 如何突破這個不可能性結果，解決其他所有協議的不足；
6. 最後總結DAG-KNIGHT 如何成為時間的主宰，以及這對分散式系統理論意味著什麼。
分散式系統的定義
分散式系統有多種定義。 Leslie Lamport 在1987 年的一次交流是這樣描述的：在一個分散式的系統中，發生在一台你甚至不知道存在於系統中的電腦上的故障都可能導致你自己的電腦無法使用。 Imran Bashir 在他的《區塊鏈共識》一書中則將分散式系統定義為透過訊息傳遞網路為以實現共同目標自主協同工作的匿名電腦的集合。
從根本上說，分散式系統的目標是使其所有的組成部分就係統的整體狀態達成一致——即達到共識。儘管 Facebook、Google、推特、亞馬遜等是中心化管理的企業，但他們採用的都是分散式系統（還有萬維網）。在本文中，我將討論由區塊鏈、分散式帳本和區塊有向無環圖（blockDAG）構成的另外一種分散式系統的歷史發展過程。
首先，我們需要了解分散式系統的幾個核心屬性：正確性、時效性和系統內部容錯率。
分散式系統中的正確性、時效性和容錯性
Leslie Lamport 在《證明多處理程序正確性》中定義了分散式系統正確性的概念。他認為，一個想要具備正確性的分散式系統必須同時具備活躍度和安全性。安全性是指無法撤銷已做出的決定，而活躍度是指無法無限期地延遲做出決定。換句話說，安全性保證了不同的誠實節點永遠不會做出不同的決定，而活躍度則保證了每個誠實節點都將最終做出一個決定。
我們將看到，一些分散式系統更傾向於保證活躍度，而有些則更傾向於保證安全性。
時效性和容錯性
時效性反映了分散式系統中的通訊行為模型。通訊模型包括關於網路延遲和處理器延遲及速度的設定。這些設定本質上決定了網路對抗者在系統中能夠控制訊息延遲的程度。換句話說，通訊模型定義了網路對抗者乾擾通訊的能力極限。
根據同步方式不同，有三種主要的通訊模型：（完全）同步、非同步和部分同步。每種模型決定了系統的容錯率，即通訊模型決定了協定是否能夠抵禦 1/3 或 1/2 的錯誤率。
（完全）同步模型
在同步模型中，存在一個預先已知的最大訊息延遲界限∆，所有訊息必須在這個時間內送達，網路中的所有參與者都知道訊息送達所需的時間。因此，對手最多只能延遲訊息的送達時間至δ。舉例而言，比特幣採用同步模型，那麼按照最長鏈規則操作，該規則遵循每個區塊的最大延遲L，L 會不斷更新並始終確保區塊到達的時間約為10 分鐘，即上限延遲∆為10 分鐘。
同步系統簡單並能提供強大的正向結果。但它們太嚴格，難以在不損害安全性的情況下有效模擬現實世界（如網路中斷和意外長時間攻擊）。例如，設定一個較長的延遲∆可以提供代表現實世界的強正結果，但會導致長時間超時和效能下降。相反，設定一個較短的延遲∆可以提高效能，但可能無法準確模擬現實世界，從而損害安全性。換句話說，如果網路參與者高估延遲，系統運作會比實際情況慢；反之，系統則不夠安全。
此外，嘗試在兩者之間找到一個理想的平衡並不容易。例如，如果發送者廣播一則訊息給兩個接收者，一則訊息在∆−ϵ後到達，另一則訊息在∆+ϵ後到達，那麼現實世界中的行為就會與模型設定所希望不同，這會損害系統的安全性。
儘管同步模型有這些問題，它仍能達到 1/2 的最高容錯界線。這是因為我們可以假設系統中的每個節點在固定時間內都能看到每一次投票，從而達成共識。具體來說，如果系統中有 n 個節點，其中 f 個是故障節點，我們希望至少有 f+ 1 個正確節點的訊息能夠超過 f 個故障節點的訊息。一旦所有訊息都收到，根據同步模型，這樣的共識就能達成。
即如果：
n ≥ f+(f+ 1)
f ≤ (n-1)/2
f < n/2
那麼最大的容錯率達到½。
非同步模型
非同步模型試圖透過不對網路延遲做任何假設來克服同步模型遇到的問題：即使正常運作的節點間也沒有網路延遲的限制。這樣有兩個優點：首先，沒有通訊時間限制，不同步（遲到的）訊息就不會意外損害安全性；其次，由於沒有固定的超時時間，節點就可以適應系統實際發生的延遲而仍保持活躍。
然而，這也帶來了一些代價。 Fischer、Lynch 和 Patterson 在其論文《具有一個故障進程的分散式一致不可能性》中提出了一個不可能性定理，在非同步模型下，即使只存在一個故障節點，也無法保證一致性。換句話說，在非同步模型中，只要一個錯誤的節點就足以使一致性變得不可能。
儘管如此，在隨機演算法下，在 t 秒內達到一致性是可能的，因為隨著 t 的增長，一致性的機率會以指數方式接近 1 。因此，非同步可能一致性演算法只能達到 1/3 的容錯率，而不是½。
此外，Eric Brewer 證明了一致性（安全性）、活躍度和分區容忍性（partition tolerance）這三者在非同步分散式系統中不能同時存在。分區容忍性是指保證系統在網路在分區期間（某些節點之間的訊息無法傳遞）仍能運作。因此，在非同步系統中，有一個三難困境──必須在安全性、活躍度和分區容忍性三者中選擇其二，而不能全部兼得。
儘管該定理適用於非同步模型系統，但網路分區仍然遵守非同步假設並在所有時序模型中都會出現。因此，無論使用何種模型，系統在網路分區期間必須要專注於活躍度，或是專注於安全性。
部分同步模型
系統有兩種方式實現部分同步。第一種方式是，當系統正常運作時採用同步模型，在發生故障（如網路故障或攻擊）時切換到非同步模型。這種方式假設存在一個觀測全域網路的時鐘，且參數∆指定了同步階段訊息可能發生的最大延遲。然而在非同步階段，參數∆不起作用，全域穩定時間（GST）決定了通訊模型從同步切換到非同步的時間點。這種版本稱為 GST 版本。
第二種方式是假設訊息傳遞沒有已知的邊界，而是存在一個未知的有限上限δ，這個上限可以由網路對抗者選擇。在這種版本中，不存在 GST，也沒有非同步和同步階段之間的切換。相反，訊息將始終在∆時間步內傳遞，就像在同步模型中一樣。
特別值得一提的是，無論哪種部分同步模型都具有 1/3 的容錯率。正如 Dwork、Lynch 和 Stock 的工作中正式證明的不可能性結果那樣，部分同步模型不能實現 1/2 的容錯率。
最終性和動態可用性
歷史上協議分為兩類：基於最長鏈的協議和經典 BFT 共識協議。前者採用同步模型，遵循中本聰共識，即最長鏈規則：當鏈之間存在分歧時，選擇最長的鏈。後者採用部分同步模型，基於狀態機複製進行操作，隨機選擇驗證者來提議區塊，並透過多輪投票決定是否將區塊納入鏈中。每輪投票中，所有誠實且線上的驗證者會對特定區塊進行表決。
與基於最長鏈的協議不同，BFT 共識協議對區塊的產生不依賴鏈的長度或大小。 BFT 共識偏向安全性而非活躍度，並提供絕對最終性，即係統內所做的決定永遠不會被撤銷。然而，由於偏重安全性，經典 BFT 模型無法實現動態可用性。經典 BFT 共識模型包括 Tendermint、PBFT 和 HotStuff 模型。
另一方面，基於最長鏈的協定（包括比特幣和其泛化版本 GHOST）無法實現絕對最終性，而是透過動態可用性來達到機率最終性。動態可用性允許節點在任何時間加入或離開系統，而不影響系統的安全性。因此，動態可用性體現了真正的無許可性——節點不會因停機或技術故障而受到懲罰。此外，在網路分區或攻擊期間，即使參與度較低，動態可用協定仍能做出決定。
許多人認為基於最長鏈的協定偏重活躍度而非安全性，但這並不完全正確。這一點非常重要。在透過機率實現活躍度的模型中，活躍度和安全性的區分是人為且具有誤導性的，因為在機率上實現活躍度的模型中，安全性和活躍度是相互依存的。
人們可能會認為絕對最終性優於機率最終性，但情況並非如此，因為每種模型在處理分區問題時有所不同。在經典 BFT 共識系統中，如果在分區期間參與度過低，可能達不到規定所需的人數，從而無法完成所需的投票，導致區塊鏈停滯。然而，即使活躍參與者數量減少到一個，只要始終存在誠實的多數，基於最長鏈的系統在分區期間就不會停止運作。相反，在這種情況下，帳本的網路輸出仍會繼續增加，並具備自動糾錯的能力：即使節點在最初存在分歧，網路最終也將收斂並達成共識。這種糾錯能力與網路安全性的強弱有關。
正如Neu 等人所示，在相同環境下模擬經典BFT 模型和最長鏈模型時，在動態參與且網路分區的情況下，最長鏈協定的帳本網路輸出總是持續增長，而經典BFT 協定的最終性在低參與度或分區期間會停滯。
因此，雖然經典 BFT 共識模型提供了安全性和絕對最終性，但其代價是網路中斷時無法自我療癒或恢復。此外，這也犧牲了系統無需許可（permissionless）的特點，導致系統中心化。例如，一些 BFT 協定要求節點必須保持在線，否則將受到懲罰。相當一部分類似的規則毫無疑問是不符合去中心化網路的設計思想的。
以太坊：PoS 的廣泛應用與陷阱
許多人希望擺脫 PoW 網路以節省電力和硬體成本，並實現更好的可擴展性。 PoS 模型最初是作為中本聰共識的替代方案在鍊式區塊鏈模型中應用。 PoS 模型透過隨機選擇質押者，並按其權益比例賦予創建單一區塊的權利，來模擬 PoW 的工作流程。
然而，許多人沒有意識到這會導致兩個主要問題：無利害攻擊和長程攻擊。
無利害攻擊發生在兩個礦工幾乎同時創建區塊時，網路必須根據最長鏈規則決定採用哪條競爭鏈。在 PoW 網路中，我們將選擇具有最多工作量的最長鏈——即在經濟上消耗了最多系統外部資源的鏈。而在 PoS 中，選擇正確的鏈不需要外部資源，因此沒有自然的機會成本。由於沒有機會成本，質押者可以在每個鏈的版本上下注，導致系統的安全性崩潰。理性的質押者會擴展到他們看到的每條的可能的鏈上去以最大化回報。
長程攻擊發生在對手透過賄賂獲得過去驗證者的金鑰，重新編寫區塊鏈歷史，即創建虛假的網路歷史。
為了解決無利害攻擊，Vitalik Buterin 提出了Slasher 的概念：如果質押者在兩個分叉上簽署相同高度的區塊，他們就會失去區塊獎勵。然而，Vlad Zamfir 和Ethan Buchman 為Slasher 添加了額外的功能——質押保證金。這樣，明顯違規的節點會被削減其質押保證金，而不是僅僅放棄部分利潤，這是更大的懲罰。這些改進後來被納入以太坊的Gasper 共識模型，並證明了ETH 作為 PoS 資產的價值僅通過強制質押保證金和削減懲罰來保障——如果不鎖定ETH，就沒有能支持以太坊的經濟價值。
換句話說，ETH 的價值不是透過工作量證明的無法偽造的成本性創造的，而是被強制維持的，這與我們今天的法幣系統非常相似，因此無法作為硬通貨運作。比特幣則具有無法偽造的成本性，因為透過資本支出（如硬體礦機）和營運支出（如電力）來生產新的比特幣需要花費大量成本。偽造比特幣非常困難，因為偽造者需要重做之前所有的昂貴工作量證明，而且速度要超過網路中的所有持續工作量證明。
科學怪人：以太坊的 Gasper
Gasper 旨在依靠 PoS 網路結合基於最長鏈規則模型的同步通訊模型和經典BFT 模型的部分同步通訊模型的設計。前者透過LMD GHOST（最新消息驅動的最貪婪最重的觀察子樹）實現，是一種最長鏈規則的泛化；後者透過Casper FFG（友好的最終性小工具）實現。 LMD GHOST 是GHOST 的變種，也是Kaspa 網路的創建者 Sompolinsky 和Zohar 在《比特幣中高速交易處理的安全》中提出的包容性協議的一部分。在以太坊中，LMD GHOST 作為分叉選擇規則運作，每個分叉處，驗證者選擇得到所有驗證者最多支持（即收到最多最新消息）的鏈，而不是最長鏈。在 PoW 網路的GHOST 模型中，支持指的是工作量最多的鏈。而在LMD GHOST 中，支持指的是獲得最多投票的鏈（參與者根據其質押ETH 餘額加權獲得投票）。
以太坊也設立了查驗區塊節點以便引入問責機制，如果驗證者違反系統規則則會被罰款，罰金將取決於特定的違規情況。 Casper FFG 是Vlad Zamfir 的論文《友善的小幽靈：正確建構的區塊鏈共識協議》衍生產物。然而，以太坊決定將Casper 作為最終性小工具實現，作為機率活躍度鏈頂層的額外安全層，即LMD GHOST。因此，Casper FFG 在網路分區期間也能確保提議區塊的安全性。然而，由於Casper FFG 依照部分同步模型運作，只有當驗證者集的總數中少於 1/3 故障/對抗性時，才能實現最終性，即其容錯性為 1/3 。由於Casper FFG 提供可問責的安全性，它本身並不存在一般意義上的、確定的活躍度，而是提供了一種新的、更弱形式的、概率性的活躍度。
正如Vitalik 所說，“可信的活躍度意味著演算法不應陷入無法最終確定任何事物的狀態的擁塞。”
Gasper 也實施了弱主觀檢查點作為防範長程攻擊的措施。在弱主觀檢查點之前的Gasper 區塊鏈歷史無法被撤銷，即如果節點接收到與檢查點衝突的區塊，它將拒絕該區塊，防止長程攻擊。弱主觀性的一個問題是，新的或重新加入網路的節點必須信任和依賴其他節點以獲得系統的正確更新狀態，這與去中心化的目標相矛盾，即建立一個無需信任的系統。工作量證明則是依照客觀性運作，新節點可以獨立得出與網路其他部分相同的結論，從而實現無需信任的系統。
因此，儘管以太坊的Gasper 融合了同步性與部分同步性和活躍度與安全性，但這是以犧牲許多其他特性為代價的，主要源於對強制權益證明的追求。
PoS 帶來的主要問題
首先，由於放棄實現中本聰共識，它用強制保證金取代了無法偽造的成本性，創造了一種弱經濟價值形式。其次，它實施了削減懲罰，包括離線懲罰。儘管離線懲罰很小，可能只相當於錯過獎勵的機會成本，但動態可用性仍然有限。第三，弱主觀性的查驗節點在系統內默認了信任的存在。 =這違背了區塊鏈技術的初衷。
人為安全和活躍度區別帶來的主要問題
第四，以太坊沒有改進其分叉選擇規則（例如LMD GHOST），而是屈服於協議中錯誤的人為活躍度與安全性區分。也就是說，以太坊沒有增強網路的自我修復能力，而是使用了經典BFT 共識的工具Casper FFG。
這導致了第五個問題，Casper FFG 只能實現1/3 的容錯率。雖然在部分同步模型中，這是最高的容錯率，但它確實是一個限制。正如我們將看到的，DAG-KNIGHT 可以做得更好。
最後，Gasper 引入了高複雜度，這損害了基礎層的安全性、不變性以及ETH 作為貨幣的能力。這種對複雜性的無盡追求創造了一個「科學怪人式」的系統。
總結：比特幣、經典 BFT 和以太坊
比特幣能夠實現 1/2 的高容錯性，但這是以犧牲對現實世界（如網路延遲、網路中斷和意外長時間攻擊）的建模和可擴展性為代價的。因此，比特幣不能成為有效的交換媒介，因為若降低其上限延遲以達到更快的交易速率，會損害其安全性和保障。
另一方面，經典 BFT 模型偏向安全性，犧牲了在網路分區或攻擊期間的動態可用性和自我修復能力。此外，由於經典 BFT 模型依賴部分同步通訊模型，因此它們只能實現 1/3 的容錯性。
以太坊試圖融合基於最長鏈模型和經典 BFT 模型的優點，但結果卻是創造了一個不必要的怪物自毀式系統。
DAG-KNIGHT：時間之主
DAG-KNIGHT 在部分同步模型中實現了 1/2 的容錯率。要知道，Cynthia Dwork、Dwork、Lynch 和Stock 曾正式證明，在部分同步模型中，實現超過1/3 的容錯率是不可能的，Shi 和Pass 在其論文《混合共識》中進一步形式化了這一點。現在，讓我們解釋 DAG-KNIGHT 是如何做到這一點的。
首先，需要了解 GHOST-DAG 的工作原理，以及 DAG-KNIGHT 如何在此基礎上進行建構。相關資訊可以在 Spectre、Phantom 和 GHOST-DAG 的子部分中找到。我在文章《如何解決區塊鏈三難困境：BlockDAG 和中本聰共識的友誼》中詳細描述了 GHOST-DAG 如何解決這個問題。
實現不可能：DAG-KNIGHT 和部分同步性
DAG-KNIGHT 透過最大限度地利用 PoW 解決了 Dwork 等人提出的不可能性結果。工作量證明將交易排序協議與最終性協議分開。共識模型決定如何排序交易，例如比特幣的最長鏈規則和 DAG-KNIGHT 的排序規則，而這些規則是所有參與者（包括對抗性節點）以相同方式運行的規範演算法。另一方面，交易的最終性是一個非約束性程序，每個使用者根據其對系統的本地信念進行配置或計算。
在比特幣中，此預設時間是基於假設α，即攻擊者擁有網路總哈希率的 10 ％，且節點願意承擔<0.1 的風險ε。然而，節點也會依據其本地系統信仰作出相應的反應。例如，如果一個比特幣節點認為惡意礦工擁有不到1/3 的哈希率，那麼該節點將比認為上限為49 ％的節點更快確認交易，這允許34 ％的攻擊者損害前者，但無法損害後者。
另一個將排序與最終性分離的工作量證明的例子是 Spectre，這是一個部分同步 PoW 區塊的 DAG 排序演算法。在 Spectre 中，節點必須配置一個單獨的參數來指定其延遲上限 d，而這個參數是不為系統其他部分所知的。此外，每個節點對其選擇的 d 負責，過於不準確的選擇可能會損害它們。例如，如果一個節點高估了 d，它無法識別不可逆交易；如果一個節點低估了 d，它會過早接受交易。然而，Spectre 無法實現高活躍度。
DAG-KNIGHT 利用工作量證明此特性，使其交易排序規則對延遲無關緊要，而交易最終性取決於使用者本地配置的延遲上限。因此，它在這種意義上是部分同步的。響應性是經典部分同步通訊模型中的關鍵特徵，根據協定共識模型如何回應延遲，有兩種形式的回應性。一種強響應性來自於可以根據網路的可觀察延遲確認交易的協議。另一種弱響應性是指協定在目前由網路對抗者造成的最大延遲下緊密運作。 DAG-KNIGHT 按照後一種方式運作，因此能夠繞過 Dwork 的不可能性結果。
正如DAG-KNIGHT 論文所述：「在KNIGHT 中，僅設定本地觀察到的延遲上限是不夠的，相反，該上限應反映攻擊者可能造成的最大延遲。即使訊息目前完全在1 或2 秒內傳播，但如果攻擊者可能破壞網絡，使訊息最多需要30 秒通過，客戶端應將D 設為30 秒。
雖然這似乎是一個限制，但實施弱響應性的能力創造了第一個在部分同步性下實現 1/2 容錯率的共識模型，打破了不可能的結果。
打破不可能的結果：這代表什麼？
作為中本聰共識最長鏈規則的泛化，DAG-KNIGHT 實現了動態可用性、機率最終性和自我修復能力。然而，DAG-KNIGHT 相較於比特幣能更快實現最終性，因此也能更快實現安全性。也就是說，重組的機率更快地趨向於零，從而更快達到最終性。這意味著每秒可以產生 100 個區塊，礦工獲得補貼和無轉換費用區塊獎勵的速度也更快，從而變成徹底的去中心化系統，使單獨挖礦變得更有效率。
與經典 BFT 模型不同，DAG-KNIGHT 在網路分區期間不會停止運行，同時實現了可能的最高容錯率 1/2 ，而 BFT 模型只能實現 1/3 。此外，與比特幣不同，DAG-KNIGHT 可以模擬現實世界的非同步性，避免長時間逾時和效能下降，同時確保在低延遲界線下的安全性。因此，比特幣無法成為理想的交換媒介，因為降低其上限延遲以增加交易速度會損害安全性和保障。而 DAG-KNIGHT 則可以創造第一個無狀態未來世界的儲備貨幣。
此外，DAG-KNIGHT 作為一個非雙重共識模型實現了這個框架，而不是像以太坊的 Casper FFG 那樣不斷添加更多層。 DAG-KNIGHT 僅僅改進了其基礎層的分叉選擇規則，從而實現了簡化，這是遠離複雜的以太坊式「弗蘭肯斯坦」怪物的一大進步。簡化允許更快和更安全的發展，並且DAG-KNIGHT 透過強經濟價值實現了簡化：a. 基於無法偽造的工作量證明的資產；b. 強客觀性，即消除以太坊弱主觀性模型中的信任問題。
最後，DAG-KNIGHT 進一步去中心化了PoW，因為α、ε和δ是由節點本地決定和確定的，而不是像比特幣的上限延遲那樣的中央規則，間接解決了Friedrich Hayek 所謂的地方知識問題。每個人都有一些獨特的資訊優勢，只有在決策依賴這些資訊時，才能得到最有效的利用。因此，個體（或在我們的情況下，節點）根據其特定時間和地點的情況擁有獨特的信息，計劃（特別是經濟計劃，對於Hayek 來說，但這也可以涉及α、ε和δ）最好由個別參與者以分佈式的方式進行，因為中心化的計劃缺乏這些信息，無法準確地考慮到每一個個體的知識。
結論：Kaspa 的未來共識模型 DAG-KNIGHT 解決了比特幣、以太坊及經典 BFT 模型無法實現的不可能性結果，作為一個部分同步模型，具有可能的最高容錯界限。 DAGKNIGHT 提供了比任何其他協議更強的安全性、可擴展性和去中心化。沒有其他協議正式實現這樣的壯舉，也許也沒有其他協議能再做到。因此，Kaspa 是名符其實的時間之主。
