本文探讨了 KV-witness 区块见证数据方案的解析算法、优缺点，以及网络效率等方面。

原文标题：《引介 | 无状态性：基于键值对的见证数据方案》 撰文：Igor Mandrigin 翻译：阿剑

无状态以太坊运动当前提议了一种区块见证数据（witness）的格式，详述见此处。这套区块见证方案是基于操作码（opcode）的，你可以理解为一种小型的编程语言，可以使用少数几个命令来生成 「默克尔多值证明」

本文研究了另一种区块见证数据的建构方法，它基于一个键值对的列表，语义也更简单。

在本文中我将尝试回答下列问题：

见证数据方案需满足的）前提：

所有的区块见证数据方案都必须满足下列要求：

这一部分我先讲讲键值对见证格式的语义，还不会谈到具体的数据布局（byte layout）。

后面，我再讲解我用在测试中的数据格式。

见证数据的数据体由两个元素构成：

1. 数据

「键」（key）可以是：账户的地址，storage key 或者 code key；而 「值」（value）可以是：账户、storage item 或者相应的代码分块（code chunk）。这一部分的数据体与用于验证正确性的默克尔树的格式完全无关。而且，即使用其它方式来验证正确性，这一部分也不会改变。

2. 证据

键是默克尔路径，而值是一个哈希值。证据的形式依赖于状态树的格式，所以十六进制树和二进制树下的证据将有所不同。这一语义使得我们能在同一个见证中包含多种类型的多值证明。所以，理论上来说，我们可以创建出一种既能支持十六进制状态树、又能支持二进制状态树的见证数据格式。

数据体按 key 的字典顺序排序、存储，以确保：

对比一下键值对见证格式与当前的操作码见证格式的优缺点。

优点：

缺点：

我们首先必须证明这种格式能够实现正确性。它必须能执行以太坊主网上的所有区块。

为此，我在 turbo-geth 代码库的一个分支里面实现了这种见证方案：kv-witness-research。

这一实现是在谷歌云里面测试的，执行的是块高从 500 万到 800 万的以太坊主网区块。

你需要至少 200 GB 的可用硬盘空间，和至少 32 GB 的内存（因为代码还在概念验证阶段，没怎么优化）。

1）复制 turbo-geth 客户端（commit 号为 aa6b4dc609b3d871c778597a71ac08601f17de53）的 kv-witness-research 分支

2）同步主网的区块头和区块体：go run ./cmd/geth --syncmode staged --datadir ~/stateless-chaindata/ （我花了一天时间）

3）以同步所得的数据运行无状态客户端的原型（我花了 17 天）

如此，在 stats_kv_witness.csv 文件中，你就能得出跟我在本文中所示的一模一样的结果。

见证数据的开头是一个单字节的数据头（header），包含其版本信息。

然后就是数据体（body），由大小信息和元素（elements）本身组成；大小信息会占用 1～4 个字节，具体要看元素的数量。

每一个元素都以一个字节的类型（type）开头，然后是键（key）字段，是一个长度任意的字节数组；键字段的前缀是大小信息，然后是实际数据（就像数据体的布局一样）。

数据的形式取决于元素的类型：

以账户为键的数据则更复杂一些，但主要的数据包括：

最终，见证数据看起来会长这样：

键是一个由半字节（nibble）组成的默克尔路径，不是由字节组成的。对于十六进制默克尔树而言，一个半字节的长度是 4 个比特，对二进制默克尔树来说则是 1 个比特。因此，有时候键的字节长度并不是整数（举个例子，12 比特是 8.5 个字节）。

键被编码为 []byte，这样就是字节对齐的（所以如果有一个键的长度在 4 个字节到 5 个字节之间，它总是会被补齐为 5 个字节）。同样地，可以加入一个额外的 「面罩」 在开头，指明在最后一个字节中，哪些比特是 1。

然后，我们可以加入一个简单的优化措施，减少数据和证据中的重复前缀 。

为提高压缩效率，我们会在同一个有序映射中混合数据和证据。

数据头的前 4 个比特将用来说明前一个键的字节偏移量（The highest 4 bits of a header byte mean a byte offset of a previous key.）。

因为在我们的语意中，键是排过序的，我们可以使用前 4 个字节来说明下列情况：

本结果的原始数据可以在此 GitHub 仓库 中找到。

为了在网络效率角度得出一个全面的图景，我比较了 3 种见证数据格式，统一用十六进制默克尔树来运行：

1）基于操作码的见证数据，就是现有的这个。（数据沿用自我的上一次实验）

2）基于键值对的见证数据（未压缩）：没有删除重复的键前缀

3）基于键值对的见证数据（压缩后）

测试的范围是区块高度从 500 万到 800 万的区块。

绝对大小比较

量化分析

删除重复的键前缀为 KV witness 带来了相当大的提升。有了这个功能，它与基于操作码的方案的带宽消耗就几乎相同了。

而基于键值对的方案还有许多优点。

最重要的优点是：简洁。为一种数据格式（本质上就是一个字典）撰写详述，要比为一个几乎是编程语言一样的方法撰写详述简单得多。

第二大优势是，证据在语义上与数据是独立的，所以，当我们想要改变状态树的形式（从十六进制转为二进制）、或者想要完全改变证据的机制时，KV-Witness 方法所需的变更要小得多。

我认为，KV-witness 方案是见证数据标准的有力竞争者。