读书笔记《区块链原理与技术 郑子彬》——区块链共识层

0 引入

• 区块链每个节点都有一份完整的账本，其面临的一大难题就是账本的更新，要保证区块链中各个节点的账本在更新后能保持一致。区块链的共识层就是解决上述问题的层级：在去中心化且存在恶意节点的场景下维护区块链的全局账本。

1 一致性问题

• 一致性问题是分布式领域最为基础和最为重要的问题。
• 系统间一致性程度的达成是不一样的，拜占庭容错算法达成的共识是确定性的，即共识生成高度为n的区块就是确定的；工作量证明达成的共识是概率确定的，即共识生成高度为n的区块是不确定的（分叉），随着区块链高度的增长，区块发生变化的概率越来越小。
• 一致性要求：

2 共识设计的理论限制

2.1 FLP不可能原理

• 在推广到任意情形时，分布式系统的共识问题是无通用解的：当分布式系统中多个节点之间的通信网络不可靠的情况下，无法确保实现共识。
• FLP不可能原理：在网络可靠，但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性算法。

2.2 CAP原理

• 本质上描述的是分布式系统在应用过程中三个特性的取舍，即分布式计算系统不可能同时确保以下三个特性：
  一致性：每次读操作都能得到最近写的结果或者返回错误。
  可用性：每次请求都能返回一个非错误的结果。
  分区容忍性： 任意节点间的连接中断或大大延迟，系统仍能够工作。

3 区块链共识算法

• 本质上是为了解决拜占庭将军问题

3.1 拜占庭问题

3.1.1 两将军问题

• 两个将军通过信使来达成进攻还是撤退的约定，信使可以被敌军阻拦或者迷路导致消息无法送达（或丢失或伪造）。根据FLP不可能定理，两将军问题是无通用解的。

3.1.2 拜占庭将军问题

问题描述

• 拜占庭是古代东罗马帝国的首都，守卫边境的多个将军们（即分布式系统中的多个节点）需要通过信使来传递消息，以对军事活动（系统中的某个提案）达成一致的决定。
• 将军中可能存在叛徒（系统中某些节点作恶），叛徒努力的向不同的将军传递不同的信息，目标是干扰共识的达成，使得某些将军做出错误的决定。
• 拜占庭问题即，在上述情况下，如何让忠诚的将军们能达成行动的一致。

结论

• 加入节点总数为N，叛变将军数为F，则当N>=3F+1时，问题才有解，由BFT算法进行保证。即叛徒不超过1/3时，存在有效的拜占庭容错算法。

3.2 拜占庭容错算法

BFT（Byzantine Fault Tolerance）
拜占庭容错算法

• 主要用于解决在网络通信可靠但节点可能故障的情况下，如何达成共识。
• 该算法存在复杂度过高的问题，后提出了实用拜占庭容错算法。

PBFT（Practical Byzantine Fault Tolerance）
实用拜占庭容错算法

• 给全网消息的顺序进行共识，得到一个全局的序。
• 在恶意节点不高于总数的1/3并在一个比较弱的同步假设的情况下，该算法能够同时保证安全性和活性。
• PBFT应用于欧盟链的场景而不应用于公有链的原因：
  1. PBFT在网络不稳定的情况下延迟很高；
  2. 基于投票机制，而投票集合是有限的，否则无法满足少数服从多数；
  3. 通信复杂度O(N^2)过高，可拓展性较低，一般的系统在达到100左右的节点个数时，性能下降非常快。

3.2.1 PBFT的基本概念

• 客户端（Client）
  向主节点发起请求的客户端，在区块链中往往跟主节点合二为一。
• 主节点（Primary）
  提案发起者，在区块链中即为区块发起者，在收到客户端请求后生成新区块并广播。
• 验证节点（Backup）
  提案投票者，在区块链中即为区块验证者，在收到区块后进行验证，然后广播验证结果对区块进行投票和共识。
• 视图（View）
  一个主节点和多个备份形成一个视图，在该视图上对某个提案达成共识，在区块链中即为对某个区块达成共识。不同视图的主节点一般是不一样的，即所有节点轮流做主节点，每个视图都会重新选择一个主节点。
• 编号（Sequence Number n）
  在每个视图中由主节点指定的一个数字，即提案的编号，在区块链中可以理解为区块高度。
• 检查点（Checkpoint）
  如果某个编号n对应的提案（区块）收到了超过2/3的确认，则称为一个检查点。

3.2.2 PBFT的具体流程

• PBFT的三个核心阶段：
  预准备阶段（PRE-PREPARE）、准备阶段（PREPARE）、提交阶段（COMMIT）
  
• 在该轮共识中，0是主节点，1~3是验证节点，收到客户端向主节点发起请求后，系统将进行PBFT核心的三阶段共识。

（1）预准备阶段

