區(qū)塊鏈導論 課件 第四章：共識算法

第四章：共識算法Chapter4:ConsensusAlgorithm作者:北京大學匯報時間:2024/07/03目錄共識算法概述01RAFT共識算法03共識算法的未來發(fā)展05共識問題02共識算法的應用04思考題06

1.共識算法概述1.Overviewofconsensusalgorithms011.1共識正確性的定義一個正確的共識算法需要滿足以下三個核心特性：一致性（Agreement）：在分布式系統(tǒng)中，所有參與共識的節(jié)點必須對某個決策值達成一致。這意味著即使不是所有節(jié)點都同意同一個決策值，也至少要有大多數(shù)節(jié)點達成共識。一致性確保了系統(tǒng)不會分裂成多個持有不同決策值的子集。有效性（Validity）：最終的決策值必須是系統(tǒng)中某個節(jié)點提出的有效值，而不是一個預設的默認值。有效性確保了共識的結果是基于實際提出的值，而不是一個無關緊要的默認選項。這也有時被稱為正確性，強調(diào)了決策值的正確來源。終止性（Termination）：所有節(jié)點最終都必須完成決策過程。終止性保證了共識算法能夠在有限的時間內(nèi)完成，不會無限期地運行下去，從而確保了系統(tǒng)的穩(wěn)定性和可靠性。1.2共識的通信模型共識的通信模型主要分為以下三類：同步模型（SynchronousModel）：在同步模型中，網(wǎng)絡通信具有已知的延遲上限，即消息傳遞有一個最大延遲時間。每個節(jié)點處理事務的時間有一個已知的最大差異。每輪共識中，節(jié)點都能在預定時間內(nèi)完成任務，如果超時則可以認為節(jié)點發(fā)生故障。同步模型是一種理想化的模型，在實際中很難實現(xiàn)，但早期的共識算法多以此為基礎。異步模型（AsynchronousModel）：異步模型中，消息傳遞的延遲沒有已知的上限，即消息可能無限延遲。節(jié)點處理任務的速度未知，且可能有很大的差異。無法通過超時來判斷節(jié)點是否正常工作，因為延遲可能非常長。異步模型更接近現(xiàn)實世界的網(wǎng)絡環(huán)境，適用于異步模型的共識算法也適用于同步模型，但反之則不成立。FLP不可能定理指出，在純粹的異步模型中，無法設計出總是能夠達成共識的算法。1.2共識的通信模型3.部分同步模型（PartialSynchronyModel）：部分同步模型介于同步模型和異步模型之間。存在一個全局穩(wěn)定時間（GST），在這段時間內(nèi)網(wǎng)絡可以被認為處于同步狀態(tài)，共識可以進行。如果網(wǎng)絡出現(xiàn)問題，共識流程可能終止，但經(jīng)過GST后，網(wǎng)絡會恢復到同步狀態(tài)，共識可以繼續(xù)。這種模型更符合現(xiàn)實世界的網(wǎng)絡環(huán)境，即在大多數(shù)時間內(nèi)網(wǎng)絡是可靠的，偶爾會出現(xiàn)故障。部分同步模型是許多現(xiàn)代共識算法的基礎，如Paxos和PBFT。1.3共識算法的詳細案例分析1.比特幣的PoW（工作量證明）算法原理：礦工通過計算哈希值來競爭記賬權，成功找到符合要求的哈希值后即可添加區(qū)塊。優(yōu)點：高度去中心化，安全性高。缺點：能源消耗巨大，交易確認時間長。2.以太坊的PoS（權益證明）算法原理：通過持有代幣的數(shù)量和時間來決定誰有記賬權，減少了對計算能力的依賴。優(yōu)點：節(jié)能環(huán)保，交易確認速度快。缺點：初期分配不公平，富者恒富。3.PBFT（實用拜占庭容錯）在聯(lián)盟鏈中的應用原理：通過多輪投票機制實現(xiàn)共識，確保系統(tǒng)在有不超過1/3惡意節(jié)點的情況下仍能正常運行。優(yōu)點：高效低延遲，適用于私有鏈和聯(lián)盟鏈。缺點：不適用于公有鏈，擴展性差。2.共識問題2.Consensusissues02問題背景：拜占庭帝國的將軍們必須通過信使來溝通，以達成是“進攻”還是“撤退”的共識。將軍們之間相隔遙遠，無法面對面交流。存在叛徒可能散布虛假信息或發(fā)送矛盾的指令。問題定義：需要找到一個算法，即使在有叛徒的情況下，也能讓忠誠的將軍們達成正確的決策。叛徒的行為被稱為“拜占庭錯誤”。問題復雜性：叛徒可能以任意方式行為，包括發(fā)送矛盾的信息或不發(fā)送信息。忠誠的將軍們必須識別并忽略叛徒的影響。解決方案：拜占庭容錯（BFT）算法提供了一種解決方案。當總節(jié)點數(shù)N大于或等于3倍的叛變將軍數(shù)F加1（N≥3F+1）時，問題有解。2.1拜占庭將軍問題5.共識過程：每個節(jié)點收到提案后，會向其他節(jié)點發(fā)送確認消息以驗證提案的真?zhèn)魏吞岚刚叩纳矸荨Ｈ绻岚腹?jié)點不是叛徒，但收到了F個非正常的確認消息，需要超過2/3的多數(shù)正常確認才能達成共識。如果提案節(jié)點是叛徒，它會發(fā)送矛盾的信息，忠誠的節(jié)點需要通過進一步的驗證和多數(shù)投票來達成共識。6.問題難點：在異步模型中，由于消息傳遞的延遲沒有上限，設計一個總是能夠達成共識的算法是非常困難的。FLP不可能定理表明，在純粹的異步模型中，不存在一個總是能夠達成共識的算法。7.實際應用：拜占庭將軍問題在現(xiàn)實世界中的分布式系統(tǒng)中非常普遍，如區(qū)塊鏈網(wǎng)絡中的節(jié)點共識。該問題的解決方案對于設計能夠在存在惡意行為者的情況下仍然能夠可靠運行的系統(tǒng)至關重要。拜占庭將軍問題的核心挑戰(zhàn)在于如何在不完全信任的網(wǎng)絡中達成共識，并且要能夠抵御來自叛徒的干擾。2.1拜占庭將軍問題2.2FLP不可能定理1.FLP定理影響共識設計FLP不可能定理揭示了分布式系統(tǒng)中實現(xiàn)強一致性共識的困難，對設計高效的共識算法產(chǎn)生深遠影響。2.FLP定理的實用意義FLP定理雖然指出不可能在所有情況下都達成共識，但它為開發(fā)者提供了設計容錯分布式系統(tǒng)的實用指導。3.共識算法回避FLP限制盡管受到FLP定理的限制，但許多共識算法通過異步模型、故障檢測等方法成功地實現(xiàn)了系統(tǒng)級的共識。4.FLP定理的學術價值FLP定理是分布式系統(tǒng)理論的重要里程碑，為后續(xù)分布式計算和共識問題的研究奠定了理論基礎。2.3CAP理論1.CAP理論定義重要性CAP理論定義了分布式系統(tǒng)在設計時需要在一致性、可用性和分區(qū)容忍性之間做出的權衡，是系統(tǒng)設計的基石。2.一致性對網(wǎng)絡延遲敏感CAP理論中的一致性要求數(shù)據(jù)在所有副本中保持一致，對低延遲網(wǎng)絡要求高，現(xiàn)代系統(tǒng)常通過優(yōu)化算法實現(xiàn)最終一致性。3.可用性影響用戶體驗在分布式系統(tǒng)中，即使部分節(jié)點出現(xiàn)故障，系統(tǒng)仍需保持對外提供服務的能力，高可用性直接關聯(lián)用戶滿意度。4.分區(qū)容忍性必不可少隨著分布式系統(tǒng)規(guī)模的擴大，網(wǎng)絡分區(qū)現(xiàn)象不可避免，CAP理論指出設計系統(tǒng)時需確保其在網(wǎng)絡分區(qū)時仍能繼續(xù)運行。5.設計啟示：在共識算法設計中，不必追求同時滿足三種特性，應根據(jù)實際需求做出取舍。例如，比特幣網(wǎng)絡犧牲了強一致性，采用最終一致性，以保證可用性和分區(qū)容錯性，這導致了可能出現(xiàn)分叉和區(qū)塊回退。3.共識算法3.consensusalgorithm033.1.1RAFT概述1.RAFT性能卓越RAFT共識算法以其高效性和容錯性著稱，能夠在分布式系統(tǒng)中快速達成數(shù)據(jù)一致性，確保系統(tǒng)的高可用性。2.故障恢復能力強RAFT通過選舉領導者和日志復制的機制，使得在節(jié)點故障時能夠快速恢復并繼續(xù)服務，保持系統(tǒng)穩(wěn)定性。3.適用性強泛RAFT算法設計簡潔，易于理解和實現(xiàn)，已廣泛應用于多個開源項目和商業(yè)系統(tǒng)，顯示出其強大的適用性和擴展性。4.社區(qū)支持活躍RAFT算法擁有活躍的社區(qū)支持和開源維護，不斷推動算法的演進和優(yōu)化，為用戶提供更優(yōu)質(zhì)的服務。3.1.2RAFT詳細流程1.RAFT的高效性RAFT共識算法通過減少不必要的通信開銷和簡化的日志復制機制，在實驗中表現(xiàn)出顯著的性能提升，適用于大規(guī)模集群。2.RAFT的容錯性RAFT算法通過選舉Leader并允許故障轉移，保證了系統(tǒng)即使在節(jié)點故障時也能繼續(xù)提供服務，具有高度的容錯性。3.RAFT的可理解性相較于其他復雜的共識算法，RAFT算法設計簡潔直觀，易于理解，使得系統(tǒng)開發(fā)和維護更加便捷。Raft初啟動多候選者多領導者無法選出領導者同步過程3.1.3RAFT算法的核心要點問題分解：RAFT將一致性問題分解為領導者選舉（LeaderElection）、日志復制（LogReplication）和安全性（Safety）三個相對獨立的問題。領導者選舉：領導者（Leader）是處理所有客戶端請求的節(jié)點，負責生成日志數(shù)據(jù)并廣播給從節(jié)點（Follower）。從節(jié)點是被動的，僅接收來自領導者的日志數(shù)據(jù)。候選節(jié)點（Candidate）是選舉過程中的過渡狀態(tài)，任何節(jié)點在發(fā)現(xiàn)領導者故障后都可成為候選節(jié)點。3.任期和心跳機制：RAFT通過任期（Term）來管理領導者選舉，每個任期的開始都是一次選舉。使用心跳機制觸發(fā)領導者選舉，領導者通過周期性發(fā)送心跳信息維持其地位。4.日志復制：領導者接收客戶端請求，將命令作為新的日志條目加入日志，并廣播給從節(jié)點復制。從節(jié)點存儲日志條目，領導者確保所有從節(jié)點都存儲了所有日志條目。3.1.3RAFT算法的核心要點5.安全性：RAFT通過任期號和日志匹配原則來確保日志的一致性和安全性。如果領導者的任期號過時，它會轉換為從節(jié)點。6.動態(tài)集群成員變更：RAFT支持動態(tài)改變集群成員，使用聯(lián)合一致性（JointConsensus）方法來處理配置變更。7.簡化管理：日志條目只從領導者發(fā)送給其他服務器，簡化了日志復制的管理。領導者選舉的條件限制為擁有最新、最全日志的節(jié)點，減少了數(shù)據(jù)同步時間。RAFT算法以其清晰的結構和邏輯，使得在實際系統(tǒng)中實現(xiàn)變得相對容易，成為分布式系統(tǒng)中廣泛使用的共識算法之一。3.2.1Pow共識算法1.背景與概述RAFT共識算法的局限性

