拜占庭共识机制

区块链学习笔记

 Liu Ke     2017-11-11   7541 words    & views

This document is not completed and will be updated anytime.

Contents

  1. 拜占庭将军问题
    1. 问题描述
    2. 口头协议(OM)
    3. 书面协议(SM)
  2. 实用拜占庭容错协议PBFT
    1. PBFT算法的步骤
    2. 客户端C
    3. 预准备(pre-prepare)
    4. 准备(prepare)
    5. 确认(commit)
    6. 垃圾回收
    7. 视图更换
  3. 并发拜占庭共识协议CBFT

拜占庭将军问题

拜占庭将军问题是一个共识问题: 首先由Leslie Lamport与另外两人在1982年提出,被称为The Byzantine Generals Problem或者Byzantine Failure。核心描述是军中可能有叛徒,却要保证进攻一致,由此引申到计算领域,发展成了一种容错理论,即拜占庭容错(BFT,Byzantine Fault Tolerance)

问题描述

拜占庭帝国想要进攻一个强大的敌人,为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国,但也足以抵御5支常规拜占庭军队的同时袭击。基于一些原因,这10支军队不能集合在一起单点突破,必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算,除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周,依靠通信兵相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是,他们不确定他们中是否有叛徒,叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下,拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商,从而赢取战斗?这就是著名的拜占庭将军问题。

需要明确,拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题,即消息传递的信道绝无问。

Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以,在研究拜占庭将军问题的时候,我们已经假定了信道是没有问题的,并在这个前提下,去做一致性和容错性相关研究。如果需要考虑信道是有问题的,这涉及到了另一个相关问题:两军问题

拜占庭失效指一方向另一方发送消息,另一方没有收到,或者收到了错误的信息的情形。在容错的分布式计算中,拜占庭失效可以是分布式系统中算法执行过程中的任意一个错误。

Lamport提出并论证了口头算法和书面算法两种解决方法。

口头协议

首先,我们明确什么是口头协议。我们将满足以下三个条件的方式称为口头协议:

 (1) 每个被发送的消息都能够被正确的投递

 (2) 信息接收者知道是谁发送的消息

 (3) 能够知道缺少的消息

简而言之,信道绝对可信,且消息来源可知。但要注意的是,口头协议并不会告知消息的上一个来源是谁。

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

这个结论说明了,一个三模冗余的系统只能容故障冻结类型的错误,即一个元件故障以后就卡住不动了(也即已知错误后会出现的结果),那么三模冗余是足够的。

但是对于拜占庭将军问题,由于叛徒可以做出各种各样的判断,就必须四模冗余系统才足够容错。口头协议算法就是把自己的命令告诉其他人,并利用对其他人的命令取多数的方法来得到自己的结论。但要注意的是,别的将军传来的命令是通过算法递归的方法来确定的。利用这个方法,可以保证在叛徒数量少于1/3的情况下,忠诚的将军可以实现一致性和正确性要求,即问题可解。

算法详情:

OM(0)算法

(1)司令将他的命令发送给每个副官。

(2)每个副官采用从司令发来的命令;如果没有收到命令,则默认为撤退命令。

OM(m)算法

(1)司令将他的命令发送给每个副官。

(2)对于每个i,vi是每个副官i从司令收到的命令,如果没有收到命令,则默认为撤退命令。副官i在OM(m-1) 中作为发令者将之发送给另外n-2 个副官。

(3)对于每个i,和每个j ≠ i,vj 是副官i 从第2步中的副官j (使用OM(m-1)算法)发送过来的命令,如果没有收到第2步中副官j 的命令,则默认为撤退命令。最后副官i 使用majority(v1,…,vn-1)得到命令。

其中,majority(v1,…,vn-1)代表了大多数人的命令,若不存在则默认为撤退命令。

需要注意的几个地方是:
  1. 算法始终保证了一个更加安全的默认值,这意味着若信息没有传到是可知的,并且传输时间不在考虑范围内。

  2. 这个算法是一个递归算法,在OM(m)中需要采用OM(m-1)得到相关结果。m代表的是叛徒数量,从m到0,意味着对于每个将军,需要m+1轮的算法才能完成。

  3. 该算法是关于m的,意味着使用该算法必须知道有多少个叛徒。或者说,利用该算法,可以保证叛徒数量在某一个最大值(即总将军数量的1/3)之下时,拜占庭将军问题可解。

  4. 对于任意k<m,在第m-k+1步中OM(k)的vi,都是利用OM(k-1)得来的,即每个将军将会在OM(k-1)中询问其他人,i将军传给他们的是什么,而其他人传递回来的信息则是利用OM(k-2)得到。

书面协议

揭示了口头协议的缺点是消息不能追本溯源,这使得口头协议必须在四模冗余的情况下才能保证正确。由此引入了书买协议。

在口头协议的三个条件之上,再添加一个条件,使之成为书面协议。

 (a)签名不可伪造,一旦被篡改即可发现,而叛徒的签名可被其他叛徒伪造;
 (b)任何人都可以验证签名的可靠性。  

可以论证:对于任意m,最多只有m个背叛者情况下,算法SM(m)能解决拜占庭将军问题。

算法详情

