【01】共识机制

BTF共识

拜占庭将军问题

拜占庭将军问题是一个共识问题

起源

Leslie Lamport在论文《The Byzantine Generals Problem》提出拜占庭将军问题。

核心描述

军中可能有叛徒，却要保证进攻一致，由此引申到计算领域，发展成了一种容错理论。随着比特币出现和兴起，这个著名问题又重入大众视野。

问题描述

假如5位拜占庭将军分别各率领一支军队共同围困一座城市，各支军队的行动策略只有进攻和撤退两种，低于3支部队则无法攻打下来反而会被反攻。

因为背负军队进攻，部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所以军队一起进攻或所有军队一起撤离。

因为各位将军分处城市不同方向，他们只能通过信使互相联系。

在投票过程中每个将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

可能出现的问题

假如有5支部队，低于3支部队则无法攻打下来反而会被反攻，有2支部队选择进攻，2支选择撤退；

这时候出现一个叛徒，对其中2支选择进攻的部队送信说要进攻，选择进攻的部队一看有3支部队选进攻则进攻；

叛徒对2支选择撤退的部队送信说要撤退，选择撤退的部队一看有3支部队选择撤退则撤退了，最终2支部队攻城失败，整个部队失败。一致性遭到破坏。

前置条件

拜占庭将军问题中不考虑通讯兵是否会被截获或无法传达信息等问题，即认为消息传递的信道绝无问题。

拜占庭将军问题中每个将军间彼此不信任，他们需要反复进行消息传递。

问题分析

拜占庭将军问题实际上就是一个互不信任对方构成的网络，但是又必须携手努力达成最终目的的过程；

对于各个将军而言，达成共识并不像想象中那么简单，每个将军都可能出现传递错误信息、单独行动、拖延时间等各种问题；

最重要的事情：如何达成共识攻破城堡。

拜占庭将军问题≠两军问题

拜占庭将军问题和两军问题看起来有点相似，但是问题的实质是不一样的。

两军问题

白军驻扎在沟渠里，绿军则分散在沟渠两边。白军比任何一支绿军都更为强大，但是绿军若能同时合力进攻则能够打败白军。他们不能够远程沟通，只能派遣通讯兵穿过沟渠去通知对方，协商进攻时间。

是否存在一个能使绿军必胜的通信协议，这就是两军问题。

两军问题中通讯兵需要穿过白军区域，他可能被捕，即信息传输通道不一定可靠，同时也没有叛徒。

两军问题的根本在于信息传递通道的不可靠，如果传递信息通道完全可靠，那么就不存在两军问题，绿军随时打败白军。

形式化

仅靠“一致”就可以解决问题吗？

如果万事俱备，客观上每个忠诚的将军只要进攻了就一定能够胜利，但是却因为叛徒的存在有可能他们都“一致的”没有进攻；反之，条件不利，将军们不应该进攻，但是却因为叛徒的存在导致所有人都“一致的”进攻了。最后也可能导致失败。

只靠“一致性”是不足以解决拜占庭将军问题的，还必须满足“正确性”。

如果客观来看或许会有“绝对正确的”判断，但针对每一个将军，大家的判断或许都不相同，我们如何定义“正确”呢？

正确就是每个忠诚的将军都正确地表达了自己的意思，不会因为叛徒让别的将军认为忠诚的将军是叛徒而不采用他传达的消息。

因此，拜占庭将军问题可以简化描述如下：

所有忠诚的将军都能让别的将军接收到自己的真实意图，并最终一致行动。

形式化的要求就是“一致性”与“正确性”。

抽象

求解拜占庭将军问题，隐含要满足以下两个条件：

每个忠诚的将军必须收到相同的命令值Vi（Vi是第i个将军的命令）。
如果第i个将军是忠诚的，那么他发送的命令和每个忠诚将军收到的Vi相同。

拜占庭将军问题可以描述为：一个发送命令的将军要发送一个命令给其余n-1个将军，使得：

所有忠诚的接收命令的将军遵守相同的命令；
如果发送命令的将军是忠诚的，那么所有忠诚的接收命令的将军遵守所接收的命令

拜占庭将军问题在一个分布式系统中，是一个非常有挑战性的问题。

修复

解决拜占庭将军问题有两种办法

口头协议

实现起来简单，但是算法复杂，同时需要克服的困难更多

口头协议具有以下假设

每个被发送的消息都能够被正确地投递
信息接收者知道是谁发送的消息
能够知道缺少的消息

结论

采用口头协议，若叛徒数少于1/3，则拜占庭将军问题可解。也就是说，若叛徒数为m，当将军总数n至少为3m+1时，问题可解。

口头协议算法就是把自己的命令告诉其他人，采取少数服从多数的原则来得到自己的结论。

但要注意的是，别的将军传来的命令是通过算法递归的方法来确定的。

利用这个方法，可以保证在叛徒数量少于1/3的情况下，忠诚的将军可以实现一致性和正确性要求，即问题可解。

书面协议

算法本身很简单，却能够克服很多问题，但是实现算法并不容易。

在口头协议中，叛徒可以说谎，口头协议不能追本溯源，如何解决如此棘手问题？

结论

书面协议的本质就是引入了签名系统，这使得所有消息都可追本溯源。这一优势，大大节省了成本，他化解了口头协议中1/3要求，只要采用了书面协议，忠诚的将军就可以达到一致。

PBFT算法

由来

PBFT是Practical Byzantine Fault Tolerance的缩写，意为实用拜占庭容错算法。

该算法是Miguel Castro和Barbara Liskov在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。

该论文发表在1999年的操作系统设计与实现国际会议上，作者之一Barbara Liskov就是提出著名的里氏替换原则（LSP）的人，同时也是2008年图灵奖得主。

核心

PBFT算法可以在失效节点不超过总数1/3的情况下同时保证Safety和Liveness。即满足n>=3f=1,n是系统中的总节点数，f是允许出现故障的节点数，同时少数服从多数原则。

为什么PBFT算法最大容错节点数量f是(N-1)/3?

假定节点总数是N，作恶节点数为f，那么剩下的正确节点数为N-f，意味着只要收到N-f个消息且N-f>f就能做出决定，但是这N-f个消息有可能有f个是由作恶节点冒充的（活因网络延迟导致f个恶意节点的消息被先收到），那么正确的消息就是N-f-f个，为了多数一致，正确消息必须占多数，也就是N-f-f>f，所以最少是3f+1个。

5个概念

client：请求（request）自愿者。
replica：副本，所有参与提供服务的节点
primary：主节点，承担起提供服务主要职责的节点。
backup：其他副本，但相对于primary角色。
view：视图，处于存在primary-backup场景中的相对稳定的关系。

如果primary出现故障，这种相对稳定的视图关系就会转变（transit）。比如军长叛逃等，系统也就从视图a转变为视图b（a，b均为整数）。

primary-backup

在一个view里，一个replica会是主节点（primary），其余的replica都叫备份节点（backups）。

主节点负责将来自client的请求给排好序，然后按序发送给备份节点们。

但是主节点可能会是faulty的：它可能会给不同的请求编上相同的序号，或者不去分配序号，或者让相邻的序号不连续。

备份节点应当有职责来主动检查这些序号的合法性，并能通过timeout机制检测到主节点是否已经宕机。

当出现这些异常情况时，这些备份节点就会触发view change协议来选举出新的主节点。

quorums

quorums有两个重要的属性

Intersection：任意两个quorums至少有一个共同的并且正确的replica

Availability：总是存在一个没有faulty replicas的quorum

如果一个replica把信息写给一个quorum，并让该quorum来存储信息，在收到每一个quorums中的成员的确认反馈后，那么我们可以认为该replica的信息已经被可靠地保存在了这个分布式系统中。

这是强的约束，当然还有一个weak certificates：就是至少f+1个节点来共同存取信息，这样至少有一个正确的replica存到了这份信息。

基本流程

Client：客户端节点，负责发送交易请求。

Primary：主节点，负责将交易打包成区块和区块共识，每轮共识过程中有且仅有一个Primary节点。

Replica：副本节点，负责区块共识，每轮共识过程中有多个Replica节点，每个Replica节点的处理过程类似。

PBFT算法的基本流程主要有四步：

客户端发送请求给主节点
主节点广播请求给其他节点，节点执行PBFT算法的三阶段共识流程
节点处理完三阶段流程后，返回消息给客户端
客户端收到来自f+1个节点的相同消息后，代表共识已经正确完成。

算法的核心三个阶段分别是pre-prepare阶段（预准备阶段），prepare阶段（准备阶段），commit节点（提交节点）。

三种协议

系统正常运行在一致性协议和检查点协议下，只有当主节点出错或者运行缓慢的情况下才会启动视图更换协议，以维持系统继续响应客户端的请求。

一致性协议

一致性协议的目标是使来自客户端的请求在每个服务器上都按照一个确定的顺序执行。

协议基本流程

