区块链导论 课件 第四章：共识算法

第四章：共识算法Chapter4:ConsensusAlgorithm作者:北京大学汇报时间:2024/07/03目录共识算法概述01RAFT共识算法03共识算法的未来发展05共识问题02共识算法的应用04思考题06

1.共识算法概述1.Overviewofconsensusalgorithms011.1共识正确性的定义一个正确的共识算法需要满足以下三个核心特性：一致性（Agreement）：在分布式系统中，所有参与共识的节点必须对某个决策值达成一致。这意味着即使不是所有节点都同意同一个决策值，也至少要有大多数节点达成共识。一致性确保了系统不会分裂成多个持有不同决策值的子集。有效性（Validity）：最终的决策值必须是系统中某个节点提出的有效值，而不是一个预设的默认值。有效性确保了共识的结果是基于实际提出的值，而不是一个无关紧要的默认选项。这也有时被称为正确性，强调了决策值的正确来源。终止性（Termination）：所有节点最终都必须完成决策过程。终止性保证了共识算法能够在有限的时间内完成，不会无限期地运行下去，从而确保了系统的稳定性和可靠性。1.2共识的通信模型共识的通信模型主要分为以下三类：同步模型（SynchronousModel）：在同步模型中，网络通信具有已知的延迟上限，即消息传递有一个最大延迟时间。每个节点处理事务的时间有一个已知的最大差异。每轮共识中，节点都能在预定时间内完成任务，如果超时则可以认为节点发生故障。同步模型是一种理想化的模型，在实际中很难实现，但早期的共识算法多以此为基础。异步模型（AsynchronousModel）：异步模型中，消息传递的延迟没有已知的上限，即消息可能无限延迟。节点处理任务的速度未知，且可能有很大的差异。无法通过超时来判断节点是否正常工作，因为延迟可能非常长。异步模型更接近现实世界的网络环境，适用于异步模型的共识算法也适用于同步模型，但反之则不成立。FLP不可能定理指出，在纯粹的异步模型中，无法设计出总是能够达成共识的算法。1.2共识的通信模型3.部分同步模型（PartialSynchronyModel）：部分同步模型介于同步模型和异步模型之间。存在一个全局稳定时间（GST），在这段时间内网络可以被认为处于同步状态，共识可以进行。如果网络出现问题，共识流程可能终止，但经过GST后，网络会恢复到同步状态，共识可以继续。这种模型更符合现实世界的网络环境，即在大多数时间内网络是可靠的，偶尔会出现故障。部分同步模型是许多现代共识算法的基础，如Paxos和PBFT。1.3共识算法的详细案例分析1.比特币的PoW（工作量证明）算法原理：矿工通过计算哈希值来竞争记账权，成功找到符合要求的哈希值后即可添加区块。优点：高度去中心化，安全性高。缺点：能源消耗巨大，交易确认时间长。2.以太坊的PoS（权益证明）算法原理：通过持有代币的数量和时间来决定谁有记账权，减少了对计算能力的依赖。优点：节能环保，交易确认速度快。缺点：初期分配不公平，富者恒富。3.PBFT（实用拜占庭容错）在联盟链中的应用原理：通过多轮投票机制实现共识，确保系统在有不超过1/3恶意节点的情况下仍能正常运行。优点：高效低延迟，适用于私有链和联盟链。缺点：不适用于公有链，扩展性差。2.共识问题2.Consensusissues02问题背景：拜占庭帝国的将军们必须通过信使来沟通，以达成是“进攻”还是“撤退”的共识。将军们之间相隔遥远，无法面对面交流。存在叛徒可能散布虚假信息或发送矛盾的指令。问题定义：需要找到一个算法，即使在有叛徒的情况下，也能让忠诚的将军们达成正确的决策。叛徒的行为被称为“拜占庭错误”。问题复杂性：叛徒可能以任意方式行为，包括发送矛盾的信息或不发送信息。忠诚的将军们必须识别并忽略叛徒的影响。解决方案：拜占庭容错（BFT）算法提供了一种解决方案。当总节点数N大于或等于3倍的叛变将军数F加1（N≥3F+1）时，问题有解。2.1拜占庭将军问题5.共识过程：每个节点收到提案后，会向其他节点发送确认消息以验证提案的真伪和提案者的身份。如果提案节点不是叛徒，但收到了F个非正常的确认消息，需要超过2/3的多数正常确认才能达成共识。如果提案节点是叛徒，它会发送矛盾的信息，忠诚的节点需要通过进一步的验证和多数投票来达成共识。6.问题难点：在异步模型中，由于消息传递的延迟没有上限，设计一个总是能够达成共识的算法是非常困难的。FLP不可能定理表明，在纯粹的异步模型中，不存在一个总是能够达成共识的算法。7.实际应用：拜占庭将军问题在现实世界中的分布式系统中非常普遍，如区块链网络中的节点共识。该问题的解决方案对于设计能够在存在恶意行为者的情况下仍然能够可靠运行的系统至关重要。拜占庭将军问题的核心挑战在于如何在不完全信任的网络中达成共识，并且要能够抵御来自叛徒的干扰。2.1拜占庭将军问题2.2FLP不可能定理1.FLP定理影响共识设计FLP不可能定理揭示了分布式系统中实现强一致性共识的困难，对设计高效的共识算法产生深远影响。2.FLP定理的实用意义FLP定理虽然指出不可能在所有情况下都达成共识，但它为开发者提供了设计容错分布式系统的实用指导。3.共识算法回避FLP限制尽管受到FLP定理的限制，但许多共识算法通过异步模型、故障检测等方法成功地实现了系统级的共识。4.FLP定理的学术价值FLP定理是分布式系统理论的重要里程碑，为后续分布式计算和共识问题的研究奠定了理论基础。2.3CAP理论1.CAP理论定义重要性CAP理论定义了分布式系统在设计时需要在一致性、可用性和分区容忍性之间做出的权衡，是系统设计的基石。2.一致性对网络延迟敏感CAP理论中的一致性要求数据在所有副本中保持一致，对低延迟网络要求高，现代系统常通过优化算法实现最终一致性。3.可用性影响用户体验在分布式系统中，即使部分节点出现故障，系统仍需保持对外提供服务的能力，高可用性直接关联用户满意度。4.分区容忍性必不可少随着分布式系统规模的扩大，网络分区现象不可避免，CAP理论指出设计系统时需确保其在网络分区时仍能继续运行。5.设计启示：在共识算法设计中，不必追求同时满足三种特性，应根据实际需求做出取舍。例如，比特币网络牺牲了强一致性，采用最终一致性，以保证可用性和分区容错性，这导致了可能出现分叉和区块回退。3.共识算法3.consensusalgorithm033.1.1RAFT概述1.RAFT性能卓越RAFT共识算法以其高效性和容错性著称，能够在分布式系统中快速达成数据一致性，确保系统的高可用性。2.故障恢复能力强RAFT通过选举领导者和日志复制的机制，使得在节点故障时能够快速恢复并继续服务，保持系统稳定性。3.适用性强泛RAFT算法设计简洁，易于理解和实现，已广泛应用于多个开源项目和商业系统，显示出其强大的适用性和扩展性。4.社区支持活跃RAFT算法拥有活跃的社区支持和开源维护，不断推动算法的演进和优化，为用户提供更优质的服务。3.1.2RAFT详细流程1.RAFT的高效性RAFT共识算法通过减少不必要的通信开销和简化的日志复制机制，在实验中表现出显著的性能提升，适用于大规模集群。2.RAFT的容错性RAFT算法通过选举Leader并允许故障转移，保证了系统即使在节点故障时也能继续提供服务，具有高度的容错性。3.RAFT的可理解性相较于其他复杂的共识算法，RAFT算法设计简洁直观，易于理解，使得系统开发和维护更加便捷。Raft初启动多候选者多领导者无法选出领导者同步过程3.1.3RAFT算法的核心要点问题分解：RAFT将一致性问题分解为领导者选举（LeaderElection）、日志复制（LogReplication）和安全性（Safety）三个相对独立的问题。领导者选举：领导者（Leader）是处理所有客户端请求的节点，负责生成日志数据并广播给从节点（Follower）。从节点是被动的，仅接收来自领导者的日志数据。候选节点（Candidate）是选举过程中的过渡状态，任何节点在发现领导者故障后都可成为候选节点。3.任期和心跳机制：RAFT通过任期（Term）来管理领导者选举，每个任期的开始都是一次选举。使用心跳机制触发领导者选举，领导者通过周期性发送心跳信息维持其地位。4.日志复制：领导者接收客户端请求，将命令作为新的日志条目加入日志，并广播给从节点复制。从节点存储日志条目，领导者确保所有从节点都存储了所有日志条目。3.1.3RAFT算法的核心要点5.安全性：RAFT通过任期号和日志匹配原则来确保日志的一致性和安全性。如果领导者的任期号过时，它会转换为从节点。6.动态集群成员变更：RAFT支持动态改变集群成员，使用联合一致性（JointConsensus）方法来处理配置变更。7.简化管理：日志条目只从领导者发送给其他服务器，简化了日志复制的管理。领导者选举的条件限制为拥有最新、最全日志的节点，减少了数据同步时间。RAFT算法以其清晰的结构和逻辑，使得在实际系统中实现变得相对容易，成为分布式系统中广泛使用的共识算法之一。3.2.1Pow共识算法1.背景与概述RAFT共识算法的局限性

