张卫、简海波、葛鑫：共识算法&区块链可扩展性方案选讲

12月27日，由中关村大数据产业联盟主办，中国信息协会、数据观、大数据文摘等协办的线上网络分享会——“区块链100分”在当晚准时举办。本期分享会的主题为《共识算法&区块链可扩展性方案选讲》，万向区块链研究组负责人张卫、资深区块链开发工程师简海波、万向区块链核心技术人员葛鑫分别为大家作了分享。

　 以下是张卫、简海波、葛鑫分享的全文内容（略有删减）：

张卫：共识的目标和建模的过程

假设我们处在一个集中的场合，比如一个会议室中，我们需要对某项提案达成一个统一的意见，那么我们现场投票就可以完成了，达成一个投票结果的过程可以是比较简单的。

但是在分布式节点之间，如果想要协商出一个一致的结果，这会是一个非常复杂的过程，为什么呢？

除了因为分布式系统节点故障，通信带来的消息丢失或者延迟等原因，系统复杂性的最大来源是：出错的组件可能会给不同的系统部分，发送自相矛盾的信息。假设我们有a、b、c三个节点，a、c是正常节点；b节点是恶意节点，b发给a，c节点的意见是不同的，那么a、c可能就会做出不同的最终决策。

比如说部署多个雷达，并且部署多个信号处理设备。那么在这多个处理节点收到的多个信息源的模型里，得到一个期望的靠谱结果，就是一个高可靠的系统的正常需要。在这个场景里，就需要一个靠谱的算法，试图得到一个靠谱的结果，这样能应对部分节点故障，或者被恶意控制的时候，依然能得出一个合理的结果。

在学术界，应对这类节点出错的问题被抽象成“拜占庭将军问题”。这个问题是由图灵奖得主Lamport在1982年的同名论文中提出的。故事的设定是：多只拜占庭部队攻击敌方的城池，每只部队由单独的将军统领，将军之间只能通过发送消息来沟通。在观察了敌军后，将军们必须决策出相同的行动方案，但是部分将军可能是叛徒，他们想要阻止忠诚的将军达成一致。在这种情况下，将军们需要一个算法来达到如下目标：

A.忠诚的将军采用相同的行动方案：忠诚的将军必须要根据算法指定的去做，但是叛徒的行为可能是任意的。不管叛徒做什么，算法都需要保证目标A是成立的。忠诚的将军不能只达成共识，共识本身需要是合理的。所以，我们增加了目标B。

B.一小部分叛徒不能让忠诚的将军们接受一个糟糕的计划。在这个模型中的两个目标是易于理解的，但是B目标是很难量化的。这个目标，经过一些演化，可以转换成如下这个模型：ByzantineGeneralsProblem。一个司令官将军需要给n-1个副官将军发送命令，以至：

IC1.所有忠诚的副官采用了相同的行动方案

IC2.如果司令官是忠诚的，那么忠诚的将军都要遵从他发送的行动方案

条件IC1和IC2被称为“交互一致性”（interactiveconsistency）条件，为了解决我们提出的原始问题，我们定义了拜占庭将军问题，如果此问题能解决，那么原始问题也能解决。

如上的这个模型是1982年的同名论文中提出的，论文同时提出了两个解决方案。分别被命名成口头协议和书面协议。但是这两个协议因为消息复杂度太高，基本没有在商用环境中落地。直到1999年，PBFT论文中提出了消息复杂度为n平方，只依赖于弱同步假设的方案，BFT类算法才走向商用。

简海波：PBFT的原理和特点

PBFT算法是第一个基于状态机副本复制（state-machinereplication）的拜占庭容错算法，由MIT的两位科学家MiguelCastro和BarbaraLiskov于1999年提出，发表在操作系统设计与实现国际会议上（OSDI99）。

PBFT的全称是PracticalByzantineFaultTolerance，这个算法翻译成中文的话，就是【实用拜占庭容错】，顾名思义，该算法是可以能够容拜占庭错误的，并且是实用的。事实上，PBFT的算法正常流程的消息复杂度相对以往的一些BFT（拜占庭容错）算法已经大为降低，是节点数规模的平方复杂度。

PBFT能够容拜占庭错误，也就是可以解决经典的拜占庭将军问题。

