区块链核心技术：拜占庭共识算法之PBFT

PBFT是Practical Byzantine Fault Tolerance的缩写，意为有用拜占庭容错算法。该算法是Miguel Castro (卡斯特罗)和Barbara Liskov（利斯科夫）在1999年提出来的，处理了原始拜占庭容错算法功率不高的问题，将算法复杂度由指数级下降到多项式级，使得拜占庭容错算法在实际体系应用中变得可行。该论文发表在1999年的操作体系设计与完结国际会议上（OSDI99）。没错，这个Loskov便是提出著名的里氏替换准则（LSP）的人，2008年图灵奖得主。

OSDI99这篇论文描绘了一种副本仿制（replication）算法处理拜占庭容错问题。作者以为拜占庭容错算法将会变得愈加重要，由于歹意进犯和软件错误的发生将会越来越多，而且导致失效的节点发生恣意行为。（拜占庭节点的恣意行为有或许误导其他副本节点发生更大的危害，而不只仅是宕机失掉呼应。）而前期的拜占庭容错算法或许根据同步体系的假定，或许由于功能太低而不能在实际体系中运作。这篇论文中描绘的算法是有用的，由于该算法能够作业在异步环境中，而且经过优化在前期算法的基础上把呼应功能提升了一个数量级以上。作者运用这个算法完结了拜占庭容错的网络文件体系（NFS），功能测验证明了该体系仅比无副本仿制的标准NFS慢了3%。

第一段大片废话便是阐明拜占庭算法越来越重要了，然后说这篇论文提出处理拜占庭容错的状况机副本仿制（state machine replication）算法。这个算法在确保活性和安全性（liveness & safety）的前提下供给了(n-1)/3的容错性。从Lamport教授在1982年提出拜占庭问题开端，现已有一大堆算法去处理拜占庭容错了。可是一句话概括：这些算法都是狗屎！PBFT算法跟这些妖艳贱货彻底不同，在只读操作中只运用1次音讯往复（message round trip），在只写操作中只运用2次音讯往复，而且在正常操作中运用了音讯验证编码（Message Authentication Code,简称MAC），而造成妖艳贱货功能低下的公钥加密（public-key cryptography）只在发生失效的情况下运用。作者不只提出算法，而且运用这个算法完结了一个牛逼的体系（拜占庭容错的NFS），反正功能杠杠的。 作者先夸耀一下这边论文的贡献亮瞎你们的狗眼：

1）初次提出在异步网络环境下运用状况机副本仿制协议

2）运用多种优化使功能明显提升

3）完结了一种拜占庭容错的分布式文件体系

4）为副本仿制的功能损耗供给试验数据支持

体系假定为异步分布式的，经过网络传输的音讯或许丢失、推迟、重复或许乱序。作者假定节点的失效有必要是独立发生的，也便是说代码、操作体系和管理员暗码这些东西在各个节点上是不一样的。（那么假如节点失效不独立发生，PBFT算法就失效了吗？）

作者运用了加密技能来避免欺骗进犯和重播进犯，以及检测被破坏的音讯。音讯包含了公钥签名（其实便是RSA算法）、音讯验证编码（MAC）和无磕碰哈希函数生成的音讯摘要（message digest）。运用m表明音讯，mi表明由节点i签名的音讯，D(m)表明音讯m的摘要。依照惯例，只对音讯的摘要签名，而且附在音讯文本的后边。而且假定一切的节点都知道其他节点的公钥以进行签名验证。

体系允许大魔王能够操纵多个失效节点、推迟通讯、甚至推迟正确节点来毁灭世界。可是作者限制大魔王不能无限期地推迟正确的节点，而且大魔王算力有限不能破解加密算法。例如，大魔王不能假造正确节点的有用签名，不能从摘要数据反向核算出音讯内容，或许找到两个有相同摘要的音讯。

论文算法完结的是一个具有确定性的副本仿制服务，这个服务包含了一个状况（state）和多个操作（operations）。这些操作不只能够进行简单读写，而且能够根据状况和操作参数进行恣意确定性的核算。客户端向副本仿制服务建议恳求来履行操作，而且堵塞以等候回复。副本仿制服务由n个节点组成。

算法在失效节点数量不超越（n-1)/3的情况下一起确保安全性和活性（safety & liveness）。安全性是指副本仿制服务满意线性共同性（linearizability）,就像中心化体系一样原子化履行操作。安全性要求失效副本的数量不超越上限，可是对客户端失效的数量和是否与副本串谋不做限制。体系经过拜访控制来限制失效客户端或许造成的破坏，审核客户端并阻止客户端建议无权履行的操作。一起，服务能够供给操作来改变一个客户端的拜访权限。由于算法确保了权限撤销操作能够被一切客户端观察到，这种办法能够供给强壮的机制从失效的客户端进犯中康复。

