拜占庭问题

这篇具有很好参考价值的文章主要介绍了拜占庭问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

拜占庭问题

说明

本文为哈尔滨工程大学计算机科学与技术学院区块链技术课程附加作业

完成人:

(1)学号:2019201131 姓名:周光煜 工作量:50%

(2)学号:2019201120 姓名:孙世威 工作量:50%

区块链简介

区块链是一个基于比特币协议的不需要许可的分布式数据库,它维护了一个持续增长的不可被篡改和修改的数据记录列表,即使对于数据库节点的运营者也是如此。简而言之,区块链是由区块用某种方式组织起来的链条。区块链现如今广泛应用于我们的生产生活之中,例如疫情防控后的有序复工复产等。
区块链是一个分布式账本账本,区块链网络系统务中心地维护一条不停增长的有序的数据区块,每一个数据区块内部都有一个时间戳和一个指针,指向上一个区块,一旦数据上链后就不可修改。由此可见,区块链的典型特点之一就是具备分布式结构。这就要求我们必须解决分布式系统中实现状态共识的算法,保证不同账本节点上的账本数据的一致性和正确性,否则区块链将失去其信用。由此,便有了拜占庭将军问题和拜占庭容错技术。

拜占庭问题简介

拜占庭问题是莱斯特兰伯特等科学家于1982年提出用来解决一致性问题的一个模型。拜占庭是古代东罗马帝国的首都,由于其地域宽广,守卫边境的多个将军需要通过信使来传递消息,以对军事活动达成一致的决定。但是由于将军中可能存在叛徒,这些叛徒将努力向不同的将军传递不同的消息,试图干扰共识的达成并使得某些将军做出错误的决定。拜占庭问题描述的就是在此情况下,如何让忠诚的将军们能够达成行动的一致。

三将军模型

拜占庭有n个将军,他们都可以独立的作出决策,选择进攻和撤退,彼此之间通过信使传递消息。对于一场战争,所有的将军必须作出共同的作战决策并依此执行,只有半数以上的将军同时进攻才能取得战斗的胜利,作战计划的制定遵循“少数服从多数原则”。为了简化问题,我们采用3个将军进行说明。
假设现有三个将军A、B、C,他们都是忠诚于拜占庭的将军,对于一场战斗,他们三人将讨论出一个共识的作战计划,选择进攻或者撤退,并忠诚的执行作战指令。他们首先分别根据自己的判断选择进攻或者撤退,然后将自己的决策发送给其他两个将军,其他两个将军也将他们的作战计划传递给该名将军,然后这名将军根据少数服从多数的原则,执行大多数人选择的作战方案。
假设A、B两名将军选择进攻,C将军选择撤退。那么,
A将军通过信使告知B、C选择进攻;
B将军通过信使告知A、C选择进攻;
C将军通过信使告知A、B选择撤退;

拜占庭问题,区块链,区块链

对于每个将军而言,收到的消息中进攻与撤退的比例均为2:1,因此每个将军根据少数服从多数的原则,均执行进攻指令,实现了共同作战的目标。
但是,拜占庭地域辽阔,将军中可能存在叛徒。叛徒并不一定会如实的发送相同的指令,就会导致将军之间的一致性遭到破坏,无法达成共识作战目标。
下面假设叛徒为B,叛徒B将告知A和C不同的作战信息。
A将军通过信使告知B、C选择进攻;
C将军通过信使告知A、B选择撤退;
叛徒B通过信使告知A选择进攻,但告知将军C选择撤退;

拜占庭问题,区块链,区块链

在这种情况下,A收到的指令中进攻与撤退的比例为2:1,A将军将选择进攻.C将军收到的指令中,进攻与撤退的比例为1:2,C将军选择了撤退。而叛徒B理所当然会选择撤退。于是我们发现,只有将军A发动了进攻,无法取得战争的胜利,将军之间的共识也被打破,产生了结果的不一致性。

指挥官-副官模型

将拜占庭问题简化一下描述即为:有一个指挥官发送一个命令给他的n-1个副官们,而且在这个问题中要有两个基本条件:

条件一:所有忠实的副官遵从相同的指令;

条件二:如果指挥官是忠实的,那么所有副官都将执行他的命令。

下面我们就用实际的例子讨论一下拜占庭问题,帮助大家理解

指挥官和副官都是忠诚的

拜占庭问题,区块链,区块链

指挥官分别向两个副官发出进攻命令。副官1和副官2都是忠诚的,副官2向副官1说:“指挥官下达了进攻的命令”。副官1收到的副官2的消息和指挥官的消息是相同的,这时就达成了共识,共同发起进攻。