前面介绍过，该问题的正式提出是在较早的1982年，由LeslieLamport等3人在论文《TheByzantineGeneralsProblem》中提出。也是在这篇论文中，Lamport他们提出了口头协议和书面协议两种解决拜占庭将军问题的算法。在这之后的十几年的时间里，人们又陆续提出了不少算法，尝试解决拜占庭将军问题。

不过，在PBFT之前，以上这些算法或多或少都存在着一些不足。比如有的算法虽然理论上是可行的，是比较低效，从而并不实用；而其他一些算法，却依赖于同步假设：要么是对消息延迟的时间或者处理速度进行假定，要么是算法的正确性依赖于同步假设，而这都会导致算法不够实用或者容易受到攻击。

而PBFT则尝试克服已有的算法的这些不足之处：

首先，算法的独特设计，结合通信和消息认证的优化，使得该算法较为【高效和实用】；

其次，算法本身【不依赖于同步假设来提供安全性（safety）】，也就是说算法运行过程中，各节点在收集投票时，并不需要假定在一个已知的时间间隔里就收集到合法的票数。

接下来我们来具体看下PBFT算法的基本概念和原理。

在PBFT中，每个参与运行的节点被建模为一个状态机，并且如果状态机的初始状态相同，而它们的输入又相同的话，则经过转换后的结束状态也是一致的（这里的输入导致的状态转换需要是确定性的）。

PBFT算法就是要保证每个节点，也就是每个状态机的输入是一致的，也就是所有节点会看到来自客户端的请求的执行顺序是完全一致的。

PBFT算法的容错率是1/3，也就是说系统中的恶意节点的比率如果小于1/3，则算法能够保证系统能够达成共识，也就是所有的诚实节点能够达成一致，它们将按照完全一样的顺序来执行客户端发过来的请求。运行PBFT算法的所有节点组成的系统会不断接收到客户的请求，它们不断地进行投票，完成共识。

整个过程可以比喻为：所有的参与节点在一个虚拟的会议室中通过召开会议的形式，对客户请求进行共识。一旦完成共识后，所有（诚实）节点将会按照相同的顺序执行客户端请求，这就保证了大家的最终状态的一致性。

之后，各节点将执行后的结果分别发送给客户端，而客户端则只需要收集到指定个数的相同的回复结果后，就可以将该结果当作是正确的请求结果（这里的指定个数，就是系统中可能存在的最大的恶意节点的个数再加上1之后的个数）。

接下来，我们再仔细地了解一下上述共识的投票过程。

主节点作为主持人收到请求后形成提案并发送给其余参会者，也就是各副本节点的过程叫做Preprepare（预准备）阶段。发送的消息，相应地叫做【预准备】（preprepare）消息。该消息中，指定了客户请求被分配好的执行序号，以及其他一些信息，例如，当前所在的会议室的编号（算法中称为视图编号，会议室就相当于视图）

每个参会者（副本节点）收到提案（预准备消息）后，将会判断提案的有效性，例如消息是否确实由当前的主持人所发送，是不是在当前的会议室（同一视图），请求编号数值本身是否合理（没有超出合理范围）等等。

如果没有问题，节点将会接受提案，并进行第一次投票，这个投票被称为是【准备消息（prepare）】，并且发送给其余所有参与者（包括主节点和其他所有副本节点），并且该节点正式进入准备阶段。同时，发送完准备消息的副本节点将会等待并收集来自其他副本节点的投票（准备消息）。

副本节点什么时候结束准备阶段呢？也就是说，副本节点等待收集其他节点的准备消息要等到什么时候结束呢？

这里有一个临界值，就是说，副本节点会在收集到来自超过2/3的节点的准备消息（当然也包括主持人的预准备消息）后，就可以结束投票收集状态，结束准备阶段，而进入下一阶段。上面说的超过2/3的投票数是一个合理选择的比例，它也是接下来将介绍的下一投票阶段所应收集的票数的比例

在本阶段也就是准备阶段中，这个比例的准备消息收集票数，能够保证所有诚实的参与者节点将会就这件事情达成一致：【大家看到的提案中，正在共识的客户请求被分配了相同的执行序号】。

