更多信息 +
下载
关闭菜单 -

使用Unitrie实现更高的onchain可扩展性

Published on: 19 三月, 2019

RSK 诞生于 2015 年，当时作为一种以太坊兼容比特币侧链。回到 2016 年，RSK 侧链当时仍然处在开发阶段，我们决定改进并简化其设计，更换了一个关键以太坊组件：账户 trie，在以太坊黄皮书中也称作 world state。world-state trie 是以太坊式区块链中的主数据库，其支持数据结构称作 Secure Modified Patricia Trie。我们设计了一种替代状态数据结构，该结构后来演变为现在所谓的 Unitrie。

Sergio Lerner（RSK 实验室）在 laBitConf 演示 Unitrie (2016)

（原始）Unitrie 的部分主要特性如下：

  1. radix-16 树替换为 radix-2（二进制）树。
  2. 任意长度值可存储于存储单元中。
  3. 所有 trie 组合到一起，将合约存储单元与账户单元合并为更大的单个数据结构，我们称其为 Unitrie。
  4. 链接通过最后更新时间戳（lastUpdateTimestamp 字段）得到增强，从而使得 Unitrie 能够支持存储租金和节点自动休眠。
  5. 前缀存储于父节点中，可用于其每个子节点。这样就能够通过休眠移除叶节点，以便最大化数据处理能力。这样也可以防止对并行事务处理产生跨节点副作用。
  6. 密钥通过一个 10 字节（80 位）散列前缀进行“前缀保护”，以防止散列前缀之后 trie 失衡但仍包含完整密钥（散列像原）。
  7. 节点存储其有效负载的大小。
  8. 节点存储其子树消耗了多少字节。
  9. 如果节点太小，不足以在数据库中独立存储，则被嵌入其父节点。这样可节省用于引用该节点的 32 字节散列摘要。

Unitrie 的优点有些很明显，有些则比较微妙。主要改进列表如下：

  • 简化总体设计。
  • 降低实施的复杂程度，从而降低共识失败风险。
  • 简化轻量化客户端设计。
  • 通过使其对恶意状态提供方更加可并行、更有弹性而减少状态同步（也称作快速同步/曲线同步）时间。
  • 实现更简单的 SPV 客户端和 SPV 桥接欺诈防护。
  • 实现更简单的状态垃圾收集。
  • 实现按存储单元计算合约租金。
  • 实现按存储单元休眠和唤醒。
  • 通过按存储单元进行冲突检测实现并行执行。
  • 实现快速 EXTCODESIZE 查询，无需检索代码数据。

Unitrie 设计由 RSK 实验室针对 RSK 区块链提出，并于 2016 年 11 月 4-5 日在 laBitConf 上简要演示。然而，RSK 主网此时尚未启动，我们面临的首要任务是与以太坊开发工具保持更好的兼容性，因此，我们决定推迟实施 Unitrie，我们仅实施了 trie 数据结构的两个关键更改：采用 radix-2 替代 radix-16 以及存储任意长度值。采用 radix-2 后，应该可以通过进行动态 trie 转换实现将来到 Unitrie 的迁移，而非整个数据库迁移。事实证明，这是一个明智的选择，因为我们现在测试的整个树形结构快速动态迁移保留了最具结构性的部分。

到 2017 年底，我们意外发现 Vitalik 在以太坊论坛中提出了一个类似的以太坊变更。他还强调了组合状态树的优点。这种情况也支持了我们最初的论点：trie 联合是一种整体上好得多的设计。

Vitalik 的组合状态 Trie 提案 (2017)

时机已经成熟

2019 年 1 月，RSK 区块链面世一周年，这标志着 100% 正常运行时间状态已持续了一年时间，因此，我们决定继续努力，推动在下一次网络升级时采用 Unitrie 数据结构。我们编辑并打磨了旧版 RSKIP，创建了新版 RSKIP 和参考实现。本文代表了我们的一部分努力举措，旨在宣传 RSK 社区将如何从建议的更改中受益。我们更新了 RSKIP16，并增加了 RSKIP107、RSKIP108 和 RSKIP109。RSKIP107 介绍在存储 trie 节点时如何进行压缩。RSKIP108 介绍账户地址和存储单元地址如何映射到 trie 密钥中。RSKIP109 重新定义了存储单元写入成本，以激励使用更短的存储地址。我们还对所有这些更改一起进行了实施和测试，我们发现从状态更新到同步，节点性能和存储器消耗都有显著改进。然而，测试过程也并非一帆风顺。例如，我们决定从建议的设想中排除将 trie 节点前缀移至父节点的方案。原因是这种更改会使新旧 trie 之间的快速转换复杂化，使其依赖树形结构的相似性。