客户端发送请求给主节点（如果请求发送给了从节点，从节点会将该请求转发给主节点或者将主节点的信息告知客户端，让客户端发送给主节点）。
主节点将请求广播给从节点。
主从节点经过2轮投票后执行客户端的请求并响应客户端。
客户端收集到来自f+1个不同节点的相同的响应后，确认请求执行成功。（因为最多有f个恶意节点，f+1个相同即能保证正确性）。

协议主要包括三个阶段：pre-prepare阶段（预准备阶段），prepare阶段（准备阶段），commit节点（提交节点）。

REQUEST

首先是客户端发起请求，请求<REQUEST, o, t, c>中的时间戳t主要用来保证exactly-once语义，也就是说对同一客户端请求不能执行2次的情况，具体实现时也不一定非是时间戳，也可以是逻辑时钟或者其他，只要能唯一标识这个请求就可以了。

PRE-PREPARE

主节点收到客户端的请求消息后，先判断当前正在处理的消息数量是否超出限制，如果超出限制，则先缓存起来，再打包一起处理。否则的话（当然，没超过也可以缓存处理），对请求分配序列号n，并附加视图号v等信息生成PRE-PREPARE消息<<PRE-PREPARE, v, n, d>,m>，广播给其他节点，简而言之就是对请求分配序号并告知所有节点。
从节点收到PRE-PREPARE的消息后进行如下处理：
1. 消息合法性检查，消息签名是否正确，消息摘要是否正确
2. 视图检查，检查是否同一个视图号v。
3. 水线检查，判断n是否在h和H之间（h一般是系统稳定检查点，H是上限，会随着h的不断提高而提高）

如果都通过的话，从节点就广播PREPARE消息<PREPARE, v, n, d, i>给其他节点，表明自己收到并认可[n, v]这个请求，进入prepare阶段，如果没有通过，则忽略该消息。

PREPARE

所有节点收到PREPARE消息<PREPARE, v, n, d, i>后，进行如下处理：

消息合法性检查，消息签名是否正确，消息摘要是否正确
视图检查，检查是否是同一视图号v
水线检查，判断n是否在h和H之间。

如果上面都通过，就将PREPARE消息加入到日志中，并继续收集PREPARE消息，如果收到正确的2f个（包括自己）PREPARE消息，就进入COMMIT阶段，广播COMMIT消息<COMMIT, v, n,D(m), i>。

COMMIT

在上一阶段，节点收到足额PREPARE投票后会广播COMMIT投票，过程类似，当节点收到其他节点的COMMIT投票消息后，会进行如下检查：

消息合法性检查，检查消息签名是否正确，消息摘要是否正确
视图检查，view是否匹配
水线检查，判断n是否在h和H之间。

如果都通过，则把收到的投票消息写入日志log中，如果收到的合法的COMMIT投票消息大于等于2f+1个（包括自己），意思就是，已经确认大多数节点都准备好了执行请求，就执行请求并回复REPLY消息给客户端。这里如同上面一样，也是检查视图，序号及消息是否匹配。

客户端收到REPLY后，会进行统计，如果收到f+1个相同时间戳t和响应值r，则认为请求响应成功。

如果在规定的时间内没有收到回应或者没有收到足额回应怎么办？可以将该请求广播给所有节点，节点收到请求后，如果该请求已经被状态机执行了，则再次回复客户端REPLY消息，如果没有被状态机执行，如果节点不是主节点，就将该请求转发给主节点。如果主节点没有正常地将该请求广播给其他节点，则将会被怀疑是主节点故障或恶意节点，当有足够的节点都怀疑时将会触发视图变更协议，更换视图。

检查点协议

为什么需要设置检查点？

为了节省内存，系统需要一种将日志中的无异议消息记录删除的机制。

为了保证系统的安全性，副本节点在删除自己的消息日志前，需要确保至少f+1个正常副本节点执行了消息对应的请求，并且可以在视图变更时向其他副本节点证明。另外，如果一些副本节点错过部分消息，但是这些消息已经被所有正常副本节点删除了，这就需要通过传输部分或者全部服务状态实现该副本节点的同步。

因此，副本节点同样需要证明状态的正确性。在每个操作执行后都会生成这样的证明是非常消耗资源的。因此，证明过程只有在请求序号可以被某个常数（比如100）整除的时候才会周期性地进行。

我们将这些请求执行后得到的状态称作检查点（checkpoint），并且将具有证明的检查点称作稳定检查点（stable checkpoint）。

如何进行垃圾回收（日志清理）？

如果一个请求已经被f+1台非拜占庭节点执行，并且某一服务器节点i可以向其他服务器节点证明这一点，那么该i节点就可以将关于这个请求的日志删除。

协议一般采用的方式是服务器节点每执行一定数量的请求就将自己的状态发送给所有服务器并且执行一个该协议，如果某台服务器节点收到2f+1台服务器节点的状态，那么其中一致的部分就是至少有f+1台非拜占庭服务器节点经历过的状态。

因此，这部分日志就可以删除，同时更新为较新状态。

水线检查

检查点协议可以用来更新水线（watermark）的高低值（h和H），这两个高低值限定了可以被接受的消息。

其中，低水线h值等同于稳定检查点，稳定检查点之前的日志都可以被清理掉。高水线H=h+k，也就是接收请求序号上限值，因为稳定检查点往往是间隔很多的序号才触发一次，所以k一般要设置足够大。例如，每间隔100个请求就触发一次检查点协议，提升水线，k可以设置为200。

视图更换协议

一旦主节点自身发生错误，就可能导致从节点接收到具有相同序号的不同请求，或者同一请求被分配多个序号等问题，这将直接导致请求不能被正确执行。

视图更换协议的作用

在主节点不能继续履行职责时，将其用一个从节点替换掉，并且保证已经被非拜占庭服务器执行的请求不会被篡改。

总结核心有2点

当主节点故障时，可能造成系统不可用，要更换主节点；
当主节点是恶意节点时，要更换为诚实节点，不能让作恶节点作为主节点。

当检测到主节点故障或为恶意节点触发视图更换时，下一任主节点应该如何选出？

PBFT的办法是采用“轮流上岗”的方式。通过(v+1) mod N，其中v为当前视图号，N为节点总数，通过这一方式确定下一个视图的主节点。

什么时候触发视图更换协议呢？

针对主节点故障的情况，具体实现包括：

从节点会维护一个定时器，如果长时间没有收到来自主节点的消息，就会认为主节点发生故障。此时可以触发视图更换协议。

也可以是客户端发送请求给故障主节点必然导致长时间收不到响应。所以，客户端将请求发送给了系统中所有从节点，从节点将请求转发给主节点并启动定时器，如果主节点长时间没有将该请求分配序号发送PRE-PREPARE消息，认为主节点故障，触发视图更换协议。

其他几种触发视图更换的情况包括：

从节点广播PREPARE消息后，在约定的时间内未收到来自其他节点的2f个一致合法消息。

从节点广播COMMIT消息后，在约定时间内未收到来自其他节点的2f个一致合法消息。

从节点收到异常消息，比如视图、序号一致，但消息不一致。

这三点，都有可能是主节点作恶导致的，但也有可能是消息丢失等原因导致的。虽然不一定是因为主节点异常导致的，但从另一个角度看，解决了从节点不能无限等待其他节点投票消息的问题。

补充说明：触发视图更换协议后，将不再接收除检查点消息、VIEW-CHANGE消息、NEW-VIEW消息之外的消息，也就是视图更换期间，不再接收客户端请求、暂停服务。

视图更换，具体如何实现？

当因上面的情况触发视图更换协议时，从节点i就会广播一个VIE-CHANG消息<VIEW-CHANGE, v+1, n, C, P, i>，序号n是节点i的最新稳定检查点s，C是2f+1个有效检查点消息，是为了证明稳定检查点s的正确性，P是位于序号n之后的一系列消息的结合。

这里包含的这些信息可以理解为是证据，也就是说，从节点不能随便就发送一个VIEW-CHANGE，什么证据都没有，别人怎么能认同你更换视图呢？上面我们提到过下一任主节点是谁的问题？通过确定的下一任主节点p（在图中就是节点1），在收到2f个有效的VIEW-CHANG消息后，就广播<NEW-VIEW, v+1,V, O>消息，主要是VIEW-CHANGE和PRE-PREPARE等消息构成的集合，主要目的是为了让从节点去验证当前新的主节点的合法性以及解决下面这个问题，还有要处理未确认消息和投票消息。

如何保证已经被非拜占庭服务器执行的请求不被更改？

由于系统达成一致性之后至少有f+1台非拜占庭服务器节点执行了请求，所以目前采用的方法是：

由新的主节点收集至少2f+1台服务器节点的状态信息（也就是上面在构造消息时所需的各种消息集合），这些状态信息中一定包含所有执行过的请求；然后，新主节点将这些状态信息发送给所有的服务器，服务器按照相同的原则将上一个主节点完成的请求同步一遍，同步之后，所有的节点都处于相同的状态，这时就可以开始执行新的请求。

在3阶段协议中，对收到的消息都要进行消息合法性检查、视图检查、水线检查这3项检查，为什么呢？