这就能保证：共识完成后，所有诚实节点能按相同的顺序执行请求。上述超过2/3的比例，正是考虑到了恶意节点的占比的情况（小于1/3），才能达到让诚实节点达成一致的结果。

接下来，我们要说明的是，仅有上面一个阶段，即准备阶段的投票是不够的。我们还需要保证两点：

（1）有足够多的诚实节点都完成了准备阶段；

（2）当系统中因为主节点宕机或者是恶意节点而需要发生会议室变更（称为视图变更）时，需要保证在旧的会议室（也就是旧的视图）中已经在部分节点上执行过的请求的编号仍然能够在新的会议室（也就是新视图）中加以保持，这样就能保证所有新旧请求的执行顺序能够得以保证，而不会乱序，造成节点之间状态的不一致。

因此，PBFT中还有一个投票阶段，叫确认阶段（commit）。在节点收到超过2/3的准备消息后，就结束准备阶段而进入确认阶段，这伴随着节点向其他节点发送确认消息（commit）。同时，节点将等待并收集来自其他节点的投票信息，也就是确认消息，直到收集到超过2/3的投票数，这时节点就算结束了本投票阶段，也就是确认阶段，同时，节点相当于进入到了被称之为本地确认（commit-local）的状态。

此时，节点就可以确信，系统中的（诚实）节点已经达成共识，可以放心地执行客户请求（前提是更早的请求都已经执行完成）。

以上我们就大致了解了PBFT算法的正常执行流程，从中我们可以看到整个正常流程分为三个阶段：预准备、准备和确认阶段，因此也称为是三阶段协议。其中预准备阶段是主节点的准备提案的阶段，而后两个阶段则是投票阶段

前面提过，当主节点发生宕机或是恶意节点时，系统需要发生会议室变更，也就是视图变更，从而确保整个共识过程能够继续进行。PBFT中视图变更的发起，由各个节点先发送申请视图变更的消息，由新会议室的主持人，也就是新视图的主节点收集超过2/3的申请视图变更的消息时，新的主节点将组装【new-view】（新视图）消息，其中就包含整个视图变更中需要保留的、来自旧视图的、之前已经收集到超过2/3的准备和预准备消息的所有客户请求对应的新的预准备消息。

这些工作都是由新的主节点完成，它会对这些请求进行编号，也就是保留旧视图中已经编好的序号。这样，视图变更协议就能保证新旧视图中请求的执行序号不会乱序，从而保证算法的正确性。不过，PBFT中视图变更的消息复杂度是比较高的，是节点数的3次方的量级。目前已有不少BFT类算法对此进行了改进，将其消息复杂度进行降低。

最后，我们简单说一下PBFT的应用。从PBFT算法的特点来看，首先系统中不能有太多节点，否则共识的消息数量会过多；其次需要保证恶意节点的比例不能超过1/3，否则算法无法保证正确性（safety），因此PBFT较为适用于联盟链。在联盟链中，每个新加入的节点都是需要进行验证和审核的。HyperledgerFabric0.6版本使用的就是PBFT算法。

接下来，简要介绍一下Tendermint共识算法。

和PBFT一样，Tendermint也是基于状态机副本复制技术，适用于区块链的账本存储，结合了区块链的技术特性而进行的设计。

Tendermint共识算法有一个显著特征：通过将共识引擎与应用逻辑解耦，能够用于构建各种分布式应用，它容易理解和使用，并且是高效的算法。Cosmos、Ethermint和HyperledgerBurrow等项目都是基于Tendermint共识算法而构建的。

也就是说，在这个前提下，系统能够保证所有正常节点拥有相同的交易列表，并按相同的顺序执行交易，最终得到相同的状态。

系统中，节点分为两种类型：validator和非validator节点。validator节点参与共识，也就是对区块（包含一批交易）进行共识，包括propose区块，对提议的区块进行投票。而非validator节点不参与共识，但会帮助传播区块和投票消息，以及相互同步状态等

无论是validator节点，还是非validator节点，都包含与共识过程相关的一些状态，如区块链当前高度height，round，以及step等。节点之间运行gossip协议，相互同步共识状态和区块链状态信息，Tendermint共识过程基于round进行。基于区块链的当前高度，每个新区块的共识需要一个或多个round。

