分片包含列表（公告板链）

本文讨论了区块链网络中交易排序的瓶颈问题，并提出了一种通过分片包含列表（Bulletin Chains）来扩展区块链的方案，旨在减少对所有应用都要求完全排序的需求。文章探讨了SUAVE、Orderflow Auctions等概念，及Narwhal等现有技术，并设计了几种改进的算法，以实现更快的共识和水平扩展，同时考虑了安全性和活性之间的权衡。

在制品：公告链（分片包含列表）

这项工作可以被看作是一种分层共识，其中每个子组件实现因果广播而不是全序广播。

设置和目标

建立事务的全序是区块链网络中的主要可扩展性瓶颈之一。已经有许多扩展区块链的尝试，例如闪电网络、乐观和 ZK Roll Up、分片等等。 在这里，我们概述了一种扩展方法，该方法建立在这样的观察之上：对于希望比其基础链更快地实现共识的所有应用程序，不需要全序。

SUAVE

在 Flashbot 成功地使用 PBS 设计将 MEV 的中心化效应隔离到 Gasper PoS 中的区块构建者角色之后，下一个目标是去中心化区块构建者角色本身。 为了尝试这样做，发布了 MEVM，它是 EVM 的修改版本，带有预编译来支持 MEV 用例，所有这些都在可信执行环境 (TEE) 网络之上运行。 这种架构允许用户将出价发送到加密的 mempool，并允许他们的出价由 MEV 应用程序处理，这些应用程序以 Builder Solidity 中的智能合约编写。 通过提供一个更高层次的区块链来运行这些程序，用户可以保证他们授予权限的订单流拍卖规则，可以被验证地运行在他们的出价之上。

MEVM 设计中最强大的部分之一是 OFA、Solver Networks、RFQ 和区块构建之间通用的组件都可以重用。 下面我们可以看到一个早期的 MEVM 生态系统可能是什么样子以及组件如何交互的示例。

订单流拍卖

SUAVE 上的可信拍卖包含三个部分：

  • 一个精心设计的机制 - 即没有泄漏和最佳匹配、路由等。
  • 一个抗审查的包含列表，列出在拍卖运行期间可用的出价
  • 拍卖计算的证明（ZK、TEE 签名等）

使用最后两部分，如果用户的出价未被包含，他们应该能够构建欺诈证明。

MEVM 驱动的订单流拍卖的一个例子是 walrassian 拍卖，“一种同步拍卖，其中每个代理计算其对每种可能价格的商品的需求，并将其提交给拍卖师。 然后设置价格，以便所有代理的总需求等于商品的总量。”[1]。

为了将这个例子翻译到 SUAVE 上，我们只需要用 solidity 将我们的拍卖逻辑写入一个智能合约，部署它，然后用户就可以开始向链发送出价，以便纳入拍卖。 因为拍卖的输入越多越好（不确定这是否严格正确），并且用户想要抗审查性，他们可以将这些加密的交易存储在链上，以便在聚集了足够多的出价时使用。

💡 观察 1：在这种框架中，拍卖中出价的顺序并不重要。 或者等效地，类似的机制设计者无需在其设计中考虑排序。 无论你的交易在批处理中是第一个还是最后一个，你的需求曲线都是相同的。

这种观察，即我们的系统需要对一个集合达成共识，而不是对一个单一的排序达成共识，将构成本文档中提到的所有设计的基础。 另一种说法是我们不需要 全序广播，而是可以使用许多其他选项中的一个[2]：

  • 因果广播：这确保如果消息 m1 在因果关系上先于另一条消息 m2，那么任何正确的进程都不会在 m1 之前传递 m2。 它尊重因果顺序，但不一定尊重全序。
  • 先进先出广播：这确保来自同一发送者的消息按照它们发送的顺序传递。 但是，来自不同发送者的消息可以以任何顺序传递。

在上述广播类型中，应使用每种类型的 可靠广播 变体。 在可靠广播中，目标是确保如果正确的进程广播消息，那么所有正确的进程最终都会传递它。 它不保证任何特定的传递顺序。

最后，应该注意的是，这种设计选择对 SUAVE 上所有未来的拍卖都具有强烈的意见，不应掉以轻心。

