Turboproof 证明系统初探

以太坊的状态数据正不受限制地快速增长，长此以往，将只有少数大型公司才能负担运行节点的成本。应 Alexey 的要求，本文阐述了我对 Alexey 的 turboproof 证明系统的理解，该技术也许能用在多种轻客户端上。

以太坊区块链的状态数据使用十六叉（hexary）帕特里夏树（patricia tree）（或简称 trie）来存储的。数据存储有两个层次：

1. 地址树是从地址到账户数据的映射。
2. 智能合约的数据也存储在一棵数据树中，该树就是由从 32 字节内存地址到 32 字节的值的映射构成的。

这些默克尔树存储（键，值）对。请注意，键的基本单位是半字节（4 个 bit），而不是一个字节。这些默克尔树具有 3 种类型的节点：

• 叶子节点：这些是（键后缀，值）对，它们始终是默克尔树的终端节点。
• 分支节点：内部节点，并且此节点及其所有子节点共享相同的前缀。每个分支节点有 17 个条目。前 16 个条目对应于子节点的键后缀的第一个半字节。如果存在，则第 17 个条目是与键前缀关联的值
• 扩展节点：“捷径节点”，让所有子节点共享一个公共前缀。有了扩展节点，就不会建出很多只有一个叶子的分支节点了。。

举个例子，以下的树有一组叶子节点，分支节点以及扩展节点：

-图1. 一个 Trie 编码以下键值对：（0x1234，0x0000），（0x1111，0x1111），（0x4567，0x2222）和（0x4569，0x3333）。在此示例中，键和值已缩短为 2 个字节，以提高可读性。标签为 0 到 15 的行表示分支节点，延伸出来的箭头所指的半字节是其子节点的前缀。第 17 个条目（索引 16）未使用，因此未显示。 [5,6] 的那一行是扩展节点，这意味着其子节点必须以这两个半字节为前缀。终端节点是叶子，左边的两个具有前缀（为的是记录键），右边的两个不需要前缀，因为根据指向它的路径就能得到完整的键。-

在实际应用中，这个模型是以太坊很多效率问题的根源，但是它也被证明有很强的韧性。

序列化值

一些用例需要在用户之间传递（键，值）元组。例如，为了节省空间，轻客户端仅存储各默克尔树的根。因此，为了与状态进行交互，用户需要告诉轻客户端自己的状态是什么样的，以便轻客户端可以执行操作并计算新的状态根。为压缩数据，该建构必须能够将多个账户的状态变化打包成单个证明。

在前面的示例的基础上，这是树中同时存在（0x1234，0x0000）和（0x4567，0x2222）的证明：

-图2. 证明图1中的树包含（0x1234，0x0000）和（0x4567，0x2222）。除了这两个值以外的子树所存储的值都用原值相应哈希值替代。（在本图中，这两个子树都是简单的叶子节点）。 -

（依照默克尔树的计算规则）只要在该证明中提供的哈希值就是原值的哈希值，那么根据图 2 中的信息计算出的树根哈希值将与图 1 中的树根哈希值一致。

问题是如何序列化数据：给定一个哈希表列表和（键，值）对列表，人们如何找出树的结构？例如，仅给出以下输入：

• （0x1234，0x0000）和（0x4567，0x2222）的（键，值）对（键和值长度被缩短以使生成的图片更具可读性）
• 表示子树的哈希值。

人们可能重建出下面这棵树：

-图3. 因为缺少结构信息而建出的错误数据树-

也可能建出下面这样的数据树：

-图4. 另一棵因为缺乏结构信息而产生的错误数据树-

因此，我们需要编码
结构信息的方法。

Turboproof

Alexey Akhunov 的提案仍在制定中，而我这篇独立的文章也想略尽绵薄，为定义整个概念做点工作。这里介绍的解决方案与我和 Sina Mahmoodi 合作的 rust 实现相对应。Turboproof 分为三个部分：

1. 叶子节点的清单
2. 哈希值的列表，与树的原始分支一一对应
3. “结构信息”，即仅使用提供的哈希和叶子如何重建树的指令列表。

为能重建出正确的数据树，最后一部分被编码为供堆栈器执行的一系列指令：

