在我们的 2003 SOSP“最佳论文”通过速率限制采样投票保留对等副本（也在此处，扩展版本此处）中，我们介绍了许多概念。最重要的是基于随机抽样选民的共识，这与传统的拜占庭容错 (BFT) 不同，后者在每一步都征求整个选民的选票。这种机制的优势是如此显着，以至于在 15 年后，它在区块链协议的背景下被重新发现和改进。下面我解释了我们最初的共识系统，并描述了基本思想是如何被采用和增强的。
犯错是人之常情，但要真正把事情搞砸，你需要一台电脑。匿名的
然后
唉，在现实世界中，计算机既不可靠也不能够抵御攻击。因此，当 1982 年 Leslie Lamport等人发表拜占庭将军问题时，这是计算机科学的重大进步。他们展示了一种算法，通过该算法，尽管有f个副本同时发生故障或错误， n=3f+1 个副本的系统仍能正确执行。
我们的应用是对数字学术文献的长期保存，因为图书馆已经成功地管理了几个世纪以来的纸质文献。可靠性和抗攻击性至关重要。在这种情况下，BFT 遇到了以下问题：
- 它很脆。尽管3f+1 个副本足以在f个同时发生的故障中存活在理论上是严格的，但任何实际的实现都会有一定的同时遇到F>f个故障的有限概率。一旦F个同时发生故障，整个系统的状态就无法预测，或者在我们的例子中是失败的。因此，BFT 提供了概率容错，并且不会在故障或攻击下优雅地降级。
- 它是集中的。 BFT 需要对选民的n 个成员具有可信的全球知识，随着时间的推移，这需要一个受信任的中央机构来管理和排除成员，并将这些变化传达给选民。全球图书馆社区在保存纸张方面取得成功的部分原因在于它是去中心化的；没有中央机构来确定一个机构是否是图书馆。正如我们在 2000 年的永久网络出版中所写：
图书馆的循环馆藏形成了一个模型容错的分布式系统。它被高度复制，并利用它来提供比任何单个组件都更可靠的服务。没有单点故障，没有中央控制被颠覆。副本之间的政策一致性程度较低，因此系统风险较低。当参与者为自己的当地利益采取行动并以临时、非正式的方式与其他参与者合作时，整个系统的期望行为就会出现。
- 它没有缩放。因为我们保存的内容由一些最喜欢打官司的版权所有者所有，所以我们认为任何涉及图书馆向其他图书馆提供保存服务的计划都可能最终告上法庭。重要的学术期刊有成百上千的图书馆订阅，因此我们需要一个可以扩展到数千个副本的系统。 BFT requires global communication from an elected leader node, so has overhead that rises rapidly with n .
我们总结了我们的方法：
与拜占庭容错相同……我们的投票协议在一组同行中获得了明显的普遍意见，其中一些是恶意的。有很多不同之处；我们的人口规模对于 BFT 的全球通信来说太大了，我们逐渐降级而不是掩盖故障或攻击的影响，并且由于我们不能假设恶意对等方资源的绝对上限，我们必须考虑被淹没的可能性。我们使用采样来避免全局知识或通信，使用速率限制器来防止我们的对手的无限资源快速压倒系统，并使用集成入侵检测来抢占不可恢复的故障。
图书馆的节点向自己保证其某些内容的副本与图书馆网络的共识相匹配，每个节点每隔一段时间就会选择它所知道的其他图书馆的随机子集，并邀请他们在投票中投票。为了简化，节点组对内容的哈希进行投票。为什么这是个好主意？
我们的研究模拟了三种对手的攻击；一个隐形攻击者，其目标是在不被发现的情况下改变共识，一个讨厌的对手，其目标是通过用虚假警报淹没系统来诋毁系统，以及一个类似于 DDoS 的消耗型对手，以浪费资源。由于内容的随机损坏既罕见又不相关，民意调查结果应该是双峰的；如果节点的内容是好的，滑坡协议，如果它是腐败的滑坡分歧。这些极端之间的任何民意调查结果都表明相关的损坏，这是引发警报的隐形攻击的信号。
 |