适用于私有链和内部互信较高的联盟链。

未考虑拜占庭节点（篡改数据、不一致消息）的情况。

PoW共识算法的应对方式

增加作恶成本，减少拜占庭行为可能性。

鼓励正常参与，通过奖励机制提升参与积极性。2.起源与发展1993年：辛西娅·德沃克和莫尼·瑙尔首次提出概念。

2008年：比特币采用PoW作为共识算法，使其广为人知。3.PoW共识算法核心哈希算法特性

输入长度任意，输出为固定长度（y=H(x)）。

正向计算简单，逆向计算困难（防篡改特性）。数学难题（Mining）

目标：通过哈希函数计算小于目标值（`htarget`）的哈希值。

随机数（nonce）与区块数据（data）、上一区块哈希值（hprevious）共同参与计算。

难度调整：通过设置htarget控制计算难度和区块生成时间。4.区块生成与分叉区块生成流程1.收集交易，生成区块数据。

2.不断调整随机数nonce直到满足条件hcurrent<htarget。

3.广播区块，接受全网验证，通过后获得奖励。分叉问题及解决

网络延迟可能导致多个区块同时上链。

采用

最长链原则：选择最长的链作为主链，其他链回退，交易重新打包。3.2.2Pow共识算法5.关键挑战与问题51%算力攻击如果单个节点算力占全网总算力的51%以上，可篡改链条并主导主链生成。资源消耗大