为了降低 hard-fork 相关风险，我们认为最好的策略是将这些更改拆分为两次连续的网络升级。首先，在 2019 年二季度会引入 Unitrie、前缀保护密钥、有效负载尺寸缓存、树大小缓存以及磁盘上节点压缩。其次，在 2019 年四季度会引入存储租金最后更新时间戳。我们推迟存储租金相关功能，因为存储租金 RSKIP 尚不是最终版本，并且因为第二次网络升级的更改仅影响新创建的 trie 节点（它不需要迁移 trie），而第一个网络更新需要全面迁移 trie。

独一无二的网络升级

将账户与存储节点完全组合到单个树中只能通过 hard-fork 实现，这意味着大多数矿工需要升级后才能支持此更改，并且所有完整节点也需要更新，以便保持同步。然而，Unitrie 升级不会给平台经济带来任何相关变化。将执行略低的存储成本，这是因为实际存储成本更好地匹配了收费金额。此变化将使社区的所有参与者获益。此外，这些变化也不影响平台的安全或隐私。请注意，大多数开发工具和钱包不直接访问 world-state 内部构件，因此，它们不会受到此 hard-fork 的影响。

该升级机制的缺点是，旧的完整节点状态数据库将不再兼容新数据库。创建同时兼容旧 trie 和新 trie 的完整节点是一项非常艰巨的任务，但几乎无益。好消息是，由于进行了许多性能改进，与之前相比，新的完整同步将仅需要一小段时间。此外，我们还测试了将状态数据库迁移至该新的节点启动格式，以便节点可以在软件升级后保持几乎不中断的正常运行时间。

Unitrie

Unitrie 将账户信息与所有合约的存储单元相结合。它存储合约存储单元，作为位于与合约的存储地址对应的节点上子树的叶。它还将合约信息划分为几个不同的树子节点。下面的简图显示一个账户（ECDSA 控制，没有任何子账户），一个合约（有一个子节点，存储合约代码），以及一个子子树（包含实际存储单元）。

区块链状态 Unitrie 示例

账户与合约存储的组合不是仅有的差异，密钥映射也不同。下面简述以太坊账户 trie 的工作原理：trie 通过采用账户地址的散列摘要进行“保护”，作为检索某个值的密钥。trie 上的节点不按账户地址存储，而是按其散列摘要存储。执行这种密钥转换以防止攻击者刷屏共享可将树降级到长链中的增长密钥前缀的值的数据结构。这种攻击会强制完整节点非常缓慢地执行某些查找，或者增加某些 trie 包含证据的大小。在 Unitrie 中，密钥从一个 80 位散列摘要前缀构建，之后是完整无格式账户地址。只有采用 80 位方可在整个 trie 上分布密钥并保持密钥大致平衡。考虑到树降级攻击的影响很小，因此，80 位远远足够抑制这种攻击。上述攻击需要设计一种特殊的基于 ASIC 的散列前缀强力强制硬件，这种硬件非常类似于一个工作证明矿工，并可制造数百万个此类“挖矿”盒子。如果我们想象最先进的比特币挖矿机可以执行任意 80 位前缀原像搜索，则攻击者应需要花费大约 6 百万美元的电费在 80 个不同的 80 位位置寻找冲突，然后方可轻微降级该 trie。然而，对块处理时间的影响应微不足道（因为缓存），失衡账户的包含证据的大小应仅增长 2 千字节。

此新映射的其中一个优点是它保存账户地址和存储单元地址时的状态能够使许多数据收集应用在向用户提供有意义的信息时无需索引整个区块链。下图说明账户和存储地址到 trie 密钥的转变：

账户和存储地址到 trie 密钥的转变

为了表现整体情况，我们介绍每个数据类型如何映射到 Unitrie 中：

密钥 值 描述
0x00

SHA3(account_addr)[0:9] account_addr

 Rlp（随机数，金额，标记） 账户状态
0x00

SHA3(account_addr)[0:9] account_addr

0x80

 字节矩阵 账户代码
0x00

SHA3(account_addr)[0:9] account_addr

0x00

 0x00 占位符，用于隔离存储树
0x00

SHA3(account_addr)[0:9] account_addr

0x00

SHA3(storage_address)[0..9]

trimmed_storage_address

 字节矩阵 存储单元上的值

