以太坊源码解读-第3.1讲-trie原理介绍

前言

了解以太坊的同学都知道，以太坊中有三大重要的状态：账户状态、交易状态、收据状态（不要问小编它们有什么用-_-）。这三大状态怎么保存，怎样保证这些信息的安全？这就离不开我们这次要讲的以太坊trie模块了。

它提供了一种强大的数据结构Merkle Patricia Tries，我们亲切的称它为MPT。正是它维护着我们的这三种状态，让整个以太坊平稳有序的进行着。
看到这么强大的东西，是不是经不起诱惑了？那我们就快来解刨吧。

这篇文章主要是讲阅读trie模块源码前要掌握编码以及节点原理，具体源码的解析请看小编的另一篇文章：以太坊源码解读-第3.2讲-trie模块源码解读

MPT的前世今生

• MPT是这三种结构的组合：Trie，Patricia Trie，Merkle tree。每一种都非常经典，为了更好的了解以太坊，小编专门整理了三篇文章，值得一读（依次从上往下读）：
  浅谈标准Trie树（字典树）
Patricia树介绍
Merkle Tree（默克尔树）算法解析
  正是这三种树的进一步柔和，才有了今天以太坊上大名鼎鼎的MPT。
• MPT是什么，它相比上面有什么优势？建议大家看看小编整理的这篇文章：
  Merkle Patricia Tree (MPT) 以太坊merkle技术分析

注意，上面这篇文章只是宏观上的介绍，MPT也只是大概讲讲是什么样的逻辑，能有个大概映像。具体细节，小编后面再详细介绍。

MPT中的编码概念

MPT中会涉及到三种编码：KEYBYTES encoding、HEX encoding、COMPACT encoding，每种编码在特定场合都有其重要的作用，小编曾尝试通过网络中的相关文章来了解这些编码是怎么生成的，但无奈啊，这些文章一个比一个写的复杂，一堆数学公式和专业术语，越看越看不懂。。。
终于，小编还是看完源码后，弯回来，自己来解释下这三种编码具体是怎么实现的。毕竟，了解了这些基础后，再看源码就会容易很多。吸取以前看的文章的不足之处，这次小编一定讲的通俗易懂：

KEYBYTES encoding

这就是原生的字节，没有添加任何防腐剂：go语言中的byte,长度为8，范围是0～255。二进制表示的话，就是00000000~11111111。
也就是说，一串普通数据通过KEYBYTES encoding编码后，就是由很多byte组成的一个byte[]数组，也就是我么说的字节数组。
这个编码搞开发的应该都懂，不难理解。

HEX encoding

我想，把它称为半字节编码(nibble)更好一些，具体细节一会儿讲。
在内存中，这种编码访问会更容易，不要问为什么，小编也不知道。。。涉及到硬件效率相关，貌似是因为16进制更容易计算。
具体这种编码是怎么实现的？这块小编重点讲讲。
用KEYBYTES encoding编码（上面有讲，就是go中普通的byte）转为hex编码的过程来演示，大家可能会更容易理解，先看代码演示：

//申明一个byte数据t，值为249，这个t可以理解为就是`KEYBYTES encoding`编码数据
//它将会被转为`hex`编码
var t byte = 249

//为了方便演示这里加一个l变量，表示t的长度为1，也就是总共一个字节
var l = 1  
//hex编码t总共会用到的空间大小
l := 2*l + 1  
//开辟l大小的空间，传说中的nibbles
var nibbles = make([]byte, l)  
//将s的高4位存入nibbles的第一个字节
nibbles[0] = s / 16
//将s的低4位存入nibbles的第二个字节
nibbles[1] = s % 16
//nibbles的最后一位存入标示符，代表这个是hex编码
nibbles[l-1] = 16
fmt.Println(nibbles)

最后输出编码为hex的结果nibbles：

[15 9 16]  //原先数据的高4位保存位15，低4位保存位9，16表示该hex编码是通过KEYBYTES编码转换的

代码里有些地方是不是还很懵逼？小编来解释一下：

• hex编码的目的是：
  要将一个原始字节数组byte[]，其中的每个byte都拆分位高4位和低4位，分别放在同为字节数组的nibbles[]中（bibbles的数组长度为原始字节数组的2倍再加1）。其中依次高4位放在nibbles[]的偶数位，低4位放在nibbles[]的奇数位，最后一位设置为16（二进制表示00010000），表示这个hex编码是通过KEYBYTES编码转换的。

