2022-01-18发表2025-03-13更新以太坊12 分钟读完 (大约1860个字)

区块链学习笔记16——ETH交易树和收据树

点击阅读更多查看文章内容

区块链学习笔记16——ETH交易树和收据树

学习视频：北京大学肖臻老师《区块链技术与应用》
笔记参考：北京大学肖臻老师《区块链技术与应用》公开课系列笔记——目录导航页

交易树和收据树

每次发布区块，区块中的交易会组织成一棵交易树，也是一棵Merkle tree与比特币类似
每个交易执行完之后会产生一个收据，记录交易的相关信息，交易树和收据树的结点是一一对应的。
由于以太坊智能合约执行较为复杂，通过增加收据树，便于快速查询执行结果。

数据结构
交易树和收据树都是MPT，而BTC中都采用普通的MT，MPT的好处是支持查找操作，通过键值沿着树进行查找即可。对于状态树，查找键值为账户地址；对于交易树和收据树，查找键值为交易在发布的区块中的序号，序号由发布区块的结点决定。
交易树和收据树只把当前发布区块的交易组织起来，而状态树是把系统中所有账户的状态包含进去，无论这些账户是否与当前区块中交易有关系。多个区块状态树共享节点，只会为更改了状态的结点新建一个分支，而交易树和收据树依照区块独立。

交易树和收据树的作用

提供Merkle proof
更加复杂的查找操作(例如：查找过去十天与某个智能合约有关的交易；过去十天的众筹事件等)

Bloom filter

支持较为高效地查找某个元素是否在某个比较大的集合中
最笨：元素遍历，复杂度为O(n)，且轻节点没有存储交易列表不能使用
Bloom filter的思想：给一个大的集合，计算出一个非常紧凑的“摘要”

例：如下图，给定一个数据集，其中含有元素a、b、c，通过一个哈希函数H()对其进行计算，将其映射到一个初始全为0的向量的某个位置，将该位置置为1。将所有元素处理完，就可以得到一个向量，则称该向量为原集合的“摘要”。可见该“摘要”比原集合是要小很多的。
假定想要查询一个元素d是否在集合中，假设H(d)映射到向量中的位置处值为0，说明d一定不在集合中；假设H(d)映射到向量中的位置处为1，有可能集合中确实有d，也有可能因为哈希碰撞产生误报。

Bloom filter特点：有可能出现误报，但不会出现漏报。
Bloom filter变种：采用一组哈希函数进行向量映射，有效避免哈希碰撞
Bloom filter不支持删除操作，有产生碰撞的可能

ETH中的Bloom filter
每个交易完成后会产生一个收据，收据中会包含一个Bloom filter，记录这个交易的类型、地址等其他信息，在发布的区块的block header中也包含一个总的Bloom filter，其为该区块中所有交易的Bloom filter的一个并集。

要查找过去十天发生的与智能合约相关的所有交易
查找时候先查找哪个块头中的Bloom filter有要查找的交易类型，如果块头中没有，则这个区块就不是我们要找的，如果块头有的话，我们继续查找这个区块所包含的交易的收据树中的Bloom filter，如果存在，再查看交易进行确认；如果不存在，则说明发生了“碰撞”。

好处：通过Bloom filter这样一个结构，快速大量过滤掉大量无关区块，从而提高了查找效率。

补充

以太坊的运行过程，可以视为交易驱动的状态机，状态机的状态是状态树的内容，交易是每次发布的区块所包含的交易，通过执行当前区块中包含的交易，驱动系统从当前状态转移到下一状态。BTC我们也可以视为交易驱动的状态机，其状态为UTXO。

问题1：A转账到B，有没有可能收款账户不包含再状态树中？
可能。因为以太坊中账户可以节点自己产生，不需要通知其他人，只有在产生交易时才会被系统知道，此时在状态树中会新插入一个结点。
问题2：可否将每个区块中状态树更改为只包含和区块中交易相关的账户状态？(大幅削减状态树大小，且和交易树、收据树保持一致)
不能。首先，这样设计要查找账户状态很不方便，因为不存在某个区块包含所有状态，在转账的时候因为要查找相关账户的状态信息，需要从区块依次往前查找这个账户的信息，如果这个账户很久没有参与交易的话会需要往前查找很多区块，其次，如果要向一个新创建账户转账，因为需要知道收款账户的状态，才能给其添加金额，但由于其是新创建的账户，所以需要一直找到创世纪块发现根本不存在这个账户，才能知道该账户为新建账户，系统中并未存储。