设计目标

  • 横向扩展 - 实现更高 TPS 的方式不应该是通过增加验证器硬件的尺寸。
  • 可调整的安全性 - 为了更快的共识而权衡安全性和活跃性风险应该是一个留给开发人员和用户的选项。 在一个极端，我们有大型且地理上分散的验证器集，而在另一个极端，我们有小型且超本地的验证器集。
  • 低于 SUAVE（主链）的区块时间 - 只有当任何设计能够实现比 SUAVE 主链（目前约为 2 秒）更快的同步周期时，才应选择它。

现有技术

为了简洁起见，我已将现有技术移至末尾，但将高亮显示每个技术的关键思想：

Narwhal [3]：

  • 将数据与共识分离，并使用固定大小的引用（元数据）来减小消息大小
  • 在排序之前就哪些事务可用达成共识，可以简化负责排序的共识协议的工作。

异构 Narwhal [4]：

  • 两个协议，每个协议都有自己的 Narwhal mempool 和一些重叠的验证器，可以通过叠加它们的 DAG mempool 来实现原子跨链事务
  • 如果重叠的验证器很小，则存在活跃性风险。 他们以某种方式减少了这种情况，但从在制品论文中并不清楚。

异构 Narwhal 的一个很大的灵感来源是 Cosmos 和 Cosmos Hub 中的验证器拓扑，其中一些节点为多个网络进行验证，而另一些节点为一个网络进行验证。

分层共识 [5]：

  • 这不是以算法方式分配节点成员资格和负载平衡状态的分布，而是一种用户和矿工被分组到他们可以自由参与的子网中的方法。
  • 子网通过检查点帮助保护其后代子网——这有助于缓解对子子网的攻击，例如在基于 PoS 的子网中的远程和相关攻击。 （我不确定这与 Roll Up 有何不同）

分层共识 [5]：

  • 这不是以算法方式分配节点成员资格和负载平衡状态的分布，而是一种用户和矿工被分组到他们可以自由参与的子网中的方法。
  • 子网通过检查点帮助保护其后代子网——这有助于缓解对子子网的攻击，例如在基于 PoS 的子网中的远程和相关攻击。 （我不确定这与 Roll Up 有何不同）

提出的算法描述

在深入研究设计之前，让我们先来看一个分布式区块构建流程的示例，我们可以使用它作为比较不同设计的基础。 该流程以用户发送出价开始，以将区块发送给验证器结束。

我们的示例设置包括：

  • 验证器集 v = { v0, v1, …, vn }，其中 n = 9
  • 5 个 SUAVE 应用程序：UniX、CowSwap、Mev-Share、默认构建器、Otter 构建器
  • 3 个子委员会，SUAVE、UniX 和 CowSwap：
    • 验证器集分别为 vm、vu 和 vc，其中 vm ∪ vu ∪ vc = v 是整个网络的验证器集
    • UniX 中的第一个验证器表示为 vu1，它可以等效于任何 vi，其中 i <= n
  • Δ 是共识期间同步周期的最大长度。
    • ΔS、ΔU 和 ΔC 分别是子委员会 SUAVE、UniX 和 CowSwap 的同步周期
    • 此外，我们的示例应用程序具有这样的偏好：ΔS > ΔC > ΔU，这意味着主 SUAVE 链的共识时间严格大于 CowSwap 的共识时间，后者严格大于 Uniswap 的共识时间。

交易/出价/机密计算请求：

  • 4 个对 UniX 的出价
    • 2 个调用来运行 UniX 拍卖
  • 2 个对 CowSwap 的出价
    • 1 个调用来运行 CowSwap 拍卖
  • 2 个对 Mev-Share 的出价
  • 6 个调用来构建区块，主要集中在订单流的末尾，我们自然会期望有最多的调用来执行区块构建计算。

以下是从当前 SUAVE 链的角度来看，这样的交易进展情况：

注意：此图的一个不足之处是没有区分机密计算请求，例如，这可能会触发将区块发送给验证器。 来自 confidenitla 计算的影响，该计算导致区块被发送，不一定只在链上接收到负责该请求的交易时才注册。 区块将在执行器节点运行该请求后发送给验证器，然后该函数返回的任何回调最终都会到达链上。

简单方法 - DAG（顺序无关）“RollUps”

我将其称为 Roll Up，因为它正在使用这些箭头将更新推回主链，但关键是它仅推送可用内容的摘要，而不是收到的内容的顺序。

请注意，MEV 共享出价仍然可以进入主链。 理想情况下，子网是完全可选的。

这满足了我们的设置目标，其中 ΔU < ΔC < ΔS，但它是否尽可能快？

