算法共识

markdown 2022年8月31日

2

1

没有区块链技术和中本聪在Nakamoto协议上的创新工作， cryptocurrencies 将不存在。区块链基本上是一种分布式账本技术（DLT或复制日志技术或RJT）。这些东西是什么，它们是如何工作的！？这些缩写难道只是掩饰我们几乎没有魅力的事实吗？

继续阅读，了解这项创新技术的整体概述，重点关注它们的共识机制。在某些点被简单概述得很稀疏，但是这是入门级内容，请见谅！享受吧，伙计们☕

订阅

分布式账本技术

不过是用来描述一种在网络中共享数据给不同节点的系统。

DLT 是一个系统/协议，它是在网络中的参与系统之间同时复制的数字数据（通常不受地理限制），并且在没有单个故障点的情况下进行。这些本质上是基于共识算法运作的点对点（p2p）网络，以确保信息的完全复制按时完成，并在人为干预的过程中达到最小。

网络状态的复制和更新是在参与系统中独立发生的，参与者通过预设的正确多数/诚实少数模型就网络值的正确性达成共识。

关于谁可以导致网络状态更新，DLTs 可能是有权限的或无权限的。

• 有权限的 DLT 是受到审查的，需要已知管理员的批准，才能允许新节点加入或现有节点能够读取或写入网络。因此，这些网络的安全性是由管理员的存在所保证的。这类网络的例子包括供应链和银行链。

• 无权限的 DLT 是开放给任何希望加入的人的，无论位置和身份。然而，进入和参与是受到预设算法的限制和管理的，这虽允许假名和去中心化，但会引入安全成本函数。它们是通过加密密钥、成本与哈希函数以及不同迭代中的博弈论假设来保护的。这类网络最著名的例子是 cryptocurrencies。

关于 cryptocurrencies 的无权限 DLT 可以有两种形式：

1. 区块链

2. 有向无环图（DAG）。

区块链：

是一种消息复制系统，由各种子系统组成，合作以确保其假定的特性得以维护。数据在上下文中被称为交易，存储在一个“块”中，该块位于一个去中心化的数据库上，由 p2p 网络中的参与者管理。 这些网络由在互联网覆盖下的不同协议集之间运作的节点/对等方维持。

区块链中存在的子系统依赖于其预期的用例，构成其架构。根据其架构，区块链可分为：

• 单体区块链堆栈，包含其能够独立正常运作所需的所有子系统。

• 模块化区块链堆栈，至少将一个必需的子系统外包给另一个区块链系统以实现适当功能。

典型单体区块链中存在的子系统/方面/层次为：

• 网络层，由对等协议和共识协议组成。它决定节点如何彼此通信，以及在存在或不存在威胁网络的故障时，如何独立达成统一决策。

• 数据（可用性）层，负责维护稳定、结构良好、符合网络有效性规则的交易与块的账本，该账本在网络参与节点之间被复制。

• 执行层，负责将构建在区块链之上的终端用户应用程序连接到数据层并执行特定应用命令。

在模块化区块链中，一种额外的子系统称为结算层，属于其堆栈的一部分，负责为区块链提供替代执行层（我知道这一点过于简化而略过了）以及其他功能。

块是包含在区块链中的数据容器，它们串联链接以形成区块链。每个区块都有一个“头”，其中包含三个不同部分：

1. 前一个区块的哈希，实际上它作为任何两个区块之间的链接，并且在除创世区块之外的所有区块中都有。

2. 区块的哈希，其中包含时间戳、随机数（nonce）和难度；即它包含区块形成时的条件。

3. Merkle 树，由 merkle 根哈希表示，是包含在区块中的所有交易的摘要。

Merkle 树是使用哈希函数（通常是 SHA256）进行数据验证的结构，通过成对数据来防止模糊和拥挤，同时保持可证明的完整性。它们包含三部分：

