共识经典

共识经典

时间戳记：31年2023月9日，凌晨50:XNUMX
共识经典柏拉图区块链数据智能。垂直搜索。人工智能。

编者按：a16z crypto 有一个很长的系列“枪炮”——来自我们的原创 加密经典 我们 DAO 经典 和 NFT经典 最近，我们的 零知识经典. 下面，我们现在为那些寻求理解、深入和构建的人挑选了一组资源 共识：使加密货币起作用的协议系统，确定交易的有效性和区块链的治理。

共识协议是区块链世界中正在发生的一切的核心部分。 不幸的是，文献很难掌握。 在这里，我们提供了一个链接列表，可以让您了解最新的前沿研究

我们将根据讨论的协议类型对以下链接进行分类。 不过，首先是一些通用资源的列表，这些资源对现有研究进行了很好的概述。 

一般资源

分散思想. 该博客由 Ittai Abraham 和 Kartik Nayak 运营，但也有许多来自其他领先研究人员的贡献。 它从基础开始，但您也可以找到最近论文的简单解释。 

50 页的共识. Andrew Lewis-Pye 的笔记涵盖了经典共识文献的主要结果。 此链接上的版本正在建设中，并经常更新。 另请参阅基于这些说明的 a16z 加密研讨会 (第一部分, 第二部分). 

分布式共识和区块链的基础. Elaine Shi 编写的教科书初稿。

区块链基础. Tim Roughgarden 在 YouTube 上的系列讲座。 

区块链基金会. 讲义侧重于 David Tse 的工作量证明和权益证明协议。 

定义共识

研究最多的三个共识问题是 拜占庭广播, 拜占庭协议及 状态机复制 （区块链协议解决的问题）。 有关这些问题之间关系的解释，请参阅 50 页共识（上面列出），或 Decentralized Thoughts 上的这些博客：“什么是共识？“和”状态机复制共识设立的区域办事处外，我们在美国也开设了办事处，以便我们为当地客户提供更多的支持。“

拜占庭将军问题 (1982) 由 Leslie Lamport、Robert Shostak 和 Marshall Pease 合着。
本文介绍了著名的“拜占庭将军问题”。 它仍然值得一读，但可以在其他地方找到一些证明的更好版本。 为了证明在给定公钥基础设施 (PKI) 的情况下可以解决任意数量的故障处理器的问题，可以在 Dolev 和 Strong 的论文中找到一个更简单、更有效的版本（见下文“同步”部分协议”）。 对于著名的不可能结果，即在没有 PKI 的情况下，除非少于三分之一的处理器显示拜占庭故障，否则问题无法解决，可以在 Fischer、Lynch 和 Merritt 的论文中找到更容易理解的证明（也在下文） . 

使用状态机方法实现容错服务：教程 (1990) 弗雷德·施奈德 (Fred Schneider)。
您还应该看看这篇较旧的论文，它处理状态机复制 (SMR) 的问题——区块链协议解决的问题。

以下链接根据所考虑的协议类型进行分类，从 拥有权限 协议（正如大多数经典文献中所考虑的那样）。 许可协议是那些从协议执行开始就知道所有参与者的协议。 在下面的链接中，许可协议根据消息可靠性模型进一步分类： 同步, 部分同步或 异步. 

有关这些术语的解释，请参阅：“同步、异步和部分同步”在去中心化的思想。 有关在不同模型中获得的结果的摘要，请参阅 去中心化思想备忘单.

同步协议

当消息传递可靠时，我们处于“同步”设置中，也就是说，消息总是被传递并且消息传递的最长时间存在一些有限的已知界限。 有关正式定义，请参阅上面给出的链接。 

拜占庭协议的认证算法 (1983) 丹尼·多列夫 (Danny Dolev) 和 H. 雷蒙德·斯特朗 (H. Raymond Strong)。
这里有两个重要的证据。 有证据表明，在给定公钥基础设施 (PKI) 的情况下，可以为任意数量的故障处理器解决拜占庭广播问题。 有关此的另一个说明，请参见“Dolev-强认证广播”在去中心化的思想。 也有证据表明 f+1 回合是解决拜占庭广播所必需的，如果达到 f 处理器可能有故障。 有关更简单的证明，请参见 t-弹性共识需要 t+1 轮的简单二价证明 Marcos Aguilera 和 Sam Toueg 着。 

