- 区块链每个节点都有一份完整的账本，其面临的一大难题就是账本的更新，要保证区块链中各个节点的账本在更新后能保持一致。区块链的共识层就是解决上述问题的层级：在去中心化且存在恶意节点的场景下维护区块链的全局账本。
- 一致性问题是分布式领域最为基础和最为重要的问题。
- 系统间一致性程度的达成是不一样的，拜占庭容错算法达成的共识是确定性的，即共识生成高度为n的区块就是确定的；工作量证明达成的共识是概率确定的，即共识生成高度为n的区块是不确定的（分叉），随着区块链高度的增长，区块发生变化的概率越来越小。
- 一致性要求：
- 在推广到任意情形时，分布式系统的共识问题是无通用解的：当分布式系统中多个节点之间的通信网络不可靠的情况下，无法确保实现共识。
- FLP不可能原理：在网络可靠，但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性算法。
- 本质上描述的是分布式系统在应用过程中三个特性的取舍，即分布式计算系统不可能同时确保以下三个特性：
一致性：每次读 *** 作都能得到最近写的结果或者返回错误。
可用性：每次请求都能返回一个非错误的结果。
分区容忍性： 任意节点间的连接中断或大大延迟，系统仍能够工作。
- 本质上是为了解决拜占庭将军问题
- 两个将军通过信使来达成进攻还是撤退的约定，信使可以被敌军阻拦或者迷路导致消息无法送达（或丢失或伪造）。根据FLP不可能定理，两将军问题是无通用解的。
问题描述
- 拜占庭是古代东罗马帝国的首都，守卫边境的多个将军们（即分布式系统中的多个节点）需要通过信使来传递消息，以对军事活动（系统中的某个提案）达成一致的决定。
- 将军中可能存在叛徒（系统中某些节点作恶），叛徒努力的向不同的将军传递不同的信息，目标是干扰共识的达成，使得某些将军做出错误的决定。
- 拜占庭问题即，在上述情况下，如何让忠诚的将军们能达成行动的一致。
结论
- 加入节点总数为N，叛变将军数为F，则当N>=3F+1时，问题才有解，由BFT算法进行保证。即叛徒不超过1/3时，存在有效的拜占庭容错算法。
BFT（Byzantine Fault Tolerance）
拜占庭容错算法
- 主要用于解决在网络通信可靠但节点可能故障的情况下，如何达成共识。
- 该算法存在复杂度过高的问题，后提出了实用拜占庭容错算法。
PBFT（Practical Byzantine Fault Tolerance）
实用拜占庭容错算法
- 给全网消息的顺序进行共识，得到一个全局的序。
- 在恶意节点不高于总数的1/3并在一个比较弱的同步假设的情况下，该算法能够同时保证安全性和活性。
- PBFT应用于欧盟链的场景而不应用于公有链的原因：
- PBFT在网络不稳定的情况下延迟很高；
- 基于投票机制，而投票集合是有限的，否则无法满足少数服从多数；
- 通信复杂度O(N^2)过高，可拓展性较低，一般的系统在达到100左右的节点个数时，性能下降非常快。
- 客户端（Client）
向主节点发起请求的客户端，在区块链中往往跟主节点合二为一。 - 主节点（Primary）
提案发起者，在区块链中即为区块发起者，在收到客户端请求后生成新区块并广播。 - 验证节点（Backup）
提案投票者，在区块链中即为区块验证者，在收到区块后进行验证，然后广播验证结果对区块进行投票和共识。 - 视图（View）
一个主节点和多个备份形成一个视图，在该视图上对某个提案达成共识，在区块链中即为对某个区块达成共识。不同视图的主节点一般是不一样的，即所有节点轮流做主节点，每个视图都会重新选择一个主节点。 - 编号（Sequence Number n）
在每个视图中由主节点指定的一个数字，即提案的编号，在区块链中可以理解为区块高度。 - 检查点（Checkpoint）
如果某个编号n对应的提案（区块）收到了超过2/3的确认，则称为一个检查点。
- 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消息后，对消息进行检验，检验包括：
- 检查收到的消息摘要d与自己对m生成的摘要是否一致，确保消息的完整性。
- 检查与当前视图编号是否一致。
- 检查序号为n是否在高低水位区间[h,H]，防止主节点恶意地快速消耗可用的序号。
- 检查之前是否已经收到相同n和v，但不同摘要d的消息m，保证验证节点只处理具有相同n和v消息中的一个。
- 验证通过之后，验证节点会构造PREPARE消息结构体 << PREPARE,v,n,d,i>>，并在签名后广播给其他节点。
其中，v、n、d的含义与PRE-PREPARE消息中一致；
i为本节点的编号。- 在这个过程中，节点会将PREPARE消息和PRE-PREPARE消息记录到本地的日志中，用于视图切换中恢复未完成的请求，并重播到网络中在新的视图中继续共识。
（2）准备阶段
- 当节点收到其他节点的PREPARE消息时，进行如下检验：
- 检验PREPARE消息的签名是否正确
- 当前节点是否已经收到与PREPARE消息中v、n对应的PRE-PREPARE消息，且n在区间[h,H]
- 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，便会暂停脚步，直到稳定检查点发生变化再继续向前，从而避免日志的积压。）
- 保证系统的可用性：
客户端发来的请求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消息集合的选取规则：
- 选取V中高度最低的稳定检查点的编号min，以及V中已达到PREPARED状态消息的最大编号max。
- 对于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三个集合就是解决这个问题的，确保在新视图中，主节点重放的旧视图中的消息依旧能保持顺序一致性。
上述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消息
- 当新视图的主节点收到2F+1个VIEW-CHANGE消息时，广播NEW-VIEW消息，并切换到预准备阶段，开始新视图的共识。
- 当验证节点收到2F+1个VIEW-CHANGE消息，切换到等待请求状态；若在这之前收到主节点NEW-VIEW消息，则开始新视图的共识，切换至准备阶段。
- 若超时，节点广播编号为v+1的VIEW-CHANGE消息，继续视图切换的协议，直到新视图切换成功。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）