添加消息签名是为了验证投票是否合法，正确统计合法票数，不能是随便一个不知道的节点都能投票，那么我们怎么验证到底是谁呀？也就是说，要通过消息签名的方式确认消息来源，通过消息摘要的方式，确认消息没有被篡改。当然，考虑到性能因素，也可以使用消息认证码（MAC)，以节省大量加解密的性能开销。PBFT算法，可以容忍节点作恶，消息丢失、延时、乱序，但消息不能被篡改。

视图检查比较容易理解，所有节点必须在同一个配置下才能正常工作。如果节点的视图配置不一致，比如主节点不一致、节点数量不一致，那统计合法票数的时候，真没法干了。

水线检查，是检查点协议的一部分，在工程实现时，不是所有的请求我都有处理，比如，你收到一个历史投票信息，你还有必要处理吗？当然，它的作用不止于此，还可以防止恶意节点选择一个非常大的序列号而耗尽序列号空间，例如，当一个节点分配了超过H上限的序列号，这时，正常节点会拒绝这个请求从而阻止了恶意节点分配的远超过H的序列号。

蚂蚁链共识

在蚂蚁区块链中，共识协议被定义成使分布式系统中的节点快速有效地达成数据的一致性，即确保所有诚实节点以完全相同的顺序执行共识结论中交易，达成数据一致性，同时正确的客户端发送的有效交易请求最终会被处理和应答。

蚂蚁区块链平台的共识组件通过提供不同的共识插件来实现共识协议。

目前，蚂蚁区块链系统已实现的共识协议包括MyBTF共识协议和MyTumble共识协议。

共识与BTF算法

共识是分布式系统各节点达成一致性的过程，一致性指各节点数据的值相同，保持各节点的一致性是系统能安全对外提供服务的关键。

在分布式系统中，拜占庭错误节点可以表现出任意行为，如改变自己的状态、发送内容错误的消息或者向不同进程发送不同的消息等。

拜占庭容错（Byzantine Fault Tolerance，BFT）共识算法则是为解决拜占庭错误（Byzantine Fault）而设计的。

拜占庭容错共识（BTF）算法的目标是，在一个含拜占庭错误节点的比例不超过某个阈值的系统中，使得所有正确节点就目标值达成一致，同时保证系统的可用性与活性。

MyBFT共识协议

MyBFT是蚂蚁区块链提供的拜占庭容错共识，是对PBFT协议的改进，其特点如下：

共识窗口流水线：当一个区块被共识完成交付执行的同时，后续的区块提议能继续被共识，形成共识-执行流水线；
状态持久化：能容忍任意数量的诚实节点宕机后重启；
能容忍不超过节点总数1/3的拜占庭节点；
共识交易哈希：交易数据提前广播，减少主节点带宽压力；
支持运行时的配置、共识节点、共识算法等动态变更，变更也是通过共识以后在链上完成。

基于以上特点，MyBFT共识协议适用于大规模集群、网络环境好、高吞吐场景。

MyTumble共识协议

以PBFT为代表的半同步共识算法，有以下两个弊端：

依赖一个主节点进行区块提案，因此主节点容易成为系统瓶颈，而且影响公平性；
引入半同步的时间假设，正确性和效率依赖于对时间参数的选取。

MyTumble是蚂蚁链自主研发的一种纯异步共识算法，其特点是：

每个节点都可以独立提案，不依赖单一的主节点；
纯消息驱动，不需要引入超时机制；
与市面上其他异步算法（如HoneyBadger）相比，MyTumble首创将定序和共识上链两个步骤分离，不强制要求每个节点在每个区块号上参与提案，大大增加了共识定序的灵活性

由于MyTumble是一种高效低延迟的异步共识协议，在百节点广域网中延迟能降到1秒以下，在网络情况不稳定时表现出更强的鲁棒性，因此适用于广域网大规模集群、网络高延迟、不稳定的网络。

共识算法概述

工业和信息化部人才交流中心发布的《区块链产业人才岗位能力要求》对共识算法的定义是：

区块链系统中各分布节点对事务或状态的验证、记录、修改等行为达成一致确认的方法。

共识算法有以下三个特征

可终止性

合法性

共识性

因为共识算法都建立在底层的网络模型基础上，所以从网络同步模型的角度来看，共识算法可以分为三种，即同步共识算法，半同步共识算法，和异步共识算法。

同步共识算法

要求网络中任一消息能够在已知的限定时间内到达所有的共识节点

主要应用在限定规模的网络环境中

半同步共识算法

要求网络中消息某限定时间后到达所有共识节点的概率与时间的关系是已知的

异步共识算法

对于消息在网络中的传播延迟没有任何限制，消息可以在无限长时间后才能发送到其他共识节点

由于FLP不可能定理，异步共识算法无法确定性保证共识终局

半同步共识算法

HotStuff算法

HotStuff算法作为BFT共识算法，在2019年提出不久，就被Facebook在数字货币系统Libra中采用，其优越的地方在于以下几点：

算法复杂度为O(n)；
算法实现复杂度相对更低；
易于理解；

HotStuff是基于view的共识协议，View表示一个共识单元，共识过程是由一个接一个的View组成。在一个View中，存在一个确定Leader来主导共识协议，并经过三阶段投票达成共识，然后切换到下一个View继续进行共识。假如遇到异常状况，某个View超时未能达成共识，也是切换到下一个View继续进行共识。

HotStuff算法的整体思路是使用leader来完成本来每一个节点都需要重复做的事情，更重要的是将整个共识的阶段抽象成了流水线的模型，从而将每一轮广播的证明的功能最大化，从而将工作量再减少2/3，因为每一个QC同时证明了三个cmd的状态。

但是HotStuff算法严重依赖leader，一旦出现了leader出错，这个算法就会停止，所以在HotStuff算法中，每一个leader在广播完一个(QC，cmd)之后就会更换另一个leader。

异步共识

HB-BFT算法

2016年CCS首次提出一个实用的异步拜占庭协议HoneyBadger-BFT（HB-BFT）轰动一时。

HB-BFT通过非常巧妙的设计将通信复杂度降低到了渐近最优的水平O(|B|)，其中|B|是一个block所占用的带宽，前提是|B|的值要非常大。

HB-BFT的核心创新点就是发现了ABC的问题可以分解成RBC（Reliable Broadcast）+ABA（Asynchronous Binary Agreement），并且分别针对这两个组件找到了两个比较优化的实现。

HB-BFT算法具备无主节点、异步交互、支持较大节点规模、拜占庭容错等优势，但实现复杂程度较高。

HB-BFT是第一个实用的异步共识算法，蚂蚁区块链采用了HoneyBadgerBFT共识插件，可以有效地降低网络带宽负载，以及防止选择性共识问题。但在最新的蚂蚁链产品中，将用蚂蚁链最新自研的MyTumble算法替代旧的HoneyBadgerBFT。MyTumble能将共识延迟再降低一个数量级。

算法流程

HB-BFT算法分为三个步骤：

随机选择交易
通过ACS协议实现加密后的交易的共识，获取交易列表
解密加密交易

注：

ACS-Asynchronous Common Subset。ACS协议由两个协议组成：一个是RBC协议，一个是BA协议。ACS协议的主要功能是通过RBC协议广播交易，再通过BA协议形成一致的交易列表。
RBC，Reliable Broadcast协议。RBC协议通过纠删码算法降低节点间的数据传输。两次广播（ECHO以及READY消息），网络节点间可以形成共识。
BA协议，Binary Agreement。

网络模型

HB-BFT系统假定每两个节点之间都有可靠的通信管道连接，消息的最终投递状态完全取决于敌方（Adversary），但是诚实节点之间的消息最终一定会被投递。在整个网络中的总节点数必须大于三分之一的敌方节点，也就是N≥3F+1。

网络中的交易还依赖于一个全局顺序。

一个成功的网络，最后状态应该是这样的：

任何诚实的节点确认了一笔交易TX，那么其他所有的诚实节点也会确认这笔交易。
任何诚实的节点确认了一笔交易TX，其序号是s1，而另一个诚实节点确认了另一笔交易TX，其序号是s2，那么要么s1发生在s2之前，要么之后，也就是说，其时间顺序是确定的。
如果一笔交易被发送到N-F个诚实节点了，那么最终每个诚实节点都会确认这笔交易。这就是可审查特性。

实现

HB-BFT使用了两个方法来提升共识效率：

1. 通过分割交易来缓解单节点带宽瓶颈

在网络中，批量的交易（总数为n），需要打包传输给其他节点，作为共识发起方，一个节点需要把打包的交易发送N-1份给其他节点。

改进的方案是，把总数为n的交易分割成N-1份，也就是说，每份包含n/N-1条交易。如图，把交易分成三个小块，每块发给不同的节点。这样原来一共需要发3*n份交易数据就变成了只需要发送n份即可。

其他节点收到了分块的交易之后，分别再从其他节点收取缺失的交易块，这样，节点A、B、C之间的带宽就被充分利用了，而减少了P作为发起节点的瓶颈，整个系统的性能不会完全受限于P节点。

2.通过在批量交易中选择随机交易块，并配合门限加密来提升交易吞吐量

