# 160期【币圈人物】 北大肖臻以太坊的状态树

**Published by:** [币同学](https://paragraph.com/@0x4484c3371eb90c8a9092ec8caecb3dfb3038c818/)
**Published on:** 2022-04-17
**URL:** https://paragraph.com/@0x4484c3371eb90c8a9092ec8caecb3dfb3038c818/160

## Content

你好，我是币同学。这是我分享学习的第160天，每天学习进步一点点。 关键词：北大肖臻老师的公开课，关于以太坊的状态树。 1. 以太坊采用的是基于账户的模式，系统中显示维护每个账户的余额，那以太坊是用什么样的数据结构，来实现这样的模式？ 我们要完成的是什么功能？是账户地址到账户状态的映射。addr→state（账户状态包括： 外部账户和合约账户的状态，包括余额、交易次数nonce；合约账户还包括代码和存储。） 以太坊用的账户地址是160位（bits）的，也就是20个字节，一般表示成40位十六进制的数。 2.trie数据结构，翻译为中文叫字典树/前缀树。 在上述例子中：单词，有可能在trie的中间节点结束。 这个结构有些特点，第一个特点就是在trie当中，每个节点的分支数目取决于key值里，每个元素的取值范围。第二个特点是trie的查找速度，取决于key的长度，key的长度越长，查询需要访问内存的次数就越多。第三个特点就是trie不会出现碰撞。第四个特点就是trie顺序的一致性，只要给定一组输入不变，无论你的输入怎么打乱重新排序，最后插入的trie当中，构成的trie是同一棵树。第五个特点就是更新的局部性是很好的。 trie的缺点：存储有些浪费，像上图中左边一列，都只有一个子节点，一脉单传的情况。如果我们能把这些节点进行合并，能够减少存储的成本，同时也提高了查找的效率。 那么在以太坊里面是什么样的？以太坊地址是表示成40位十六进制的数，所以分叉数目叫做分支因子（branching factor），是17。因为是16进制的，0——f，加上一个结束标志符，所以是17。 3.以上述例子来解释patricia tree/trie这样压缩路径的好处：直观上看，树的高度明显缩短了，这样访问内存的次数就会大大减少，效率就提高了。 键值分布比较稀疏的时候，路径压缩效果比较好。 【注意：对于patricia tree/trie来说，如果新插入一个单词，原来压缩的路径，可能需要扩展开来。】 在以太坊的键值是地址，地址是160位的，所以整个地址的空间有2的160次方（这是一个非常非常大的数）。 以太坊的普通账户，创建的方法和比特币是一样的。没有一个中央的节点，每个用户自己独立创建账户，你在本地产生一个公私钥对，就是一个账户。 那如何防止两个人的账户正好碰撞（产生的一样）？这种可能性是存在的，但是概率其实是微乎其微的。 以太坊当地址足够长的时候，分布足够稀疏，才不会产生碰撞。这可能看上去有点浪费，但这是去中心系统防止账户冲突的唯一办法。 4. MPT（merkle patricia tree） Merkle Patricia Tree（又称为Merkle Patricia Trie）是一种经过改良的、融合了默克尔树和前缀树两种树结构优点的数据结构，是以太坊中用来组织管理账户数据、生成交易集合哈希的重要数据结构。 以太坊中，用到的还不是原生版的MPT，用的叫modified MPT，对MPT结构做一些修改，这些修改不是很本质的修改。如图：这四个地址，前两位的开头都是a7，所以它的根节点就是extension node（即a7） Shared nibble(s)是十六进制数的意思，一个nibble就是一个十六进制数。 地址的第三个数就分开了，有1、7、f。 1的后面只有一个地址，就1355，以此类推。 【注意：如例子中，数的根节点取哈希之后，得到了一个根哈希值，根哈希值要写进块头里。】 这就是一个关于地址余额的状态树。 每次发布新一个新的区块的时候，状态树中有些节点数的值，会发生变化。这些改变，不是在原地改的，而是新建一些分支，原来的状态是保留下来的。上面的例子，是合约账户，有code（代码），还有存储。 合约账户的存储，也是用MPT的方式保存下来的。 例子中，新的区块里交易次数nonce是发生变化了，余额balance也发生变化。 代码code是不变的，所以code hash是指向原来树中的节点。 存储是变了的，但是存储树中的大部分节点也是没有改变的，只有底下的一个节点---整数变量从29变成了45。 以太坊系统的全节点，维护的不是一颗MPT，而是每次出现一个区块，都要新建一个MPT。只不过这些状态树中，大部分的节点是共享的。只有少数发生变化的节点，需要新建分支。 5. 出现一个新的区块，为什么要新建一个MPT？举个例子，如下图以太坊有智能合约，以太坊的智能合约是图灵完备的，编程功能是很强的。从理论上说，可以实现很复杂的功能，它与比特币中简单的脚本还不同。所以以太坊中，如果不保存前一个的状态，智能合约执行完之后，不可能再推算出前面是什么状态。所以要想支持回滚，必须保存历史状态。 6. 以太坊代码的数据结构图7. 状态树中保存的是（key，value），key就是地址，目前上述的内容主要指的是键值，地址的管理方式。 value，是要经过一个序列化的过程（RLP：recursive length prefix），用编码做序列化之后再做存储。 特点是简单，越简单越好。 今天就学习到这里，明天见。

## Publication Information

- [币同学](https://paragraph.com/@0x4484c3371eb90c8a9092ec8caecb3dfb3038c818/): Publication homepage
- [All Posts](https://paragraph.com/@0x4484c3371eb90c8a9092ec8caecb3dfb3038c818/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@0x4484c3371eb90c8a9092ec8caecb3dfb3038c818): Subscribe to updates