1. 叶节点，这些是包含在区块中的每笔交易的交易哈希（txid），它们包含交易的详细信息。

2. 非叶（分支）节点，这些通常开始时是两个先前叶节点的哈希值，即将两个先前交易哈希值哈希在一起以生成非叶节点。这个过程会对区块中的每笔交易及生成的非叶节点重复进行，直到剩下两个哈希值。

3. Merkle 根/根哈希，这是最后两个非叶节点值的哈希。它是所有包含在区块中的交易的唯一哈希，并可用于识别和验证交易 ID（txids）。

随机数据被 Merkle 化

有向无环图：

缩写为 DAG，又称为无环有向图，是一种没有循环的有向图。它们通常展示多个数据项（在上下文中称为顶点）之间的关系假设，这些假设以有向线条（←/→）的形式表现，从一个顶点指向另一个，称为边或弧。因此，可以说 DAG 是一种数据建模工具，具有两个组成部分；顶点是相关的数据项，边则显示了顶点之间的有向关系，以非二进制的方向将它们连接起来，使得没有顶点能够通过非平凡路径返回自己。

一个简单的 DAG 示例是没有谱系崩溃的家谱树。因为没有人可以是自己的祖先，顶点可以表示每个家庭成员，边显示父母与子女的关系。

在去中心化网络共识的背景下，虽然 DAG 不是一个非常流行的选择，但若愿意忽视中心化的风险，高效性、可扩展性和费用相对区块链是更具理论性（迄今为止）。在这种情况下，顶点是必须基于前馈、有效但未确认交易（称为 tips）构建的交易，选择算法可导致链接交易的确认，并避免网络垃圾邮件，同时便于后续交易确认的新交易。这个过程不断循环。针对 tip/父级选择，存在各种通用算法，包括：

• 均匀随机提示选择，其中进入的交易选择至少两个随机提示进行确认和构建。看似简单而优雅，但交易速率并不恒定，因此可能导致提示被忽视的时间超过正常时间。

当交易速率过高时，即网络比平常更忙，进入的交易可能会直接链接到创始交易，而忽略彼此及其他已存在的提示。当交易速率过低时，就会发生“链式反应”，其中进入的交易只基于一个提示构建，而不是多个，因此呈现出区块链的特征。

• 无加权随机游走提示选择方案，其中从创世节点实施“游走”算法，其功能是“指向”进入的交易，使其构建在以相等权重概率选择的提示上。交易的权重指的是有多少其他交易直接或间接地在其上构建。

该方案的问题在于懒惰姑姑。懒惰提示是建立在先前确认的交易上而非最近交易上，导致账本保持相对滞后。

• 加权随机游走方案，维护大部分无加权方案的特性，但考虑提示的权重，以促使不创建和不构建懒惰提示，同时保持随机游走特性，以防止“过重”游走，导致每个进入的交易仅在最重的可用提示上构建，导致大量尚未批准和被忽视的提示。

分布式网络中的容错与网络层

在典型的分布式网络中，客户端向节点网络发送操作请求，这些节点应能提供及时且正确的响应，而无须关注单个节点的故障。为了达成响应值的一致性，一组节点——可以互相通信——各自从一组值中独立抽取特定值，所有正确/诚实的节点必须在每个初始值上独立得出相同的最终值。这个过程由一组在网络中用于通信的对等协议和达成一致的共识协议连同称为共识机制或原子广播协议所管理。

在分布式系统中对等/共识协议的需求源于需要在持有账本副本的多个节点之间提供故障恢复能力。因此，共识机制的主要目标是确保所有参与者维护相同的分布式账本，同时隐式保证此类网络的容错和安全性。

共识协议不是为了防止恶意行为者而实施的，它们只广播一致性，即所有组件必须接收相同的消息，你就安全了。因此，在此情况下，共识主要指多数无故障节点就一个值达成一致，无论是对抗性的还是良性的。共识协议中的有效性规则因此被称为在所有节点上是确定性的，并且是统一的，以便单个节点不能提出构成有效消息的内容。

