北大肖臻老师《区块链技术与应用》系列课程学习笔记[15]以太坊-交易树和收据树-Toy模板网

这篇具有很好参考价值的文章主要介绍了北大肖臻老师《区块链技术与应用》系列课程学习笔记[15]以太坊-交易树和收据树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、以太坊中的三种树

二、状态树、交易树和收据树的区别

三、交易树和收据树的用途

1.交易树和收据树的用途

2.如何实现复杂的查询操作

3.以太坊中Bloom Filter的用途

四、以太坊的运行过程

一、以太坊中的三种树

在以太坊中，存在三种基于树的数据结构——状态树、交易树和收据树。所有的交易会组成一棵Merkle tree，叫交易树，交易树类似于比特币系统中的Merkle tree。此外，以太坊中还增加了收据树，每个交易执行完之后会形成一个记录这个其相关信息的收据，交易树和收据树上面的节点是一一对应的。增加这个收据树的目的是便于快速查询执行的结果（主要因为以太坊的智能合约执行过程比较复杂）。

从数据结构上来看，交易树和收据树都是MPT，与比特币系统不同，比特币系统中的交易树就是由区块里的所有交易组织成的一个普通的Merkle tree，MPT也是Merkle Patricia tree，跟比特币系统中有所不同。为了方便，以太坊中的三棵树都用同样的数据结构，这样代码比较统一，便于管理，当然用MPT的一个好处是支持查找操作，可以通过键值从顶向下沿着这颗树查找。在状态树中，查找的键值就是这个账户的地址，对于交易树和收据树来说，查找的键值就是这个交易在发布的区块里的序号，就他的排序，这个交易的排列顺序是由发布区块的那个节点决定的。

二、状态树、交易树和收据树的区别

（1）交易树和收据树都是只将当前发布的区块里的交易组织起来，状态树需要把系统中所有账户的状态都要包含进去，不管这些账户跟当前区块的交易有没有什么关系。

（2）从数据结构上来说，多个区块的状态树是共享节点的（新发布一个区块的时候，只有该区块中改变了状态的节点需要新建一个分支，其他节点都是沿用原来状态树上的节点），相比之下，每个区块的交易树和收据树都是独立的，是不会共享节点的（一个区块和另一个区块发布的交易本身也认为是独立的）。

三、交易树和收据树的用途

1.交易树和收据树的用途

提供Merkle Proof。比特币系统中，交易树可以证明某个交易被打包到某个区块里面，即向轻节点提供这样的Merkle Proof。收据树也是类似的，可以提供Merkle Proof来证明某个交易的结果，除此之外，以太坊还支持一些更加复杂的查询操作，比如说，想查询过去十天当中，所有与某个智能合约有关的交易（一种方法是把过去十天产生的所有区块都扫描一遍，看看其中有哪些交易是和智能合约相关的，但是这种方法有几个缺点：①复杂度较高，是线性的；②得有足够得存储来保存整个集合的元素；③实际上，轻节点没有交易列表，只有一个块头的信息，所以也没有办法通过扫描所有交易列表的方法来找到符合这个查询条件的交易），与之类似的一些查询，找到过去十天当中符合某种类型的所有事件（如，所有的众筹事件或者所有的发行新币的事件），这些都需要一个比较高效的方法。

2.如何实现复杂的查询操作

以太坊中引入了Bloom Filter，这种数据结构可以支持比较高效的查找某个元素是不是在一个比较大的集合里，比如说有一个集合，里面有很多元素，现在想知道某个指定的元素是不是在这个集合里。Bloom Filter给这个包含很多元素的集合计算出一个很紧凑的摘要（如一个128位的向量）。如，有一个集合(a,b,c)，要计算出digest，其下方是一个初始全为零的向量，存在一个哈希函数H，将元素中每个元素取哈希后映射到向量表中，将这个位置的元素从0变成1，如下图3-1所示。集合中所有元素都这样处理完，得到的向量就是原集合的一个摘要，这个摘要比原集合小很多。