適用于私有鏈和內(nèi)部互信較高的聯(lián)盟鏈。

未考慮拜占庭節(jié)點（篡改數(shù)據(jù)、不一致消息）的情況。

PoW共識算法的應對方式

增加作惡成本，減少拜占庭行為可能性。

鼓勵正常參與，通過獎勵機制提升參與積極性。2.起源與發(fā)展1993年：辛西婭·德沃克和莫尼·瑙爾首次提出概念。

2008年：比特幣采用PoW作為共識算法，使其廣為人知。3.PoW共識算法核心哈希算法特性

輸入長度任意，輸出為固定長度（y=H(x)）。

正向計算簡單，逆向計算困難（防篡改特性）。數(shù)學難題（Mining）

目標：通過哈希函數(shù)計算小于目標值（`htarget`）的哈希值。

隨機數(shù)（nonce）與區(qū)塊數(shù)據(jù)（data）、上一區(qū)塊哈希值（hprevious）共同參與計算。

難度調(diào)整：通過設置htarget控制計算難度和區(qū)塊生成時間。4.區(qū)塊生成與分叉區(qū)塊生成流程1.收集交易，生成區(qū)塊數(shù)據(jù)。

2.不斷調(diào)整隨機數(shù)nonce直到滿足條件hcurrent<htarget。

