拜占庭容错(BFT)算法介绍

简介: 【原文作者:Jae Kwon,译者:郭光华】2011年比特币将世界的注意力引向到了区块链。但可惜的是,比特币版本的区块链不能解决区块链行业的很多问题。

【原文作者:Jae Kwon,译者:郭光华】

2011年比特币将世界的注意力引向到了区块链。但可惜的是,比特币版本的区块链不能解决区块链行业的很多问题。那是因为:

1、比特币的POW共识会浪费大量能源。

2、交易非常缓慢,一笔交易需要花一个小时甚至更长的时间。

3、没有什么激励机制来激励POW矿工忠于一条链,所以会导致升级很困难。

我们需要一种安全的共识,并且不会给我们的地球施加巨大的能源成本。这种方法就是基于拜占庭容错(BFT)的权益证明(POS )。我们称之为BFT-PoS。

在我们深入了解BFT-PoS之前,我们只需要知道拜占庭错误,而不需要知道拜占庭将军问题 的细节。 在分布式系统中,数据需要在数百或数千个节点上进行复制,而计算机时不时会网络中断或脱机,所以需要有一些容错机制或共识算法。那么如果这些节点的一部分失败,整个系统仍然需要达成共识。

标准的容错共识算法(如Raft 和Paxos)假设当一个节点出现故障时,它只是停止工作而不回复消息。谷歌,Facebook和一些现有的数据库产品已经在他们的防火墙内使用了这一系列的共识算法,使机器有故障产生时也能确保服务仍然可用。

但这些算法不适用于公有区块链,因为公有区块链中没有防火墙。任何拥有算力(PoW)或代币(PoS)的人都可以参与,甚至可以试图破坏网络。为了达成共识,我们需要拜占庭的容错能力。在拜占庭故障中,故障节点能以完全任意的方式运行。节点甚至可以串通来尝试作恶,并最大限度地发挥其破坏力。

因此,本质上,BFT共识算法的目的是在不信任网络(如万维网)中的节点间建立信任。 BFT不是什么新概念,该概念首先在Lamport,Shostak和Pease于1982年的一篇学术论文中引入 。但是Lamport等人只在同步环境中(所有的消息总是及时到达)演示了算法的理论可行性。 但在现实世界中,你不能真正地相信互联网能及时交付任何东西。

所以在1988年,Dwork,Lynch,Stockmeyer(DLS)提出了一种在大多数异步环境中工作的算法。 1999年晚些时候,米格尔·卡斯特罗和芭芭拉·里斯科夫提出了一个实用的解决方案,用于持续的BFT协商一致,这仍然是迄今为止最先进的BFT算法。

但长久以来,主流媒体忽视了这些创作。 没有人明白BFT在学术界和诸如IBM和DARPA之类的主要机构之外的重要性,直到2009年Bitcoin来临。比特币是第一个开放式去中心化应用程序,为全球货币帐本提供BFT共识,但对拜占庭式将军的问题采用了一种全新的解决方案:PoW。在PoW中,谁的算力最强,谁最有可能打包交易出块,获得该块交易费和新产生的比特币。今天,许多矿业公司在生产矿机,也有许多矿工正在加入矿池。

另一方面,PoS完全消除了PoW的能源依赖。在PoS中,矿工被替换为在系统中拥有股权的“验证者”。验证者不必投资昂贵的处理系统,但他们必须购买“股权代币”。任何普通笔记本电脑都足以解决计算。 Peercoin,BitShares,Nxt等已经使用了某种形式的PoS,而Ethereum正在计划于不久的将来进行PoS。然而,虽然PoS具有实际意义,但是很多人都反对使用PoS,声称这是不可能的。但这根本不是事实。使用BFT,您绝对可以保护PoS。只是我们还没有看到任何公有链实现了BFT-PoS。

虽然该理论可能难以解释或理解,但适当的BFT算法提供的最终结果很容易掌握。 与PoW区块链不同,BFT-PoS块链根本不分叉。对于双花攻击,除非1/3或更多的验证者协调进行此类攻击。而且,当1/3或更多的验证者确实导致双重花费攻击时,我们可以计算确定哪些验证者需要对攻击负责,进而可以摧毁它们的权益代币并将其从网络中剔除,就好像矿工联合起来控制整个链一样。

至今,包括POW算法在内,还没有哪种共识算法可以达到BFT-PoS的容错水平。 BFT-PoS表现非常出色。今天,在全球有几百个验证节点的公有链中,你可以在3s内轻松获得交易确认。这一“即时确认”的最佳容错阈值理论已经被tendermint证明。虽然随着验证节点的增加共识速度会变慢,但遵循着Nielsen定律(网络带宽和响应速度增长),每年都可以增加一定的节点,而性能不会变。

此外,BFT-PoS还将增加移动钱包的安全性。目前存在的移动钱包很少充分利用了比特币提供的安全性,因为没有人愿意等待一个小时才能确认交易。相反,大多数钱包只是假设转账的人不会双花。而且,虽然我们没有时间在这里进行深入研究,但高效的移动钱包协议或“轻客户端SPV”协议是未来区块链互操作性的关键。

虽然PoW在比特币方面表现很好,但代价昂贵,速度慢,环境不友好。现在最好的选择是BFT-PoS。它是一种持久、节能的解决方案,在异步环境中运行良好。最重要的是,由于BFT是计算机科学界最好和最聪明的开发机构证明安全的。