分布式共识问题的简单不可能证明 (1986) 迈克尔·菲舍尔、南希·林奇和迈克尔·梅里特合着。
另请参阅最近的讨论，作者： 安德鲁刘易斯派伊 和 蒂姆·拉夫加登. 

拜占庭协议的信息交换界限 (1985) 由 Danny Dolev 和 Rüdiger Reischuk 执导。
没有 这 共识文献中的许多形式的不可能性证明。 这是一个重要的例子，展示了如何对解决共识问题所需发送的消息数量设置下限。 

“The Phase King Protocol”，摘自论文 比特最优分布式共识 (1992) 由 Piotr Berman、Juan Garay 和 Kenneth Perry 合着。
如果您想在没有 PKI 的同步设置中看到解决拜占庭协议的协议，这可能是最有用的。 有关清楚地解释这一点的最新博客文章，请参阅“Gradecast 镜头下的 Phase-King：一个简单的未经身份验证的同步拜占庭协议”在去中心化的思想。

部分同步协议

粗略地说，当消息传递有时可靠有时不可靠时，我们处于“部分同步”设置。 协议需要始终确保“安全”，但只需要在消息传递可靠的时间间隔内“有效”。 对此建模的标准方法是假设存在未知的“全球稳定时间”(GST)，之后消息将始终在已知时限内传递。 有关正式定义，请参阅上面框中的链接。 

存在部分同步的共识 (1988) 由辛西娅·德沃克、南希·林奇和拉里·斯托克梅耶合着。
这是介绍部分同步设置并证明许多关键结果的经典论文。 

BFT共识最新八卦 (2018) 伊桑·布赫曼、Jae Kwon 和扎科·米洛舍维奇。
如果呈现正确，Tendermint 协议（在本文中描述）非常简单，是在部分同步设置中学习状态机复制的好方法。 一个非常简单的介绍可以在 50 页的 Consensus 中找到（见上文），在 talks 中也有清晰的介绍 安德鲁刘易斯派伊 和 蒂姆·拉夫加登. 

Streamlet：教科书简化的区块链 (2020) 作者：Benjamin Chan 和 Elaine Shi。
本白皮书描述了一种专为易于教学而设计的区块链协议。 你可以在上面找到 Elaine Shi 的演讲 此处. 

Casper 友好的最终小工具 (2017) 作者：Vitalik Buterin 和 Virgil Griffith。
这是构成以太坊当前权益证明方法支柱的协议。 它本质上是 Tendermint 的“链式”版本。 有关“链接”的解释，请参阅下面列出的 Hotstuff 论文。 

HotStuff：区块链视角下的 BFT 共识 (2018) 作者：Maofan Yin、Dahlia Malkhi、Michael K. Reiter、Guy Golan Gueta 和 Ittai Abraham。
这本质上是 Facebook 的 Libra 项目（更名为 Diem）最初打算实施的协议。 与 Tendermint 相比的优势在于协议是 乐观地回应，这意味着当领导者是诚实的时，确认块可以以“网络速度”产生，即不需要花费预定的最短时间来产生每个确认块。 您还可以观看 Ittai Abraham 就此发表的演讲 此处. 

预期的线性循环同步：线性拜占庭 SMR 的缺失环节 (2020) 作者：Oded Naor 和 Idit Keidar。
本文解决了 Hotstuff 的问题，即它没有建立任何有效的“视图同步”机制。 这 新闻 Dahlia Malkhi 和 Oded Naor 对视图同步问题的工作进行了概述。 也可以看看 这个进一步优化 Andrew Lewis-Pye 和 Ittai Abraham 着。

Paxos 变得简单 (2001) 莱斯利·兰波特 (Leslie Lamport)。
如果您不想直接使用最新的区块链协议，例如 Tendermint，另一种方法是从 Paxos（不处理拜占庭故障）开始，然后转到 PBFT，这是我们列表中的下一个链接（以及哪个）。 

实用的拜占庭容错 (1999) 米格尔卡斯特罗和芭芭拉利斯科夫。
这就是经典的 PBFT 协议。 可以找到 Barbara Liskov 关于协议的精彩演讲 此处.

异步协议

在“异步”设置中，消息可以保证到达，但可能需要任何有限的时间。 有关正式定义，请参阅上面框中的链接。 