3.廣播區(qū)塊，接受全網(wǎng)驗證，通過后獲得獎勵。分叉問題及解決

網(wǎng)絡延遲可能導致多個區(qū)塊同時上鏈。

采用

最長鏈原則：選擇最長的鏈作為主鏈，其他鏈回退，交易重新打包。3.2.2Pow共識算法5.關鍵挑戰(zhàn)與問題51%算力攻擊如果單個節(jié)點算力占全網(wǎng)總算力的51%以上，可篡改鏈條并主導主鏈生成。資源消耗大

大量算力導致電力浪費和資源損耗。

吞吐量低為降低分叉概率，區(qū)塊生成速度較慢，無法滿足高頻應用需求。6.系統(tǒng)安全保障去中心化的實現(xiàn)算力分散：所有礦工均有機會生成新區(qū)塊，避免單點風險。

長鏈原則：增加攻擊成本，降低系統(tǒng)被篡改的可能性。數(shù)學難題平衡挖礦激勵和系統(tǒng)安全性，避免分叉和資源浪費。區(qū)塊結構

分叉情況3.3.1PoS共識算法1.背景與動機PoW共識算法的誕生資源消耗巨大，限制實際應用。每日需消耗大量算力和能源，只能用于達成共識，造成嚴重的資源浪費。PoS共識算法的提出受股份分紅機制啟發(fā)，權益論證以節(jié)點持有的股份（虛擬貨幣）決定其投票權重，降低資源消耗。2.核心概念驗證者節(jié)點（Validator）節(jié)點通過投票虛擬貨幣作為股份參與投票，成為投票者節(jié)點。幣齡（Coinage）幣齡和虛擬貨幣作為股份的時間長短呈線性關系，即Coinage=k×time幣齡隨股份使用歸零，無論是用于交易還是區(qū)塊生成。PoS對比DPoS3.3.2PoS共識算法驗證通過后，代幣的幣齡歸零，以非股份形式返回持有者。獎勵機制出塊者獲得獎勵，受到關注參與討論。5.PoS優(yōu)勢節(jié)能出塊不依賴算力，依賴于持股比例和幣齡。大幅降低能源與資源浪費，經(jīng)濟實用。公平性改進通過幣齡清零機制，確保出塊機會動態(tài)調(diào)整，唯一避免節(jié)點長期占優(yōu)。3.區(qū)塊生成流程與PoW的共同點均需解決數(shù)學難題。使用哈希值htarget，通過計算獲取當前區(qū)塊的哈希值hcurrent。PoS的改進引入幣齡影響：只需要計算結果hcurrent<(htarget×Coinage)，便可以生成區(qū)塊幣齡，節(jié)點生成區(qū)塊的概率越大。大幅減少算力和能源消耗。4.區(qū)塊驗證與獎勵驗證與廣播出塊者將包含已使用幣齡的代幣隨區(qū)塊廣播到全網(wǎng)，提供其他節(jié)點驗證。3.3.3PoS共識算法6.面臨挑戰(zhàn)安全性問題無利害關系攻擊（NothingatStake）：攻擊者以底部甚至無成本發(fā)起分叉攻擊。幣齡機制可能使攻擊成本降低，系統(tǒng)更容易受到拜占庭行為的影響。公平性與激勵的平衡如何既維持系統(tǒng)公平性，又激勵節(jié)點長期參與。7.PoS的應用與場景改進方向典型應用比特幣和以太坊等區(qū)塊鏈系統(tǒng)逐步向PoS轉型以減輕壓力。改進方向增加攻擊成本（如復合PoS共識算法）。引入更多參數(shù)調(diào)節(jié)出塊權重，提升系統(tǒng)安全性和公平性。3.4.1DPoS共識算法1.背景與簡介PoW和PoS的缺陷PoW：資源消耗巨大，算力集中化（礦池）。PoS：權益集中化趨勢（大節(jié)點壟斷）。DPoS目標結合PoW和PoS優(yōu)勢，避免其缺陷。通過委托機制，在保留去中心化的同時提升效率。2.角色與結構角色：1.候選人（Candidate）：通過注冊成為見證人的候選節(jié)點。2.投票人（Voter）：持幣者，有權投票選舉見證人。3.見證人（Witness）：由投票人選出的代表節(jié)點，負責生成區(qū)塊。權力制衡：投票人可以隨時更新選票，支持或反對投票人。見證人權利有限，需接受社區(qū)監(jiān)督。3.共識流程選舉流程：1.錯誤注冊：提供標識信息（介紹、網(wǎng)站等）。支付高額注冊費用（生成單個區(qū)塊獎勵的上百倍）。2.投票機制：記錄可信（Trusted）和非可信代表（Distrusted）。根據(jù)投票表現(xiàn)評分，維護觀察代表（Observed）列表。投票產(chǎn)生見證人，并更新見證人列表。3.見證人輪流出塊：見證人按亂序輪流生成區(qū)塊，每個周期結束后重新選舉見證人。3.4.2DPoS共識算法4.技術特點中心化與去中心化平衡：提前設計中心化權益的分配與制衡機制，避免礦池化或大節(jié)點壟斷。高效區(qū)塊生成：每輪見證人排序后輪循物料，提升系統(tǒng)吞吐量。EOS.io和BitShares實現(xiàn)上千到上萬級交易吞吐量。投票與動態(tài)調(diào)整：投票權可隨時調(diào)整，阻止權力固化。投票需持續(xù)參與以達成成本平衡。5.優(yōu)勢高飼料：相比PoW和PoS，大幅提升交易效率，適應商業(yè)需求。資源保護：避免PoW高算力消耗，減少資源浪費。用戶參與興趣：普通用戶通過投票即可參與投票機制。3.4.3DPoS共識算法6.面臨挑戰(zhàn)部分去中心化的比重：系統(tǒng)設計初期即具有中心化趨勢。部分投票人不積極參與投票，形成“運行中空”。安全性風險：權力風險集中可能導致決策效率下降或故障。投票質(zhì)量問題：投票行為可能受到賄選等外部因素影響。7.適用場景與典型應用適用場景：高頻交易、需要快速共識的區(qū)塊鏈應用。商業(yè)化需求（如去中心化交易所、支付系統(tǒng)）。典型應用：EOS.io：提供企業(yè)級高效區(qū)塊鏈服務。BitShares：去中心化交易平臺。3.5.1PBFT共識算法3.核心過程