目录
相关文章
|
算法
secondday--拜占庭之书面算法
书面协议: 上面揭示了口头协议不能追本溯源、如果我们引入一种方法让他能达到追本溯源呢? 除了A1、A2和A3以外、我们在口头协议上加入一个A4、使之成为书面协议 A4:(1)、签名不可伪造、一旦被篡改即可被发现、而叛徒的签名可被其他叛徒伪造      ...
1064 0
|
5天前
|
算法
基于模糊控制算法的倒立摆控制系统matlab仿真
本项目构建了一个基于模糊控制算法的倒立摆控制系统,利用MATLAB 2022a实现了从不稳定到稳定状态的转变,并输出了相应的动画和收敛过程。模糊控制器通过对小车位置与摆的角度误差及其变化量进行模糊化处理,依据预设的模糊规则库进行模糊推理并最终去模糊化为精确的控制量,成功地使倒立摆维持在直立位置。该方法无需精确数学模型,适用于处理系统的非线性和不确定性。
基于模糊控制算法的倒立摆控制系统matlab仿真
|
5天前
|
机器学习/深度学习 算法 定位技术
MATLAB - 遗传算法(GA)求解旅行商问题(TSP)
MATLAB - 遗传算法(GA)求解旅行商问题(TSP)
9 3
|
6天前
|
算法
基于多路径路由的全局感知网络流量分配优化算法matlab仿真
本文提出一种全局感知网络流量分配优化算法,针对现代网络中多路径路由的需求,旨在均衡分配流量、减轻拥塞并提升吞吐量。算法基于网络模型G(N, M),包含N节点与M连接,并考虑K种不同优先级的流量。通过迭代调整每种流量在各路径上的分配比例,依据带宽利用率um=Σ(xm,k * dk) / cm来优化网络性能,确保高优先级流量的有效传输同时最大化利用网络资源。算法设定收敛条件以避免陷入局部最优解。
|
1月前
|
传感器 算法
基于无线传感器网络的MCKP-MMF算法matlab仿真
MCKP-MMF算法是一种启发式流量估计方法,用于寻找无线传感器网络的局部最优解。它从最小配置开始,逐步优化部分解,调整访问点的状态。算法处理访问点的动态影响半径,根据带宽需求调整,以避免拥塞。在MATLAB 2022a中进行了仿真,显示了访问点半径请求变化和代价函数随时间的演变。算法分两阶段:慢启动阶段识别瓶颈并重设半径,随后进入周期性调整阶段,追求最大最小公平性。
基于无线传感器网络的MCKP-MMF算法matlab仿真
|
16天前
|
算法 5G vr&ar
基于1bitDAC的MU-MIMO的非线性预编码算法matlab性能仿真
在现代无线通信中,1-bit DAC的非线性预编码技术应用于MU-MIMO系统,旨在降低成本与能耗。本文采用MATLAB 2022a版本,深入探讨此技术,并通过算法运行效果图展示性能。核心代码支持中文注释与操作指导。理论部分包括信号量化、符号最大化准则,并对比ZF、WF、MRT及ADMM等算法,揭示了在1-bit量化条件下如何优化预编码以提升系统性能。
|
23天前
|
算法
基于kalman滤波的UAV三维轨迹跟踪算法matlab仿真
本文介绍了一种使用卡尔曼滤波(Kalman Filter)对无人飞行器(UAV)在三维空间中的运动轨迹进行预测和估计的方法。该方法通过状态预测和观测更新两个关键步骤,实时估计UAV的位置和速度,进而生成三维轨迹。在MATLAB 2022a环境下验证了算法的有效性(参见附图)。核心程序实现了状态估计和误差协方差矩阵的更新,并通过调整参数优化滤波效果。该算法有助于提高轨迹跟踪精度和稳定性,适用于多种应用场景,例如航拍和物流运输等领域。
|
14天前
|
存储 算法 调度
基于和声搜索算法(Harmony Search,HS)的机器设备工作最优调度方案求解matlab仿真
通过和声搜索算法(HS)实现多机器并行工作调度,以最小化任务完成时间。在MATLAB2022a环境下,不仅输出了工作调度甘特图,还展示了算法适应度值的收敛曲线。HS算法模拟音乐家即兴创作过程,随机生成初始解(和声库),并通过选择、微调生成新解,不断迭代直至获得最优调度方案。参数包括和声库大小、记忆考虑率、音调微调率及带宽。编码策略将任务与设备分配映射为和声,目标是最小化完成时间,同时确保满足各种约束条件。
|
24天前
|
算法 网络性能优化 调度
基于De-Jitter Buffer算法的无线网络业务调度matlab仿真,对比RR调度算法
1. **功能描述**: 提出了一个去抖动缓冲区感知调度器,结合用户终端的缓冲状态减少服务中断。该算法通过动态调整数据包发送速率以优化网络延迟和吞吐量。 2. **测试结果**: 使用MATLAB 2022a进行了仿真测试,结果显示De-Jitter Buffer算法在网络拥塞时比RR调度算法更能有效利用资源,减少延迟,并能根据网络状态动态调整发送速率。 3. **核心程序**: MATLAB代码实现了调度逻辑,包括排序、流量更新、超时和中断处理等功能。 仿真结果和算法原理验证了De-Jitter Buffer算法在无线网络调度中的优势。
|
28天前
|
传感器 机器学习/深度学习 算法
基于GA遗传算法的WSN网络节点覆盖优化matlab仿真
本研究应用遗传优化算法于无线传感器网络(WSN),优化节点布局与数量,以最小化节点使用而最大化网络覆盖率。MATLAB2022a环境下,算法通过选择、交叉与变异操作,逐步改进节点配置,最终输出收敛曲线展现覆盖率、节点数及适应度值变化。无线传感器网络覆盖优化问题通过数学建模,结合遗传算法,实现目标区域有效覆盖与网络寿命延长。算法设计中,采用二进制编码表示节点状态,适应度函数考量覆盖率与连通性,通过选择、交叉和变异策略迭代优化,直至满足终止条件。

热门文章

最新文章