加餐 | 拜占庭将军问题：如何基于签名消息实现作战计划的一致性？

Feb 10, 2020

加餐 | 拜占庭将军问题：如何基于签名消息实现作战计划的一致性？-极客时间



下载APP





关闭

讲堂部落提薪训练营云原生训练营架构实战营企业版极客商城兑换中心 App下载浏览器插件

渠道合作

推荐作者

加餐 | 拜占庭将军问题：如何基于签名消息实现作战计划的一致性？

2020-02-10 韩健来自北京

《分布式协议与算法实战》

课程介绍



讲述：于航

时长10:40大小9.77M



你好，我是韩健。
在01 讲中，为了不啰嗦，让你举一反三地学习，我对签名消息型拜占庭问题之解，没有详细展开，而是聚焦在最核心的点“签名约束了叛徒的作恶行为”，但从留言来看，很多同学在理解签名和如何实现作战一致性上，还是遇到了问题。比如不理解如何实现作战计划的一致性。
另外，考虑到签名消息是一些常用的拜占庭容错算法（比如 PBFT）的实现基础，很重要，所以这节课我会对签名消息型拜占庭问题之解进行补充。在今天的内容中，除了具体讲解如何基于签名消息实现作战计划的一致性之外，我还会说一说什么是签名消息。希望在帮你掌握签名消息型拜占庭问题之解的同时，还帮你吃透相关的基础知识。
当然，在学完 01 讲之后，相信你已经明白了，签名消息拜占庭问题之解，之所以能够容忍任意数量的叛徒，关键就在于通过消息的签名，约束了叛徒的作恶行为，也就是说，任何篡改和伪造忠将的消息的行为，都会被发现。
既然签名消息这么重要，那么什么是签名消息呢？
什么是签名消息？签名消息指的就是带有数字签名的消息，你可以这么理解“数字签名”：类似在纸质合同上进行签名来确认合同内容和证明身份。
在这里我想说的是，数字签名既可以证实内容的完整性，又可以确认内容的来源，实现不可抵赖性（Non-Repudiation）。既然签名消息优点那么多，那么如何实现签名消息呢？
你应该还记得密码学的学术 CP（Bob 和 Alice）吧（不记得的话也没关系，你把他们当作 2 个人就可以了），今天 Bob 要给 Alice 发送一个消息，告诉她，“我已经到北京了”，但是 Bob 希望这个消息能被 Alice 完整地接收到，内容不能被篡改或者伪造，我们一起帮 Bob 和 Alice 想想办法，看看如何实现这个消息。
首先，为了避免密钥泄露，我们推荐 Bob 和 Alice 使用非对称加密算法（比如 RSA）。也就是说，加密和解密使用不同的秘钥，在这里，Bob 持有需要安全保管的私钥，Alice 持有公开的公钥。
然后，Bob 用哈希算法（比如 MD5）对消息进行摘要，然后用私钥对摘要进行加密，生成数字签名（Signature），就像下图的样子：
图1
接着，Bob 将加密摘要和消息一起发送给 Alice：
图2
接下来，当 Alice 接收到消息和加密摘要（Signature）后，她会用自己的公钥对加密摘要（Signature）进行解密，并对消息内容进行摘要（Degist-2），然后将新获取的摘要（Degist-2）和解密后的摘要（Degist-1）进行对比，如果 2 个摘要（Digest-1 和 Digest-2）一致，就说明消息是来自 Bob 的，并且是完整的，就像下图的样子：
图3
你看，通过这种方法，Bob 的消息就能被 Alice 完整接收到了，任何篡改和伪造 Bob 消息的行为，都会因为摘要不一致，而被发现。而这个消息就是签名消息。
现在，你应该理解了什么是签名消息了吧？另外，关于在留言区提到的“为什么签名消息能约束叛将们的作恶行为？”，在这里，我再补充下，通过上面的 Bob 和 Alice 的故事，我们可以看到，在数字签名的约束下，叛将们是无法篡改和伪造忠将的消息的，因为任何篡改和伪造消息的行为都会被发现，也就是作恶的行为被约束了。也就是说，叛将这时能做“小”恶（比如，不响应消息，或者叛将们相互串通发送指定的消息）但他们无法篡改或伪造忠将的消息了。
既然数字签名约束了叛将们的作恶行为，那么苏秦怎么做才能实现作战的一致性的呢？也就是忠将们执行一致的作战计划。
如何实现作战计划的一致性？之前我已经提到了，苏秦可以通过签名消息的方式，不仅能在不增加将军人数的情况下，解决二忠一叛的难题，还能实现无论叛将数多少，忠诚的将军们始终能达成一致的作战计划。
为了方便你理解，我以二忠二叛（更复杂的叛徒作恶模型，因为叛徒们可以相互勾结串通）为例具体演示一下，是怎样实现作战计划的一致性的：
图4
需要你注意的是，4 位将军约定了一些流程来发送作战信息、执行作战指令。
第一轮：
先发送作战指令的将军，作为指挥官，其他的将军作为副官。
指挥官将他的签名的作战指令发送给每位副官。
每位副官，将从指挥官处收到的新的作战指令（也就与之前收的作战指令不同），按照顺序（比如按照首字母字典排序）放到一个盒子里。
第二轮：
除了第一轮的指挥官外，剩余的 3 位将军将分别作为指挥官，在上一轮收到的作战指令上，加上自己的签名，并转发给其他将军。
第三轮：
除了第一、二轮的指挥官外，剩余的 2 位将军将分别作为指挥官，在上一轮收到的作战指令上，加上自己的签名，并转发给其他将军。
最后，各位将军按照约定，比如使用盒子里最中间的那个指令来执行作战指令。（假设盒子中的指令为 A、B、C，那中间的指令也就是第 n /2 个命令。其中，n 为盒子里的指令数，指令从 0 开始编号，也就是 B）。
为了帮你直观地理解，如何基于签名消息实现忠将们作战计划的一致性，我来演示一下作战信息协商过程。而且我会分别以忠将和叛将先发送作战信息为例来演示，这样可以完整地演示叛将对作战计划干扰破坏的可能性。
那么忠诚的将军先发送作战信息的情况是什么呢？
为了演示方便，假设苏秦先发起带有签名的作战信息，作战指令是“进攻”。那么在第一轮作战信息协商中，苏秦向齐、楚、燕发送作战指令“进攻”。
图5
在第二轮作战信息协商中，齐、楚、燕分别作为指挥官，向另外 2 位发送作战信息“进攻”。可是楚、燕已经叛变了，但在签名的约束下，他们无法篡改和伪造忠将的消息，为了达到干扰作战计划的目的，他们俩一个选择发送消息，一个默不作声，不配合。
图6
在第三轮作战信息协商中，齐、楚分别作为指挥官，将接收到的作战信息，附加上自己的签名，并转发给另外一位（这时的叛徒燕，还是默不作声，不配合）。
图7
最终，齐收到的作战信息都是“进攻”（它收到了苏秦和楚的），按照“执行盒子最中间的指令”的约定，齐会和苏秦一起执行作战指令“进攻”，实现忠将们作战计划的一致性。
那么如果是叛徒楚先发送作战信息，干扰作战计划，结果会有所不同吗？我们来具体看一看。在第一轮作战信息协商中，楚向苏秦发送作战指令“进攻”，向齐、燕发送作战指令“撤退”。（当然还有其他的情况，这里只是选择了其中一种，其他的情况，你可以都推导着试试，看看结果是不是一样？）
图8
然后，在第二轮作战信息协商中，苏秦、齐、燕分别作为指挥官，将接收到的作战信息，附加上自己的签名，并转发给另外两位。
图9
为了达到干扰作战计划的目的，叛徒楚和燕相互勾结了。比如，燕拿到了楚的私钥，也就是燕可以伪造楚的签名，这个时候，燕为了干扰作战计划，给苏秦发送作战指令“进攻”，给齐发送作战指令却是“撤退”。
接着，在第三轮作战信息协商中，苏秦、齐、燕分别作为指挥官，将接收到的作战信息，附加上自己的签名，并转发给另外一位。
图10
最终，苏秦和齐收到的作战信息都是“撤退、进攻”，按照“执行盒子最中间的指令”的约定，苏秦、齐和燕一起执行作战指令“撤退”，实现了作战计划的一致性。也就是说，无论叛将楚和燕如何捣乱，苏秦和齐都能执行一致的作战计划，保证作战的胜利。
另外在这里，我想补充一点，签名消息的拜占庭问题之解，也是需要进行 m+1 轮（其中 m 为叛将数，所以你看，只有楚、燕是叛变的，那么就进行了三轮协商）。你也可以从另外一个角度理解：n 位将军，能容忍 (n - 2) 位叛将（只有一位忠将没有意义，因为此时不需要达成共识了）。关于这个公式，你只需要记住就好了，推导过程你可以参考论文。
最后，我想说的是，签名消息型拜占庭问题之解，解决的是忠将们如何就作战计划达成共识的问题，也就只要忠将们执行了一致的作战计划就可以了。但它不关心这个共识是什么，比如，在适合进攻的时候，忠将们可能执行的作战计划是撤退。也就是，这个算法比较理论化。
关于理论化这一点，有的同学会想知道它如何去用，在我看来呢，这个算法解决的是共识的问题，没有与实际场景结合，是很难在实际场景中落地的。在实际场景中，你可以考虑后来的改进过后的拜占庭容错算法，比如 PBFT 算法。
内容小结本节课我主要带你了解了什么签名消息，以及忠将们如何通过签名消息实现作战的一致性，我希望你明确这样几个重点：
1. 数字签名是基于非对称加密算法（比如 RSA、DSA、DH）实现的，它能防止消息的内容被篡改和消息被伪造。
2. 签名消息约束了叛徒的作恶行为，比如，叛徒可以不响应，可以相互勾结串通，但叛徒无法篡改和伪造忠将的消息。
3. 需要你注意的是，签名消息拜占庭问题之解，虽然实现了忠将们作战计划的一致性，但它不关心达成共识的结果是什么。
最后，我想说的是，签名消息、拜占庭将军问题的签名消息之解是非常经典的基础知识，影响和启发了后来的众多拜占庭容错算法（比如 PBFT），理解了本讲的内容后，你能更好地理解其他的拜占庭容错算法，以及它们如何改进的？为什么要这么改进？比如，在 PBFT 中，基于性能的考虑，大部分场景的消息采用消息认证码（MAC），只有在视图变更（View Change）等少数场景中采用了数字签名。
课堂思考我演示了在“二忠二叛”情况下，忠将们如何实现作战计划的一致性，那么你不妨推演下，在“二忠一叛”情况下，忠将们如何实现作战计划的一致性呢？欢迎在留言区分享你的看法，与我一同讨论。
最后，感谢你的阅读，如果这篇文章让你有所收获，也欢迎你将它分享给更多的朋友。