一个错误进程不可能实现分布式共识 (1985) 迈克尔·菲舍尔、南希·林奇和迈克尔·帕特森合着。
FLP 定理（以作者的名字命名）可能是关于共识协议的文献中最著名的不可能结果：即使是单个未知处理器可能出现故障，也没有确定性协议可以解决异步设置中的拜占庭协议（或 SMR）。 您可以在 Tim Roughgarden 的讲座中找到精彩的演示文稿 此处. 

“Bracha's Broadcast”首次出现在报纸上 异步拜占庭协议 (1987) 加布里埃尔·布拉查 (Gabriel Bracha)。
绕过 FLP 不可能性定理的一种方法是削弱终止要求。 Bracha 的广播是一种确定性协议，通过解决一种较弱的拜占庭广播形式在异步设置中运行，这种形式在广播发生故障时不需要终止。 虽然 Bracha 的广播首先出现在上面的论文中，但该论文还展示了如何使用广播协议借助随机性来解决拜占庭协议。 如果你只是想学习 Bracha's Broadcast，那么可以找到一个清晰的介绍 此处.

FastPay：高性能拜占庭容错结算 (2020) 由​​ Mathieu Baudet、George Danezis 和 Alberto Sonnino 执导。
本文描述了如何使用可靠广播（无需建立总序）在异步设置中实现支付系统。 

如果你真的需要在异步设置中解决拜占庭协议或 SMR，那么 FLP 结果意味着你将不得不使用某种形式的随机性。 除了 Bracha 的论文（上面列出）之外，以下两个链接是描述如何使用随机性解决拜占庭协议的文献中的经典内容： 

  1. 自由选择的另一个优势：完全异步的协议协议 (1983) 迈克尔·本·奥尔
  2. 君士坦丁堡的随机神谕：实用的异步拜占庭协议使用 加密 (2005) 克里斯蒂安·卡钦、克劳斯·库萨维和维克多·舒普

经过验证的具有最佳弹性和渐近最佳时间和文字通信的异步拜占庭协议 (2018) 由 Ittai Abraham、Dahlia Malkhi 和 Alexander Spiegelman 合着。
了解如何在异步设置中解决 SMR（和拜占庭协议）的另一种途径是跳转到上面的论文，它修改了 Hotstuff。 如果你已经了解Hotstuff，那么修改就相当简单了。 不能在异步设置中运行标准的 Hotstuff，因为在选择领导者后，对手只能拒绝来自该领导者的消息。 由于诚实方不知道领导者是否不诚实并且没有发送消息，或者领导者是否诚实但他们的消息被延迟，最终他们被迫尝试以另一种方式取得进展。 要解决这个问题，我们只需让所有各方同时担任领导者。 一旦绝大多数参与方成功完成了 Hotstuff 协议的标准“视图”，我们就会回顾性地随机选择一个领导者。 如果他们产生了一个确认块，那么我们使用那个，丢弃其余的。 

Dumbo-MVBA：最佳多值验证异步拜占庭协议，再访 (2020) 卢元、卢振良、唐强和王桂玲。
本文优化了 Abraham、Malkhi 和 Spiegelman 的前一篇论文，降低了预期的通信复杂度。 

BFT 协议的蜜獾 (2016) 作者：Andrew Miller、Yu Xia、Kyle Croman、Elaine Shi 和 Dawn Song。

寻找最佳的认证拜占庭协议 (2020) 亚历山大·斯皮格曼 (Alexander Spiegelman)。
异步协议的优点是即使消息传递不可靠，它们也能取得进展。 缺点是当网络条件良好时，通信成本不是最佳的（以各种方式）。 上面的论文解决了“我们可以在多大程度上获得两全其美”的问题。 

DAG协议

最近有一系列关于许可的基于 DAG 的协议的工作。 在这些协议中，已确认的区块集形成有向无环图，而不是线性排序。 通常，这些在异步或部分同步设置中运行。 

在这个 a16z 加密研讨会上，Andrew Lewis-Pye 给出了 概述 基于 DAG 的共识。

以下四篇论文描述了实现高效交易总排序的 DAG 协议。 DAG-Rider 在异步设置中运行，与 Cordial Miners 类似，但具有更高的延迟和更低的预期（摊销）通信复杂性。 Narwhal 是一个 mempool 协议，而 Tusk 是运行在 Narwhal 之上的 SMR 协议，在某些方面提高了 DAG-Rider 的效率。 Bullshark 与此类似，但经过优化，可以在部分同步设置中利用良好的网络条件。 

你只需要 DAG (2021) 由 Idit Keidar、Lefteris Kokoris-Kogias、Oded Naor 和 Alexander Spiegelman 执导。
这是介绍 DAG-Rider 协议的论文。 