大量算力导致电力浪费和资源损耗。

吞吐量低为降低分叉概率，区块生成速度较慢，无法满足高频应用需求。6.系统安全保障去中心化的实现算力分散：所有矿工均有机会生成新区块，避免单点风险。

长链原则：增加攻击成本，降低系统被篡改的可能性。数学难题平衡挖矿激励和系统安全性，避免分叉和资源浪费。区块结构

分叉情况3.3.1PoS共识算法1.背景与动机PoW共识算法的诞生资源消耗巨大，限制实际应用。每日需消耗大量算力和能源，只能用于达成共识，造成严重的资源浪费。PoS共识算法的提出受股份分红机制启发，权益论证以节点持有的股份（虚拟货币）决定其投票权重，降低资源消耗。2.核心概念验证者节点（Validator）节点通过投票虚拟货币作为股份参与投票，成为投票者节点。币龄（Coinage）币龄和虚拟货币作为股份的时间长短呈线性关系，即Coinage=k×time币龄随股份使用归零，无论是用于交易还是区块生成。PoS对比DPoS3.3.2PoS共识算法验证通过后，代币的币龄归零，以非股份形式返回持有者。奖励机制出块者获得奖励，受到关注参与讨论。5.PoS优势节能出块不依赖算力，依赖于持股比例和币龄。大幅降低能源与资源浪费，经济实用。公平性改进通过币龄清零机制，确保出块机会动态调整，唯一避免节点长期占优。3.区块生成流程与PoW的共同点均需解决数学难题。使用哈希值htarget，通过计算获取当前区块的哈希值hcurrent。PoS的改进引入币龄影响：只需要计算结果hcurrent<(htarget×Coinage)，便可以生成区块币龄，节点生成区块的概率越大。大幅减少算力和能源消耗。4.区块验证与奖励验证与广播出块者将包含已使用币龄的代币随区块广播到全网，提供其他节点验证。3.3.3PoS共识算法6.面临挑战安全性问题无利害关系攻击（NothingatStake）：攻击者以底部甚至无成本发起分叉攻击。币龄机制可能使攻击成本降低，系统更容易受到拜占庭行为的影响。公平性与激励的平衡如何既维持系统公平性，又激励节点长期参与。7.PoS的应用与场景改进方向典型应用比特币和以太坊等区块链系统逐步向PoS转型以减轻压力。改进方向增加攻击成本（如复合PoS共识算法）。引入更多参数调节出块权重，提升系统安全性和公平性。3.4.1DPoS共识算法1.背景与简介PoW和PoS的缺陷PoW：资源消耗巨大，算力集中化（矿池）。PoS：权益集中化趋势（大节点垄断）。DPoS目标结合PoW和PoS优势，避免其缺陷。通过委托机制，在保留去中心化的同时提升效率。2.角色与结构角色：1.候选人（Candidate）：通过注册成为见证人的候选节点。2.投票人（Voter）：持币者，有权投票选举见证人。3.见证人（Witness）：由投票人选出的代表节点，负责生成区块。权力制衡：投票人可以随时更新选票，支持或反对投票人。见证人权利有限，需接受社区监督。3.共识流程选举流程：1.错误注册：提供标识信息（介绍、网站等）。支付高额注册费用（生成单个区块奖励的上百倍）。2.投票机制：记录可信（Trusted）和非可信代表（Distrusted）。根据投票表现评分，维护观察代表（Observed）列表。投票产生见证人，并更新见证人列表。3.见证人轮流出块：见证人按乱序轮流生成区块，每个周期结束后重新选举见证人。3.4.2DPoS共识算法4.技术特点中心化与去中心化平衡：提前设计中心化权益的分配与制衡机制，避免矿池化或大节点垄断。高效区块生成：每轮见证人排序后轮循物料，提升系统吞吐量。EOS.io和BitShares实现上千到上万级交易吞吐量。投票与动态调整：投票权可随时调整，阻止权力固化。投票需持续参与以达成成本平衡。5.优势高饲料：相比PoW和PoS，大幅提升交易效率，适应商业需求。资源保护：避免PoW高算力消耗，减少资源浪费。用户参与兴趣：普通用户通过投票即可参与投票机制。3.4.3DPoS共识算法6.面临挑战部分去中心化的比重：系统设计初期即具有中心化趋势。部分投票人不积极参与投票，形成“运行中空”。安全性风险：权力风险集中可能导致决策效率下降或故障。投票质量问题：投票行为可能受到贿选等外部因素影响。7.适用场景与典型应用适用场景：高频交易、需要快速共识的区块链应用。商业化需求（如去中心化交易所、支付系统）。典型应用：EOS.io：提供企业级高效区块链服务。BitShares：去中心化交易平台。3.5.1PBFT共识算法3.核心过程

