以太坊代码的数据结构

以太坊采用基于账户的模型。 系统明确维护每个账户的余额。 今天我们就来看看用什么样的数据结构来实现账本分类账。

需要完成的功能：

从账户地址到账户状态的映射

地址 -> 状态

addr：账户地址，以太坊中使用的账户地址为160位，即20个字节，一般表示为40个十六进制数（0~f）。

state：外部账户和合约账户的状态，包括余额、交易次数、合约账户、代码、存储等。

那么应该设计什么样的数据结构来实现这种映射呢？

数据结构假设

以下是一些可供考虑的选项：

假设一：用哈希表实现

直观上，就像典型的键值对一样，给定一个账户地址，需要找到对应的账户状态。

于是一个直观的想法：用哈希表来实现。

系统中的所有节点都维护一个哈希表。 每有一个新的账户，就插入到哈希表中，直接在哈希表中查询账户余额。 如果不考虑哈希冲突，基本上查询的效率是在常数时间内完成的，更新也很容易在哈希表中更新。

>>> 问题：如果使用这个哈希表，如何提供默克尔证明？

比如你要跟一个人签合同，希望他能证明他有多少钱，你怎么提供证明？

一种方法是将哈希表中的元素组织成Merkle树，然后计算出一个根哈希值，存储在区块头中。 只要根哈希值正确，就可以保证底层树不会被篡改。

如果发布新区块怎么办？

新区块包含一个新交易。 执行这个事务必然会改变哈希表的内容。 下一个区块发布时，哈希表的内容会不会重新组织成Merkle树？

价格太高了。 事实上，只有一小部分账户状态真正发生了变化，因为只有那个区块关联的账户会发生变化，而大部分账户的状态是保持不变的。 所以每次重建Merkle树，成本都非常高。

比特币系统不是每出现一个区块就需要重建一棵默克尔树吗？ 为什么没有问题呢？

Merkle树就是将区块中包含的交易组织成Merkle树。 每发布一个新的区块，都会为区块中的交易发出一系列新的交易。 因此，比特币中的 Merkle 树是不可变的。 第一次发布一个新的区块对应一棵Merkle树，之后Merkle树构建完成后不会改变，下次发布新的区块构建新的Merkle树。

该区块中有多少笔交易？ 最大约4000个（按1M字节计算，每笔交易约250M字节），这其实是一个上限，很多区块的交易数根本达不到4000个，很多区块只有几百个，甚至可能更少，所以每出一个块，就在比特币中建一棵默克尔树，由这几百到几千笔交易组成一棵默克尔树。

如果采用这种方法，这里会发生什么？

就是把所有以太坊账户一起组成一个Merkle树，比刚才说的成百上千笔交易要高几个数量级，相当于每出一个块就遍历所有账户去建立一个Merkle树，下次再出块，再遍历一遍所有的账户，然后建一棵Merkle树。

这棵Merkle树除了提供Merkle证明来证明账户里有多少钱之外，还有一个很重要的作用，就是保持所有节点之间状态的一致性。 如果没有根哈希值，就发不出去，每个节点在本地维护一个数据结构，那你怎么知道你的数据结构的状态和别人的数据结构的状态是否一致呢？ 所有节点必须保持相同的状态。 这就是比特币为什么要将根哈希值写在区块头中的原因，即所有全节点必须就当前区块中包含哪些交易达成共识。

>>> 结论：不可行，因为每次构建Merkle树的成本太高

如果每个全节点在本地都维护一个哈希表，那么当需要构建Merkle树时，构建Merkle树，然后将根哈希值发送到区块头，这种方法就不行了。 哈希表本身的效率是相当不错的，插入和更改的效率都很好，但是每次构建Merkle树的成本太高了。

假设2：直接用一个Merkle树，把所有的账户都放进去

不用哈希表，直接用一个Merkle树把所有的账户都放进去，想改的时候直接在Merkle树里面改。 因为每个区块只更新一小部分账户，所以只改变了一小部分默克尔树。

>>> 问题一：默克尔树没有提供高效的搜索和更新方式

比特币的默克尔树是如何构建的？

最底层是tx，然后hash值放在上层节点，两两组合，然后取一个hash向上调整。

他没有提供快速查找和更新的方法。