分享给需要的人，Ta购买本课程，你将得18元

生成海报并分享

赞 15

提建议

01 | 拜占庭将军问题：有叛徒的情况下，如何才能达成共识？

02 | CAP理论：分布式系统的PH试纸，用它来测酸碱度

 写留言

精选留言(41)

安排
2020-03-25
除了第一、二轮的指挥官外，剩余的 2 位将军将分别作为指挥官，在上一轮收到的作战指令上，加上自己的签名，并转发给其他将军。第一二轮不是所有人都当过指挥官了吗？为什么还会有剩余的两位将军呢？
作者回复: 加一颗星:)，执行多少轮，不是由“是否当过指挥官”决定的，而是叛将数m决定的，也就是m个叛将，需要执行m +1轮。另外，论文中的“指挥官”和“副官”，是辅助大家理解的。
共 11 条评论
19
充值一万
2021-03-16
老师好。困惑于指令序列。按照文中列子，第一轮苏秦收到指令[功]，齐收到[撤]；第二轮后苏秦[功、功、撤]，齐[撤、功、撤]，（收到其他指挥官的指令的顺序可能不一定一致，不影响最终排序）。第三轮，苏秦[功、功、撤、撤、撤]，齐[撤、功、撤、功、功]。排序后，苏秦[撤、撤、撤、功、功]，齐[撤、撤、功、功、功]，取中间的话指令不一致了。还是说指令集合是去重后排序的？
共 1 条评论
11
羽翼1982
2020-03-25
每位副官，将从指挥官处收到的新的作战指令（也就与之前收的作战指令不同），按照顺序（比如按照首字母字典排序）放到一个盒子里。 ---------------------------------- 这个排序的方法感觉不是说的很清楚，是按照命令本省的字面量（进攻 / 撤退这两个文字）的字典序进行排序吗？在上面的2忠2叛问题中，1名武将会收到 1+2+2=5条消息，这些消息如何排序，麻烦用例子说明的清晰些
展开
作者回复: 加一颗星:)，问题1，是的；问题2，需要排序的是指令，而不是消息。可以这么理解，最终所有忠诚的将军都会收到完全相同的作战指令集合，如果把这些指令按照一定的顺序进行排序，再约定执行某个位置的指令，就能保证忠将们执行一致的作战指令了。
共 5 条评论
10
Geek_8af153
2020-03-26
在楚发起的两忠两叛案例中，苏秦的盒子的第一个指令不是进攻吗？为什么变成撤退了？
作者回复: 盒子的指令要排序的，比如字典排序，因为C在J前面，所以，“撤退”排在了“进攻”前面。
共 3 条评论
8
Jowin
2021-03-09
一个简便的理解：类比http的via头字段，每个节点收到一条消息后，都在via后面追加自己的签名，并把消息转发给所有其他不在via里面的节点。最终，每一条消息，都会经过所有节点的签名。换句话说，所有节点都了解完整的决策列表。
共 3 条评论
7
Jackie
2020-12-17
https://www.zhihu.com/question/52493697/answer/1600962734 看了这篇文章，再来看本文感觉好理解多了
共 1 条评论
8
第二少
2021-09-19
> 第三轮：除了第一、二轮的指挥官外，剩余的 2 位将军将分别作为指挥官，在上一轮收到的作战指令上，加上自己的签名，并转发给其他将军。老师在这里的表述确实比较费解，其实应该从指令的角度来看更清楚：所有指令最初是由楚（图8）发出，第一轮共发出3条指令，都带上了楚的签名，其他将军接下来都只是转发这3条指令；第二轮，齐、苏、燕分别把第一轮收到的指令转发出去，并各自带上自己的签名，由于指令上已经有楚的签名了，所以不再把指令转发给楚，同时，齐、苏、燕又分别收到了两条指令；第三轮，齐、苏、燕继续转发第二轮收到的指令，同样，如果一条指令上已经有了某个签名，就不再把这条指令转发给对应的将军，比如齐在第二轮收到了【进攻：楚、苏】，就只把【进攻：楚、苏】转发给燕，而不再转发给楚、苏，燕最终收到的指令就是【进攻：楚、苏、齐】，可以看出这条指令最初由楚发出，然后依次流转到苏、齐、燕
展开
7
dakingkong
2020-07-15
实际操作时，不知道判将的数目，怎么判断是否迭代了m+1轮
作者回复: 加一颗星:)，从将军总数来反推，n个将军，能容忍(n - 2)个叛将。需要我们注意的是，这个算法是“早期经典”算法，比较理论化，很难在实际场景中落地，在实际场景中一般使用PBFT等算法。
共 2 条评论
6
Geek_8c4282
2020-10-30
老师图10没有看懂，每个将军发送其他两人的指令为什么不一致呢，我的理解是每个将军，当然除了叛将外，忠将发送的指令都是一致的，是不是画错了？
作者回复: 加一颗星:)，因为在第三轮作战信息协商中，苏秦、齐、燕分别作为指挥官，将接收到的作战信息，附加上自己的签名，并转发给另外一位，而他们接收到的消息可能是不同的，比如，齐需要将来自“楚、燕”的作战指令“撤退”转发给苏秦，需要将来自“楚、苏秦”的作战指令“进攻”转发给燕。
5
Geek_4c6cb8
2021-04-05
第三轮，“除了第一、二轮的指挥官外，剩余的 2 位将军将分别作为指挥官，在上一轮收到的作战指令上，加上自己的签名，并转发给其他将军。”结合前文的逻辑，剩余的将军数量是0，这个2是哪里来的？按照图示，第二轮齐楚之间进行了通信，所以第三轮齐楚之间就不进行通信，第二轮齐楚都没有收到燕的消息，所以第三轮齐楚都要向燕发送一次消息，是这样的吗？作者可以回复一下吗，感谢。
共 1 条评论
2
Rayjun
2022-07-14
文章中关于公钥和私钥的说法不严谨，使用私钥叫签名，此时公钥是验签，使用公钥才叫加密，此时私钥用来解密
2
Geek_201736
2020-09-21
你好，下面内容是我个人的理解，不知道是否正确。图9中苏秦指向齐的箭头应为：“进攻：楚、苏秦”而非“进攻：苏秦、楚” 图10中苏秦指向齐的箭头应为：“进攻：楚、燕、苏秦”而非“进攻：苏秦、楚、燕” 图10下面文字结论：“最终，苏秦和齐收到的作战信息都是‘撤退、进攻’”，事实上，仔细看图，发现第三轮的作战协商，苏秦收到的作战信息为： {撤退：楚、燕、齐；撤退：楚、齐、燕} 齐收到的作战信息为：{进攻：楚、苏秦，燕；进攻：楚、燕、苏秦}。而苏秦和齐发出的指令倒是“进攻”和“撤退“都包含。看了你下面的回复，是针对指令进行排序，收到的指令无法排出来“撤退、进攻”序列。请指明。如果再进行第四轮协商，苏秦都将收到“进攻”，而齐都将收到“撤退”，而且苏秦发出的指令都是”撤退“，而齐发出的指令都是进攻。另外因为非对称密钥的特性，考虑一旦指令传递链条中有忠将的私钥进行过加密，则这条指令不能再被篡改或伪造，因此指令后跟随的信息传递链条的顺序应该很重要，不可以擅自更改顺序。是不是这样描述会更准确些。由于geekbang这边，您如果不精选留言，我看不到这条留言，因此重发了一下，盼回复解惑，多谢。
展开
作者回复: 加一颗星:)，赞，思考很细致，1. 在图中没有对将军顺序在显示上做特别区分；2. 是对所有接收到指令进行排序，而不是只对一轮接收到的指令进行排序；3. 是的，消息的多轮传递链条，确保了所有忠将能最终接收到相同的指令集合。
1
Matrix
2022-12-23 来自山西
忠将的消息可以被篡改吧，只不过会被发现，只不过是签名无法被篡改。在上一讲中签名解决方案用的是叛将篡改消息后被发现，次讲又说叛将无法篡改所以一个发送，一个不发送。让人难以理解
三景页
2022-05-18
最后一幅图苏秦发给齐的换成进攻：楚燕苏秦会不会更好一些，就跟这条指令下发的顺序一致了
三景页
2022-05-17
签名消息推荐可以看掘金这个文章，会比较好理解一些：https://juejin.cn/post/6844904021925298183
惜心（伟祺）
2022-04-04
如果身体和嘴不一致问题怎么解决叛徒嘴上完全支持忠臣做法要出兵时候并不出兵或者拦截某队出兵或者同时制造信息混乱同时协商线下搞破坏
janey
2022-02-24
原文：第一轮：先发送作战指令的将军，作为指挥官，其他的将军作为副官。。。第二轮：除了第一轮的指挥官外，剩余的 3 位将军将分别作为指挥官，。。。第三轮：除了第一、二轮的指挥官外，剩余的 2 位将军将分别作为指挥官问题：第三轮“剩余的2位将军”是怎么来的？从原文描述理解这时候还有3位将军
展开
共 1 条评论
Geek_42bdf1
2021-12-02
如果真的只有两个忠将(A和B)，那么无论A从叛将那儿得到什么信息，他都会同步给B；B也会将任何信息同步给A。所以他们俩收到的信息去重排序后肯定是一样的，所以最终能达成一致。不知道我理解的是否正确？
FelixFly
2021-11-12
第二轮协商后苏秦和齐收到的作战信息都是"撤销、进攻"，就可以按照执行盒子最中间的指令了，为啥还需要第三轮协商？第三轮协商的目的何在？
LWD
2021-10-17
为了达到干扰作战计划的目的，叛徒楚和燕相互勾结了。比如，燕拿到了楚的私钥，也就是燕可以伪造楚的签名。。。这个已经违反了签名规则了吧。如果私钥都泄露了只能通过口信消息型方式才能解决。而这里有2个叛徒,4个根本解决不了吧。。看迷糊了求解惑