共识协议的通用特性包括；

• 活跃性，即来自正确客户端（网络用户）的请求/消息必须最终被处理。这类请求必须是有效的（节点广播的信息必须根据共识按顺序排列），所有诚实节点必须在消息值上达成一致。

• 一致性，即当一个诚实节点决定一个值的正确性时，所有其他诚实节点也必须得出相同的决定。一致的系统必须保证完整性（消息传递必须仅发生一次）和总顺序（所有诚实节点必须对所有传递的消息提取相同的顺序）。

在分布式网络中，这两个特性之间进行权衡，以容忍短暂的分区/分叉，而不导致网络故障。

共识协议包含使参与节点能在正常条件下和故障情况下如何运作的通信和失败过程。

• 通信过程可以是同步、部分同步或异步。

• 失败过程可以是崩溃故障或拜占庭故障模型。

网络同步是存在于网络所有过程之间的协作水平；它也可以指节点之间如何相互通信。网络同步主要有三种形式：

1. 同步网络，在这种网络中，过程完成始终按规定时间约束不断协调进行。即参与节点之间的消息传递在已知固定延迟内得以保证。

2. 部分同步网络，在这种网络中，过程松散地协调，拥有一个大致共同的时间概念，导致在不确定延迟后保证消息传递，即交付时间是变量，毕竟交付是确定的。部分同步网络有两种形式：

• 弱同步网络要求随着时间的推移，网络中消息传递的时间必须不断减少。即消息传递时间有固定的界限，但仅在事后得知。

• 最终同步网络确保在经过一段不确定的时间后，产生固定延迟的消息交付，即消息传递的固定界限存在，但仅在经过某个未知时间后开始成立。

在适当的时间范围内，部分同步网络的过程执行方式与同步网络的过程极为相似。

3. 异步网络，其中过程几乎不协同，没有消息传递的延迟保证，因为缺乏时间的共同概念。在这种网络中，如发生单一故障就很难保证达成共识。这被称为“FLP 不可能性”，通常通过随机决策和放松/概率过程终止来克服。

在分布式系统的节点中，故障/失败可能以不同形式出现，影响网络的攻击恢复能力并导致异常。它是一种特殊情况，因为在这样的网络中，每个节点既被视为服务器又被视为客户端，相对于传统架构。故障可能是：

• 崩溃故障，当节点正确地执行协议指令但随时可能停止并永不重启时发生。它大多由于拒绝服务攻击或突然断电引起。

• 拜占庭故障，会导致节点的任意和恶意行为，通常被认为是最需要绕过的故障，因为容忍拜占庭故障意味着也要容忍崩溃故障。它多是由于对硬件或软件的敌对影响造成的。

对等协议和数据传播在分布式网络中：

如前所述，保存在分布式网络上的数据并没有特定的“来源”，它负责确保数据的有效性和完整性，而是由所有维护链副本的节点共同处理这个函数。

在典型的区块链网络中，对等/节点可以承担两个主要角色，涉及交易验证和状态转换：

• 区块生产/主节点，也称为矿工（质押者），他们负责确保来自网络用户的请求符合区块链的有效性约束。如果符合，他们会批准这些请求并将其与其他有效请求放在区块中，将其传递给其他区块生产和合格的非区块生产节点，后者会重新检查其有效性。共识节点可以通过忽略/审查无效交易和区块来防止恶意行为。

• 非区块生产节点；其他网络用户，进一步分为两个小组：

1. 完全节点，也称为验证者，拥有本地复制的网络状态。他们通常负责在网络中聚合和传播交易及区块。它们可以执行矿工的所有其他功能，但无法生成区块。他们仅传播区块链的有效状态，因此能够通过忽略无效的状态转移来对抗区块生产者的恶意行为。