• 还不懂？小编继续换种方式解释：

  • 先记住：一个byte的长度为8，范围是0～255。二进制表示的话，就是：00000000~11111111。
  • 要将byte值为249的数据转为hex编码，首先将249转为二进制表示：11111001，看清楚，高4位是1111，低4位是1001
  • 249除以16得到的值为15，15的二进制表示是：1111，看清楚了吗？这就是249的高4位，
  • 249除以16得到的余数为9，9的二进制表示是：1001，看清楚了吗？这就是249的低4位，
  • 249的长度为l=1，因此nibbles[]字节数组的长度为2*l+1=3，就是说，hex编码需要用3个byte才能表示了原来的249，nibbles的偶数位nibbles[0]存入249的高4位00001111，nibbles的奇数位nibbles[1]的低4位存入249的低4位00001001,最后一位nibbles[2]存入16（也就是二进制00010000）,发现了吗？hex中的每一个byte都表示一个16进制数。
  • 因此249最终hex编码结果为：[00001111,00001001,00010000]，也就是[15 9 16]
  • 这下该懂了吧，再不懂就只能弯回去再读几遍了。。小编自认为对这个hex编码的解释算是很仔细啦。。

• 小编还要补充的重要内容是，很重要，否则很难理解COMPACT encoding编码：

  • KEYBYTES encoding编码的数据转成HEX encoding的编码的数据后，该byte[]最后一个是一定有后缀的，值为16，并且除去后缀后，剩余的编码长度为偶数。具体看上面的解释。
  • hex中两个连续byte表示原始数据的一个byte。
  • 但是小编从以太坊源码中了解到，hex字节数组如果不是经过KEYBYTES encoding编码得到的，可能会有前缀(姑且这么称呼)这么一个东西，具体生成的hex结果会分为如下几种情况：
    1. hex字节数组长度为奇数，最后一个是后缀，标记为16，此时无前缀这。种就是前面所讲的经过KEYBYTES encoding编码得到的。
    2. hex字节数组长度为奇数，最后一个不是后缀，此时会认为hex字节数组的第一个是其的前缀。
    3. hex字节数组长度为偶数，最后一个是后缀，此时hex字节数组的第一个一定是其前缀。
    4. hex字节数组长度为偶数，最后一个不是后缀，并且无前缀

  ps:截止目前为止，小编依旧不知道hex的这个前缀是怎么生成的，为什么要有。。。如果有哪个小伙伴了解，可以留言分享一下。

COMPACT encoding

这种编码也就是黄皮书里讲的Hex-Prefix Encoding编码，可以看作是HEX encoding编码的另一种形式，在磁盘存储数据的时候，会节省磁盘空间。
既然都说了它是HEX encoding编码的另一种形式，也就是说，COMPACT encoding是通过HEX encoding转换实现的，转换后，会节省将近一半的磁盘空间。
思前想后，换了N种方式，最终小编认为，还是得先通过数学公式来理解什么是COMPACT encoding编码。

数学公式定义

这是黄皮书中给出的公式，耐心看，不复杂。

\begin{split} HP(x,t):x \in \mathbb{Y} &\equiv \begin{cases} &(16f(t),16x[0]+x[1],16x[2]+x[3],...)\ \ \ \ if\ ||x||\ is\ even \\\ &(16(f(t)+1)+x[0],16x[1]+x[2],16x[3]+x[4],...)\ \ \ \ otherwise \end{cases} \\\ f(t) &\equiv \begin{cases} &2\ \ \ \ if\ \ t = 1 \\\ &0\ \ \ \ if\ \ t = 0 \end{cases} \end{split}

解释一下公式的意思：

1. ||x||表示求x的长度，在源码中，x表示一个字节数组byte[]，也就是hex编码。
2. HP(x,t)代表的就是最终COMPACT encoding编码后的结果，其中的t，黄皮书中原本定义的是$t=0和t \neq 0$两种情况，但是结合源码，小编将其改为t=0和t=1这两种情况，这样更容易理解。
   因为，源码中是这样实现的：当hex有后缀的时候，则t=1，否则t=0。
3. $\mathbb{Y}$根据hex的长度是偶数(even)还是奇数(odd)，划分为两种集合。每种集合中的第一个数据，代表的是COMPACT encoding编码的前缀，它包含了转换回hex编码所需要的信息。
4. $\mathbb{Y}$每种集合中的第二个数据开始，你会发现全是16x[i]+x[i+1]这种样式，这在二进制中，其实就是高4位和低4位组成一个byte 8位的过程1。如下图（为了画个像样的图，小编专门学axure。。。）：