请记住，观察 1 意味着存储桶或插槽中出价的排序实际上并不重要，因为用户的机制应该是与排序无关的。 因此，我们可能在浪费通信轮次，以便就排序达成一致。

待办事项：创建类似于下面的图表，其中包含 Narwhal 与 PBFT 和 Gasper 的通信复杂性比较。

检查点安全性的问题在于，你可以获得安全性，但我们想到的用例不需要安全性。 因为我们正在影响其他链的工作方式，所以在产生下一个区块后，如果我们追溯回顾并说“哦，嘿，这是无效的”，那就无关紧要了，就像 Roll Up 所做的那样。

更好方法 - 具有独立验证器集的并行 Narwhal

这里有几个想法：

  1. 我不确定此协议是否可靠或是否捕获了链下交易的概念
  2. 不确定 SUAVE 主链验证器传播回 UniX 和 CowSwap 验证器是否有意义。
  • 我认为确实有意义，因为他们想知道他们被包含在链中。 但是他们是否需要将投票提交回来？ 如果是这样，那意味着需要 CowSwap 区块，并且我们处于相同的位置。 因此，也许他们会发回投票，签署来自他们链的部分，而 SUAVE 主链验证器会汇总来自子委员会的这些部分签名，以及来自 SUAVE 主链验证器的完整签名。
    1. 这将我们的安全性从 9 个节点分散到每个链 3 个节点。 需要注意的一点是，从处理能力 standpoint 来看，子委员会验证器的资源消耗可能要少得多，因为它们仅维护一个协议的出价，并且通信成本较低。 但通常安全性是指与权益相关的权益，而不是运行验证器的机器的资源。

更好方法 - 具有验证器子职责的并行 Narwhal

这与之前的方法相同，除了 UniX 和 CowSwap 验证器也将参与对 SUAVE 主链验证器提出的区块进行投票，即所有验证器都是 SUAVE 主链验证器，但有些具有额外的职责。

但是，这种方法的优点是，我们不会分散主链的验证器集安全性。

更好方法 - 分层向量时钟

也许我不确定。

分层向量时钟非常适合使用高度分层通信网络的现代消息传递分布式系统。

开放性问题

  • 聚合分叉选择规则是什么？
  • 子网之间的交互？
  • 子网是独立的还是分层的？

这种方法的缺点：

  • 出价不能跨越多个子网，除非使用类似异构 Narwhal/Paxos 的东西
  • 上述说法是否正确，这是一个问题吗？
    • Narwhal 仍然有一些预期的 TPS，当我们突破这个界限时，我们不会遇到同样的问题吗？ （巨魔回答：如果我们以此为理由不进行构建，那么以太坊就不会开始。 但这是一个需要考虑的合理问题）

实现

我们可以使用与 ERC 4337 捆绑器规范中的 mempool ID 类似的想法，但这并没有回答权益问题。

捆绑器支持的每个 mempool 关联的元数据都记录并存储在 IPFS 中（还建议将一份副本提交到 eth-infinitism Github 仓库）。 文件的此 IPFS 哈希称为 mempool-id，它用作捆绑器中订阅的主题。 mempool 元数据的建议结构如下

chainId: '1'
entryPointContract: '0x0576a174d229e3cfa37253523e645a78a0c91b57'
description: >-
  This is the default/canonical mempool, which will be used by most bundlers on
  Ethereum Mainnnet
minimumStake: '0.0'

规范 mempool 的 mempool-id 为待定（yaml/JSON 文件的 IPFS 哈希）。

问题：

  • 任何人都可以部署 mempool ID 吗？

  • 用户如何知道 mempool 的安全性？

  • 如何

现有技术

Narwhal

有向无环图 (dag) 出现在最近提出的几个共识中

协议 Danezis et al. 2022; Keidar et al. 2021; Spiegelman et al. 2022. - 🔗 sauce

Narwhal 声称：领导者是瓶颈

Narwhal 想法：

  • 交易数据未包含在共识中 => 更小的消息大小
  • 通过工作人员进行并行化

与异构 Narwhal 的主要区别在于，我们可以为底层证书拥有不同的验证器集。 当然，这会带来活跃性风险，但理想情况下，“更高阶”子网的活跃性不受底层子网脱机的影响。

