Raft论文研读 Ⅱ

地址：知网

引用：[1]翟社平,廉佳颖,杨锐等.基于Raft分组的实用拜占庭共识算法[J/OL].计算机应用研究:1-9[2023-09-06].

期刊：计算机应用研究（北大核心）

作者：翟社平，廉佳颖，杨 锐，刘法鑫

基金项目：国家自然科学基金资助项目

日期：2023年

{/collapse-item}
{collapse-item label=" 1.2 文章主要创新点 "}
该篇论文与上周讲的一篇来自计算机应用期刊的论文高度相似，本文也是主要采用了K-medoids聚类算法将区块链进行分片，分片之后每个节点的主节点用PBFT算法进行共识，在分片内部采用Raft共识算法进行共识。

上周论文发布较早。

本文在这篇论文的基础上再次改进了一下K-medoids聚类算法计算各节点之间的距离的方法。在上周所讲的文章中，其采用了节点到领导者的通信时延做为欧式距离。而本篇是使用了一个混合蛙跳算法进行分片，大大提高了K-medoids分类的速度。

①创新点一：Raft与PBFT结合 -> H-PBFT

解决的问题：解决PBFT通信开销问题

解决方案：先分片、全局共识改为多中心共识、分片的小组组长采用PBFT、内部采用Raft。

②创新点二：监督策略

解决的问题：Raft是非拜占庭容错算法，为了解决在组内共识中存在恶意节点的问题。

解决方案：监督节点负责对当前子共识小组内领导者行为的进行监督。在监督节点的引入机制中，首先，为确保监督节点为非拜占庭节点，监督节点由上层管理者进行指定，无须考虑监督节点作恶。其次，为保证监督有效，监督节点不参与领导者选举，仅作为跟随者参与本组Raft共识。同时，为防止监督节点暴露造成领导者的恶意欺诈，监督节点需匿名加入系统。

{/collapse-item}

{collapse-item label=" 1.3 启发和总结 "}

本文的第一个创新点是很好的，为PBFT和Raft的结合提供了一种很高效的方向。本文的第二个创新点，个人认为通过监督节点来监督组内共识的领导者是不是有点太中心化了呢？因为监督节点是由上层管理者指定的！中心化太明显，而且如果一个信誉度很好并选为了监督节点，但是在组内共识时突然叛变了，这还是不安全。容错性和去中心化都没提升，而是有所下降。
{/collapse-item}

地址：知网

引用：[1]刘炜,郭灵贝,夏玉洁等.基于信用评价模型的Raft共识算法[J].计算机科学,2023,50(06):322-329.

期刊：计算机科学(北大核心)

作者：刘炜，郭灵贝，夏玉洁

日期：2023

{/collapse-item}
{collapse-item label=" 2.2 文章主要创新点 "}

①创新点一：

解决的问题：Raft改进为拜占庭算法

解决方案：通过节点信用度，采用孤立森林算法挖掘出异常的数据，从而检测出拜占庭节点。剔除拜占庭节点参与共识。

{/collapse-item}
{collapse-item label=" 2.3 启发 "}

使用机器学习算法剔除区块链中的拜占庭节点为改进Raft算法为拜占庭容错算法提供了一种新的思路，但是也会出现一定的问题，如果拜占庭节点剔除不干净或者拜占庭节点当场叛变。这些问题该如何处理呢？

{/collapse-item}

地址：知网

引用：[1]钱慧,郑朝晖,荣宝俊等.RPFT:基于PoW的高效率共识算法[J].小型微型计算机系统,2023,44(05):1061-1068.

期刊：小型微型计算机系统（北大核心）

作者：钱慧，郑朝晖，荣宝俊，王健翔

基金项目：国防科技创新特区支持

日期：2023

{/collapse-item}
{collapse-item label=" 3.2 文章主要创新点 "}

①Raft与POW共识算法结合