>>> 问题2：直接把账户放到Merkle树里，Merkle树要不要排序？

排序的 Merkle 树

如果不排序会怎样？

1、搜索速度会变慢。

2.还有一个问题。 这些账户组成了默克尔树，叶子节点就是这些账户的信息。 如果不指定这些账户在叶子节点中出现的顺序，那么这样构建的默克尔树就不是唯一的。

比如系统中有很多全节点，每个全节点按照自己的顺序构建一棵Merkle树。 自己决定的，最后构建的Merkle树不一样，计算出来的根哈希值也不一样

比特币里面的节点也是没有排序的，那为什么比特币没有问题呢？

由于比特币中各个全节点收到的交易顺序也不一样，理论上构建的默克尔树的根哈希值也不一样。

但在比特币中，每个节点在本地组装一个候选区块，由节点决定将哪些交易按什么顺序打包到区块中，然后通过挖矿来竞争记账权。 如果他不夺取记账权，其他人就不需要知道他的任何决定； 只有他有记账权，而区块发布后，最终会成为一个被所有人接受的区块，那么这个顺序就是区块发布的顺序。 节点确定。

也就是说，虽然比特币中没有排序好的默克尔树，但它的顺序是唯一的，由发出区块的节点决定。

那么为什么以太坊不能这样做呢？

如果以太坊也这样做，则需要在区块中发布账户状态。 也可以说是每个全节点决定如何把账户组织成Merkle树，计算哈希值，挖矿，但是怎么让别人知道顺序，你得在区块里公布。 但公布的是所有账户的状态，而不是交易。 两者相差几个数量级。 比特币只需要几百/几千笔交易就可以发布一个区块。

>>> 结论：不可行，没有排序的Merkle树也不可行。

交易必须发布，不发布别人无法知道，但可以在本地维护账户状态，大部分账户状态保持不变。 一个区块中的交易只能更改少量账户。 大多数帐户保持不变并重复发布。 每十秒发布一个新区块，所有状态打包发布。 超过十秒再发布是不可行的。

假设3：使用Sorted Merkle tree >>> 问题：如何添加新账户

一个账户的地址是随机生成的，它的叶子节点的位置很可能是插在中间的，那么这些树的结构就得改变。

创建一个新帐户，并进行外部交互。 我需要将它添加到我的数据结构中。 确实如此，但问题是，这个加法的成本是多少？

可能需要重构一半以上的 Merkle 树，代价太大了。

>>> 结论：不可行。 使用 Sorted Merkle 树，插入和删除的成本太高。

而且区块链是不可篡改的，就是说加东西容易，删东西难。

事实上，以太坊中并没有明确删除账户的操作。 有的账号只有一点钱，一两微，删不掉。

以上解决方案均无效。

以太坊的数据结构

那么以太坊采用的方法就是使用一种叫做MPT（Merkle Patricia Tree）的结构。

说这个之前，先说一个简单的数据结构。

【特里】

源自“retrieval”，检索。

trie：字典树，前缀树。

它也是一个键值数据对。 一般来说，字符串更多地用于键。 例如，一些单词被排列成一个 trie 数据结构。

例子：

一般的

genesis（区块链的第一个区块称为创世区块，Genesis block）

去

上帝

好的

下图是一个trie结构。 这些词都是以G开头，然后第二个字母开始分裂，左边是E，右边是O。 左边的前两个字都是N和E，然后下面Separate，R和S，然后是最后三个字母，右边的分支，分支O，Go就结束了，从这里我们可以看出word可能在trie的中间节点结束以太坊合并后怎么获得新币，然后左边是D，右边是D O，左边变成God，右边变成Good。

Trie 树可以使用字符串的公共前缀来节省存储空间。

如果系统中存在大量的字符串，而这些字符串基本没有共同的前缀，对应的trie树就会消耗大量的内存，这也是trie树的一个缺点。

Trie的特点 Feature 1: trie的每个节点的fork数取决于key value中每个元素的取值范围

在这个例子中，each是一个英文单词，并且是小写的，所以每个节点的分叉数最多为26，再加上一个结束标志（表示单词到此结束）。

比如英文字母的字典树是26点树，数字的字典树是10点树。

在以太坊中，地址用40个十六进制数表示，所以分支因子为17（十六进制为0~f，加上结束标志）。

