ETH-交易树和收据树
相关术语
Bloom Filter 布隆过滤器
概述
以太坊中还有另外俩棵树，交易树和收据树。每次发布交易的时候，这个区块里所包含的交易组成成一个交易树，也是一棵MPT，跟比特币是类似的不过比特币是简单的merkle tree。同时以太坊还增加了一个收据树，每个交易执行完止后会形成一个收据，记录这个交易的相关信息。交易树和收据树上面的节点是一一对应的。增加收据树主要是因为以太坊的智能合约执行过程比较复杂，所以通过收据的结构有利于快速查询一些执行的结果。
应该是为了统一，代码更容易管理，所以以太坊中的三棵树都是MPT。而且MPT是支持查找操作的，可以通过键值从顶向下沿着这棵树进行查找。对于状态树来说，查找的键值，就是这个账户的地址。对于交易树和收据树，查找的键值就是这个交易在发布区块里面的序号，交易的排列顺序中排第几。它的顺序是由发布的那个区块决定的。
这三棵树的主要区别是，交易树和收据树只把当前发布的区块的交易组织起来的。而状态树是要把系统中所有账户的状态都要包含进去。不管账户跟当前区块中的交易有什么关系。上一篇说过，多个区块的状态树是共享节点的。每次新发布一个区块的时候，只有这个区块中的交易改变了状态的那些节点，需要新建一个分支，其他的节点都是沿用原来状态树上的节点的。相比之下，每个区块的交易树和收据树都是独立在当前所在区块的，是不会共享节点的。
作用
交易树和收据树有什么用呢？
一个用途就是提供merkle proof，用来证明某个交易被打包到某个区块里了。
收据树也是类似，也可以通过收据树提供一个merkle proof。
除此之外，以太坊还支持一些更加复杂的查询操作，比如想要找到过去10天中，所有跟某个智能合约有关的交易。
一种方法是，把过去10天产生的所有区块都扫描，看其中有哪些交易跟这个智能合约相关，但是这种方法复杂度比较高，对于轻节点来说，没有交易列表只有一个块头信息，所以也没有办法通过扫码所有交易列表的方法来查询。
与之类似的场景，比如过去10天当中符合某种类型的所有事件。比如，所有的众筹事件、所有的发行新币的事件。以太坊中，引入了bloom filter这个数据结构，布隆过滤器，它可以支持高效的查找某个元素是否在一个比较大的集合里。普通的布隆过滤器是不支持删除操作的。
bloom filter
布隆过滤器（Bloom Filter）是一种空间效率很高的概率型数据结构,可以理解为一种摘要，主要用于判断一个元素是否在一个集合中。它由一个位数组和多个哈希函数组成。位数组初始全部为0，当给定一个待查询的元素时，这个元素会被一系列哈希函数计算映射出一系列的值，所有的值在位数组的偏移量处置为1。判断某个元素是否在这个集合中时，同样是这个元素经过哈希函数计算后得到所有的偏移位置，若这些位置全都为1，则判断这个元素在这个集合中，若有一个不为1，则判断这个元素不在这个集合中。
布隆过滤器的优点包括：
- 空间效率：相较于将过滤元素直接存储在内存中，布隆过滤器占用的内存空间会小很多。
- 查询速度：布隆过滤器可以快速判断某个值是否存在于集合中。
- 简单性：布隆过滤器的实现相对简单，易于理解和应用。
然而，布隆过滤器也有一些缺点：
- 误判率：存在一定的误判概率，即假阳性（False Positives），这意味着布隆过滤器可能会错误地判断一个元素存在于集合中，尽管实际上它并不存在。
- 删除困难：布隆过滤器不支持元素的删除操作。
布隆过滤器的应用场景非常广泛，包括但不限于：
- 大数据去重：在处理大规模数据时，布隆过滤器可以高效地进行去重操作。
- 分布式系统中的缓存击穿问题：布隆过滤器可以减少对数据库的无效访问，保护数据库。
- 广告拦截：用于拦截高风险、政治敏感、黄赌毒等不良广告点击。
- 垃圾邮件和恶意请求过滤：提高系统的安全性和稳定性。
- 点赞系统：快速判断用户是否已经点赞过某个内容，避免重复点赞。
- Hbase读取RowKey：提升RowKey查询效率。
总的来说，布隆过滤器是一种在空间和时间效率之间做出权衡的数据结构，适用于那些可以容忍一定误判率的场景。
在以太坊中的使用
每个交易执行完会形成一个收据，这个收据里面就包含了一个bloom filter。记录这个交易的类型、地址等其他信息。发布的区块的块头里也有一个总的bloom filter，这个总的bloom filter是这个区块所有交易的bloom filter的一个并集。
比如说要查找过去十天，发生的跟这个智能合约相关的所有交易，就可以先查一下，哪个区块的块头里面的bloom filter有需要的交易的类型，如果块头里面没有的话，那么就可以知道这个区块不是想要的。如果有的话，再去查找这个区块内部交易的所对于收据树里面的那些bloom filter。
状态机
以太坊的运行过程，可以把它看成一个交易驱动的状态机transaction-driven state machine。这个状态机的状态就是所有账户的状态，就是状态树中包含的内容。那么交易是什么，就是每次发布区块里包含的那些交易，通过执行这些交易，会驱动系统从当前的状态转移到下一个状态。其实比特币也可以认为是一个交易驱动的状态机，而比特币中的状态是UTXO。而且这俩个状态机有一个共同点，就是每次状态转移都得是确定性的。
状态机
状态机（State Machine）是一种计算模型，它可以根据一组规则从一个状态转换到另一个状态。状态机的概念在计算机科学、软件工程、通信协议设计等多个领域都有广泛的应用。状态机的基本组成包括：
- 状态（State）：状态机在任何给定时间点所处的情况或条件。例如，在交通信号灯的例子中，状态可能是“红灯”、“黄灯”和“绿灯”。
- 事件（Event）：触发状态转换的特定动作或条件。在交通信号灯的例子中，事件可能是“计时器到时”。
- 转换（Transition）：基于事件和当前状态，状态机从一个状态移动到另一个状态的过程。
- 初始状态（Initial State）：状态机开始执行时所处的状态。
- 终止状态（Final State）：状态机完成其任务后所处的状态，有些状态机可能没有终止状态。
状态机可以分为几种类型：
- 有限状态机（Finite State Machine, FSM）：状态和事件都是有限的，这是最常见的状态机类型。
- 确定性有限状态机（Deterministic Finite Automaton, DFA）：对于任何给定的状态和事件，都有一个确定的下一个状态。
- 非确定性有限状态机（Non-deterministic Finite Automaton, NFA）：对于某些状态和事件，可能有多个可能的下一个状态。
- 无限状态机（Infinite State Machine）：状态或事件的数量是无限的，这在理论上更常见。
状态机的应用非常广泛，包括但不限于：
- 软件设计：在软件设计中，状态机可以用来管理复杂的流程控制，如工作流、用户界面管理等。
- 硬件设计：在数字电路设计中，状态机用来描述电路的不同工作模式。
- 通信协议：在网络通信协议中，状态机用来定义不同通信状态之间的转换，如TCP/IP协议。
- 游戏开发：在游戏开发中，状态机用来管理游戏对象的行为，如角色的行走、跳跃、攻击等状态。
状态机的优点包括易于理解和实现，能够清晰地表示复杂的状态依赖关系，以及有助于设计出可预测和可维护的系统。
如果向一个新的以太坊账户转账，有可能回溯到创世区块。。
源码
看一下关于交易树和收据树的源码。