COMPACT encoding大体就是这样子，理解了吗？不理解的继续看看后面的代码实现。

代码实现

来看一下hex编码是怎样转换为COMPACT编码的（先知道，hex是有前缀的，前面提到过）,要对着上面公式看：

// 测试案例，将hex编码{1,2,3,4,5}转换成Compact编码，并输出
func TestHexToCompact(t *testing.T) {
	testBytes := []byte{1, 2, 3, 4, 5}
	fmt.Print(hexToCompact(testBytes))
}

//用于hex编码是转换为COMPACT编码
func hexToCompact(hex []byte) []byte {
	terminator := byte(0) //初始化一个值为0的byte，它就是我们上面公式中提到的t
	if hasTerm(hex) { //验证hex有后缀编码，
		terminator = 1  //hex编码有后缀，则t=1
		hex = hex[:len(hex)-1]  //此处只是去掉后缀部分的hex编码
	}
	//Compact开辟的空间长度为hex编码的一半再加1，这个1对应的空间是Compact的前缀
	buf := make([]byte, len(hex)/2+1) 
	
	//这一阶段的buf[0]可以理解为公式中的16*f(t)
	buf[0] = terminator << 5 
	if len(hex)&1 == 1 { //hex 长度为奇数，则逻辑上说明hex有前缀
		//这一阶段的buf[0]可以理解为公式中的16*（f(t)+1）
		buf[0] |= 1 << 4 
		//这一阶段的buf[0]可以理解为公式中的16*（f(t)+1）+ x[0]
		buf[0] |= hex[0]  
		hex = hex[1:] //此时获取的hex编码无前缀无后缀
	}
	decodeNibbles(hex, buf[1:]) //将hex编码映射到compact编码中
	return buf  //返回compact编码
}


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] //这个过程就是16x[i]+x[i+1]的过程
	}
}

最后输出的Compact编码结果为：

//17为compact前缀
[17 35 69]  

大伙这下该理解Compact编码是怎么实现的了吧？要还有什么疑问，就请大家留言吧。。

总结一下

在以太坊中，KEYBYTES encoding不会直接转位COMPACT encoding，需要先经过HEX encoding。
三种编码中，目前以太坊只支持如下转换：

• KEYBYTES encoding转HEX encoding
• HEX encoding转KEYBYTES encoding
• HEX encoding转COMPACT encoding
• COMPACT encoding转HEX encoding

MPT树的形成原理

MPT的节点的形成等细节，网上很多文章讲的都很模糊，对于初学者很难理解，小编当初也是半天没看懂，最终还是看了源码后才真正了解是怎么一回事。也因此打算以自己的方式举个例子来好好解释下这些细节。
我们假设要将4个交易信息：A、B、C、D存储在MPT中，需要经过以下一系列操作。这四个交易信息，假设分别如下：
A的交易信息内容：i am a
B的交易信息内容：i am b
C的交易信息内容：i am c,i am not d
D的交易信息内容：i am d,i am not c

1. 将源数据序列化

为了便于传输，A、B、C、D这四个交易信息的数据是需要先使用rlp进行序列化的，它们经过序列化后分别为如下结果：
A_Serialize：[134 105 32 97 109 32 97]
B_Serialize：[134 105 32 97 109 32 98]
C_Serialize：[145 105 32 97 109 32 99 44 105 32 97 109 32 110 111 116 32 100]
D_Serialize：[145 105 32 97 109 32 100 44 105 32 97 109 32 110 111 116 32 99]

2. 为序列化后的数据源生成hash并将其转为hex编码

在MPT中，其实是在操作经过hex编码的hash(32位)。因此上面序列化后的数据，需要做如下两部分操作：

• 生成hash（均为32位长度）：
  A_Hash：[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 134 105 32 97 109 32 97]
  B_Hash：[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 134 105 32 97 109 32 98]
  C_Hash：[0 0 0 0 0 0 0 0 0 0 0 0 0 0 145 105 32 97 109 32 99 44 105 32 97 109 32 110 111 116 32 100]
  D_Hash：[0 0 0 0 0 0 0 0 0 0 0 0 0 0 145 105 32 97 109 32 100 44 105 32 97 109 32 110 111 116 32 99]