PBFT共识算法的核心过程有三个阶段，分别是预备（pre-prepare）、准备（prepare）和提交（commit）阶段1.背景与适用场景适用：场景联盟链，节点数量少，但对交易吞吐量和交易确定性要求高。理论基础：拜占庭普遍问题，提出需需要满足条件N≥3F+1，其中N为将军总数，F为叛变将军的数量，时间复杂度较高，为On(f+1)。算法优化：1999年，MiguelCastro和BarbaraLiskov提出PBFT，其同样满足N≥3F+1的数量要求，但是算法的时间复杂度降低到了On(2)。

2.PBFT核心机制Quorum机制quorum机制常被用于分布式系统中以保证数据冗余存储情况下结果的最终一致，实际上是一种投票机制。​PBFT共识算法的核心过程3.5.2PBFT共识算法为了实现PBFT算法，我们需要进行以下步骤：初始化系统：选择足够数量的节点来构成系统，并确保每个节点都知道其他节点的存在。请求处理：当节点收到请求时，它会将请求发送给其他节点进行prepare阶段的处理。消息传递：节点之间通过传递prepare和commit消息来达成共识。这些消息需要在一定的时间内被确认和响应。共识达成：当收到足够数量的prepare和commit消息后，节点就可以执行请求并写入数据。错误处理：如果节点发现其他节点存在问题或故障，需要进行相应的处理和恢复机制。PBFT共识算法视图变更流程3.6共识算法对比分析1.性能对比

PoW：低性能，交易确认时间长（10分钟）。

PoS：中等性能，交易确认时间较短（几秒到几分钟）。

PBFT：高性能，低延迟（秒级）。2.安全性对比

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

PoS：对51%攻击和女巫攻击有一定防范，但需合理设计代币分配。

PBFT：防范拜占庭故障，但不适用于大规模公有链。3.去中心化程度对比

PoW：高度去中心化，但矿池集中化问题严重。

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

PBFT：低去中心化，适用于小规模联盟链。4.资源消耗对比

PoW：高资源消耗（计算能力和能源）。

PoS：低资源消耗（持有代币）。

PBFT：低资源消耗（网络通信）。3.7共识算法的优化与改进1.混合共识机制（HybridConsensus）结合PoW和PoS的优势，利用PoW保障安全性，利用PoS提升效率。例子：Decred采用的PoW+PoS混合共识机制。2.分片技术（Sharding）将区块链网络分为多个小块（Shard），每个小块处理一部分交易，提升整体吞吐量。例子：以太坊2.0中的分片技术。3.DAG（有向无环图）共识算法摒弃传统区块链结构，采用图结构提高交易并发量。例子：IOTA采用的Tangle共识算法。服务器通过网络发送的任何消息都有可能会丢失，为了避免日志条目的缺失，保存到日志中的条目还需要额外保存添加这个条目时所在的任期