第一个零字节用于将此树存储到特殊命名空间中。这样能够使将来的改进采用其他命名空间而无冲突风险。有可能使用自己的命名空间的部分未来改进如下：

  • 存储一种特殊节点，这种节点扩大至所有之前块散列的树（或森林），以启用工作证明的证据 (NiPowPow) 和忽略列表
  • 引用具有更高密钥长度（如 256 位）的账户地址以增强安全性。
  • 引用采用双重散列地址的账户地址，如 RSKIP32 所定义。

RSKIP16 Unitrie 与 Vitalik 的提案之间有许多不同点。其中一个不同点是，Unitrie 不在不同节点中存储随机数和金额，而是将它们放在一起。这有几种原因：

  • 这两个字段的序列化与反序列号需要很少的时间，因此，进一步拆分因增加检索账户状态的磁盘访问次数而导致效率损失。
  • 最好使特定合约地址上的部分数据能够在未来跟踪合约变化。
  • 账户可用于“刷屏” trie，因此，减少账户使用的空间非常重要。

Unitrie RSKIP 概览

Unitrie 通过 9 个 RSKIP（RSK 改进提案）定义。每个 RSKIP 描述 Unitrie 的一个具体组件：结构、存储、密钥映射、存储租金、休眠、gas 费用。下图分别进行介绍：

Unitrie 相关 RSKIP

在第一次网络升级中，将仅部署其中 4 个 RSKIP，其余将在后续网络升级中部署。这样可最大限度降低迁移风险。

 

Unitrie 忽略的问题

最初讨论 Unitrie 问题期间，我们推断，将来自节点数据的前缀拆分为两个不同的节点应有助于保持树的未受影响分支的完整不变性，并实现更精细的树更新并行。我们将此方案称为 PDB trie，因为节点可以是三种互斥类型之一：前缀、数据或分支。由于切换到 PDB 树需要进行重大结构性更改，因此，Unitrie 提案忽略了这个问题。但是，PDB 树可以作为进一步研究的一个主题。

用于存储区块链状态的 PDB 树示例

现在，我们更加详细地讨论 RSK Unitrie 的每一项优点。

缩短会员资格证明

通过采用二进制 trie 代替 radix-16 trie，可尽最大可能缩短 RSK trie 中账户的会员资格证明，同时，验证其会员资格证明需要的时间也接近最优水平。这样可实现分散化轻量节点、在移动电话上运行、消耗更少的带宽以及更低的功率。在下面的示例图中，radix-16 rie 需要 30 个指针（实心圆）和 3 个节点（圆圈）来证明存在目标节点（蓝色圈）。radix-2 trie 仅需要 8 个指针和 8 个节点。传输节点时不需要传输父参考，因为可动态计算其参考，因此，二进制 trie 证明需要的空间是 radix-16 trie 的 26%。

radix-16 与 radix-2 trie 会员资格证明的比较

通过压缩账户节点减小状态大小

Unitrie 中的账户既不需要存储“存储”trie 根散列摘要，也不需要存储代码散列摘要，这意味着从状态中几乎移除了 60% 的账户数据。例如，存储 1 个 RBTC 的账户使用约 38 个字节，而以太坊中使用 104 个字节。下图显示移除不必要的字段节省的大致空间。

通过移除不必要的字段压缩账户节点

通过嵌入小节点减小状态大小

对于大小小于 ~44 个字节（准确值待定）的子节点，Unitrie 提供将其直接嵌入父节点的功能。此功能在 RSKIP107 中说明。 由于大部分账户最终的节点大小范围均为 31 至 41 字节，这意味着大部分账户将嵌入父节点中。这样可降低账户间接费用达 62%。通过节点嵌入以及缩短账户记录实现的账户大小减小达 81%，这样不仅可减少完整节点的同步时间和资源需求，而且还可降低 DoS 攻击风险（通过创建账户刷屏状态）。下面的示例图显示以太坊 trie 中有两个子节点的节点如何转换为 Unitrie 中嵌入子节点的单个节点。

将两个小节点嵌入其父节点

通过压缩存储单元密钥减小状态大小并降低 Gas 费用

我们的 RSKIP108 介绍存储密钥具有一长串零前缀时可以怎样压缩存储单元。具有单字节地址以及存储单个字节的单元最多可压缩至之前未压缩大小的 10%，因为其尺寸小，也可实现节点嵌入。为了激励用户使用压缩存储，RSKIP109 更新了合约存储写入操作的成本。例如，在地址 0x00 存储 0x01 会使用低至 5460 gas 单位，而以太坊中为 20K。下图说明以太坊和 Unitrie 中存储单元地址 0x01 使用的不同密钥。

