1 介绍

BFT(Byzantine Fault Tolerance)是分布式系统对错误容忍程度的一种考量的模型，如果一个分布式系统能够容忍任意错误的发生 （这些错误可能包括硬件错误、网络拥塞和延迟、黑客攻击、节点叛变），我们就说这个系统达到了拜占庭容错。 虽然早在上世纪80年代，lamport就已经在论文中证明了拜占庭容错的可行性，但一直没有一个实用的、高效率的算法实现，直到castro和liskov发表了PBFT， 其中P表示的是Pratical。

DPOS(Delegated Proof Of Stake)是一种基于委托人的权益证明的共识机制，主要用来实现分布式账本的一致性。虽然实际应用了DPOS的系统，比如bitshares，crypti 都还没遇到过重大安全问题，但经过我们的测试和分析，它存在理论上的漏洞，如果被黑客利用就很容易对系统造成分叉，引发双重支付的风险。 也就是说这种系统没有达到拜占庭容错。

本项目主要做了两件事

1. 分析DPOS算法的漏洞，并模拟最简单的黑客攻击，导致网络分叉
2. 引入PBFT算法，对DPOS的安全性方面进行增强，使之容忍拜占庭错误

为了简化模型，代码中并没有实现区块链持久化、签名认证、区块同步等功能，只实现了一个基本的网络模型，因此只能用于演示和教学，暂时不能用于真实项目中。

2 DPOS分析

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

1. 谁来产生block
2. 何时产生block
3. 如何验证block的合法性

DPOS是这样回答的

1. 由当前的排名靠前的委托人列表和当前的时间偏移共同决定
2. 按照固定的时间间隔定期产生
3. 因为可以通过block的时间戳确定合法锻造者，所以可以通过block附带的签名和委托人的公钥验证其合法性，区块中交易的验证以及与上一块的衔接这里就略去不说了。

用伪代码表示如下

for round i
    dlist_i = get N delegates sort by votes
    dlist_i = shuffle(dlist_i)
    loop
        slot = global_time_offset / block_interval
        pos = slot % N
        if delegates[pos] exists in this node
            generateBlock(keypair of delegates[pos])
        else
            skip

DPOS算法的缺点主要有两个。

