交易树（Transaction Trie）

交易树是为每一个区块单独构建的、一次性的数据结构，它的唯一目的就是存储该区块内包含的所有交易，并为它们生成一个唯一的、可验证的“指纹”。当一个验证者（Validator）要创建一个新区块时，它会为这个区块专门构建一棵交易树：

1. 收集数据：验证者从交易池中选择一批交易，并将它们按特定顺序（通常由验证者自己决定，以优化Gas费收益）排列好，形成一个列表。
2. 构建MPT：它会创建一个全新的、空的默克尔·帕特里夏·树，然后将这个交易列表存入其中。
   • 键 (Key)：不是交易哈希，也不是地址，而是这笔交易在这个列表中的索引（index），例如第0笔、第1笔、第2笔... 这个索引会经过RLP编码。
   • 值 (Value)：就是这笔交易本身的完整数据（包含了nonce, to, value, gasLimit, data等所有字段），同样经过RLP编码。
3. 生成根哈希：当所有交易都插入到这棵树中后，会计算出这棵树唯一的根哈希。
4. 写入区块头：这个最终的根哈希，就是被记录在区块头中的transactionsRoot字段。

交易树的核心目的有两个：

1. 保证数据的完整性 (Data Integrity)
   • transactionsRoot是对区块内所有交易内容及其顺序的一个密码学承诺。
   • 任何人，包括验证者自己，都无法在事后添加、删除或调换区块内的任何一笔交易，否则transactionsRoot就会变得完全不同，导致整个区块无效。它确保了区块内容的不可篡改性。
2. 提供高效的交易包含证明 (Proof of Inclusion)
   • 这是对用户和轻客户端最重要的功能。
   • 任何人都可以通过一个简短的默克尔证明，来向一个不信任的节点或应用证明：“我发送的这笔哈希为0xabc...的交易，确实被包含在了第N号区块里。”
   • 轻客户端（如手机钱包）只需要拥有区块头（包含了可信的transactionsRoot），就能独立验证这笔交易是否真的被打包了，而无需下载整个区块的交易列表。

收据树（Receipts Trie）

收据树是为每一个区块单独构建的、一次性的数据结构，它的唯一目的就是存储该区块内每一笔交易执行后所产生的“结果”或“收据”，并为这些收据生成一个唯一的、可验证的“指纹”。

对于区块里的每一笔交易，网络都会生成一个对应的“收据”，这张收据主要包含以下四个关键信息：

1. 交易状态 (status)
   • 这是一个简单的布尔值，1代表成功，0代表失败。这让我们可以快速知道一笔交易是否执行成功，而无需重新执行它来判断。
2. 累计消耗的Gas (cumulativeGasUsed)
   • 记录了到当前这笔交易为止，这个区块内所有交易累计消耗的Gas总量。这个字段对于快速定位区块内哪笔交易导致了“Gas耗尽”（Out of Gas）的错误非常有用。
3. 事件日志 (logs)
   • 这是收据中最重要的部分，是智能合约与外界沟通的桥梁。
   • 智能合约在执行过程中，可以触发（emit）一些预定义的“事件（Events）”。这些事件就像是合约在执行关键步骤时喊出的话：“一个ERC-20代币刚刚被转移了”或者“一个新的NFT被铸造了”
   • 所有这些“喊话”记录，都会被收集在这笔交易收据的logs字段里。dApp的前端和后端应用，就是通过监听和查询这些事件日志来了解链上发生了什么的。
4. 日志的布隆过滤器 (logsBloom)
   • 为了能极其高效地、快速地在海量区块中过滤和查找特定的事件日志，每张收据都会根据其logs内容生成一个布隆过滤器（Bloom Filter）。
   • 区块头中的logsBloom字段，就是将该区块所有收据的布隆过滤器合并起来的结果。这使得dApp可以快速判断一个区块是否可能包含它感兴趣的事件，从而避免了大量无效的查询。

