以太坊技术黄皮书学习笔记3：改进的Merkle Patricia

2018-05-16 本文已影响200人西二旗李老师

在讲解改进的Merkle树之前，需要先解释一下16进制开头的编码算法：

这个算法比较简单，就是将半字节序列拼装成字节序列。根据序列的长度和是否存在结束符分成4中情况，其中表达式7，8最后一个半字节16表示结束符，在计算x的长度算法中忽略不计。示例已经很清楚了解释了整个流程，不再过多解释，以太坊代码有兴趣的可以自行查找：

改进的Merkle Parricia树—Trie的定义：

首先表达式1是对TRIE的输入数据的定义，首先输入的数据是一个序列，序列的元素是key-value对，而key和value的取值都是B即字节序列。为了方便表达，把key-value对用I表示，I0表示key I1表示value。

有时key会被用半字节来表示，因此将一个序列J转换成半字节表示的函数y(J)的定义为公式2，这个公式的作用就是根据规则将key的字节序的每个字节拆成2个半字节。示例如下:

公式3，4，5给出了Trie的精确定义，首先我们看公式3，我们对C函数的返回结果进行KEC加密运行可以得到Trie运算的结果。

公式5给出了C函数的精确定义，首先它是个分段函数，而每个分段函数中用到了其他几个子函数和之前将到的RLP封装和HP编码。我们逐个分析其操作方式对于不同的输入J，其运算过程和结果以示例的方式来解释。

当J={}时，即输入是一个空集合时候，TIRE给出了自己的特殊定义:

当输入不为空，则根据公式5，给出3种情况，每种情况都对应以太坊对Merkle

树的改进，第一种情况公式6是对普通叶子节点的处理，第二中情况公式7是对扩展节点的处理，第三种情况是分支节点的处理，叶节点是在很多树形状的数据结构经常用到的内容，扩展节点和分支节点是以太坊为了提高访问速度和节省存储大小对Merkle树进行的改进。下面我们会一一讲解。

Step1:只有一个键值对J={“alice1”,”40 eth”}

首先根据公式1，我们先描述了输入域的值，只有1个键值对。然后根据公式2在前面讲解过，把属于的key转换成可以用于计算hash树根的格式，即key属于Y:半字节结合。根据J的长度为1这个条件，使用公式3，4，首先计算key的HP运算的结果。在公式4中结束符标志t是true，因此f(t)

= 2, k'0的长度为12，是个偶数，运用前面的知识，我们首先计算出key的HP值。

在计算完key的HP值之后，可以用于RLP的算法，将此此键值对序列化。公式6是上一节的知识，不再详细解释。公式7也是在上一节中也有过详细讲解，这一段主要是将key的HP序列号。公式8是讲value序列化。这些都是上一节的只是，并不需要多解释，需要解释的是，我们的示例是讲字符串键值对进行保存，所以需要根据ASCII码表【6】去查询这些字符串的字节码值。公式9也是上一节的只是，||s(x)||=15,没有超过56，因此根据上一节的知识。将所有结果串联之后得到一串字节码序列.我们发现对于至于1个键值对的情况，这个字节码序列就是我们尽心hash运算的对象了，对得到的结果如公式10.具体值太长

0x1b1f569b5f27c6160298a9d56d0084b24424c13622526f7a285644b3f9ca2f67

此时Merkle树的数据结构如下图:

Step2:在Step1的基础上增加一个键值对("alice9":"20

wei"),

则J的长度变成了2，我们可以理解键值对是一个个增加的，因此我们可以在Step1的基础上执行增加操作，就可以得到新的Merkle树。但是为了方便证明，我们把J的key和value都设计短些，对J重新定义:{(“dog1”,”40

eth”),(“do9”,”20 wei”)}

公式1和2只是定义输入范围并将属于数据的key转换为半字节集群。当执行公式3时，J的长度是2，已经不能使用条件一下的序列化公式，只能比较另外2个条件，对于条件2，本质上是寻找多个KEY之间相同字符最大结合。公式4找到了两个key的共同集合然后继续调用公式5。在公式6中，条件1和2已经都不满足，只能看C函数的第三段分段函数如下：