区块链-共识算法

首先我们知道有两种故障容错类型：拜占庭容错(BFT)和崩溃容错(CFT)。

• 崩溃容错（CFT）是一种弹性，在这种情况下，如果组件出现故障，系统仍可以正确地达成共识。
• 拜占庭的容错（BFT）表示即使在存在恶意参与者的情况下也可以完成共识。

分布式系统

共识算法一般在分布式系统中经常使用，而且我们这学期也在想学习MapReduce、Spark、Flink这类框架。其实，区块链系统也是一种分布式系统，因为在区块链中每个节点独立运行交易，不同的节点可能运行在地理上分离的区域，而有些节点可能存在恶意、可能发生故障。

因此，区块链系统作为一个整体应该对外提供可靠、可用、一致性的服务，但处理结果的一致性是基础。

分布式系统分为同步和异步分布式系统。

同步分布式系统

同步分布式系统需要严格满足：

（1）节点运行指令的时间有严格的上限和下限；

（2）消息能够在有限的时间内传输到目标节点；

（3）每个节点有一个本地时钟，与实际时间的偏移率在一个已知的范围内。

同步分布式网络就像两个人打电话，只要不挂断，一个人就必须等待在那边听声音

对于运行在广域网上的区块链系统来说，上述约束条件很难满足(因为区块产生的速度比较慢)，而且区块链网络中的节点可能在空间上的距离不等。因此区块链系统一般采用异步分布式系统(弱同步)。

异步分布式系统

异步分布式系统具有如下性质：异构性、并发性、可靠性、可用性、缺乏全局时钟、故障独立性

异步分布式系统存在一些限制：

1. 每一个动作在不同的节点运行时间不同，因为机器的性能不一样
2. 消息可以在任意长时间后接收到，因为网络存在延迟
3. 时钟漂移率可以使任意的

异步模型对运行速度和消息延迟没有任何假设，这就要求区块链系统中的模型和算法不应立足于某些限制进行设计。就好比发微信，我看到了别人发来的微信，才会回复，而不是一直抱着手机等在那边

• 一致性问题

  • 处理结果一致（状态一致）。指分布式系统中多个节点就某一处理结果达成一致，基本方法是状态复制（State Replication）。如传统数据库的发布订阅模式，就实现了数据库的一致性。
  • 输入的一致性。指从多个节点的输入值中，选取其中一个作为决策值，并作为分布式系统共同的输入。这也是区块链中通常所说的共识。

• 可靠性问题

  • 可靠性（可用性）是描述系统可以提供服务能力的重要指标，通常用两个时间指标MTBF（ Mean Time Between Failures ，平均故障间隔时间）和MTTR（ Mean Time to Repair ，平均修复时间）来衡量。一个高可用性系统应该具有尽量长的MTBF和尽量短的MTTR。

在集中式系统中，一旦出现单点故障，就只能让系统重启，任务会被搁置。分布式系统就解决了这个问题，分布式系统需要首先保证高可靠、高可用性。由此，在分布式系统中需要有多个节点。

假设系统中有n个节点，其中最多有f个节点可能崩溃，在剩下的n-f个好的节点中，从节点i提交一个区块$B_i$(输入值)开始，所有节点要遵循相同的协议，从全部提交的区块中选择一个区块(一致性结果，决策值)，并用该去快提交到区块链系统

从多个节点输入值中选取一个决策之就称为共识，达成共识过程中所遵循的协议就是共识算法

共识需要满足的条件

• 一致性： 所有好节点的决策之必定相同
• 可终止性： 所有好节点在有限的时间内结束决策过程
• 有效性: 选择出的决策之必须是某个节点的输入值

故障容错是指区块链系统中节点和通信信道都有可能出现故障，导致部分节点不可用或者偏离被认为正确的结果或行为。

不同故障的影响：“遗漏故障”，“随机故障”，“时序故障”（时序故障主要针对同步分布式系统，对执行时间、通信时间和时钟漂移均有限制）。

遗漏故障是指节点或通信信道不能完成它应该做的动作，就是崩溃了。也称为CFT。在异步环境下，由于对节点的运行速度和消息传递延迟没有限制，因此我们无法判断消息到底是在路上，还是节点已经崩溃。这种情况被称为可变消息延迟。区块链系统中共识算法的设计应该基于可变消息延迟的模式

• 节点遗漏故障： 主要是崩溃，意味着节点停止并不再执行任何动作，也不再对消息进行响应。一般用一段固定时间等待故障节点对消息的应答来检测，如果其他节点能确切检测到节点已经崩溃，那么这个节点崩溃称为故障-停止。但对异步系统，超时只能表明节点没有响应，这可能是节点崩溃了，也可能是节点执行速度慢甚至是消息还没有到达
• 通信遗漏故障： 指通过通信信道，节点A不能把消息m成功传送到节点B，也叫信息丢失。在存在消息丢失的消息传递模式下，任何一条消息都不能保证可以安全地到达消息的接收者。存在两种情况，一种是消息到达节点B，但消息内容已经损坏，这种可以通过消息签名检测；另一种情况就是消息丢失。

遗漏故障在异步分布式系统中是比较难解决的——无论是节点还是通信，都难以判断其是否发生了故障。

随机故障也称为拜占庭故障，用于描述可能发生的任何类型故障，如故意返回错误结果或者处理的结果本身就是一个错误的。