摘要的用处：假设有一个元素d，想知道这个d是否在某集合里，但集合本身不一定能保存下来，可以用这个哈希函数H对d取哈希值，比如说，取完哈希值之后，映射到向量中某个是0的位置，则说明该元素一定不在该集合里，如图3-2所示；若取完哈希值之后，映射到向量中某个是1的位置，则不能说明该元素在该集合里，有可能确实是集合中的元素，d=a，也有可能d不在该集合里，但出现了哈希碰撞，恰好映射到跟集合某个元素一样的位置，所以使用Bloom Filter要注意，有可能会出现false positive，但是不会出现false negative，就是可能出现误报，但是不会出现漏报。即若元素属于集合，则判断出来一定为元素属于集合；元素不属于集合，也可能判断出来元素属于集合。

文章来源地址https://www.toymoban.com/news/detail-744524.html

Bloom Filter有各种各样的变种，为解决这样的哈希碰撞，有时候会用一组哈希函数而不是单个哈希函数，将某个带证明元素分别通过每个哈希函数映射到向量中的一个位置。一般来说，不会所有的哈希函数都出现哈希碰撞。Bloom Filter的局限性是不支持删除操作。比如把a删掉了，对应的向量1要不要改，如果改成0的话，集合中可能有另外一个元素也映射到这个位置（哈希碰撞是有可能的），所以简单的Bloom Filter是不支持删除操作的。若要支持删除操作，则需要将向量中的值改成一个计数器，记录该位置有多少元素映射过来，而且还需要考虑到计数器会不会溢出。这样数据结构就复杂得多了，和当初设计Bloom Filter的初衷相违背，所以一般来说，Bloom Filter是不支持删除操作的。

3.以太坊中Bloom Filter的用途

每个交易执行完之后会形成一个包含Bloom Filter的收据，Bloom Filter用于记录交易的类型、地址等信息。发布的区块的块头里也有一个总的Bloom Filter，是这个区块里所有交易的一个Bloom Filter的并集。比如说要查找过去十天发生的跟智能合约相关的交易，可以找一些有哪些区块的块头的bloom filter有要的交易类型，如果没有，这个区块就不是我们想要的，如果有，再去查找区块里面包含的交易所对应的收据树里面的那些Bloom Filter（就每个收据的bloom filter）看看哪个有，也可能都没有，因为有可能是false positive。如果是有的话，再找到相对应的交易直接进行一下确认，好处是通过Bloom Filter的结构能够快速过滤掉大量无关的区块，就很多区块，一看块头的Bloom Filter就知道肯定没有我们要的交易，然后剩下的一些少数的候选区块，再仔细查看。比如轻节点，只有块头信息，根据块头就已经能够过滤掉很多区块了，剩下有可能是想要的区块，再问全节点要进一步的信息即可。

四、以太坊的运行过程

这三棵树的根哈希值都包括在块头里面，以太坊的运行过程可以看作一个交易驱动的状态机（Transaction-driven State Machine），这个状态机的状态是所有账户的状态，即状态树中包含的那些内容，交易是指每次发布区块里包含的交易，通过执行这些交易会驱动系统从当前状态转移到下一个状态。比特币系统也可以认为是一个交易驱动的状态机，比特币中的状态是UTXO（没有被花掉的那些输出），每次新发布一个区块，会从UTXO里用掉一些输出，又会增加一些新的输出，发布的区块会驱动系统从当前状态转移到下一个状态。而且这两个状态机有一个共同的特点，就是状态转移都得是确定的，对一个给定的当前状态，一组给定的区块中包含的交易，能确定性地转移到下一个状态。因为所有的全节点，所有地矿工，都要执行同样的状态转移，所以状态转移必须是确定性的。

到了这里，关于北大肖臻老师《区块链技术与应用》系列课程学习笔记[15]以太坊-交易树和收据树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！