17. ETH 交易树和收据树

以太坊中，每次发布一个区块的时候，区块里所包含的交易会组成一棵交易树， 也是一棵Merkle Tree，和BTC类似。每个交易执行完成之后会生成一个收据，记录交易的相关信息。交易树和收据树上面的节点是一一对应的。以太坊的智能合约执行过程比较复杂，增加收据树的结构有利于快速查询结果。

交易树和收据树的结构都是MPT。可能是为了代码统一，方便管理，可以通过键值从顶向下沿着树进行查找。

对于状态树来说，查找的键值就是账户的地址；包含系统中所有的账户的状态，不管这些账户和当前区块的交易有没有关系；状态树的数据结构中：多个区块的状态树是共享节点的，每次新发布的区块中，只有改变状态的节点（即发生过交易的节点）需要新建一个分支，其他的节点只需沿用原来状态树上的节点

对于交易树和收据树来说，查找的键值就是交易在发布区块里的序号（排序），交易的排列顺序是由发布区块的节点决定的；只把当前交易发布区块的交易组织起来；交易树和收据树的数据结构中：他们的数据是相互独立的，一个区块和另外一个区块发布的交易本身也是独立的。

三棵树的根哈希值都是包括在块头里面。

1. 交易树和收据树有什么用呢？

用途一：用于提供Merkle Proof。就像BTC中，交易树可以用来证明某个交易打包在某个区块里，向轻节点提供MF;收据树可以提供证MF明某个交易的执行结果。

用途二：以太坊还支持更加复杂的查询操作，比如说想找到过去十天所有和某个智能合约相关的交易（过去十天符合某种类型的所有事件），一种方法是把过去十天产生的所有区块都扫描一遍，看看其中有哪些交易是和智能合约相关的，方法复杂度高，轻节点只有块头消息，没有交易列表，无法完成。第二种方法：以太坊引入了bloom filter数据结构。

bloom filer 数据结构可以支持比较高效的查找某个元素是不是在一个比较大的集合里。eg. 有一个很大的集合，想要查找某一个元素在不在这个集合里。

方法一：遍历一遍集合里面所有的元素（复杂度：线性），前提是必须有足够的储存来保存整个集合的元素，轻节点没有交易列表，没有集合的元素信息，无法完成。

方法二：bloom filter会计算出一个大集合里面的摘要（digest），比如一个128位的向量，假设有个集合{a, b, c}，计算出一个digest, 底下是一个向量，向量的初始都是0，哈希函数H，把每个元素取哈希之后映射到向量中的某个位置，这个位置的元素就置成1，所有的元素都处理完成之后得到的向量就是原来集合的摘要，摘要会比原来的集合小很多，这个例子当中128bits就可以代表摘要。比如验证元素d是否在这个集合当中，如果H(d)映射到向量的位置是0,那么d一定不在集合里面，如果映射到的位置是1，那么d不一定在集合里，因为此处可能会发生哈希碰撞，所以bloom filter 会发生false positive，(在里面就一定会说在里面，不在里面也有可能说在里面, H0: d不在里面)属于第一类错误。

Bloom filter的变种与延伸：选择一组哈希函数，每个哈希函数独立完成任务，所有哈希函数都发生哈希碰撞的概率几乎为0。

Bloom filter 不支持数据删除，如果删除某个元素，把哈希值在向量对应的值从1变成0，那么如果有哈希碰撞产生，即集合里面的其他元素哈希值对应向量里面的值也可能是1，就会连同另外一个元素一同删除，所以是不可行的。

 

	Fail to Reject H0(No)	Reject H0(Yes)
H0 is True	Right Decision (TN)	Type I Error(FP)
H0 is False	Type II Error(FN)	Right Decision(TP)

每个交易执行结束之后会形成一个收据，收据里面就包含一个bloom filter, 记录交易的类型地址等信息。发布的区块块头也有一个总的bloom filter，是区块里所有交易的bloom filter的并集。比如要查找过去十天和某个智能合约相关的所有交易，先查一下区块块头里的bloom filter有查找的交易，如果块头bloom filter有的话，再去查找区块里面包含的交易所对应的收据树里面的bloom filter，即每个收据的bloom filter，有可能都没有（FP）,有的话找到相对应的交易进行确认。

优点：通过bloom filter结构，能够快速过滤掉大量无关的区块，通过块头删选过滤。

2. 以太坊的运行过程-交易驱动的状态机（transaction-driven state machine）

状态机的状态是什么？交易是什么？

是所有账户的状态，即所有状态树中包含的内容。交易是每次发布的区块所包含的交易，通过执行这些交易，驱动系统从当前的状态转移到下一个状态。BTC也可以视为TDSM，状态为UTXO，每次新发布一个区块，会从UTXO用掉一些输出和增加一些新的输出，所以发布的区块可以驱动状态机从当前的状态转移到下一个状态。