• 主节点收到客户端发来的请求之后，构造PRE-PREPARE消息结构体 << PRE-PREPARE,v,n,d>,m>，并签名后广播给其他节点。
  其中，PRE-PREPARE代表当前消息所处的协议阶段；
  v为当前视图的编号；
  n为主节点广播消息的一个唯一递增编号；
  d为消息m的摘要；
  m为客户端发来的消息，在区块链中可以视为交易。
• 验证节点收到主节点的PRE-PREPARE消息后，对消息进行检验，检验包括：
  1. 检查收到的消息摘要d与自己对m生成的摘要是否一致，确保消息的完整性。
  2. 检查与当前视图编号是否一致。
  3. 检查序号为n是否在高低水位区间[h,H]，防止主节点恶意地快速消耗可用的序号。
  4. 检查之前是否已经收到相同n和v，但不同摘要d的消息m，保证验证节点只处理具有相同n和v消息中的一个。
• 验证通过之后，验证节点会构造PREPARE消息结构体 << PREPARE,v,n,d,i>>，并在签名后广播给其他节点。
  其中，v、n、d的含义与PRE-PREPARE消息中一致；
  i为本节点的编号。
  • 在这个过程中，节点会将PREPARE消息和PRE-PREPARE消息记录到本地的日志中，用于视图切换中恢复未完成的请求，并重播到网络中在新的视图中继续共识。

（2）准备阶段

• 当节点收到其他节点的PREPARE消息时，进行如下检验：
  1. 检验PREPARE消息的签名是否正确
  2. 当前节点是否已经收到与PREPARE消息中v、n对应的PRE-PREPARE消息，且n在区间[h,H]
  3. d和当前已收到PRE-PREPARE消息中的d是否一致。
• 当节点在规定时间内收到2F+1（包括自己）个通过检验的PREPARE消息后，构造COMMIT消息结构体 << COMMIT,v,n,d,i>>，并签名后广播给其他节点。
  其中，v、n、d、i的含义与PREPARE消息中一致。
  • 在这个过程中，节点会将COMMIT消息和其他节点发送的PREPARE消息记录到本地的日志中，用于视图切换中恢复未完成的请求。
  • 此时，主节点发送的消息已经达到PREPARED状态，节点将进入提交阶段。

（3）提交阶段

• 当节点收到来自其他节点的COMMIT消息时，会对COMMIT消息进行检验，检验步骤与对PREPARE消息的相似。
• 当节点在规定时间内收到2F+1个（包括自己）通过检验的COMMIT消息，说明当前网络中的大部分节点已经对当前视图内的请求达成共识。
• 节点会处理消息m中包含的操作，如果有多个m，则按照序号n从小到大执行。
• 执行完成后，节点会返回结果给客户端。同样，在该过程，节点会将其他节点发送的COMMIT消息记录到本地的日志中。

  当客户端收到F+1个相同的结果（来自不同节点）时，说明已经在全网达成共识，否则客户端需要判断是否重新向主节点发起请求。

3.2.3 日志压缩（垃圾回收）

• 在PBFT核心的三个阶段过程中，为了确保视图切换能够恢复一些未完成的请求，每一个节点都会记录一些消息到本地的日志中。若不对其进行压缩或者回收，日志将会占用大量的磁盘空间。
• PBFT采用检查点（CHECKPOINT）的机制来实现日志压缩。
  • 最简单的做法（理想情况）：在节点处理完一个请求后并返回结果给客户端之后，再执行一次当前状态的同步。当这种状态同步得到全网的共识之后，节点可将该请求对应的日志清除。
  • 鉴于对每个请求作状态同步的成本太高，因此，可以在执行完多个请求（例如k个）之后执行一次状态同步，而状态同步消息便是在节点之间广播的检查点消息 < CHECKPOINT,n,d,i >。
  • 每执行k个请求后，节点 i 会创建一个检查点并广播消息 < CHECKPOINT,n,d,i > 给其他的节点。
    其中，i 为本节点的编号；
    n 是最后一次执行请求的序号；
    d 为执行序号为n的请求后的状态机的状态摘要。
    • 此外，该检查点消息同样会被记录到本地的日志中。
    • 同时检查点变成稳定检查点，高度为n。
  • （实际情况）：节点 i 向其他的节点发出检查点消息后，其他节点并未处理完k个请求，不会立刻对节点i做出响应。而节点 i 不会等待其他节点的回复，而是继续按照自己的节奏向前处理请求，但是节点i创建的检查点在此时没有变成稳定检查点。
  • 如果节点 i 处理请求过快，其创建多个检查点一直无法变成稳定检查点，会造成日志积压。
  • 解决方法：PBFT设置了高低水位区间[h,H]
    其中，低水位 h = 上一个稳定检查点的高度，高水位 H=h+L。
    L是系统设定的数值，等于节点周期处理请求数值K的整数倍。
    （例如设L=3K，当节点i处理的请求序号到达高水位 H=h+3K，便会暂停脚步，直到稳定检查点发生变化再继续向前，从而避免日志的积压。）