由于HB-BFT是一种异步共识协议，节点之间收到交易是非同步的，随机的，也就是说，每个节点收到来自客户端的交易可以是不同的，交易到达各个节点的时间顺序也是不定的，具体操作如下：

各节点收到交易信息之后，会把该交易放入它自身的input buffer中，后续收到的交易也依次按顺序放入其input buffer。
HoneyBadger网络中是依靠epochs来作为时间间隔进行交易打包处理的，在一个epoch中，每个节点会从自身的input buffer中选一批交易，并广播给其他所有节点。
最终，每个节点都会有现成一个有相同交易集的交易池，他们是这些节点广播出来的所有交易的并集，也就是Batch A U Batch B U Batch C U...。显然，这个交易池中可能存在重复的、无效的交易，需要删除。

最终确认哪些交易还需要一个叫做Binary Byzantine Agreement的过程，简单来说就是在所有节点之间进行一轮共识，得到一个最终确认的二进制数值，由这个二进制的对应的位来决定哪个交易会被最终确认。

在Binary Byzantine Agreement完成之后，会得到一个确定的Value，根据这个Value来确定交易合集。在剔除无效交易和重复交易之后，每个节点就可以立刻确认剩余的交易集（Asychronous Common Subset）。

需要注意的是，各节点广播的交易都是按照顺序从自己的input buffer中取出的，为了防止这种策略被Adversary节点监控到，从而对诚实节点进行网络干扰阻碍交易的发布和共识，Honey Badger采用了一种Random Selective 的优化方式随机选取一批交易。

每个节点从自己的input buffer中随机选取一批交易，这样的好处有两个，一是可以防止adversary了解策略进行干扰或攻击，二是随机选取一批交易可以很大程度上避免各节点提交的交易出现大量重复。原因是各节点虽然收到的交易顺序不一定一致，但在网络条件差不多的情况下，大部分交易顺序可能是相同的，随机选取而不是按顺序选取可以避免大量的重复。

因为adversary的存在可能干扰Binary Byzantine Agreement的结果。因此，Honey Badger提出了门限加密的方式来避免最终交易集受到攻击。

门限加密的原理

允许任何节点使用一把主公钥来加密一条消息，但是解密则需要网络中所有节点来共同合作，只有当f+1个诚实节点共同合作才能获得解密密钥，从而得到消息原文。在这之前，任何攻击者都无法解密获得消息的原文。

具体过程如下

由一个第三方的可信节点为每个节点生成公/私钥，使用一把主公钥（Master Public Key）加密原交易信息得到一份ciphertext，然后每个节点分别使用其私钥SKi和这份ciphertext得到完整解码密钥的一个部分σ。

当节点拿到f+1份σ时，配合PK就可以解密ciphertext。

小结

HB-BFT是针对异步网络设计的共识算法。HB-BFT算法的核心是RBC广播协议，主要思想是，网络节点可以同时广播交易，通过BA算法形成一致的交易列表。

在网络节点少的情况下（比如，8节点），HB-BFT性能稍逊PBFT算法。
在网络节点变多的情况下，HB-BFT算法的性能几乎不变，而PBFT算法的性能显著下降。

Dumbo算法

由于HB-BFT需要对每个RBC实例进行一次ABA的共识，导致协议的延迟很长。因此Dumbo就针对单个节点需要运行ABA次数太多这个问题，通过两个思路进行优化：

将ABA的实例数从n降到k，其中k是一个Committee size，跟n的大小和安全参数有关。
采用MVBA（Multi-value Validated Byzantine Agreement）代替RBC+ABA，这样可以把ABA的实例数降到常数。

该算法以独到的视角对HB-BFT算法进行分析，揭示性能受限的根源是大量随机化子模块调用导致的运行时间增加，提出了全新的可证明可靠广播（Provable Reliable Broadcast）原语，并给出了基于门限数字签名技术的高效构造方法，通过一种创新性的多值拜占庭共识应用，在容忍1/3的恶意节点的同时，突破了异步共识算法在性能上的设计挑战。

在遍布全球四大洲的100个共识节点测试网络中，Dumbo-BFT算法的确认延迟时间为24秒，不到HB-BFT算法的1/20，交易吞吐量为每秒近1.8万笔、是HB-BFT算法的9倍多。

在Dumbo-BFT算法的基础上进一步提出了Dumbo-MVBA（多值共识算法），在消息数量、通信代价和运行时间等关键性指标上均达到了渐进理论最优，回答了关于“如何提升异步共识算法的关键性能指标”这一问题。

Dumbo-MVBA执行流程

Dumbo-MVBA协议和HB-BFT协议的渐进复杂度对比

POW共识

POW共识算法定义

POW工作量证明（Proof of Work）在比特币之前就已经出现，中本聪在设计区块链的共识机制的时候借鉴了POW工作量证明。常见的是利用HASH运算的复杂度进行CPU运算实现工作量确定。

定义

工作量证明是一种对应服务与资源滥用、或是阻断服务攻击的经济对策。

一般是要求用户进行一些耗时适当的复杂运算，并且答案能被服务方快速验算，以此耗用的时间、设备与能源作为担保成本，以确保服务与资源是被真正的需求所使用。

POW的历史

Adam Back是一位著名的英国计算机科学家和密码学家。他是加密朋克的重要人物之一，在1990年代，主要研究密码学和计算机科学的交叉领域。互联网刚刚兴起，电子邮件作为当时互联网的第一应用，在大众普及。然而，随之而来的便是垃圾邮件的泛滥。为了防止垃圾邮件，不少人开始尝试解决这个问题。

1997年3月，Adam Back在密码朋克邮件列表发送了一封主题为《A partial hash collision based postage scheme》的邮件，提出了Hashcash。

Hashcash使用一种叫做工作量证明的技术来防止垃圾邮件。简单来说，就是发送邮件前需要进行一些计算，这对于发送少量邮件来说，并不会有很大计算量，但如果你想大批量发送邮件，计算量就十分巨大。

Hashcash算法思路

Hashcash为了解决垃圾邮件泛滥的问题，提供的思路也很简单，就是在发邮件前先干点小活，这个活不能太重但至少要占用发送方的一些资源，做对了我才接收你的邮件。

举个简单的例子来说，我们每年春节过年买火车票的时候，登录12306网站的时候会出现很变态的验证，早先的验证让你做一道题目1+1=？，升级后看字识图的验证，这是在消耗我们的眼力。

只不过hashcash消耗的是CPU的算力。Hashcash的设计就是希望基于数学难题，希望你做一些工作，也就是付出CPU的计算代价（算力），得到正确的结果才能获得某些资源。

Hash算法速度相对快速，输入数据相差一点点都会导致散列值的千差万别，Cash代表付出算力之后的资源回报（获得发送垃圾邮件或奖励比特币）。HashCash使用的是SHA-1（160位），前20个字符为0.比特币使用的是SHA-256（256位），前32个字符为0（难度增加后为前72个字符为0）。

Hashcash原理

假设S给R发送邮件，要想发送成功，则：

S的邮件头中需要带一个称之为hashcash stamp的戳记；
对hashcash stamp进行SHA1后的值必须满足接收方R设定的条件：生成的hash值的前20位必须为0；
hashcash stamp可能由多个域组成，比如生成邮件的时间，收件人地址等不变量，还包含可变量counter；
由于Hash的特点，导致发送方S没有办法快速找到满足条件的hashcash stamp，只能通过不断递增counter的值来穷举；
发送方S通过暴力破解的方式计算出满足接收方条件的值，这个过程发送方消耗了一定量的CPU。而验证方只需要对收到的hashcash stamp进行SHA1，检查结果是否满足

由于发送方计算满足邮件接收方条件的值需要消耗一定时间，对于垃圾邮件系统来说，这样的成本基本上是不可接受的，从而有效避免了垃圾邮件。

POW基本过程

以比特币节点求解工作量证明问题的步骤为例：

生成铸币交易，并与其他所有准备打包进区块的交易组成交易列表，通过Merkle树算法生成Merkle根哈希；
把Merkle根哈希及其他相关字段组装成区块头，将区块头的80字节数据作为工作量证明的输入；
不停地变更区块头中的随机数，即nonce的数值，并对每次变更后的区块头做双重SHA-256运算，将结果值与当前网络的目标难度值做对比，如果小于目标值，则解题成功，工作量证明完成。

基于POW共识记账步骤

以比特币系统的记账过程为例：

客户端产生新的交易，向全网进行广播要求对交易进行记账；
每一个记账节点一旦收到这个请求，将收到的交易信息纳入一个区块中；
每个记账节点都通过POW过程，尝试在自己的区块中找到一个具有足够难度的工作量证明；
当某个节点找到了一个工作量证明，它就向全网进行广播；
当且仅当包含在该区块中的所有交易都是有效的且之前未存在过的，其他节点才认同该区块的有效性；
其他节点标识它们接受该区块，而表示接受的方法则是在跟随该区块的末尾，制造新的区块以延长该链条，而将被接受区块的随机哈希值视为先于新区块的随机哈希值。

POW共识算法的优点