特征2：trie的搜索率取决于key的长度

键值越长，查找所需的内存访问次数就越多。

在这个例子中，不同的单词键值有不同的长度。

在以太坊中，所有密钥都是 40，因为地址是 40 位十六进制数。

比特币和以太坊的地址不是通用的，两个地址的格式和长度都不一样。

但是有一点是相似的，以太坊中的地址也是通过公钥转换得到的。 其实就是获取公钥的hash，然后前面的部分就不要了，只要需要后面的部分，就会得到一个160bit的地址。

特点3：只要两个地址不同，就一定映射到树中的不同分支，所以trie不会碰撞

特点4：不同的节点，不管这些账户的插入顺序如何，最终构建的树都是一样的

至于前面提到的Merkle树，如果不排序的话，一个问题就是账户插入Merkle树的顺序不一样，得到的树结构也不一样。

尝试呢？

比如上图中的五个词，如果按照不同的顺序插入到树中，结果会不会是不同的树呢？ 其实都是一样的，只要给定的输入不变，不管输入如何打乱和重新排列，最后插入到trie中，得到的树都是一样的。

特点五：更新操作的局部性很好

每次出块时，系统中大部分账户的状态都保持不变，只有少数受影响的账户会发生变化，因此更新操作的局部性非常重要。

特里地方呢？

比如上图中，我想更新genesis的key对应的value（这张图中只画了key，没有画value）。 我只要访问genesis的分支，其他的分支不需要访问，也不需要遍历整棵树。

轮胎的缺点：储存浪费

例如，左分支只有一个子节点。 对于这种single-pass的情况，如果可以合并节点，可以降低存储成本，也可以提高搜索效率。 您不需要一次一个地搜索。

然后介绍了Patricia树，也有人写成Patricia trie，是一种通过路径压缩的前缀树，有时也叫压缩前缀树。

【帕特里夏树】/【帕特里夏树】

如果路径被压缩，就会变成下图这样。

可以看到E和O还是在G下面分叉，接着是NE，然后E和S分叉，然后都连在一起，右边是一样的。

这种压缩有什么好处？

直观上，这个高度明显缩短，访问内存的次数会大大减少，效率会提高。

注意：对于Patricia tree，如果插入了新词，可能需要对原有的压缩路径进行扩展。

比如这个例子，如果加了geometry，左边的分支就不能那样压缩了。

路径压缩在什么情况下效果更好？

当键值分布比较稀疏时，路径压缩效果较好。

例如，在这个例子中，使用了英文单词。 假设每个词都很长，但是总共没有多少词。

例如：

误解

权力下放

disintermediation (to middlemen, disintermediation) (中间人：中间人)

这三个词插入一个普通的trie中就变成了下图这样

可以看出这样的结构效率比较低，基本就是一条线。

如果使用帕特里夏树，请参考下图

这棵树的高度明显提高了。

因此，当键值分布比较稀疏时，路径压缩效果较好。

以太坊应用中键值稀疏吗？

以太坊应用中的关键值是地址，地址是160位，地址空间有2^160，这是一个非常非常大的数字。

如果你给一个计算机程序设计一个算法，他需要进行的计算次数是2^160，这是我们所有人一生中不可能计算出来的，而世界上的以太坊账户数量远少于此大，与这个数字相比，简直是小巫见大巫。

为什么要弄得这么稀疏，而不是缩短地址长度，这样访问效率更快，而且没必要这么稀疏呢？

以太坊普通账户的创建方法与比特币相同。 没有中心节点，每个用户独立创建一个帐户。 你在本地生成一对公私钥，就是一个账号。

那么如何防止两个人的账号碰撞，导致相同呢？

这种可能性是存在的，但这种可能性比地球爆炸还要小。

如何做到这么小的概率，就是地址要足够长，分布要足够稀疏，防止碰撞。

这可能看起来很浪费，但这是去中心化系统防止账户冲突的唯一方法。

所以他是非常稀疏的，这也是数据结构中使用Patricia树的原因。

【MPT】(Merkle Patricia树) >>> Merkle树和二叉树的区别

即区块链与普通链表的区别：普通指针被哈希指针代替。

>>> Merkle Patricia树和Patricia树的区别

它还将普通指针替换为散列指针。