• 节点的随机故障通常是指节点进程随机地省略要做的处理步骤或执行一些不需要的步骤，从而导致产生错误的执行结果。这类故障不能通过查看节点是否应答来检测，也无法通过密码学的方式来进行判断，因为它可能随机地应答或者应答错误的结果。
• 通信通道也会出现随机故障，如消息内容可能被损坏或者传递不存在的消息，也可能多次传递同样的消息。这类故障可以通过校验、消息签名或时间戳等机制进行检测。

因此在基于拜占庭故障的共识算法在设计时，除了考虑拜占庭节点是否返回结果，还需要考虑返回错误结果的情况，因此基于拜占庭的共识算法通常要求不超过1/3的出错节点，就是考虑到即使1/3的正常节点和1/3的故障节点对冲后，仍然有多数1/3能够使算法形成共识

FLP原理

FLP不可能原理：当允许存在节点失效的情况下，不存在一个确定性的共识算法总能在异步模型下达成一致。就连POW也不是确定性的，也可能存在一条链被推翻的情况

但是，在同步模型下，由于其对节点处理时间、消息传递、始终都有要求，很容易判断是否失败，从而决定是否重传或者其他方式进行故障排除。

FLP原理实际上说明对于允许节点失效的情况下，纯粹的异步系统无法确保一致性在有限的时间内完成。即便对于非拜占庭错误的前提下，包括Paxos、Raft等共识算法都存在无法达成共识的情况。

但是，在工程实践中，在付出一些代价的情况下，获得高效的共识算法还是很有必要的。具体付出什么代价，共识算法能达到什么程度，往往通过CAP原理进行衡量。

CAP原理

CAP 原理是指在一个分布式系统中，一致性（Consistency）、可用性（Availability）、分区容错性（Partition tolerance），三者不可兼得。

分区容忍性是在物理上进行保证的，比如说在海底铺设多条光缆，出现概率较小且难以完全避免。因此我们只能在AC之间做一个trade-off，这是由业务场景决定的

1. 弱化一致性(保证A)，允许某个时刻不一致，但是最终仍然会达到一致
   • 适用于对结果一致性不敏感的应用，可以允许新的数据副本产生后经过一段时间后，所有节点才更新成功，期间不保证一致性。如简单分布式p2p协议Gossip
   • 不同的区块链系统采用不同的机制来确保新的交易所基于的区块链数据库是最新状态。如比特币要求6个区块确认，Fabric要求背书节点对交易背书
2. 弱化可用性(保证C), 允许执行过程”慢一些“，甚至拒绝服务
   • 适用于对结果一致性很敏感的应用，例如银行取款机，当分布式系统对处理不能达到一致结果时会拒绝服务。
   • Paxos 、Raft 等共识算法，主要处理这种情况。在Paxos 类算法中，可能存在着无法提供可用执行结果的情形，同时允许少数节点离线。

区块链系统中的ACID原则

ACID我们已经不陌生了，那么区块链中的ACID是什么样的呢？

• 原子性：每次对系统的更新操作都是原子的，要么成功，要么不执行。对于区块链系统，一个原子操作是一个 区块，因此区块的提交应满足原子性要求。
• 一致性：上面我们说的都是一致性。一个操作开始和结束时，数据库的状态是一致的，无中间状态。对于区块链系统，不同节点在一个区块提交前后的状态应该是一致的。
• 隔离性：并发操作时，彼此不需要知晓对方存在，执行互不影响，需要串行化执行，有时间顺序。在区块链系统中，要根据并发交易到达的顺序逐个添加到区块中，在区块提交时按照排序顺序执行。
• 永久性： 状态的改变是持久的，不会失效，也不会无缘无故回滚。区块链系统中，一个区块一旦达成共识，会永久附加到原有的区块链中，不可篡改。

BASE理论

在计算机网络中中，还有一个很重要的理论：BASE (Basic Availability ,Soft-state, Eventual Consistency 三个短语的缩写)

这个原则与ACID相对，就是说牺牲掉对一致性的约束(最终仍然实现一致性)，来换取一定的可用性。BASE理论的核心思想是：即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性

• Basic Availability(基本可用,总归会可用的)。分布式系统在出现不可预知故障的时候，允许损失部分可用性，如响应时间上的损失或系统功能上的损失。实际例子：12306抢票
• Soft-state(允许系统中的数据存在中间状态)。认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。即节点之间不一致的状态
• Eventual Consistency(最终一致性)。所有的数据副本在经过一段时间的同步之后，最终都能够达到一个一致的状态。因此本质是需要保证最终达到一致，而不需要实时保证强一致性。

BASE理论是对CAP中一致性和可用性权衡的结果(牺牲一致性，换取可用性)、其来源于对大规模互联网系统分布式实践的总结，是基于CAP定理逐步演化而来的。

BASE理论面向的是大型高可用可扩展的分布式系统，和传统的事务ACID特性是相反的，它完全不同于ACID的强一致性模型，而是通过牺牲强一致性来获得可用性，并允许数据在一段时间内是不一致的，但最终达到一致状态。

在实际的分布式场景种，由于不同业务单元和组件对数据一致性的要求是不同的，因此在具体的分布式系统架构设计过程中，ACID特性和BASE理论又往往会结合在一起

Paxos

Paxos算法是基于消息传递且具有高度容错的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。该算法能够解决分布式网络中存在遗漏故障，并且故障节点数小于总节点数的1/2的场景下的共识问题。

PBFT算法