4.共识算法的应用4.Applicationofconsensusalgorithm044.1比特币共识算法1.区块链提高效率共识算法如工作量证明和权益证明，在区块链中确保交易安全性的同时，提高了网络处理交易的速度和效率。2.智能合约保障信任基于共识算法的智能合约自动执行，无需第三方介入，大大降低了欺诈风险，保障了交易双方的信任关系。以太坊工作量证明（PoW）挖矿难度调整网络稳定性网络稳定性工作量证明（PoW）工作量证明（PoW）工作量证明（PoW）工作量证明（PoW）权益证明(PoS)权益证明(PoS)以太坊升级权益证明(PoS)以太坊升级权益证明(PoS)权益证明(PoS)权益证明(PoS)以太坊升级以太坊采用工作量证明以太坊逐步转向权益证明权益证明(PoS)以太坊升级4.2以太坊共识算法4.3新型共识算法：1.去中心化程度不断提高随着区块链技术的发展，共识算法将更强调去中心化，如采用分片技术提高可扩展性，同时保持系统的去中心化特性。2.跨链共识成为新趋势随着多链和侧链的兴起，跨链共识算法成为研究热点，它们能实现不同区块链之间的价值转移和信息交互。3.安全性与性能持续增强共识算法将不断优化，通过密码学、分布式计算和智能合约等技术的结合，提升区块链网络的安全性和交易处理性能。4.3新型共识算法1.Algorand共识算法原理：采用VRF（可验证随机函数）选举出参与者，实现快速共识。创新点：高效、去中心化、安全。应用前景：适用于高性能公有链。2.Avalanche共识算法原理：利用随机抽样和子采样技术，实现快速、可靠的共识。创新点：高吞吐量、低延迟、高扩展性。应用前景：适用于需要高频交易的区块链应用。VRF（VerifiableRandomFunction）可验证随机函数4.3新型共识算法Algorand共识算法Algorand共识算法旨在通过随机选择用户来进行区块提议和投票，结合加密抽签和快速拜占庭协议，确保高效的共识达成且系统具备扩展性和安全性。1.节点角色与共识流程Algorand每轮共识过程中，节点可以扮演三种角色：区块提议者：用户所持资产越多，成为提议者的优先级越高，提议区块被选中为出块的概率越大。委员会成员：在全体用户中随机挑选的小规模节点集合，负责对提议的区块进行投票。普通节点：不参与提议或投票的用户节点。2.核心技术Algorand共识算法的核心由两大技术构成：加密抽签算法（CryptographicSortition）：通过可验证随机函数（VRF），以随机的方式选出区块提议者和委员会成员，难以被攻击者定位。快速拜占庭协议（BA）：用于低延迟达成共识，避免分叉。3.加密抽签过程系统首先使用VRF决定当轮的随机数种子，基于此随机数种子进行区块提议者和委员会成员的选择。用户的资产按最小单位被划分为若干“子用户”，每个子用户被选中的概率为固定的n/s。若某个子用户被选中，其所属用户成为提议者或委员会成员。4.3新型共识算法4.共识流程区块提议阶段：区块提议者广播区块，各节点收集提议并丢弃优先级较低的区块。区块Reduction阶段：各节点可能收到不同优先级的区块，需达成对优先级最高区块的共识。BinaryBA*阶段：在收敛的区块上进行多轮投票，直至系统达成共识。5.安全性与可扩展性抵抗女巫攻击：通过基于用户资产权重的抽签机制，防止攻击者通过伪造身份增加被选中概率。可扩展性：通过抽签选取少量节点组成委员会进行投票，有效减少计算负担，支持区块链扩展至大规模网络环境。总结来说，Algorand共识算法通过高效的随机选取和快速拜占庭协议，保证了系统的去中心化、安全性和可扩展性，适用于大规模区块链网络环境。

运行BinaryBA*，就唯一区块达成共识，记为hblock1等待一段时间，以接收区块

区块提议者选择优先级最高的子用户来广播区块和消息π区块Reduction，将目标区收敛至hblock2或空块

根据第r-1轮消息，确认第r轮种子seedr

通过VRF确定第r轮的区块提议者集合

统计final状态的投票信息，达成最终共识

Algorand共识算法的流程4.3新型共识算法HotStuff共识算法HotStuff共识算法是为了解决PBFT共识算法在处理视图变更时的复杂性问题，同时提升联盟链的性能表现，如交易吞吐量和网络带宽的需求。它通过简化视图变更流程和提高并行度，适用于高效的区块链共识。1.HotStuff的核心特性线性视图变更：HotStuff将视图变更（视图是共识过程的阶段）融入常规的共识流程，减少了复杂性。相比PBFT共识算法的非线性视图变更，HotStuff具备了线性视图变更（LinearViewChange），从而降低了处理视图变更的复杂度。时间复杂度降低：HotStuff将PBFT共识算法的时间复杂度由$O(n^2)$降低到了$O(n)$，主要通过减少从节点之间的消息广播，使得消息只在主节点和从节点之间传递。2.基本共识流程（BasicHotStuff）HotStuff的基本共识过程可以简化为围绕主节点进行的三轮投票：主节点职责：每个视图都有一个唯一的主节点，负责打包区块、收集和转发消息，并生成共识证书（QuorumCertificate,QC）。QC是主节点收集到$n-f$条从节点投票后生成的数据集合，包含共识阶段、视图编号、交易请求等信息。从节点简化消息传递：从节点不再相互广播消息，所有共识消息由主节点处理和转发，从而降低了网络复杂度，但提高了主节点的处理负担。3.HotStuff的五阶段流程HotStuff共识流程分为五个阶段：准备阶段（Prepare）：从节点向主节点发送new-view消息，主节点再向从节点广播共识消息。4.3新型共识算法5.性能与优化提升了系统活性：HotStuff延续了PBFT的三阶段共识，但增加了两个额外阶段来提高系统的整体活性。负担集中于主节点：虽然减少了从节点的消息传递负担，但这增加了主节点的计算和通信需求，对其性能提出了更高要求。总结来说，HotStuff通过简化视图变更、减少网络复杂度和提高并行度，实现了更高效的区块链共识流程，适用于需要大规模、低延迟共识的场景。HotStuff共识流程

