以太坊mpt树检验

Ⅰ 以太坊解读——Recursive Length Prefix协议图解(上)

在以太坊中，采用了一种名为Recursive Length Prefix(RLP)的方法对交易、账号、合约等基础的数据结构进行序列化处理，从而实现对链上数据的网络传输和持久化存储。RLP作为最为底层的编码方法，其重要性是不言而喻。因此，网上介绍RLP的文章也不少，但是由于RLP是二进制编码，又涉及到嵌套结构，造成编码过程的可读性较差，在学习中过程中，也一直没有找到完整的、易于理解的说明，总是绕在各种规则之中，且不能"自拔"，着实有点无奈。所以，在本文中，采用图形化的解释和举例的方法，帮助大家理解RLP嵌套等特点、编解码过程等。

和其他的序列化协议不同，RLP只支持两种数据类型：
1）byte数组，可以是二进制数组，当然也可以是字符串；
2）byte数组的数组，也就是列表。并支持列表内的嵌套。
对于其他的数据类型，RLP都不支持，需要用户自己先转化为数组和列表的类型。

从RLP的命名中就可以看出两个关键字：一个是递归Recursive和前缀Prefix。首先，关于递归，也就是嵌套结构，结构上非常接近“树”，在Ethereum WiKi中，更是直接地采用树的items来进行命名，叶子节点(leaf tress)来存储“byte数组”，嵌套的节点就是一个树的分叉(branching trees)。

比如，需要是对如下对象进行RLP的编码，该对象中包含一个字符数组的列表、一个单个字符的字符数组、一个空字符数组。

< <[cat],[dog]>, [0xbf], [] >

将该对象展开为树的结构，就如下图。其中[0xbf]和[]属于字符数组。<[cat], [dog]>属于列表，可以嵌套展开，再根据各个节点，进行编码。然后，对于不同长度的数组和列表，编码的方法略有不同，这个也就是Length Prefix相关的内容，和“编码过程”相关的内容，在第二节进行详细地说明。

关于为什么以太坊需要单独设计一种序列化协议，目前还没有找到官方的描述。但与其他序列化方法相比，RLP协议具有一些直接的优点，比如：

1）在以太坊中，最小货币单位为1 Wei，并且1 ETH = 10^18 Wei，所以在编码中，需要考虑对很大的整数类型的序列化，在RLP中采用去除前导零(leading zero)的大端big-endian方式，可以有效处理大整数；

2）使用了灵活的长度前缀来表示数据的实际长度，并且使用递归的方式能编码相当大的数据；

3）为了实现在链上节点的“共识Consensus”，防止出现数据的不一致，以太坊中并不支持浮点数类型，所以一般的序列化协议也不适用。

编码的过程就是将嵌套结构(nested sequence)的树形结构，添加长度前缀(Length Prefix)后，转化为顺序结构(flat sequence)的过程。添加长度前缀的目的，就是在反序列化时，可以根据长度前缀(Length Prefix)，将(flat sequence)重构出树的结构(nested sequence)。

关于前缀的生成规则，《Ethereum Yellow Paper》[2]给出了非常形式化的数学符号描述，漂亮是非常漂亮，可惜不是人类的语言，非常难于理解和表达。网上大部分文章的写法也是引用了Yellow Paper中的5个文字形式上的描述，把原文和翻译一并给出如下：

将上面这个“长度”Length Prefix的编码规则，通过“决策树”可以图形化的表达如下图。

首先，根据编码的类型，进行分类，分为“字节数组”和“列表”两类；第二，根据不同的长度，编码的长度前缀不同。若待编码对象的长度小于56，就是把长度和“前缀字符”进行求和，占用一个字节。反之，待编码对象的长度大于56，其前缀需要多个字节，第一个字节，求出“长度”所占的字节数，再加上“前缀字符”，比如：长度为56，占用1字节。然后对“长度”进行编码，其实也是一个嵌套的过程。

还是以上文中的例子，该编码对象，已经完成了“树的构建”，然后根据“长度前缀”的原则，对树的各个项目进行长度前缀的计算。

< <[cat],[dog]>, [0xbf], [] >