去中心化，节点系统开放：理想状态下，它可以吸引很多用户参与其中，特别是越先参与的获得越多，会促使加密货币的初始阶段发展迅速，节点网络迅速扩大。在CPU挖矿的时代，比特币吸引了很多人参与“挖矿”，就是一个很好的证明；
安全稳定、节点自由度高：破坏系统需要投入极大的成本。

在指定时间内，给定一个难度，找到答案的概率唯一地由所有参与者能够迭代哈希的速度决定。与之前的历史无关，与数据无关，只跟算力有关。

掌握51%的算力对系统进行攻击所付出的代价远远大于作为一个系统维护者和诚实参与者所得到的。

POW共识算法的局限

1.会造成资源浪费

算力是计算机硬件（CPU、GPU等）提供的，需要耗费电力，是对能源的直接消耗，与人类追求节能、清洁、环保的理念相悖。

简单来讲，POW算法的工作原理就是网络中的各个节点通过自身的计算能力（算力）来获得创建下一个区块的权利。

设备闲置

POW共识算法带来了硬件设备的大量浪费。随着比特币价值的增长，比特币算力竞赛经历了从CPU到GPU，再到ASIC专用芯片的阶段。算力强大的ASIC芯片矿机将挖矿算法硬件化，而ASIC芯片矿机在淘汰后，没有其他的用途，造成了大量的硬件浪费。

电力消耗

POW饱受诟病的地方是对全球电量大量的消耗。例如，比特币2017年消耗的电量已经超过159个国家的年均耗电量。另外目前总市值排名第二的ETH全网每秒消耗价值17美元的电力，每年消耗的电力的价值在5亿美元左右。

挖矿需要大量哈希运算，哈希运算消耗大量电力

2. POW共识算法算力集中化

发展到今天，算力的提供已经不再是单纯的CPU了，而是逐步发展到GPU、FPGA，乃至ASIC矿机。用户也从个人挖矿发展到大的矿池、矿场，算力集中越来越明显，这与去中心化的方向背道而驰，渐行渐远。

在区块链的POW共识算法中由于算力小的节点挖到矿的概率非常小，所以一般会选择加入矿池，通过合作汇集算力来提高挖矿的成功概率，然后平分收益，这样导致大矿池具有相当高的话语权，可能影响到最终决策（比如判断交易正确性、确认最长链等），如果矿池选择作恶将带来数据篡改的风险；并且由于挖私矿问题的存在，很多矿工加入私矿队伍，并且私矿队伍很容易拥有超过50%的矿力，所以只需要总矿力的25%的矿力就能够篡改数据（因为私矿队伍不公布分支也就不参与验证），这将使得区块链中存储的信息篡改难度减小，整体安全性受到影响。

3. 网络性能很低

比特币出块的时间是10分钟，所以交易确认至少需要10分钟，而且比特币区块链系统目前每秒只能处理约7笔交易，随着用户量的上升，7笔交易不够满足用户的交易需求，它无法承担全球市场的交易量。同时，由于比特币交易是由矿工记账，其中手续费有利可图，手续费越高而越被优先受理，因此手续费较低的交易将会被排到后方，堆积到一起，加剧了网络拥堵，应用的扩展性不好。

出块时间这么久？

比特币平均出块时间为10分钟，是难度系数与全网算力共同作用的一个动态结果，这个时间并不是一个确定的值。

我们假设任何一个新的区块传遍网络需要1分钟，如果30秒产生一个区块的话，问题就大了——假设区块传输的速度平均，那么几乎可以确定，在新产生的区块传输到一半的时候，还没收到这个区块的网络有很大可能性也生成了一个新的区块。

以太坊POW改进

区块链鼻祖比特币，是POW共识，已经稳定运行10年。但在2011年开始，因为比特币有利可图，市场经济下出现了专业矿机专门针对哈希算法、散热、耗能进行优化，这脱离了比特币网络节点运行在成千上万的普通计算机中并公平参与挖矿的初衷。这将造成节点中心化，面临51%攻击风险。

因此，以太坊需要预防和改进POW算法的缺陷。

以太坊共识算法期望达到的目的

抵制ASIC矿机

轻客户端验证

全链数据存储

Ethash是以太坊1.0 POW共识算法，它的前身是Dagger Hashimoto算法。

在以太坊早期起草的共识算法是Dagger Hashimoto，但被证明Dagger很容易受到Sergio Lerner共享内存硬件加速的影响。所以最终抛弃了Dagger Hashimoto，改变研究方向。在对Dagger Hashimoto进行大量修改，终于形成了明显不同于Dagger Hashimoto的新算法：Ethash。

Dagger和Hashimoto其实是两个东西

Hashimoto算法

开发者：Thaddeus Dryja

目的：通过“内存读取”限制来抵制矿机

ASIC矿机可以通过设计专用电路来提升计算速度，但是很难提升“内存读取”速度，因为经历了这么多年的发展，内存访问已经被工业界优化到了极致了。Hashimoto算法直接采用区块链数据，也就是区块中的交易作为输入源。

Dagger算法

开发者：Vitalik Buterin

目的：利用有向无环图DAG同时获得“Memory-Hard Function计算”和“Memory-easy verification验证”两个特性；

理论依据是基于每个特定场合nonce只需要访问大型数据总量树的一小部分，并且针对每个特定场合nonce的子树的再计算是被禁止挖矿的。因此，需要存储树但也支持一个独立场合nonce的验证价值。Dagger算法注定要替代现存的仅内存计算困难的算法。

然而，Dagger算法被Sergio Lerner证明易于遭受共享内存硬件加速的攻击，从而该算法逐渐被废弃。

Ethash算法基本步骤

根据区块信息生成一个种子seed
从种子中，可以计算出16MB的伪随机缓存。轻客户端存储此缓存。
从缓存中，可以生成1GB的DAG数据集，数据集中的每个项依赖于缓存中的少量项。完整客户端和矿工存储此数据集，数据集大小随时间线性增长
矿工会从数据集中随机取出数据计算hash
验证者会根据缓存重新生成数据集所需要的那部分数据，因此只需要存储缓存就可以了。

POS共识

PoS工作机制

以Peer Coin来举例说明PoS的工作机制

Peer Coin是最先采用PoS共识机制的数字货币。在Peer Coin中，引入了币龄和币天的概念。所谓币天，就是你持有货币的时间，币龄=币的数量*天。

比如你有100个币，总共持有30天（Peer Coin中未使用至少30天的币可以参与竞争下一区块），那么你的币龄就是100*30=3000，你作为币的持有者，参与下一轮竞争，过程如下：

加入PoS的均为持币人，并称之为验证者；
在验证者中随机选出一个持币人，给予权利生成新的区块，挑选顺序依据持币的多少；
其余持币人（验证者）对区块进行验证，验证通过则生成新的区块；
如果在一定时间内没有生成新区块，PoS会挑选下一个验证者，给予生成新区块的权利，以此类推。

PoS的优点

PoS不需要比拼算力进行挖矿，节省能耗，相比于PoW，PoS大大地减少了电力消耗；

PoW出块需要大量哈希运算，哈希运算需要消耗大量电力，因此PoW共识算法带来了大量的电力消耗，造成了严重的资源浪费。而PoS共识算法去除了大量的算力竞争，所以，相比于PoW共识算法，PoS大大地减少了电力消耗。

PoS提高了节点数据处理的门槛

PoW之所以有种种问题，主要是因为人人都可以自由地成为节点，而每个节点又通过竞争的方式参与数据处理。一笔数据要经过这么多人的处理，肯定会造成资源浪费和效率低下。

PoS之所以能解决这个问题，是因为PoS提高了节点处理数据的门槛，它规定：虽然每个人都可以自由地加入进来成为节点，但只有满足一定条件的节点，比如抵押一定数量的代币，才有资格成为验证节点，也就是候选人。

对节点性能要求低，在一定程度上，缩短了共识达成的时间；

PoS是PoW的一种升级共识机制，不需要消耗电力来进行运算，根据每个节点记账权的获得难度，令其与节点持有的权益成反比，等比例的降低挖矿难度，从而加快找随机数的速度。

PoS可以更有效地防御51%算力攻击。

在PoS中，节点拥有的币越多，涉及利益越多，节点反而会愿意去维护这个系统的稳定。他们不会进行恶意攻击损害自己的利益。PoS可以更有效地防御51%算力攻击。

PoS中心化风险

“经济学安全”并不能代表区块链网络绝对安全，寡头垄断是任何经济形式都面临的问题。

在PoW网络中，存在算力中心化、矿机制造商垄断的问题，人们一方面担心大型矿池集中了过多的算力，另一方面也担心专门的矿机制造商以技术从源头垄断矿机的生产。由于规模经济的存在，投入大规模资金制造矿机或建立矿场的经营者比小经营者拥有更低的成本，因此在PoW算力竞争模式中更加有竞争力，也更容易形成垄断。

PoS共识机制虽然避免了算力、矿机中心化的问题，却也产生了新的垄断形式。