2.预提交阶段（Pre-commit）：主节点向从节点发送消息，从节点返回确认消息。3.提交阶段（Commit）：主节点收集到足够多的确认消息后，进入下一个阶段。4.决定阶段（Decide）：主节点向从节点发送最终共识消息，节点执行共识。5.最终阶段（Final）：从节点将执行结果返回给客户端，完成共识流程。每个阶段的操作非常相似，都是由主节点发起消息，等待从节点的确认响应。4.ChainedHotStuff为了进一步提高并行度，HotStuff提出了ChainedHotStuff，将多个共识流程串联起来，实现并行共识。这解决了BasicHotStuff中每个阶段独立进行的局限性，使得多个共识过程可以重叠进行，提升系统效率。4.4

跨链共识1.Cosmos的Tendermint

原理：基于BFT共识，结合区块链间的互操作协议（IBC）。创新点：实现跨链通信和资产转移。应用前景：构建多链生态系统。2.Polkadot的RelayChain

原理：中心中继链（RelayChain）与多个平行链（Parachain）协同工作，确保不同链间的共识和通信。创新点：高安全性、高扩展性。应用前景：支持不同区块链网络的互操作性。4.5公有链共识算法PoW共识算法PoW（ProofofWork，工作量证明）共识算法是一种应对网络中可能存在的恶意节点（拜占庭节点）的机制。PoW共识算法的核心是哈希算法（见2.5节），能够将任何长度的输入，通过哈希函数转化为固定长度的输出，记作y=Hx()，其中H()被称为哈希函数，通常情况下将素数的模运算作为哈希函数，如Hx()=xmod11等。由哈希函数的定义可知，其具有正向计算快速简单，却很难做到逆向计算的特点，大多数情况下，不同的x会计算得到不同的y值，否则将发生哈希冲突。哈希冲突不是本书讨论的重点内容，感兴趣的读者可以在课后深入了解哈希算法的相关内容，以及如何处理哈希冲突的情况。在解数学难题的过程中，矿工需要先收集一组交易，并打包成一个区块得到区块数据data。然后矿工会生成一个随机数nonce，并将这个随机数与区块数据data和上一个区块的哈希值hprevious进行哈希运算，得到当前区块的哈希值hcurrent，即

hcurrent=H(data,nonce,hprevious)如果hcurrent≥htarget，那么矿工需要重新生成一个随机数nonce，重新进行哈希运算，直到hcurrent<htarget为止，那么随机数nonce就是数学难题的解。由此可见，htarget越小，数学难题的难度就越大，节点的求解过程越困难，需要调用的算力也就越多。因此，调整数学难题的难度可以通过控制区块生成的时间间隔来实现。

4.5公有链共识算法区块结构分叉情况当矿工得到数学难题的解后，会将hcurrent、nonce和hprevious打包添加到当前区块的区块头中，并向网络中广播，让其他网络中的节点进行验证。一旦验证得到通过，解题区块就可以得到相应的比特币奖励。

在比特币网络中，最先得到难题的解并通过验证的区块将被加入网络，完成上链。但由于实际中存在网络延迟等问题，可能部分节点在收到最新区块消息前也完成了求解，于是可能出现两个甚至更多区块同时上链的情况，这便是PoW共识算法的分叉（Fork）4.5

公有链共识算法PoS共识算法PoS（ProofofStake，权益证明）共识算法是一种旨在减少资源消耗并提高效率的区块链共识机制。以下是PoS共识算法的关键知识点：算法理念：PoS从股份概念中得到启发，认为持有货币的节点应有更多影响力。节点角色：拥有虚拟货币的节点可以将其转化为股份参与共识，这些节点被称为验证者（Validator）。币龄概念：币龄（Coinage）描述了节点持有货币作为股份的时间，与货币作为股份的时间长短呈线性关系。区块生成：PoS在生成区块时也需要解决数学难题，但解题难度考虑了币龄的影响，降低了计算资源消耗。出块机制：节点持有的币龄越大，越容易生成满足要求的区块，从而节省了计算资源。6.公平性：使用过的币龄在区块生成后会被广播到网络中进行验证，并通过验证后清零。7.能源效率：PoS算法相比PoW大大减少了能源和资源消耗，更为经济实用。8.安全性问题：PoS存在安全性缺陷，攻击者可能通过控制大量币龄来低成本地发起攻击，这被称为无利害关系攻击。9.比较PoW：PoW要求节点控制超过51%的算力才能发起攻击，而在PoS中，攻击者可能通过控制大量币龄来实现分叉。PoS共识算法通过考虑节点持有货币的量和时间来分配记账权，有效地减少了能源消耗，但同时也引入了新的安全挑战。这种算法在设计上试图平衡效率和安全性，但也需要持续的改进来应对潜在的攻击。4.5公有链共识算法DPoS共识算法节点角色：节点分为候选人（Candidate）、投票人（Voter）和见证人（Witness）。共识过程：持币者作为投票人，从候选人中选举出多个见证人，这些见证人负责区块的生成。去中心化与中心化：DPoS具有一定的去中心化特性，但相比PoW和PoS，它保留了更多的中心化特征。矿池与委托：DPoS认为在PoW和PoS系统中，用户趋向于加入矿池或委托第三方，形成中心化倾向。共识流程：包括选举见证人、见证人轮流生成区块，以及周期性的重新选举。候选人注册：候选人在注册时需要提供个人信息并支付高额的注册费用，以确保其认真履行责任。