解决的问题：随着节点数量的增加，造成能投票的追随者节点数量增加，限制了选举速度。在极端情况下，由于分裂投票，将会有多轮选举，影响集群的工作效率。

解决方案：在Ｒaft算法3种状态的基础上添加“副领导”状态，作为领导者节点的备用节点，当节点宕机下线时，副领导者节点直接成为领导者节点。

等待时间选举模型：

该服务器节点距离上一次当选为领导者节点间隔的任期差值。为了防止等待时间无限大，规定当服务器节点当选为领导者节点时，置等待时间为零，剩余服务器节点更新等待时间值。

副领导者选举执行步骤是:

1．领导者正常工作时在无副领导者条件下会定时不断广播PoW难题消息，跟随者节点收到PoW难题解题，并在完成PoW难题时回复领导者。

2．验证:当领导者收到跟随者节点完成回复时，首先验证该跟随者节点任期和日志是否与自己一致，如果是一致并且副领导者为空，则执行3);否则认为该跟随者节点不符合要求，状态不变。

3．设置通过验证的跟随者节点成为副领导者，并广播告知其他节点副领导者身份并告知剩余服务器节点停止解题。

{/collapse-item}
{collapse-item label=" 3.3 启发 "}

本文实现了Raft与Pow共识算法的结合，将Pow的思想运用到了Raft中，但是由于Pow算法的特性，其功耗消耗太大。虽然解决了Raft领导选举中的一些问题，但是增加了能耗。不过也为解决Raft领导者选举提供了一种新方案。

{/collapse-item}

地址：知网

引用：[1]田苗. Raft共识算法研究及应用[D].郑州大学,2022.

期刊：郑州大学（硕士论文）

作者：田苗

日期：2022年

{/collapse-item}
{collapse-item label=" 4.2 文章主要创新点 "}

①降低领导节点的选举复杂度

解决的问题：Raft共识算法在候选者-->领导人的过程中，候选者会向所有的跟随着发送请求投票消息。为了解决这个过程时耗长的问题。

解决方案：选择部分节点 ，参与领导节点的选举投票过程，从而减小节点信息确认过程的开销。

• 提案节点P，Ｐ节点是共识节点通过主动被选举所产生的。它们通常有待发布的区块。
• 投票验证节点V，Ｖ节点是对Ｐ节点进行预选择所产生的，它们具有选举Ｌ节点的投票权和被选举权。
• 确认节点A，Ａ节点是共识节点选出来进行选举新的领导节点。

过程：

• 提案节点生成一对密钥，PK、SK（PK是公钥，SK是私钥）；
• 提案节点计算result=VRF-Hash(SK,info)得出随机数（info是节点的投票信息）；
• 确认节点计算 proof＝VRF-Proof（SK，info）该过程用于确认投票结果签名的合法性；
• 确认节点把result和proof递交给提案节点，即交付投票结果和确认结果，提案节点根据随机数结果产生投票节点；
• 投票节点计算True/False＝VRF－Verify(PK,info,proof)，True表示验证通过，False表示验证未通过。True选举为领导者。

• 在E-Raft共识算法中，通过VRF方法随机选择n倍的提案节点成为投票节点参与本次共识。
• E-Raft共识算法对所有提案节点产生的随机数进行验证，选择产生随机数大于阈值的节点成为投票节点。

{/collapse-item}
{collapse-item label=" 4.3 启发 "}

当E-Raft共识过程中信息受阻时，区块链存在分叉的可能性。区块链分叉会导致支链的信息无效化，从而使部分信息失效，降低信息传递效率。

{/collapse-item}

地址：知网

引用：[1]屈直. 基于多策略的Raft共识算法优化研究[D].西安工业大学,2023.

期刊：西安工业大学(硕士论文)

作者：屈直

日期：2023年

{/collapse-item}
{collapse-item label=" 5.2 文章主要创新点 "}

①增加节点状态信息、增加RPC心跳包状态消息

解决的问题：通过增加节点的信息，从而解决系统的中心化问题以及选举问题。

