北京大学肖臻老师《区块链技术与应用》公开课笔记(十七)：ETH数据结构：交易树、收据树

每次发布一个区块时，区块中的交易会形成一颗Merkle Tree，即交易树。此外，以太坊还添加了一个收据树，每个交易执行完之后形成一个收据，记录交易相关信息。也就是说，交易树和收据树上的节点是一一对应的。

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

交易树和收据树都是M(Merkle)PT，而BTC中都采用普通的MT(Merkle Tree)。（可能就仅仅是为了三棵树代码复用好所以这样设计的）
MPT的好处是支持查找操作，通过键值沿着树进行查找即可。对于状态树，查找键值为账户地址；对于交易树和收据树，查找键值为交易在发布的区块中的序号。

交易树和收据树只将当前区块中的交易组织起来，而状态树将所有账户的状态都包含进去，无论这些账户是否与当前区块中交易有关系。
多个区块状态树共享节点，而交易树和收据树依照区块独立。

交易树和收据树的用途：

向轻节点提供Merkle Proof。
更加复杂的查找操作(例如：查找过去十天的交易；过去十天的众筹事件等)

Bloom filter(布隆过滤器)

支持较为高效查找某个元素是否在某个集合中(如果你在集合里，不会误判你不在，如果你不在，有小概率判断你在。也就是有可能出现误报，但不会出现漏报)

给一个大的集合，计算出一个紧凑的“摘要”，如下图，a、b、c代表一个大的集合，里面可能有很多元素，然后通过某种方法映射到下方的digest(摘要)中，这个摘要是一个全0的数组，映射到某个位置，那么那个位置变为1。之后如果想判断一个元素x，那么用同样的方法映射到摘要中，如果映射的位置为0，那么这个元素一定不在集合中，如果映射的位置为1，那么如果映射方法有碰撞，那么说明他可能在也可能不在(实际上都是把一个较大的集合映射到一个较小的摘要中，碰撞是难以避免的)

那么如果我集合中要删除一个元素：无法操作。因为简单的布隆过滤器是不支持删除的，他存储的除了0就是1。如果想实现删除操作，就要把存储改成计数器，但那样违背了设计初衷，考虑的因素会变多。

以太坊中Bloom filter的作用

快速的查找与某个智能合约相关的交易

每个交易完成后会产生一个收据，收据包含一个Bloom filter记录交易类型、地址等信息。在区块block header中也包含一个Bloom filter，其为该区块中所有交易的Bloom filter的一个并集。所以，查找时候先查找块头中的Bloom filter，如果块头中能找到，那么就再查看区块中包含的交易的Bloom filter，如果存在，再查看交易进行确认；如果不存在，则说明发生了“碰撞”。

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

交易驱动的状态机

以太坊的运行过程，可以视为交易驱动的状态机(transaction-driven state machine)，状态指的所有账户的状态，通过执行当前区块中包含的交易。当然，BTC我们也可以视为交易驱动的状态机，其状态为UTXO。发布的区块会驱动系统从当前状态转移到下一状态。并且状态转移必须是确定性的，也就是说对一个给定的当前状态，一组给定的交易，能够确定性的转移到下一个状态。因为所有的全节点，所有的矿工都要执行同样的状态转移，所以状态转移必须是确定性的。