# 161期【币圈人物】 北大肖臻以太坊的交易树和收据数

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

## Content

你好，我是币同学。这是我分享学习的第1天，每天学习进步一点点。 关键词：北大肖臻老师的公开课，关于以太坊的交易树和收据树。 1. 以太坊除了状态树外，还有交易树和收据树。 每次发布一个区块的时候，这个区块里所包含的交易会组织成一颗交易树，也是一颗Merkle tree，跟比特币中的情况是类似的。 同时以太坊还增加了收据树，每个交易执行完之后，会形成一个收据，记录交易的相关信息。 交易树和收据树上面的节点，是一一对应的。 增加收据树，主要是考虑到以太坊的智能合约执行过程比较复杂，所以通过增加收据树的结构，有利于快速查询一些执行的结果。 从数据结构上，交易树和收据树都是MPT（merkle patricia tree）。 这与比特币有所区别，比特币中的交易树就是用普通的Merkle tree（区块中的所有交易，组织成一颗普通的Merkle tree）。当然，MPT也是一种Merkle tree。 可能是为了方便，以太坊中的三颗树，都用同样的数据结构。这样代码比较统一，并且便于管理。 用MPT的一个好处是，它支持查找操作，即可以通过键值，从顶向下沿着这个树进行查找。 对于状态树来说，查找的键值就是该账户的地址。 对于交易树和收据树来说，查找的键值就是交易在发布的区块里面的序号（排序为第几）。交易的排列顺序，是由发布区块的节点决定的。 这三棵树，有一个重要的区别：交易树和收据树，都是只把当前发布的区块里的交易，组织起来的。而状态树，是把系统中所有账户的状态都要包含进去。不管这些账户，跟当前区块的交易有没有什么相关性。 从数据结构上讲，多个区块的状态树，是共享节点的。每次新发布一个区块的时候，只有这个区块中的交易改变了状态的那些节点，需要新建一个分支。其他的节点，都是沿用原来状态树上的节点即可。 相比之下，每个区块的交易树和收据树都是独立的，它们是不会共享节点的。一个区块和另外一个区块，发布交易的本身，我们也认为是独立的。 2. 交易树和收据树的用途？ 一是提供Merkle Proof，就像比特币中交易树可以用来证明某个交易被打包到某个区块里，可以向轻节点提供Merkle Proof。 二是收据树也是类似的，要证明某个交易的执行结果，也可以在收据树里提供一个Merkle Proof。 除此之外，以太坊还支持一些更加复杂的查询操作：比如你想找到过去十天当中，所有跟某个智能合约有关的交易。 查询方法一：把过去十天产生的所有区块，都扫码一遍，看看其中有哪些交易是跟智能合约相关的。但这种方法的复杂度比较高，而且对于轻节点来说，实际上轻节点没有交易列表，它只有块头的信息。所以轻节点没有办法，通过扫描交易列表的方法，来找到符合查询条件的交易。 与之类似的查询，比如找到过去十天当中，符合某种类型的所有时间，比如说所有的众筹时间，或者是所有的发行新币的时间，这些都是需要比较高效的方法才能支持。 3. Bloom filter数据结构 可以支持比较高效的查找某个元素，是否在一个比较大的集合里面。 给大的包含很多元素的集合，计算出一个很紧凑的摘要。 比如说128位的向量：如上图所示，abc元素各取哈希后，映射到向量中的各自位置，变成1。 所有的元素都处理完后，得到的向量，就是原来集合的一个摘要。这个摘要，比原来的集合要小很多。 这个摘要的用途？ 比如有一个元素d，查询d元素是否在集合里，但集合本身不一定保存下来了。 用哈希函数，对d取哈希值后，映射到向量的其他位置，而且是0，说明元素d不在集合里。 假设d取完哈希值后，映射到a所映射的位置，而且也是1。说明d有可能就是集合里的元素d=a；有可能d不在集合里面，但是出现了哈希碰撞，恰好映射到了跟集合中某个元素一样的位置。 用Bloom filter，有可能出现假阳性（false positive），但不会出现假阴性（false negative）。 有可能出现误报，但不会出现漏报。（元素在里面，一定可以查询在里面；不在里面，也有可能查询在里面。） 简单的Bloom filter的局限性，不支持删除操作（比如例子中的a，不能删除，删除后取哈希的1，就有可能出现哈碰撞）。 4. 每个交易执行完后，在以太坊系统中，会形成一个收据。这个收据里面，就包含了一个Bloom filter，记录该交易的类型地址等信息。 发布的区块在块头里，有一个总的Bloom filter，总的Bloom filter是这个区块里，所有交易的Bloom filter的并集。 回到本文2点的例子，查询过去十天和智能合约的相关交易。 查询方法：先查一下哪个区块的块头里的Bloom filter，有要的交易的类型。 如果块头里的Bloom filter，没有的话，那这个区块不是我们想要的（过去十天和智能合约的相关交易并没有找到）。 如果块头的Bloom filter有的话，再查找区块里面包含的交易，所对应的收据树里面的那些Bloom filter（每个收据的Bloom filter）。 好处？ 通过Bloom filter的结构，能够快速过滤掉大量无关的区块。（很多区块，看块头的Bloom filter，就知道肯定不会有我们要的交易。剩下的一些少数的候选区块，再进行仔细查看。） 比如说一个轻节点，轻节点只有块头信息，根据块头就可以过滤掉很多的区块。剩下有可能是你想要的那些区块，再去问全节点要一些进一步的信息。 5. 以太坊的三棵树的根哈希值，都是包括在块头里面的。 以太坊的运行过程，可以看做交易驱动的状态机。 状态机的状态就是所有账户的状态，状态数包括的那些内容。 交易是每次发布的区块里包括的那些交易，这些交易通过执行那些交易会驱动系统，从当前的状态转移到下一个状态。 比特币，也可以认为是由交易驱动的状态机。比特币中的状态是UTXO，没有被花掉的那些输出。每次新发布于一个区块，会从UTXO里用掉一些输出，增加一些新的输出。 所以发布这个区块，会驱动状态机从当前的状态，转移到下一个状态。UTXO，可以认为是比特币状态机中的状态。 而且这两个状态机，有一个共同的特点，即状态转移都得是确定性的。 对一个给定的当前状态，一组给定的交易（区块中包含了这组交易），能够确定性的转移到下一个区块。因为所有的全节点，所有的矿工，都要执行同样的状态转移。 今天就学习到这里，明天见。

## 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