一些持有大量通证的节点可能自发地组织成为验证者联盟，他们不需要做出任何可能会被没收抵押金的行为，只要他们抵押金超过51%，那么就对链上的治理、社区等拥有绝对话语权。这样的联盟如果有足够的执行力，他们可以拒绝打包任何他们不希望打包的交易。这些潜在的垄断者可能是项目早期的投资人、交易所、甚至是项目方本身。如果类似的攻击行为发生，那么只能依靠“社区共识”强制分叉，因此对于PoS项目来说，通证初始分配方案以及具有一定的流动性和市值规模非常重要。

PoS区块链遇到的最大问题在于初始代币如何分发以及后续如何解决富者越富的问题。

PoS的无利害关系

什么是无利害关系

无利害关系（Nothing At Stake）问题的本质是“作恶无成本，好处无限多”。

具体来讲，是当在POS/Staking共识系统查询分叉（fork）的情况下，出块节点可以在“不受任何损失”的前提下，同时为多条链出块，从而有可能获得“所有收益”。

会出现什么问题？

“聪明”的出块节点会有动力产生新的分叉，支持或发起不合法交易，其他逐利的出块节点会同时在多条链（窗口）上排队出块支持新的分叉。随着时间的推移，分叉越来越多，非法交易，作恶猖狂。区块链将不再是唯一链，所有出块节点没有办法达成共识。

如何解决？

一般的策略都是后置惩罚，即如果被判为恶意出块行为，则会将stake的一部分或保证金作为罚金。然而，所有的惩罚和监管措施都只是事后，而不像POW需要算力出块的隐形约束直接。

POW机制天生避免了这个问题。因为在出块时，矿工会付出机会成本——算力资源。如果分叉出现，矿工需要慎重选择哪条链上出块，一旦选错，付出的算力成本则没有收益。矿工也不会选择在两条链上均分算力，这样只会将原链的出块概率缩小一半，可能得不偿失。

Capper协议

Capper是以太坊选择实行的POS协议，它应用了“执剑人”（Slasher）机制，在共识机制中引入惩罚措施，解决以往POS共识公共地悲剧。

验证者押下一定比例的他们拥有的以太币作为保证金。
然后，他们将开始验证区块。也就是说，当他们发现一个他们认为可以被加到链上的区块的时候，他们将通过押下赌注来验证它。
如果该区块被加到链上，然后验证者们将得到一个跟他们的赌注成比例的奖励。
但是，如果一个验证者采用一种恶意的方式行动、试图做“无利害关系”的事，他们将立即遭到惩罚，收回验证者权利，他们所有的权益都会被砍掉。

对表现出可能的恶意行为的节点进行经济制裁（Slashing），改变了节点在可能出现分叉链时挖矿与不挖两种选择的预期收益，只要节点挖分叉链，或者发动攻击行为能获得的预期收益小于其抵押的保证金，那么理性节点的选择将是遵守规则，做一个诚实的节点，从而化解了无利害关系攻击。

长程攻击

基于链的POS共识在如何确定共识的最终性上更加复杂。

POS抛弃了“以累积工作量最大的链作为主链”的概念，在节点可以自由加入或退出的POS网络中，抵押金的变动是动态的，验证者需要获取最新的其他验证者信息，才能判断哪些区块是真正有效的。不同于POW网络判断区块是否合法仅仅依赖几个客观的信息：交易合法性、区块头哈希是否满足要求，判断主链采用确定的最长链原则，POS还需要考虑“长程攻击”的可能性。

“长程攻击”是POS共识中威胁最大的攻击形式，当一个节点收回了他的抵押金时，虽然它不再拥有验证以后的区块的权利，但是仍然可以对收回抵押之前的区块进行回滚，并且由于它再会受到没收抵押金惩罚，因此攻击者能够通过贿赂这些节点，收集足够的“幽灵”抵押金（这些抵押金已经被收回了），重新构造一条足够长的攻击链，尝试替换这些节点在作为验证者期间曾经验证过的区块。

解决方案

移动检查点

即每隔一定的区块间隔设置检查点，只有检查点之后的区块可能会被重组。检查点的间隔一般少于要求的最短抵押金抵押时间，从而保证有充足可能性的区块都是由还有缴纳了抵押金的节点验证的。

上下文感知交易

在构造一笔交易时，在交易中记录前一个或前几个区块的哈希值，这样就能将一笔交易和特定的区块分支联系起来，在分叉链上伪造交易就变得困难。

DPOS共识机制

来源

DPOS（Delegated Proof of Stake，委托权益证明）是一种区块链的共识算法，2014年由Bitshares的首席开发者Dan Larimer（现为EOS CTO）提出并应用。

定义

假设有这样一家公司：

公司员工总数有1000人，每个人都持有数额不等的公司股票。每隔一段时间，员工可以把手里的票投向自己最认可的10人作为代表来领导公司，其中每个员工的票权和他手里持有的股份数成正比。等所有人投完票以后，得票率最高的10个人作为代表成为公司的领导。如果有领导能力不胜任或做了不利于公司的事，那员工可以撤销对该领导的投票，让他的得票率无法进入前10名，从而退出管理层。

那么这些代表是怎么被选出来的呢？

是每个持币人（员工）根据手中持币数量（股份）投票选出来的，当然这些被选出来的代表是会获得一定的代币奖励的。但如果这些代表不能履行他们的职责（比如当轮到他们时，没能生成区块），他们会被除名，网络会选出新的超级节点来取代他们，毕竟排队等着上的人有很多。

DPOS受托人的职责

在DPOS共识算法中，区块链的正常运转依赖于受托人（Delegates），这些受托人是完全等价的。受托人的职责主要有：

保证金的的正常运行；
收集网络里的交易；
节点验证交易，把交易打包到区块；
节点广播区块，其他节点验证后把区块添加到自己的数据库；
带领并促进区块链项目发展；
受托人的节点服务器相当于比特币网络里的矿机，在完成本职工作的同时可以领取区块奖励和交易的手续费。

知名DPOS项目

Bitshares

最早应用DPOS机制的项目，其DPOS机制里包含见证人（Witnesses）和受托人（Delegates），见证人负责区块的打包，受托人负责系统参数的修改。一般有101个受托人。

EOS

共识算法为DPOS+BFT，有21个受托人。

Asch

共识算法为DPOS+PBFT，有51个受托人。

DPOS的选举机制

以BitShares项目为例

选举机制

一个区块链项目的受托人数由项目发起方决定，BitShares项目一般是101个受托人。任何一个持币用户都可以参与到投票和竞选受托人这两个过程中。用户可以随时投票、撤票，每个用户投票的权重和自己的持币量成正比。投票和撤票可以随时进行，在每一轮（round）选举结束后，得票率最高的101（一般为101，也可以是其他数字，具体由区块链项目方决定）个用户则成为该项目的受托人，负责打包区块、维持系统的运转并获得相应的奖励。

选举目的

选举的根本目的是通过每个人的投票选举出社区里对项目发展和运行最有利的101个用户。这101个用户的服务器节点即可以高效维护系统的运转，而他们也会贡献自己的能力促进区块链项目的发展。通过这种方式，即达到了去中心化的选举共识，又保证了整个系统的运行效率和减少能源浪费。

DPOS算法

DPOS算法要求系统做三件事：

随机指定生产者出场顺序；
不按顺序生产的区块无效；
每过一个周期洗牌一次，打乱原有顺序。

DPOS允许所有矿池每三秒钟轮换一次，并且其他人已被安排在后续进程中，于是，没有人可以在预设位置外生产区块。如果一个生产者这么做了，就可能被投票出局。

这意味着，以EOS项目为例，在正常情况下生产者之间没有争夺，也不会遗漏区块，每三秒会有一个区块。

DPOS算法原理图

DPOS算法过程

注册受托人，并接受投票

用户注册为受托人；
接受投票（得票数排行前10位）；

维持循环，调整受托人

块周期：也称为时段周期（slot），每个块需要10秒，为一个时段（slot）；
受托人周期：或叫循环周期（Round），每101个区块为一个循环周期（Round）。这些块均由101个代表随机生成，每个代表生成1个块。一个完整循环周期大概需要1010秒（101*10），约16分钟；每个周期结束，前101名的代表都要重新调整一次；
奖励周期：根据区块链高度，设置里程碑时间（Milestone），在某个时间点调整区块奖励。

上述循环，块周期最小（10秒），受托人周期其次（16分钟），奖励周期最大（347天）。

循环产生新区块，广播产生新区块和处理分叉等内容

DPOS与其他算法对比

POW（工作量证明）特点：

安全、去中心化
速度低，共识时间长，耗能大

POS（权益证明）特点

共识时间短，耗能小
仍然存在算力挖矿，竞争不充分，存在垄断机会

DPOS（委托权益证明）特点：

出块时间短
效率非常高

DPOS是在POW和POS的基础上发展起来的，其解决POW能耗高，避免POS权益分配下可能的“信任天平”偏颇，但DPOS相对不够去中心化，而是多中心化。

持币人投票选举出块节点
最大化持币人的盈利
最小化维护网络安全的费用
最大化网络的效能
最小化运行网络的成本