初始化Vi=空集合。

  1. 将军签署命令并发给每个副官;

  2. 对于每个副官i:

    • 如果副官i从发令者收到v:0的消息,且还没有收到其他命令序列,那么他

      • 使Vi为{v};

      • 发送v:0:i给其他所有副官。

    • 如果副官i收到了形如v:0:j1:…:jk的消息且v不在集合Vi中,那么他

      • 添加v到Vi;

      • 如果k<m,那么发送v:0:j1:…:jk:i 给每个不在j1,..,jk 中的副官。

  3. 对于每个副官i,当他不再收到任何消息,则遵守命令choive(Vi)。

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

实用拜占庭容错协议PBFT

实用拜占庭容错协议(PBFT,Practical Byzantine Fault Tolerance)是Miguel Castro (卡斯特罗)和Barbara Liskov(利斯科夫)在1999年提出来的,解决了原始拜占庭容错算法效率不高的问题,将算法复杂度由指数级降低到多项式级,使得拜占庭容错算法在实际系统应用中变得可行。

这是一种基于消息传递的一致性算法,算法经过三个阶段达成一致性,这些阶段可能因为失败而重复进行,交易与投票是串行的,建块过程要经过三次投票。

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算法就是使用类似方法解决良性容错的。

每个副本节点的状态都包含了服务的整体状态,副本节点上的消息日志(message log)包含了该副本节点接受(accepted)的消息,并且使用一个整数表示副本节点的当前视图编号。

PBFT算法的步骤

  1. 取一个副本作为主节点,其他的副本作为备份;

  2. 用户端向主节点发送使用服务操作的请求;

  3. 主节点通过广播将请求发送给其他副本;

  4. 所有副本执行请求并将结果发回用户端;

  5. 用户端需要等待F+1个不同副本节点发回相同的结果,作为整个操作的最终结果。

同所有的状态机副本复制技术一样,PBFT对每个副本节点提出了两个限定条件:

  1. 所有节点必须是确定性的。也就是说,在给定状态和参数相同的情况下,操作执行的结果必须相同;
  2. 所有节点必须从相同的状态开始执行。

这两个限定条件下,即使失效的副本节点存在,PBFT算法对所有非失效副本节点的请求执行总顺序达成一致,从而保证安全性。


1. 当节点发现leader作恶时,通过算法选举其他的replica为leader。

2. leader通过pre-prepare 消息把它选择的 value广播给其他replica节点,其他的replica节点如果接受则发送 prepare,如果失败则不发送。

3. 一旦2f个节点接受prepare消息,则节点发送commit消息。

4. 当2f+1个节点接受commit消息后,代表该value值被确定。

如下图表示了4个节点,0为leader,同时节点3为fault节点,该节点不响应和发出任何消息,C为客户端。最终节点状态达到commited时,表示该轮共识成功达成。

客户端C

客户端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个副本的一致响应必定能够保证结果是正确有效的。

如果客户端没有在有限时间内收到回复,请求将向所有副本节点进行广播。如果请求已经在副本节点处理过了,副本就向客户端重发一遍执行结果。如果请求没有在副本节点处理过,该副本节点将把请求转发给主节点。如果主节点没有将该请求进行广播,那么就有认为主节点失效,如果有足够多的副本节点认为主节点失效,则会触发一次视图变更。

本文假设客户端会等待上一个请求完成才会发起下一个请求,但是只要能够保证请求顺序,可以允许请求是异步的。

预准备(pre-prepare)

在预准备阶段,主节点分配一个序列号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之间。

水线存在的意义在于防止一个失效节点使用一个很大的序号消耗序号空间。

准备(prepare)

如果备份节点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。

确认(commit)

当(m,v,n,i)条件为真的时候,副本i将<COMMIT,v,n,D(m),i>向其他副本节点广播,于是就进入了确认阶段。

每个副本接受确认消息的条件是:

  1. 签名正确;
  2. 消息的视图编号与节点的当前视图编号一致;
  3. 消息的序号n满足水线条件,在h和H之间。一旦确认消息的接受条件满足了,则该副本节点将确认消息写入消息日志中。(补充:需要将针对某个请求的所有接受的消息写入日志,这个日志可以是在内存中的)。

确认阶段保证了以下这个不变式(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)。在完成请求的操作之后,每个副本节点都向客户端发送回复。副本节点会把时间戳比已回复时间戳更小的请求丢弃,以保证请求只会被执行一次。

垃圾回收

为了节省内存,系统需要一种将日志中的无异议消息记录删除的机制。为了保证系统的安全性,副本节点在删除自己的消息日志前,需要确保至少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。

视图更换

视图变更协议在主节点失效的时候仍然保证系统的活性。视图变更可以由超时触发,以防止备份节点无期限地等待请求的执行。备份节点等待一个请求,就是该节点接收到一个有效请求,但是还没有执行它。当备份节点接收到一个请求但是计时器还未运行,那么它就启动计时器;当它不再等待请求的执行就把计时器停止,但是当它等待其他请求执行的时候再次情动计时器。

并发拜占庭共识协议CBFT

并发拜占庭共识协议(CBFT,Concurrent Byzantine Fault Tolerance ),这个算法是蔡维德教授同我的导师郁莲老师等人于2015年提出的,这个算法将交易与投票并行进行。