| 来源 |
假设隐形攻击者控制了许多 Sybil 节点，但为了避免发出警报，必须在这些节点不是绝大多数的投票中“正确”投票。攻击者的问题是他只知道每个投票中邀请了哪些人，而不知道总共有多少被邀请者。因此，他必须猜测在哪些民意调查中他有足够的多数赢得而不引起警报。由于改变整体共识需要快速连续赢得许多民意调查，攻击者必须多次连续猜对，这使得未被发现的成功攻击变得非常困难。示例图显示了隐身攻击的模拟。 X 轴是攻击者控制的网络节点的比例，Y 轴是攻击检测的时间，以年为单位。在这个模拟中，没有运行以成功的未被检测到的攻击为特征。请注意，攻击者控制的网络越多，就越早被发现。
- 它是有弹性的。即使有无限的资源，攻击也很难在被检测到之前成功破坏大多数节点。一旦检测到，节点管理员可以从大多数有效节点中恢复。
- 它是分散的。每个节点自主运行，与它发现的节点进行通信，因为过去它们已经与它知道的其他节点达成一致。没有分配或选举的领导者，也没有全局通信或同步。
- 它可以扩展，因为没有全局通信或同步，并且随着n的增加，每次轮询中涉及的节点比例减少。
现在
“Team Rocket ”等人声称（我的重点）：
本文介绍了一个新的共识协议系列，称为 Snow。受八卦算法的启发，这个家族通过一种有意的亚稳态机制获得了它的特性。具体来说，该系统通过重复随机抽样网络来运行，并将正确的节点引导到一个共同的结果。分析表明，这种亚稳态机制非常强大：它可以将大型网络快速移动到不可逆状态，这种不可逆性意味着网络中足够大的部分已经接受了一个提案，并且不会接受一个高于可忽略不计的冲突提案。 (ε) 概率。
……正如我们稍后讨论的那样，Snow 家族容忍成员知识的差异。相比之下，经典的共识协议需要对n的全面和准确的了解作为其安全基础。
Snow 的二次抽样投票机制有两个额外的属性，它们改进了以前的共识方法。当超过预定阈值f时，基于 quorum 的方法的安全性立即失效，而当拜占庭参与者超过f时，Snow 的概率安全保证会平稳降级。
这听起来很熟悉吗？然而，他们广泛的“相关工作”部分未能引用我们的SOSP 论文，或后来ACM Transactions on Computer Systems中的扩展版本。这就是说“火箭队”等人夸大了他们的系统有多新颖。尽管如此，很明显他们在以下领域取得了重大进展：
- 他们系统的共识是动态的，而我们的应用程序需要静态共识。
- 他们的系统在我们的应用程序需要强大的速率限制器的地方快速运行。
- 它们提供了严谨的理论分析，这是我们的论文所缺乏的。
“火箭队”等人的阐述按照一系列越来越有效的协议进行：
- 在Slush中，每个节点以与我们所做的基本相同的方式重复采样它知道的节点集。
- 在Snowflake中，节点保留状态，计算距离出现分歧的时间。这类似于我们的节点保留的状态。
- 在Snowball中，节点保留提供滞后的附加状态，这是对我们协议的重大改进。
- 在Avalanche中，他们使用 Snowball 来实现加密货币的基本功能，这是一个与我们完全不同且要求更高的应用程序。
他们标题中的“无领导者”很重要。中本聪共识实际上是一个两阶段的过程。首先是一场选举验证区块的节点的竞赛，用 Avalanche 的话来说是一个领导者，然后是一个由最长链规则驱动的扩展共识阶段，它说服不同意选举的节点加入队列。这就是为什么比特币交易在距离头部六个区块之前不应被视为最终交易。 Snowball 是一种单阶段共识协议。
请注意，这些协议都不能防御 Sybil 攻击：
包括 PBFT [ 15 ] 在内的一系列工作将 Sybil 问题与共识分开处理，这是理所当然的，因为 Sybil 控制机制不同于底层的、更复杂的协议协议。事实上，据我们所知，只有 Nakamoto 式的共识将 Sybil 预防作为其共识的一部分，通过链式工作量证明 [ 5 ] 实现，这需要矿工持续进行硬件投资。第 7 节中讨论的其他协议依赖于权益证明（通过经济论证）或权威证明（通过使系统“获得许可”的管理论证）。本文提出的共识协议可以采用任何 Sybil 控制机制，尽管权益证明与其静态操作最为一致。人们可以使用已经建立的基于权益证明的机制 [ 30 ]。
它们也不能防御我们在 TJ Giuli等人 的点对点数字保存系统的消耗防御中讨论的那种攻击。他们写道：
如果没有保护机制，攻击者可以生成大量事务并泛滥协议数据结构，从而消耗存储空间。有多种技术可以阻止此类攻击，包括网络层保护、权威证明、本地工作证明和经济机制。在 Avalanche 中，我们使用交易费用，即使攻击者将资金发送回其控制下的地址，此类攻击的成本也会很高。
当然，费用需要足够高以阻止洪水攻击；像 Avalanche 那样大大增加交易的供应量将降低每笔交易的费用，但可能不会降低洪水攻击的总成本。但请注意，Solana 区块链的竞争优势是非常低的费用，结果是：
4 月 30 日，NFT 铸造机器人开始以每秒 400 万笔交易涌入 Solana 网络，导致网络失去共识。该项目在推特上写道：“工程师仍在调查网络无法恢复的原因，验证者运营商准备重启。”网络中断了七个小时。
这并不是该网络首次表现出的不稳定性，这令其用户非常懊恼。交易泛滥是 Solana 上的一个问题，部分原因是与比特币和以太坊等网络相比交易费用较低，这些网络的汽油费相对较高，这将使泛滥变得极其昂贵。
总体而言，Avalanche 使用随机抽样、有向无环图而不是链和权益证明实现了更高效、更健壮的加密货币实施，这是一项重大成就。
原文： https://blog.dshr.org/2022/05/probabilistic-fault-tolerance.html