副官2是叛徒

拜占庭问题,区块链,区块链

指挥官会分别向两个副官发出进攻命令。副官2是叛徒,他欺骗副官1说:“指挥官下达了撤退命令”。副官1收到了两个不同的命令,判定指挥官与副官2中至少有一个叛徒。他无法判断谁是叛徒,因此也无法正确行动。

指挥官是叛徒

拜占庭问题,区块链,区块链

指挥官向两个副官下达了不同的命令。副官1收到的是不同的命令,那么指挥官和副官2中有叛徒,但由于不能确定谁是叛徒,无法采取正确的行动。

结论

当三人中有一个是叛徒时,无法达成一致的行动,即拜占庭问题无解,且无法判断叛徒是谁。

如何解决拜占庭问题

F代表叛徒的数量,N代表将军的总数,

根据Lamport对拜占庭问题的研究表明,当N>=3*F+1时,拜占庭问题有解。

证明 n>3m,BGP(n, m)存在
接下来,让我们一起来看下当 n>3m,BGP(n, m)存在时应该如何证明。存在类的证明相比较而言直接一些,如果我们能够找到一个解决 BGP(n, m)的策略就可以证明解法存在。此时的难点变成——如何找到这个策略,对于这类策略问题,同样有一个通用的数学证明方法,那就是数学归纳法。

和反证法类似,数学归纳法的证明通常也分为两步:

证明 n=1 的时候命题成立;
假设 n=k-1 时命题成立,证明 n=k 时命题也成立。
可以看出,数学归纳法和反证法比较类似,在上一个证明中我们利用反证法从假设命题推导已知结论,而在数学归纳法里,我们是从已知结论推导假设命题。

在上一讲中,已经讲了在四个将军、一个叛徒的情况下,也就是BGP(4, 1) 是存在解决方法的。那接下来我们就来小试牛刀,证明一下在 n>=4 的情况下, BGP(n, 1) 存在这个命题。n=4 的情况已经是成立的了,现在假设 n=k-1 命题也成立,也就是 BGP(k-1, 1)存在,看一下 n=k 的情况是怎样的。

首先,假设在 n=k 的情况下发令将军是忠诚的,那么剩下的 k-1 个副官里有 1 个叛徒。接下来,k-1 个副官之间同步关于发令将军所发出的命令。这种情况下每个副官都成为了一个发令将军,发的命令是关于自己从最开始的发令将军那里所得到的命令。由于BGP(k-1, 1) 的存在,忠诚副官之间可以通过 BGP 算法对每个副官所发出的命令达成一致,因此每个忠诚副官就会受到 k-2 个忠诚副官的命令、1 个叛徒副官的命令。由于忠诚副官之间的命令都是从忠诚发令将军那里来的命令,他们之间命令也是一致的,因此每个忠诚副官只要对所收到的命令取一个大多数人的意见,彼此之间就可以达成一致。

再来看下发令将军是叛徒的情况,那么剩下 k 个副官都是忠诚的,且他们彼此之间不存在欺骗,我们还是用上一步中用BGP(k-1, 1) 同步消息取大多数的方法,所有忠诚副官之间最终达到的命令,依然是一致的。如此一来,我们用同一套同步消息,且取大多数的方法就完成了从 n=k-1 到 n=k 的推导,也就证明了在 n>=4 的情况下 BGP(n, 1)的存在。而且,你会发现在证明推导的过程中我们也找到了解决这个问题的策略。

好了,现在让我们进入正餐,证明 n>3m 时,BGP(n, m) 存在的命题。由于我们上一步证明了 BGP(n, 1),因此 BGP(n, 1) 也就变成了一个已知条件。我在这里对 m 进行一下归纳:假设 m=k-1 命题成立,也就是BGP(n, k-1) 存在,证明 m=k 时命题也成立。这一命题和上一个命题的证明过程,非常类似。

首先,假设在 m=k 时发令将军是叛徒, 剩下的 n-1 个副官之间进行信息同步,由于剩下的副官里有 k-1 个叛徒,在 n>3k 的情况下 n-1>3k-1>3k-3,因此剩下的忠诚副官之间可以通过 BGP(n, k-1) 算法来对每个副官发出的命令达成一致。这样一来,我们依然可以用取大多数的方法来让忠诚副官之间达到一致。