解决方案：增加节点信息，并在心跳包中增加当前领导者节点的吞吐量、写入业务处理次数、共识时延和报文发出的时间戳（用于测算跟随者节点与领导者节点间的心跳报文时延）信息。

②更改随机选举超时机制

解决方案：根据节点的状态信息实时计算出对应的节点分级，拟分为三个等级，用1、2、3表示，数字越小对应的优先等级越高。优先级为1的节点使用150-200ms的选举超时，优先级为2的节点使用200-250ms的选举超时，优先级为3的节点使用250-300ms的选举超时，高等级节点因其更短的随机时长而有更大几率成为候选者节点。

{/collapse-item}
{collapse-item label=" 5.3 启发 "}

{/collapse-item}

混合蛙跳算法（Hybrid Firefly Algorithm）是一种基于自然界生物行为的元启发式优化算法，用于解决优化问题。该算法结合了蛙跳算法和萤火虫算法的特点，以提高搜索效率和全局探索能力。

混合蛙跳算法的基本原理如下：

1. 初始化种群：随机生成一组候选解作为初始种群。
2. 适应度评估：计算每个候选解的适应度值，用于衡量其优劣程度。
3. 运动行为更新：根据候选解的当前位置和适应度值，参考蛙跳算法的思想，进行运动行为的更新。较好的解将引导其他蛙跳向其附近，从而实现解的迭代改进。
4. 光强更新：参考萤火虫算法的概念，根据候选解的适应度值和距离信息，更新光强。较好的解会释放更强的光，吸引其他蛙跳者向其移动。
5. 移动操作：根据候选解的当前位置、适应度值和光强，综合考虑蛙跳和萤火虫的行为方式，进行移动操作。蛙跳操作用于探索邻域解空间，而光强操作有助于引导全局搜索。
6. 终止条件：根据预设的停止准则，判断是否满足终止条件。例如，达到最大迭代次数或找到了满意的解等。

混合蛙跳算法通过蛙跳和萤火虫的交互作用，在解空间中进行全局和局部搜索，以寻找最优解或接近最优解的解。它具有较好的收敛性和搜索能力，可以用于求解各种优化问题，如函数优化、参数调整、组合优化等。

需要注意的是，混合蛙跳算法的性能受到参数设置的影响。合理选择适应度函数、调整步长、控制光强强度等参数，能够进一步提高算法的效果。此外，对于不同的问题，可能需要根据实际情况进行算法的定制和优化。
{/collapse-item}
{collapse-item label=" 6.2 孤立森林算法 "}

孤立森林算法（Isolation Forest）是一种用于检测异常值的机器学习算法。该算法利用数据点在树结构中的孤立度来判断其是否为异常值。

以下是孤立森林算法的基本原理：

1. 构建孤立树：随机选择一个特征，并在该特征的最小值和最大值之间随机选择一个分割值。将数据集分成两个子集，其中一个子集包含分割值之上的数据点，另一个子集包含分割值之下的数据点。重复这个过程，递归地构建二叉树，直到每个叶节点只包含一个数据点或达到预设的树的高度。
2. 计算孤立度：通过计算数据点在孤立树中的路径长度来衡量其孤立度。路径长度表示从根节点到叶节点经过的边数。孤立度越小，数据点越容易被孤立，可能是异常值；反之，孤立度较大的数据点更常见，可能是正常值。
3. 判定异常值：使用孤立度来判断数据点是否为异常值。通常，可以根据预先定义的阈值来决定何时将某个数据点标记为异常值。如果数据点的孤立度低于阈值，则被认为是异常值；否则，被视为正常值。

孤立森林算法的优点在于其计算高效、易于实现和对数据分布不敏感。它适用于各种领域的异常检测问题，包括网络安全、金融欺诈、工业监控等。然而，需要注意的是，在使用孤立森林算法时，选择合适的树的数量和高度以及定义恰当的孤立度阈值都是需要仔细考虑的因素。
{/collapse-item}