网站创建器,上海专业做网站公司有哪些,镇江百度竞价,做空间的网站吗文章目录 拜占庭将军问题问题背景问题的现实意义将军-副官模型三将军问题四将军问题3m将军问题 口头消息算法基本假设方法介绍正确性证明 签名消息算法 区块链区块链是什么区块链对于拜占庭将军问题的解决方法工作量证明奖励机制最长链原则小结 区块链的意义 总结 拜占庭将军问… 文章目录 拜占庭将军问题问题背景问题的现实意义将军-副官模型三将军问题四将军问题3m将军问题 口头消息算法基本假设方法介绍正确性证明 签名消息算法 区块链区块链是什么区块链对于拜占庭将军问题的解决方法工作量证明奖励机制最长链原则小结 区块链的意义 总结 拜占庭将军问题
问题背景
拜占庭帝国是历史上赫赫有名的一个帝国也就是东罗马帝国。它的首都是君士坦丁堡。但是1453年君士坦丁堡沦陷了之后这个帝国也就灭亡了。拜占庭将军问题并不是历史上真实存在的而是一个虚拟的问题。它是在1982年的时候由著名的计算机大神兰波特图灵奖获得者提出的。
拜占庭将军问题可以这么描述说有这么一个城堡拜占庭帝国想进攻这个城堡于是它就派出了很多支军队。由于通信的落后军队之间只能通过信使来交流。城堡非常坚固足以抵挡几支军队的进攻但是如果所有军队同时进攻这个城堡就会沦陷。但是问题是在军队中可能存在叛徒这个叛徒会胡说八道。 于是他们要商量一个方法让大家同时进攻。
问题的现实意义
计算机可以分布在世界各地我们称之为分布式节点。这些分布式节点可能会出现故障比如宕机也可能会有恶意节点比如黑客。那么在这样的情况下我们如何才能保持那些忠诚的计算机的一致性和正确性这就是拜占庭将军问题的意义。
究其根底“拜占庭将军问题”最终想解决的是互联网交易、合作过程中的四个问题信息发送的身份追溯、信息的私密性、不可伪造的签名和发送信息的规则。
将军-副官模型
我们把拜占庭问题简化一下简化为将军-副官模型。 只考虑一个将军如何发送信息给其他将军这种模式被称为指挥官-副官模式我们定义发送消息的将军为指挥官接收消息的将军为副官。在n个将军的情况下指挥官向n-1个副官发送消息需要满足如下条件
IC1. 所有忠诚的副官都遵守相同的命令一致性
IC2. 如果将军是忠诚的那么所有忠诚的副官必须遵守将军的命令正确性。
令 n n n表示总人数 m m m表示叛徒的人数。 当 n 3 m n3m n3m时该问题可解。
三将军问题
我们来看一个例子 n 3 , m 1 n3,m1 n3,m1。 假设将军为Ccommander两个副官分别为1和2。
先看第一种情况叛徒在副官中。 假设2为叛徒。 将军告诉1和2说要进攻。 1接到命令之后不会立刻进攻因为他不确定C是不是叛徒。这个时候他就去问2接到的命令是什么。因为2是个叛徒他就会告诉1他接到的是撤退命令。这样一来1就会困惑。将军告诉他进攻2号副官告诉他撤退。这个时候他就会困惑不知道该进攻还是撤退他也没办法分辨谁是叛徒。
再看第二种情况假如将军是叛徒。1和2都是忠诚的。 作为叛徒将军会告诉1进攻告诉2撤退。然后1告诉2自己接到了进攻命令2告诉1自己接到了撤退命令。1和2这两个忠诚的将军都会接到一个进攻命令和一个撤退命令。他们都会知道对方和将军中有一个是叛徒但无法知道是谁。
所以在这种情况下该问题不可解。
四将军问题
再来看一个例子 n 4 , m 1 n4,m1 n4,m1。 将军为C副官分别为1、2和3。
先看第一种情况叛徒在副官中。假设3号是叛徒。 将军告诉三个副官的命令是进攻然后三个副官之间就开始互通信息。1和2会互相告诉对方自己接到的命令是进攻。1和2也会告诉3自己接到的命令是进攻。3是叛徒他可能会告诉1和2自己接到的命令是撤退。 1从将军和2接到了进攻命令从3接到了撤退命令他只要取这三个命令中最多的进攻命令就可以了。 2从将军和1接到了进攻命令从3接到了撤退命令这样2也会进攻。 这样1和2都会进攻且忠诚地执行了将军的命令满足了IC1和IC2。
再看第二种情况将军是叛徒3个副官都是忠诚的。 此时只需要满足IC1即可。只要三个副官做出了一致的决定即可。 假设将军告诉1和2进攻告诉3撤退。然后三个副官会如实地告诉其他两个副官自己接到的命令。 1会接到将军和2的进攻命令接到3的撤退命令于是1会进攻。 2会接到将军和1的进攻命令接到3的撤退命令于是2会进攻。 3会接到将军的撤退命令但是接到1和2的进攻命令于是3也会进攻。 这样一来三个副官都会进攻就达到了一致性IC1满足。由于将军的命令是混乱的所以不用管将军的命令只要他们达成一致就可以了。
3m将军问题
我们现在要说明当有m个叛徒而将军数小于3m1时该问题无解 证明(反证法) 将3m将军m叛徒问题中的将军称为阿尔巴尼亚将军3将军1叛徒中的将军称为拜占庭将军以示区分。 注意此处的拜占庭将军并不单指叛徒而是指所有的将军。 拜占庭指挥官代表一个阿尔巴尼亚指挥官和m-1个阿尔巴尼亚副官两个拜占庭副官分别代表m个阿尔巴尼亚副官。 因此对于拜占庭叛徒将军(代表m个阿尔巴尼亚将军)最多对应m个阿尔巴尼亚叛徒将军。 由IC1可知m个阿尔巴尼亚中尉(由单个诚实拜占庭中尉所代表)遵循相同的命令这一命令也是该诚实拜占庭节点所需要遵守的命令。 对于阿尔巴尼亚将军可知是满足IC1和IC2的又由以上对应关系可知3将军问题是满足IC1和IC2的也即3将军问题存在解。 这与已知(3将军(1叛徒)问题不存在解)矛盾故3m将军问题不存在解。
口头消息算法
基本假设
每个将军都会执行某个算法来把消息传送给其他将军同时我们假设忠诚的将军会正确地执行该算法 “口头消息”可以通过如下我们为将军消息系统所做的假设来具体定义 A1-每个发送的消息都会被正确的传输 A2-消息的接收者知道发送者是谁 A3-消息如果丢失可以被检测到 假设A1和A2是防止叛徒介入其他两个将军的通信中 根据A1他无法妨碍其他两位将军发送的消息 根据A2他不能伪造消息来搅乱其他两位将军的交流 假设A3是为了防止一个叛徒通过简单的不发送消息来阻止一次决定
方法介绍
一个叛变的发令者可能会决定不发送任何命令。 由于下属们必须遵守相同的命令因此这种情况下他们必须有一个默认的命令。 我们使用RETREAT(retreat撤退)作为该默认命令。 我们归纳性的定义该口头消息(Oral Message简称OM)算法OM(m)m是非负整数m为叛徒个数通过这个算法一个发令者向n-1个下属发送命令。 可以证明对于3m1或者更多个将军时OM(m)解决了拜占庭将军问题。 用”获取一个值”来取代”遵守一个命令”这样的说法在描述该算法时显得更方便一些。 算法中还假设了一个函数 majority(取收到的消息(v1,v2……vn-1)的大多数(大多数的确定众数或者中位数))当一系列元素(v1,v2…vn-1)中出现次数占半数以上的元素为v时则 majority(v1,v2…vn-1) v否则 majority(v1,v2…vn-1) RETREAT。
算法OM(0) (1)发令者发送他的值给每个下属 (2)每个下属使用他从发令者那收到的值如果没有收到则使用值RETREAT
算法OM(m)m0 (1)发令者发送他的值给每个下属 (2)对于任意ivi代表下属i从发令者处收到的值如果没有收到则采用RETREAT下属i扮演算法OM(m-1)中的发令者并采用该算法将值vi发送给其余的n-2个下属 (3)对于任意i以及任意的j!i让vj代表下属i在步骤2中(使用算法OM(m-1))从下属j处收到的值如果他没有收到这样的值就采用RETREAT下属i采用函数majority(v1,v2…vn-1)的值
算法OM(m)中的 m 指代算法最多可以容许有多少个叛徒 不是要求有 m 个叛徒或者已知 m 个叛徒 OM(0)即为不提防任何叛徒的情况 在 m 0 的情况下每个下属都无法信任任何人因此对于每个接收到的值他们都需要使用 majority(v1,v2…vn-1) 确定 在第 m 轮中发令将军给每个下属都发送了一个值但谁都不敢相信这个值 因此每个下属都给其他 n-2除消息上游和自己个下属发送自己接收到的信息以帮助他人做决定叛徒可以发送任何值但规定了遵守此规则这就是 m-1 轮 而 m-1 轮收到的值大家又需要其他人的信息做决定因此又给其他 n-3除消息上游上上游和自己个下属发送自己的信息帮助他人做决定 以此类推一直到 OM(0) 为止
上面整个过程是一个递归的过程每个下属都会给其他下属发送很多信息为了使这些不同信息得以区分每个下属可以在发送消息时加上自己所属序号的前缀
正确性证明 引理1对任意m,k若系统中将军总数超过2km叛徒最多有k个算法OM(m)满足IC2即如果指挥官诚实那么每一个诚实的中尉都遵从指挥官的命令。 引理1证明 当m0时由A1可知IC2满足 当m0时在OM(m)算法的step(1)指挥官把值传给n-1个中尉在step(2)中每一个诚实的中尉调用OM(m-1)前文已知n2km因此n-12k(m-1)所以每一个诚实的中尉i都会得到城实中尉的vjv。又因为n-12k(m-1)2k即这n-1个中尉的半数以上都是诚实的所以step(3)中获得的majority(v1,v2……vn-1)必等于v即满足IC2。 定理1 对任意m如果将军数量大于3m且叛徒数最多是m算法OM(m)满足IC1和IC2。 定理1证明 当不存在叛徒(m0)的时候显然OM(0)满足IC1IC2的约束因此假定OM(m-1)成立证明OM(m)m0成立。 假设指挥官诚实由引理1可知若k与m相等则OM(m)满足IC2又因为在指挥官诚实的情况下IC1可以由IC2推出所以只需要证明在指挥官是叛徒的情况下检验是否满足IC1。 已知指挥官是叛徒最多有m个叛徒。所以中尉中最多有m-1个叛徒。中尉的数量是3m-1且3m-13(m-1),因此OM(m-1)满足IC1IC2。对于每一个j任意两个诚实的中尉得到的都是相同的vj的值(这任意两个中尉有一个是j的话就由IC2可以推出若不包括j的话由IC1可以推出)。因此任意两个诚实的中尉最终会得到相同的v1,v2……vn-1也即算法step(3)的majority(v1,v2……vn-1)相同OM(m)的IC1的以证明。
签名消息算法
其实口头消息的解决方案之所以复杂就是因为叛徒可以随意改更忠诚将军的消息而别人无法发现消息被改。如果我们让忠诚将军的消息无法篡改那么问题就变得简单多了。这就是签名消息的解决方案。
于是在前面的三条假设之下我们加入第四条假设 A4a忠诚将军的签名是不能伪造的内容修改可检测。即 即使是叛徒也要原封不动的签了名将消息转发出去 b任何人都可以识别将军的签名叛徒可以伪造叛徒司令的签名。后半句是论文中的后半部分规定的。
既然我们现在使用了消息签名那么之前将军数量必须大于等于 3 m 1 3m1 3m1才能达成共识的限制就可以去除了。事实上我们可以让任何数量的将军团体在存在 个叛徒的情况下达成共识这里虽然说任意数量但如果总数小于 m 2 m2 m2将没有意义。因为「达成共识」意味着两个或两个以上的人只有一个忠诚将军或跟本没有忠诚将军谈不上「达成共识」。
在给出解决方案之前我们首先要定义一个函数 。这个函数输入一个值的集合输出一个单一值。我们对这个函数有两个要求
1.如果集合 V V V由单个元素 v v v组成那么 c h o i c e ( v ) v choice(v)v choice(v)v 2. c h o i c e ( ϕ ) choice(\phi) choice(ϕ)始终为相同的默认值比如 RETREAT。共中 ϕ \phi ϕ代表集合为空。
另外在算法中我们使用 x : i x:i x:i代表由将军 i i i签名的值 x x x。类似的 v : j : i v:j:i v:j:i代表值 v v v先由将军 j j j签名得到 v : j v:j v:j然后 v : j v:j v:j又被将军 i i i签名得到 v : j : i v:j:i v:j:i 。
我们定义使用签名消息解决拜占庭将军问题的算法为 S M ( m ) SM(m) SM(m)其中 m m m代表叛徒的数量且 m ≥ 0 m\geq0 m≥0。 算法如下 (0). 每个将军 i 初始化自己的值集合 V i ϕ V_i\phi Viϕ 。 (1). 司令官将要发送的值签名然后发送签名后的值。 (2). 对于每个副官 i i i (A) 如果副官 i i i之前没接收过任何将军发过来的任何值且值的形式是 v : 0 v:0 v:0 那么 (i) 将 v v v加入到 V i V_i Vi中此时 V i { v } V_i\{v\} Vi{v} (ii) 将 v : 0 : i v:0:i v:0:i发送给其他副官 (B) 如果副官 i i i接收到了一个形式如 v : 0 : j 1 : ⋯ : j k v:0:j_1:\cdots:j_k v:0:j1:⋯:jk 这样的值并且 v v v不在 V i V_i Vi中那么 (i) 将 v v v加入到 V i V_i Vi中 (ii) 如果 k m km km那么此副官将值 v : 0 : j 1 : ⋯ : j k : i v:0:j_1:\cdots:j_k:i v:0:j1:⋯:jk:i发送给除 j 1 , ⋯ , j k j_1,\cdots,j_k j1,⋯,jk之外的所有其它副官 (C ) 如果副官 i i i接收到一个已经存在于 V i V_i Vi中的值则忽略它。 (3). 对于每个副官 i i i当自己不会再接收到更多值的时候它将 c h o i c e ( V i ) choice(V_i) choice(Vi)作为最终自己的共识值。
区块链
区块链是什么
区块链是一种分布式数据库技术用于记录数字信息的交易和事件。
它以去中心化的方式工作没有单一的控制中心每个节点都持有数据库的副本并能够进行验证和更新。区块链的核心特点包括去中心化、不可篡改、透明、安全以及可追溯性。它通过加密算法和共识机制来保证数据的安全性和可信度。每个区块包含多个交易信息和前一个区块的哈希值形成一个不可篡改的交易记录链。
区块链对于拜占庭将军问题的解决方法
在中本聪发明比特币以前世界上并没有一个非常完美的方法来解决“拜占庭将军问题”。
我们来看看区块链是如何解决拜占庭将军问题的。
工作量证明
这个工作量证明就是解决了各个将军之间可以随便发信息的问题比如3个将军都同时给对方发自己的军令那就是同时发9条军令。而且现实情况不是复杂的多吗如果都同时发消息那早都混乱不堪了。
那中本聪就给大家定了个规矩按顺序来发令那几个将军谁也不服谁。怎么办大家先去做算术题吧这就是所谓的哈希运算谁先算出题来谁就有资格发令这总公平吧。假如A将军先做出算术题那么A先发。
那A先做完了数学题其他将军就停止做算数然后都在自己这里记录下来并确认A确实是最先做出算术题的那就A将军获得发出广播的资格。并且大家重头开始做算术题还是谁做的快谁先发令如此往复。
假如叛徒B也解出来了题目B说是我先解出来的怎么办呢没关系聪哥说了咱们按解答的先后顺序给第一个解答出来的盖个章这个印章上有顺序和时间这也就是时间戳。
奖励机制
那还有了假如十多个将军某个将军最先做出算术题其他将军凭啥帮你确认和记录时间呢那这就有一个奖励机制了。
参与做题并且记录这个事情的人都会给一点奖励这也就是比特币。
最长链原则
为了解决不同将军间可能出现的分歧区块链技术引入了“最长链原则”。
这个原则要求将军们总是选择最长的区块链作为有效链。因为最长链需要更多的计算能力来达成所以最长链更有可能是诚实将军们达成共识的结果。
当不同的链产生时将军们会继续在自己的链上工作而最终最长的链会胜出。这样一来即使有叛徒尝试操纵区块链他们也难以形成比诚实将军们形成的区块链更长的区块链。
换句话说在区块链的设计结构和最长链原则下如果要篡改交易作恶者必须投入大量的计算资源与整个系统中其他所有矿工进行对抗这是非常困难的一件事情特别是整个系统已经具有一定基础计算资源的情况下。
所以篡改账本需要付出的算力成本可能远远大于篡改交易获得的收益。正常人都会把这些算力投入到正常记账中而不会拿来作恶这就避免了恶意攻击和作恶使得区块链具有不可篡改性。
小结
总结一下区块链利用共识机制确保只有找到答案的将军才能传递决策增加了叛徒影响决策的难度。
依靠区块链结构保护历史消息不被篡改确保每个将军都能看到完整且一致的历史记录。
遵循最长链原则在出现分歧时诚实将军们可以达成一致并且叛徒难以持续地干扰共识。
通过这些机制区块链技术帮助拜占庭将军们在可能存在叛徒的情况下实现了有效的分布式协作和一致性决策。
区块链的意义
区块链技术建立了新的信任机制允许各网络节点之间在没有权威节点的去中心化情况下达成可信共识是一项从思想到技术的重大飞跃。
拜占庭问题是为了解决由谁来发起信息并且怎么保证信息的同步和一致性。
而比特币的区块链技术则是解决了由谁来挖出区块并且让整个链上的所有区块统一的问题。
两者的问题在某些意义上可谓是一样的虽然在现实环境中有所不同可是区块链技术却为解决拜占庭难题提供了现行的最合理的方法也为后继者打开了新的思路。
所以比特币并不只是一串数字背后所用到的技术和原理解决了相当多的问题无可否认它是伟大的。
总结
本文先详细介绍了兰波特在1982年提出的拜占庭将军问题并列举了其在论文中给出的口头消息算法和签名消息算法。然后介绍了区块链并介绍了区块链是如何解决拜占庭将军问题的。