密钥存储压缩示例

配合并行事务处理时具有更好的可扩展性

我们的 RSKIP04 建议采用并行事务处理以减少块处理时间。通过减少块处理时间，我们可以更快地传播块并改进共识。这也意味着我们可以将更多的事务纳入块中而不延迟块传播。通常，相对于较小的挖矿池，较高的块传播延迟有利于最大的的挖矿池，因此，了解我们扩展但不降低分散化程度是一个令人安心的事实。然而，如果事务可以拆分为合约状态访问不重叠的集合，则区块链只能从并行事务处理中获益。如果所有事务均调用某个单个令牌合约，则该合约强制事务序列化并成为瓶颈。其中一个解决方案（如 RSKIP59 中所规定）是，在设计合约时使合约存储单元移入子合约，从而创建父子关系。然后，将不同用户的令牌余额存储于不同的合约中。该解决方案仍然需要重新设计和重新实施合约以强制特定设计模式的用户启用可扩展性。但 Unitrie 有可能解决该问题，并且没有使用新模式的相关障碍。Unitrie 启用同时访问存储单元简化检测，而非仅检测同时访问完整合约。这意味着只要两个合约不写入同一存储单元（或一个合约读取另一个合约写入的存储单元），则两个合约可同时执行。例如，ERC20 合约通常仅修改与源账户和目标账户相关的单元，因此，这些合约会通过单元级检测获取立即并行处理的能力。虽然没有 Unitrie 也可以实现同样的功能，但 Unitrie 可大大简化写入冲突检测算法。我们以下图为例来介绍处理事务的两个线程。第一个线程修改合约 C 的某个单元（通过紫色箭头指示），它不受线程 2 的影响。而线程 2 修改同一合约的另外两个单元，它不影响线程 1 修改的单元。

两个执行线程修改同一合约存储

与存储租金组合时更加公平

以太坊设计的其中一个结果是，它启用 gas 套利，用户可通过该功能预购和占有存储单元而不存储任何有用数据，只是在晚些时候清空这些单元以便重新获得最初用于购买这些单元的部分 gas，然后将该 gas 出售给第三方。另一个非计划结果是，以太坊需要高额预付款以便使用新的存储单元，因为此付款主要用于密钥/值对的永久性存储和活性保证。

存储租金可同时缓解这两个问题。讨论最多且广为接受的存储租金形式需要用户与合约交互，以便支付与上述合约不活动的时间成比例的费用，该费用也与不活动时间期间合约使用的存储空间成比例。RSKIP61 建议采用合约租金，以防止原始 EVM 设计的部分不受欢迎结果影响平台公平。虽然这样可提供大致的公平性，但是它只是一个粗略框架，并且在极端情况下效果不佳。许多人拥有的合约存储数百万条密钥/值对但很少使用的情况将导致长时间不活动周期后第一个调用的用户产生巨大存储租金负担。Unitrie 可简化单个存储单元跟踪最后访问时间的任务，从而细化存储租金，允许合约仅支付调用执行涉及的单元的租金。这种简化（在 RSKIP113 中详述）源自平等对待所有节点，因此，账户、代码和存储单元可在被访问时收取租金。

通过简化状态垃圾收集提高完整性

状态垃圾收集指清除正常情况下因已覆盖而绝不会再次被引用的旧状态数据。在区块链重大重组等异常情况下，可通过从预先计算的状态检查点重新执行旧块来重新计算此数据。但是，以太坊中的垃圾收集非常重要，因为它必须应用到许多单独的数据库（或 trie），每个活动合约一个。采用 Unitrie 意味着垃圾收集应用到单个数据库，从而降低有可能在垃圾收集过程中更改数据库而使其处于不连贯状态的线程中断风险。

状态同步更快、更简单

许多应用都需要在特定块高度查询区块链的状态，包括轻量级钱包和区块链桥等。Unitrie 采用二进制结构，使用空间最少，检索和证明该状态下数据会员资格的性能最高。它还可降低传输状态信息所涉及网络命令的复杂性。