所有账户组织成一棵帕特里夏树，利用路径压缩提高效率，然后用哈希指针代替普通指针，这样就可以计算出一个根哈希值。 这和哈希值也写在块头中。

比特币的区块头中只有一个根哈希值：交易树，它是由区块中包含的交易组成的默克尔树组成的根哈希值。

以太坊的区块头中存在三个根哈希值：交易树、状态树、收据树。

现在我们正在谈论状态树。 账户状态最终组织成一棵 Merkle 树，即它的根哈希值。

这个根哈希值的作用： 1.防止篡改

只要根哈希值保持不变，整棵树的任何部分都不能被篡改，也就是说每个账户的状态都可以保证没有被篡改。

2.默克尔证明

(1) 可以证明账户余额

你账户所在的分行作为Merkle证明向上发送给轻节点，轻节点可以验证你账户里有多少钱。

(2) 可以证明账户不存在

前面提到过，Sorted Merkle 树的功能之一就是证明非成员性。

这里的证明方式类似于Sorted Merkle树。

例如，在向某个地址转账之前，验证该账户信息是否存在于全节点中。 说白了就是证明MPT中的某个键值不存在。

如果存在，它在哪个分支上？ 发送这个分支作为 Merkle 证明可以证明它不存在。

改进的MPT

以太坊中使用的不是原来的MPT，而是Modified MPT，就是对MPT做一些修改，这些修改不是很本质的修改。

例如（如下图），有四个账户（右上角）。 为了简单起见，地址相对较短。 假设只有 7 位地址而不是 40 位地址。 账户状态只显示余额，其他账户状态不显示。 第一个账户有45个ETH，第二个账户只有1WEI（这是以太坊最小的计量单位，1WEI基本可以忽略不计）

在此示例中，存在三种类型的节点。

1.扩展节点

如果这棵树发生路径压缩，就会有一个Extension Node。

这四个地址的前两位都是同一个a7，所以它的Root（根节点）是一个Extension Node。

shared nibble（nibble：十六进制数，一个半字节就是一个十六进制数），这里的共享半字节是a7

2.分支节点

这里隔开第三个数字，有1、7、f，所以跟在一个Branch Node后面。

3.叶节点

先说1。 在这个 1 之后是 1355。只有这个地址跟在 Leaf Node 之后。

这个7有两个地址，连接到路径压缩d3。

然后3和9分开，后面跟着一个Branch Node。

下面两个叶子节点都是7。

最后一个 f 后面是叶节点 9365。

这是状态树。

另外，将树的根节点哈希后得到的根哈希值写入区块头（左上角）。

他还使用散列指针。 比如7的位置，这里存放了后面的节点（扩展节点）的hash值。 如果是普通指针，位置7存放的是后面节点的地址。

每发布一个新区块，状态树中某些节点的值就会发生变化。 这些改动并不是原地改动，而是创建了一些分支，原来的状态其实是保留下来的。

在下面的示例中，有两个相邻的块。

Block N Header：State Root是状态树的根哈希值，状态树如下图（灰色）。

Block N+1 Header：这是新区块的状态树。

可以看出，虽然每个区块都有一棵状态树，但是两棵树的大部分节点是共享的。

右边的树主要指向左边树的节点，只有那些发生变化的节点才需要创建新的分支。

在这个例子中，这个账户是一个合约账户，因为有Code和Storage。

合约账户的存储也由 MPT 保存。

这个存储其实就是一个Key Value Store，维护着这个变量到这个变量的值的映射。 在以太坊中，也使用 MPT。

所以以太坊中的这个结构是一个大的MPT，里面包含了很多个小的MPT，每个合约账户的存储都是一个小的MPT。

在上图中账户的新区块中：

随机数已经改变。

Balance余额也发生了变化。

Code不变，所以Codehash指向原树中的节点。

存储变了（下面的存储称为存储树），存储树中的大部分节点没有变。 本例中只有一个节点发生变化，整型变量从29变为45，因此新建了一个分支。

因此，系统中每个全节点需要维护的不是MPT，而是每出现一个区块，就必须创建一个新的MPT。 然而，在这些状态树中，大多数节点是共享的，只有少数节点出现。 改变的节点需要创建一个新的分支。

Q：为什么保留历史状态，为什么不直接原地改？

