数量庞大的区块链节点是如何维持各节点间的共识的

Jun 26, 2018 distribution-consensus blockchain bitcoin ethereum

如果想要定制一条联盟/私有链，要求该链交易成本更低/高，交易延时更低/高，拥有完全的控制权/去中心化，什么样的共识协议能够最大程度满足需求？本文将对截止时下各大主流共识算法进行逐一介绍，提供一种客观的视角去更好地选择共识协议方案。



工作量证明(Proof-of-Work)

工作量证明是最早被发明出来并切实可行的 P2P 共识方案，也是目前唯一做到了完全去中心化的共识方案。 该概念首次在 2008 年，由 Satoshi 在 Google 的加密邮件列表中发表的一篇名为 「Bitcoin: A Peer-to-Peer Electronic Cash System」 的论文中被提出。

PoW 也是最广为人知的一种共识，工作量是证明节点清白的唯一手段，也是节点间彼此信任达成共识的唯一手段。 如果在计算完成后关于新区块的 hash 值存在分歧，那么节点总是信任计算量最大的节点。

首次应用

2009 年 1 月 3 日，世界上第一个区块链应用以及去中心化货币 Bitcoin 诞生。 Satoshi 在 Bitcoin 的区块生成过程中使用了这种共识机制： 一个符合要求的块区 hash 由 $N$ 个前导零构成，零的个数取决于网络的难度值， 节点想得到合理的块区 hash 需要经过大量随机尝试计算，计算时间取决于机器的哈希运算速度。

当某个节点能够提供一个合理的 hash 值，说明该节点确实经过了大量的尝试计算， 然而并不能得出计算次数的绝对值，因为寻找合理 hash 是一个概率事件。 当节点拥有占全网 $n\%$ 的算力时，该节点即有 $n\%$ 的概率找到区块 hash。

这是人类在分布式共识领域中迈出的重要的一步，再次感谢 Satoshi 创造出这个东西。

不足之处

  • PoW 存在 51% 攻击问题，恶意挖矿者超过全网算力的 51% 后基本上就能完全控制整个网络。
  • 虽然已上链的数据无法被更改，但恶意挖矿者仍然可以做一些 DoS 攻击。
  • 所有相同创世块的旷工都能随时加入网络，潜在的安全隐患会长期存在。
  • 大量的电力资源消耗也是需要作为后续成本考虑。



权益证明(Proof-of-Stake)

PoW 并非完美，其中被指责最多的主要有两点：一是浪费能源；二是风险和收益博弈必然导致联合挖矿， 大算力矿池可能会对系统的去中心化构成威胁。

2011 年，名叫 Quantum Mechanic 的数字货币爱好者在 Bitcointalk 论坛提出 Proof-of-Stake 的共识机制， 该机制被充分讨论之后证明其具有可行性。 PoW 比拼算力，算力越大，挖到块的概率越大；PoS 则比拼余额，手里的币越多，挖到块的概率越大。

这意味着发表一个新区块的时候，无需证明矿工付出了什么代价，而需要证明矿工拥有一定数量的钱。 如果矿工作弊损害了这个系统的安全性，矿工的钱在交易所会贬值，这变相地让矿工付出了代价。

PoS 可以解决 Pow 的部分问题：

  • 由于不需要矿工持续地进行挖矿产生区块记录，更能节省电力；
  • 在 PoS 的共识理论下，越有钱的人，作弊付出的代价就越大，所以 51% 攻击在 PoS 是不可行的。

PoW 中能够影响共识结果的唯一因素是工作量，也就是说 PoW 的应用手段总是离不开大量的计算。 PoS 的设计需要一项具体的经济学模型或假说支撑其理论，算法的可靠性依赖于其背后的经济学理论， 所以 PoS 能够具体出多种不同的实现方案。

不足之处

PoS 从控制权、安全考虑以及运营方面仍有欠缺：

  • 持有量越多挖矿的可能越大，有可能会出现屯币现象，降低货币流通量。
  • PoS 仍然允许任何符合条件的旷工加入，对于没钱的人而言，他们的代价成本为零 。

Casper

Casper 是以太坊设计的一套 PoS 共识协议，是一种基于保证金的经济激励共识协议。 Casper 实际上是一棵 GHOST，因此 Casper 又被称为友善的小精灵(the friendly ghost)。

GHOST：Greedy Heaviest-Observed Sub-Tree(贪心最重观察子树)

PoW 最大的威胁之一就是矿工形成以损害非成员利益为代价，从而最大化成员获利的集团， 因此 Casper 将共识过程看作一个合作博弈：

  • Casper 协议中的节点，作为锁定保证金的验证人，必须先缴纳保证金才可以参与出块和共识形成；
  • 验证人如果做出任何 Casper 认为无意义的事情，他的保证金将被没收，出块和参与共识的权利也会被取消。

