本假设方法介绍正确性证明

区块链区块链是什么区块链对于拜占庭将军问题的解决方法工作量证明奖励机制最长链原则小结

拜占庭将军问题

拜占庭帝国是历史上赫赫有名的一个帝国也就是东罗马帝国。

它的首都是君士坦丁堡。

但是1453年君士坦丁堡沦陷了之后这个帝国也就灭亡了。

拜占庭将军问题并不是历史上真实存在的而是一个虚拟的问题。

它是在1982年的时候由著名的计算机大神兰波特图灵奖获得者提出的。

拜占庭将军问题可以这么描述说有这么一个城堡拜占庭帝国想进攻这个城堡于是它就派出了很多支军队。

由于通信的落后军队之间只能通过信使来交流。

城堡非常坚固足以抵挡几支军队的进攻但是如果所有军队同时进攻这个城堡就会沦陷。

但是问题是在军队中可能存在叛徒这个叛徒会胡说八道。

计算机可以分布在世界各地我们称之为分布式节点。

这些分布式节点可能会出现故障比如宕机也可能会有恶意节点比如黑客。

那么在这样的情况下我们如何才能保持那些忠诚的计算机的一致性和正确性这就是拜占庭将军问题的意义。

究其根底“拜占庭将军问题”最终想解决的是互联网交易、合作过程中的四个问题信息发送的身份追溯、信息的私密性、不可伪造的签名和发送信息的规则。

将军-副官模型

只考虑一个将军如何发送信息给其他将军这种模式被称为指挥官-副官模式我们定义发送消息的将军为指挥官接收消息的将军为副官。

在n个将军的情况下指挥官向n-1个副官发送消息需要满足如下条件

IC1.

1接到命令之后不会立刻进攻因为他不确定C是不是叛徒。

这个时候他就去问2接到的命令是什么。

因为2是个叛徒他就会告诉1他接到的是撤退命令。

这样一来1就会困惑。

将军告诉他进攻2号副官告诉他撤退。

这个时候他就会困惑不知道该进攻还是撤退他也没办法分辨谁是叛徒。

作为叛徒将军会告诉1进攻告诉2撤退。

然后1告诉2自己接到了进攻命令2告诉1自己接到了撤退命令。

1和2这两个忠诚的将军都会接到一个进攻命令和一个撤退命令。

他们都会知道对方和将军中有一个是叛徒但无法知道是谁。

四将军问题

将军告诉三个副官的命令是进攻然后三个副官之间就开始互通信息。

1和2会互相告诉对方自己接到的命令是进攻。

1和2也会告诉3自己接到的命令是进攻。

3是叛徒他可能会告诉1和2自己接到的命令是撤退。

1从将军和2接到了进攻命令从3接到了撤退命令他只要取这三个命令中最多的进攻命令就可以了。

这样1和2都会进攻且忠诚地执行了将军的命令满足了IC1和IC2。

假设将军告诉1和2进攻告诉3撤退。

然后三个副官会如实地告诉其他两个副官自己接到的命令。

3会接到将军的撤退命令但是接到1和2的进攻命令于是3也会进攻。

这样一来三个副官都会进攻就达到了一致性IC1满足。

由于将军的命令是混乱的所以不用管将军的命令只要他们达成一致就可以了。

3m将军问题

将3m将军m叛徒问题中的将军称为阿尔巴尼亚将军3将军1叛徒中的将军称为拜占庭将军以示区分。

拜占庭指挥官代表一个阿尔巴尼亚指挥官和m-1个阿尔巴尼亚副官两个拜占庭副官分别代表m个阿尔巴尼亚副官。

因此对于拜占庭叛徒将军(代表m个阿尔巴尼亚将军)最多对应m个阿尔巴尼亚叛徒将军。

由IC1可知m个阿尔巴尼亚中尉(由单个诚实拜占庭中尉所代表)遵循相同的命令这一命令也是该诚实拜占庭节点所需要遵守的命令。

对于阿尔巴尼亚将军可知是满足IC1和IC2的又由以上对应关系可知3将军问题是满足IC1和IC2的也即3将军问题存在解。

这与已知(3将军(1叛徒)问题不存在解)矛盾故3m将军问题不存在解。

口头消息算法

每个将军都会执行某个算法来把消息传送给其他将军同时我们假设忠诚的将军会正确地执行该算法

“口头消息”可以通过如下我们为将军消息系统所做的假设来具体定义

方法介绍

由于下属们必须遵守相同的命令因此这种情况下他们必须有一个默认的命令。

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)

(2)每个下属使用他从发令者那收到的值如果没有收到则使用值RETREAT

算法OM(m)m0

(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)的值

个叛徒或者已知

的情况下每个下属都无法信任任何人因此对于每个接收到的值他们都需要使用

majority(v1,v2…vn-1)

n-2除消息上游和自己个下属发送自己接收到的信息以帮助他人做决定叛徒可以发送任何值但规定了遵守此规则这就是

m-1

n-3除消息上游上上游和自己个下属发送自己的信息帮助他人做决定

OM(0)