DPOS比POW和POS在交易速度等方面有很多优势，这些设计背后逻辑简单即利益最大化，成本最小化。

DPOS共识机制的优点

在共识周期方面，DPOS共识机制大幅缩小参与验证和记帐节点的数量，可以达到秒级的共识验证，系统处理效率得到大幅提高，更有可能取代现代商业应用：DPOS机制将节点数量进一步减少到101个，EOS是只有21个节点，在保证网络安全的前提下，整个网络的能耗进一步降低，网络运行成本最低，更加去中心化。目前，对于比特币而言，个人挖矿已经不现实了，比特币的算力都集中在几个大的矿池手里。每个矿池都是中心化的，就像DPOS的一个委托人，因此DPOS机制的加密货币更加去中心化。
在治理能力方面，在DPOS模式下，治理的结构是清晰的，所有股东都有发言权，这种治理的成本与共识过程是一致的，所以在制定决策的时候，就很清楚，基本不会产生“意外分叉”。
在能耗方面更低。POS机制的加密货币，要求用户开着客户端，事实上用户不会天天开着电脑，因此真正的网络节点是由几个股东保持的，去中心化程度也不能与DPOS机制的加密货币相比。DPOS机制将全节点减少，在保证网络安全的前提下，耗能更低。
更快的确认速度。每个块的时间为10秒，一笔交易（在得到6-10个确认后）大概1分钟，一个完整的101个块的周期大概仅仅需要16分钟，而比特币（POW机制）产生一个区块需要10分钟，一笔交易完成（6个区块确认后）需要1个小时，点点币（POS机制）确认一笔交易也需要1小时。

DPOS共识机制的缺点

投票的积极性比较低。像EOS的投票，拖了好久主网才上线，且绝大多数持股人（90%+）就没有在第一时间去参与投票。这是因为投票需要时间、精力以及技能，而这恰恰是大多数投资者所缺乏的。
对于坏节点的处理存在诸多困难，社区选举不能及时有效的阻止一些破坏节点的出现，给网络造成安全隐患。
DPOS共识机制依然依赖于token（代币），但目前很多商业应用是不需要token参与的。

DPOS算法的应用

Bitshares

Bitshares(比特股）是一个全球去中心化虚拟货币交易所。全世界任何国家比特股用户都可以在比特股钱包进行虚拟货币交易，不同于任何运行在互联网上的其他系统，比特股的服务器是由分散在世界各地的受托人维护的，即使其中一些人被攻击也不会导致整个系统宕机。也不必担心服务器的数量（目前27个）和性能（目前能达到100000tps)问题，因为随着这个平台价值的提升，服务器的数量和性能肯定会随之提升。

Bitshares平台上流通的系统币叫BTS。像BTC一样设定了一个总量：37亿（目前流通25亿左右，37亿是理论值，系统已销毁超过1亿）。也就是说不同于支付宝可以在账号余额上加减，这个平台是最多只能存在总量为37亿的数字（除非持有的货币总量超过半数的人们都同意修改这个总量，这一点和BTC一样），这些BTS可以在这个网络中自由流通。

比特股允许个人和企业在比特股系统内发行自己的资产。所有发行的资产都通过智能合约完成，所有虚拟资产都在BTS比特股账户，所有资产都保存在比特股区块链上，交易速度及规模完全可以容纳目前的美国纳斯达克交易所。

比特股是全球虚拟货币支付系统。比特股自带转账功能，每笔交易3秒确认，每秒可以处理10万次交易，这个速度可以快速处理企业级的应用，类似于支付宝。

比特股是一个去中心化的银行。在比特股系统内可以通过抵押BTS代币来借贷。比如我有100个BTS，按BTS0.3元的价格计算，折合人民币一共30元，如果我要借5元钱，最少需要2倍的BTS作抵押，一共要抵押50个BTS，当市场上涨时，所需要抵押的BTS代币比例会减少，可以随时卖掉从而获取赚取的利润，当市场下跌时，需要及时补仓，如果没有足够的BTS做抵押，系统会在BTS跌到1.5倍时自动平仓，一切由网络自动完成。

比特股是区块链金融的基础设施。致力于把比特股的创新区块用于互联网的每个行业，比如银行，证券交易所，彩票，音乐，拍卖等。

Bit shares的功能

用户首先需要抵押得到的BTS。可使用Bit shares支持的其他加密币抵押（为了保证币值的稳定，抵押率通常都超过200%）按照市价换取BTS，可能会收取一定的费用。
将换得的BTS兑换成BTS内置标准货币。用户在交易前，需将其BTS兑换成等价值的Bit shares中内置的bitUSD/bitCYN/bitGold/...等货币，bitshares保证bitUSD始终等价1美元，bitCNY始终等价于1元人民币，bitGold始终等价于1克黄金等...
使用内置标准货币购买场内交易品种。使用内置的标准货币如bitUSD购买或卖出BTC，ETH等交易品种。

Bitshares的核心价值：

通过抵押BTS代币锚定实际资产比如bitCNY/bitEUR/bitUSD等并能实现1:1兑换，能更好地解决跨境汇款的汇率风险。
能在比特股系统中发行资产。比如企业可以发行自己公司的股票，还可以通过抵押资产借贷，比如借入数字资产bitCNY/bitEUR/bitUSD等。
比特股转账速度快，每笔交易3秒确认，每秒可以处理10万次交易，能实现商业级的应用。用户有了足够的需求在系统内完成更多的场景的交易，加固了锚定，它可以说是一个更好的支付系统，不再是单纯的小额商品的支付系统，而是数字资产的交易管理系统。

EOS

EOS，可以理解为Enterprise Operation System，即为商用分布式应用设计的一款区块链操作系统。EOS是引入的一种新的区块链架构，旨在实现分布式应用的性能扩展。

EOS币

EOS币采用了一种新型区块链架构，通过并行链和DPOS的方式解决了延迟和数据吞吐量的难题。EOS币提供账户，身份验证，数据库，异步通信以及在数以百计的CPU域群上的程序调度。

EOS项目

EOS项目旨在实现一个区块链体系架构，该区块链每秒可以支持数百万个交易，同时普通用户无需支付使用费用。EOS币正好解决了开发人员在使用这些数字货币时遇到的性能不足和可用性等问题，因此有人将其称为区块链3.0。

EOS公链

EOS公链允许人们在其上构建去中心化的应用程序（DApp),并且能够运行这些应用程序，被认为是针对大型企业的以太坊。

EOS的主要特点如下：

去中心化。区块链技术不依赖额外的第三方管理机构或硬件设施，没有中心管制，除了自成一体的区块链本身，通过分布式核算和存储，各个节点实现了信息自我验证，传递和管理。去中心化是区块链最突出最本质特征。
开放性。区块链技术基础是开源的，除了交易各方的私有信息被加密外，区块链的数据对所有人开放，任何人都可以通过公开的接口查询区块链数据和开发相关应用，因此整个系统信息高度透明。
独立性。基于协商一致的规范和协议（类似比特币采用的哈希算法等各种数学算法），整个区块链系统不依赖其他第三方，所有节点能够在系统内自动安全地验证，交换数据，不需要任何人为的干预。

HPOS区块链

混合POS/POW

HPOS混合区块链由POS和POW两种不同的区块组成。这些块是由用户使用不同的共识创建的。

例如热度很高的BTCA，目前也是HPOS极具代表性的数字货币了。

HPOS混合区块链通过在区块链中插入一定数量的POW块，可以提高区块链系统的安全性。

较低比例的POW块将增加事务的处理时间，高比例的POW块将占用太多的计算能力，超过用户的容量。因此，需要平衡POW块混合的频率，并且POS和POW块之间的比率r对于区块链的稳定性至关重要。

NPOS提名权益证明

NPOS机制

NPOS（Nominated Proof-of-Stake,提名权益证明）共识机制是保证网络安全的核心，而NPOS的核心是分散。

验证人分为有效验证人和候选验证人，候选验证人需要获得足够多的提名人的投票才能成为有效验证人，只有有效验证人才能获得收益。另外，提名人可以随时投票给其他候选验证人，所以有效验证人是动态变化的。

波卡是使用了NPOS共识的公链，下面以波卡为例介绍NPOS机制：

波卡的节点数量远多于ETH等链，目前超过200个，提高了抱团作恶的难度。同时，波卡网络会动态调整有效验证人的席位，平行链越多，验证人席位就越多。

提名人为了保证其质押DOT的安全，会花较多时间研究候选验证人的可靠性，会降低验证人作恶的概率。不同于POS，NPOS所有有效验证人节点的奖励分配是相同的，跟质押的DOT数量无关。这就导致提名人会提名质押DOT总数较低的节点，以提高自身的收益。

随着DOT价格的上涨，验证人和提名人的投入也会增加，从而降低作恶的概率。最后要说的是，波卡上的平行链都是基于NPOS共识机制，而通过转接桥的外部链有自己的共识机制，比如ETH。

NPOS与DPOS的区别

BPOS担保权益证明

BPOS过程

BPOS即Bonded Proof of Stake,担保权益证明，其过程如下：