收据树与交易树类似，都是为每个区块独立构建的一次性MPT，它的键（Key）也是交易在区块内的索引（0, 1, 2...）。其核心目的有：

1. 提供交易结果的证明 (Proof of Outcome)
   • receiptsRoot是对区块内所有交易执行结果的密码学承诺。
   • 它允许任何人（特别是轻客户端）高效地证明：“我这笔交易不仅被打包了，而且它执行成功了，并且触发了某个特定的事件。”
   • 这对于需要确认链上操作结果的应用（例如一个跨链桥，需要确认资金已在一端锁定）至关重要。
2. 支持高效的事件查询 (Efficient Event Querying)
   • 通过receiptsRoot和logsBloom的结合，dApp和区块浏览器（如Etherscan）可以非常快速地索引和查询历史事件，而无需执行或检查每一笔历史交易的细节。

布隆过滤器（Bloom Filter）

简单来说，布隆过滤器是一个极其节省空间的、用来快速判断“一个元素是否可能存在于一个集合中”的概率性数据结构。布隆过滤器核心特性是：

• 它绝不会“漏报”（False Negative）：如果它说“不在”，那就一定不在。
• 但它可能会“误报”（False Positive）：如果它说“可能在”，那它只是可能在，需要进一步确认。在以太坊中，每个区块头里的logsBloom字段就是一个256字节（2048位）的布隆过滤器。

Bloom Filter的目标是回答一个问题：“元素 x 是否在一个集合 S 中？”

它由两个核心部分组成：

1. 一个长度为 m 的位数组（Bit Array）
   • 这是一个包含 m 个比特（bit）的数组，所有比特的初始值都被设置为 0。
   • m 的大小是影响过滤器性能的关键参数之一。
2. k 个独立的哈希函数（Hash Functions）
   • 这些哈希函数（h1, h2, ..., hk）可以将任意输入元素转换成一个数值。
   • 这些函数需要尽可能地独立，且产生的哈希值分布要均匀。
   • k 的数量也是影响性能的关键参数。

工作流程：

操作一：添加元素 (add)

当想将一个元素 x 添加到集合中时，布隆过滤器会执行以下步骤：

1. 将元素 x 分别输入到 k 个哈希函数中，得到 k 个不同的哈希值。
   • hash1 = h1(x)
   • hash2 = h2(x)
   • ...
   • hash_k = hk(x)
2. 将这 k 个哈希值分别映射到位数组的索引上。最常用的方法是取模运算：
   • index1 = hash1 % m
   • index2 = hash2 % m
   • ...
   • index_k = hash_k % m
3. 将位数组中所有这 k 个索引位置上的比特，从 0 设置为 1。

这个过程会对集合中的每一个元素重复执行。如果某个位置的比特已经是1了，它会保持为1。

操作二：查询元素 (query 或 contains)

当您想查询一个元素 y 是否存在于集合中时，过程如下：

1. 将元素 y 输入到同样的 k 个哈希函数中，得到 k 个哈希值。
2. 同样，将这 k 个哈希值映射到 k 个位数组的索引上。
3. 检查位数组中这 k 个索引位置上比特的值。
4. 根据检查结果得出结论：
   • 如果这 k 个位置中，有任何一个位置的比特是 0，那么布隆过滤器会断定：元素 y 绝对不存在于集合中。
     • 逻辑：因为如果 y 曾经被添加过，那么它对应的所有 k 个位置都必然已经被设置成了 1。只要有一个0存在，就说明y从未被添加过。
   • 如果这 k 个位置中，所有的比特都是 1，那么布隆过滤器会断定：元素 y 可能存在于集合中。

概率性与误报（False Positive）

为什么是“可能存在”而不是“绝对存在”？因为位数组中的某个比特位被设置为1，可能是由其他不同元素的哈希结果所导致的。

例如：