Ethereum 和BTC的状态转移必须是确定性的，因为所有的矿工，全节点都要执行同样的状态转移。

Q1：有人在以太坊发布交易，节点收到交易转账A-B，有没有可能收款人的地址是节点从来没有听过？

可能的，因为创建账户是不需要通知别人，只有账户第一次收到钱的时候其他人才会知道这个节点的存在，这个时候状态树需要新插入一个节点，新增账户。

Q2：状态树要包含系统中所有账户的状态，无论账户是否参与当前区块的交易，能不能把状态树的设计改成只包含该区块交易相关的账户的状态，这样就和交易树和收据树一致，并且可以大幅度削减每个区块所对应的状态树的大小，因为大部分的账户状态是不会变的，可以吗？

不可以，1.查找账户状态不方便。A-B，需要同时知道账户A的状态，才能只能A能不能转账， 如果账户A有比较长一段时间没有发生交易，那么就需要从后往前扫描很多个区块才能找到A账户的状态。 2. 也要知道账户B的状态，才能做账户余额的更新，如果B账户是新建的账户，需要从当前区块扫描到创世区块才能只能这是一个新建的账户，很消耗时间和资源。

3. 代码中具体的数据结构

1. 交易树和收据数的创建过程

 

 

Newblock里创建了交易树和收据树，并且得到了他们的根哈希值，block.go中，Newblock 函数里调用DeriveSha来得到交易树和收据树的根哈希值。

交易树的代码：创建交易树，判断交易列表是否为空，如果为空，则区块块头的哈希值也为空，否则通过调用Derivesha来得到交易树的根哈希，然后创建区块的交易列表。

中间代码是收据树：判断收据列表是否为空，如果为空，则区块块头的收据树哈希值也为空，否则通过调用Derivesha来得到收据树的根哈希值，然后创建区块块头里面的bloom filter。每个交易执行完之后会得到一个收据，所以交易列表的长度和收据列表的长度是一致的。

下面代码是处理叔父区块，和下一节课Ghost协议相关。判断叔父列表是否为空，如果为空，则区块块头的叔父区块的哈希值也为空，否则通过调用CalUncleHasj函数计算出哈希值，通过一个循环构建出区块里的叔父数组。

Receipt的数据结构，收据记录了交易的执行结果，这里的Bloom域就是收据的bloom filter；Log域是个数组，每个收据可以包含多个Log，收据的Bloom filter就是根据Log产生出来的。

2. Bloom filter 的创建过程

这个是区块块头的数据结构，里面这个Bloom域就是整个区块的Bloom filter，是由刚才看到的每个收据的bloom filter合并在一起得到的。

这是相关的三个函数代码实现，CreatBloom函数的参数是这个区块的所有收据，for循环对每个收据调用LogsBloom函数来生成这个收据的Bloom filter,然后把bloom filter用Or合并起来得到整个区块的bloom filter。

LogsBloom函数的功能是生成每个收据的bloom filter，他的参数是这个收据的logs数，每个receipt包含一个log的数组，外层的for 循环对log的数组里面的每一个log进行处理，首先把log的地址取哈希后加到bloomfilter里面，bloom9是bloomfilter中用的哈希函数，内层循环把Logs里包含的每个topic加到bloom filter。这样就得到了收据的bloom filter。

bloom9和课上讲的哈希函数有些区别（把集合中的每个元素映射到digest的某个位置，集合要生成一个digest，哈希函数把每个元素映射到要生成的digest中的某一个位置，把这个位置视为1），这里的bloom9是把输入映射到digest的三个位置，也就是把三个位置都置为1。第一行调用crypto函数生成一个256位的哈希值，b变量是32字节的哈希值，r是最后要返回的bloom filter，第二行把r初始化为0，接下来的for循环是把刚才生成的32字节的哈希值取前6个字节，每两个字节组成一组拼接在一起，再add 2047，相当于对2048取余，得到了一个位于0-2017区间里的数，因为以太坊中bloom filter的长度是2048位，循环最后一行把i左移这么多位，然后合并到上一轮得到的bloom filter里面，通过or运算合并到前面的bloom filter里。这样经过三轮循环，把三个位置置为1后返回所创建的bloom filter。

3. Bloom filter的查找功能

怎么查询某个bloom filter是否包含我们感兴趣的topic？

通过调用BloomLookup函数，查询bin Bloom filter有没有包含要找的第二个参数,topic，首先用刚才讲的bloom9函数把topic转换成一个bit vector，然后把他和bloom filter取add操作，看结果是否和Bit vector相等，bloom filter除了包含查找的topic还可以包含其他topic，所以要先做一个add再和自身比较，相当于判断一下我们要查找的topic在bloom filter对应的位置是不是都是1。