以太坊中的交易树和收据树

每次发布的区块中，交易会组织成一棵交易树，也是一棵merkle tree，和比特币中情况类似；每个交易执行完之后会形成一个收据，记录交易的相关信息，交易树和收据树上的节点是一一对应的，增加收据树是考虑到以太坊的智能合约执行过程比较复杂，通过增加收据树的结构有利于快速查询执行结果。从数据结构上看，交易树和收据树都是MPT，和比特币有所区别，比特币的交易树就是普通的merkle tree ，MPT也是一种merkle tree，但是和比特币中用的不是完全一样。对于状态树来说，查找账户状态所用的key是地址，对于交易树和收据树来说，查找的键值就是交易在区块中的序号，交易的排列顺序由发布区块的节点决定。这三棵树有一个重要的区别，就是交易树和收据树都是只把当前发布的区块中的交易组织起来，而状态树是把系统中所有账户的状态都组织起来，不管账户和当前区块中的交易有没有关系。从数据结构上来说，多个区块的状态树是共享节点的，每次新发布的区块时，只有区块中的的交易改变了账户状态的那些节点需要新建分支，其它节点都沿用原来状态树上的节点。相比之下不同区块的交易树和收据树都是独立的。

交易树和收据树的作用

交易树一个用途是merkle proof ，像比特币中用来证明某个交易被打包到某个区块里。收据树也是类似的，证明某个交易的执行结果，也可以在收据树里提供一个merkle proof。除此之外，以太坊还支持更复杂的查询操作，比如查询过去十天当中和某个智能合约有关的交易，这个查询方法之一是，把过去十天产生的所有区块中交易都扫描一遍，看看哪些是和这个智能合约相关的，这种方法复杂度比较高，且对轻节点不友好。以太坊中的查询是引入了bloom filter（布隆过滤器），这个数据结构支持比较高效的查找某个元素是不是在一个比较大的集合里，bloom filter给一个大的集合计算出一个很紧凑的摘要，比如说一个128位的向量，向量初始都是0，通过hash函数，把集合中的每个元素映射到向量中的某个位置，元素的映射位置都置为1，所有元素处理完后向量就是一个摘要，这个摘要比原来的集合小很多。这个过滤器的作用是，我们想查询一个元素，但集合太大我们不能保存，这时候对该元素取hash值，发现映射到向量中0的位置，说明这个元素不在集合里，但是映射到向量中1的位置，也不能说明元素在集合里，因为可能会出现hash碰撞。所以用bloom filter时，可能会出现false positive，但是不会出现false negative，意思是有可能出现误报，但是不会出现漏报，在里面一定说在里面，不在里面可能也会说在里面。bloom filter有各种各样的变种，比如说像解决hash碰撞，有的bloom filter用的不是一个hash函数，而是一组，每个hash函数独立的把元素映射到向量中的某个位置，用一组hash函数的好处是，一般不可能一组hash函数都出现碰撞。bloom filter的一个局限性不支持删除操作，因为存在hash碰撞，使得不同元素映射到向量同一个位置，如果删掉一个元素，使对应位置上的1变成0，那么和它发生碰撞的元素也被删除了，所以简单的bloom filter 不支持删除操作，可以将0和1改成计数器，记录有多少元素映射过来，而且还要考虑计数器是否会overflow，但是这样就复杂的多，和当初设计的理念就违背了，所以一般用bloom filter就不支持删除操作。以太坊中bloom filter 的作用是，每个交易执行完成后会形成一个收据，收据里面就包含了一个bloom filter ，记录这个交易的类型、地址等其它信息，发布的区块在块头里也有一个总的bloom filter ，这个总的bloom filter 是区块里所有交易的bloom filter 的并集，所以说想查询过去十天当中和某个智能合约有关的交易，先查哪个区块的块头的bloom filter里有我要的交易的类型，如果块头的bloom filter里面没有，那么这个区块里面就没有我们想要的，如果块头的bloom filter 里有，我们再去查找区块里面包含的交易所对应的收据树里面对应的bloom filter，但是可能会出现误报，如果有的话，我们再找到相对应的交易进行确认，好处是通过bloom filter能快速过滤大量无关区块，很多区块看块头的bloom filter就知道没有我们想要的交易，剩下的少数候选区块再仔细查看。轻节点只有块头信息，根据块头就能过滤掉很多信息，剩下有可能是想要的区块，问全节点要具体信息。

以太坊的运行过程可以看作交易驱动的状态机（transaction-driven state machine），状态机的状态指状态树中的那些账户状态，交易指交易树中那些交易，通过执行这些交易，使得系统从当前状态转移到下一个状态。比特币也可以认为是交易驱动的状态机，比特币中的状态是UTXO。这两个状态机有一个共同特点是状态转移都是确定性的，对一组给定的交易能够确定性的驱动系统转移到下一个状态，因为所有的节点都要执行同样的交易，所以状态转移必须是确定性的。

状态树的两个问题

如果交易的收款方是从未听过的账户，全节点需要在状态树中新插入一个账户。
状态树中保留所有账户状态的目的之一是快速查找付款人的余额，如果像比特币一样，那么账户余额就得往前推算；目的之二是快速查询收款人是否是新建账户，因为转账过程中收款人的余额也得知道，否则无法更新，如果像比特币一样，一直往前找直到创世纪块才知道这个账户是新建的。

下面是代码实现的数据结构

上图是交易树和收据树的创建过程，在NewBlock 函数中创建了交易树和收据树，并且得到了两者的根hash值

以太坊