1. 首页
  2. 资讯
  3. 百科

分布式网络的信任难题——拜占庭将军问题

拜占庭将军问题(Byzantine Generals Problem)是由莱斯利·兰波特(Leslie Lamport)与另外两人在1982年提出的一个虚拟模型,并由此引申到计算领域,提出了分布式对等网络的通信容错问题。

1.问题描述

引用一个经典的例子,相距甚远的拜占庭将军分别率领一支军队要共同围困一座城市,将军间必须通过投票来达成一致行动(进攻或撤退)。

每位将军都将自己“进攻”或“撤退”的决定通过信使分别通知其他将军,然后每位将军根据所有的消息决定进攻还是撤退。

但是,当将军中出现“叛徒”时,情况就变复杂了。叛徒不仅可以投票给错误的决策,还可能会选择性地发送投票,叛徒的存在会影响一致性的建立。

如何在军中可能有叛徒传递错误消息的情况下,保障忠诚的将军行动一致,这就是拜占庭将军问题。

拜占庭将军问题的前提是假定消息传递的信道绝对可靠(即不存在两军问题),在这个前提下,拜占庭将军问题的实质就是“一致性”和“正确性”。

“一致性”指所有忠诚将军的行为一致;“正确性”指的是每个忠诚的将军都真实的表达了自己的消息。

2.传统解决方法

在经典场景中,解决拜占庭将军问题有两种方法,口头协议和书面协议。采用口头协议,若叛徒数少于1/3,则拜占庭将军问题可解。

使用口头协议的传递消息时,每位将军除了给其他将军传递消息, 还会将自己收到的消息分别转给其他将军,最后每位将军根据收到的所有消息选择与大多数将军的行为保持一致。使用口头协议时,不能溯源,知道有叛徒也不能确定谁是叛徒。

书面协议规定在发送消息时添加发送者的签名,伪造签名会被发现并且任何人可以验证签名的可靠性,这使得消息可以追本溯源。

采用书面协议,叛徒人数多于1/3时,拜占庭将军问题仍然有解。书面协议真正的实现需要考虑诸多问题,比如可信的签名体系等。

3.区块链解决方法

随着时代的发展和技术的完善,区块链站在巨人的肩膀上提出了拜占庭将军问题的解决方案–共识机制和非对称加密技术。

共识机制使得一段时间内只有一个节点发送消息,其他节点验证即可。由于区块链消息全网广播,故各个节点接收到的消息是一致的。(访问链接:有声阅读||分布式信仰的基础–共识机制,了解更多共识机制相关内容)

非对称加密技术保护消息内容, 同时让消息接收方确定发送方的身份。A发给B的消息通过B的公钥加密,B通过私钥解密。

若A想申明自己的身份,只需要将消息使用自己的私钥进行签名即可,B收到消息后就可以使用A的公钥验证消息的来源。

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

更多区块链信息:www.qukuaiwang.com.cn/news

声明:登载此文出于传递更多信息之目的,并不意味着赞同其观点或证实其描述。