• LEAF 表示应从证明的叶子序列中弹出一个叶子节点；
• BRANCH（i）规定需要创建一个新的分支节点，并且之前构造的节点应存储为新分支节点的第 i 个子节点。然后将新节点存储在堆栈中；
• ADD（i）规定，应将堆栈顶部的节点设置为堆栈上位于其下方的分支节点的第 i 个子节点；
• EXTENSION（ext）规定应将堆栈顶部的节点设置为扩展节点（在 geth 中又称 shortNode）的子节点，整个子树的前缀由半字节 ext 的序列表示；
• HASH 是表示子树哈希值的节点。

一些例子

树

假设整个状态由以下 4 个（键，值）对组成：[（0xcafecafe，0x0303030303030303），（0xcafedeca，0x0202020202020202），（0xdeadbee0，0x0404040404040404），（0xdeadbee7，0x0101010101010010101）]

（为清楚起见，键被缩短为 12 个字节，而不是通常的 32 个字节，并且值设置为 8 个字节，而不是大小不受限制）

这些键值对所组成的数据树表示如下：

-图5. 初始树-

证明

我们的证明将是针对两个键 0xcafecafe 和 0xcafedeca 的。不需要用到的两个叶子节点将被转化为哈希值。然后将证明序列化为：

• 节点以深度优先的顺序序列化：

-图6. 证明的节点部分-

• 哈希也按深度优先顺序进行序列化。只有一个哈希值，代表 0xd* 子树
• 用于重建树的指令集：

LEAF
LEAF
BRANCH(14)
ADD(13)
EXTENSION([0xa, 0xf, 0xe])
BRANCH(13)
HASH
ADD(14)

用户现在可以证明他们知道树的当前状态。他们可以将证明发送给中继器或任何想要确保用户知道他们自己状态的人。

重建树

一开始，节点和哈希列表被接受，接着堆栈被初始化为空。

-图7. 重建树过程的初始状态-

让我们跟随这个程序。

\1. LEAF

-图8. 第一个叶子节点被推入堆栈-

\2. LEAF

-图9. 两个叶子节点都在堆栈中-

\3. BRANCH(14)

-图10. 将序列中的节点设为分支节点，然后弹出堆栈顶部的节点，将后者设置为前者的第 14 个子节点。如此组成的子树随后立即被推入栈顶。-

\4. ADD(13)

-图11. 弹出堆栈顶部的两个元素，并添加第二个元素作为第一个元素的第 13 个子元素。结果被推回堆栈。-

\5. EXTENSION([0xa, 0xf, 0xe])

-图12. 将序列中的节点设为扩展节点，扩展节点的前缀为 “0xafe”，然后栈顶的元素成为该扩展节点的子节点。完成操作后，整个子树被推回堆栈。-

\6. BRANCH(13)

-图13. 将序列中的节点设为分支节点，并让栈顶的元素成为其第 13 个子节点。结果再次被压入堆栈。-

\7. HASH

-图14. 哈希从证明的哈希列表中提取并推入堆栈的顶部。-

\8. ADD(14)

-图15. 栈顶的哈希值被添加为树的第 14 个子节点。-

该程序至此终止，并且堆栈的顶部存有树的最终版本。该树与图 6 中的树具有相同的根哈希，并且很简单就能验证两个键均存在。

关联性

以太坊状态数据正在增长。在撰写本文时，状态数据已增长到约占 20 GB（不包括所有索引和其他必要的功能，如加入还需膨胀 10 倍）。对于手机来说，这个量级已经太大了。想让所有人都能访问网络，就必须保证不那么强大的设备也能访问网络。

有了这样的证明方式，用户就可以只存储他们感兴趣的数据，并在他们想与区块链进行交互时证明所有权。这就是所谓的轻客户端。

想深一步，人们可以构想用这种 “无状态” 的方式来维护主链（这一计划与 Serenity 无关），用户只需保存链上状态中跟自己有关的部分，并在需要时发布这些信息。这将有助于阻止状态所需空间的持续增长，并使所有人都能使用以太坊。

为了使证明尺寸较小并能快速处理，仍需要做一些工作，好在让它们变得更加普及也会有助于我们的工作。

致谢

仰赖于 Alexey Akhunov 和 Sina Mahmoodi 的投入和反馈，这篇文章才得以写就。

(完)

原文链接: https://medium.com/@gballet/turboproofs-light-clients-and-saving-private-eth1-487aaa9b386
作者: Guillaume Ballet
翻译&校对: TrumanW & 阿剑

你可能还会喜欢：

干货 | 以太坊无状态客户端初探
观点 | 论状态租金和 Stateless Ethereum
观点 | Vitalik：Eth2 会越来越依赖于轻客户端