区块链共识算法分类总结

2022/02/12 笔记导图区块链

以下为 mindmanager 的预览

Full Screen

概述

介绍

数据同步的方法

所谓“共识机制”，是通过特殊节点的投票，在很短的时间内完成对交易的验证和确认；

对一笔交易，如果利益不相干的若干个节点能够达成共识，我们就可以认为全网对此也能够达成共识。

再通俗一点来讲，如果中国一名微博大V、美国一名虚拟币玩家、一名非洲留学生和一名欧洲旅行者互不相识，
但他们都一致认为你是个好人，那么基本上就可以断定你这人还不坏。

指可以使用所有节点对某一种状态达成一致的方式，
有共识机制去中心化才有意义，才具备可信度，否则只是数据共享

目前主流的共识机制有：POW、POS、DPOS、PBFT等

所有记账节点之间怎么达成共识，去认定一个记录的有效性，这既是认定的手段，也是防止篡改的手段。当加入区块链的节点足够多的时候，基本上不可能伪造出一条不存在的记录，从而杜绝了造假的可能。

区块链的共识机制通常包含了两个方面

达成共识的计算机算法，即共识算法（Consensus Algorithm）

达成共识的规则，即共识规则（Consensus Rule）

分布式一致性算法（共识机制）

什么是共识，什么是共识算法？

……

Paxos

Raft

所有记账节点之间怎么达成共识，去认定一个记录的有效性，这既是认定的手段，也是防止篡改的手段。
区块链提出了四种不同的共识机制，适用于不同的应用场景，在效率和安全性之间取得平衡。

区块链的共识机制具备“少数服从多数”以及“人人平等”的特点，其中：

“少数服从多数”并不完全指节点个数，也可以是计算能力、股权数或者其他的计算机可以比较的特征量。

“人人平等”是当节点满足条件时，所有节点都有权优先提出共识结果、直接被其他节点认同后并最后有可能成为最终共识结果。 [8]

以比特币为例，采用的是工作量证明，只有在控制了全网超过51%的记账节点的情况下，才有可能伪造出一条不存在的记录。
当加入区块链的节点足够多的时候，这基本上不可能，从而杜绝了造假的可能。

即便在网络通信可靠情况下，
一个可扩展的分布式系统的共识问题通用解法的下限是——没有下限（无解）

目的

让分布式数据记录不可逆

选择节点产生区块

作用

分布式系统对某个提案，大部分节点达成一致意见的过程

在区块链系统中没有像银行一样的中心化机构，所以在进行传输信息、价值转移时，共识机制解决并保证每一笔交易在所有记帐节点上的一致性和正确性问题。
区块链的这种新的共识机制使其在不依靠中心化组织的情况下，依然大规模高效协作完成运转

数据一致性要解决哪些问题

以谁的数据为准
- 任何结点都可以修改自己所下载的账本，也就是任何一个人都可以伪造账本
- 在去中心化的网络下，我们只能认为，大多数人认识的数据是对的。
  只要我控制了一半以上的结点，我让这 “ 大多数人 “ 伪造同一份账本，那么相当于整个账本都被我修改过来了
- 因为在没有服务器的去中心化的网络下，所谓的真理只不过是大多数人同意的东西。
“ 大多数人 “ 的问题
- 是人数吗？在网络世界里，我可以用程序模拟出无穷多的 “ 人 “ 出来投票，
  所以，用人数来解决去中心化的问题，在分不清是人还是狗，是生物还是程序的计算机世界里，是一件很愚蠢的事。
意见分歧问题
- 如果在同一个时刻，有多个人都在告诉其它人，这账应该这么记有人说，我转了10块给gg，又有人说，xx转了20块给我

提案，包括：发生顺序、某个键对应的值、谁是主节点…，比较宽泛

多节点系统最关键的是对多个事件的顺序进行共识，即排序

评价标准

资源消耗

性能效率

Pow

Pos

较高

DPoS

PBFT

扩展性

对不同加密算法的支持

安全性

特点

一致性

分布式网络数据的一致性