算法不依赖同步供给安全性，因而有必要依靠同步供给活性。不然，这个算法就能够被用来在异步体系中完结共同，而这是不或许的（由Fischer1985的论文证明）。本文的算法确保活性，即一切客户端终究都会收到针对他们恳求的回复，只需失效副本的数量不超越（n-1)/3，而且推迟delay(t)不会无限增长。这个delay(t)表明t时刻宣布的音讯到它被目标终究接纳的时刻距离，假定发送者继续重传直到音讯被接纳。这时一个适当弱的同步假定，由于在真实体系中网络失效终究都会被修复。可是这就规避了Fischer1985提出的异步体系无法达到共同的问题。

本文的算法弹性是达到最优的：当存在f个失效节点时有必要确保存在至少3f+1 个副本数量，这样才能确保在异步体系中供给安全性和活性。这么多数量的副本是需求的，由于在同n-f个节点通讯后体系有必要做出正确判别，由于f个副本有或许失效而不发回呼应。可是，有或许f个没有失效的副本不发回呼应（是由于网络推迟吗？），因而f个发回呼应的副本有或许是失效的。尽管如此，体系依旧需求满意数量非失效节点的呼应，而且这些非失效节点的呼应数量有必要超越失效节点的呼应数量，即n-2f>f，因而得到n>3f。

算法不能处理信息保密的问题，失效的副本有或许将信息泄露给进犯者。在一般情况下不或许供给信息保密，由于服务操作需求运用参数和服务状况处理恣意的核算，一切的副本都需求这些信息来有用履行操作。当然，还是有或许在存在歹意副本的情况下经过隐秘分享模式（secret sharing scheme）来完结私密性，由于参数和部分状况对服务操作来说是不可见的。

PBFT是一种状况机副本仿制算法，即服务作为状况机进行建模，状况机在分布式体系的不同节点进行副本仿制。每个状况机的副本都保存了服务的状况，一起也完结了服务的操作。将一切的副本组成的调集运用大写字母R表明，运用0到|R|-1的整数表明每一个副本。为了描绘便利，假定|R|=3f+1，这儿f是有或许失效的副本的最大个数。尽管能够存在多于3f+1个副本，可是额外的副本除了下降功能之外不能提高可靠性。

一切的副本在一个被称为视图（View）的轮换进程（succession of configuration）中运作。在某个视图中，一个副本作为主节点（primary），其他的副本作为备份（backups）。视图是连续编号的整数。主节点由公式p = v mod |R|核算得到，这儿v是视图编号，p是副本编号，|R|是副本调集的个数。当主节点失效的时分就需求发动视图替换（view change）进程。Viewstamped Replication算法和Paxos算法便是运用相似办法处理良性容错的。

PBFT算法的狗血剧情如下：

1.客户端向主节点发送恳求调用服务操作

2.主节点经过播送将恳求发送给其他副本

3.一切副本都履行恳求并将成果发回客户端

4.客户端需求等候f+1个不同副本节点发回相同的成果，作为整个操作的终究成果。

同一切的状况机副本仿制技能一样，PBFT对每个副本节点提出了两个限制条件：（1）一切节点有必要是确定性的。也便是说，在给定状况和参数相同的情况下，操作履行的成果有必要相同；（2）一切节点有必要从相同的状况开端履行。在这两个限制条件下，即使失效的副本节点存在，PBFT算法对一切非失效副本节点的恳求履行总次序达到共同，从而确保安全性。

接下去描绘简化版本的PBFT算法，忽略磁盘空间不足和音讯重传等细节内容。而且，本文假定音讯验证进程是经过数字签名办法完结的，而不是愈加高效的根据音讯验证编码（MAC）的办法。

客户端c向主节点发送<REQUEST,o,t,c>恳求履行状况机操作o，这儿时刻戳t用来确保客户端恳求只会履行一次。客户端c宣布恳求的时刻戳是全序摆放的，后续宣布的恳求比早先宣布的恳求拥有更高的时刻戳。例如，恳求建议时的本地时钟值能够作为时刻戳。

每个由副本节点发给客户端的音讯都包含了当时的视图编号，使得客户端能够跟踪视图编号，从而进一步推算出当时主节点的编号。客户端经过点对点音讯向它自己以为的主节点发送恳求，然后主节点自动将该恳求向一切备份节点进行播送。