其一是使用时间戳对委托人个数取余的方式，确定当前时间片的锻造者，这增大了出错的可能，如果委托人服务器的时间出现漂移（比如可能是网络问题 或者没有正确配置ntp服务），就会造成网络的分叉，具体可以参考这里[LiskHQ/lisk-sdk#82]

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

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

以crypti为例，crypti中委托人有101个，锻造速率是10s一块，每一轮竞选周期大概16.8分钟。每个期间内排序算法的种子是不变的。具体可参考如下代码

function shuffle(height) {
  var truncDelegateList = [];
  for (var i = 0; i < 101; i++) {
    truncDelegateList.push(i);
  }
  var seedSource = String(Math.floor(height / 101) + (height % 101 > 0 ? 1 : 0));
  console.log(seedSource);
  var currentSeed = crypto.createHash('sha256').update(seedSource, 'utf8').digest();
  for (var i = 0, delCount = truncDelegateList.length; i < delCount; i++) {
    for (var x = 0; x < 4 && i < delCount; i++, x++) {
      var newIndex = currentSeed[x] % delCount;
      var b = truncDelegateList[newIndex];
      truncDelegateList[newIndex] = truncDelegateList[i];
      truncDelegateList[i] = b;
    }
    currentSeed = crypto.createHash('sha256').update(currentSeed).digest();
  }
  return truncDelegateList;
}

也就是说在这16.8分钟内，101个委托人锻造区块的顺序是确定的，这就给了黑客很大的操作空间。

举个例子，排序后的委托人列表如下

1,6,9,10,50,70,31,22,13,25

黑客实际控制的节点为

1,10,70,31,13,25

黑客在1号节点造成网络分叉后，由于中间隔着几个忠诚的节点，分叉很快被最长链同步机制消除，但是如果黑客此时对这些间隔内的忠诚节点发起 DDOS攻击，那么他就可以使他们入侵的本来不连续的恶意节点连续地产生区块了，也就是说分叉将持续到6个区块后，这时两个分叉网络中的所有交易都将被 确认6次以上，这些交易中可能会包括相互冲突的交易。也就是说黑客只需要控制6个节点，配合DDOS就可以100%造成双重支付。

3 PBFT

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

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

本算法假定错误节点数不超过f个，总结点数n>=3f+1，那么系统可以通过满足以下两个条件来保证区块链的一致性

1. 如果一个正确的节点接受并执行了一个block，那么所有正确的节点都提交相同的block
2. 所有正确的节点要么落后于最长链，要么与最长链一致，不会出现高度相同但block hash不同的情况

算法流程如下：

1. 当前时间片的锻造者将收集到的交易打包成block并进行广播（这一步与之前的算法一致）
2. 收到block的委托人节点如果还没有收到过这个block并且验证合法后，就广播一个prepare<h, d, s>消息，其中h为block的高度，d是block的摘要，s是本节点签名
3. 收到prepare消息后，节点开始在内存中累加消息数量，当收到超过f+1不同节点的prepare消息后，节点进入prepared状态，之后会广播一个commit<h, d, s>消息
4. 每个节点收到超过2f+1个不同节点的commit消息后，就认为该区块已经达成一致，进入committed状态，并将其持久化到区块链数据库中
5. 系统在在收到第一个高度为h的block时，启动一个定时器，当定时到期后，如果还没达成一致，就放弃本次共识。

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

由于取消了视图变化，达成一次共识的性能也大幅度提升。假设系统中总共有N个节点，包括委托人节点和普通节点。系统的消息传播使用的gossip算法，一次广播需要传递的消息上限是N^2，对应的时间开销为O(logN)。假如普通节点只接收不转发，那么N可以降为委托人的节点总数n，因为系统中委托人数量一定时期内保持不变，可以认为一次广播的时间开销为常数t。确认一个block需要3轮广播，也就是总时间为3t。 block消息大小设为B，prepare和commit的消息大小设为b，那么总共的带宽消耗为(B+2b)N^2。

算法的正确性就不在这里证明了，大家可以参考lamport和liskov的原始论文，本项目并没有创新任何算法，只是对经典PBFT算法的一个实现，并稍作修改后与DPOS结合起来。Demo的运行结果可以看出其效果，这也算是一种证明。

4 demo说明

安装

npm install

运行

// 帮助
node main.js -h

// 使用pbft, 默认不使用
node main.js -p

// 模拟错误节点，-b后跟节点id列表，逗号分隔
node main.js -b 1,2,3

// 组合使用pbft，和错误节点
node main.js -b 1,2,3 -p

5 演示

首先我们使用默认的dpos算法，模拟一个分叉攻击

node main.js -b 10

等到第10个节点锻造区块时，它会制造两个fork，并发往不同的节点，可以看出在高度为4的时候，就开始分叉了

fork on node: 10, height: 4, fork1: 58b1c8d429f7ed6d47bf6e7bead2139af420be453259ea0da42091ced3b28ed8, fork2: 61084a05844c436a36dc1f14ad151bda19ab3774aa15d8b1006cbe1dfb01b943
send fork1 to 2
send fork2 to 5
send fork1 to 6
send fork2 to 8
send fork1 to 9
node 0 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:58b1c8:10) -> 
node 1 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:61084a:10) -> 
node 2 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:58b1c8:10) -> 
node 3 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:61084a:10) -> 
node 4 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:61084a:10) -> 
node 5 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:61084a:10) -> 
node 6 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:58b1c8:10) -> 
node 7 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:61084a:10) -> 
node 8 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:61084a:10) -> 
node 9 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:58b1c8:10) -> 
node 10 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:58b1c8:10) -> 
node 11 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:58b1c8:10) -> 
node 12 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:61084a:10) -> 
node 13 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:61084a:10) -> 
node 14 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:58b1c8:10) -> 
node 15 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:61084a:10) -> 
node 16 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:58b1c8:10) -> 
node 17 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:61084a:10) -> 
node 18 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:61084a:10) -> 
node 19 (0:713304:0) -> (1:f76cf6:7) -> (2:f1d1bc:8) -> (3:cccd58:9) -> (4:61084a:10) -> 

接着，我们开启pbft选项，并指定4个“坏节点”

node main.js -p -b 1,5,7,10