Narwhal 和 Tusk：基于 DAG 的 Mempool 和高效的 BFT 共识 (2022) 乔治·丹尼兹、莱夫特里斯·科科里斯-科吉亚斯、阿尔贝托·桑尼诺和亚历山大·斯皮格曼。

Bullshark：DAG BFT 协议变得实用 (2022) 亚历山大·斯皮格曼、尼尔·吉里达兰、阿尔贝托·桑尼诺和莱夫特里斯·科科里斯-科吉亚斯。

Cordial 矿工：针对各种情况的基于 Blocklace 的排序共识协议 (2022) 由 Idit Keidar、Oded Naor 和 Ehud Shapiro 撰写。
一个有趣的事实是，人们实际上并不需要区块链来实施去中心化支付系统——后者是一项非常容易的任务（见 这张纸 为证明）。 在分析如何建立交易的总排序之前，上面的 Cordial Miners 论文首先描述了一个确定性（并且非常优雅）的 DAG 协议，该协议成功地在异步设置中实现了支付。 

无许可协议 

无许可协议是那些无许可进入的协议：任何人都可以自由加入达成共识的过程，参与者的集合甚至可能在协议执行期间的任何时候都是未知的。 

比特币：一个对等的电子现金系统 (2008) 中本聪。
你听说过这个。 这里还有一个 博客文章 Kartik Nayak 直观地分析了协议不同方面的需求，例如工作量证明，以及网络同步如何在协议中发挥作用。 

比特币和Cryptocurrency技术 (2016) 作者：Arvind Narayanan、Joseph Bonneau、Edward Felten、Andrew Miller 和 Steven Goldfeder。
这本教科书为刚接触该领域的人很好地介绍了比特币。 还有一个相关的 免费 Coursera 课程. 

在更技术层面上，以下三篇论文使用略有不同的建模假设分析了比特币的安全性和活性。 “比特币主干”论文最著名。 繁重的符号使其难以阅读，但证明背后的基本思想并不像最初看起来那么复杂。 Dongning Guo 和 Ling Ren 的证明解释了基本思想并且更短更简单。 

  1. 比特币骨干协议：分析与应用 (2015) 由 Juan Garay、Aggelos Kiayias 和 Nikos Leonardos 合着。
  2. 异步网络中的区块链协议分析 (2017) 由 Rafael Pass、Lior Seeman 和 Abhi Shelat 执导。
  3. 比特币的延迟安全分析变得简单 (2022) 郭东宁和任凌。

一切都是一场比赛，中本聪总是赢家 (2020) 作者：Amir Dembo、Sreeram Kannan、Ertem Nusret Tas、David Tse、Pramod Viswanath、Xuechao Wang 和 Ofer Zeitouni。
在本文中，作者对比特币进行了优雅的安全分析，该分析表明，竞相构建更长链的最明显攻击是最有效的。 该分析还扩展到 Ouroboros、SnowWhite 和 Chia（均在下面列出）。 

然后接下来的三篇论文描述了对比特币和旧的工作量证明以太坊的不同形式的攻击。 

多数还不够：比特币挖矿很脆弱 (2014) 伊泰·埃亚尔和埃敏·古恩·西勒。
这就是著名的“自私挖矿”论文。 

Eclipse 对比特币点对点网络的攻击 (2015) 伊桑·海尔曼、艾莉森·肯德勒、阿维夫·佐哈尔和莎朗·戈德堡。

对以太坊点对点网络的低资源 Eclipse 攻击 (2018) 由 Yuval Marcus、Ethan Heilman 和 Sharon Goldberg 合着。

FruitChains：一个公平的区块链 (2017) 由 Rafael Pass 和 Elaine Shi 撰写。
上述论文是对自私挖矿问题的回应。 作者描述了一个协议，使得矿工的诚实策略是一种近似均衡的形式。 

棱镜：解构区块链以接近物理极限 (2019) 作者：Vivek Bagaria、Sreeram Kannan、David Tse、Giulia Fanti 和 Pramod Viswanath。
在比特币中，区块扮演着多重角色，既用于列出交易，也用于在区块排序中达成共识。 在上面的论文中，作者将中本聪的区块链解构为其基本功能，并展示了如何构建具有高吞吐量和低延迟的工作量证明协议。