• 我们添加了元素 A，它将索引 10, 25, 60 的位置设为了 1。
• 我们又添加了元素 B，它将索引 18, 40, 99 的位置设为了 1。
• 现在我们查询一个从未被添加过的元素 C。不巧的是，C经过哈希后，对应的索引恰好是 10, 40, 60。
• 当过滤器检查这三个位置时，发现它们的值全部是1（分别由A和B设置的）。
• 因此，过滤器会错误地报告C“可能存在”，尽管它实际上并不在集合里。这种情况被称为误报（False Positive）。但是如果它判断一个元素不存在，那它就100%不存在。

因此布隆过滤器特性如下：

• 绝无漏报（No False Negatives）：这是布隆过滤器最重要的特性。如果它判断一个元素不存在，那它就100%不存在。
• 存在误报（Has False Positives）：如果它判断一个元素存在，那它只是可能存在。
• 空间效率：它用极小的空间就能代表一个巨大的集合。
• 不可删除元素：标准的布隆过滤器不支持从集合中删除元素。因为将某个比特从1改回0，可能会影响到其他共享这个比特位的元素。

1. 在ETH中，这个“集合”是什么？
   • 这个“集合”包含了该区块内所有交易收据里，所有事件日志（Logs）中的两个关键信息：
     • 发出事件的合约地址
     • 被索引的事件主题（Topics），例如ERC-20转账事件的“Transfer”标识。
2. 它是如何工作的？
   • 当一个验证者处理区块时，每当一笔交易产生一个事件日志，验证者就会取出其中的合约地址和Topics，通过几个哈希函数计算出几个位置，然后到logsBloom这个2048位的序列中，将对应位置的比特（bit）从0设置为1。
3. 目的—— 加速事件搜索
   • 当一个dApp或者区块浏览器（如Etherscan）想要查找历史上所有的“USDT代币转账”事件时，它不必去下载和解析历史上每一个区块的每一笔交易收据。
   • 它可以先批量下载所有区块头（这非常快）。
   • 然后对每一个区块头，它会先检查logsBloom字段：
     • 如果过滤器说“不包含”（根据USDT合约地址和Transfer事件主题计算出的某一位是0），那么这个dApp就可以100%确定这个区块里没有它要找的事件，从而可以立即跳过，大大提高了效率。
     • 如果过滤器说“可能包含”（所有对应的位都是1），那么dApp才会去下载这个区块完整的收据数据，进行精确的查找和确认。

布隆过滤器是以太坊为了提升应用层（dApp）的数据查询效率而设计的一个工程优化。通过牺牲一点点的确定性（允许极小概率的误报），换来了数量级的性能提升。让dApp和用户能够快速地在海量的链上数据中，定位到自己感兴趣的信息，是整个以太坊dApp生态能够流畅运行的关键基础设施之一。

交易树和收据树的一一对应

交易和收据是一一对应的，但交易树（Transaction Trie）和收据树（Receipts Trie）所承诺和证明的东西，在逻辑上和时间上都是完全分离的，它们分别代表了状态转换的“输入”和“输出”。至少在ETH的环境中，这两棵树不可以合并。

1. 时间和逻辑上的分离：先有“意图”，后有“结果”

这是最根本的原因。

• 交易的创建（意图）：当一个EOA账户创建并签署一笔交易时，这个动作发生在交易被执行之前。在签名的时候，EOA并不知道这笔交易最终会消耗多少Gas，不知道它是否会因为某种链上状态的改变而失败，也不知道它会触发哪些具体的事件日志。EOA只是在对其的“意图”进行签名授权。
• 交易的执行（结果）：只有当验证者将交易打包进一个区块并实际执行它时，才会产生“结果”——即消耗的Gas量、成功/失败的状态、以及触发的事件日志。

结论：因为“结果”（收据）是在“意图”（交易）被创建和签名之后才产生的，所以它们无法被包含在同一个经过签名的原始数据包里。因此，必须有两棵独立的树，一棵用来证明“不可否认的意图”，另一棵用来证明“不可否认的结果”。

2. 功能和证明目标完全不同

