區塊鏈節點使用共識引擎在區塊鏈狀態上達成統一。本文介紹了區塊鏈系統中共識的基本原理，共識如何與 Substrate 框架中的 runtime 互動，以及框架中可用的共識引擎。
狀態機和衝突
區塊鏈 runtime 是一個狀態機[1]。它有一些內部狀態和狀態轉換功能，允許它從當前狀態轉換到未來狀態。在大多數 runtime 中，有些狀態具有到多個未來狀態的有效轉換，但必須選擇一個轉換。
區塊鏈必須在以下幾方面達成一致：
一些初始狀態，叫做“創世”
一系列的狀態轉換，每個都稱為“區塊”
最終（當前）狀態
為了對轉換後的結果狀態達成一致，區塊鏈的狀態轉換功能[2]中的所有操作都必須是確定性的。
衝突排除
在中心化系統中，中心化的許可權透過按照他們看到的順序記錄狀態轉換，在相互排斥的備選方案中進行選擇，並在發生衝突時選擇競爭備選方案中的第一個。在去中心化系統中，節點將看到不同順序的交易，因此它們必須使用更精細的方法來排除交易。更復雜的是，區塊鏈網路力求容錯，這意味著即使某些參與者不遵守規則，系統也應繼續提供共識的資料。
區塊鏈將交易批處理成區塊，並有一些方法來選擇哪個參與者有權提交區塊。例如，在 PoW 鏈中，首先找到有效工作證明的節點有權向鏈提交塊。
Substrate 提供多種區塊構造演算法，還允許你建立自己的：
Aura (Round Robin)
BABE (基於插槽)
PoW
分叉選擇的規則
作為一個基元，區塊包含一個區塊頭和一批外部物件[3]。區塊頭必須包含對其父塊的引用，以便可以跟蹤鏈的起源。當兩個區塊引用同一父塊時，會發生分叉。必須解決分叉，以便只存在一個規範鏈。
分叉選擇規則是一種演算法，它獲取一個區塊鏈並選擇“最佳”鏈，從而選擇應該擴充套件的鏈。Substrate 透過SelectChain 展現了這個概念。
Substrate 允許你編寫一個自定義的分叉選擇規則，或使用一個現成的。例如：最長鏈規則
最長鏈規則簡單地說，最好的鏈就是最長的鏈。Substrate 用LongestChain 結構提供這個鏈選擇規則。GRANDPA 用最長鏈規則進行投票。
GHOST 規則
GHOST 規則就是，從創世塊開始，透過遞迴地選擇在其上構建塊最多的分支來解決每個分叉。
區塊生產
區塊鏈網路中的某些節點能夠生成新的區塊，這一過程稱為 authoring。具體哪些節點可以編寫區塊取決於你使用的共識引擎。在一箇中心化的網路中，一個節點就可以編寫所有的區塊，而在完全無許可權的網路中，演算法必須在每個高度選擇區塊的生產者。PoW
在像比特幣這樣的 PoW 系統中，任何節點都可以在任何時候生成一個塊，只要它解決了計算密集的問題。解決這個問題需要 CPU 時間，因此礦工只能根據計算資源的比例生成塊。
Substrate 提供了一個 PoW 塊生產引擎。插槽
基於插槽的共識演算法必須有一組已知的驗證人，這些驗證人可以生成塊。時間被分配到不同的插槽中，在每個插槽中只有一些驗證人可以產生塊。在每個插槽中，驗證人可以編寫塊的細節因引擎而異。Substrate 提供 Aura 和 Babe，這兩個都是基於插槽的區塊生產引擎。
最終性
任何系統中的使用者都想知道他們的交易何時完成，區塊鏈也不例外。在一些傳統的系統中，最終性發生在收據被移交或檔案被簽署時。
使用到目前為止描述的區塊生產方案和分叉選擇規則，交易永遠不會完全完成。總有一個機會，一個較長（或較重）的鏈將出現，並恢復你的交易。然而，在一個特定的塊上構建的塊越多，它被還原的可能性就越小。這樣，塊生產和適當的分叉選擇規則提供了概率的最終性。
當需要確定的最終性時，可以向區塊鏈的邏輯中新增一個終結性小工具。一個固定許可權集的成員鑄造最終性的投票，當對某個區塊投了足夠的票時，該區塊被視為最終的。在大多數系統中，這個閾值是 2/3。如果沒有外部協調（如硬分叉），由此類小工具完成的塊將無法恢復。“
一些共識系統將出塊和最終性聯絡在一起，例如，最終性是出塊過程的一部分，在塊 N 完成之前，不能生成新的塊 N+1。然而，Substrate 分離了這兩個過程，並可以單獨使用任何具有概率終結性的出塊引擎，或者將其與最終性小工具耦合以獲得確定性的最終性。
在使用最終性小工具的系統中，必須修改分叉選擇規則以考慮最終性遊戲的結果。例如，節點將選擇包含最近完成的塊的最長鏈，而不是選擇最長鏈的週期。
Substrate 中的共識
Substrate 框架附帶了幾個共識引擎，這些引擎提供了塊生產或最終性。本文簡要概述了 Substrate 本身自帶的產品。歡迎開發者提供自己的定製共識演算法。Aura
Aura[4]提供基於插槽的塊生產機制。在 Aura 中，一個已知的許可權集輪流出塊。BABE
BABE[5]是透過一組已知驗證人的基於插槽的塊生產共識。在這些方面它類似於 Aura。與 Aura 不同，插槽分配基於可驗證隨機函式（VRF）的評估。為每個驗證人分配一個 epoch 的 weight。這個 epoch 被分成多個插槽，驗證人在每個插槽計算它的 VRF。對於驗證人的 VRF 輸出低於其 weight 的每個插槽，允許生成一個塊。
因為多個驗證人可能會在同一個插槽中產生一個塊，所以分叉在 BABE 中比在 Aura 中更常見，即使在良好的網路條件下也很常見。
當在給定的插槽內沒有區塊的生產者時，Substrate 的 BABE 實現也有一個後備機制。這些 “次要” 插槽分配允許 BABE 獲得恆定的區塊時間。PoW
PoW 塊的生產不是基於插槽的，也不需要已知的許可權集。在 PoW 中，任何人都可以在任何時候生成一個塊，只要他們能夠解決一個具有計算挑戰性的問題（通常是找出雜湊原像）。這個問題的難度可以調整為提供一個統計目標塊時間。GRANDPA
GRANDPA[6]提供區塊的最終性。它有一個像 BABE 一樣的已知 weight 的許可權集。然而，GRANDPA 並不生產塊，它只聽取由生產引擎（比如上面三種）生成的塊的“八卦”。GRANDPA 驗證人在鏈上投票，而不是在區塊上投票，也就是說，他們投票給一個他們認為“最好”的區塊，並且他們的投票可以傳遞地應用到之前的所有區塊。一旦超過三分之二的 GRANDPA 許可權者投票支援某一特定區塊，它就被認為是最終的。與 Runtime 協調
最簡單的靜態共識演算法完全在 runtime 之外工作，正如我們目前所描述的那樣。然而，許多共識遊戲透過新增需要與 runtime 協調的功能而變得更加強大。例如，包括 PoW 中的可調難度、權威證明中的許可權輪換以及 PoS 網路中的基於 stake 的權重。
為了適應這些共識特徵，Substrate 有一個 DigestItem 的概念，一個從節點的外部（共識所在的地方）傳遞到 runtime 的訊息，反之亦然。
瞭解更多
因為 BABE 和 GRANDPA 都在波卡網路中使用，Web3 基金會提供了研究級別的演算法演示。
BABE Research[7]
GRANDPA Research[8]
所有確定性的最終性演算法，包括 GRANDPA，都需要至少2f + 1 個非故障節點，其中f是故障或惡意節點的數量。你可以在有缺陷的情況下達成一致[9]的開創性論文或維基百科：拜占庭錯誤[10]中，瞭解更多關於這個門檻的來源以及為什麼它是理想的。
並非所有的共識協議都定義了一個單一的規範鏈。當具有相同父塊的兩個塊沒有衝突的狀態更改時，一些協議驗證有向無環圖[11]（DAG）。
原文：https://substrate.dev/docs/en/knowledgebase/advanced/consensus
翻譯：PolkaWorld 社羣參考連結
[1]
狀態機: https://en.wikipedia.org/wiki/Finite-state_machine[2]
狀態轉換功能: https://substrate.dev/docs/en/knowledgebase/runtime/index[3]
外部物件: https://substrate.dev/docs/en/knowledgebase/learn-substrate/extrinsics[4]
Aura: https://crates.parity.io/sc_consensus_aura/index.html[5]
BABE: https://crates.parity.io/sc_consensus_babe/index.html[6]
GRANDPA: https://crates.parity.io/sc_finality_grandpa/index.html[7]
BABE Research: https://research.web3.foundation/en/latest/polkadot/BABE/Babe.html[8]
GRANDPA Research: https://research.web3.foundation/en/latest/polkadot/GRANDPA.html[9]
缺陷的情況下達成一致: https://lamport.azurewebsites.net/pubs/reaching.pdf[10]
維基百科：拜占庭錯誤: https://en.wikipedia.org/wiki/Byzantine_fault[11]
有向無環圖: https://en.wikipedia.org/wiki/Directed_acyclic_graph
