MPT 中对 key 的编码

MPT中涉及到了三种编码，分别为keybytes编码、Hex编码和Compact编码。

keybytes 编码

这种编码格式就是原生的key字节数组，大部分的Trie的API都是使用这边编码格式。

Hex 编码

当 [k,v] 数据插入 MPT 时，它们的 k(key)都必须经过编码。这时对 key 的编码，要保证原本是 []byte 类型的 key 能够以 16 进制形式按位进入 fullNode.Children[]，因为 Children[] 数组最多只能容纳 16 个子节点。相应的，Ethereum 代码中在这里定义了一种编码方式叫 Hex，将 1byte 的字符大小限制在 4bit(16 进制)以内。

先来看 Hex 编码的实现，Hex 编码的基本逻辑如下图：

Hex.png

很简单，就是将 keybytes 中的 1byte 信息，将高 4bit 和低 4bit 分别放到两个 byte 里，最后在尾部加 1byte 标记当前属于 Hex 格式。这样新产生的 key 虽然形式还是 []byte，但是每个 byte 大小已经被限制在 4bit 以内，代码中把这种新数据的每一位称为 nibble。这样经过编码之后，带有[]nibble 格式的 key 的数据就可以顺利的进入 fullNode.Children[] 数组了。

节点被加载到内存里面的时候key使用的是这种编码，因为它的方便访问。

Hex 编码虽然解决了 key 是 keybytes 形式的数据插入 MPT 的问题，但代价也很大，就是数据冗余。典型的如 shortNode，目前 Hex 格式下的 Key，长度会变成是原来 keybytes 格式下的两倍。这一点对于节点的哈希计算，比如计算 hashNode，影响很大。所以 Ethereum 又定义了另一种编码格式叫 Compact，用来对 Hex 格式进行优化。

Compact 编码（Hex-Prefix Encoding 16进制前缀编码）

Hex-Prefix Encoding (16进制前缀编码)，是一种将任意长度的nibble(4bit为一个nibble) 编码成byte数组的方法，也就是将最小粒度为4bit的数组编码成最小粒度为8bit数组。

以太坊黄皮书中Hex-Prefix Encode原文介绍：

HP.png

重点是理解其中各符合的定义：x是一个nibble数组，t是标志位，用以标志节点类型。

在以太坊协议中，不管是地址还是hash，都是一个16进制串，如"0x5b3edbcf7d0a97e95e57a4554a29ea66601b71ad"，数据最小的表示单位为一位16进制，如1、a等，但在编程实现中，数据的最小表示单位往往是byte（8bit，2位16进制数），这样在用byte来表示一串奇数长度的16进制串时会出现问题，如"5b3"和"5b30"，直接转成byte都是5b30。Hex 编码简单直观，"5b3"->"050b03"，这种方式虽然简单，但是数据量会翻倍，不利于大量hash的计算，同时也会增加tree的大小，降低同步性能。Hex-Prefix Encoding能解决这些问题。

Compact.png

如上图所示，

Compact 编码首先将 Hex 尾部标记 byte 去掉，然后将原本每 2 nibble 的数据合并到 1byte；

如果输入 Hex 格式字符串有效长度为偶数，增添 1byte 在输出数据头部以放置 Compact 格式标记位00100000(叶子节点偶数)/00000000(扩展节点偶数)；

如果输入 Hex 格式字符串有效长度为奇数，将 Hex 字符串的第一个 nibble 放置在标记位 byte 里的低 4bit,并增加奇数位标志 0011xxxx(叶子节点奇数)/0001xxxx(扩展节点奇数)。

扩展节点且nibbles数量为偶数，prefixes为0，二进制为:0000;
扩展节点且nibbles数量为奇数，prefixes为1，二进制为:0001;
叶子节点且nibbles数量为偶数，prefixes为2，二进制为:0010;
叶子节点且nibbles数量为奇数，prefixes为3，二进制为:0011;
关于节点类型见以太坊MPT数据结构介绍。

节点放入数据库时候的key用到的就是Compact编码，可以节约磁盘空间。