然而，最为重要的是，Untrie 可启用快速并行下载状态信息以执行“快速同步”或“曲线同步”。 如果所有信息均存储在单个 trie 中，则节点可更高效地检索状态信息。由于 Unitrie 存储位于每个子节点的子树使用的字节个数，因此，Unitrie 数据结构支持尺寸范围查询。此功能可用于同级请求特定大小的 trie“包”，从任何字节偏移开始均可。因此，请求可以负载平衡良好的方式并行。例如，某个节点可以收集来自 10 个节点的状态信息，并依次请求字节范围 0K 至 100K、100K 至 200K 等，以此类推。这样可允许创建同步模式时兼具快速同步（立即验证返回的数据）和曲线同步（同时从多个源检索大数据块）两者的优点。下图为示例 Unitrie 显示节点子树大小的情况。trie 可被拆分为三个块，各包含几乎等量的数据，每个块均可被不同的同级请求。即使请求者不知道每个块的内容和限制，请求者也可提前了解块的大小。收到块时可高效、分别验证每个块。部分内部节点包括于一个以上的块中，以便启用验证。

状态 Unitrie 拆分为三个单独的可验证块

 

而 Unitrie 的另一个巨大优势在于，通过存储 trie 节点大小，网络节点可以显示状态同步完成百分比，并预估完成同步的剩余时间。

较小的区块链通过自动代码消除重复

通过将存储单元和代码组合至单个内容寻址数据库中，包含相同密钥/值的节点在该数据库中仅存储一次。这样可提供自动数据去重复功能，对于合约代码，该功能可减少区块链大小，并且不需要单独的去重复机制，也不需要使用数据压缩技术。trie 中的代码节点将始终包含相同的前缀 (0x80)；因此，相同的代码意味着相同的节点散列和相同的存储。

EXTCODESIZE 执行更快

每个 Unitrie 节点均包含一个字段，缓存该节点中所存储数据的大小。在以太坊 trie 中，查询节点数据大小时强制从数据库提取该数据。Unitrie 可通常查询此新字段响应大小查询，例如 EXTCODESIZE 运算码生成的查询，无需从硬盘提取该代码。EXTCODESIZE 运算码过去在某些以太坊实施中一直用于执行 DoS 攻击，而 Unitrie 对这种攻击提供免疫力。

升级方法详述

任何区块链都从未执行过在该数据库提交到区块标题中时更改状态数据库的升级。因此，该升级将是首次这种升级。该升级实质上分两个阶段实施。新的软件版本将计算新的 trie 根，但仍然导出旧的 trie 根，利用动态算法在运行中将新的状态 trie 结构性转换为旧的 trie，之后是一个 hard-fork，在此提交和验证新的状态根，并且不再进行动态转换。事实上，不仅必须转换状态 trie，而且还要转换事务和收据 trie。

成功执行网络更新必须发生几个事件。新版本完整节点软件将在时间 R 发布。该新版本包含定期检查点（从起源块到特定块，时间 C）。时间 C 在时间 R 之前发生。之后是一个间隔，此时节点将于时间 H 在 hard-fork 之前升级。下图显示时间轴：

Unitrie 网络升级时间轴

安装新版本（我们称之为 0.7.0）时，完整节点必须根据新规则重新构建其状态数据库。它可迁移当前状态，也可从起源到最佳链顶端重新处理所有块以重新计算状态。对于 RSK 升级，我们选择重新处理。这样可确保所有完整节点的数据库完美同步，即使之前的数据库因某种原因已损坏。

选择事件 C，以便它在 hard-fork 之前约两星期发生。用户应在发布日期 R 之后但在 hard-fork 日期 H 之前升级其完整节点软件。在 C-H 周期期间，节点将同时计算旧的和新的 trie 状态根。将从新的状态 trie 动态计算旧的状态根。轻量化节点（也称作SPV 节点）可决定在这个短间隔期间不验证状态根以减轻 CPU 负载。这是因为轻量化节点始终遵循散列率。此外，节点也可在此周期期间通过一些方法降低验证间接费用：例如，在 C-H 间隔期间每 10 个状态根提交只验证 1 个。但是，hard-fork 之后的第一个块将不再计算或验证旧的状态根。如果社区接受，我们希望发生非常干净的 hard-fork 事件。

总结

RSK 在 2016 年提出的 Unitrie 可显著改进 RSK 等基于账户的区块链中的状态存储，提供明显更好的完整节点性能。Unitrie 通过降低完整节点资源要求改进分散化效果，通过启用更好的并行事务执行提高事务产量，通过缓存有效负载大小并减小账户尺寸防止 DoS 攻击，通过启用更好的存储租金提高公平性，并通过压缩状态减少同步时间。

我们知道执行网络升级以采用 Unitrie 具有挑战性，但是我们认为实施这种改变的时机已经成熟。RSK 实验室正在完成参考代码并为 RSKIP 增加最终修饰，同时，RSK 社区也正在评估这种改变。未来几个月，我们期望实施安全网络升级以激活 Unitrie。