PBFT共識算法的核心過程有三個階段，分別是預備（pre-prepare）、準備（prepare）和提交（commit）階段1.背景與適用場景適用：場景聯(lián)盟鏈，節(jié)點數(shù)量少，但對交易吞吐量和交易確定性要求高。理論基礎：拜占庭普遍問題，提出需需要滿足條件N≥3F+1，其中N為將軍總數(shù)，F(xiàn)為叛變將軍的數(shù)量，時間復雜度較高，為On(f+1)。算法優(yōu)化：1999年，MiguelCastro和BarbaraLiskov提出PBFT，其同樣滿足N≥3F+1的數(shù)量要求，但是算法的時間復雜度降低到了On(2)。

2.PBFT核心機制Quorum機制quorum機制常被用于分布式系統(tǒng)中以保證數(shù)據(jù)冗余存儲情況下結果的最終一致，實際上是一種投票機制。?PBFT共識算法的核心過程3.5.2PBFT共識算法為了實現(xiàn)PBFT算法，我們需要進行以下步驟：初始化系統(tǒng)：選擇足夠數(shù)量的節(jié)點來構成系統(tǒng)，并確保每個節(jié)點都知道其他節(jié)點的存在。請求處理：當節(jié)點收到請求時，它會將請求發(fā)送給其他節(jié)點進行prepare階段的處理。消息傳遞：節(jié)點之間通過傳遞prepare和commit消息來達成共識。這些消息需要在一定的時間內(nèi)被確認和響應。共識達成：當收到足夠數(shù)量的prepare和commit消息后，節(jié)點就可以執(zhí)行請求并寫入數(shù)據(jù)。錯誤處理：如果節(jié)點發(fā)現(xiàn)其他節(jié)點存在問題或故障，需要進行相應的處理和恢復機制。PBFT共識算法視圖變更流程3.6共識算法對比分析1.性能對比

PoW：低性能，交易確認時間長（10分鐘）。

PoS：中等性能，交易確認時間較短（幾秒到幾分鐘）。

PBFT：高性能，低延遲（秒級）。2.安全性對比

PoW：對51%攻擊有一定防范，但需消耗大量能源。

PoS：對51%攻擊和女巫攻擊有一定防范，但需合理設計代幣分配。

PBFT：防范拜占庭故障，但不適用于大規(guī)模公有鏈。3.去中心化程度對比

PoW：高度去中心化，但礦池集中化問題嚴重。

PoS：中等去中心化，受代幣初期分配影響。

PBFT：低去中心化，適用于小規(guī)模聯(lián)盟鏈。4.資源消耗對比

PoW：高資源消耗（計算能力和能源）。

PoS：低資源消耗（持有代幣）。

PBFT：低資源消耗（網(wǎng)絡通信）。3.7共識算法的優(yōu)化與改進1.混合共識機制（HybridConsensus）結合PoW和PoS的優(yōu)勢，利用PoW保障安全性，利用PoS提升效率。例子：Decred采用的PoW+PoS混合共識機制。2.分片技術（Sharding）將區(qū)塊鏈網(wǎng)絡分為多個小塊（Shard），每個小塊處理一部分交易，提升整體吞吐量。例子：以太坊2.0中的分片技術。3.DAG（有向無環(huán)圖）共識算法摒棄傳統(tǒng)區(qū)塊鏈結構，采用圖結構提高交易并發(fā)量。例子：IOTA采用的Tangle共識算法。服務器通過網(wǎng)絡發(fā)送的任何消息都有可能會丟失，為了避免日志條目的缺失，保存到日志中的條目還需要額外保存添加這個條目時所在的任期