上面整个过程是一个递归的过程每个下属都会给其他下属发送很多信息为了使这些不同信息得以区分每个下属可以在发送消息时加上自己所属序号的前缀

正确性证明

引理1对任意m,k若系统中将军总数超过2km叛徒最多有k个算法OM(m)满足IC2即如果指挥官诚实那么每一个诚实的中尉都遵从指挥官的命令。

引理1证明

当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的以证明。

签名消息算法

其实口头消息的解决方案之所以复杂就是因为叛徒可以随意改更忠诚将军的消息而别人无法发现消息被改。

如果我们让忠诚将军的消息无法篡改那么问题就变得简单多了。

这就是签名消息的解决方案。

b任何人都可以识别将军的签名叛徒可以伪造叛徒司令的签名。

后半句是论文中的后半部分规定的。

3m1

3m1才能达成共识的限制就可以去除了。

事实上我们可以让任何数量的将军团体在存在

m2将没有意义。

因为「达成共识」意味着两个或两个以上的人只有一个忠诚将军或跟本没有忠诚将军谈不上「达成共识」。

在给出解决方案之前我们首先要定义一个函数

。

这个函数输入一个值的集合输出一个单一值。

我们对这个函数有两个要求

1.如果集合

它以去中心化的方式工作没有单一的控制中心每个节点都持有数据库的副本并能够进行验证和更新。

区块链的核心特点包括去中心化、不可篡改、透明、安全以及可追溯性。

它通过加密算法和共识机制来保证数据的安全性和可信度。

每个区块包含多个交易信息和前一个区块的哈希值形成一个不可篡改的交易记录链。

在中本聪发明比特币以前世界上并没有一个非常完美的方法来解决“拜占庭将军问题”。

工作量证明

这个工作量证明就是解决了各个将军之间可以随便发信息的问题比如3个将军都同时给对方发自己的军令那就是同时发9条军令。

而且现实情况不是复杂的多吗如果都同时发消息那早都混乱不堪了。

那中本聪就给大家定了个规矩按顺序来发令那几个将军谁也不服谁。

怎么办大家先去做算术题吧这就是所谓的哈希运算谁先算出题来谁就有资格发令这总公平吧。

假如A将军先做出算术题那么A先发。

那A先做完了数学题其他将军就停止做算数然后都在自己这里记录下来并确认A确实是最先做出算术题的那就A将军获得发出广播的资格。

并且大家重头开始做算术题还是谁做的快谁先发令如此往复。

假如叛徒B也解出来了题目B说是我先解出来的怎么办呢没关系聪哥说了咱们按解答的先后顺序给第一个解答出来的盖个章这个印章上有顺序和时间这也就是时间戳。

奖励机制

那还有了假如十多个将军某个将军最先做出算术题其他将军凭啥帮你确认和记录时间呢那这就有一个奖励机制了。

最长链原则

为了解决不同将军间可能出现的分歧区块链技术引入了“最长链原则”。

这个原则要求将军们总是选择最长的区块链作为有效链。

因为最长链需要更多的计算能力来达成所以最长链更有可能是诚实将军们达成共识的结果。

当不同的链产生时将军们会继续在自己的链上工作而最终最长的链会胜出。

这样一来即使有叛徒尝试操纵区块链他们也难以形成比诚实将军们形成的区块链更长的区块链。

换句话说在区块链的设计结构和最长链原则下如果要篡改交易作恶者必须投入大量的计算资源与整个系统中其他所有矿工进行对抗这是非常困难的一件事情特别是整个系统已经具有一定基础计算资源的情况下。

所以篡改账本需要付出的算力成本可能远远大于篡改交易获得的收益。

正常人都会把这些算力投入到正常记账中而不会拿来作恶这就避免了恶意攻击和作恶使得区块链具有不可篡改性。

总结一下区块链利用共识机制确保只有找到答案的将军才能传递决策增加了叛徒影响决策的难度。

依靠区块链结构保护历史消息不被篡改确保每个将军都能看到完整且一致的历史记录。

遵循最长链原则在出现分歧时诚实将军们可以达成一致并且叛徒难以持续地干扰共识。

通过这些机制区块链技术帮助拜占庭将军们在可能存在叛徒的情况下实现了有效的分布式协作和一致性决策。

区块链技术建立了新的信任机制允许各网络节点之间在没有权威节点的去中心化情况下达成可信共识是一项从思想到技术的重大飞跃。

拜占庭问题是为了解决由谁来发起信息并且怎么保证信息的同步和一致性。

而比特币的区块链技术则是解决了由谁来挖出区块并且让整个链上的所有区块统一的问题。

两者的问题在某些意义上可谓是一样的虽然在现实环境中有所不同可是区块链技术却为解决拜占庭难题提供了现行的最合理的方法也为后继者打开了新的思路。

所以比特币并不只是一串数字背后所用到的技术和原理解决了相当多的问题无可否认它是伟大的。

本文先详细介绍了兰波特在1982年提出的拜占庭将军问题并列举了其在论文中给出的口头消息算法和签名消息算法。

然后介绍了区块链并介绍了区块链是如何解决拜占庭将军问题的。