比特币起源

区块链技术的起源通常被简单地归因于化名中本聪的神秘天才的行为。 这种历史观常常使技术看起来近乎神奇且难以理解。 当一个人了解这些系统开发背后的实际历史时，就会增加更多的基础知识。 在本文中，我们将概述几十年来对共识算法和分布式系统的研究中最重要的主题，这些主题导致了区块链的创建。

什么是分布式系统？

分布式系统领域的先驱之一 Leslie Lamport 曾说过：

分布式系统是这样一种系统，其中一台您甚至不知道其存在的计算机发生故障可能会导致您自己的计算机无法使用。

这句话总结了为什么设计分布式系统如此困难。 系统中的每个节点都是更大网络的一部分，并且依赖于与其他节点的通信来完成一些工作。 大量的移动部件使这些系统成为最难开发的系统之一。 然而，几十年来，能够利用连接在一起的多台计算机的强大功能的好处激发了计算机科学家研究克服这些挑战的方法。

故障模型

计算机不完美，容易损坏，这是事实。 但是，对于需要高可用性的服务，比如现在的很多互联网公司，这些有缺陷的机器可能并不总是被容忍的。 想象一下，如果谷歌只在一台服务器上运行，而那台服务器必须持续运行，如果出现问题，整个谷歌就会宕机。 分布式系统最重要的动机之一是使服务更具容错性。 这意味着系统本身可以容忍某些节点的故障，但可以继续其提供的服务。

节点可能会在不同的严重级别发生故障。 故障模型从最不严重到最严重如下：

1. 崩溃失败——系统中的一个节点可能会崩溃并永远停止响应。

2.遗漏失败-系统中的一个节点可以无限延迟地回复系统中的任何消息。 就像崩溃一样，但节点仍在运行，并且可能会像往常一样传输未来的消息，可选地省略消息。

3. 拜占庭故障——节点不仅会崩溃并停止响应，还会主动错误地向不同节点发送冲突消息。 节点还可以伪造从一个节点到另一个节点的消息。 这是一个失败的模型，你不能简单地相信节点说出真相。

了解这些不同的故障模型很重要，因为并非所有协议都可以解决所有故障模型。 但是，任何管理更安全故障模型的协议都会自动管理任何更小的故障模型。

网络模型

由于分布式系统中的所有节点都必须通过网络进行通信，因此网络的特性对于系统的性能至关重要。 从最可靠到最不可靠的网络类型如下：

1. 同步——节点之间存在已知上限（我们假设消息传递通信）和节点速度差异的已知上限的网络。 基本上在同步系统中，如果消息没有及时到达，那么您可以假设发送方遇到故障（崩溃、丢失或拜占庭）。

2. 部分同步——同步和异步混合的网络。 在这个网络中，消息传递时间和节点速度之间的差异存在未知界限。

3. 异步 - 节点之间的消息传递时间没有上限且节点速度没有上限的网络。

如果一个协议被评定为在不太可靠的网络中工作，它也可能在更可靠的网络中工作。 所以，如果一个协议在异步环境中工作，那么它在所有环境中都工作，这就是为什么它被认为是协议的黄金标准。 还应该注意的是，解决不太可靠的网络模型要困难得多。

大多数没有经验的人可能认为互联网是一个连接节点的相对同步的网络。 事实上，这种假设是错误的，互联网上的节点在通信时无法保证任何形式的可靠性。 还应该注意的是，解决不太可靠的网络模型要困难得多。

状态机复制

状态机复制 (SMR) 是一个通用框架，用于通过让所有副本经历相同的确定性事件来在多个副本之间复制状态。 通过在所有服务器上运行相同的确定性事件，所有服务器都应该达到相同的状态。 这对我们今天的区块链来说可能很熟悉，Leslie Lamport 早在 1984 年就提出了这个公式。

解决 SMR 的一种方法是在网络中的节点之间达成共识。

共识概述

共识是包括区块链在内的所有分布式系统中的关键主题。 共识是描述网络中每个节点如何进入公共状态的算法。 这个问题实际上比看起来更难。 在多年的研究中，几乎没有开创性的共识证据可以指出问题的真正困难。 证据还将有助于指出一些可疑的区块链公司做出的任何潜在的“好得令人难以置信”的承诺。 虽然我不会详细说明每条证据，但我会尝试对它们包含的内容进行高层次的解释。

最重要的结果如下：

FLP 不可能 (1985)

即使存在单个崩溃故障，也没有确定性协议来解决消息传递异步系统中的共识。

这意味着协议必须是随机的，或者假设某种更强大的网络模型，以在发生任何类型的故障时解决共识。 这并不能解决更难的拜占庭故障问题。 我强烈建议您尝试在此处阅读这篇开创性论文。

CAP 定理 (1999)

分布式系统不可能提供以下 3 个保证中的 2 个以上：

一致性——每个读取请求都得到最新的写入

可用性——每个请求都会得到成功/失败的响应

