🗒️共识机制

一 共识机制

1. 共识：一群各方面差异性的人在某方面达成一致意见并上升成共同遵守的规则。 共识机制：一个群体用以达成并维护共识的方式。

2. 范围：网络环境； 作用对象：所属权各异的计算机； 逻辑：去中心化方式进行记账。

3. 两个问题： ①完全对等的节点之间如何竞争记账权 ②同时获得记账权后如何处理(保留最长链)。

4. 共机与分布网络关系： ①区块链是一个分布式系统 ②共识机制负责安全地更新分布式网络中的数据状态，使其状态达成统一。

5. 共机作用： ①是决定按照哪一个参与节点记账和确保交易安全完成的重要手段 ②同时满足一致性和有效性 ③可确保区块链不存在区别对待从而达到公平分配 ④具有激励的能力。

二 分布式系统

1. 节点：可独立按分布式协议完成逻辑的程序个体。OS进程。物理/虚拟机。

2. 通信：节点之间完全独立相互隔离，通过不可靠的网络通信。发消息节点无法确认消息是否被接收节点完整正确收到。

3. 存储：将数据写入与节点同一本地存储设备保存数据。 存储读取数据节点为有状态节点，反之无~。

4. 异常： 机器宕机， 网络异常(①消息丢失：网络拥塞，路由变动，设备异常②消息乱序：ip网络存储转发机制，路由不确定性③数据错误：比特错误，校验后丢弃④不可靠TCP：网络异常导致)， 存储数据丢失， 无法归类异常。

5. 三态：成功，不~(失败/超时) 。

6. 副本：fbsxt中为数据或服务器提供的冗余。 数据副本：不同节点上持久化同一份数据。

7. 副本一致性：fbsxt通过副本控制协议使得从系统外部读取系统内部各个副本的数据在一定的约束条件下相同。 ①强一致性：任何时刻任何用户或节点都可读到最近一次成功更新的副本数据 ②单调~：任何时刻用户一旦读到某数据某次更新后的值，此用户不会再读到比这个值更旧的值 ③会话~：任何用户在某次会话一旦读到某个数据在某次更新后的值，此用户在这次会话过程中不会再读到比这个值更旧的值 ④最终~：一旦更新成功，各副本的数据最终将达到完全一致，但所需时间不能保障 ⑤弱~(副本可能一致)：一旦更新成功，用户无法在确定时间内读到这次更新的值，且即使在某个副本上读到了新的值，也不能保证在其他副本上可以读到新的值。

8. 性能： ①系统吞吐能力：系统某时间可处理的数据总量，每秒处理的总数据量 ②响应延迟：完成某功能所需时间 ③并发能力：同时完成某功能的能力，QPS来衡量。 可用性：系统面对各种异常时可正确提供服务的能力(衡量：系统停服务与正常服务时间的比，某功能失败与成功次数的比)。 可扩展性：fbsxt通过扩展集群机器规模提高系统性能（吞吐延迟并发）、存储容量、计算能力的特性。 一致性：fbsxt为提高可用性使用副本的机制引发副本一致性问题。

三 分布式系统一致性

1. 一致性：fbsxt中多个服务节点在特定协议保障下操作对外呈现的状态一致，即保证集群中所有服务节点中的数据完全相同并且能够对某个提案达成一致。

2. 模型假设分类： ①每个节点的计算能力及其失效模式 ②节点间通信的能力及是否可能失效 ③整个系统的属性如时序。

3. 网络模型：据时序模式分为同步(所有节点时钟误差有上限，网络传输时间有上限)、异步网络(节点时钟漂移无上限，传输时间任意长，计算速度不可料)。

4. 故障模型： ①拜占庭故障：系统会发生任意类型错误，错误节点为bzt节点(硬件错误、宕机，发生错消息) ②崩溃-恢复：比bzt多了一限制，节点总按照程序逻辑执行，结果正确但不保证消息返回的时间 ③崩溃-遗漏：比恢复多了一非健忘，节点崩溃之前能把状态完整保存在持久存储上，启动后可再次按照以前状态继续执行和通信 ④崩溃-停止：理想化故障模型，节点故障后立即停止接收和发送所有消息，或者网络出现故障无法进行任何通信。