4.共識算法的應用4.Applicationofconsensusalgorithm044.1比特幣共識算法1.區(qū)塊鏈提高效率共識算法如工作量證明和權益證明，在區(qū)塊鏈中確保交易安全性的同時，提高了網(wǎng)絡處理交易的速度和效率。2.智能合約保障信任基于共識算法的智能合約自動執(zhí)行，無需第三方介入，大大降低了欺詐風險，保障了交易雙方的信任關系。以太坊工作量證明（PoW）挖礦難度調(diào)整網(wǎng)絡穩(wěn)定性網(wǎng)絡穩(wěn)定性工作量證明（PoW）工作量證明（PoW）工作量證明（PoW）工作量證明（PoW）權益證明(PoS)權益證明(PoS)以太坊升級權益證明(PoS)以太坊升級權益證明(PoS)權益證明(PoS)權益證明(PoS)以太坊升級以太坊采用工作量證明以太坊逐步轉向權益證明權益證明(PoS)以太坊升級4.2以太坊共識算法4.3新型共識算法：1.去中心化程度不斷提高隨著區(qū)塊鏈技術的發(fā)展，共識算法將更強調(diào)去中心化，如采用分片技術提高可擴展性，同時保持系統(tǒng)的去中心化特性。2.跨鏈共識成為新趨勢隨著多鏈和側鏈的興起，跨鏈共識算法成為研究熱點，它們能實現(xiàn)不同區(qū)塊鏈之間的價值轉移和信息交互。3.安全性與性能持續(xù)增強共識算法將不斷優(yōu)化，通過密碼學、分布式計算和智能合約等技術的結合，提升區(qū)塊鏈網(wǎng)絡的安全性和交易處理性能。4.3新型共識算法1.Algorand共識算法原理：采用VRF（可驗證隨機函數(shù)）選舉出參與者，實現(xiàn)快速共識。創(chuàng)新點：高效、去中心化、安全。應用前景：適用于高性能公有鏈。2.Avalanche共識算法原理：利用隨機抽樣和子采樣技術，實現(xiàn)快速、可靠的共識。創(chuàng)新點：高吞吐量、低延遲、高擴展性。應用前景：適用于需要高頻交易的區(qū)塊鏈應用。VRF（VerifiableRandomFunction）可驗證隨機函數(shù)4.3新型共識算法Algorand共識算法Algorand共識算法旨在通過隨機選擇用戶來進行區(qū)塊提議和投票，結合加密抽簽和快速拜占庭協(xié)議，確保高效的共識達成且系統(tǒng)具備擴展性和安全性。1.節(jié)點角色與共識流程Algorand每輪共識過程中，節(jié)點可以扮演三種角色：區(qū)塊提議者：用戶所持資產(chǎn)越多，成為提議者的優(yōu)先級越高，提議區(qū)塊被選中為出塊的概率越大。委員會成員：在全體用戶中隨機挑選的小規(guī)模節(jié)點集合，負責對提議的區(qū)塊進行投票。普通節(jié)點：不參與提議或投票的用戶節(jié)點。2.核心技術Algorand共識算法的核心由兩大技術構成：加密抽簽算法（CryptographicSortition）：通過可驗證隨機函數(shù)（VRF），以隨機的方式選出區(qū)塊提議者和委員會成員，難以被攻擊者定位?？焖侔菡纪f(xié)議（BA）：用于低延遲達成共識，避免分叉。3.加密抽簽過程系統(tǒng)首先使用VRF決定當輪的隨機數(shù)種子，基于此隨機數(shù)種子進行區(qū)塊提議者和委員會成員的選擇。用戶的資產(chǎn)按最小單位被劃分為若干“子用戶”，每個子用戶被選中的概率為固定的n/s。若某個子用戶被選中，其所屬用戶成為提議者或委員會成員。4.3新型共識算法4.共識流程區(qū)塊提議階段：區(qū)塊提議者廣播區(qū)塊，各節(jié)點收集提議并丟棄優(yōu)先級較低的區(qū)塊。區(qū)塊Reduction階段：各節(jié)點可能收到不同優(yōu)先級的區(qū)塊，需達成對優(yōu)先級最高區(qū)塊的共識。BinaryBA*階段：在收斂的區(qū)塊上進行多輪投票，直至系統(tǒng)達成共識。5.安全性與可擴展性抵抗女巫攻擊：通過基于用戶資產(chǎn)權重的抽簽機制，防止攻擊者通過偽造身份增加被選中概率。可擴展性：通過抽簽選取少量節(jié)點組成委員會進行投票，有效減少計算負擔，支持區(qū)塊鏈擴展至大規(guī)模網(wǎng)絡環(huán)境?？偨Y來說，Algorand共識算法通過高效的隨機選取和快速拜占庭協(xié)議，保證了系統(tǒng)的去中心化、安全性和可擴展性，適用于大規(guī)模區(qū)塊鏈網(wǎng)絡環(huán)境。

運行BinaryBA*，就唯一區(qū)塊達成共識，記為hblock1等待一段時間，以接收區(qū)塊

區(qū)塊提議者選擇優(yōu)先級最高的子用戶來廣播區(qū)塊和消息π區(qū)塊Reduction，將目標區(qū)收斂至hblock2或空塊

根據(jù)第r-1輪消息，確認第r輪種子seedr

通過VRF確定第r輪的區(qū)塊提議者集合

統(tǒng)計final狀態(tài)的投票信息，達成最終共識

Algorand共識算法的流程4.3新型共識算法HotStuff共識算法HotStuff共識算法是為了解決PBFT共識算法在處理視圖變更時的復雜性問題，同時提升聯(lián)盟鏈的性能表現(xiàn)，如交易吞吐量和網(wǎng)絡帶寬的需求。它通過簡化視圖變更流程和提高并行度，適用于高效的區(qū)塊鏈共識。1.HotStuff的核心特性線性視圖變更：HotStuff將視圖變更（視圖是共識過程的階段）融入常規(guī)的共識流程，減少了復雜性。相比PBFT共識算法的非線性視圖變更，HotStuff具備了線性視圖變更（LinearViewChange），從而降低了處理視圖變更的復雜度。時間復雜度降低：HotStuff將PBFT共識算法的時間復雜度由$O(n^2)$降低到了$O(n)$，主要通過減少從節(jié)點之間的消息廣播，使得消息只在主節(jié)點和從節(jié)點之間傳遞。2.基本共識流程（BasicHotStuff）HotStuff的基本共識過程可以簡化為圍繞主節(jié)點進行的三輪投票：主節(jié)點職責：每個視圖都有一個唯一的主節(jié)點，負責打包區(qū)塊、收集和轉發(fā)消息，并生成共識證書（QuorumCertificate,QC）。QC是主節(jié)點收集到$n-f$條從節(jié)點投票后生成的數(shù)據(jù)集合，包含共識階段、視圖編號、交易請求等信息。從節(jié)點簡化消息傳遞：從節(jié)點不再相互廣播消息，所有共識消息由主節(jié)點處理和轉發(fā)，從而降低了網(wǎng)絡復雜度，但提高了主節(jié)點的處理負擔。3.HotStuff的五階段流程HotStuff共識流程分為五個階段：準備階段（Prepare）：從節(jié)點向主節(jié)點發(fā)送new-view消息，主節(jié)點再向從節(jié)點廣播共識消息。4.3新型共識算法5.性能與優(yōu)化提升了系統(tǒng)活性：HotStuff延續(xù)了PBFT的三階段共識，但增加了兩個額外階段來提高系統(tǒng)的整體活性。負擔集中于主節(jié)點：雖然減少了從節(jié)點的消息傳遞負擔，但這增加了主節(jié)點的計算和通信需求，對其性能提出了更高要求?？偨Y來說，HotStuff通過簡化視圖變更、減少網(wǎng)絡復雜度和提高并行度，實現(xiàn)了更高效的區(qū)塊鏈共識流程，適用于需要大規(guī)模、低延遲共識的場景。HotStuff共識流程