分区容错 - 允许网络丢失从一个节点发送到另一个节点的任意数量的消息，并且仍然正常运行

在今天的互联网中，需要分区容忍，不能因为网络不可靠就放弃，所以必须在一致性和可用性之间做出折衷。 因此，分布式系统必须处理一致性和可用性之间的权衡。 如果协议是 100% 一致的，那么它在某些时候一定是不可用的，反之亦然。 这背后的证明非常优雅且易于理解，因此我建议您在这里阅读更多相关信息。

Lamport/Pease 结果

如果超过 1/3 的节点在同步网络中出现拜占庭故障，则无法达成共识。

这意味着要达成共识，我们需要 2/3 的节点是诚实和可用的。 您可以在此处阅读有关原始论文中证明的更多信息。 你们中的一些人可能对这个证明感到困惑，因为你们可能知道 PoW 区块链，在 51% 攻击下是安全的，这显然超过了 1/3，这是因为 PoW 区块链实际上并没有实现一致性，因为它们可以技术上被具有无限计算能力的对手回滚和改变。

这些结果将帮助我们分析所有共识技术并以我们可以检查它们提供的保证和安全性的方式构建区块链。

传统共识算法

在区块链发明之前，有一些著名的遗留共识算法被广泛使用。

帕克索斯 (1989)

最广泛使用的早期共识协议是 Paxos。 Paxos 由 Leslie Lamport 发明，在出现崩溃故障和至少有 1/2 节点未发生故障的异步网络时提供安全性。 Paxos 仅防止崩溃，这很重要，因为它要求所有节点都值得信赖（它们不应该说谎，否则它们将是拜占庭式的），这对于试图构建高可用性服务的大公司很有用。

细心的读者可能会认为我说 Paxos 在异步设置下可以承受 1/2 崩溃失败是错误的，但我之前说过，在 FLP 不可能的情况下这是不可能的。 Paxos绕过FLP的方式不是任何时候。 Paxos 需要主节点才能生存和进步，并且不能异步设置主节点选举。 所以 Paxos 需要一些同步窗口来选举 master 才能在异步设置中取得进展。 在所有执行过程中，即使在异步设置中，Paxos 也始终是安全的。

因此，考虑到 FLP 的不可能约束，Paxos 似乎是最好的，这就是为什么它可能是分布式系统研究中最值得关注的共识算法。 Paxos 始终是安全的，并且只在同步期间存活。

实用 BFT (1999)

第一个实用的拜占庭容错 (BFT) 算法是 PBFT。 它与Paxos类似，即使在异步网络下也始终是安全的，只能在弱同步下运行。

拜占庭 Paxos (2010)

原始 Paxos 的 BFT 版本，在相同网络假设下具有 1/3 拜占庭故障节点是安全的。 这是由（您可能已经猜到了）Leslie Lamport 发明的，作为他最初的 Paxos 论文的扩展。

木筏 (2014)

一种流行的现代共识算法，被认为是原始 Paxos 的更简单、更易于理解的版本。 据说它提供了与 Paxos 相当的保证和约束，同时整个协议更容易让工程师使用。

虽然分布式系统的研究取得了许多显着进步比特币的源头，但这些协议突出了当时最流行和最有影响力的作品。

现在我们在分布式系统方面有了良好的基础，我们可以开始进入区块链了！

工作量证明 (PoW) 的起源

许多人错误地认为中本聪在比特币中创造了 PoW 算法，但它实际上是 20 世纪 90 年代中期创造的一个更古老的想法。 早期被用作Hashcash的邮件反垃圾邮件算法。 Hashcash 要求发件人完成 PoW（很像比特币今天使用的算法）来发送电子邮件比特币的源头，这样垃圾邮件发送者不得不浪费更多资源来发送大量电子邮件。

但是，需要注意的是，PoW 的早期用例并不是用它来解决共识，而是用它来强迫人们做出可能耗费大量资源的行动。

比特币的起源

这就是比特币神话真正接管的地方。 传说 2008 年 10 月 31 日，一位名叫中本聪（Nakamoto）的匿名人士发布了一个针对数字货币的去中心化数字点对点系统的协议。我恳请您阅读这篇简短但精彩的论文。 虽然比特币背后的想法是革命性的，但它现在可以开始在所有其他系统的背景下变得更有意义，而不是单独存在。

比特币标志

比特币提出区块链作为同步网络中概率共识的解决方案。 它是来自拜占庭对手的 BFT，其哈希率不到总网络哈希率的 50%（这是一种与其他历史协议不同的获得安全性的方式）。 区块链的设计更注重可用性而非一致性，并且能够支持数以千计的去中心化节点。 去中心化的成本是以每秒事务数 (TPS) 衡量的低得多的吞吐量。

我将在下一篇文章中详细介绍这些保证和更多信息！

=============================

FLP论文：

有关 CAP 定理的更多信息：

Lamport/Pease 论文：

~luca/cs174/byzantine.pdf

中本聪论文：