这里我们可以总结出数学归纳法的一个套路,就是想方设法在 n=k 的情况下削减掉一个将军,这样就可以复用 n=k-1 的假设,然后再削减掉一个到 n=k-2 的假设,一直递归下去到 n=1 的已知情况。之后在使用 n=1 的结论一路向上来解决 n=2,n=3 一直到 n=k。

再来看发令将军是忠臣的情况。你会发现少了一个忠臣,副官里叛徒数量占比变大了,固而没办法再用之前的假设了。如果我们还是用上一步的方法不断地削减一个将军进行递归的话,叛徒的比例可能会越来越大,当削减到 BGP(n-m+1, 1) 时,剩余的副官里最多可能有 m 个叛徒和 m+1个忠臣。表面看上去问题似乎是无法解决了,但是你回过头来仔细再想一下,该假设的前提是发令将军是忠臣,因此 m+1 个忠臣收到的命令是一致的。由于同步信息后所有的 2m+1 个命令中与发令将军一致的占据了多数,因此用同样取大多数的方法我们依然得到了正确且一致的结果。

综合上面两个推导,不难看出:

无论发令将军忠诚与否,BGP 算法都可以达成一致;
我们既证明了在 n>3m 时,BGP(n, m) 存在的命题,同时又在推导的过程中得出了 BGP 算法的解决策略,可谓是一举两得。

拜占庭容错算法

拜占庭容错算法是面向拜占庭问题的容错算法,主要用于解决在网络通信可靠但节点可能故障的情况下如何达成共识。

实用拜占庭容错算法其实就是给全网消息的顺序进行共识,得到一个全局的序。在恶意节点不高于总数的1/3并在一个比较弱的同步假设的情况下,该算法能够同时保证安全性和活性。

区块链网络的记账共识和拜占庭将军问题相似。参与共识记账的每一个记账节点相当于将军,节点之间的消息传递相当于信使,某些节点可能由于各种原因产生错误信息并传递给其他节点。通常,这些发生故障节点被称为拜占庭节点,而正常的节点称为非拜占庭节点。
拜占庭容错系统是一个拥有n台节点的系统,整个系统对于每一个请求,满足以下条件:
(1)所有非拜占庭节点使用相同的输入信息,产生同样的结果;
(2)如果输入的信息正确,那么所有的非拜占庭节点必须接收这个信息,并计算相应的结果。
与此同时,在拜占庭系统实际运行中,还需假设整个系统的拜占庭节点不超过m台,并且满足安全性和活性。
拜占庭系统普遍采用的假设有:
(1)拜占庭节点的行为可以是任意的,拜占庭节点间可以共谋;
(2)节点之间错误不相关;
(3)服务器间传递的信息,第三方可以嗅探到,但不能篡改、伪造和破坏完整性;
(4)大部分协议假设消息在有限时间内可以传递到目的地。

原始的拜占庭容错系统缺乏实用性,采用一定的手段改进而来的PBFT算法降低了拜占庭协议运行复杂度,使拜占庭协议在分布式系统中的应用成为可能。PBFT在很多场景中都有应用,区块链中适合于对强一致性有要求的私有链和联盟链场景,如IBM主导的区块链超级账本项目。
整个协议的基本过程如下:
(1)客户端发送请求,激活主节点的服务操作。
(2)当主节点接收请求后,启动三阶段的协议以向各从节点广播请求
A.序号分配阶段,主节点给请求赋值一个序列号n,广播序列分配消息和客户端请求消息m,并将构造PRE-PREPARE消息给各从节点;
B.交互阶段,从节点接收PRE-PREPARE消息,向其他服务节点广播PREPARE消息;
C.序号确认阶段,各节点对视图内请求和次序进行验证后,广播COMMIT消息,执行收到的客户端的请求并给客户端响应。
(3)客户端等待来自不同节点的响应,若有m+1个响应相同,则该响应即为运算的结果。

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

RE消息,向其他服务节点广播PREPARE消息;
C.序号确认阶段,各节点对视图内请求和次序进行验证后,广播COMMIT消息,执行收到的客户端的请求并给客户端响应。
(3)客户端等待来自不同节点的响应,若有m+1个响应相同,则该响应即为运算的结果。

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

比特币的工作量证明共识机制给予了解决拜占庭问题的新思路。工作量证明能够在恶意节点的算力不超过系统总算力1/2的情况下解决拜占庭问题。工作量证明1/2的容错阈值比BFT类共识机制1/3的容错阈值要高,其主要原因是BFT类共识机制解决拜占庭将军问题的框架是通过投票的方法实现的,而工作量证明是通过争夺记账权的方式而非以合作投票的方式解决拜占庭将军问题。文章来源地址https://www.toymoban.com/news/detail-793883.html

