欢迎各位的到来,匿名科技专业开发区块链项目,为您定制专业的区块链解决方案!
当前位置: > 认识区块链 > 正文

拜占庭将军问题(Byzantine failures)

2019-03-12 16:02:36 认识区块链

拜占庭将军问题(Byzantine failures),是由莱斯利·兰伯特提出的点对点通信中的基本问题。含义是在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。因此对一致性的研究一般假设信道是可靠的,或不存在本问题。

拜占庭将军问题起源

拜占庭位于如今的土耳其的伊斯坦布尔,是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔,为了防御目的,因此每个军队都分隔很远,将军与将军之间只能靠信差传消息。 在战争的时候,拜占庭军队内所有将军和副官必须达成一致的共识,决定是否有赢的机会才去攻打敌人的阵营。但是,在军队内有可能存有叛徒和敌军的间谍,左右将军们的决定又扰乱整体军队的秩序。在进行共识时,结果并不代表大多数人的意见。这时候,在已知有成员谋反的情况下,其余忠诚的将军在不受叛徒的影响下如何达成一致的协议,拜占庭问题就此形成。

在拜占庭问题里,各邻国最重要的事情是:所有将军如何能过达成共识去攻打拜占庭帝国。

达成共识并非坐下来开个会那么简单,有的将军心机深不可测,口是心非,如果有叛徒,可能会出现各种问题:

1.叛徒可能欺骗某些将军自己将采取进攻行动。

2.叛徒可能怂恿其他将军行动。

3.叛徒可能迷惑其他将军,使他们接受不一致的信息,从而感到迷惑。

针对拜占庭问题的深入研究,科学家们得出一个结论:如果叛徒的数量大于或等于1/3,拜占庭问题不可解。

解释过程可以用一个副官模型来解释:

1.假设只有3个人,A、B、C,三人中如果其中一个是叛徒。当A发出进攻命令时,B如果是叛徒,他可能告诉C,他收到的是“撤退”的命令。这时C收到一个“进攻”,一个“撤退“,于是C被信息迷惑,而无所适从。

2.如果A是叛徒。他告诉B“进攻”,告诉C“撤退”。当C告诉B,他收到“撤退”命令时,B由于收到了司令“进攻”的命令,而无法与C保持一致。

正由于上述原因,在只有三个角色的系统中,只要有一个是叛徒,即叛徒数等于1/3,拜占庭问题便不可解。

当然,只要叛徒数小于1/3,问题还是可解的。

科学家们提出了口头信息方案和书面协议两个方案。

解决方案一:用口头信息

口头信息即使将军们派人用口信传达消息,口头传达消息的实际含义指的是

1.每个被发送的消息都能够被正确投递

2.信息接受者知道消息是谁发的

3.沉默(不发消息)可以被检测

这种口头协议的算法也存在明显的缺点:口头协议并不会告知消息的上一个来源是谁,也就是消息不可追根溯源,出现信息不一致也很难找到叛徒在哪。

解决方案二:用书面协议

可以假设10个国家,每个国家都可以派人向各个国家派信,比如一起约定 “某天早上六点,大家一起进攻拜占庭,同意就签个字”。收到信的国家如果同意的话,就可以在原信上签名盖章。

书面协议相比口头协议,实际说的是在这个多人的将军模型中加了了个隐含条件:

1.将军们能够使用签名技术,签名不可伪造,一旦篡改即可发现。

2.同时任何人都可以验证签名的可靠性。

书面协议相比口头协议,所有的消息都是有记录的,解决了追根溯源的问题。

但在现实中仍然可能面临各种问题:

中世纪的邻邦之间沟通只能靠信使骑马,将军们互不信任,也不可能亲自聚在一起开会,物理距离导致信息传输延迟。

真正可信的签名体系难以实现。签名造假的问题也没法避免。

签名消息记录的保存难以摆脱中心化的机构。

终极解决方案:区块链技术

互联网的存在,首先降低了信息的流通成本。每个将军配一台电脑,就解决了”书面协议“中骑马通讯造成时间延迟的问题。

如果10个将军中的几个同时发起消息,势必会造成系统的混乱,造成各说各的攻击时间方案,行动难以一致。

谁都可以发起进攻的信息,但由谁来发出呢?中本聪巧妙地在个系统加入了发送信息的成本,即:一段时间内只有一个节点可以传播信息。
 

它加入的成本就是”工作量“——节点必须完成一个计算工作才能向各城邦传播消息,当然,谁第一个完成工作,谁才能传播消息。

当某个节点发出统一进攻的消息后,各个节点收到发起者的消息必须签名盖章,确认各自的身份。中本聪在这里引用现代加密技术为这个信息签名。

这种加密技术——非对称加密完全可以解决古代难以解决的签名问题:

1.消息传送的私密性

2.能够确认身份

3.签名不可伪造、篡改

非对称加密算法的加密和解密使用不同的两个密钥.这两个密钥就是我们经常听到的"公开密钥"(公钥)和"私有密钥"(私钥).

公钥和私钥一般成对出现, 如果消息使用公钥加密,那么需要该公钥对应的私钥才能解密; 同样,如果消息使用私钥加密,那么需要该私钥对应的公钥才能解密.

非对称加密的作用是:保护消息内容, 并且让消息接收方确定发送方的身份.

由此,一个不可信的分布式网络变成了一个可信的网络,所有的参与者可以在某件事在达成一致。

 

比特币的工作机制,POW(proof of work)工作量证明。工作量证明系统主要特征是众多参与节点需要做一定难度的工作得出一个结果,谁先得出立即全网广播,其他节点很容易通过结果来检查出之前节点是不是做了相应的工作,一旦结果被证明正确,其他节点会把之前节点的结果添加到各自的账单中,为争取下一笔的交易记录做好计算的准备。