一个公司内的分布式系统中的结点是被假设成可信任的
而在去中心化的网络下，所有结点要被假设成不可信任的
cap定理
- 在一致性、可用性和分区容忍性上只能三选两。在区块链的 P2P 网络下也是很类似的，在去中心化、安全和高性能中，我们也只能选两个

所有诚实节点保存的前缀一致

有效性

由诚实节点发送的数据会达到其他诚实节点

区块链同步基本流程

发送节点将新的数据全网广播

接收节点对数据进行校验，数据记录纳入区块

全网所有接收节点对区块执行共识算法

区块通过共识后，纳入区块链存储。

问题

隔离见证

交易和结算分开

原因是当前比特币确认时间过长

达到安全的状态需6个区块确认，约1小时

双花

双重支付

同一个钱，用两次

理论上说，超过全网51%的算力，就能改账本，完成双花

预防双花

后面查资料看看呗

种类

公链

工作量证明(Proof of Work，简称POW)

定义

工作量证明
可简单理解为一份证明，证明你做过一定量的工作。
通过查看工作结果，就能知道你完成了指定量的工作。
区块链共识算法用的最多的就是POW。比特币和以太坊都是基于POW的共识机制。
- 例
  - 比特币在区块的生成过程中使用的就是POW机制，
  - 简单理解就是大家共同争夺记账权利，谁先抢到并正确完成记账工作，谁就得到系统的奖励，奖励为比特币，也就是所谓的“挖矿”。
  - 矿工（参与挖矿的人）通过计算机的算力去完成这个记账工作，这个拥有计算能力的专业计算机就是所谓的“矿机”。
目前有很多数字资产用pow发行新币
开放性和匿名性，意味着任何节点可以随时进入这个网络，即使是恶意节点。
区块的生成和发送，意味着对整个区块链状态的修改。
- 对状态的修改，必须要付出一定的成本，这里面就是算力，增大攻击的成本。
  - ……
在一个不可信的网络环境（节点不可信，网络不可信）下，如何就状态，在不同的节点之间达成一致
新区块生成条件
- ……
  - 要求 10 分钟一个区块， 2016 个区块的时间就是 2 个星期 ( 2016 * 10 * 60 / ( 24 * 60 * 60) = 14 days)
  - 根据时间偏差来对应的调整难度值
  - 调整幅度有最大/最小比例
比喻
- 谁的算力大，谁就更大的几率做出记账
  - 举例子：比如生成的hash后面几位需要为0.你计算了多少次拿到了这个结果。

评价

特点
- 1、算一道很难的题，系统给予挖矿奖励
- 2、多劳多得
优点
- 1、所有节点均可参与，记账权公平的分派到每个节点，去中心化
- 2、多劳多得，矿工积极性高
- 3、安全性高，欺诈成本高，如果能够欺诈成功，那么做诚实节点收益更大
缺点
- 1、主流矿池垄断严重，存在51%算攻击风险
- 2、浪费资源严重
- 3、持币人没有话语权，算力决定一切
- 4、网络性能低，共识时间长

评价

优点
- 完全去中心化，节点自由进出，避免了建立和维护中心化信用机构的成本。
- 只要网络破坏者的算力不超过全网总算力的50%，网络的交易状态就能达成一致，并不可篡改历史记录。
- 投入越多算力，获得记账权概率越大，越有可能产生新的区块奖励。
缺点
- 目前比特币挖矿造成大量的算力和能源浪费。
- 挖矿的激励机制也造成挖矿算力的高度集中
  - 随着算力的集中，渐渐向中心化演变
    - 算力集中于占据了大多数算力矿池
- 结算周期长，每秒最多结算7笔交易，不适合商业应用。

POW – 农耕文明

需要“工作量证明”来声明新区块
pow：工作量证明，放弃了高性能
- 挖矿：用大规模的计算来找到一个符合系统要求的区块 ID
  - 要找到符合条件的区块 ID 只能通过暴力穷举的方式，所以要付出大量的系统计算资源和电力。
- 修改几乎变得不可能
  - 试想，如果生成一个区块需要大量的长时间的计算力。也就是在世界上最好的电脑集群下计算 10 分钟才能打好一个包，那么，当我们要去修改数据内容的时候，这个过程也是一样的。前面说过，如果你要伪造一个块，那么你就要修改后面所有的块，修改一个块的成本如此之高，那么修改整个链的成本也就非常之高了