7.投票机制：投票人可以对候选人进行投票，支持或反对他们成为见证人，并根据表现进行评分。8.系统效率：DPoS算法能够提供较高的交易吞吐量，满足大多数应用需求。9.中心化风险：尽管DPoS设计了权益分配和权利制约，但仍然存在中心化风险，因为一些投票人可能不履行投票职责。10.实际应用：DPoS被应用于EOS.io、BitShares等区块链系统中，以实现高效率和可扩展性。DPoS共识算法通过委托机制提高了区块链系统的效率和可扩展性，但这种算法在一定程度上牺牲了去中心化程度，需要在设计时就考虑到权益分配和权利制约，以避免中心化带来的潜在问题。4.6

联盟链共识算法PBFT共识算法PBFT共识算法的核心过程

PBFT共识算法视图变更流程1.PBFT共识算法背景PoW和PoS：常用于公有链，具有较高安全性，但吞吐量低，交易确认延迟高。联盟链需求：节点少，对吞吐量和交易确定性要求高。适用场景：

不考虑拜占庭错误：可采用RAFT轻量级共识算法。考虑拜占庭错误：优先选择PBFT共识算法。2.PBFT共识算法介绍定义：实用性拜占庭容错（PracticalByzantineFaultTolerance）算法。提出：由米格尔·卡斯特罗（MiguelCastro）和巴巴拉·利斯科夫（BabaraLiskov）在1999年提出。核心理论：满足条件N≥3F+1，其中N为节点总数，F为错误节点数量。优化：时间复杂度降低至O(n²)。3.Quorum机制来源：鸽巢原理。作用：确保数据冗余存储情况下的最终一致性，本质为一种投票机制。投票机制：读取操作需要的票数：qr。写入操作需要的票数：qw。需满足条件：qr+qw>n和qw>n/2。4.6

联盟链共识算法PBFT共识算法4.核心过程PBFT的共识过程分为三个阶段：预备阶段（Pre-prepare）：主节点广播预备消息，其他节点验证合法性。准备阶段（Prepare）：从节点广播准备消息，收集足够的准备消息（2f+1条）进入准备状态。提交阶段（Commit）：收集足够的提交消息（2f+1条），进入提交状态并执行操作。执行结果反馈给客户端。5.垃圾回收机制检查点流程：用于定期清理冗余的共识数据。每K次请求后执行一次检查点。高低水位机制：通过设定高水位（H）和低水位（h）限制系统缓存的数据量。6.视图变更机制触发条件：主节点失效或被认为存在问题时触发。视图编号更新：视图变更时，编号v+1，主节点切换到下一个节点。变更过程：节点广播view-change消息，附带旧视图共识日志。新主节点汇总view-change-ack消息，确认非拜占庭节点发出的变更请求，生成new-view消息，恢复必要的共识数据。7.PBFT共识算法的优缺点优点：抵抗拜占庭行为，保证高交易吞吐量。无分叉现象。缺点：通信复杂度高，达到O(n²)。无法防御女巫攻击，需额外模块辅助处理身份伪造问题。8.应用场景PBFT广泛应用于联盟链、分布式系统中，特别是对交易吞吐量和确定性要求较高的场景。

5.共识算法的未来发展5.Futuredevelopmentofconsensusalgorithms055.1挑战与机遇：1.算力要求日益增长随着区块链网络规模的扩大，共识算法对算力的要求越来越高，这增加了参与门槛和能源消耗。2.安全威胁日益严重近年来，针对共识算法的攻击事件频发，51%算力攻击和双重支付问题严重威胁了区块链系统的稳定性。3.去中心化与技术效率的平衡在去中心化追求与技术效率提升之间寻找平衡，成为共识算法发展的关键挑战之一。4.跨链共识技术兴起随着区块链技术的广泛应用，跨链共识技术成为连接不同区块链网络、实现价值互通的重要机遇。5.2共识算法的安全性1.51%攻击

-定义：攻击者控制了全网超过50%的计算能力或权益，能够篡改交易记录。

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

-定义：攻击者创建多个虚假身份以控制网络。

-防御机制：采用权益证明、引入身份验证机制。3.拜占庭容错问题（ByzantineFaultTolerance,BFT）

