在讲解改进的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函数的第三段分段函数如下：
公式8其公式定义比较复杂，其本质是对键值对中，key不属于交集的部分，逐个进行RLP封装，当逐个封装是，就是公式9，公式9就与step1的操作不收是一样的了，注意公式7会在后面的例子中讲到。
当公式9执行完成之后，将结果返回给公式8，公式8 的结果返回到公式6然后最后求出来的结果就是最新的Merkle树如下图。
其中C函数的条件3对应的是Branch
Node的设计，条件2对应的Extension Node的设计，本例中extension node也是root
node。条件1对应的是leaf Node的设计，上图中给出了key=”do9”的查找路径，找到leaf
node即可访问其value字段值:”20 wei”
Step3: 当J= {("dog1","40 eth"),("do9","20 wei"),("do91b","5 fin"),("do99c","12 sza")}其Merkle树的结果:
其中需要注明的是红色7的位置，这里就是step2中未涉及到的条件7
本节使用的测试数据：
【1】https://en.wikipedia.org/wiki/Trie
【2】https://en.wikipedia.org/wiki/Radix_tree
【3】https://easythereentropy.wordpress.com/2014/06/04/understanding-the-ethereum-trie/
【4】https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/
【5】https://github.com/ebuchman/understanding_ethereum_trie
【6】http://tool.oschina.net/commons?type=4
网友评论