- 能掌握 51% 的算力的人也变得几乎不可能
  - 除了伪造一条链的成本很高，还要控制大多数人的算力，这意味着，是一个非常大的金钱的投入。这两个难度加起来，几乎不太可能。
- 解决分歧
  - 一方面，这么大的工作量找出来的区块 ID，已经有效地降低了大家有意见冲突的概率。
    另一方面，就算是出现了合法冲突的区块（同时出现了多个合理的区块，即区块链出现分支 / 分叉），也就是多个合法的账本。而因为挖矿的成本太高，导致要同时跟进多个账本是不可能的，所以矿工们只能赌跟其中一个。
    大多数人所选择的那一个分支的链就会越来越多，于是另外一边也就无人问津，从而作废了。
- pow机制存在的问题
  - 越来越中心化地记账
  - 越来越跑不动

工作量证明机制：pow

工作量证明机制即对于工作量的证明，
是生成要加入到区块链中的一笔新的交易信息(即新区块)时必须满足的要求。
在基于工作量证明机制构建的区块链网络中，节点通过计算随机哈希散列的数值解争夺记账权，求得正确的数值解以生成区块的能力是节点算力的具体表现。
工作量证明机制具有完全去中心化的优点，在以工作量证明机制为共识的区块链中，节点可以自由进出。
大家所熟知的比特币网络就应用工作量证明机制来生产新的货币。
然而，由于工作量证明机制在比特币网络中的应用已经吸引了全球计算机大部分的算力，其他想尝试使用该机制的区块链应用很难获得同样规模的算力来维持自身的安全。
同时，基于工作量证明机制的挖矿行为还造成了大量的资源浪费，达成共识所需要的周期也较长，因此该机制并不适合商业应用。

工作量证明（POW）

问题
- 公地悲剧问题

使用项目

比特币、以太坊、比原链等

其他

原理
- 通过找到合理随机数争夺记账权

权益证明(Proof of Stake，简称POS)

定义

通过持有Token（代币）的数量和时长来决定你获得记账的机率，
类似于股票的分红制度，持有股权越多的人就能够获得更多的分红。
Token相当于区块链系统的权益。
2012年，化名Sunny King的网友推出了Peercoin，该加密电子货币采用工作量证明机制发行新币，
采用权益证明机制维护网络安全，这是权益证明机制在加密电子货币中的首次应用。
- 与要求证明人执行一定量的计算工作不同，权益证明要求证明人提供一定数量加密货币的所有权即可。
- 权益证明机制的运作方式是：
  - 当创造一个新区块时，矿工需要创建一个“币权”交易，交易会按照预先设定的比例把一些币发送给矿工本身。
    权益证明机制根据每个节点拥有代币的比例和时间，依据算法等比例地降低节点的挖矿难度，从而加快了寻找随机数的速度。
    这种共识机制可以缩短达成共识所需的时间，但本质上仍然需要网络中的节点进行挖矿运算。
    因此，PoS机制并没有从根本上解决PoW机制难以应用于商业领域的问题。
随着代币的集中，渐渐向中心化演变
需要“财产证明”来声明新区块
- 根据持有数字货币的数量与时间，进行利息发放和区块产生的机制
比喻
- 谁有的区块链资产多大，谁就更大的几率做记账
- 资本主义模式，钱越多，责任越多

评价

优点
- 降低了PoW机制的资源浪费。
- 加快了运算速度，也可以理解为工作量证明的升级版
缺点
- 拥有币龄越长的节点获得记账权的几率越大，
  容易导致马太效应，富者越富，权益会越来越集中,从而失去公正性。

POS – 资本主义

pos：股权证明，放弃了安全
- 在 PoS 机制下，矿工不在叫矿工，而是叫 Validator（校验者）
- pow 好像是 “ 多劳多得 “ 的社会，而 pos 更像是 “ 资本主义 “ 社会，钱越多的人越有话语权
- pos的好处
  - 不需要那么费劲的挖矿了。那样浪费电力不环保地挖矿的确有点太糟糕了。PoS 很明显地解决了这个问题。
  - 在 PoS 下，你需要有 51% 的财富，你才可以发起攻击，这相对于算力而言需要更多的成本。设想一下，你得拥有 51% 的比特币，你才能黑了比特币，然而，如果你有 51% 的财富，你为什么要黑了这个系统，自己把自己干死呢？
