柚子快报邀请码778899分享：算法 拜占庭将军问题与区块链
文章目录
拜占庭将军问题问题背景问题的现实意义将军-副官模型三将军问题四将军问题3m将军问题
口头消息算法基本假设方法介绍正确性证明
签名消息算法
区块链区块链是什么区块链对于拜占庭将军问题的解决方法工作量证明奖励机制最长链原则小结
区块链的意义
总结
拜占庭将军问题
问题背景
拜占庭帝国是历史上赫赫有名的一个帝国，也就是东罗马帝国。它的首都是君士坦丁堡。但是1453年君士坦丁堡沦陷了之后，这个帝国也就灭亡了。拜占庭将军问题并不是历史上真实存在的，而是一个虚拟的问题。它是在1982年的时候，由著名的计算机大神兰波特（图灵奖获得者）提出的。
拜占庭将军问题可以这么描述：说有这么一个城堡，拜占庭帝国想进攻这个城堡，于是它就派出了很多支军队。由于通信的落后，军队之间只能通过信使来交流。城堡非常坚固，足以抵挡几支军队的进攻，但是如果所有军队同时进攻，这个城堡就会沦陷。但是问题是在军队中可能存在叛徒，这个叛徒会胡说八道。 于是他们要商量一个方法，让大家同时进攻。
问题的现实意义
计算机可以分布在世界各地，我们称之为分布式节点。这些分布式节点可能会出现故障，比如宕机；也可能会有恶意节点，比如黑客。那么在这样的情况下，我们如何才能保持那些忠诚的计算机的一致性和正确性，这就是拜占庭将军问题的意义。
究其根底，“拜占庭将军问题”最终想解决的是互联网交易、合作过程中的四个问题：信息发送的身份追溯、信息的私密性、不可伪造的签名和发送信息的规则。
将军-副官模型
我们把拜占庭问题简化一下，简化为将军-副官模型。 只考虑一个将军如何发送信息给其他将军，这种模式被称为指挥官-副官模式，我们定义发送消息的将军为指挥官，接收消息的将军为副官。在n个将军的情况下，指挥官向n-1个副官发送消息，需要满足如下条件：
IC1. 所有忠诚的副官都遵守相同的命令（一致性）
IC2. 如果将军是忠诚的，那么所有忠诚的副官必须遵守将军的命令（正确性）。
令
n
n
n表示总人数，
m
m
m表示叛徒的人数。 当
n
>
3
m
n>3m
n>3m时，该问题可解。
三将军问题
我们来看一个例子，
n
=
3
,
m
=
1
n=3,m=1
n=3,m=1。 假设将军为C（commander），两个副官分别为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
n=4,m=1
n=4,m=1。 将军为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个叛徒，而将军数小于3m+1时，该问题无解 证明(反证法)： 将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个下属发送命令。 可以证明对于3m+1或者更多个将军时，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)，m>0 (1)发令者发送他的值给每个下属 (2)对于任意i，vi代表下属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，若系统中将军总数超过2k+m，叛徒最多有k个，算法OM(m)满足IC2，即如果指挥官诚实，那么每一个诚实的中尉都遵从指挥官的命令。
引理1证明： 当m=0时，由A1可知，IC2满足； 当m>0时，在OM(m)算法的step(1)，指挥官把值传给n-1个中尉，在step(2)中，每一个诚实的中尉调用OM(m-1)，前文已知n>2k+m，因此n-1>2k+(m-1)，所以每一个诚实的中尉i都会得到城实中尉的vj=v。又因为n-1>2k+(m-1)>=2k，即这n-1个中尉的半数以上都是诚实的，所以step(3)中获得的majority(v1,v2……vn-1)必等于v，即满足IC2。
定理1 对任意m，如果将军数量大于3m且叛徒数最多是m，算法OM(m)满足IC1和IC2。
定理1证明： 当不存在叛徒(m=0)的时候，显然OM(0)满足IC1&IC2的约束，因此假定OM(m-1)成立，证明OM(m)，m>0成立。 假设指挥官诚实，由引理1可知，若k与m相等，则OM(m)满足IC2，又因为在指挥官诚实的情况下IC1可以由IC2推出，所以只需要证明在指挥官是叛徒的情况下检验是否满足IC1。 已知指挥官是叛徒，最多有m个叛徒。所以中尉中最多有m-1个叛徒。中尉的数量是3m-1，且3m-1>3(m-1),因此OM(m-1)满足IC1&IC2。对于每一个j，任意两个诚实的中尉得到的都是相同的vj的值(这任意两个中尉有一个是j的话就由IC2可以推出；若不包括j的话，由IC1可以推出)。因此，任意两个诚实的中尉最终会得到相同的v1,v2……vn-1，也即算法step(3)的majority(v1,v2……vn-1)相同，OM(m)的IC1的以证明。
签名消息算法
其实口头消息的解决方案之所以复杂，就是因为叛徒可以随意改更忠诚将军的消息，而别人无法发现消息被改。如果我们让忠诚将军的消息无法篡改，那么问题就变得简单多了。这就是签名消息的解决方案。
于是在前面的三条假设之下，我们加入第四条假设： A4（a）忠诚将军的签名是不能伪造的，内容修改可检测。（即 即使是叛徒也要原封不动的签了名将消息转发出去） （b）任何人都可以识别将军的签名，叛徒可以伪造叛徒司令的签名。（后半句是论文中的后半部分规定的）。
既然我们现在使用了消息签名，那么之前将军数量必须大于等于
3
m
+
1
3m+1
3m+1才能达成共识的限制就可以去除了。事实上，我们可以让任何数量的将军团体在存在 个叛徒的情况下达成共识（这里虽然说任意数量，但如果总数小于
m
+
2
m+2
m+2将没有意义。因为「达成共识」意味着两个或两个以上的人，只有一个忠诚将军或跟本没有忠诚将军谈不上「达成共识」）。
在给出解决方案之前，我们首先要定义一个函数 。这个函数输入一个值的集合，输出一个单一值。我们对这个函数有两个要求：
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
k k 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年提出的拜占庭将军问题，并列举了其在论文中给出的口头消息算法和签名消息算法。然后介绍了区块链，并介绍了区块链是如何解决拜占庭将军问题的。 柚子快报邀请码778899分享：算法 拜占庭将军问题与区块链 好文链接
发表评论