以下两篇论文展示了如何实现具有可证明保证的最长链权益证明协议。 

  1. Ouroboros：可证明安全的权益证明区块链协议 (2017) 作者：Aggelos Kiayias、Alexander Russell、Bernardo David 和 Roman Oliynykov。
  2. 白雪公主：稳健可重构的共识和可证明安全的权益证明的应用 (2019) 作者：Phil Daian、Rafael Pass 和 Elaine Shi。

Algorand：扩展加密货币的拜占庭协议 (2017) 作者：尤西·吉拉德、罗腾·赫莫、西尔维奥·米卡利、乔治斯·弗拉乔斯和尼古拉·泽尔多维奇。
本文展示了如何将经典的拜占庭容错式协议实现为权益证明协议。 这是 关于 Algorand 的谈话 西尔维奥·米卡利 (Silvio Micali)。

结合 GHOST 和 Casper (2020) 作者：Vitalik Buterin、Diego Hernandez、Thor Kamphefner、Khiem Pham、Zhi Qiao、Danny Ryan、Juhyeok Sin、Ying Wang 和 Yan X Zhang。

对权益证明以太坊的三种攻击 (2022) 卡斯帕·施瓦茨-席林、约阿希姆·诺伊、巴纳贝·蒙诺、阿迪蒂亚·阿斯冈卡尔、厄特姆·努斯雷特·塔斯和大卫·谢。
当前版本的以太坊需要更多分析。 本文描述了一些攻击。 

Chia网络区块链 (2019) 作者 Bram Cohen 和 Krzysztof Pietrzak。
本文展示了如何使用空间和时间证明构建最长链协议。

未经许可的拜占庭将军 (2021) 安德鲁·路易斯·派伊和蒂姆·拉夫加登。
在这篇论文中，作者开发了一个分析无许可协议的框架，允许人们做一些事情，比如证明无许可协议的不可能结果，并清楚地描述工作量证明和权益证明协议的一般能力. 

***

安德鲁刘易斯派伊 是伦敦经济学院的教授。 他曾在多个领域工作，包括数理逻辑、网络科学、种群遗传学和区块链。 在过去的四年里，他的研究重点一直是区块链，他的主要兴趣是共识协议和代币经济学。 你可以在推特上找到他 @安德鲁刘易斯派 .

致谢：许多 t多亏了凌忍， 伊泰·亚伯拉罕, 卡尔蒂克纳亚克, 瓦莱里娅·尼古拉连科, 亚历山大·施皮格曼及 马蒂厄·博德 有用的建议。 

***

此处表达的观点是引用的个人 AH Capital Management, LLC (“a16z”) 人员的观点，而不是 a16z 或其关联公司的观点。 此处包含的某些信息是从第三方来源获得的，包括来自 a16z 管理的基金的投资组合公司。 虽然取自被认为可靠的来源，但 a16z 并未独立验证此类信息，也不对信息的持久准确性或其对特定情况的适用性做出任何陈述。 此外，该内容可能包含第三方广告； a16z 未审查此类广告，也不认可其中包含的任何广告内容。

此内容仅供参考，不应被视为法律、商业、投资或税务建议。 您应该就这些事项咨询您自己的顾问。 对任何证券或数字资产的引用仅用于说明目的，并不构成投资建议或提供投资咨询服务的要约。 此外，本内容并非针对也不打算供任何投资者或潜在投资者使用，并且在任何情况下都不得在决定投资于 a16z 管理的任何基金时作为依据。 （投资 a16z 基金的要约仅通过私募备忘录、认购协议和任何此类基金的其他相关文件提出，并应完整阅读。）任何提及、提及或提及的投资或投资组合公司所描述的并不代表对 a16z 管理的车辆的所有投资，并且不能保证这些投资将是有利可图的，或者将来进行的其他投资将具有类似的特征或结果。 由 Andreessen Horowitz 管理的基金进行的投资清单（不包括发行人未允许 a16z 公开披露的投资以及对公开交易的数字资产的未宣布投资）可在 https://a16z.com/investments 获得/。

其中提供的图表仅供参考，在做出任何投资决定时不应依赖。 过去的表现并不预示未来的结果。 内容仅在所示日期生效。 这些材料中表达的任何预测、估计、预测、目标、前景和/或意见如有更改，恕不另行通知，并且可能与他人表达的意见不同或相反。 有关其他重要信息，请参阅 https://a16z.com/disclosures。

时间戳记：

更多来自 安德森霍洛维茨