副本发给客户端的呼应为<REPLY,v,t,c,i,r>，v是视图编号，t是时刻戳，i是副本的编号，r是恳求履行的成果。

客户端等候f+1个从不同副本得到的相同呼应，相同呼应需求确保签名正确，而且具有相同的时刻戳t和履行成果r。这样客户端才能把r作为正确的履行成果，由于失效的副本节点不超越f个，所以f+1个副本的共同呼应必定能够确保成果是正确有用的。

假如客户端没有在有限时刻内收到回复，恳求将向一切副本节点进行播送。假如恳求现已在副本节点处理过了，副本就向客户端重发一遍履行成果。假如恳求没有在副本节点处理过，该副本节点将把恳求转发给主节点。假如主节点没有将该恳求进行播送，那么就有以为主节点失效，假如有满意多的副本节点以为主节点失效，则会触发一次视图改变。

本文假定客户端会等候上一个恳求完结才会建议下一个恳求，可是只需能够确保恳求次序，能够允许恳求是异步的。

每个副本节点的状况都包含了服务的整体状况，副本节点上的音讯日志(message log)包含了该副本节点承受(accepted)的音讯，而且运用一个整数表明副本节点的当时视图编号。

当主节点p收到客户端的恳求m，主节点将该恳求向一切副本节点进行播送，由此一场轰轰烈烈的三阶段协议（three-phase protocol）拉开了前奏。在这儿，至于什么音讯过多需求缓存的情况咱们就不管了，这不是要点。

咱们要点评论预预备（pre-prepare）、预备(prepare)和承认(commit)这三个历史性阶段。预预备和预备两个阶段用来确保同一个视图中恳求发送的时序性（即使对恳求进行排序的主节点失效了），预备和承认两个阶段用来确保在不同的视图之间的承认恳求是严格排序的。

在预预备阶段，主节点分配一个序列号n给收到的恳求，然后向一切备份节点群发预预备音讯，预预备音讯的格式为<<PRE-PREPARE,v,n,d>,m>，这儿v是视图编号，m是客户端发送的恳求音讯，d是恳求音讯m的摘要。

恳求本身是不包含在预预备的音讯里边的，这样就能使预预备音讯满意小，由于预预备音讯的意图是作为一种证明，确定该恳求是在视图v中被赋予了序号n，从而在视图改变的进程中能够追索。另外一个层面，将“恳求排序协议”和“恳求传输协议”进行解耦，有利于对音讯传输的功率进行深度优化。

只要满意以下条件，各个备份节点才会承受一个预预备音讯：

1、恳求和预预备音讯的签名正确，而且d与m的摘要共同。

2、当时视图编号是v。

3、该备份节点从未在视图v中承受过序号为n可是摘要d不同的音讯m。（许仙在这辈子从未见过名字叫白素贞的美貌女子）

4、预预备音讯的序号n有必要在水线（watermark）上下限h和H之间。

水线存在的意义在于避免一个失效节点运用一个很大的序号耗费序号空间。

假如备份节点i承受了预预备音讯<<PRE-PREPARE,v,n,d>,m>，则进入预备阶段。在预备阶段的一起，该节点向一切副本节点发送预备音讯<PREPARE,v,n,d,i>，而且将预预备音讯和预备音讯写入自己的音讯日志。假如看预预备音讯不顺眼，就什么都不做。

包含主节点在内的一切副本节点在收到预备音讯之后，对音讯的签名是否正确，视图编号是否共同，以及音讯序号是否满意水线限制这三个条件进行验证，假如验证经过则把这个预备音讯写入音讯日志中。

咱们界说预备阶段完结的标志为副本节点i将(m,v,n,i)记入其音讯日志，其间m是恳求内容，预预备音讯m在视图v中的编号n，以及2f个从不同副本节点收到的与预预备音讯共同的预备音讯。每个副本节点验证预预备和预备音讯的共同性主要查看：视图编号v、音讯序号n和摘要d。