3.2.4 视图切换

• 保证系统的可用性：
    客户端发来的请求m由当前视图指定的主节点广播到网络中，但当主节点系统中断或者作恶，或者全网超过1/3的节点系统中断时，当前视图内的消息就无法在全网达成共识。此时，PBFT通过视图切换协议将全网的节点切换到新视图中， 对未完成的请求继续共识，避免节点无限期的等待，保证系统的可用性。
• 每个视图开始或者节点收到消息时，
  节点 i 会启动一个计时器，若此时有计时器在运行，则会重置计时器；
  但是当主节点系统中断或者其他情况导致节点 i 在当前视图v超时的时候，节点会触发视图切换的操作，启动视图切换协议。
  • 启动视图切换协议：
    节点 i 向其他节点广播 < VIEW-CHANGE,v+1,n,C,P,i > 消息，
    其中，n是最新的稳定检查点的高度；
    C 是节点 i 保存的经过2F+1个（包括自己）节点确认稳定检查点消息的集合，表面该稳定检查点已经达到全网共识；
    P 是当前节点保存的n之后所以已经达到PREPARED状态消息的集合，即已完成准备阶段的消息。
• 当新视图v+1中的主节点 i 收到2F+1个（包括自己）经过检验的VIEW-CHANGE消息后，将向其他节点广播 < NEW-VIEW,v+1,V,O > 消息。
  其中，V是有效的VIEW-CHANGE消息集合；
  O 是PRE-PREPARE消息集合，该集合是从已经达到PREPARED状态的消息中转换过来的。
  关于O ：
  • 当主节点收到2F+1个VIEW-CHANGE消息，可以确认高度为n的稳定检查点之间的消息在视图切换的过程中不会丢失，但是当前检查点之后、下一个检查点之前的已经达到PREPARED状态的消息会丢失。
  • 因此，新视图的主节点会把旧视图中已经达到PREPARED状态的消息转换为PRE-PREPARE消息，重新广播到网络中。
  • PRE-PREPARE消息集合的选取规则：
  1. 选取V中高度最低的稳定检查点的编号min，以及V中已达到PREPARED状态消息的最大编号max。
  2. 对于min和max之间的每个序号n，如果存在某个P中，则创建<< PRE-PREPARE,v+1,n,d>,m>消息；否则，创建一个空的PRE-PREPARE消息<< PRE-PREPARE,v+1,n,d(null)>,m(null)>，其中d(null)为空消息摘要，m(null)为空消息。
• 其他验证节点收到主节点的 NEW-VIEW消息后，校验签名，V和O的消息是否合法，验证通过后，则主节点和新节点都进入新视图。
• 总结：
  在视图切换中，C、P、O是三个重要的消息集合，
  C 确保了视图切换时，在最新稳定点之前的状态安全；
  P 和O 确保了视图切换中达到PREPARED状态的消息能够得到重放，而不会丢失。
  • 前文提到过，预准备阶段和准备阶段是为了确保同一视图下消息的一致性，而C、P、O三个集合就是解决这个问题的，确保在新视图中，主节点重放的旧视图中的消息依旧能保持顺序一致性。

3.2.5 PBFT中节点的状态

上述PBFT的核心流程中节点可能出现的状态如下：

• 等待请求 等待客户端的请求，所有节点都处于这个状态，主节点收到客户端请求之后，会切换到预准备状态；验证节点收到主节点消息后会切换到准备状态。
• 预准备 该状态是主节点专属的，主节点处理客户端的请求并广播PRE-PREPARE消息，切换到准备状态。
• 准备 节点进入这个状态后，验证主节点的PRE-PREPARE消息并生成和广播PREPARE消息，同时等待2F+1个（包括自己）节点的PREPARE确认。
• 等待2F+1个PREPARE确认 如果在超时之前收到2F+1个PREPARE确认，则切换到提交状态；否则，切换到视图切换状态。
• 视图切换 节点广播编号为v+1的VIEW-CHANGE消息，并等待2F+1个（包括自己）VIEW-CHANGE消息。
• 等待2F+1个VIEW-CHANGE消息 
  1. 当新视图的主节点收到2F+1个VIEW-CHANGE消息时，广播NEW-VIEW消息，并切换到预准备阶段，开始新视图的共识。
  2. 当验证节点收到2F+1个VIEW-CHANGE消息，切换到等待请求状态；若在这之前收到主节点NEW-VIEW消息，则开始新视图的共识，切换至准备阶段。
  3. 若超时，节点广播编号为v+1的VIEW-CHANGE消息，继续视图切换的协议，直到新视图切换成功。

3.3 比特币的工作量证明共识机制

3.4 以太坊共识算法Ethash

3.5 以太坊共识算法Casper

3.6 EOSIO共识算法BFT-DPoS

3.7 Monoxide