一个round包括3个阶段（step）：Propose，Prevote和Precommit：整个Tendermint共识过程就是由一个或多个round，再加上Commit和NewHeight两个特殊的阶段组成。完成了两阶段投票（Prevote和Precommit）后，Commit和NewHeight阶段就负责将共识后的区块上链，并开始下一个round进行共识，一个round对应于一个特定的区块提议者（proposer）。

前面说到过，一个round包括3个阶段（step）：Propose，Prevote和Precommit，其中Propose阶段就是区块提议阶段，区块提议者提议区块后，发给其他共识节点进行投票共识。

和PBFT一样，Tendermint的投票阶段也是两个：Prevote和Precommit，并且两个阶段也都是分别收集超过2/3的投票数，才会进入下一个阶段。另外，Tendermint在Prevote阶段，当节点收集到超过2/3的Prevote投票时，会对区块进行锁定，这有点类似于PBFT中的prepared状态，结合了区块链自身的技术特性，这使得它成为Tendermint的一个特性。

与PBFT不同的是，Tendermint对视图变更过程（也就是round变更）进行了优化。其流程合并到了正常的投票流程，即【复用】了投票信息，用于判断系统是否要进行视图变更。从而使得Tendermint的视图变更的消息复杂度从PBFT的节点数的3次方，降低为节点数的平方的量级。

当然，Tendermint的正常流程的消息复杂度也是平方量级。和PBFT一样，Tendermint的最终确认性（Finality）也是instantfinality（即时确认性）。

葛鑫：Libra中的共识算法LibraBFT以及HotStuff

今年Facebook公布了Libra区块链的计划，Libra中的共识算法是LibraBFT，该算法是基于HotStuff共识算法改进而来的。

HotStuff共识算法总结了PBFT、Tendermint等共识算法的特点，实现了一个既有安全性（safety）、活性（liveness），又有响应性（responsiveness）的共识算法。为了更好的理解HotStuff的创新点，我们先简要回顾一下PBFT和Tendermint的短板。

PBFT是最早的可以实用的拜占庭容错共识算法，该算法最大的短板是ViewChange时的消息复杂性，每当需要在共识节点中切换Leader时，都需要大量的消息O（n^2），这是很复杂的。

Tendermint是2017年提出的共识算法，该算法采用了锁定、解锁机制，简化了Leader切换过程。但是该算法却损失了响应性，在该算法中即使某个节点集齐了各个共识节点的投票消息，依然需要等待一段时间，以保证大多数节点都能集齐消息。这会带来什么影响呢？在网络情况很好的时候，依然需要等待固定时间，才能出块。比如说，在目前的Cosmos主网中，出块间隔相当稳定，大约是6秒左右。

如何才能让区块的确认只与网络的实际延迟有关呢，也就是说网络状况好的时候，区块更快确认；网络状态差的时候，可以多花点时间确认。这样的特性就是所谓的响应性（Responsiveness）。

HotStuff给出了这样一个算法，Leader切换只需要线性复杂度，同时保证了响应性。那么它是怎么做到的呢？

首先，HotStuff引入了门限签名，每一轮的共识投票消息，都是各个共识节点发送给Leader节点，由Leader将这些消息签名组合成一个，再广播给大家。这样极大的较少了系统中消息量，从O（n^2）减到了O（n）。

然后，相比于PBFT和Tendermint的两轮投票，HotStuff采用了三轮投票，多了一轮投票，各个节点集齐投票就可以进入下一个共识，而不需要等待固定的时间。

除了响应性，HotStuff还采用了链式确认，我们认可一个区块，实际上也是对于该区块父区块的认可。在链式的HotStuff中，可以将区块的确认放在下一个区块中，只要一个区块后面产生了三个连续区块，那么就说明该区块经过了三轮投票确认，就可以最终敲定了。

还有一个比较大的创新是，HotStuff提出了安全性和活性的解耦，安全性和活性可以分开独立的设计。共识算法的安全性经过严格的数学证明，同时其活性可以更加灵活，可以定制。比如说，一个系统想要采用HotStuff，安全性的部分不用担心，对于活性的部分，比如Leader怎么切换、超时时间如何定义等等可以灵活的留给使用者定义。

HotStuff的特点包括：

1.消息复杂度是线性的，O（n），Leader切换时也是线性的