保证金的引入解决了无意义攻击，也就是经典 PoS 协议中做坏事的代价很低的问题。

同时 Casper 要求验证人将保证金中的大部分对共识结果进行下注，共识结果通过该下注情况形成：

  • 验证人必须猜测哪个块会胜出，同时下注这个块。
  • 赌对了可以拿回保证金外加交易费用，赌错了将失去保证金。
  • 没有在一定时间内达成一致，拿回部分保证金。

数回合后下注的分布就会收敛，这也是为什么说 Casper 是一种 PoW 在 PoS 上的变体：

  • 当出现分岔时，矿工选择一个块基于它进行开采。
  • 赌对了将得到挖矿的费用，赌错了将会损失电费。
  • 只要大部分的矿工都将算力下注到正确的链上，使这条链拥有最多的工作量，共识就是安全的。

PoW 的赌注会随着确认数的增加线性增加，而 Casper 的验证人可以通过协调使下注比例指数增长。 除了更节省电力，还能使共识能够以最快速达到最大安全。

委任权益证明(Delegated Proof-of-Stake)

DPoS 是 BTS/EOS 采用的一种共识协议，是一种类似股东议会制度的投票机制。 实际上这是解决 Nothing-at-stake attack 的另一种方式：只有富人才能参加共识。

DPoS 本质上还是一个中心化的共识机制，不再过多介绍。



权威证明(Proof-of-Authority)

PoA 由以太坊和 Parity Technologies 的联合创始人 Gavin Wood 提出，采用了授权签名的方式进行共识：

  • 创始块依靠预设好的 signer(已获得授权的 miner) 负责产生区块；
  • 在区块的生产过程中可以通过现有的 signer 投票选举出新的 signer；
  • 现有的 signer 也可以投票踢出恶意的 signer。

投票需要超过 50% 的同意。

以太坊的每个区块都包含了一个区块头，在 PoA 下，所有 signer 都将保存在其之中一个叫 Extra 的字段中。 Extra 包含所有签名者列表和当前签名者对该区块的签名数据(可以恢复出来签名者的地址)。

保存到 Extra 中而非引入新的字段的目的在于在避免改变核心数据结构的情况下直接引进新的功能。

任意高度的区块都有且仅有一个 signer 处于一个 $\text{IN-TURN}$ 的状态（相当于 leader）， 其它的 signer 则处于被称为 $\text{OUT-OF-TURN}$ 的状态。 leader 签名的块会立即广播，其它 signer 签名的块会延时一段随机时间后广播， 保证 leader 签名的块有更高的优先级上链。

为避免出现同一个 signer 能够在短期内频繁地签名并广播区块的情况，PoA 对签名作出了一点限制：

  1. 所有 signer 需轮流成为 leader；
  2. 如果用 $R$ 表示所有 signer 的数量，那么一个 signer 只能签名每 $\dfrac{R}{2} + 1$ 个块中的一个。

当 $R = 10$，signer $N$ 签名了第 4 个 pending 块， 则 $N$ 在到达第 7 块时才能恢复继续参与签名区块的能力（$5 + 1 \lt 7$）。

不足之处

只有少数被授权的 signer 才能够对区块进行签名，没有激励机制不利于自发的节点参与到共识环境， 这又回到了去中心化不足的我问题。



拜占庭容错(Byzantine Fault Tolerance)

一个安全的分布式计算和多代理系统，或者说一个具有较高可靠性的共识协议，它首先必须是可容错的。

这里将简单讨论下不可解的两位将军问题，再引申到拜占庭将军问题和分布式系统的容错问题及实用拜占庭容错。

两位将军问题(Two General’s Problem)

2 generals problems

  • 有两支军队一起攻打一座城市，他们各自占领城市附近两边不同的山谷，且各由一名将军领导。
  • 两军之间隔着一个山谷，双方唯一的通信方式就是派遣信使来往于三个山谷。
  • 中间山谷已被城市保卫军占领，信使在通过山谷时可能会被捕。
  • 现在两支军队要协商进攻城市的时间，只有两支军队同时进攻才能获得战斗的胜利。
  • 两位将军此时需要约定一个时间点，并就在约定的时间发动攻击。

将军们就攻击时间达成共识非常简单，在信息安全方面将军们可以使用签名的方法防止敌军进行伪造，于是：

  1. 一位将军发送了消息，但他无法确定消息是否到达，除非他收到了确认回复，因此他就会犹豫是否发起进攻。
  2. 另一位将军进行了回复，但他也无法确定回复是否到达，除非他收到了回复的回复，同上。