- pos潜在的问题
  - 双重支付的问题

3、POS(股权证明)

特点
- 1、不挖矿，依靠币龄(币持有数量 * 持有天数)决定记账权，利息即为奖励，记账后币龄清零
- 2、按钱分配，钱生钱
优点
- 1、在一定程度上缩短了共识达成的时间
- 2、节约资源
- 3、防作弊，币龄越大，获得记账权几率越大、避免51%攻击，会因为攻击会使自己权益受损
缺点
- 1、数字货币过于集中化，富者越来越富有，散户参与积极性低
项目
- ADA等

委托权益证明(Delegated Proof of Stake，简称DPOS)

概述

股份授权证明机制
- Delegated Proof Of Stake
股份授权证明机制是一种新的保障网络安全的共识机制。
它在尝试解决传统的PoW机制和PoS机制问题的同时，
还能通过实施科技式的民主抵消中心化所带来的负面效应。
- 股份授权证明机制与董事会投票类似，该机制拥有一个内置的实时股权人投票系统，就像系统随时都在召开一个永不散场的股东大会，所有股东都在这里投票决定公司决策。
  基于DPoS机制建立的区块链的去中心化依赖于一定数量的代表，而非全体用户。
  在这样的区块链中，全体节点投票选举出一定数量的节点代表，由他们来代理全体节点确认区块、维持系统有序运行。
  同时，区块链中的全体节点具有随时罢免和任命代表的权力。如果必要，全体节点可以通过投票让现任节点代表失去代表资格，重新选举新的代表，实现实时的民主。
- 股份授权证明机制可以大大缩小参与验证和记账节点的数量，从而达到秒级的共识验证。
  然而，该共识机制仍然不能完美解决区块链在商业中的应用问题，因为该共识机制无法摆脱对于代币的依赖，而在很多商业应用中并不需要代币的存在。
用户票选代理人。由代理人轮流生成新区块
代理人相互制约，确保不会伪造
类似董事会投票机制
代理权益证明，放弃了去中心化
- DPoS 已经开始把区块链的去中心化的初衷开始向中心化的地方演进了
- DPoS 就是政治主义社会。
  谁的选票多谁说话，但是感觉又回到了中心化架构中的 Leader 选举
是基于POS衍生出的更专业的解决方案，类似于董事会投票，指拥有Token的人投票给固定的节点，选举若干代理人，由代理人负责验证和记账。
不同于POW和POS的全网都可以参与记账竞争，DPOS的记账节点在一定时间段内是确定的
通过不同的策略，不定时地选中一小群节点，这一小群节点做新区块的创建、验证、签名和相互监督。
这样就大幅度减少了区块创建和确认所需要消耗的时间和算力成本。
比喻
- 每个有币节点投票，产生100名候选人。随机选取一个股东来产生区块。轮流记账

评价

特点
- 不挖矿
- 每年按比例增发代币
- 奖励超级节点
优点
- 相较pow，dpos大幅提高区块链处理数据的能力，甚至可以实现秒到账，同时也大幅降低维护区块链网络安全的费用
- 高效、扩展性强
缺点
- 去中心程度较弱，节点代理是人为选出的，公平性相比POS较低，依赖于代币的增发来维持代理节点的稳定性
- 21个节点太少，非去中心化，而是多中心化

项目

其他

DPOS – 社会主义

联盟链

实用拜占庭容错算法（Practical Byzantine Fault Tolerance，简称PBFT）

概述

Practical Byzantine Fault Tolerance
PBFT，是联盟币的共识算法的基础。
实现了在有限个节点的情况下的拜占庭问题，有3f+1的容错性，并同时保证一定的性能。
该算法在保证活性和安全性的前提下提供了（n-1）/3的容错性。
主要实现的有拜占庭容错的NFS文件系统。

应用

联盟链和私有链
- Hyperledger组织下的Fabric项目使用的是该算法