2.預提交階段（Pre-commit）：主節(jié)點向從節(jié)點發(fā)送消息，從節(jié)點返回確認消息。3.提交階段（Commit）：主節(jié)點收集到足夠多的確認消息后，進入下一個階段。4.決定階段（Decide）：主節(jié)點向從節(jié)點發(fā)送最終共識消息，節(jié)點執(zhí)行共識。5.最終階段（Final）：從節(jié)點將執(zhí)行結果返回給客戶端，完成共識流程。每個階段的操作非常相似，都是由主節(jié)點發(fā)起消息，等待從節(jié)點的確認響應。4.ChainedHotStuff為了進一步提高并行度，HotStuff提出了ChainedHotStuff，將多個共識流程串聯(lián)起來，實現(xiàn)并行共識。這解決了BasicHotStuff中每個階段獨立進行的局限性，使得多個共識過程可以重疊進行，提升系統(tǒng)效率。4.4

跨鏈共識1.Cosmos的Tendermint

原理：基于BFT共識，結合區(qū)塊鏈間的互操作協(xié)議（IBC）。創(chuàng)新點：實現(xiàn)跨鏈通信和資產(chǎn)轉移。應用前景：構建多鏈生態(tài)系統(tǒng)。2.Polkadot的RelayChain

原理：中心中繼鏈（RelayChain）與多個平行鏈（Parachain）協(xié)同工作，確保不同鏈間的共識和通信。創(chuàng)新點：高安全性、高擴展性。應用前景：支持不同區(qū)塊鏈網(wǎng)絡的互操作性。4.5公有鏈共識算法PoW共識算法PoW（ProofofWork，工作量證明）共識算法是一種應對網(wǎng)絡中可能存在的惡意節(jié)點（拜占庭節(jié)點）的機制。PoW共識算法的核心是哈希算法（見2.5節(jié)），能夠?qū)⑷魏伍L度的輸入，通過哈希函數(shù)轉化為固定長度的輸出，記作y=Hx()，其中H()被稱為哈希函數(shù)，通常情況下將素數(shù)的模運算作為哈希函數(shù)，如Hx()=xmod11等。由哈希函數(shù)的定義可知，其具有正向計算快速簡單，卻很難做到逆向計算的特點，大多數(shù)情況下，不同的x會計算得到不同的y值，否則將發(fā)生哈希沖突。哈希沖突不是本書討論的重點內(nèi)容，感興趣的讀者可以在課后深入了解哈希算法的相關內(nèi)容，以及如何處理哈希沖突的情況。在解數(shù)學難題的過程中，礦工需要先收集一組交易，并打包成一個區(qū)塊得到區(qū)塊數(shù)據(jù)data。然后礦工會生成一個隨機數(shù)nonce，并將這個隨機數(shù)與區(qū)塊數(shù)據(jù)data和上一個區(qū)塊的哈希值hprevious進行哈希運算，得到當前區(qū)塊的哈希值hcurrent，即

hcurrent=H(data,nonce,hprevious)如果hcurrent≥htarget，那么礦工需要重新生成一個隨機數(shù)nonce，重新進行哈希運算，直到hcurrent<htarget為止，那么隨機數(shù)nonce就是數(shù)學難題的解。由此可見，htarget越小，數(shù)學難題的難度就越大，節(jié)點的求解過程越困難，需要調(diào)用的算力也就越多。因此，調(diào)整數(shù)學難題的難度可以通過控制區(qū)塊生成的時間間隔來實現(xiàn)。

4.5公有鏈共識算法區(qū)塊結構分叉情況當?shù)V工得到數(shù)學難題的解后，會將hcurrent、nonce和hprevious打包添加到當前區(qū)塊的區(qū)塊頭中，并向網(wǎng)絡中廣播，讓其他網(wǎng)絡中的節(jié)點進行驗證。一旦驗證得到通過，解題區(qū)塊就可以得到相應的比特幣獎勵。

在比特幣網(wǎng)絡中，最先得到難題的解并通過驗證的區(qū)塊將被加入網(wǎng)絡，完成上鏈。但由于實際中存在網(wǎng)絡延遲等問題，可能部分節(jié)點在收到最新區(qū)塊消息前也完成了求解，于是可能出現(xiàn)兩個甚至更多區(qū)塊同時上鏈的情況，這便是PoW共識算法的分叉（Fork）4.5

公有鏈共識算法PoS共識算法PoS（ProofofStake，權益證明）共識算法是一種旨在減少資源消耗并提高效率的區(qū)塊鏈共識機制。以下是PoS共識算法的關鍵知識點：算法理念：PoS從股份概念中得到啟發(fā)，認為持有貨幣的節(jié)點應有更多影響力。節(jié)點角色：擁有虛擬貨幣的節(jié)點可以將其轉化為股份參與共識，這些節(jié)點被稱為驗證者（Validator）。幣齡概念：幣齡（Coinage）描述了節(jié)點持有貨幣作為股份的時間，與貨幣作為股份的時間長短呈線性關系。區(qū)塊生成：PoS在生成區(qū)塊時也需要解決數(shù)學難題，但解題難度考慮了幣齡的影響，降低了計算資源消耗。出塊機制：節(jié)點持有的幣齡越大，越容易生成滿足要求的區(qū)塊，從而節(jié)省了計算資源。6.公平性：使用過的幣齡在區(qū)塊生成后會被廣播到網(wǎng)絡中進行驗證，并通過驗證后清零。7.能源效率：PoS算法相比PoW大大減少了能源和資源消耗，更為經(jīng)濟實用。8.安全性問題：PoS存在安全性缺陷，攻擊者可能通過控制大量幣齡來低成本地發(fā)起攻擊，這被稱為無利害關系攻擊。9.比較PoW：PoW要求節(jié)點控制超過51%的算力才能發(fā)起攻擊，而在PoS中，攻擊者可能通過控制大量幣齡來實現(xiàn)分叉。PoS共識算法通過考慮節(jié)點持有貨幣的量和時間來分配記賬權，有效地減少了能源消耗，但同時也引入了新的安全挑戰(zhàn)。這種算法在設計上試圖平衡效率和安全性，但也需要持續(xù)的改進來應對潛在的攻擊。4.5公有鏈共識算法DPoS共識算法節(jié)點角色：節(jié)點分為候選人（Candidate）、投票人（Voter）和見證人（Witness）。共識過程：持幣者作為投票人，從候選人中選舉出多個見證人，這些見證人負責區(qū)塊的生成。去中心化與中心化：DPoS具有一定的去中心化特性，但相比PoW和PoS，它保留了更多的中心化特征。礦池與委托：DPoS認為在PoW和PoS系統(tǒng)中，用戶趨向于加入礦池或委托第三方，形成中心化傾向。共識流程：包括選舉見證人、見證人輪流生成區(qū)塊，以及周期性的重新選舉。候選人注冊：候選人在注冊時需要提供個人信息并支付高額的注冊費用，以確保其認真履行責任。