-对于<[cat],[dog]>属于嵌套数组，需要对内部各项非常进行长度编码的计算
  `对于[cat]，属于字符数组，且长度为3，其对应的长度为0x80+3 = 0x83
  `对于[dog]，属于字符数组，且长度为3，其对应的长度为0x80+3 = 0x83
  `<[cat],[dog]>整体上，其长度前缀为0xc0 + 2(新增的两个子项的长度所占用的字节)+6(待编码字符的长度)=0xC8
- 对于[0xbf], 属于字符数组，且长度为1，其对应的长度为0x80+1 = 0x81
- 对于[dog]，属于字符数组，且长度为3，其对应的长度为0x80+3 = 0x83
- 对于[]，属于字符数组，且长度为0，其对应的长度为0x80+0=0x80
总体上，增加的“长度编码”的字节数为6，加上原来的长度为10，所以整个对象的长度前缀为0xC0+16d=0xD0。所以最后的编码结果为：
D0 C8 83636174 83646F67 81B7 83646F67 80

解码过程将在 《以太坊解读——Recursive Length Prefix协议图解(下)》 一文中，给出图形化的解读说明。

Ⅱ 以太坊技术系列-以太坊数据结构

本篇文章和大家介绍一下以太坊的数据结构，上篇文章我们提到，以太坊为了实现智能合约这一功能，使用了基于账户的模型。我们来看看以太坊中数据结构。

既然是基于账户的模型，我们需要通过账户地址找到账户的状态。就像通过银行卡号可以找到你在银行中的各种信息一样。最简单的想法当然是一个简单的哈希表 key是账户地址 value是账户状态。但这里有个问题解决不了。

轻节点如何校验账户合法性？

上篇我们说过，区块链中有2类节点，全节点和轻节点，轻节点只会存储block header，所以轻节点如何才能校验账号是否合法呢？

这个思路和我们平时用的md5校验一致，我们会对区块内的信息进行hash运算从而得出区块内信息唯一确定的值，区块链所有节点中这个值都是相同的。

在这个过程中我们用到了一种数据结构Merkle Tree（哈希树），我们先看下Merkle Tree（哈希树）的示意图。

上篇文章说到区块链中的链表(哈希链)和我们平时常见链表不同的是将指针从地址改为了hash指，这里也一样，哈希树和二叉树的区别有2个

1.将地址改为了哈希值

2.只有叶子节点存储数据

回到之前的问题轻节点是如何校验1个账户或交易是否是在链上的呢？

整个流程如上图所示

1.轻节点需要判断1个账号是否合法

2.轻节点由于只存储block header，所以拿到1个账号的时候会向全节点发出请求

3.全节点存储了所有账户状态，将账户路径中的需要计算用到的hash值返回给轻节点

4.轻节点本地进行计算根hash值，如果计算结果和自己存储一致则账户合法，不一致则不合法。

那以太坊中的账户信息的数据结构就是这样吗？

直接用这样的数据结构来存储账户信息会有2个问题

查找困难

生成hash值不确定

第1个问题应该比较容易发现，在这个树中寻找1个账号需要的复杂度是O(n),因为没有任何顺序。

第2个问题其实也是因为无序导致的，无序的组合每个节点针对同一批账户生成的hash值不一致，这就导致无法达成共识。

既然2个问题都和顺序有关，那我们类似二叉排序树一样，使用哈希排序树是不是就可以解决问题了呢？

使用排序树后会带来另外1个问题

插入困难

因为要维持树是有序的，很可能带来树结构的很大变动。

以太坊中使用了另外一种数据结构字典树。和哈希树不同，字典树应该是很多地方都有使用。我们简单来看下字典树的结构。

字典树能够较好地解决哈希树的2个缺点1.查找困难 2.生成的hash值不确定以及排序二叉树的1个缺点 插入困难。

但字典树我们可以看到可能树的深度可能由于部分元素导致整棵树深度非常深。

这时我们可以进一步优化，将相同路径进行压缩。这就是压缩字典树。

将哈希树和压缩字典树结合，就可以得到以太坊存储账户的最终数据结构-MPT。

将压缩字典树里面的指针从地址改为指针，并且将数据存储在叶子节点中即可。

介绍完状态树的数据结构，我们接下来讨论1个问题，区块中存储的账户状态是什么样的范围。有2种选择。

只保存当时区块中产生交易的账户状态。

保存全局所有的账户。

我们可以看下这2种方式，无非就是空间和时间的平衡，只保存当前区块产生的交易意味着是做懒加载(需要的时候才去寻找账户)，在区块链中这个代价是非常大的，因为寻找的账户之前从未交易过，这样会遍历整个区块链。另外一种保存全局的账户方式虽然看起来空间消耗较大，但查找快捷，而且空间的问题我们可以通过其他方式优化。所以最终以太坊选择了第2种每个区块都报错全局所有账户的方式。

我们来看下以太坊中是如何保存状态树的。

可以看到以太坊中虽然每个区块都保存了全部账户，但是会将未发生变化的账户状态指向前1个节点，本身只存储发生变化的状态，这样可以较大程度优化空间占用。

介绍完以太坊中比较复杂的状态树后，我们继续来看看以太坊中的另外两棵树，交易树和收据树。

首先介绍一下，为什么需要交易树&收据树。

1.交易树

虽然以太坊是基于账户的模型，但是就像银行不仅会存储银行卡的余额，还会存储卡中的每笔钱怎么来的以及怎么花的。交易树中就存储着当前区块中的包含的所有交易。

2.收据树

由于智能合约的引入增加了不少复杂性，所以以太坊用收据树存储着一些交易操作的额外信息。比如交易过程中执行日志就包含在收据树中方便查询。收据树和交易树是一一对应的。每发生一次交易就会有一次收据。

和状态树不同交易树和收据树只维护当前区块内发生的交易，因为当时区块发生交易时不需要再去查找另外1个交易，也就之前需要可能遍历整个区块链的查找操作了。

由于以太坊中的出块速度较快，我们进行一些查询一些符合条件交易的时候会面临大量数据遍历困难的问题。收据树中引入了布隆过滤器可以帮助我们有效缓解这一困难。

布隆过滤器将大集合中每个元素进行hash运算映射到1个较小的集合，这时再来1个元素要判断是否在大集合的时候，不需要遍历整个大集合，而是去进行hash运算去小集合中寻找是否存在，如果不存在，肯定不在大集合中，如果存在则不能说明任何问题。

如上图所示，布隆过滤器只能证明某1个元素不在集合中，不能证明1个元素在结合中。

以太坊中如果我们要在较多区块中寻找某1个交易，则可以利用布隆过滤器，过滤掉肯定不存在目标交易的区块，然后进入收据树内继续利用布隆过滤器筛选，剩下的才是可能的目标交易的交易，进行一一比对即可。

我们介绍了以太坊的核心数据结构，状态树&交易树&收据树，他们都是使用相同的数据结构-哈希压缩字典树。但状态树是维护1颗全局账户树，交易树和收据树则是维护本区块内的交易或收据。

介绍完数据结构后，后面我们会用几篇文章来介绍以太坊中的一些核心算法，比如共识机制，挖矿算法等。

Ⅲ 006：MPT与RLP|《ETH原理与智能合约开发》笔记

待字闺中开发了一门区块链方面的课程：《深入浅出ETH原理与智能合约开发》，马良老师讲授。此文集记录我的学习笔记。

课程共8节课。其中，前四课讲ETH原理，后四课讲智能合约。
第二课分为三部分：

这篇文章是第二课第二部分的学习笔记：MPT与RLP。

MPT，Merkle Patricia Tree，结合了Merkle Tree（默克尔树）和 Patricia Tree（帕特里夏树）的一种数据结构。
RLP，Recursive Length Prefix，一种编码方法。

这是两个非常重要的数据结构，在以太坊的区块和交易中都有用到。

先分别介绍一下Merkle Tree 和 Patricia Tree。
Merkle Tree 和 Patricia Tree Merkle Tree 和 Patricia Tree
默克尔树的解释：对每一个交易计算其散列值（Hash），再对两个散列值求他们的散列值。如果是奇数个，就把最后一个重复一次。最后得到的一个散列值就是默克尔树根的值。如图，交易1、1、2、3的散列值分别是HASH0、HASH1、HASH2、HASH3。HASH0和HASH1结合在一起计算散列值得HASH01，HASH2和HASH3结合在一起计算散列值得HASH23，接下来HASH01、HASH23结合在一起，计算散列值得HASH0123。

采用默克尔树的好处是可以方便的判断一个交易是否在区块中。

Patricia Tree，可称为压缩前缀树。如上图右半部分。相同的前缀在同一分支中，后面一同的部分分叉出来，如test和toast，都有相同的t，est和oast在两个分支中。

这个结构的好处是节省空间，因为每一级的键值可以是多个字符。

了解了Merkle Tree 和 Patricia Tree后，再来看这两者混合后的产物——MPT。
这里的原理知识单独来看不易理解，和具体的例子结合起来才更容易理解，此处先放上课件截图。在后面的例子中再做说明。
Merkle Patricia Tree 规格 Merkle Patricia Tree 规格
在MPT中，还涉及到三个小的编码标准。主要规则如图。下面结合两个例子说明一下。
三个编码标准 三个编码标准
HEX编码的例子：从ASCII码表中可以查出，b的十六进制编码为62，o的十六进制编码为6F，F在十六进制中就是15的意思。因为这是个叶子节点，最后加上0x10表示结束，也就是16。所以最后的编码为[6 2 6 15 6 2 16]

HEX-Prefix编码的例子：[6 2 6 15 6 2 16]，将其最后的0x10去掉，[6 2 6 15 6 2]。前面补一个四元组，其中（倒数）第0位是区分奇偶信息的，[6 2 6 15 6 2]是偶数位，第0位是0；第1位是区分节点类型的，这是叶子节点，第1位是1。所以这个四元组就是0010是2。“如果输入key的长度是偶数则再添加一个四元组0x0在flag四元组之后。”，所以，最终的前缀是0x20。本例最终的结果，[32 98 111 98]，即[0x20, 0x62, 0x6F, 0x62]

下面是综合性的例子，通过它可以很方便地理解前面的理论知识。值得多看几篇，仔细休会。

初始的key-value对为：

其中，<>中的数据为key的16进制编码。
MPT.jpg MPT.jpg
因为4组数据都有公共的6，所以这个节点的值为6，长度为1，奇数；节点类型：扩展节点；所以前缀就是0001，即1。

这是个扩展节点，它的值是一个Hashvalue，它指向一个分支节点。Hashvalue，具体指的是分支节点RLP编码的结果的散列值。（RLP见下小节）

分支节点。上面4组数据的第2位是4和8两种情况。在4的位置上存的是下面的扩展节点的散列值，在8的位置上存的是下面的叶子节点的散列值。

叶子节点。以68开头的只有一个了。所以这个节点上的四元组就是6f727365了。它是偶数位。前缀是0x20（同前文HEX-Prefix编码的例子）。这个叶子节点的value值为'stallion'。

扩展节点。在64之后，公共的部分是6f，这个扩展节点的key即为6f，前缀为0000，即00。这个扩展节点的value存放的是一个hashvalue，指向下一个节点，一个分支节点。

分支节点。646f已经表达完，这个节点的value值就是646f对应的值，'verb'。

除此之外，646f之后就是6，所以在这个分支节点的6位置上有一个散列值，指向下一个节点。

扩展节点。在646f6之后，公共的部分是7，其长度为1，奇数。所以前缀为0001。这个节点的value是一个散列值，指向下一个节点。

分支节点。646f67已经表达完，这个节点的value值就是646f67对应的值，'puppy'。

除此之外，646f67之后就是6，所以在这个分支节点的6位置上有一个散列值，指向下一个节点。

叶子节点。key为5，value为'coin'。长度为1，奇数，前缀0011，即3。

整个分析过程结束。可结合上图和前文的理论多加复习。

这小节也是理论性较强，通过例子可以方便理解。先放上课件，再根据我的理解举更多的例子。同样，学习方法也是理论和例子配合学习。其中，list的例子在下篇文章的上机实验部分再列举。 RLP的编码标准 RLP的编码标准 再举几个例子 再举几个例子

Ⅳ 以太坊架构是怎么样的

以太坊最上层的是DApp。它通过Web3.js和智能合约层进行交换。所有的智能合约都运行在EVM（以太坊虚拟机）上，并会用到RPC的调用。在EVM和RPC下面是以太坊的四大核心内容，包括：blockChain, 共识算法，挖矿以及网络层。除了DApp外，其他的所有部分都在以太坊的客户端里，目前最流行的以太坊客户端就是Geth（Go-Ethereum）