两者为网络提供了不同但都至关重要的证明能力：

• 交易树证明了“授权”：
  • 它能向世界证明：“Alice确实在某个时间点，用她的私钥签署了这笔交易，授权了这个操作。” 这对于问责和防止伪造至关重要。收据里并不包含Alice的原始签名信息（v,r,s）。没有交易树，我们就无法证明这笔操作的合法来源。
• 收据树证明了“结果与事件”：
  • 它能向世界证明：“当Alice的交易被执行时，确实成功了，并且确实触发了一个‘转账1000 USDT’的事件。” 这对于dApp和链下服务的运作至关重要。例如：
    • 一个跨链桥需要监控收据树来确认一端的资产是否已锁定。
    • 一个DeFi仪表盘需要读取收据树来展示您的交易历史和收益。
    • 一个NFT市场需要监听收据树来更新NFT的所有权。
  • 如果没有收据树，所有这些应用都必须自己去重新执行每一笔历史交易来推断结果，这在计算上是完全不可行的。

为什么BTC不需要维护收据树

比特币：无状态，确定性系统

1. 交易即结果：一笔比特币交易的核心，是销毁一些旧的UTXO（未花费的交易输出），并创造一些新的UTXO。这个操作的有效性在交易被打包前就可以被完整验证（签名是否有效、UTXO是否存在且未被花费）。
2. 无“副作用”：比特币交易除了转移价值，不会产生任何其他的“副作用”或“附带事件”。它不会与一个复杂的程序交互，也不会改变除了相关UTXO之外的任何状态。
3. 验证即确认：一个节点验证比特币交易时，只需要检查交易数据本身和当前的UTXO集合。一旦交易被验证并通过，并被打包进一个区块，其结果就是确定的、不可改变的价值转移。证明交易被打包了，就等同于证明了结果。

以太坊：一个非确定性结果的通用计算平台

1. 交易是“调用”，而非“结果”：一笔以太坊交易，本质上是对一个账户（EOA或合约账户）的“调用（Call）”。这个调用的结果，取决于被调用合约的内部代码逻辑以及调用时的世界状态，这些在交易被创建时是未知的。
2. 需要记录执行的“副作用”：
   • 成功或失败：一个语法正确的交易，在执行时完全可能因为代码逻辑（如revert()）或资源耗尽（Out of Gas）而失败。网络必须有一个机制来记录这个最终的执行状态，这就是收据中的status字段。
   • 与外界的通信（事件日志）：智能合约是一个封闭的沙盒环境，它与dApp前端或其他链下服务沟通的唯一标准方式，就是通过触发事件（Emitting Events）。这些事件被记录在收据的logs字段中，是整个dApp生态能够运作的基石。没有收据，dApp就变成了就没办法运行。
3. 需要精确的资源消耗记录：交易中指定的gasLimit只是一个上限，实际消耗的gasUsed只有在执行后才知道。这个精确的数字必须被记录下来，用于计算退款和成本，它同样在收据中。

按需重建

交易树和收据树的历史版本不会像状态树那样被持续地、作为一个整体结构来保存。其价值在于生成被记录在区块头里的根哈希。一旦这个使命完成，树的结构本身就可以被“遗忘”，但其原始数据会被保留下来。

为了理解这一点，我们必须区分一个节点保存的数据和它为了验证而临时构建的结构。

• 状态树 (State Trie)：是持续演变的。第N+1个区块的状态树是在第N个区块的基础上修改得来的。节点必须维护这个持久的、可演变的结构（至少是最近的版本），因为计算新状态依赖于旧状态。
• 交易树 & 收据树 (Transaction & Receipts Tries)：则是按需重建的。

生命周期：“构建、证明、然后遗忘”

