ETH-以太坊的交易树和收据树

交易树和收据树

每发布一个区块，区块中的交易就会形成一棵Merkle Tree，也就是交易树，类似于比特币中的情况。

此外，以太坊还增加了收据树，每笔交易执行后形成一张收据，记录交易相关信息。 也就是说，交易树上的节点和收据树上的节点是一一对应的。 主要原因是以太坊智能合约的执行比较复杂，收据树的加入方便了执行结果的快速查询。

交易树和收据树都是M（Merkle）PT，而BTC中使用的是普通的MT（Merkle Tree）。 （也许它只是为了三叉树代码重用而设计的）

MPT的优点是支持查找操作，可以通过key值沿树查找：

交易树和回执树只组织当前区块中的交易，而状态树包括所有账户的状态，不管这些账户是否与当前区块中的交易相关。 多个区块状态树共享节点，而交易树和回执树按区块独立。

交易树和收据树的用途：

为轻节点提供Merkle Proof。更复杂的搜索操作（例如：查找近十天的交易；近十天的众筹事件等）布隆过滤器（Bloom filter）布隆过滤器的作用

支持更有效地查找元素是否在集合中

eg：查找某个元素是否在集合中

最笨：元素遍历，复杂度为O(n)——不能使用轻节点

方法：给定一个大集合，计算一个紧凑的“摘要”

如下图所示，给定一个数据集，通过哈希函数H()计算出意义元素a、b、c，并映射到一个初值为0的128位向量的某个位置，将该位设置为1。所有元素处理完后，可以得到一个向量，称为原始集合的“汇总”。 可以看出，“摘要”比原始集合小得多。

总结的作用：假设要查询一个元素d是否在集合中，假设H(d)映射到向量中的位置为0，说明d一定不在集合中； 假设H(d)映射到vector中的位置如果为1，则有可能集合中确实存在d，或者可能因为哈希冲突产生误报。

集合中删除元素怎么办？

无法操作。 也就是说，简单的布隆过滤器不支持删除操作。 如果要支持删除操作，需要将记录数从0和1改为一个计数器（需要考虑计数器会不会溢出）。

Bloom filter 特点：可能有误报，但不会有误报。

布隆过滤器变体：使用一组哈希函数进行向量映射，有效避免哈希冲突

布隆过滤器在以太坊中的作用

每笔交易完成后，都会生成一张收据，收据中包含一个布隆过滤器，用于记录交易类型、地址等信息。 区块头中还包含一个布隆过滤器，它是区块中所有交易的布隆过滤器的联合体。

所以，在查找的时候，先查找区块头中的Bloom filter，如果区块头中包含的话。 然后检查块中包含的交易的布隆过滤器。 如果存在，检查交易以确认； 如果不存在怎么查询以太坊的交易记录，则表示发生了“碰撞”。

好处：采用布隆过滤器等结构怎么查询以太坊的交易记录，可以快速过滤掉大量不相关的块，从而提高搜索效率。

事务驱动的状态机

以太坊的运行过程可以看作是一个交易驱动的状态机。 通过执行当前块中包含的交易，驾驶系统从当前状态转移到下一个状态。 当然，BTC也可以看作是一个交易驱动的状态机，其状态为UTXO。

状态转换都是确定性的：对于给定的当前状态和一组给定的事务，可以确定性地移动到下一个状态（以确保系统一致性）。

问题一：A向B转账时，是否有可能收款账户不在状态树中？

可能的。 因为以太坊中的账户可以由节点自己生成，不需要通知其他人，只有在交易产生时其他节点才知道。 这时，必须在状态树中插入一个新的节点。

问题2：是否可以将每个区块中的状态树改为只包含区块中与交易相关的账户状态？ （显着减小状态树的大小并与交易树和收据树保持一致）

不能。 首先，在这种设计中查找账户状态很不方便，因为没有包含所有状态的区块。 其次，如果你想转账到一个新创建的账户，你需要知道收款账户的状态，然后才能添加金额。 但是由于是新创建的账户，需要一直找到创世块才能知道该账户是新创建的账户。 该系统不存储在区块链中，由区块链不断扩展。

代码中的具体数据结构

创建交易树和收据树的过程

下图中的函数创建交易树和收据树，并创建它们的根哈希值