algorithm - 您如何缓解拜占庭 Paxos 中的提案编号溢出攻击？

Question

我最近对 ​​Paxos 进行了大量研究，但我一直想知道一件事，我没有看到任何答案，这意味着我不得不问。

Paxos 包括一个递增的提案编号(可能还有一个单独的轮次编号，具体取决于您正在阅读的论文的作者)。当然，两个想成为领导者的人可能会进行决斗，在这种情况下，每个人都试图在恶性循环中超过另一个人。但是当我在拜占庭式 P2P 环境中工作时，它让我如何应对试图将提案编号设置得非常高的提议者 - 例如，最大 32 位或 64 位字。

一个与语言无关、与平台无关的基于 Paxos 的协议(protocol)应该如何处理提案编号和/或轮数的整数最大值？尤其是故意/恶意情况，这使得溢出回 0 的模算术方法有点没有吸引力？

Answer 1

据我所读，我认为这仍然是一个未在文献中解决的悬而未决的问题。

Byzantine Proposer Fast Paxos解决拒绝服务问题，但仅限于通过与递增(提议)计数器泛洪无关的攻击来延迟消息发送的那种。

话虽如此，整数溢出可能是您遇到的最少的问题。您可能不想考虑整数溢出，而是首先考虑成员攻击(通过 DoS)。在多个节点达成共识后了解成员资格可能是一种可行的策略，但可能仍然容易受到 Sybil attacks 的攻击。在某种程度上。

另一种策略可能是合并一些 proof-of-work system限制请求泛滥的建议。然而，很难知道用什么作为衡量标准来平衡(例如，当你在比特币中挖掘区 block 链时，免费货币)。这实际上取决于您要构建的系统类型。您应该考虑系统中信息的值(value)，然后创建一个需要稍微多一点成本才能规避的工作量证明系统。

但是，一旦您有能力减慢提议计数器的速度，您仍然需要担心任何具有大量(有效)操作的系统中的整数最大值。您应该有一个数字环绕策略或多精度方案，您可以在其中清楚地确定您的网络可以运行多少年/几十年而不会遇到问题而不会破坏固定精度计数器。如果您可以确定您的系统将运行 100 年(或其他时间)而不会耗尽您的固定精度计数器，即使存在恶意实体，那么您可以选择简化事情。

另一个(重要的)注意点是，大多数论文中使用的系统模型并没有反射(reflect)使现实生活中的实现变得实用的所有内容(Raft 是一个很好的异常(exception))。如果有的话，有些作者犯了创建系统模型的罪，该模型旨在避免他们尚未找到答案的难题。所以，如果有人说 X 将解决所有问题，请注意他们只是意味着它解决了他们定义的非常具体的系统模型中的所有问题。另一方面，您应该考虑系统模型与“Y is impossible”的陈述密切相关。解释这个概念的一个很好的例子是 Ben-Or consensus algorithm 的完全异步消息传递。它在系统模型的状态机中使用不确定性来避免 FLP impossibility result 指定的限制(它指定当系统模型的状态机是确定性的时，共识需要部分异步消息传递)。

因此，在阅读了表明无法完成的证明后，您应该继续考虑“不可能”。南希林奇做了一个nice writeup关于这个概念。

我想我真正想说的是，目前还没有真正解决您的问题的好方法。如果你弄明白了，请发表它(或者如果你找到现有的论文，请告诉我)。