私链

验证池共识机制Pool

定义

Pool验证池
Pool验证池基于传统的分布式一致性技术建立，并辅之以数据验证机制，是目前区块链中广泛使用的一种共识机制。
- 基于传统的分布式一致性技术，加上数据验证机制，是目前行业链大范围在使用的共识机制。
Pool验证池不需要依赖代币就可以工作，在成熟的分布式一致性算法(Pasox、Raft)基础之上，
可以实现秒级共识验证，更适合有多方参与的多中心商业模式。
不过，Pool验证池也存在一些不足，例如该共识机制能够实现的分布式程度不如PoW机制等。

评价

优点
- 不需要依赖代币也可以实现秒级共识验证
  - 不需要代币也可以工作，在成熟的分布式一致性算法（Pasox,Raft）基础上实现秒级共识验证。
缺点
- 去中心化程度弱，更适合多方参与的多中心商业模式
  - 去中心化程度不如bitcoin，适合多中心的商业模式

paxos

概述

Paxos算法是莱斯利・兰伯特( Leslie Lamport,现就职于微软研究院)于1990年提出的，是一种基于消息传递的一致性算法。
莱斯利・兰伯特于2013年获得了图灵奖。他的分布式计算理论莫定了这门学科的基础。
菜斯利・兰伯特在1978年发表了论文《分布式系统内的时间、时钟事件顺序》(Time, Clocks, and the Ordering of Events in a Distributed System),
这篇论文成为目前计算机科学史上被引用最多的文献。他的论文为并发系统的规范与验证课题的研究贡献了核心原理。
Paxos算法是在莱斯利・兰伯特的论文 The Part- Time Parliamen中提出的。
在论文中，他以故事的方式讲述了 Paxos算法
- 古希腊有一个叫 Paxos的岛屿，是爱琴海上的一个小島， Paxos是一个兴盛的商业贸易中心。
  在这个岛屿上，法律的制定与修订通过议会表决的形式进行，而非传统的神权治。
- 所有法律都必须经由议会成员授票表决后才能生效实范，而且已通过的律法必须被记录在案。
- 在岛上，商业繁荣，做生意赚钱才是头等大事，因此没有人愿意始终在议会大斤里从头到尾参与每一个法律表决的会议。
  为此，每一个议员都来维护一个法律律簿，用来记录一系列已通过的法令，每个法令带有一个唯编号。
  为了保持各个议员法律律薄内容的一致性，法律律簿是用擦不掉的墨水书写而成的，所以内容一旦书写就不能改变。
- 在议会中有多个角色的成员：议员和服务员。
  服务员的工作是在比较曹杂的议会厅里传递信息，议员的工作是发起法律提案或将通过的法律记录在自己的法律律簿上。
- 由于议员和服务员有可能并不可靠，他们可能随时会因为各种事情临时甚至是彻底离开议会大斤，服务员也有可能重复传递消息，
  当然也可能有新的议员在临时事务处理完毕后再回到议会大厅进行法律表决，
  因此议会的协议要求保证在上述情况下能够正确地修订法律并且不会产生冲突。
- 在法律表决时，议员的角色分为 proposers和 acceptors
- 通过一个法律决议时，分为两个阶段：
  - 阶段1: prepare阶段
    - proposer选择一个提案编号n,并将 prepare请求发送给 acceptors群体。
    - acceptor收到 prepare消息后，如提案的编号大于它已经回复的所有prepare消息，
      则 acceptor将自己上次接受的提案回复给 proposer,并承诺不再回复小于n的提案；
      如果提案的编号小于等于它已经回复的所有 prepare消息，则说明是重复消息，不再重复处理。
  - 阶段2:批准阶段
    - 当 proposer收到多数 acceptors对 prepare的回复后，就进入批准阶段。
      它要向回复 prepare请求的 acceptors发送 accept请求。
      acceptor收到accept请求后，则立即接受这个请求。