到了这里,关于拜占庭问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【区块链共识协议论文】【拜占庭异步通信】【Chronos: An Efficient Asynchronous Byzantine Ordered Consensus】

    1、 版权归属:牛津大学出版社(Oxford University Press) 2、 笔者为共同作者之一,联系方式:E230047@e.ntu.edu.sg 3、 引用格式: 4、 代码仓库:见GitHub 第1页 第2页 第3页 第4页 第5页 第6页 第7页 第8页

    2024年02月20日
    浏览(41)
  • PBFT实用拜占庭容错算法

    本篇文章开启区块链共识算法的普及——我以 PBFT (Practical-Byzantine-fault-tolerant)实用拜占庭容错共识算法打头阵。 为什么先是PBFT呢? 一个原因是觉得这个算法的名字很酷,实际上它也有着有趣的历史背景。另一个原因呢,就是最近在接触联盟链,而这个算法呢,正是联盟链

    2024年02月02日
    浏览(39)
  • 实用拜占庭容错算法 (PBFT)

    一、算法原理     实用拜占庭容错算法 (Practical Byzantine fault tolerance, PBFT)是一种状态机副本复制算法, 每个状态机的副本都保存了服务的状态, 同时也实现了客户端所有合法请求的操作, 能够保证在满足分布式系统活性和安全性的前提下, 允许 (n − 1)/3 个节点出错 (数据丢失、

    2024年02月11日
    浏览(44)
  • 一致性广播、可靠广播、原子广播、安全因果原子广播以及与拜占庭协议结合

    在分布式系统中,广播协议是确保信息在网络中的节点之间有效传递的关键机制。一致性广播、可靠广播、原子广播和安全因果原子广播是分布式系统中用于确保消息传递和一致性的四种不同类型的广播协议。它们各自有不同的目标和特性,适用于不同的应用场景。本文是对

    2024年04月13日
    浏览(61)
  • 区块链媒体发稿:区块链媒体宣发常见问题解析

    据统计,由于区块链应用和虚拟货币的兴起,越来越多媒体对区块链领域开展报导,特别是世界各国媒体宣发全是热火朝天。但是,随着推卸责任媒体宣发的五花八门,让很多人因而上当受骗,乃至伤害一大笔资产。身为投资人或是参加者,世界各地媒体宣发是否靠谱?应该

    2024年02月14日
    浏览(37)
  • 区块链存在的问题

    源自于:区块链关键技术及存在问题研究综述_刘双印 综述 多形式数据存储 数据更新 跨链时延 用户隐私保护 企业资源保护 事务排序依赖 数据高冗余 不可持续发展 算力浪费  系统自身产生分叉导致的分叉 首先,区块链在弱共识的前提下,因系统时间顺序产生区块的特性,

    2024年02月02日
    浏览(27)
  • 区块链常见问题

    双花问题(double spending attack):虚拟货币与纸质货币的区别在于可以复制,我可以把虚拟币100元给到A,再复制100元给到B。 如何解决:每个交易通过分布式账本进行记录,这个分布式账本就是区块链。每个交易都会 指明币的来源,证明币不是凭空捏造的是有记录的,同时根

    2024年02月09日
    浏览(52)
  • 区块链常见交易问题-高级

    以太坊账户类型 交易部署合约 交易调用合约(ERC20 等) 合约运行报错 合约的gas不足 抛出event的交易 多合约互相调用 Token 与 NFT 数据区别 交易、消息与调用(Message Call)的区别 介绍区块链交易 区块链是一种记录保存系统,在将条目添加到数据链之前会有多个源来验证该条

    2024年02月06日
    浏览(47)
  • 共识问题:区块链如何确认记账权?

    区块链可以说是最近几年最热的技术领域之一,区块链起源于中本聪的比特币,作为比特币的底层技术,本质上是一个去中心化的数据库,其特点是 去中心化 、 公开透明 ,作为分布式账本技术,每个节点都可以参与数据库的记录。 区块链是一个注重安全和可信度胜过效率

    2024年02月05日
    浏览(41)
  • 区块链入门的几个基本问题

    当我们在提到区块链的时候,很多人都知道这是个跟金融,就是跟money有关的东西,与其说区块链,我们常用的词应该是区块链技术,这种说法其实就揭露了其本质——技术。那与区块链相关联的另一个名词又是什么呢?那当然就是大名鼎鼎的比特币(BitCoin)。 比特币,你可

    2023年04月09日
    浏览(28)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包