2. 轻节点/客户端节点，仅能读取区块链上的有限数据项（区块头和大多数情况下的少量交易），因此无法完全参与网络验证过程。

多个参与节点相互贡献不同部分的故事（来自不同客户端的交易），形成共享的完整图景。该过程被称为流行病传播，因为网络的所有组件都是潜在的信息和数据传播者。每个合格的组件随机选择其对等方的一个子集，并反复地向他们转发新数据，直到满足预定义条件。

分布式系统中的传播指的是在多个网络对等方之间概率性地交换数据的重复过程。这是一个无穷无尽的过程，不断随机选择网络中的其他成员，并持续在彼此之间交换网络更新，以数据集的形式进行。

传播协议在聚合位于网络中不同节点的不同数据子集时非常有用。数据传播、聚合和查询由每个合格的非故障网络节点执行，导致网络中的共享状态。

传播协议可以基于以下任何一种通用模型：

• “感染与消亡”模型，其中在网络中获得新消息的节点只与其对等方的一个子集共享一次，然后保持沉默，直到再次引入新消息。

• “永远感染”模型，其中节点在网络中不断重复地将新消息转发给其对等方，直到满足某些停止标准。

传播协议通常由三个组件组成，可以根据网络情况定制：

a) 对等选择：节点必须选择其他节点进行连接并共享数据。不同的协议假设不同的对等抽样服务，以允许节点从其他节点的池中均匀随机选择。

b) 数据交换：此组件决定节点可以与其对等方共享何种类型的数据。通常，区块链网络中的节点共享应用数据（交易和网络状态），但它们也可以共享与其匹配的其他节点的引用，从而增强网络的传播和拓扑。

c) 数据处理：这决定节点对接收到数据的处理方式。通常，节点更新其本地状态，并将数据重新广播给其他节点；在特殊情况下，它们还可以在网络中与其他对等方建立新连接。

通用共识协议和拜占庭容错实现：

拜占庭故障是在分布式计算系统的网络中存在的交互不一致条件，其中组件存在故障或错误信息的可能性，这可能对整个网络产生影响。它是通过拜占庭将军的寓言广为流传的，这个寓言讲述了五位军将围攻一个城镇，必须在任何时刻一起进攻或撤退以确保胜利。然而，他们处于不同的位置，无法直接进行计划沟通（没有 WiFi 的生活真是糟糕），而是利用相对值得信赖的信使。 这呈现出各种风险向量，概括如下：

• 个别将军的恶意

• 信使的恶意

将这一寓言映射到分布式网络中，将军是节点，信使是统一的通信模型。拜占庭故障通常会向不同观察者呈现出不同的症状，即一个拜占庭节点可能在其部分对等方看来是活动的，在另一些部分看来又是失活的。

拜占庭容错是分布式网络的预定义特性，它使得能够预防或恢复拜占庭故障和失败；多以共识机制的形式存在，它包含了网络中节点的通信和故障模型。拜占庭容错网络暗含崩溃故障的容忍能力。

无权限区块链的共识机制通常由多个组件构成：

1. 区块提案/生产系统- 决定区块应如何生成以及应如何附加可验证的有效性证明，以防止网络垃圾邮件。区块提案方案包括工作量证明、权益证明、权威证明等。

2. 信息/区块传播- 决定有效区块及其内容如何向其他网络参与者广播。例如，多播和传播方案。

3. 区块验证- 该方案负责验证区块生成证明，并确保网络消息的有效性。

4. 区块终结- 该组成部分决定网络参与者如何在存在多个正确但相互矛盾的结果的情况下达成一致。例如，GHOST、最长链规则、拜占庭协议等。

5. 激励机制- 一个非常重要的组成部分，确保网络参与者的诚实参与，并发放网络代币。

区块生产通常由一个共识节点或一个共识节点委员会在每个区块纪元中领导。这些领导者被奖励以解析一个区块并将其传播给其他合格节点进行验证。纪元区块生产通过两种技术建立。

