以太坊中MPT树的key值三种编码

MPT树的key值三种编码

1. Raw编码(原生字符)
2. Hex编码(扩展的16进制编码)
3. Hex-Prefix编码(16进制前缀编码)

Raw编码

原生的key值，不做任何改变。这种编码方式的key，是MPT对外提供接口的默认编码方式。

• 例如：key:”cat” value:”dog” Raw编码[‘c’,’a’,’t’]→ASCII的表示方式就是[63,61,74]

Hex编码

将原key的高低四位分拆成两个字节进行存储，Hex编码用于对内存中MPT树节点key进行编码

从Raw编码向Hex编码的转换规则是：

1. 将Raw编码的每个字符，根据高低4位拆成两个字节
2. 若key对应的字节在真实数据项(叶节点)，则末尾加一个ASCII值为16的字符作为终止
3. 若key对应的存储是另一个节点的哈希索引(扩展节点)，则不加任何字符。
   • 例：key:”cat” value:”dog” C的ASCII为63 → 00111111

HP编码

为了在持久化数据库中区分叶子/扩展节点，在存库之前，对key进行转换，从Hex转到HP,HP编码规则如下：

1. 若原key的末尾字节的值为16(即该节点是叶子节点)，去掉该字节
2. 在key之前加一个字节，原本key长度为奇，最低为为1；若为叶节点，低2位为1
3. 若key原本长度为奇，再加一个半字节
4. Hex扩展的逆过程

###实际编码过程

1. 若存在标志位，则去掉，设置terminator为1，否则为0
2. 若Hex为奇数位：
   • 叶节点 buf[0] → 0011xxxx
   • 扩展节点 buf[0] → 0001xxxx
   • 其中xxxx为hex[0]，即第一个nibble字节
3. 若Hex为偶数位，则叶节点buf[0] → 00100000，扩展节点buf[0] → 00000000

---

• ← Previous Post
• Next Post →