7.投票機制：投票人可以對候選人進行投票，支持或反對他們成為見證人，并根據(jù)表現(xiàn)進行評分。8.系統(tǒng)效率：DPoS算法能夠提供較高的交易吞吐量，滿足大多數(shù)應用需求。9.中心化風險：盡管DPoS設計了權益分配和權利制約，但仍然存在中心化風險，因為一些投票人可能不履行投票職責。10.實際應用：DPoS被應用于EOS.io、BitShares等區(qū)塊鏈系統(tǒng)中，以實現(xiàn)高效率和可擴展性。DPoS共識算法通過委托機制提高了區(qū)塊鏈系統(tǒng)的效率和可擴展性，但這種算法在一定程度上犧牲了去中心化程度，需要在設計時就考慮到權益分配和權利制約，以避免中心化帶來的潛在問題。4.6

聯(lián)盟鏈共識算法PBFT共識算法PBFT共識算法的核心過程

PBFT共識算法視圖變更流程1.PBFT共識算法背景PoW和PoS：常用于公有鏈，具有較高安全性，但吞吐量低，交易確認延遲高。聯(lián)盟鏈需求：節(jié)點少，對吞吐量和交易確定性要求高。適用場景：

不考慮拜占庭錯誤：可采用RAFT輕量級共識算法。考慮拜占庭錯誤：優(yōu)先選擇PBFT共識算法。2.PBFT共識算法介紹定義：實用性拜占庭容錯（PracticalByzantineFaultTolerance）算法。提出：由米格爾·卡斯特羅（MiguelCastro）和巴巴拉·利斯科夫（BabaraLiskov）在1999年提出。核心理論：滿足條件N≥3F+1，其中N為節(jié)點總數(shù)，F(xiàn)為錯誤節(jié)點數(shù)量。優(yōu)化：時間復雜度降低至O(n2)。3.Quorum機制來源：鴿巢原理。作用：確保數(shù)據(jù)冗余存儲情況下的最終一致性，本質(zhì)為一種投票機制。投票機制：讀取操作需要的票數(shù)：qr。寫入操作需要的票數(shù)：qw。需滿足條件：qr+qw>n和qw>n/2。4.6

聯(lián)盟鏈共識算法PBFT共識算法4.核心過程PBFT的共識過程分為三個階段：預備階段（Pre-prepare）：主節(jié)點廣播預備消息，其他節(jié)點驗證合法性。準備階段（Prepare）：從節(jié)點廣播準備消息，收集足夠的準備消息（2f+1條）進入準備狀態(tài)。提交階段（Commit）：收集足夠的提交消息（2f+1條），進入提交狀態(tài)并執(zhí)行操作。執(zhí)行結果反饋給客戶端。5.垃圾回收機制檢查點流程：用于定期清理冗余的共識數(shù)據(jù)。每K次請求后執(zhí)行一次檢查點。高低水位機制：通過設定高水位（H）和低水位（h）限制系統(tǒng)緩存的數(shù)據(jù)量。6.視圖變更機制觸發(fā)條件：主節(jié)點失效或被認為存在問題時觸發(fā)。視圖編號更新：視圖變更時，編號v+1，主節(jié)點切換到下一個節(jié)點。變更過程：節(jié)點廣播view-change消息，附帶舊視圖共識日志。新主節(jié)點匯總view-change-ack消息，確認非拜占庭節(jié)點發(fā)出的變更請求，生成new-view消息，恢復必要的共識數(shù)據(jù)。7.PBFT共識算法的優(yōu)缺點優(yōu)點：抵抗拜占庭行為，保證高交易吞吐量。無分叉現(xiàn)象。缺點：通信復雜度高，達到O(n2)。無法防御女巫攻擊，需額外模塊輔助處理身份偽造問題。8.應用場景PBFT廣泛應用于聯(lián)盟鏈、分布式系統(tǒng)中，特別是對交易吞吐量和確定性要求較高的場景。

5.共識算法的未來發(fā)展5.Futuredevelopmentofconsensusalgorithms055.1挑戰(zhàn)與機遇：1.算力要求日益增長隨著區(qū)塊鏈網(wǎng)絡規(guī)模的擴大，共識算法對算力的要求越來越高，這增加了參與門檻和能源消耗。2.安全威脅日益嚴重近年來，針對共識算法的攻擊事件頻發(fā)，51%算力攻擊和雙重支付問題嚴重威脅了區(qū)塊鏈系統(tǒng)的穩(wěn)定性。3.去中心化與技術效率的平衡在去中心化追求與技術效率提升之間尋找平衡，成為共識算法發(fā)展的關鍵挑戰(zhàn)之一。4.跨鏈共識技術興起隨著區(qū)塊鏈技術的廣泛應用，跨鏈共識技術成為連接不同區(qū)塊鏈網(wǎng)絡、實現(xiàn)價值互通的重要機遇。5.2共識算法的安全性1.51%攻擊

-定義：攻擊者控制了全網(wǎng)超過50%的計算能力或權益，能夠篡改交易記錄。

-防御機制：提高攻擊成本、采用混合共識機制。2.女巫攻擊（SybilAttack）

-定義：攻擊者創(chuàng)建多個虛假身份以控制網(wǎng)絡。