Paxos 问题是指分布式的系统中存在故障（crash fault），但不存在恶意（corrupt）节点的场景（即可能消息丢失或重复，但无错误消息）下的共识达成问题。
解决分布式系统中一致性问题的共识算法（Consensus Algorithm），其最基本的功能是为了在多个进程之间对某个值达成一致。
通过这个最基本功能，就可以在多个进程之间进行数据库、状态机、账本（区块链）等对象的同步。
被广泛应用在 Chubby、ZooKeeper 这样的分布式系统中。类似于两阶段提交算法

基本原理

三个角色
- 1. Proposer。
    提案者，用于提出议案，提案的内容为：令 x=value，对同一轮提案，最多提议一个value
- 1. Acceptor。
    投票者，完全对等，在独立的时间轴执行提案投票
- 1. Learner。
    学习者，一个提案超过半数accpetor通过即可被chosen，其他未确定的Acceptor可以通过learner来同步结果
两阶段
- 1. Prepare阶段
    - 1.Proposer选择一个提案编号N，向所有的Acceptor广播Prepare(N)请求
    - 2.Acceptor收到Prepare(N)请求，若提案编号N比之前接收的Prepare请求都要大，则承诺(Promise，将N记录下来)将不会接收提案编号比N小的提议，
      并且带上之前Accept的提议中编号小于N的最大的提案value(没有则为NULL)。如果N比之前接受的提案编号小，则不予理会。
- 1. Proposal阶段
    - 1.Proposer收到Acceptor的Promise。
      - 如果未超过半数的Accpetor回复承诺(Promise)则本次提案失败；
      - 如果超过半数的Acceptor回复承诺，又分为不同情况：
        
        如果(回复承诺的)所有Acceptor都未接收过value(都为null)，
        那么向所有的Acceptor发起(Propose)自己的value和提案编号N。
        
        如果有部分Acceptor接收过value，那么从接受过的value中选择提案编号N最大对应的value作为本次提案的value，
        提议编号仍然为N(此时Proposer不能提议自己的value，只能信任Acceptor通过的value，以达成收敛的效果)
    - 2.Acceptor接收到Proposal后，如果该提案编号N不等于自身当前承诺的编号(第一阶段记录的)，
      不接受该请求，相等则将提案的value写入本地
理解
- 分布式抢占锁
  - Prepare阶段–申请加锁，Proposal阶段–修改并释放锁
  - 只有超过半数的Acceptor同意，加锁才成功；
    否则可能存在多个申请加锁的客户端
  - 每个Proposer都可能失效，独占锁机制下获得独占锁定权的Proposer失效会导致死锁
  - 提案编号由Proposer自己维护，一般采用递增机制且全局唯一。
    这样就可以对提案进行全局排序，只有提案编号高的(最新)的提案被接受，避免了死锁

文章

raft

定义

raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。在这里强调了是在工程上，因为在学术理论界，最耀眼的还是大名鼎鼎的Paxos。
但Paxos是：少数真正理解的人觉得简单，尚未理解的人觉得很难，大多数人都是一知半解。
本人也花了很多时间、看了很多材料也没有真正理解。直到看到raft的论文，两位研究者也提到，他们也花了很长的时间来理解Paxos，他们也觉得很难理解，于是研究出了raft算法。
raft是一个共识算法（consensus algorithm），所谓共识，就是多个节点对某个事情达成一致的看法，即使是在部分节点故障、网络延时、网络分割的情况下。
这些年最为火热的加密货币（比特币、区块链）就需要共识算法，而在分布式系统中，共识算法更多用于提高系统的容错性，比如分布式存储中的复制集（replication），
在带着问题学习分布式系统之中心化复制集一文中介绍了中心化复制集的相关知识。
raft协议就是一种leader-based的共识算法，与之相应的是leaderless的共识算法。
Raft算法的头号目标就是容易理解（UnderStandable），这从论文的标题就可以看出来。
当然，Raft增强了可理解性，在性能、可靠性、可用性方面是不输于Paxos的。
- Raft more understandable than Paxos and also provides a better foundation for building practical systems
- 为了达到易于理解的目标，raft做了很多努力，其中最主要是两件事情：
  - 问题分解
  - 状态简化