预预备阶段和预备阶段确保一切正常节点对同一个视图中的恳求序号达到共同。接下去是对这个结论的形式化证明：假如prepared(m,v,n,i)为真，则prepared(m',v,n,j)必不成立，这就意味着至少f+1个正常节点在视图v的预预备或许预备阶段发送了序号为n的音讯m。

当(m,v,n,i)条件为真的时分，副本i将<COMMIT,v,n,D(m),i>向其他副本节点播送，于是就进入了承认阶段。每个副本承受承认音讯的条件是：1）签名正确；2）音讯的视图编号与节点的当时视图编号共同；3）音讯的序号n满意水线条件，在h和H之间。一旦承认音讯的承受条件满意了，则该副本节点将承认音讯写入音讯日志中。（弥补：需求将针对某个恳求的一切承受的音讯写入日志，这个日志能够是在内存中的）。

咱们界说承认完结committed(m,v,n)为真得条件为：恣意f+1个正常副本节点调集中的一切副本i其prepared(m,v,n,i)为真；本地承认完结committed-local(m,v,n,i)为真的条件为：prepared(m,v,n,i)为真，而且i现已承受了2f+1个承认（包含本身在内）与预预备音讯共同。承认与预预备音讯共同的条件是具有相同的视图编号、音讯序号和音讯摘要。

承认阶段确保了以下这个不变式（invariant）：对某个正常节点i来说，假如committed-local(m,v,n,i)为真则committed(m,v,n)也为真。这个不变式和视图改变协议确保了一切正常节点对本地承认的恳求的序号达到共同，即使这些恳求在每个节点的承认处于不同的视图。更进一步地讲，这个不变式确保了任何正常节点的本地承认终究会承认f+1个更多的正常副本。

每个副本节点i在committed-local(m,v,n,i)为真之后履行m的恳求，而且i的状况反映了一切编号小于n的恳求依次次序履行。这就确保了一切正常节点以相同的次序履行一切恳求，这样就确保了算法的正确性（safety）。在完结恳求的操作之后，每个副本节点都向客户端发送回复。副本节点会把时刻戳比已回复时刻戳更小的恳求丢掉，以确保恳求只会被履行一次。

咱们不依赖于音讯的次序传递，因而某个副本节点或许乱序承认恳求。由于每个副本节点在恳求履行之前现已将预预备、预备和承认这三个音讯记载到了日志中，这样乱序就不成问题了。（为什么？）

下图展示了在没有发生主节点失效的情况下算法的正常履行流程，其间副本0是主节点，副本3是失效节点，而C是客户端。

为了节省内存，体系需求一种将日志中的无异议音讯记载删去的机制。为了确保体系的安全性，副本节点在删去自己的音讯日志前，需求确保至少f+1个正常副本节点履行了音讯对应的恳求，而且能够在视图改变时向其他副本节点证明。另外，假如一些副本节点错过部分音讯，可是这些音讯现已被一切正常副本节点删去了，这就需求经过传输部分或许全部服务状况完结该副本节点的同步。因而，副本节点相同需求证明状况的正确性。

在每一个操作履行后都生成这样的证明是十分耗费资源的。因而，证明进程只要在恳求序号能够被某个常数（比方100）整除的时分才会周期性地进行。咱们将这些恳求履行后得到的状况称作查看点（checkpoint），而且将具有证明的查看点称作稳定查看点（stable checkpoint）。

副本节点保存了服务状况的多个逻辑复制，包含最新的稳定查看点，零个或许多个非稳定的查看点，以及一个当时状况。写时仿制技能能够被用来减少存储额外状况复制的空间开支。

查看点的正确性证明的生成进程如下：当副本节点i生成一个查看点后，向其他副本节点播送查看点音讯<CHECKPOINT,n,d,i>，这儿n是最近一个影响状况的恳求序号，d是状况的摘要。每个副本节点都默默地在各自的日志中收集并记载其他节点发过来的查看点音讯，直到收到来自2f+1个不同副本节点的具有相同序号n和摘要d的查看点音讯。这2f+1 个音讯便是这个查看点的正确性证明。

具有证明的查看点成为稳定查看点，然后副本节点就能够将一切序号小于等于n的预预备、预备和承认音讯从日志中删去。一起也能够将之前的查看点和查看点音讯同时删去。

查看点协议能够用来更新水线（watermark）的凹凸值（h和H），这两个凹凸值限制了能够被承受的音讯。水线的低值h与最近稳定查看点的序列号相同，而水线的高值H=h+k，k需求满意大才能使副本不至于为了等候稳定查看点而中止。加入查看点每100个恳求发生一次，k的取值能够是200。

视图改变协议在主节点失效的时分仍然确保体系的活性。视图改变能够由超时触发，以避免备份节点无期限地等候恳求的履行。备份节点等候一个恳求，便是该节点接纳到一个有用恳求，可是还没有履行它。当备份节点接纳到一个恳求可是计时器还未运转，那么它就发动计时器；当它不再等候恳求的履行就把计时器停止，可是当它等候其他恳求履行的时分再次情动计时器。