-定义：系统能在部分节点恶意或故障的情况下正常运行。

-例子：PBFT、Tendermint。5.3共识算法的数学基础1.博弈论

-定义：研究在不同参与者间决策的相互影响。

-应用：分析矿工在PoW中的策略选择、权益持有者在PoS中的投票行为。2.概率论

-定义：研究随机现象的数学理论。

-应用：评估共识算法中的随机选举机制（如Algorand中的VRF）。3.分布式系统理论

-定义：研究多个计算单元如何协同工作。

-应用：设计和分析共识算法的容错机制、性能优化。工作证明（ProofofWork,PoW）：在PoW中，节点通过解决复杂的计算问题来验证交易并添加新区块。比特币是一个使用PoW的典型例子。权益证明（ProofofStake,PoS）：在PoS机制中，验证者的选择基于其持有的代币数量和持有时间。以太坊等网络使用PoS共识。权威证明（ProofofAuthority,PoA）：PoA要求参与者以其身份和声誉作为抵押，适用于私有链场景，如供应链管理。覆盖证明（ProofofCoverage,PoC）：PoC用于验证网络热点确实提供了它们声称的无线网络覆盖。例如，Helium网络使用PoC。活动证明（ProofofActivity,PoA）：PoA结合了PoW和PoS的特点，例如，Decred网络就采用这种机制。身份证明（ProofofIdentity,PoI）：PoI通过比对用户私钥和授权身份来验证参与者的身份。思考题Reflectionquestions0601030204共识算法如PoW、PoS等各具特色，满足不同区块链项目需求，展现了技术创新的多样性。研究显示，采用成熟共识算法的区块链系统，如采用PoW的Bitcoin，在安全性方面表现优异，成功抵御了多次攻击。与早期PoW相比，PoS等新型共识算法在能源效率上有所提升，显著降低了区块生成成本，促进了区块链技术的可持续发展。共识算法如BFT、PBFT等通过节点间的相互验证，实现了网络的高度去中心化，增强了区块链系统的鲁棒性。共识算法多样性共识算法安全性共识算法效率共识算法去中心化1、

什么是分布式系统中的共识问题？共识正确性需要满足哪些特征？共识通信模型分类假设区别不选异步模型的原因共识通信模型主要包括同步模型、部分同步模型和异步模型，基于网络通信的不同假设。同步模型假设所有节点在同一时间步内完成通信，部分同步模型允许延迟但存在全局稳定时间，异步模型则无时间限制，导致共识难度增加。不基于异步模型研究共识问题，因异步网络下的不确定性使达成共识的算法设计和分析变得极为复杂且难以保证安全性。2、共识的通信模型有哪几类？其中的假设区别是什么？为什么不基于异步模型研究共识问题？拜占庭将军问题定义了分布式系统中可能遇到的节点故障模式，强调了在容错性设计中需考虑节点间信息不一致的复杂性。拜占庭问题定义了容错在分布式系统实现共识算法时，需解决拜占庭将军问题，确保即使在节点故障或恶意行为下，系统也能达成一致决策。对共识算法有重要影响3、什么是拜占庭将军问题？为什么此问题在分布式系统的研究中非常重要？4、

FLP不可能定理具体是指什么？其对共识算法的研究产生了什么影响？1.FLP定理定义共识局限FLP不可能定理指出，在异步系统中，即使网络是可靠的，也不存在一个能解决一致性问题的算法。它揭示了共识算法的固有局限。2.推动算法创新研究FLP定理激发了共识算法领域的创新，推动了如Paxos、Raft等实用性更强的分布式一致性算法的出现，这些算法在特定条件下实现了共识。3.促进容错性考量FLP定理促使研究者更加关注共识算法的容错性，因为在实际应用中，网络分区和节点故障是常态，需要算法能够在这些情况下保持一致性。5、试比较CAP理论和FLP不可能定理的区别和联系。1.CAP理论与FLP定理的差异性CAP理论关注分布式系统中一致性、可用性和分区容忍性的权衡，而FLP定理则强调在异步系统中，即使无故障，也可能无法就某个值达成决策。2.CAP与FLP定理的内在联系尽管CAP理论和FLP不可能定理聚焦不同，但二者均强调了分布式系统中的固有挑战，即网络通信的不确定性和系统组件的潜在故障对决策一致性的影响。6、Paxos和RAFT是针对于拜占庭将军问题模型的吗？如果不是，请说明其模型弱化了哪些拜占庭将军问题中的假设。1.Paxos和RAFT非针对拜占庭Paxos和RAFT共识算法并非直接针对拜占庭将军问题设计，它们基于更简单的故障模型，假设节点故障是崩溃-停止型，而非拜占庭型。2.弱化节点行为假设拜占庭将军问题假设节点可能发送任意信息，而Paxos和RAFT仅假设节点可能失效不响应或提供旧信息，不涵盖任意欺诈行为。3.强化网络可靠性Paxos和R