经过几轮的分叉攻击后，我们看到所有正常的节点都是一致的，只有少数坏节点不一致

node 0 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:7eb1e1:6) -> (10:3d33b9:8) -> (11:851887:9) -> (12:37a10a:11) -> (13:7d0a62:12) -> (14:08376c:13) -> (15:7221d3:14) -> 
node 1 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:faf2c9:5) -> (10:0ed227:10) -> 
node 2 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:7eb1e1:6) -> (10:3d33b9:8) -> (11:851887:9) -> (12:37a10a:11) -> (13:7d0a62:12) -> (14:08376c:13) -> (15:7221d3:14) -> 
node 3 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:7eb1e1:6) -> (10:3d33b9:8) -> (11:851887:9) -> (12:37a10a:11) -> (13:7d0a62:12) -> (14:08376c:13) -> (15:7221d3:14) -> 
node 4 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:7eb1e1:6) -> (10:3d33b9:8) -> (11:851887:9) -> (12:37a10a:11) -> (13:7d0a62:12) -> (14:08376c:13) -> (15:7221d3:14) -> 
node 5 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:faf2c9:5) -> 
node 6 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:7eb1e1:6) -> (10:3d33b9:8) -> (11:851887:9) -> (12:37a10a:11) -> (13:7d0a62:12) -> (14:08376c:13) -> (15:7221d3:14) -> 
node 7 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:faf2c9:5) -> (10:0b98f7:7) -> 
node 8 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:7eb1e1:6) -> (10:3d33b9:8) -> (11:851887:9) -> (12:37a10a:11) -> (13:7d0a62:12) -> (14:08376c:13) -> (15:7221d3:14) -> 
node 9 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:7eb1e1:6) -> (10:3d33b9:8) -> (11:851887:9) -> (12:37a10a:11) -> (13:7d0a62:12) -> (14:08376c:13) -> (15:7221d3:14) -> 
node 10 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:faf2c9:5) -> (10:0ed227:10) -> 
node 11 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:7eb1e1:6) -> (10:3d33b9:8) -> (11:851887:9) -> (12:37a10a:11) -> (13:7d0a62:12) -> (14:08376c:13) -> (15:7221d3:14) -> 
node 12 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:7eb1e1:6) -> (10:3d33b9:8) -> (11:851887:9) -> (12:37a10a:11) -> (13:7d0a62:12) -> (14:08376c:13) -> (15:7221d3:14) -> 
node 13 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:7eb1e1:6) -> (10:3d33b9:8) -> (11:851887:9) -> (12:37a10a:11) -> (13:7d0a62:12) -> (14:08376c:13) -> (15:7221d3:14) -> 
node 14 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:7eb1e1:6) -> (10:3d33b9:8) -> (11:851887:9) -> (12:37a10a:11) -> (13:7d0a62:12) -> (14:08376c:13) -> (15:7221d3:14) -> 
node 15 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:7eb1e1:6) -> (10:3d33b9:8) -> (11:851887:9) -> (12:37a10a:11) -> (13:7d0a62:12) -> (14:08376c:13) -> (15:7221d3:14) -> 
node 16 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:7eb1e1:6) -> (10:3d33b9:8) -> (11:851887:9) -> (12:37a10a:11) -> (13:7d0a62:12) -> (14:08376c:13) -> (15:7221d3:14) -> 
node 17 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:7eb1e1:6) -> (10:3d33b9:8) -> (11:851887:9) -> (12:37a10a:11) -> (13:7d0a62:12) -> (14:08376c:13) -> (15:7221d3:14) -> 
node 18 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:7eb1e1:6) -> (10:3d33b9:8) -> (11:851887:9) -> (12:37a10a:11) -> (13:7d0a62:12) -> (14:08376c:13) -> (15:7221d3:14) -> 
node 19 (0:713304:0) -> (1:bb9e59:17) -> (2:641aad:18) -> (3:e2614b:19) -> (4:ac5538:0) -> (5:c82859:1) -> (6:015639:2) -> (7:288ce7:3) -> (8:fdc189:4) -> (9:7eb1e1:6) -> (10:3d33b9:8) -> (11:851887:9) -> (12:37a10a:11) -> (13:7d0a62:12) -> (14:08376c:13) -> (15:7221d3:14) ->