十六、以太坊中的交易树和收据树
每次发布一个交易的时候，那些交易会组织成一个交易树，也是一颗Merkle tree跟比特币中的情况是类似的，同时以太坊还增加了一个收据树，每个交易执行完之后会形成一个收据，记录这个交易的相关信息，交易树和收据树上面的节点是一一对应的。增加这个收据树，主要是考虑到以太坊的智能合约执行过程比较复杂，所以通过增加收据树的结构有利于我们快速查询一些执行的结果，从数据结构上，交易树和收据树都是MPT，这个跟比特币中有所区别，比特币的交易树就是用普通的Merkle tree，区块里的所有交易就组织成一个普通的Merkle tree，MPT也是一种Merkle tree，叫Merkle Patricia tree，但是跟比特币当中用的不是完全一样的，其实是为了方便，以太坊中的三棵树都用同样的数据结构，这样代码比较统一，便于管理，不一定要有什么更深层次的原因，当然用MPT的一个好处是支持查找操作，可以通过键值从顶向下沿着这个树进行查找，对于状态树来说，查找的键值就是这个账户的地址，对于交易树和收据树来说，查找的键值就是这个交易在发布的区块里的序号，就他的ID，这个交易的排列顺序是由发布区块的那个节点决定的。
这三棵树有一个重要的区别：
交易树和收据树都是只把当前发布的这个区块里的交易组织起来的，而状态树是把系统中所有账户的状态都要包含进去，不管这些账户跟当前区块的交易有没有什么关系。
从数据结构上来说，多个区块的状态树是共享节点的，每次新发布一个区块的时候，只有这个区块中的交易改变了状态的那些节点需要新建一个分支，其他节点都是沿用原来状态树上的节点，相比之下，每个区块的交易树和收据树都是独立的，是不会共享节点的，一个区块跟另一个区块发布的交易本身也认为是独立的
交易树和收据树的用途
-
提供Merkle proof，像比特币当中，交易树可以证明某个交易被打包到某个区块里面，可以向轻节点提供这样的Merkle proof，收据树也是类似的，要证明某个交易的结果，也可以再收据树里面提供一个Merkle proof，除此之外，以太坊还支持一些更加复杂的查询操作，比如说，想找到过去十天当中，所有跟某个智能合约有关的交易，一种方法是把过去十天产生的所有区块都扫描一遍，看看其中有哪些交易是和智能合约相关的，但是这种方法的复杂度较高，而且对于轻节点来说，实际上，轻节点没有交易列表，只有一个块头的信息，所以也没有办法通过扫描所有交易列表的方法来找到符合这个查询条件的交易，与之类似的一些查询，比如说，找到过去十天当中符合某种类型的所有事件，比如说所有的众筹事件或者所有的发行新币的事件，这些都是需要一个比较高效的方法才能支持，怎么办呢
以太坊中引用了bloom filter，bloom filter这种数据结构可以支持比较高效的查找某个元素是不是在一个比较大的集合里面，比如说有一个集合，里面有很多元素，现在想知道某个指定的元素是不是在这个集合里。
一个最笨的方法是，把这集合里面的元素遍历一遍，看看有没有我想找的那个元素，这个复杂度是线性的，另外一个前提是得有足够得存储来保存整个集合的元素，对于轻节点来说，他其实没有这个交易列表，没有整个集合的元素信息，所以这种方法是用不了的。
bloom filter用一个很巧妙的思想给这个大的，包含很多元素的集合计算出一个很紧凑的摘要，比如说一个128位的向量，比如说，这个例子当中有一个（a,b,c）的集合，要计算出一个digest，底下是一个向量，这个向量初始的时候都是零，然后有一个哈希函数H，他把每一个元素映射到向量中的某个位置，比如说a这个元素，取哈希之后，映射到这个位置，然后把这个位置的元素从0变成1
然后，b,c也映射到相应的位置，如下图所示，就是把每个元素都取哈希，找到向量中的对应位置，然后把它置成1，所有元素都处理完了，得到这个向量就是原来集合的一个摘要，这个摘要比原来的集合要小很多，这个例子当中用128bits就可以代表了
摘要的用处：比如说有一个元素d，想知道这个d元素是不是在这个集合里，但是这个集合本身我们不一定能够保存下来，可以用这个哈希函数H对d取哈希值，
比如说，取完之后发现，映射到这个地方，映射到一个0的位置，说明这个元素一定不在这集合里
假设取完哈希，映射到这个位置了，是个1的位置，有可能确实是集合中的元素，d=a，也有可能不在这个集合里，而是出现了哈希碰撞，恰好映射到了，跟集合某个元素一样的位置，所以用这个bloom filter要注意，有可能会出现false positive，但是不会出现false negative，就是可能出现误报，但是不会出现漏报，在里面一定说在里面，不在里面也有可能说在里面，这是bloom filter的一个基本的工作原理。
bloom filter有各种各样的变种，比如说，解决这样的哈希碰撞，有的bloom filter的设计用的不是一个哈希函数，而是一组哈希函数，每个哈希函数独立的把这个元素映射到这个向量里面一个位置，用一组哈希函数的好处是如果出现哈希碰撞，那么一般来说，不会所有的哈希函数都出现哈希碰撞，这里讲的是bloom filter，high level的工作原理，后面会结合代码看具体是怎么工作的，回到这个例子当中，如果从这个集合中删除一个元素，该怎么操作，实际上没法操作，这也是bloom filter的一个局限性，不支持删除操作，比如把a删掉了，对应的向量1要不要改，如果改成0的话，集合中可能有另外一个元素也映射到这个位置（哈希碰撞是有可能的），所以简单的bloom filter是不支持删除操作的，如果要支持删除操作，这个地方就不能是0和1了，得改成一个计数器，记录这个位置有多少个元素映射过来，而且还要考虑到计数器会不会溢出，这样数据结构就复杂得多了，和当初设计bloom filter的初衷是相违背的，所以一般来说，bloom filter是不支持删除操作的。
以太坊中bloom filter的用途
每个交易执行完之后会形成一个收据，这个收据里面就包含一个bloom filter，记录交易的类型，地址等其他信息，发布的区块，在他的块头里也有一个总的bloom filter，这个总的bloom filter是这个区块里所有交易的一个bloom filter的并集，所以回到刚才的例子，比如说要查找过去十天发生的跟智能合约相关的交易，可以找一些有哪些区块的块头的bloom filter有要的交易类型，如果没有，这个区块就不是我们想要的，如果有，再去查找区块里面包含的交易所对应的收据树里面的那些bloom filter，就每个收据的bloom filter，看看哪个有，也可能都没有，因为有可能是false positive，如果是有的话，再找到相对应的交易直接进行一下确认，好处是通过bloom filter的结构能够快速过滤掉大量无关的区块，就很多区块，一看块头的bloom filter就知道肯定没有我们要的交易，然后剩下的一些少数的候选区块，再仔细查看。比如说一个轻节点，只有块头信息，根据块头就已经能够过滤掉很多区块了，剩下有可能是想要的区块，再问全节点要进一步的信息。
这三棵树的根哈希值都是包括在块头里面的，以太坊的运行过程可以看作是一个交易驱动的状态机（transaction-driven state machine），这个状态机的状态是所有账户的状态，就是状态树中包含的那些内容，交易是每次发布区块里包含的交易，通过执行这些交易会驱动系统从当前状态转移到下一个状态，比特币也可以认为是一个交易驱动的状态机，比特币中的状态是UTXO（没有被花掉的那些输出），每次新发布一个区块，会从UTXO里用掉一些输出，又会增加一些新的输出，所以发布的区块会驱动系统从当前状态转移到下一个状态。而且这两个状态机有一个共同的特点，就是状态转移都得是确定的，对一个给定的当前状态，一组给定的交易，就这个区块中包含的交易，能够确定性地转移到下一个状态，因为所有的全节点，所有地矿工，都要执行同样的状态转移，所以状态转移必须是确定性的。
问题1
某人在以太坊发布一个交易，有人收到这个交易，转账交易A->B，有没有可能这个收款人的地址从来没听说过？
以太坊和比特币是一样的，创建账户是不需要通知其他人的，只有这个账户第一次收到钱的时候，其他的节点才会知道这个账户的存在，这个时候要在状态树中写下新插入的一个节点，因为这个是新插入的账户。
问题2
状态树和交易树，收据树的区别是，状态树要包含系统中所有账户的状态，无论这些账户是否参与了当前区块的交易，那么能不能要状态树的设计改一下，改成每个区块的状态树也只包含这个区块中的交易相关的那些账户的状态，这样就跟交易树和收据树一致了，而且可以大幅度的削减每个区块所对应的状态树的大小，因为大部分的账户状态是不会变的？
如果这样设计的结果是每个区块没有一颗完整的状态树，只有当前区块中所包含的交易涉及到的账户的状态，这么设计的一个问题就是，如果要想查找某个账户的状态就不方便了。比如说有一个转账交易A->B(10ETH)，要检查A账户里是不是真的有10个以太币，问题是A账户当前区块和最近一个区块对应的那个状态树可能没有这个账户，往前一直找，找到最近的一个包含A账户的区块，才能知道A的账户余额是多少。不方便就在于如果A有较长的一段时间没有发生交易，可能要从后往前，扫描很多个区块，才能找到最近一次的账户状态。还有一个更大的问题，就是，A转给B钱的时候，要知道A账户的状态，才能知道A是不是有足够的钱转给B10个以太币，也要知道B账户的状态，余额是多少，因为要往B账户余额里加10个以太币，所以也要找B账户的状态，而B账户有可能是个新建的账户，这个时候就要找到创世纪块去，从当前区块一直找到创世纪块，发现这个账户没有，才知道原来是个新建的账户。
代码中具体的数据结构
交易树和收据树的创建过程，在NewBlock函数里创建了交易树和收据树，并且得到了他们的根哈希值
先看一下交易树的代码，首先判断交易列表是否为空，如果是空的话，那么这个区块里块头的交易树的根哈希值就是一个空的哈希值，否则通过调用DeriveSha函数来得到交易树的根哈希值，然后创建区块的交易列表
中间这个代码是收据树，首先判断一下收据列表是否为空，如果为空，块头里收据树的根哈希值就是一个空的哈希值，如果不为空，通过调用DeriveSha函数来得到收据树的根哈希值，然后创建块头里的bloom filter，前面见过，每个交易执行完之后会得到一个收据，所以交易列表的长度和收据列表的长度是一样的
下面这个代码是叔父区块，首先判断叔父列表是否为空，如果是的话，那么块头里叔父区块的哈希值就是一个空的哈希值，否则，通过调用CalcUncleHash函数计算出哈希值，然后通过循坏构建出区块里的叔父数组，这个代码和今天讲的交易树和收据树没有关系，是下篇文章讲GHOST协议要用到的
下面看一下DeriveSha函数
前面NewBlock函数创建交易树和收据树的时候，调用的都是这个函数，这里调用的数据结构是trie
而trie的数据结构是一棵MPT，以太坊的三棵树，交易树，收据树，还有状态树用的都是MPT，
这是Receipt的数据结构，每个交易执行完之后形成的一个收据，记录了这个交易的执行结果
这里的Bloom就是这个收据的bloom filter
这个Logs是个数组，每个收据可以包含多个Log，这些收据的bloom filter就是根据这些Lo*生出来的
这是区块块头的数据结构
里面的Bloom域就是整个区块的bloom filter，这个是由刚才看到的每个收据的bloom filter合在一起得到的
这是刚刚的NewBlock函数，红框里的代码就是创建块头里的bloom filter，通过调用CreateBloom这个函数
这是相关的三个函数的代码实现
CreateBloom的参数是这个区块的所有收据，这个for循环对每个收据调用LogsBloom函数来生成这个收据的bloom filter，然后把这些bloom filter用Or操作合并起来得到整个区块的bloom filter
LogsBloom函数的功能是生成每个收据的bloom filter，他的参数是这个收据的Log数，刚才看过Receipt的数据结构，每个Receipt里面包含一个Logs的数组，这个函数有两层for循环，外层循环对Logs数组里的每一个Log进行处理，首先把Log的地址取哈希后，加到bloom filter里面，这里的bloom9是bloom filter中用到的哈希函数，然后内层循环把Log中包含的每个Topics加入到bloom filter里，这样就得到了这个收据的bloom filter
bloom9是bloom filter中用到的哈希函数，这个和我们讲的有点不太一样，我们那个例子中的哈希函数是把集合中的每个元素映射到digest中的一个位置，这个集合要生成一个digest，这个哈希函数就是把每个元素映射到要生成的digest中的某一个位置，把这个位置置为1。这里的bloom9函数是把输入映射到digest中的三个位置，把三个位置都置为1。
第一行调用crypto里面的函数，生成一个256位的哈希值，b或者变量是个32个字节的哈希值。
第二行的r是要返回的bloom filter，在这里初始化为0。
接下来是个循环，把刚才生成的32个字节的哈希值取前六个字节，每两个字节组成一组拼接在一起，然后and上2047，相当于对2048取余，得到一个位于0到2047这个区间里的数，这样做是因为以太坊中bloom filter的长度是2048位，这个循环的最后一行，把t左移这么多位然后合并到上一轮得到的bloom filter里，通过Or运算合并到前面的bloom filter里，经过三轮循环，把三个位置置为1后，返回所创建的bloom filter
前面是生成bloom filter的过程，那么怎么查询某个bloom filter里面是否包含了某感兴趣的topic呢?
这是通过调用BloomLookup函数来实现的，查一下bin bloom filter里有没有包含要找的第二个参数topic，首先用刚才讲的bloom9函数把topic转化成一个bytesBacked，然后把他跟bloom filter取and操作，看看得到的结果是不是和bytesBacked相等。注意bloom filter里面可能包含除了我们要查找的topic之外其他的topic，所以要做一个and，然后再跟他自身比较，相当于判断一下我们要查找的这个topic在bloom filter中对应的位置是不是都是1