由於无法 100% 确定消息成功是否到达，两位将军只能在第 2 步不断重复，战况陷入了僵局。 这背后就是著名的FLP不可能原理：在分布式异步通信中，没有任何算法能绝对保障系统的一致性。

虽然两位将军问题已被证实无解， 但两位将军问题的不可解决性仅限当前处于具有不安全、不可靠的通信环境的完全异步分布式系统中才成立。

两位将军问题与网络连接都有着极为相似的安全隐患，那么 TCP 协议是如何保障网络连接的可靠性的？ 科学阐述了什么为是与不是，所以 TCP 也是不可靠的，所以三次握手和四次挥手上也是不可靠的， 所以 TCP 上的所有东西都是不可靠的，不管是 CDN 还是 P2P，任何分组交换网络都是不可靠的。

然而学术定理遵循的是严格的数学证明，通常考虑了最极端的情况。 而在工程实践中，学术上的极端情况一般很少会发生，即便发生，重试几次也就好了。 所以工程从另一个角度演绎了，只要付出一些代价，不是也是可以变成可能的， 譬如 TCP 可以通过双方发送数据包的通信频率以确定对方的状态，收不到回复的数据包可以一直重发等。 再譬如，每次都派出多名信使，或者干脆成立一个中心化的通信枢纽，通信交给可信第三方进行协调。

拜占庭将军问题(Byzantine General’s Problem)

「拜占庭将军问题」是由 Lamport、Shostak 和 Pease 于 1982 年提出的一个用于解释一致性问题的虚构模型：

  • 拜占庭军队的几个师在聚集在敌人城市外扎营，每个师都有自己将军指挥，将军们只能通过信使互相沟通。
  • 在观察敌人后，将军们决定共同行动。然而，一些将军可能是叛徒，试图阻止忠诚的将军达成共识。

这是两位将军问题的一个带反转的广义版本，它描绘了同样的场景，但增加了一层复杂性： 其中一个或几个将军有可能是叛徒，叛徒可以选择说谎。

那么将军们想要达成共识必须有一个算法来保证：

  1. 所有忠诚的将军都会采取同样的计划行动；
  2. 在叛徒占少数的情况下，忠诚的将军将不会采取糟糕的计划。

算法都必须保证条件 1 满足，但条件 2 很难正式化，因为它需要准确推测出错误的计划。

拜占庭容错(Byzantine Fault Tolerance)

拜占庭将军问题的解需要遵循一个定理： 对于任意 $m$，如果有多于 $3m$ 的将军和至多 $m$ 个叛徒，那么算法 $\mathrm{OM}(m)$ 达到共识。

此时，达成共识的算法将基于将军所观察到的其它大多数人的决策。 如果将军们在有叛徒存在的情况下仍然达成了一致，那么就称达到了拜占庭容错。

拜占庭容错是一种系统的特征，它定义了该系统可以容忍拜占庭故障类别的故障模式。

拜占庭故障：属于拜占庭将军问题的一类故障，拜占庭故障是最严重最难处理的故障之一。 在飞机发动机系统、核电站和几乎所有行为取决于大量传感器结果的系统都需要拜占庭容错。

实用拜占庭容错(Practical Byzantine Fault Tolerance)

在分布式系统的环境中，拜占庭容错一直都是分布式网络的重点研究对象， 目前这项技术已经在大量的实践中拥有了不少的优秀的优化版本。

实用拜占庭容错正是其中的众多优化之一，于 Castro 和 Liskov 于 1999 年发表的论文 「Practical Byzantine Fault Tolerance」 中被提出。 该算法旨在异步系统中工作中具有运行时的高性能，并且只有轻微的延迟增加。

pBFT 侧重于提供实用的拜占庭状态机复制，状态机通常被定义为一个多值元组： $\langle s,i,o,t,f,start \rangle$。

  • $s$: 一组状态。
  • $i$: 一组输入。
  • $o$: 一组输出。
  • $t$: 一个转换函数，$t(i, s) \rightarrow s^\prime$。
  • $f$: 一个输出函数，$f(i, s) \rightarrow o$。
  • $start$: 一个初始的状态。

一个拜占庭状态机从 $start$ 开始，在新的 $i$ 被接收到前，状态保持不变。 每一次接收到 $i$ 同时也会传入 $t$ 和 $f$，以生成新的 $s$ 和 $o$。

所有节点按顺序排序、彼此通信，假设存在故障节点时由特定节点操纵信息的传播来容忍拜占庭故障。 不仅需要证明消息来自特定的对等节点、还需要验证消息在传输过程中是否未被修改，使得节点达成状态一致。