首先，参与者锁定资金，并开始参与多个协商一致的回合-在示意图中为两轮（只是示意，实际上更多）。每个共识回合都有一个报告窗口，其他人可能会报告节点的恶意行为。这意味着在采矿者表示希望退出后，有一段时间他们必须等待，并且不能获得任何奖励。因此，他们的资本是受担保的，只有在这一时期过去后，他们才能退出。

优点

担保权益证明是对常规POS的一种补充，旨在避免“无任何利害关系”的问题。因此，BPOS提高了区块链的安全性。

缺点

BPOS引入了可能导致集中化的因素。

首先，锁定资本的要求将节点集限制为有能力锁定可支配收入的人。

其次，与POS一样，如果用户不能或不想运行自己的节点，一些协议允许用户将本机货币（不要与DPOS混淆）委托给验证者，这样，用户可以获得一些维护奖励，而验证者则收取费用，一般来说，建议将授权分散在多个验证者中，以保持网络的分散化。然而，在采用大幅削减的网络中，用户会三思而后行，考虑他们将资金委托给谁。在实践中，这导致许多POS协议中的股份集中在少数受信任的公司。

BPOS的应用

使用担保协议证明最突出协议是以太坊2.0（ETH2）。

要成为验证者，需要缴纳32ETH的押金（截至2021年6月13日，价值约55000美元），如果一个验证者在两个分叉上生成一个块，那么它被砍掉，而砍掉的数量会增加验证者恶意行为的数量。如果三分之一的验证者在大致相同的时间恶意行事，他们的全部存款将被大幅削减。

LPOS租赁权益证明

LPOS即Leading Proof of Stake,租赁权益证明。

LPOS试图解决POS中的中心性问题。它通过添加租赁选项，使余额较低的节点能够参与块验证。租赁允许余额较高的财富持有人将其资金在特定时间内租赁给余额较低的节点。租赁金额将在租赁合同期间归财富持有者所有，但这将增加解决余额较低节点阻塞的机会。当这些节点解决一个区块时，它们将按比例与财富持有人分享奖励。这种方法使区块链更加分散，从而使其更加安全。

LPOS算法提高了股权证明协议的可扩展性和事务的吞吐量。因为该算法赋予用户将其硬币出租给其他受信任节点的权利。租用给所有受信任节点的金额越大该节点被选择生成下一个块的可能性就越高，如果该节点验证了下一个块，用户将收到该节点收取的部分交易费。

例如waves网络就采用了权益证明租赁（LPOS）共识算法，LPOS可使无技术专业背景的普通用户帮助保护waves网络，在控制waves代币的前提下，将waves租用到完整节点。

类BFT+POS

Tendermint

在2011年，bitcoin Talk论坛对一个叫做权益证明（POS）的概念组织了一场讨论，最初的POS协议例如点点币，实现结果并不理想。第一个真正提出将BTF研究应用到POS公有区块链环境中的是Jae Kwon，他在2014年创建了Tendermint。Tendermint（2014）是实用拜占庭容错（PBFT）算法的第一个POS改编版。

基于BFT的POS协议伪随机的安排一个验证者在多轮投票的过程中提出一个区块，但是，提交和最终化区块取决于大多数-所有验证者中2/3的验证者在提交的区块中签名。在区块最终化之前可能需要进行几轮（译者注：这种多轮投票和现实世界的波尔卡舞蹈类似，这也是polkadot名字的由来）签名。BFT系统只能容错1/3的失败，其中包括故障或恶意的攻击。

Tendermint主要包含两个主要的技术：区块链共识引擎和通用的应用接口。

共识引擎被称为Tendermint的核心模块，确保相同的交易在每个机器中按照相同的顺序被记录下来。

应用接口被称为应用区块链接口（ABCI），让交易可被任何编程语言编写的程序处理。

在核心模块中，Tendermint基于循环投票机制进行工作，这也是共识协议的原理。

一个回合被分成3个处理步骤：

验证者提出一个块，发送提交示意图，签名后提交一个新区块。

这种机制为原子广播提供了一个安全的状态复制机，增加了一个责任层-安全故障可以完全归结于Tendermint。

Tendermint共识算法从验证者集开始，验证者们都维护了一份区块链的全拷贝，并且可以用公钥来识别验证者的身份。

在每个新的块高度他们轮流地提出一个区块。

每轮投票都只有一个验证者可以提出块，并且要用验证者相应的私钥对此进行签名，这样的话如果有错误发生就可以找到为此负责的验证者。

然后剩下的验证者就需要对每个提议都进行投票，投票都需要用自己的私钥进行签名，这些组成一个回合。不过可能因为网络的异步需要好几个回合才能提交一个新块。

验证者提交块的时候由于几种原因可能会失败：

当前的提议可能下线了，或者网络可能遇到了延迟。Tendermint允许验证者可以被跳过（就是轮到一个验证者出块的时候但是此出块者没有出块）。验证者在移到下一轮投票之前等待一小段时间来接收提议者（此轮出块的验证者）提出的整个区块。这种对超时的依赖让Tendermint成为一个弱同步协议，而不是一个异步协议。不过，剩下的协议是异步的，并且验证者只有在接收到了超过2/3的验证者集消息时才会进行处理事务。正是因为这样，所以Tendermint需要大多数的验证者可以100%正常运行，如果1/3或更多的验证者离线或脱机，网络就会停止运行了。

假设少于1/3的验证者是拜占庭，Tendermint保证安全永远不会被破坏-也就是，验证者（2/3以上）永远不会在同一个高度提交冲突的区块，因此，基于Tendermint的区块链永远不会分叉。

目前为止，Tendermint的设计决策确实是把安全性和不可改变性地位放在了灵活性之上，在现实世界上有相当高的可能性是，系统真的会停止运行，参与者将会需要在协议外组织在某种软件上更新后重启系统。

在数字加密货币社区中只有少数人理解Casper以及为什么它拥有价值的时候，Tendermint就为Casper研究奠定了基础。

这个洞察力就是：如果一个链的本身是高度容错的，那么你就可以依赖链来对于谁来生产区块做出一个好的决定，但是如果链的本身就是不可靠的，那么你就陷入了鸡和鸡蛋的问题中去了，这也是之前所以其他共识算法的灭顶之灾。

Algorand

区块链的“不可能三角”（也称为“三元悖论”），是指区块链项目无法同时兼顾去中心化（Decentralization），可扩展性（Scability），安全性（Security）这三项要求，至多只能三者取其二。“不可能三角”一直是制约区块链发展的技术瓶颈。为了解决区块链“不可能三角”的问题，64岁的图灵奖得主，美国麻省理工学院计算机学与人工智能实验室（MIT CSAIL）教授Silvio Micali 提出了Algorand项目。

Algorand是由algorithm（算法）和random（随机）两个词组合而成，从字面意思中可以看出，Algorand是基于随机算法的公有链项目（public chain），Algorand具有能耗低，效率高，民主化，分叉概率低，可拓展性等优点，旨在解决现有区块链项目存在的“不可能三角”问题。

Algorand采用的共识算法是纯粹的股权证明（Pure Proof of Stake,Pure PoS)，在这种共识算法中，每一枚Token都拥有相同的权利，并且不需要作为抵押，新的区块是通过投票产生，每个人都可以参与或授权。

Algorand通过“即时提议与确认（immediate propose and agree）”来形成共识，这是一种“超快速拜占庭协议（Byzantine Agreement，BA）”，拜占庭协议是普遍运用于区块链的通讯协议模式。Algorand的共识机制分成两个步骤，分别是提议和达成共识。

Algorand主要存在以下三个挑战：

避免女巫攻击：敌对者（adversary）制造大量的伪身份来影响BA共识
BA共识需面对数百万的用户，远大于目前拜占庭共识协议的用户数
从拒绝服务攻击（denial- of- service attacks）中恢复并继续工作

Algorand利用以下技术来解决相关的挑战：

将用户划分权重。为了防止女巫攻击，Algorand为每个用户划分权重，一般来说，只要对于三分之二的用户诚实，则BA共识可保证达成共识，用户的权重基于其账户资产。因此只要大于三分之二的资产被诚实的用户所拥有，Algorand可避免分叉和双花。
通过委员会（committee）达到共识。通过选择一个委员会（从所有用户中随机选择的少数代表集）来执行BA共识。基于用户的权重来随机选择委员会，保证大部分委员会成员是诚实的。但会造成针对委员会成员的攻击。
加密抽签。为了防止敌对者攻击委员会成员，BA共识以一种私密且非交互的方式选择委员会。通过计算私钥和区块链公共信息的VRF，系统中的每个用户可独立地验证他是否被选中，如被选中，则生成证实其为委员会成员的字符串，用户可将这个字符串包含在他发送的信息中，因为成员的选举是非交互式的，只有当用户开始参与BA共识，敌对者才会知道哪个用户被选中。
成员的替换。一旦成员在BA共识过程中发送信息，敌对者就可以发动针对此成员的攻击。对于这种攻击，BA共识要求委员会成员只能发声一次。因此，一旦委员会成员发送信息（身份暴露），则此成员对BA共识的达成不再重要。