以太坊源码（一）Merkle-Patricia Trie(MPT)的实现 这篇文章讲的比较清楚，参考了他的文章，对decoding.go进行了解读，内容查看备注信息。
以下除代码外的文字描述内容转载自上述文章
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 编码的基本逻辑如下图：
image.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 编码，它的主要意图是将 Hex 格式的字符串恢复到 keybytes 的格式，同时要加入当前 Compact 格式的标记位，还要考虑在奇偶不同长度 Hex 格式字符串下，避免引入多余的 byte。
image.png
如上图所示，
- Compact 编码首先将 Hex 尾部标记 byte 去掉，然后将原本每 2 nibble 的数据合并到 1byte；
- 增添 1byte 在输出数据头部以放置 Compact 格式标记位00100000；
- 如果输入 Hex 格式字符串有效长度为奇数，还可以将 Hex 字符串的第一个 nibble 放置在标记位 byte 里的低 4bit,并增加奇数位标志 0011xxxx。
节点放入数据库时候的key用到的就是Compact编码，可以节约磁盘空间。
trie/encoding.go源码
encoding.go主要处理trie树中的三种编码格式的相互转换的工作
作者：duanyu
链接：https://www.jianshu.com/p/1e7455d00065
來源：简书
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。
这个代码很好理解，结合测试用例测试一下，就能很清楚的理解了。
package trie
import (
"fmt"
)
// 将HEX转化为Compact格式
// 1.若存在标志位，则去掉标志位，并且设置terminator为1（叶子节点），否则为0（扩展节点）
// 2.若HEX为奇数位，则叶子节点buf[0]:0011xxxx，扩展节点：buf[0]:0001xxxx，其中xxxx为hex[0]即第一个nibble字节
// 2.若HEX为偶数位，则叶子节点buf[0]:00100000，扩展节点：buf[0]:00000000。
// 3.将每两个nibble的数据合并到1byte，返回buf
func hexToCompact(hex []byte) []byte {
terminator := byte(0)
// 如果hex存在标志位，那么terminator置为1，并且去掉标志位
// terminator为1的为叶子节点
if hasTerm(hex) {
terminator = 1
hex = hex[:len(hex)-1]
}
fmt.Println("hex length:", len(hex))
buf := make([]byte, len(hex)/2+1)
// 增添 1byte 在输出数据头部以放置 Compact 格式标记位00100000； 若terminator为0，即扩展节点，buf[0]= 00000000
buf[0] = terminator << 5 // the flag byte
// 如果HEX的长度为奇数，则执行一下步骤
if len(hex)&1 == 1 {
buf[0] |= 1 << 4 // odd flag 叶子节点奇数标志 buf[0] = 00110000 扩展节点奇数标志 buf[0] = 00010000
buf[0] |= hex[0] // first nibble is contained in the first byte 把hex[0]即第一个nibble字节存入buf[0]，buf[0] = 0011xxxx
hex = hex[1:]
}
fmt.Println("buf[0]:", buf[0])
// 将每两个nibble的数据合并到1byte
decodeNibbles(hex, buf[1:])
fmt.Println("buf[0]:", buf[0])
fmt.Println("buf[1]:", buf[1])
fmt.Println("buf[2]:", buf[2])
return buf
}
func compactToHex(compact []byte) []byte {
base := keybytesToHex(compact)
// delete terminator flag
if base[0] < 2 {
base = base[:len(base)-1]
}
// apply odd flag
chop := 2 - base[0]&1
return base[chop:]
}
// 将keybytes转成HEX编码格式
// 1.将keybytes中的1byte信息，将高4bit和低4bit分别放到两个byte里
// 2.在尾部加1byte值为16，标记当前属于Hex格式，
func keybytesToHex(str []byte) []byte {
l := len(str)*2 + 1
var nibbles = make([]byte, l)
for i, b := range str {
nibbles[i*2] = b / 16 //右移四位
nibbles[i*2+1] = b % 16 //取b的右侧四位
}
nibbles[l-1] = 16
return nibbles
}
// hexToKeybytes turns hex nibbles into key bytes.
// This can only be used for keys of even length.
// 将hex格式转换成keybytes格式，智能转换偶数位的key
func hexToKeybytes(hex []byte) []byte {
// 若存在标记位则去除标记为
if hasTerm(hex) {
hex = hex[:len(hex)-1]
}
// 奇数位不能变换
if len(hex)&1 != 0 {
panic("can't convert hex key of odd length")
}
key := make([]byte, len(hex)/2)
decodeNibbles(hex, key)
return key
}
// 将每两个nibble的数据合并到1byte
func decodeNibbles(nibbles []byte, bytes []byte) {
for bi, ni := 0, 0; ni < len(nibbles); bi, ni = bi+1, ni+2 {
bytes[bi] = nibbles[ni]<<4 | nibbles[ni+1]
}
}
// prefixLen returns the length of the common prefix of a and b.
// 返回a,b的共同前缀序号
func prefixLen(a, b []byte) int {
var i, length = 0, len(a)
if len(b) < length {
length = len(b)
}
for ; i < length; i++ {
if a[i] != b[i] {
break
}
}
return i
}
// hasTerm returns whether a hex key has the terminator flag.
// hasTerm 返回一个十六进制的key是否拥有终结符标志
func hasTerm(s []byte) bool {
return len(s) > 0 && s[len(s)-1] == 16
}
网友评论