5. 一致性算法：bzt容错、崩溃容错(容错：系统一个或多个关键部分故障时能自动进行检测与诊断并采取相应措施保证系统维持规定功能)。

6. 拜占庭将军问题：bzt几个师驻扎地城外，他们必须制定共同计划，才能攻或撤，且只有半数以上将军共同进攻时才能胜利，但是可能有将军是叛徒，阻止行动达成一致，或叛徒是信使，篡改或伪造消息。内涵：缺少可信任中央节点和可信任通道情况下，网络中各个节点如何达成共识。如何在存在恶意行为的情况下使分布式系统达成一致。

7. 解决方案： ①口信消息型：正确传达已发送消息，接受者知道谁发的，可检测消息缺席。发伪造消息。指挥官先发，副官接收。指挥官忠/判都能一致。m个叛徒需m+1轮协商至少3m+1个将军才一致 ②签名消息型：增加：忠将签名无伪造且内容修改会发现，任何人能验证将军签名真伪。签名无法篡改和伪造。任何数量叛将。忠先发：收到更改过的消息则转发人为叛；叛先发：收到不一样的消息则先发人为叛。

8. FLP定理：在异步通信场景即使只有一个进程失败，也没有任何算法能保证非失败进程达到一致性。 模型： ①异步通信(同步区别：没有时钟，不能时间同步、超时、探测失败，消息可任意延迟、乱序) ②通信健壮(只要进程非失败，消息无限延迟但最终会送达且仅一次) ③fail-stop(进程失败不再处理任何消息，不产出错误消息) ④失败进程数量(最多一个)。

9. 分布式算法衡量标准： ①终止性：非失败进程最终可做出选择，有限时间内结束不能无限循环 ②一致性：所有进程必须做出相同决议 ③合法性：进程决议值必须是其他进程提交的请求值，排除进程初始值干扰)。 Configuration：所有进程组成的状态。 不确定Con~：一系列操作后没有进程做出决策，后续可能做出提交或回滚的决议。反之，能准确做出决议为确定，一致性可达成。 极端：每次都构造一个不确定Con(异步场景无法区分进程失败和消息延迟)。

10. CAP定理：无法设计分布式协议能同时满足三个属性，只能折中：一致性(副本一致性始终指强~)、可用性(服务始终可用)、分区容忍(协议可容忍任何网络分区异常)。

四 分布式一致性算法

1. 两阶段提交：用于分布式数据库实现分布式事务。 节点：中心化协调者节点，参与者节点。 流程：协调者询问参与者可否投票；根据投票结果做出可全局提交的决定。

2. Paxos：在工程角度实现最大化保障fbsxt一致性的机制。问题：服务器宕机或网络断开，随时有新机器加入。 节点： ①proposer提案者：提出value ②acceptor批准者：value超M/2+1acceptor才通过（M为acc总数） ③learner学习者：读取结果，至少读取M/2+1至多M结果才能学习到一个通过value。

3. proposer： ①准备：发prep（b）（收到reject（b），b+1重来） ②批准：若收到prom（b，v）中m/2+1的value为空，则选一个value作为v发acc（b，v）；不空则acc（b, vi）。（vi为i最大的value）(收到Nack（B），b+1重来)

4. Acceptor： ①准备：收prep（b），回prom（b，v_B），b＞B则B=b（b为当前轮数，B为该actor改之前最大轮数，v为acc批准的value）；若b＜B则回reject（B） ②批准：接收acc（b，v），V=v并回acced.(若当前b<B，回Nack（B）)。

5. 批准value无法改变：pre（b）的b＞B，B都+1，V多一个v1。

6. RAFT：三个子问题： ①选举：leader宕机或集群初创时，需选举新leader ②日志复制：leader接收来自客户端的请求并将其以日志形式复制到集群中其他节点，并强制要求其他节点日志和自己保持一致 ③安全性：若任何服务器节点已经应用了一个确定的日志到状态机，其他节点不能在同一日志索引位置应用不同指令。

