以太坊的交易树和收据树

交易树和收据树

每发布一个区块，区块中的交易就形成一棵交易树。 此外，以太坊还增加了收据树，每笔交易执行后形成一张收据，记录交易相关信息。 也就是说，交易树上的节点和收据树上的节点是一一对应的。

为什么要增加收据树？

由于以太坊智能合约的执行较为复杂，通过添加收据树，可以方便快速查询执行结果。

交易树和收据树都是M（Merkle）PT，而BTC中使用的是普通的MT（Merkle Tree）。 （为什么以太坊不用Merkle Tree？肖老师觉得可能是为了统一以太坊三棵树代码而设计的。）

MPT的优点是支持查找操作，可以通过键值沿树查找。 对于状态树，查找键值为账户地址； 对于交易树和回执树，查找键值为交易在已发布区块中的序号。

交易树和收据树的用途：

1. 为轻节点提供Merkle Proof。

2、更复杂的搜索操作（例如：搜索近十天的交易；近十天的众筹事件等）。

布隆过滤器（Bloom filter）

布隆过滤器支持更高效地查找元素是否在集合中。

如果不使用Bloom filter，最原始的方法就是遍历all，O(n)复杂度，轻节点没有足够的空间存放所有元素，也没有完整的交易列表，所以方法brute force traversal 是不可用于轻节点的！

布隆过滤器的搜索思路

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

假设要查询一个元素d是否在集合中，假设H(d)映射到向量的位置为0，说明d一定不在集合中； 假设H(d)映射到vector的位置为1，则集合中可能确实存在d，也可能因为hash冲突而出现误报。

假阳性

使用Bloom filter的特点之一就是应该在集合中的元素会被正确广播，不在集合中的元素也可能会被广播为在集合中。

因此，布隆过滤器会有一些变体用法。 例如，在映射哈希时，使用一组哈希函数进行向量映射，可以有效避免哈希冲突。

如果我想从集合中删除一个元素怎么办？

如果你想使用布隆过滤器，这并不容易做到。 如果单纯的把1改成0，其实你没有办法判断这个操作是改了你需要改的1，还是hash冲突导致的1。 如果要支持删除操作，需要将记录数从0和1改为一个计数器（需要考虑计数器会不会溢出）。

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

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

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

好处是通过Bloom filter的结构，比如你是轻节点，可以利用区块头快速过滤掉大量不相关的区块，从而提高搜索效率，然后再去问全节点了解更多信息。

总结

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

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

A给B转账，有没有可能收款账户不在状态树中？

可能的。 因为以太坊中的账户可以由节点自己生成，只有在交易产生时才会被系统知道。

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

不能。 首先这个设计中查找账户状态不方便，因为没有包含所有状态的block，需要一个一个遍历之前的block看是否包含你账户之前的状态需要。

最麻烦的情况是如果你想转账到一个新创建的账户，因为你需要知道收款账户的状态才能往里面添加金额，但是既然是新创建的账户，你需要找到创世区块一直知道账户是新创建的，账户没有存储在系统中，区块链不断延伸。

参考

1、北京大学肖震老师《区块链技术与应用》公开课

2. 参考笔记