这是一个区别吗：在我们的 SUAVE 用例中，mempool 达成共识的事务可用性，以及拍卖产生的计算结果，不需要在 SUAVE 链上运行。 它们只需要最终出现在发送给不同域上的验证器的区块中。 尽管最终我认为我们应该

中央 Narwhal 概念

  • 每个验证器在每个高度最多可以提议一个区块；
  • 创世区块后的每个区块都必须引用法定数量（即，至少 2f + 1）的

上一轮的区块；

  • 区块需要从下一轮的弱法定数量（即，至少 f + 1）的

区块中引用，才能成为领导者区块（又名锚点）。

  • 分叉选择规则是，每个验证器都证明它看到的任何区块，只要它是该轮中来自该验证器的第一个区块，并且只要它是有效的（稍后定义的概念）

系统假设

  • 具有一组 ( n ) 方的消息传递系统。
  • 对手最多可以破坏 ( f < \frac{n}{3} ) 方。
  • 诚实方之间的异步最终可靠的通信链路。

Narwhal Mempool 抽象

  • 区块：区块 ( b ) 包含事务列表和对先前区块的引用。 其唯一摘要 ( d ) 用作其标识符。
  • 轮次：每个验证器维护一个当前的本地轮次 ( r )，从零开始。 验证器将事务累积到事务列表中，并将 ( r ) 处的区块的可用性证书累积到证书列表中。 一旦从 ( 2f + 1 ) 个不同的验证器累积了轮次 ( r - 1 ) 的证书，验证器就会移动到轮次 ( r ) 并为新轮次创建一个区块。
  • 操作：
    • write(d,b)：存储具有其摘要 ( d ) 的区块 ( b )。
    • valid(d, c(d)): 检查证书是否有效。
    • read(d)：返回一个区块 ( b )。
    • read_causal(d)：返回一组区块 ( B )，该组区块与 ( b ) 具有传递的 happened-before 关系。

算法描述

  1. 区块创建：一旦验证器从 ( 2f + 1 ) 个不同的验证器累积了轮次 ( r - 1 ) 的证书，它就会移动到轮次 ( r )，创建并广播新轮次的区块。
  2. 区块验证：如果区块包含来自其创建者的有效签名，并且位于验证器检查它的本地轮次 ( r ) 处，并且满足其他指定的条件，则该区块是有效的。
  3. 可用性证明：一旦创建者获得区块的 ( 2f + 1 ) 个不同的确认，它就会形成区块可用性证明。 然后共享此证书，并可能包含在轮次 ( r + 1 ) 的区块中。
  4. 垃圾回收：验证器只能根据有关当前轮次的信息来确定区块的有效性。 早期轮次的区块可以安全地存储在主验证器之外。 验证器同意垃圾回收轮次以保持一致性。
  5. 可靠广播：Narwhal 使用一种抗 DoS 且高效的拉取机制。 在任何时候，每个区块只有 ( O(1) ) 个请求处于活动状态，并且在收到正确的响应后，可以删除所有挂起的请求。
function MAIN_LOOP(validator v):
    WHILE TRUE DO
        TRANSACTION_ACCUMULATION(v)
        CERTIFICATE_ACCUMULATION(v)
        IF COUNT(v.certificate_list) ≥ 2f + 1 THEN
                v.r ← v.r + 1
                BLOCK_CREATION(v)
        END IF
        BLOCK_VALIDATION(v)
        CERTIFICATE_FORMATION(v)
        CERTIFICATE_HANDLING(v)
        GARBAGE_COLLECTION(v)
    END WHILE