-防御機制：采用權益證明、引入身份驗證機制。3.拜占庭容錯問題（ByzantineFaultTolerance,BFT）

-定義：系統(tǒng)能在部分節(jié)點惡意或故障的情況下正常運行。

-例子：PBFT、Tendermint。5.3共識算法的數(shù)學基礎1.博弈論

-定義：研究在不同參與者間決策的相互影響。

-應用：分析礦工在PoW中的策略選擇、權益持有者在PoS中的投票行為。2.概率論

-定義：研究隨機現(xiàn)象的數(shù)學理論。

-應用：評估共識算法中的隨機選舉機制（如Algorand中的VRF）。3.分布式系統(tǒng)理論

-定義：研究多個計算單元如何協(xié)同工作。

-應用：設計和分析共識算法的容錯機制、性能優(yōu)化。工作證明（ProofofWork,PoW）：在PoW中，節(jié)點通過解決復雜的計算問題來驗證交易并添加新區(qū)塊。比特幣是一個使用PoW的典型例子。權益證明（ProofofStake,PoS）：在PoS機制中，驗證者的選擇基于其持有的代幣數(shù)量和持有時間。以太坊等網(wǎng)絡使用PoS共識。權威證明（ProofofAuthority,PoA）：PoA要求參與者以其身份和聲譽作為抵押，適用于私有鏈場景，如供應鏈管理。覆蓋證明（ProofofCoverage,PoC）：PoC用于驗證網(wǎng)絡熱點確實提供了它們聲稱的無線網(wǎng)絡覆蓋。例如，Helium網(wǎng)絡使用PoC?；顒幼C明（ProofofActivity,PoA）：PoA結合了PoW和PoS的特點，例如，Decred網(wǎng)絡就采用這種機制。身份證明（ProofofIdentity,PoI）：PoI通過比對用戶私鑰和授權身份來驗證參與者的身份。思考題Reflectionquestions0601030204共識算法如PoW、PoS等各具特色，滿足不同區(qū)塊鏈項目需求，展現(xiàn)了技術創(chuàng)新的多樣性。研究顯示，采用成熟共識算法的區(qū)塊鏈系統(tǒng)，如采用PoW的Bitcoin，在安全性方面表現(xiàn)優(yōu)異，成功抵御了多次攻擊。與早期PoW相比，PoS等新型共識算法在能源效率上有所提升，顯著降低了區(qū)塊生成成本，促進了區(qū)塊鏈技術的可持續(xù)發(fā)展。共識算法如BFT、PBFT等通過節(jié)點間的相互驗證，實現(xiàn)了網(wǎng)絡的高度去中心化，增強了區(qū)塊鏈系統(tǒng)的魯棒性。共識算法多樣性共識算法安全性共識算法效率共識算法去中心化1、

什么是分布式系統(tǒng)中的共識問題？共識正確性需要滿足哪些特征？共識通信模型分類假設區(qū)別不選異步模型的原因共識通信模型主要包括同步模型、部分同步模型和異步模型，基于網(wǎng)絡通信的不同假設。同步模型假設所有節(jié)點在同一時間步內(nèi)完成通信，部分同步模型允許延遲但存在全局穩(wěn)定時間，異步模型則無時間限制，導致共識難度增加。不基于異步模型研究共識問題，因異步網(wǎng)絡下的不確定性使達成共識的算法設計和分析變得極為復雜且難以保證安全性。2、共識的通信模型有哪幾類？其中的假設區(qū)別是什么？為什么不基于異步模型研究共識問題？拜占庭將軍問題定義了分布式系統(tǒng)中可能遇到的節(jié)點故障模式，強調(diào)了在容錯性設計中需考慮節(jié)點間信息不一致的復雜性。拜占庭問題定義了容錯在分布式系統(tǒng)實現(xiàn)共識算法時，需解決拜占庭將軍問題，確保即使在節(jié)點故障或惡意行為下，系統(tǒng)也能達成一致決策。對共識算法有重要影響3、什么是拜占庭將軍問題？為什么此問題在分布式系統(tǒng)的研究中非常重要？4、

FLP不可能定理具體是指什么？其對共識算法的研究產(chǎn)生了什么影響？1.FLP定理定義共識局限FLP不可能定理指出，在異步系統(tǒng)中，即使網(wǎng)絡是可靠的，也不存在一個能解決一致性問題的算法。它揭示了共識算法的固有局限。2.推動算法創(chuàng)新研究FLP定理激發(fā)了共識算法領域的創(chuàng)新，推動了如Paxos、Raft等實用性更強的分布式一致性算法的出現(xiàn)，這些算法在特定條件下實現(xiàn)了共識。3.促進容錯性考量FLP定理促使研究者更加關注共識算法的容錯性，因為在實際應用中，網(wǎng)絡分區(qū)和節(jié)點故障是常態(tài)，需要算法能夠在這些情況下保持一致性。5、試比較CAP理論和FLP不可能定理的區(qū)別和聯(lián)系。1.CAP理論與FLP定理的差異性CAP理論關注分布式系統(tǒng)中一致性、可用性和分區(qū)容忍性的權衡，而FLP定理則強調(diào)在異步系統(tǒng)中，即使無故障，也可能無法就某個值達成決策。2.CAP與FLP定理的內(nèi)在聯(lián)系盡管CAP理論和FLP不可能定理聚焦不同，但二者均強調(diào)了分布式系統(tǒng)中的固有挑戰(zhàn)，即網(wǎng)絡通信的不確定性和系統(tǒng)組件的潛在故障對決策一致性的影響。6、Paxos和RAFT是針對于拜占庭將軍問題模型的嗎？如果不是，請說明其模型弱化了哪些拜占庭將軍問題中的假設。1.Paxos和RAFT非針對拜占庭Paxos和RAFT共識算法并非直接針對拜占庭將軍問題設計，它們基于更簡單的故障模型，假設節(jié)點故障是崩潰-停止型，而非拜占庭型。2.弱化節(jié)點行為假設拜占庭將軍問題假設節(jié)點可能發(fā)送任意信息，而Paxos和RAFT僅假設節(jié)點可能失效不響應或提供舊信息，不涵蓋任意欺詐行為。3.強化網(wǎng)絡可靠性Paxos和R