问题分解是将”复制集中节点一致性”这个复杂的问题划分为数个可以被独立解释、理解、解决的子问题。
在raft，子问题包括，leader election， log replication，safety，membership changes。
而状态简化更好理解，就是对算法做出一些限制，减少需要考虑的状态数，使得算法更加清晰，更少的不确定性
（比如，保证新选举出来的leader会包含所有commited log entry）
Raft implements consensus by first electing a distinguished leader, then giving the leader complete responsibility for managing the replicated log.
The leader accepts log entries from clients,replicates them on other servers, and tells servers when it is safe to apply log entries to their state machines.
A leader can fail or become disconnected from the other servers, in which case a new leader is elected.
上面的引文对raft协议的工作原理进行了高度的概括：
raft会先选举出leader，leader完全负责replicated log的管理。
leader负责接受所有客户端更新请求，然后复制到follower节点，并在“安全”的时候执行这些请求。
如果leader故障，followes会重新选举出新的leader。
Raft 通过远程过程调用(RPC)来实现节点间的通信, 定义了下面几种 RPC:
- RequestVote RPC: 由 candidate 调用, 用于进行 leader 选举.
- AppendEntries RPC: 由 leader 调用, 用于复制日志或作为心跳信息(维持leader).

这就涉及到raft最新的两个子问题

leader election
- 相关概念
  - term
    - 任期
      - 从上面可以看出，哪个节点做leader是大家投票选举出来的，每个leader工作一段时间，然后选出新的leader继续负责。
        这根民主社会的选举很像，每一届新的履职期称之为一届任期，在raft协议中，也是这样的，对应的术语叫term。
      - ……
      - term（任期）以选举（election）开始，然后就是一段或长或短的稳定工作期（normal Operation）。
        从上图可以看到，任期是递增的，这就充当了逻辑时钟的作用；
        另外，term 3展示了一种情况，就是说没有选举出leader就结束了，然后会发起新的选举，后面会解释这种split vote的情况。
- 选举过程详解
  - 上面已经说过，如果follower在election timeout内没有收到来自leader的心跳，
    （
    也许此时还没有选出leader，大家都在等；
    也许leader挂了；
    也许只是leader与该follower之间网络故障
    ）
    ，则会主动发起选举。
  - 步骤如下：
    - 增加节点本地的 current term ，切换到candidate状态
    - 投自己一票
    - 并行给其他节点发送 RequestVote RPCs
    - 等待其他节点的回复
  - 在这个过程中，根据来自其他节点的消息，可能出现三种结果
    - 收到majority的投票（含自己的一票），则赢得选举，成为leader
      - 第一种情况，赢得了选举之后，新的leader会立刻给所有节点发消息，广而告之，避免其余节点触发新的选举。
        在这里，先回到投票者的视角，投票者如何决定是否给一个选举请求投票呢，有以下约束：
        
        在任一任期内，单个节点最多只能投一票
        
        候选人知道的信息不能比自己的少
        （这一部分，后面介绍log replication和safety的时候会详细介绍）
        
        first-come-first-served 先来先得
    - 被告知别人已当选，那么自行切换到follower
      - 第二种情况，比如有三个节点A B C。
        A B同时发起选举，而A的选举消息先到达C，C给A投了一票，当B的消息到达C时，已经不能满足上面提到的第一个约束，即C不会给B投票，而A和B显然都不会给对方投票。
        A胜出之后，会给B,C发心跳消息，节点B发现节点A的term不低于自己的term，知道有已经有Leader了，于是转换成follower。
    - 一段时间内没有收到majority投票，则保持candidate状态，重新发出选举
      - 第三种情况，没有任何节点获得majority投票，比如下图这种情况：
      - ……
      - 总共有四个节点，Node C、Node D同时成为了candidate，进入了term 4，但Node A投了NodeD一票，NodeB投了Node C一票，这就出现了平票 split vote的情况。
        这个时候大家都在等啊等，直到超时后重新发起选举。如果出现平票的情况，那么就延长了系统不可用的时间（没有leader是不能处理客户端写请求的），
        因此raft引入了randomized election timeouts来尽量避免平票情况。同时，leader-based 共识算法中，节点的数目都是奇数个，尽量保证majority的出现。