属性

  • 完整性：对于任何经过认证的摘要 ( d )，诚实方对 read(d) 的所有调用都返回相同的值。
  • 区块可用性：如果在诚实方通过 write(d, b) 之后调用 read(d)，则它返回 ( b )。
  • 包含：对于 ( B ) 中的每个区块 ( b' )，由 read_causal(d') 返回的集合 ( B' ) 是 ( B ) 的子集。
  • 2/3-因果关系：成功的 read_causal(d) 返回一个集合 ( B )，该集合包含在 write(d, b) 之前写入的至少 2/3 的区块。
  • 1/2-链质量：成功的 read_causal(d) 返回的集合 ( B ) 中，至少有 1/2 的区块是由诚实方写入的。

–

异构 Narwhal

本文更多的是关于使现有

协议异构化，选择基于 dag 的共识作为一个与

异构 Paxos I. Sheff et al. 一起使用的示例。

在此过程中，我们将描述异构化如何以不同的方式应用于

可用性和完整性 I. C. Sheff et al. 2019 的问题：

可用性 所有相关的交易数据都经过认证可以获得

完整性 可用数据未更改，例如，没有重复支出、含糊不清等。

动机

作为运行示例，让我们考虑两个具有权益证明的基础账本。

验证者集着手构建包含

两个单独的“原生”Narwhal dag 的信息的单个共享 Narwhal dag。 理由是，区块可能包含可以原子执行的跨链事务。

简单方法

Narwhal DAG 的简单叠加会带来活跃性风险。

现在，作为第一个想法，我们可以将锚定区块限制为那些满足两个基础账本的条件的区块； 事实上，我们获得了组合 Narwhal mempool 的安全实现。 然而，除了关于仅持有其中一个基础账本的权益的验证器的倾斜激励的明显问题外，简单叠加的“完美”安全保证是以活跃性风险为代价的：粗略地说，叠加 Narwhal dag 导致相对于每个基础账本，“活跃度较低”的 dag。

星际共识

https://docs.filecoin.io/basics/interplanetary-consensus/hierarchical-consensus

分层向量时钟

ChatGPT 建议

问： 实现因果广播的算法有哪些示例？

答： 因果广播是一种通信原语，可确保以尊重其因果顺序的方式传递消息。 已经提出了几种算法来实现分布式系统中的因果广播。 以下是一些著名的算法：

  1. 向量时钟：
    • 由 Colin Fidge 提出，后来由 Friedemann Mattern 独立提出。
    • 每个进程维护一个计数器向量，系统中每个进程一个计数器。
    • 当进程发送消息时，它会增加其向量中自己的计数器。
    • 收到消息后，进程使用接收到的消息中的向量以元素方式最大值来更新其向量时钟，然后增加其自己的计数器。
    • 仅当消息的向量时钟可以进行因果传递时才传递消息（即，该消息的向量仅比接收进程的向量提前一个单位，用于发送方条目，并且不提前于所有其他条目）。
  2. 逻辑时钟（Lamport 时间戳）：
    • 由 Leslie Lamport 提出。
    • 每个进程维护一个计数器。
    • 在每个事件之前增加计数器，并随每条消息发送其值。
    • 虽然比向量时钟更简单，但 Lamport 时间戳仅提供事件的部分排序。 它们可用于确定一个事件是否在因果关系上早于另一个事件，但不能确定它们是否同时发生。
  3. Birman-Schiper-Stephenson 协议：
    • 使用向量时钟进行因果广播的特定协议。
    • 它使用向量时钟来对消息进行时间戳，并采用一种传递机制，该机制通过缓冲乱序消息来确保因果顺序。
  4. 触发消息序列图 (TMSC)：
    • 一种形式主义，将消息序列图与触发器相结合，以指定分布式系统中消息之间的因果关系。
  5. 依赖序列：
    • 对于通信图稀疏的系统，对向量时钟的优化。 进程不是维护完整的向量，而是维护依赖序列，以更紧凑地捕获因果依赖性。
  6. 分层向量时钟：
    • 对以分层方式组织的大规模系统的优化。 它通过为不同的层次级别维护不同的向量来减小向量时钟的大小。

这些算法和协议提供了确保如果消息 m1 在因果关系上先于另一条消息 m2，那么任何正确的进程都不会在 m1 之前传递 m2 的机制。 特定算法或协议的选择通常取决于分布式系统的特定要求以及时间和空间复杂性之间的权衡。

参考资料

[1] : https://en.wikipedia.org/wiki/Walrasian_auction

[2] : https://www.doc.ic.ac.uk/~ac3419/notes/year3/distributed_algorithms/03_fct_broadcast.pdf

[3] : https://arxiv.org/pdf/2105.11827.pdf

[4] : https://github.com/anoma/research/blob/master/distributed-systems/heterogeneous-narwhal/HeterogeneousNarwhal.pdf

[5] : https://research.protocol.ai/publications/hierarchical-consensus-a-horizontal-scaling-framework-for-blockchains/delarocha2022.pdf

  • 原文链接： hackmd.io/BALXiGhqRFmYqs...
  • 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～
点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ，好文好收益，欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
BALXiGhqRFmYqsJICpDhYg
BALXiGhqRFmYqsJICpDhYg
江湖只有他的大名，没有他的介绍。

BALXiGhqRFmYqsJICpDhYg

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！