4

我最近读了很多关于拜占庭容错的论文。有一个常见的证明是需要 3m+1 台计算机来处理 m 个拜占庭错误。一般证明是这样的：

有三个“将军”：A、B 和 C。假设将军像这样交流，其中 C 是“叛徒”：

A --> B "Attack", A --> C "Attack"
B --> A "Attack", B --> C "Attack"
C --> A "Attack", C --> B "Retreat"

A receives "Attack" from both sources, and will attack.
B receives "Attack" from A but "Retreat" from C and doesn't know what to do.
C is a traitor, so his action could be anything.

因此，我们不能保证大多数参与者会达成共识。

我有点理解这个证明，但它似乎错过了一个重点。A、B、C不也做自己的内部计算怎么办吗？由于A&B是这里的“忠诚”将军，看来“正确”的行动是进攻。在决定做什么时，不允许 B 考虑他自己的计算吗？在这种情况下，他可以轻松打破相互冲突的 A&C 输入之间的联系并决定发起攻击。然后，A&B都出击了，我们解决了问题。这是一个不同于经典拜占庭将军问题的问题吗？

4

3 回答 3

1

什么是“自己的内部计算”？这是否意味着如果一位将军有冲突消息，那么它基本上是默认选项（例如攻击）？“ （B）他自己的计算决定做什么”是什么意思？假设，B 仅在获得大部分匹配消息时才决定要做什么。好吧，冲突时可能有一个默认选项。但是默认选项并不能保证忠诚的将军之间的一致决定，因为他们彼此不信任。

拜占庭一般问题中的重要一点是他们彼此不信任，他们不知道谁忠诚与否。任何人都可能是叛徒，所以即使A和B都是忠诚的将军，他们也不知道他们每个人都是真正的忠诚将军在A或B方面。那样的话，即使B在B得到时进行自己的内部计算来自 A 和 C 的冲突消息，它不能 100% 确定正确的决定（A 和 B 执行相同的操作）。

于 2018-02-13T05:22:33.977 回答
0

您所描述的是三向共识，所有参与者都可以有自己的意见。拜占庭将军问题包括一个将军向其他将军发送命令。所有忠诚的将军都必须作为一个整体，要么服从，要么不服从命令。这是确保每个人都同意指挥官所说的话的问题。

这是一个例子：

首先，成为指挥官或拜占庭将军很容易；你不在乎别人怎么想。困难的部分是成为一名忠诚的将军，从别人那里得到命令。

对于试图决定是否应该进攻的 3 位将军，我们有两种可能的情况：

  • 如果指挥官是拜占庭将军，它可以向两位将军发出不同的命令。然后他们不能同意，因为他们从指挥官那里得到了不同的信息，最终得到了相同数量的赞成票和反对票。
  • 如果拜占庭将军不是指挥官，它可以谎报从指挥官那里得到的命令。忠诚的将军再次获得一票（来自指挥官）和一票反对（因为拜占庭将军撒谎）。

既然你这个忠诚的将军不知道指挥官实际上对对方将军说了什么，你也不知道指挥官是否对你撒谎，或者对方将军是否撒谎。

于 2016-04-02T19:28:55.917 回答
0

通常假设忠诚的将军会在相同的问题下给您相同的答案。即，A 和 B 都将返回“攻击”或“撤退”。但在 BFT 场景中情况并非如此。在 BFT 中，每个忠诚的将军看到问题的不同部分，因此可以给出不同的答案。因此，一个忠诚的将军可以说“进攻”，而另一个忠诚的将军可以说“撤退”。

一个很好的用例是飞机的高度传感器。每个人都可以给你不同的答案，因为他们“看到”不同的数据（它们都位于不同的地方，受不同因素的影响）。

引用原始论文（Lamport，1982）：

使用多数表决来实现可靠性是基于所有无故障处理器将产生相同输出的假设。只要他们都使用相同的输入，这是正确的。然而，任何单个输入数据都来自单个物理组件——例如，来自可靠计算机中的某些其他电路，或来自导弹防御系统中的某个雷达站点——并且发生故障的组件可以为不同的处理器提供不同的值。

投票系统在这里不起作用，因为有缺陷的组件可以通过向忠诚的将军发送相互冲突的信息来欺骗他们。换句话说，C（恶意）可以向 B 发送“攻击”，向 A 发送“撤退”。

假设 B（忠诚）说“撤退”（其他一切都一样）：

A --> B "Attack",  A --> C "Attack"
B --> A "Retreat", B --> C "Retreat"
C --> A "Attack",  C --> B "Retreat"

在这个例子中，他们不应该做任何事情（因为他们不同意），但是 A 会进攻，B 会撤退。诚实的节点认为他们达成了协议，但他们没有。在这种情况下，叛徒C成功地欺骗了诚实的A和B将军。

附带说明一下，如果您处于诚实组件应该给您相同答案的情况下，那么可以使用投票系统（正如 Lamport 本人在他的论文中所建议的那样）。例如，您可以在 RAID 系统上使用它，其中每个节点都有相同的数据——您需要做的就是使用大多数返回的作为实际数据。

于 2019-03-23T23:16:02.347 回答