7. 选举： ①初始都为follower，term=0，同时启动选举定时器 ②Fol转为candidate，term自增，并发送投票请求并重置选举定时器 ③投票策略：票投给请求节点或自己的term更大的 ④投票过半的can转为lea，其他节点收到定时发送的心跳并转为fol与lea保持同步。

8. 日志复制： ①客户端请求提交到lea：lea把收到的请求作为日志条目entry（状态未提交，lea不更新，∴不可读）写入本地日志 ②lea将AppendEntry随心跳并行发其他fol，并让它们复制这条entry ③lea等待fol回应：写入本地日志返回success，一致性检查失败则拒绝，返回false（lea把新entry紧接之前条目的索引位置，任期号term。若fol找不到，则拒绝新entry，∵fol和lea不一致） ④lea回客户端ok，表示写操作成功 ⑤lea随心跳通知fol将entry标为已提交。

9. 安全性： ①electionSafety：任意term内最多选举一lea ②leaderAppend-Only：lea只追加不重写不删除本地log ③logMatching：若俩节点日志相同index和term则[0，index]内log一致 ④leaderCompleteness：日志项在被commit的term后任意lea都有该项 ⑤stateMachineSafety：后续server应用本地状态机已应用的相同日志项。

五 共识机制算法

1. Pow工作量证明：hash运算，证明你做过一定量工作。 角色：工作者，验证者。 思想：分布式节点的算力竞争保证数据一致性和共识安全性。 区块体：MerkleTree算法生成mk根hash。 特点：效率低，资源消耗大，去中心化程度低。

2. pos权益证明：权益记账。 原理：提高节点处理数据门槛，每隔一段时间重新选择满足一定条件的节点。 币龄：决定记账权，持币数量×时间。 特点：无算力竞争浪费，币龄清零更公平，健壮性强，弱化去zxh。

3. dpos委托权益证明：选举见证人。 特点：能耗低，交易快，节点收益不合理，投票积极性低，安全隐患。

4. pbft拜占庭容错：总结点数|R|=3f+1，恶意f，正常2f+1，可容忍＜1/3个恶意，主节点p=v𝑚𝑜𝑑|r|，v视图编号，r节点个数，p主节点编号。若副节点i收到2f+1个验证通过的commit则已共识。客户端收到f+1个相同reply，则客户端请求已过时。

5. 共识算法对比： ①pow：记账节点选取方式：拥有最高算力的节点易获得新区块的记账权和区块奖励。 优：简单，可操作性强，节点自由加入或退出，可扩展性强。 缺：浪费电力资源，依赖专业挖矿硬件，算力集中在几大矿场之间，有中心化风险且效率低，交易吞吐量小 ②pos：拥有最高权益~。 优：降低pow机制算力浪费，不依赖专业挖矿硬件，节点自由加入或退出，可扩展性强。 缺：寡头优势，需完善pos“无利害关系”问题，吞吐量小，平台手续费高 ③dpos：由拥有权益的节点选出前N个超级节点作为新区块的记账节点，这些受理人轮流获得记账权和区块奖励。 优：高吞吐量，更快确认时间，降低能源损耗，节省区块确认时间，减少交易延迟，吞吐量提高，节点自由加入或退出，可扩展性强。 缺：超级节点投票麻烦，投票期间需锁定代币，不利于激发普通节点参与，超级节点固定数量，去中心化有争议 ④pbft：取模p=v𝑚𝑜𝑑|r|。 优：共识结果一致、正确性程度高，确认时间快。 缺：算法复杂度较高，通信量大，无法避免恶意节点成为主节点。

6. 性能：pow，pos，dpos，pbft： ①bzt容错%：50,50,50,33 ②出块时间s：＞500，＜100，＜100，＜10 ③交易吞吐量tps：＜10，＜1000，＜1000，＜2000 ④可扩展性：强,强,强,弱