2.具备响应性（Responsiveness）

3.链式的确认规则，出块更快

4.安全性规则和活性规则解耦，更加灵活

了解了HotStuff，再说说LibraBFT具体做了哪些改动优化呢？

在LibraBFT中，并没有采用门限签名，而是由Leader收集齐签名后（超过2/3），打个包广播给各个共识节点。那么显然，LibraBFT中消息复杂度是高于HotStuff的，既然消息更复杂了，为什么还这么设计呢？

我个人的理解是，这样不会丢失原始信息，每个节点都知道哪些节点投票了，方便进行监督、激励。LibraBFT还有一个改动，就是对于投票规则的简化，在LibraBFT中收到投票时的验证规则在一定程度上简化了，便于实现；其次，LibraBFT给出了详细的Pacemaker设计，也就是针对负责活性的模块进行了定制话设计。

以上就是本次对于HotStuff和LibraBFT的简要总结，下面简单的聊一下区块链扩展性的方案分片和多链架构

区块链的分片简单来说就是将区块链网络分割成不同的在分片，各个分片并行的进行交易的验证、执行以及保存数据。

目前多数区块链的设计机制是这样的，每个全节点都需要验证、处理所有的交易，并保存全量的数据。这样就带来了区块链扩展性的问题，当我们交易越来越多，整个区块链网络的处理性能实际上还是跟单个节点的处理性能一样的。

有了分片设计，可以提高了交易处理的并行性，每个节点值存储部分分片的数据，这样可以极大的提高区块链网络处理交易的性能。

分片可以分为网络分片、交易分片、状态分片。

网络分片：指的是将网络中的节点分成不同分片，这是实现交易分片、状态分片的基础。

交易分片：顾名思义就是将交易分片，把不同的交易按照特定的规则发送到特定的分片去验证处理。

状态分片：指的是节点只存储特定分片的数据，而非全量数据。

如果只实现网络分片和交易分片，节点依然保存全量数据，这样可以提高交易处理的性能，实现的技术难度也低一些，但是节点的数据会特别多；如果同时实现网络分片、交易分片和状态分片，既可以提高交易处理的性能，有可以减少节点所存储的数据。

但是这种方案的技术难度较大，实施周期比较长。其难点主要集中如下几个方面：首先是，单片安全性问题，就是说分片后单个分片验证者数量减少，安全性可能减低，应该如何应对单片攻击的？

目前比较普遍的思路是，随机地分配验证者到各个分片。攻击者攻击单个分片验证者成功的概率在统计学意义上接近攻击全网节点；还有就是，如果验证者随机分配的一个分片，而该验证者恰好缺少该分片的数据怎么验证交易？

如果从其他节点请求该分片数据，显然是有性能消耗的。频繁的更换验证者必然都这性能降低再有一个是跨片交易的问题，一个跨片交易应该如何设计，怎样保证跨片交易的原子性？

针对这个问题，目前采用比较多的是异步的跨片通讯方案，就是说让交易现在一个分片上锁定并将锁定证据传输到另一个分片，然后在另一个分片验证证据并执行交易，执行完再将证据传回前一个分片。

以上是分片的介绍，那么什么是多链架构呢？

多链架构指的是区块链系统由各种链构成，不同的区块链上运行者不同类别的应用，链与链之间可以进行资产转移、跨链调用等。多链与分片有一些类似，比如多链中的一个应用链类似于一个分片。

因此多链也存在着与分片类似的难点：

1.单条链的安全性如何保证

2.跨链交易如何设计，如何验证其他链的交易、如何保证交易的原子性

对于单链的安全性来说，有的区块链项目采用了由一条链的验证者自己验证交易以确保安全性，这样的方案中单链的安全性取决于该链的验证者。

而有的方案采用了全局共享安全的方式确保单链足够安全，具体方式是将系统的验证者随机的分配到单个链上去确认区块，这样可以实现在单链安全性在统计学意义上接近整个系统。

跨链交易原子性是多链架构中另一个需要关注的问题，与分片的跨片机制类似，跨链的方案也主要采用异步的方式实现。多链和分片的方案，技术难度高一些，所以目前从方案到具体实现，都还在进展之中，后续应该会不断演进。

责任编辑：张薇