• 对上面这些hash进行hex编码（内存运算效率高），依据hex编码原理，最终结果每个都是65位长度：
  A_Hex：[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 6 6 9 2 0 6 1 6 13 2 0 6 1 16]
  B_Hex：[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 6 6 9 2 0 6 1 6 13 2 0 6 2 16]
  C_Hex：[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 1 6 9 2 0 6 1 6 13 2 0 6 3 2 12 6 9 2 0 6 1 6 13 2 0 6 14 6 15 7 4 2 0 6 4 16]
  D_Hex：[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 1 6 9 2 0 6 1 6 13 2 0 6 4 2 12 6 9 2 0 6 1 6 13 2 0 6 14 6 15 7 4 2 0 6 3 16]

3. 生成MPT树

前两步准备ok，接下来我们就要生成这颗MPT树了。讲多少遍也不如画一张图，我们先把这颗MPT树画出来，然后再来解释

从图中我们可以看出MPT的节点分为四种：根节点、分支节点、扩展节点、叶子节点，下面我们来详细解释一下这些节点的作用：

• 根节点
  根节点不存有任何信息，是一颗空节点
• 扩展节点
  是<K,V>类型的节点，这节点中，K是hash的公共部分，就比如上面的A_Hex、B_Hex、C_Hex和D_Hex它们每个hash值从开始处，0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 共28个0是公共一致的，因此图中最上面的分支节点key就是这个公共部分;而V则是一个指针，会指向分支节点或者叶子节点。
• 分支节点
  这个节点中有17个字段，其中前16个中，分别存有16进制从0～f中的一个字符，而这每一个字符所处区域，又指向hash非公共区域的起始位置，这块靠文字解释很难解释清楚，建议大家直接看图吧。
  而第17个字段则存储在此处截止的节点信息，比如有三个key,分别是 (abc ,abd, ab) 第17个字段储存了ab节点的值。这块还有一些细节小编也还没搞懂，等后期了解后，再调整。
• 叶子节点
  存储的是rlp编码后的原始数据，这个同样看图，文字很难说明，小编最初也是看各种文章文字解释，越解释越乱。

小编想补充说明的是，在MPT中，除了叶子部分存有真实的数据，其余部分存储了完整的数据校验信息，只要获取到非叶子部分的MPT树，就可以进行如下几个操作：

• 下载某个hash对应的数据块
• 校验下载的数据块是不是真实的

看图，因为从根节点到叶子节点前，可以获取到一个完整的hash。

另外，只要节点中某条路径下新增或者删除节点，整条路径的节点都会被重新实例化，然后重新插入db。

本节总结

本节使用一个案例，介绍了生成一棵MPT树的基本流程，这为我们后续在代码中理解整个过程打下了非常好的基础。

MPT轻节点

引出

上面的MPT树，有两个问题：

• 每个节点都包含有大量信息，并且叶子节点中还包含有完整的数据信息。如果该MPT树并没有发生任何变化，并且没有被使用，则会白白占用一大片空间，想象一个以太坊，有多少个MPT树，都在内存中，那还了得。
• 并不是任何的客户端都对所有的MPT树都感兴趣，若每次都把完整的节点信息都下载下，下载时间长不说，并且会占用大量的磁盘空间。

解决方式

为了解决上述问题，以太坊使用了一种缓存机制，可以称为是轻节点机制（名词是小编瞎编的），大体如下：

• 若某节点数据一直没有发生变化，则仅仅保留该节点的32位hash值，剩下的内容全部释放
• 若需要插入或者删除某节点，先通过该hash值db中查找对应的节点，并加载到内存，之后再进行删除插入操作

图示轻节点

根据上述，一棵长时间没有发生变化的MPT树，它内存应该是一棵轻节点树，如下图所示：

是不是很惊讶，root节点指向一个只有hash值的节点，该hash表示的是完整节点中MPT中root指向的那个节点本身的hash。

轻节点中添加数据

内存中只有这么一个轻节点，但是我要添加一个数据，也就是要给完整的MPT树中添加一个叶子节点，怎么添加？大体如下图所示：

删除和获取

delete、get操作与上面的添加数据过程类似，小编就不讲了

全文总结

本文需要了解中的三种编码，以及MPT树的形成原理、MPT轻节点的原理。
小编的初衷是为了更通俗的解释一些比较理论的概念，若有不合适的地方，大家可以留言，小编会及时改进的。

Donate