pBFT 模型中的特定节点为主节点，其它节点称为备份节点。

pBFT str

为了使 pBFT 模型起到实际作用，故障的节点数量不能等于或超过系统中总节点数的 $\dfrac{1}{3}$。



Paxos

Paxos 协议于 1989 年首次发布，并以虚构的希腊 Paxos 岛所使用的立法共识系统命名， 是一系列用于在不可靠网络中解决共识的协议，假设当前场景下能够满足 Paxos 的前置假设，那么：

  1. 列举出一些场景，使得 Paxos 无法再满足一致性。
  2. 接着再丰富 Paxos 的协议流程使得能够满足该场景。
  3. 重复 1 和 2。

通过对协议不断改进，使得在任意场景下 Paxos 都能够保证系统的一致性，最终得到一套强大的 Paxos 协议。

角色(Roles)

在共识的过程中，所有参与了共识的节点都被授权了不同动作，并使用不同的角色来描述这些不同的动作：

  • Client：向分布式系统发起请求，并等待后续响应。
  • Proposer：接收到请求后发起 Proposal，在发生冲突时进行协调推进协议。
  • Leader：从 Proposer 中选出的领导者。
  • Acceptor：协议中的容错载体，会被收集到一个 Quorums 组中处理 Proposal。
  • Learner：协议的复制因子，一旦 Client 的请求得到 Accept ，那么 Learner 就可以获得一个 Action。

Acceptor 只能接收来自 Quorums 的 Proposal。

Learner 只能获得被 Accept 的提案。

在经典的 Paxos 部署中，一个节点往往能够同时扮演一个或多个角色， 并且多数时候都在同时扮演 Proposer、Acceptor、Learner 这三个角色。

不足之处

  • 传统 Paxos 协议需要满足一个前置假设：系统的环境是安全的，并不存在恶意的节点。

    Paxos 设计的初衷在于给大型企业服务器提供一种完全异步的分布式系统，虽然同样是为了解决共识难题， 但 Paxos 解决的仍然是由于网络故障、延迟导致消息出现的先后各异或丢失等一致性问题。

    因此 Paxos 要求系统不一定可靠，但一定安全，更正式的说要求系统无拜占庭将军问题。 这导致了纵使 Paxos 能够极快地形成共识，却不适合作为公链的共识算法来使用。

    Lamport 对此提出了一种 Byzantine Paxos 的方案来解决这个问题。

  • 适用性低，实现的变数大。

    Paxos 拥有非常多的变体，在不同的系统中往往需要满足不同的需求，无法统一的实现方案给移植带来了困难。



Raft

Raft 是一个用于实现分布式共识的协议，其共识过程可以简单地概括为： 使用一种可靠的投票机制选出一个中央节点 Leader，所有对系统的改变都在 Leader 的指挥下有序地完成。

当 Leader 出现问题无法继续胜任自己工作时，剩下的节点会迅速投票选举出下一个 Leader。 这种做法有效地解决了传统架构的系统主服务器出现系统故障时的问题，间接提高系统整体的可靠性及容错性。

领导选举(Leader Election)

Raft 的节点能够处于以下 3 种状态中的一种：

  • Leader：系统中的主节点。
  • Follower：系统中的其余节点。
  • Candidate： Leader 失效后，成为 Leader 候选者的 Follower 节点。

“This Is Extremely Dangerous To Our Democracy. (laugh”

日志复制(Log Replication)

当客户端发送消息给服务器时，除了 Leader 自身，所有节点都会把消息第一时间传递给 Leader。 Leader 也不会马上进行执行该条消息，而是将其作为一个 entry 添加到节点日志中。

之后 Leader 会将该条 entry 同步给所有 Follower，Follower 收到消息同样会更新自己的节点日志。 如果大多数 Follower 都完成了操作并返回，那么提交就完成了。 接下来 Leader 会执行该项 entry 并更新系统的状态，并通知所有 Follower 更新自己的系统状态。

通过这种日志复制的操作，分布式集群能够很简单且快速就系统状态方面达成共识。

不足之处

通过使随机的节点随机成为 Candidate 再选举为 Leader，其后的共识完全交给 Leader 完成， 那么当出现恶意节点时，系统基本完蛋，也就是说 Raft 同样要求系统无拜占庭将军问题。



总结

共识算法的选择与应用场景高度相关，可信环境使用 Paxos 或者 Raft，带许可的联盟链可使用 pBFT， 想创建去中心化的共链可以选择 PoW、PoS、PoA 等。

根据信任度分级，自由选择共识机制，此为最优。