1. 构建：当一个验证者创建新区块时，它会利用该区块内的交易列表和收据列表，从零开始，全新地构建出这个区块专属的交易树和收据树。
2. 证明：这两棵树的唯一目的，就是计算出它们的根哈希（transactionsRoot 和 receiptsRoot），并将这两个“指纹”放入区块头，以提供密码学上的完整性证明。
3. 遗忘结构：一旦区块被验证和接受，全节点没有必要在其数据库中永久保存这两棵树的完整结构（即所有中间的分支节点和扩展节点）。为什么？因为下一个区块（N+1）的交易树和收据树，与上一个区块（N）的这两棵树完全无关，它们是从一批全新的数据构建的。

按需（On-demand）重新计算

当SPV向全节点索要一个默克尔证明的时候，全节点按需提供默克尔证明，在这点上ETH和BTC是一样的。

1. 原始数据被永久保存：一个全节点会永久保存所有历史区块的区块体（Block Body）。这意味着，“交易列表”和“收据列表”这些原始数据，是作为历史记录被完整保留下来的。
2. 按需生成证明：当一个轻客户端请求“请证明交易X确实在区块Y中”时，全节点会： a. 从它的历史数据库中，找到并读出区块Y的完整交易列表。 b. 在内存中，根据这个列表，快速地、临时地重新计算出足以生成证明所需的那部分交易树路径。 c. 根据这个临时计算出的路径，提取出需要的哈希值，打包成一个默克尔证明，然后发送给轻客户端。 d. 它可以通过比对临时计算出的根哈希和区块Y头部的transactionsRoot，来确保自己的计算是正确的。

三棵树的对比

以太坊状态机

从上面三棵树的运作我们可以得出如下结论：

• 以太坊是一个状态机。
• 这三棵树是用来实现、表示和验证这个状态机每一次状态转换的关键数据结构。

一个标准的状态机包含：一个初始状态、一组输入、一个状态转换函数，以及一个最终状态。以太坊的区块处理过程完美地符合这个模型。

1. 状态 (State - S)
   • 以太坊中 就是我们反复提到的“世界状态（World State）”，即在某一时刻，所有账户（EOA和合约）的完整信息快照（包含余额、nonce、合约代码和存储）。
   • 表示 由状态树（State Trie）来表示。在处理一个新区块前，整个网络都公认一个起始状态 S，这个状态由上一个区块头里的stateRoot所唯一标识。
2. 输入 (Input - I)
   • 以太坊中 就是被打包进新区块里的那一组有序的交易列表。这些交易是驱动状态发生改变的指令。
   • 表示 由交易树（Transaction Trie）来表示。这棵树的根哈希transactionsRoot是对这组输入的唯一、不可篡改的承诺。
3. 状态转换函数 (Transition Function - F)
   • 以太坊中 这就是以太坊虚拟机（EVM）。EVM就是那个“机器”本身，它定义了所有的计算规则。
   • 它做什么？ 它的工作就是接收当前的状态 S 和一组输入 I（交易），然后严格按照预设的规则进行计算，最终得出一个全新的状态 S'。我们可以用公式表达： F(S, I) = S'。
4. 输出 (Output - O)
   • 以太坊中 在状态转换过程中，每一笔交易执行后都会产生一个“执行结果”的记录，即收据（Receipt）。
   • 如何表示？ 由收据树（Receipts Trie）来表示。这棵树的根哈希receiptsRoot是对所有交易执行结果的唯一、不可篡改的承诺。

所以，以太坊中每个区块的产生，都是一次完整的状态转换，可以被一个函数清晰地描述：

Y(S, T) = (S', R)

其中：

• Y: 代表以太坊整体的状态转换函数（由EVM实现）。
• S: 初始的世界状态（由旧的 stateRoot 代表）。
• T: 一组交易（由 transactionsRoot 代表）。
• S': 经过计算后，产生的全新的世界状态（由新的 stateRoot 代表）。
• R: 这个过程中产生的所有收据（由 receiptsRoot 代表）。

这三棵树，通过它们各自的根哈希，被锁定在同一个区块头里，共同构成了一份对这次状态转换的、不可分割的、可独立验证的完整报告。