log replication
- 当系统（leader）收到一个来自客户端的写请求，到返回给客户端，整个过程从leader的视角来看会经历以下步骤：
- 请求完整流程
  - leader append log entry
  - leader issue AppendEntries RPC in parallel
  - leader wait for majority response
  - leader apply entry to state machine
  - leader reply to client
  - leader notify follower apply log

性质

Election Safety:
- 最多只有一个节点成为 Leader.
Leader Append-Only:
- Leader 不会删除或覆盖自身的日志, 只会不断将新的日志附加到日志末尾.
Log Matching:
- 如果两条日志(log entry)的term和index相同, 那么从这两条日志开始, 她们和她们前面的所有日志都对应相同.
Leader Completeness:
- 如果一条日志在一个 term 中被 commit 了,
  那么在该 term 之后的所有 term 中, 这些 term 的 Leader 的日志中都包含这条日志.
State Machine Safety:
- 如果一个节点应用了一条日志到状态机, 那么其他机器不会应用一个 index 与此日志相同, 内容却不同的日志到状态机.
  也就是说, 对于不同节点应用到状态机的日志, 只要 index 相同, 日志就是相同的.

POA

定义

POA(Proof of Activity)
- 行动证明
链上节点相互信任
授权证明（PoA）是PoS一致性算法的子集，主要由测试网和私有或联盟网络使用。
在基于PoA的区块链中，交易有效性最终由一组经批准的链上账户确定，称为“授权节点”。
确定授权节点的标准是通过网络治理结构中编写的方法确定性地决定的。
PoA被广泛认为是达成共识的最快途径，但依赖于验证节点尚未受到损害的假设。
非验证参与者可以像公共以太网那样访问和使用网络（通过利用p2p交易，合约，账户等）
PoA共识依赖于验证者的声誉和过去的表现。这个想法是验证者节点将其身份/声誉放到我的身上。
私人联盟网络的一个重要方面是链上地址与已知的现实世界身份之间的联系。
因此，我们可以说验证节点正在盯着他们的“身份”或“声誉”（而不是他们的经济持有）。
这为验证者创建了一定程度的问责制，最适合企业，私有或测试网络。
PoA目前由测试网络Kovan（PoA网络）使用，并且可以在Parity中轻松配置用于私人联盟网络。
Combine Proof of Work component with a Proof of Stake.
mining first begins in the traditional manner, with miners vying to be the first to solve a puzzle and claim their reward.
The difference is that the blocks being mined do not contain transactions.
They are simply templates with header information and the mining reward address.
Once this nearly blank block is mined, the system switches to a proof of stake protocol.
The header information is used to select a random group of validators to sign the block.
These are coin holders (stakeholders) and the larger the stake a validator holds, the greater the chance they will be selected to sign the new block.
Once all the chosen validators sign the block it becomes an actual part of the blockchain.
If the block remains unsigned by some of the chosen validators after a given time, it is discarded as incomplete and the next winning block is used.
Validators are once again chosen and this continues until a winning block is signed by all the chosen validators.
The network fees are split between the winning miner and the validators who signed the block.

其他

POA – 共产主义

其他

ripple

瑞波币

小蚁共识

总结

每一种共识机制都不能同时满足安全、效率、公平。去中心程度越弱，安全性就越低，区块链的速度就越快；去中心化程度越强，安全性就会越高，区块链的速度就会越慢。

POW完全去中心化，但运行效率太低。 POS提高了效率，但却降低了公平与安全。 DPOS有强烈的中心化特性，却在短期内效率最高。

目前行业区块链大范围使用Pool共识。

其他

问题与挑战

如何提出一个待共识的提案？如通过令牌传递、随机选取、权重比较、求解难题…
如何让多个节点对该提案达成共识（同意或拒绝），如投票、规则验证…

故障节点：非拜占庭节点恶意节点：拜占庭节点非拜占庭场景的典型例子是通过报数来统计人数，即便偶有冲突（如两人同时报一个数）也能很快解决；拜占庭场景的一个常见例子是“杀人游戏”，当参与者众多时很难快速达成共识。

共识机制（数据同步）

特性

少部分写，多读

打赏

支付宝

微信

RBAC权限模型 - 基于角色的访问控制

区块链的种类

本文作者：Tako

永久链接：http://takostar.net/2022/02122235/