DPOS+PBFT共识算法在区块链中的具体实现



  • RAW DPOS CONSENSUS ALGORITHM

    区块链中的共识算法核心就是解决三个问题

    • 谁来产生block
    • 何时产生block
    • 如何验证block的合法性

    DPOS的做法:

    • 由当前的排名靠前的委托人列表和当前的时间偏移共同决定。
    • 按照固定的时间间隔定期产生。
    • 通过block(区块)的时间戳确定合法锻造者,而在PBFT中也说明了通过DIGITAL SIGNATURE的不可篡改性。

    DPOS的问题

    • 使用时间戳对委托人个数取余的方式,确定当前时间片的锻造者,这增大了出错的可能,如果委托人服务器的时间出现漂移(比如可能是网络问题 或者没有正确配置ntp服务),就会造成网络的分叉,具体可以参考这里[https://github.com/LiskHQ/lisk/issues/82]

    • 委托人的权利过高,可能会被滥用,因为DPOS不像POW那样对算力有要求,DPOS的委托人锻造区块不需要算力,他们可以在瞬间锻造出无数区块, 并发往不同的网络节点,导致网络分叉。

      对于第一个问题,DPOS没有很好的应对方案,只能寄希望于委托人拥有良好的服务器运维经验,如果他们稍微粗心,就会出现卡块、分叉的危险。 第二个问题,DPOS主要采取的应对方案是对委托人随机排序和最长链同步的方法。最长链同步是最基本的技术,比较常用的是merkel树。

    PBFT

    加入PBFT后,DPOS算法的前半部分不变,即委托人名单的确定方式和排序算法不变。

    变化的是后半部分,即区块的验证和持久化。 区块的验证,不再采用单一的签名验证,而是全节点投票的方式,每当新区块创造出来时,忠诚的节点并不会立即将其写入区块链,而是等待其他节点的投票。 当这个票数超过一定数量后,才进入执行阶段。详见pbft论文《Practical Byzantine Fault Tolerance 》

    相对与纯粹的DPOS不会出现很复杂的分叉情况:(所以暂时不用使用merkel树)

    • 如果一个正确的节点接受并执行了一个block,那么所有正确的节点都提交相同的block。
    • 分叉的正确的节点(极端情况下就是F个)要么落后于最长链,要么与最长链一致,不会出现高度相同但block hash不同的情况。

    PBFT结合DPOS在区块链中的具体实现流程

    算法流程如下:

    1. 当前时间片的块的锻造者(DPOS投票结果轮流出块)是此次验证的主节点。假定DPOS委托此节点进行出块的请求,并委任他为此轮共识的主节点。
    2. 锻造者(主节点)广播pre-prepare消息。<pre-prepare,m,n,i,d,s>,其中m是新区块,n是此轮出块中的出块块序号,i是该节点在此轮出块节点中该节点的序号,d是m的摘要(d=d(m),把byte求hash的过程),s是对摘要的签名
    3. 其余副本节点第一次收到过这个消息并且验证合法后,就广播一个<prepare,m,n, i,d, s>消息,消息的内容含义和上述一致。
    4. 所有节点(包括主节点和副本节点)收到prepare消息后,节点开始在内存中累加消息数量,当收到超过2f+1不同节点的相同的prepare消息后,节点则认证块中每一个交易,并在消息m中附上对每一个交易的验证结果,便之后会广播一个<commit, m,n, i,d, s>消息。
    5. 每个节点收到超过2f+1个不同节点的commit消息后,就认为该区块已经基本达成一致,进入通过状态,并将块中可以通过的交易打包成块,转换成不可逆转的固定块。
    6. 主节点或者副本节点在收到某一个消息时,启动一个定时器,当定时到期后,如果还没达成一致,就放弃本次共识,丢弃。

    需要说明的是,本算法与PBFT论文中的算法有所不同。一个是取消了commit-local的状态,另一个是没有视图变化的过程。因为PBFT最初提出来主要是面向的一般的C-S架构的服务系统,服务器对与客户端的每一个请求都要有所响应,但是在区块链系统中,区块的生成是可以延迟到下一个时间片的,而且这种延迟很常见,这跟视图变化本质上是一样的,每一个时间片相当于一个视图,slot = time_offset / interval,这个slot就相当于视图编号。

    算法复杂度:

    假设系统中总共有N个节点,包括超级节点(有出块资格,有被选举、委托权)和轻节点(没有被选举权,只能对超级节点进行投票的节点)。系统P2P广播的时间复杂度为N,假如普通节点只接收不广播,那么N可以降为委托人的节点总数n,因为系统中委托人数量一定时期内保持不变,可以认为一次广播的时间开销为常数t。确认一个block需要3轮广播,也就是总时间为3t。 block消息大小设为B,prepare和commit的消息大小设为b,那么总共的带宽消耗为(B+2b)N。(非常初略的计算,看看就行)



Copyright © 2018 bbs.dian.org.cn All rights reserved.

与 Dian 的连接断开,我们正在尝试重连,请耐心等待