A. 抽签技术，在这种技术中，纪元领导者的选择基于运气和概率。 使用这种技术的协议被称为“资源证明”协议，因为它们固有要求节点应该在（大多数情况下）外部相对稀缺且昂贵的资源上花费相当多的时间，才能成为纪元领导者。大多数 PoR 协议是基于比特币中实现的中本聪协议的，因此只能保证账本条目的概率最终性。这些协议的例子包括工作量证明、可检索性证明、烧毁证明等。

• 工作量证明：最初于1993年提出，作为防止网络垃圾邮件的密码学证明。它通过证明其他人已经在尝试通过网络发送消息时耗费了一定阈值的可验证计算能力来实现这一点。中本聪通过比特币的实施，将其作为无权限去中心化网络的共识模型而被推广，结合了三大核心特性：

- 一个点对点网络框架

- 一个密码学安全的数据账本结构

- POW 要求来验证通用账本的条目

工作量证明系统通常耗能较高，能耗效率相对较低，因为它仅验证共识，即 POW 算法并不关心计算难题的结果，它们旨在通过增加成本的方式来阻止数据操纵，使之几乎不可能但在理论上可能。这种密码学难题的解决所消耗的计算力通常与成功的概率成正比。然而，也有可能幸运地获得比实际付出要少的解法。验证 POW 难题的解决方案与其解决难题一样简单。

• 中本聪共识协议，即“工作量证明"，基本上总结了比特币的工作原理。它是一个基于解法验证的 PoW 协议，其中块通过工作量证明机制提案，利用强大的哈希函数进行设置，使哈希结果满足一个根据预设区块间隔算法调整的难度目标。挖矿区块通过基于广告的传播而传播。

当收到并验证一个新区块时，节点将其广告给它的对等方，他们请求该区块以扩展自己的本地账本副本。该过程持续进行，直到所有非故障节点获得该区块。

区块验证受制于严格的规则，要求在广播给对等节点之前和在附加到区块链之前，对区块及其内容进行有效性验证。有效性检查包括双重支出检查和区块头的工作量证明有效性检查。

区块最终的规则是“最长链规则”，即挖矿应始终扩展已存在的最长链。实际上，带有最多累积证明的链被延伸，因为可能积累更多证明而且可能更短。

对被认为有效的区块，节点授予激励，以 coinbase 交易的形式转给自己和区块交易费用。

中本聪协议的最终性具有概率性质，就像所有其他 PoR 协议一样。

概率最终性是指之前接受的区块及其内容可能会被网络丢弃，但随着区块链规模的扩大，丢弃的概率将会成指数性降低。由于这一特性，该协议仅能实现最终的抵御双重支出能力。这也有助于协议规避 >⅓ 故障节点的拜占庭容错阈值，允许在区块链分叉情况下存在相互矛盾的结果，前提是最终会被诚实的多数修剪掉。

B. 投票技术，合格的网络参与者通过投票选择纪元区块生产者，基于他们在网络中的股份。这种股份通常以固定期限内锁定的网络代币的形式存在。此类技术通常压力较小，也更省电。

投票为基础的协议的主要形式有 BFT 协议和 PoS 协议。

• 拜占庭容错协议是基于投票的共识协议，利用拜占庭协议和状态机复制实现区块链网络的共识。经典的 BFT 实现最适合于有权限和半有权限的区块链。BFT 协议的例子包括 pBFT 和 rBFT。

• 实用拜占庭容错协议（pBFT）利用密码算法（哈希、签名等）确保在一个去中心化网络中的 3f+1 个节点中，f 为网络中的节点数量，当至少有 2f+1 个节点运行正常时，可以实现共识。这是基于多数规则，因为一旦其中两种或多种结果中的一种领先于其他结果，其他节点必须执行领先的过程，无论之前的立场如何。

