北京大学肖臻老师《区块链技术与应用》ETH笔记 - 3.0 ETH数据结构篇

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

3.0 ETH数据结构篇

在以太坊中有三棵树的说法分别是状态树、收据树和交易树。了解了这三棵树就弄清楚了以太坊的基础数据结构设计。而以太坊实现的是一个"平台性"的应用其复杂性必然较高。因此其内部数据结构设计也存在一定复杂度。对此ETH数据结构篇将花费较多篇幅进行编写。

3.1 引入

首先我们要实现从账户地址到账户状态的映射。在以太坊中账户地址为160位表示为40个16进制数。状态包含了余额(balance)、交易次数(nonce)合约账户中还包含了code(代码)、存储(stroge)。

直观地来看其本质上为Key-value键值对所以直观想法便用哈希表实现。若不考虑哈希碰撞查询直接为常数级别的查询效率。但采用哈希表难以提供Merkle proof。Merkel proof用来证明tree里面有什么使用Merkle Tree的另一个目的是使各个节点的状态一致。

3.2 思考如何组织账户的数据结构

我们能否像BTC中将哈希表的内容组织为Merkle Tree这里我个人的理解是把哈希表中的键值对就像交易的内容一样放在叶子节点。比如你和一个人要签合同希望他能证明一下他有多少钱证明账户余额。一种方法是把哈希表组成一个Merkle tree 算出一个根哈希值放在区块头中公布出去根哈希值是正确的就能保证底下的树没用被篡改。但当新区块发布哈希表内容会改变再次将所有的账户状态组织为新的Merkle Tree如果这样每当产生新区块(ETH中新区块产生时间为10s左右)都要重新组织Merkle Tree注意是对账户余额的状态做一个Merkle Tree账户可以是无限的所以这不现实。

那为什么比特币系统就直接用了Merkle Tree比特币系统中是对一个区块中的交易内容进行MT不是整个账户的余额区块包含上限为4000个交易左右所以Merkle Tree不是无限增大的。并且每个区块里的交易信息大多数与上一个区块不一样所以每个区块建立一个Merkel Tree是正常的但是在ETH中账户余额发生变化的仅仅为很少一部分数据我们每次重新构建Merkle Tree代价很大。
那我们不要哈希表了直接使用Merkle Tree每次修改只需要修改其中一部分即可这个可以吗这里我个人的理解是把一个账户地址和其所对应的状态直接放在叶子节点上。但是Merkle Tree并未提供一个高效的查找和更新的方案。此外将所有账户构建为一个大的Merkle Tree必须进行排序Sorted Merkle Tree因为账户如果散乱放在叶节点上那构建的Merkle Tree不唯一那不利于全节点的状态一致性。但是BTC中为什么不用排序因为每个挖矿的节点打包交易的顺序确实不一样但是大家最终会同步获得记账权的节点的块信息当然就不需要排序。如果以太坊也像比特币一样把账户的状态每次在本地组装成一个Merkle Tree放在区块中然后再发布出去首先这样的Merkle Tree的占用量很大其次每次就修改很少的一部分账户余额但还要把所有的账户状态建立树再打包没必要。
那么经过排序使用Sorted Merkle Tree可以吗新增账户由于其地址随机插入Merkle Tree时候很大可能在Tree中间发现其必须进行重构。所以Sorted Merkle Tree插入、删除(实际上可以不删除)的代价太大。

既然哈希表和 Merkle Tree都不可以那么我们看一下实际中以太坊采取的数据结构MPT。

注意BTC系统中虽然每个节点构建的Merkle Tree不一致不排序但最终是获得记账权的节点的Merkle Tree才是有效的。

3.3 一个简单的数据结构——trie(字典树、前缀树)

如下为一个通过5个单词组成的trie数据结构只画出key未画出value

特点

trie中每个节点的最大分支数目取决于Key值中每个元素的取值范围(图例中最多26个英文字母分叉+一个结束标志位)。在以太坊中地址表示成40位16进制16再加上一个结束标志位一共17个分支。
trie查找效率取决于key的长度键值越长查找访问的内存次数就要更多。在以太坊中地址长度为40个16进制的数key值固定是40。以太坊的地址是公钥取哈希截取后面一半得到160位的地址。
理论上使用哈希表可能会出现哈希碰撞意思是两个地址可能不一样但映射到了同一个地方而trie上面不会发生碰撞。
给定输入无论如何顺序插入构造的trie都是一样的。
更新操作局部性较好。

那么trie有缺点吗它的缺点是存储浪费。很多节点只存储一个key但其“儿子”只有一个出现一脉单传的情况过于浪费对于一些节点需要进行合并。因此为了解决这一问题我们引入Patricia tree/trie。

3.4 Patricia trie(Patricia tree)

Patricia trie就是进行了路径压缩的trie。如上图例子进行路径压缩后如下图所示

需要注意的是如果新插入单词原本压缩的路径可能需要扩展开来。那么需要考虑什么情况下路径压缩效果较好树中插入的键值分布较为稀疏的情况下可见路径压缩效果较好。比如有几个单词很长的时候。

那在以太坊系统中路径是否稀疏呢160位的地址存在2^160 种该数实际上已经非常大了和账户数目相比可以认为地址这一键值非常稀疏。为什么要这么稀疏呢防止账户碰撞比地球爆炸的概率还要小。 因此我们可以在以太坊账户管理种使用Patricia tree这一数据结构但实际上在以太坊种使用的并非简单的PT(Patricia tree),而是MPT(Merkle Patricia tree)。 把普通指针换成哈希指针。

3.5 Merkle Tree 和 Binary Tree

区块链和链表的区别在于区块链使用哈希指针链表使用普通指针。同样Merkle Tree 相比 Binary Tree也是普通指针换成了哈希指针。

所以以太坊系统中可如此将所有账户组织为一个经过路径压缩和排序的Merkle Tree其根哈希值存储于block header中。