系统有时会出现分叉，临时分叉很常见。

在以太坊将出块时间缩短到十几秒后，这种临时分叉是常态，因为区块在互联网上传播可能需要十几秒。

假设有分叉，两个节点同时获得记账权（如下图）。

这两个分叉终于赢了上一个，下面的分叉节点怎么办？

这时候就需要回滚（roll back）了。 就本节点的当前状态而言，接受需要取消后续节点的状态，返回到上一个节点的状态，然后沿着上链继续前进。

有时可能需要将当前状态返回到之前未处理本区块交易的状态。

那么如何实现回滚呢？

就是为了维护这些历史记录。

这与比特币不同。 如果是比特币的话，它的交易类型比较简单，有时候通过这种逆向运算就可以推算出之前的状态。

比如在一个简单的转账交易中（如下图），A转10个BTC给B，这对账户余额有什么影响？

A的账户少了10个比特币，B的状态多了10个比特币。

如果这个状态要回滚，回到之前的状态，那么B账户会减10个比特币以太坊合并后怎么获得新币，A账户会加回10个比特币。

回滚一个简单的转账交易其实是比较容易的。

为什么不在以太坊？

因为以太坊有智能合约。

智能合约是图灵完备的，编程功能很强。 理论上可以实现非常复杂的功能，这和比特币的简单脚本是不一样的。

因此，如果之前的状态没有保存在以太坊中，智能合约执行后，就无法计算出之前的状态。 因此，为了支持回滚，必须保存历史状态。

以太坊代码数据结构一、区块头结构

ParentHash：父块的哈希值。 是区块链中前一个区块的哈希值，而不是区块头的哈希值。

UncleHash：叔块的哈希值。 后面讲到Ghost协议的时候，每个区块还有一个叔块。 正如你稍后会看到的，奇怪的是，大多数人似乎认为 ParentHash 和 UncleHash 是同一代的，但在以太坊中并非如此。 这位叔叔可能比父母大很多。

Coinbase：就是挖出这个矿的这个区块的矿工地址。

-------- 下面三个是本讲相关的三棵树的根哈希。 以太坊中一共有三棵树：状态树、交易号和收据树。

Root：状态树的根哈希。

TxHash：交易树的根哈希值（类似于比特币中的根哈希值）。

ReceiptHash：收据树的根哈希。

Bloom：提供高效的查询，满足一定条件的交易的执行结果（收据树相关）。

Diffculty：挖矿难度（根据需要调整）

---------- GasLimit 和GasUsed 与gas 费用有关。 智能合约会消耗 gas 费用，类似于比特币中的交易费用。

GasLimit：单个区块允许的最大gas量

GasUsed：交易消耗的gas总量

时间：区块的大概生成时间

--------MixDigest和Nonce是和挖矿过程相关的。

nonce：是挖矿时猜测的随机数（类似于比特币挖矿）。 在以太坊挖矿还需要猜测很多随机数。 写入区块头的随机数是最后找到的，满足难度要求。 的

MixDigest：混合摘要，经过一些计算后从nonce随机数中计算出一个hash值。

2. 块状结构

与本课更相关的是前三个域：header、uncles、transactions

header：是指向区块头的指针

uncles：是指向叔块头的指针。而且是一个数组，因为一个块可以有多个叔块

transactions：是这个区块中的交易列表

当这个区块上线发布的时候，就是这些信息被发布了，实际上就是上面的前三项实际上被发布了。

在状态树中存储值：RLP

状态树中保存的是(key, value)

关键是地址。 讲到这里，主要讲的是key值，这个地址的管理方式。

那么这个值，这个账户的状态，是如何存储在状态树中的呢？

实际上，它要经过一个序列化（RLP）过程，然后存储。

RLP：Recursive Length Prefix，递归长度前缀，是一种序列化方法。 它的特点是简单和极简，越简单越好。

Protocol buffer：简称Protobuf，是一个著名的序列化库。

与这些库相比，RLP的理念是越简单越好。

它只支持一种类型：nested array bytes，nested array bytes。 一个字节的数组可以嵌套。

以太坊中的所有其他类型，比如整数，或者更复杂的哈希表，最终都会变成嵌套的数组字节。

所以，实现RLP比实现protocol buffer要简单的多，因为他不做难的事情，把它们推到应用层。