在 pBFT 系统中的共识过程涉及两个节点/角色：

a) 主节点，负责事务序列化、区块提案、传播和最终确定。每个共识过程中只有一个这样的节点。

b) 复制节点，接收传播的区块，通过投票验证它们，并参与最终确定。

客户端节点是初始化节点，即负责向网络发送事务请求的节点。

pBFT 共识在三个阶段中进行：

a) 预准备阶段：在主节点中进行。该节点接收并验证客户端请求，生成相应的预准备消息并将其广播到所有复制节点。

b) 准备阶段：在这一阶段，复制节点验证收到的预准备消息的合法性，并向其他复制节点和主节点广播相应的准备消息。当任何一个节点收集到 2f+1 个准备消息时，它就广播一个提交消息，表明它已准备好进行区块提交。

c) 提交阶段：各节点相互发送提交消息，当任何一个节点收集到 2f+1 个提交消息时，它处理原始客户端请求并更新网络以反映这一变化。

这些阶段必须在规定的时间限制内完成，否则数据将被拒绝，网络保持其原始状态。如果发生这种情况，视图更改协议会被触发，以重新评估提交的数据集，并尝试再次达成共识。

视图更改协议确保网络保持活跃和安全，即确保网络的活跃性。

• 权益证明最初是由比特币社区于2011年提出，作为工作量证明的能源高效替代方案。股份是指参与者拥有的网络代币，这些代币被委托给共识过程并锁定在智能合约中。该系统利用代币所有权来缓解Sybil攻击，同时将机会成本从网络外部（计算能力损失）转移到系统内部（资本损失）。PoS 协议在某种程度上与 PoR 协议相似，因为它们需要“证明”，在这里是通过拥有锁定在智能合约中的原生代币来证明对区块链成功的承诺，并通常获得利息。

PoS 协议目前基本上都是与其他一种协议联合实现最终性。

• PoS-PoW 协议的实施，使得纪元领导者通过哈希难题确定，其计算易度取决于节点的股份值，从而防止暴力哈希竞争。解决难题的方案还附加到挖掘的区块中，以进行验证。

在另一种迭代中，由于其在网络中的股份，众多股东委员会被允许在周期内生成区块。会使用一种安全的多方计算方案来生成这样的委员会，以确保拥有更高股份的节点更有可能在委员会中占据更多位置。这类协议的一大瓶颈是委员会规模。大型委员会可能导致网络连接性下降，导致协议性能差和区块提案方案的不同步，以及由于过度通信开销导致无休止的共识周期。小型委员会确保均衡的共识过程，但其也会导致中心化。区块生产更有序，且它们继承了中本聪共识的50％网络安全阈值。

• PoS-BFT 协议，纪元领导者通常从相对固定的一组验证者中选出，这些验证者根据 BFT 标准达成共识。还实现了检查点机制，从而在特定时刻“密封”区块链，提供确定性最终性。这些协议使用“最新稳定”检查点规则来确定稳定主链，并最小化/解决分叉。

由于其继承的 BFT 风格区块最终性，PoS-BFT 协议通常具有 33％（⅓）的容错阈值，这通常通过区块提案方案或预建立的身份方案来增强。

祝贺你做到这一点，这是来自 DS 的赠品 POAP 兔子🤝

兔子攻击

你可能已经注意到，但之前的共识实现主要是针对区块链的。共识仍然是 DAG 中的一个主要问题（在我看来，简直是其存在的祸害），而且目前主要是理论性的，所以也许下次再聊。

点击喜欢并分享以赠送 Nitro 和肾上腺素，评论和批评以赠送知识，订阅以获得更多的兔子和文字沙拉，感谢！任何错误或误解都是我个人的错误，因为这段内容并未受到行业专家的校对🧏。

订阅

2个赞∙

1 Restack

2

• 原文链接： zhev.substack.com/p/algo...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～