ETH交易树和收据树

在以太坊网络中，所有的交易都被记录在一个称为区块（Block）的容器中。每个区块中包含了多个交易，这些交易被依次执行并最终打包在区块中。交易树是指这些交易之间的关系，通常以树状结构的形式展现。每一笔交易都有一个唯一的交易哈希值，而这些交易哈希值按照一定规则构成了交易树。通过交易树，可以方便地追踪到每一笔交易的相关信息，包括发送方、接收方、交易金额等。

以太坊交易树和收据树

每次发布一个区块时，这个区块里面的交易会组织成一个交易树，也是一棵Merkle tree。

同时以太坊还增加了一个收据树，每个交易执行完成之后会形成一个收据，记录这个交易的相关信息。交易树和收据树上面的节点是一一对应的。增加收据树主要是因为以太坊的智能合约执行过程比较复杂，通过增加收据树的结构，有利于快速查询一些执行的结果。

比特币中的交易树只是普通的Merkle tree，而以太坊中的交易树和收据树都是MPT。MPT其实本质上也是Merkle tree。

采用MPT后，便于查找。对于状态树，查找的key就是账户的地址。对于交易树和收据树，查找的key就是这个交易在发布的区块里面的序号。

交易树和收据树都是只把当前区块里面的交易组织起来，而状态树是把系统中所有的账户都要包含进去。多个区块的状态树是共享节点的，而每个区块的交易树和收据树都是独立的，不会共享节点。

交易树和收据树可以用来向轻节点提供Merkle proof。

除此之外，以太坊还支持一些比较复杂的查询操作。例如过去十天当中和某个智能合约有关的交易、过去十天中符合某种类型的所有事件。为了支持这些复杂查询，以太坊中引入了bloom filter（布隆过滤器）数据结构。

布隆过滤器

布隆过滤器（bloom filter），这种数据结构可以支持比较高效的查找某个元素是不是在比较大的集合里面。

如果不使用布隆过滤器，普通的查找一个元素是否在一个集合里，可以把集合中的元素遍历一遍，这个的复杂度是线性的，而且要有足够大的存储来保存整个集合的元素。而轻节点没有整个交易列表（即没有整个集合的信息）。

布隆过滤器将这个很大的集合计算出一个很紧凑的摘要，例如一个128位的向量。

基本的布隆过滤器

一个基本的布隆过滤器，如下图：

存在一个很大的集合，需要给这个集合计算出一个digest（摘要）：

1.初始化了一个数组（向量），数组中每个元素的值都是0

2.对集合中的元素做哈希运算，对应到向量中的某个位置，然后将向量中这个位置的元素从0变成1。（可能会存在哈希碰撞）

3.集合中的所有元素都映射完成后，得到的这个向量就叫摘要.这个摘要要比原来的集合小得多。

如果要判断一个元素E是否在这个集合中，则只需对这个元素E也取哈希。判断其哈希值在摘要中对应位置的值：

●如果对应位置值是0，那么说明这个元素E一定不在这个集合中

●如果对应位置值是1，说明元素E可能在集合中，也可能元素E不在集合中，只是出现了哈希碰撞。

所以，基本的布隆过滤器有可能出现false positive（假阳性，也叫误报），但是不会出现false negative（假阴性，也叫漏报）。

布隆过滤器有很多变种。例如为了应对哈希碰撞，有的布隆过滤器使用的不是一个哈希函数，而是使用一组哈希函数，每个哈希函数独立的把集合中的元素映射到向量中的某个位置。这样做的好处是，一般情况下，即使出现哈希碰撞，也不会一组哈希函数全都碰撞。

因为基本的布隆过滤器的哈希函数可能存在哈希碰撞，所以布隆过滤器无法处理元素删除的情况。例如：上图集合中如果要删除其中一个元素，那么其对应的向量位置的值无法确定是否要调整回0，如果删除的是B那么就需要调整向量中的位置值为0，如果删除的是A，就不能修改向量中的位置的值。

如果要支持删除，就需要对布隆过滤器做改造，例如下面向量的位置的值不再直接使用二进制0、1，而是使用个计数器，然后还需要考虑这个计数器是否会出现overflow。但是这样改造之后，复杂性就会变高，和最初使用布隆过滤器的初衷违背，所以一般的布隆过滤器都不支持元素的删除。

以太坊中的布隆过滤器

每个交易执行完之后会形成一个收据，这个收据里面就包含了一个bloom filter，记录了这个交易的类型、地址等信息。

发布的区块在它的块头里，也有一个总的bloom filter，是这个区块里所有交易的bloom filter的一个并集。

如果需要查找过去十天当中和某个智能合约有关的交易：

1.先查询哪个区块的块头里有需要的查找的交易的类型。如果区块的块头里没有，就说明这个区块不是我们要找的

2.如果区块的块头里面存在，那么继续查找这个区块里面包含的所有交易所对应的收据树里面的每个收据bloom filter。有可能确实存在，也有可能是出现了false positive。

优势：通过bloom filter的结构，可以快速过滤掉大量无关的区块，然后对剩余的少数的区块再进行查找。

状态机

以太坊的运行过程，可以看做是一台交易驱动的状态机（transaction-driven state machine）。这个状态机的状态就是状态树的内容，即所有账户的状态。驱动的交易就是区块中包含的交易。通过执行这些交易会驱动系统从当前的状态转移到下一个状态。

比特币也可以看做是一台交易驱动的状态机。比特币中的状态是UTXO。

这两个状态机有一个共同的特点：状态转义都需要是确定性的。对一个给定的当前状态，一组给定的交易，能够确定性的转移到下一个状态。因为所有的全节点矿工都要执行状态转移，所以状态转移必须是确定性的。

区块保存完整状态树

以太坊和比特币一样，在创建账户时是不需要通知其他人的。只有在这个账户第一次收到钱时其他节点才会知道这个账户的存在，此时需要在状态树中新插入一个节点来保存该账户。

每个区块中只保存和本区块交易相关的交易树、收据树，但是保存的状态树是完整的状态树。因为如果要转入的账户是个新建的账户，而每个区块如果都没保存完整的状态树，那么要从结尾一直搜索到创世纪块才能发现这个账户是新创建的。

交易树和收据树的创建过程

// NewBlock creates a new block. The input data is copied,
// changes to header and to the field values will not affect the
// block.
//
// The values of TxHash, UncleHash, ReceiptHash and Bloom in header
// are ignored and set to values derived from the given txs, uncles
// and receipts.
func NewBlock(header *Header, txs []*Transaction, uncles []*Header, receipts []*Receipt, hasher TrieHasher) *Block {
	b := &Block{header: CopyHeader(header)}

	// TODO: panic if len(txs) != len(receipts)
	if len(txs) == 0 {
		b.header.TxHash = EmptyTxsHash  // 如果交易树==0（即交易树为空），则块头中的根哈希值就是一个空哈希值
	} else {
		b.header.TxHash = DeriveSha(Transactions(txs), hasher)  // 通过DeriveSha函数获取到树的根哈希值
		b.transactions = make(Transactions, len(txs))  // 创建区块的交易列表
		copy(b.transactions, txs)
	}

	if len(receipts) == 0 {
		b.header.ReceiptHash = EmptyReceiptsHash  // 如果收据树列表为空，则块头中的根哈希值就是一个空哈希值
	} else {  // 因为每个交易执行完会创建一个收据，所以收据列表的长度和交易列表的长度相同
		b.header.ReceiptHash = DeriveSha(Receipts(receipts), hasher) // 通过DeriveSha函数获取到树的根哈希值
		b.header.Bloom = CreateBloom(receipts) // 创建区块头的bloom filter
	}

    // 处理叔父区块
	if len(uncles) == 0 {
		b.header.UncleHash = EmptyUncleHash// 如果叔父区块列表为空，则块头中的叔父哈希值就是一个空哈希值
	} else {
		b.header.UncleHash = CalcUncleHash(uncles)  // 调用CalcUncleHash函数计算叔父区块的哈希值
        // 通过一个循环，构建叔父区块数组
		b.uncles = make([]*Header, len(uncles))
		for i := range uncles {
			b.uncles[i] = CopyHeader(uncles[i])
		}
	}

	return b
}

计算根哈希的DeriveSha函数

// TrieHasher is the tool used to calculate the hash of derivable list.
// This is internal, do not use.
type TrieHasher interface {
	Reset()
	Update([]byte, []byte) error
	Hash() common.Hash
}


// DeriveSha creates the tree hashes of transactions, receipts, and withdrawals in a block header.
func DeriveSha(list DerivableList, hasher TrieHasher) common.Hash {

    // 旧版本中，hasher不是传入的，而是在函数内new出来的:  trie = new(trie.Trie) （旧版本中的该变量名叫做trie，数据结构为Trie，但实际是一个MPT）
    hasher.Reset() 

	valueBuf := encodeBufferPool.Get().(*bytes.Buffer)
	defer encodeBufferPool.Put(valueBuf)

	// StackTrie requires values to be inserted in increasing hash order, which is not the
	// order that `list` provides hashes in. This insertion sequence ensures that the
	// order is correct.
	//
	// The error returned by hasher is omitted because hasher will produce an incorrect
	// hash in case any error occurs.
	var indexBuf []byte
	for i := 1; i < list.Len() && i <= 0x7f; i++ {
		indexBuf = rlp.AppendUint64(indexBuf[:0], uint64(i))
		value := encodeForDerive(list, i, valueBuf)
		hasher.Update(indexBuf, value)
	}
	if list.Len() > 0 {
		indexBuf = rlp.AppendUint64(indexBuf[:0], 0)
		value := encodeForDerive(list, 0, valueBuf)
		hasher.Update(indexBuf, value)
	}
	for i := 0x80; i < list.Len(); i++ {
		indexBuf = rlp.AppendUint64(indexBuf[:0], uint64(i))
		value := encodeForDerive(list, i, valueBuf)
		hasher.Update(indexBuf, value)
	}
	return hasher.Hash()
}

BloomFilter

Receipt收据树数据结构：

// Receipt represents the results of a transaction.
type Receipt struct {
	// Consensus fields: These fields are defined by the Yellow Paper
	Type              uint8  `json:"type,omitempty"`
	PostState         []byte `json:"root"`
	Status            uint64 `json:"status"`
	CumulativeGasUsed uint64 `json:"cumulativeGasUsed" gencodec:"required"`
    
    // 这个收据的 bloom filter
	Bloom             Bloom  `json:"logsBloom"         gencodec:"required"`
    // 每个收据可以包含多个Log。这个收据的bloom filter就是根据这些Log产生出来的
	Logs              []*Log `json:"logs"              gencodec:"required"`

	// Implementation fields: These fields are added by geth when processing a transaction.
	TxHash            common.Hash    `json:"transactionHash" gencodec:"required"`
	ContractAddress   common.Address `json:"contractAddress"`
	GasUsed           uint64         `json:"gasUsed" gencodec:"required"`
	EffectiveGasPrice *big.Int       `json:"effectiveGasPrice"` // required, but tag omitted for backwards compatibility

	// Inclusion information: These fields provide information about the inclusion of the
	// transaction corresponding to this receipt.
	BlockHash        common.Hash `json:"blockHash,omitempty"`
	BlockNumber      *big.Int    `json:"blockNumber,omitempty"`
	TransactionIndex uint        `json:"transactionIndex"`
}

区块块头的bloom filter：

type Header struct {
	ParentHash  common.Hash    `json:"parentHash"       gencodec:"required"`
	UncleHash   common.Hash    `json:"sha3Uncles"       gencodec:"required"`
	Coinbase    common.Address `json:"miner"`
	Root        common.Hash    `json:"stateRoot"        gencodec:"required"`
	TxHash      common.Hash    `json:"transactionsRoot" gencodec:"required"`
	ReceiptHash common.Hash    `json:"receiptsRoot"     gencodec:"required"`
    
    // 区块块头中的Bloom filter，就是整个区块的收据的bloom filter合并一起取到的
	Bloom       Bloom          `json:"logsBloom"        gencodec:"required"`
	Difficulty  *big.Int       `json:"difficulty"       gencodec:"required"`
	Number      *big.Int       `json:"number"           gencodec:"required"`
	GasLimit    uint64         `json:"gasLimit"         gencodec:"required"`
	GasUsed     uint64         `json:"gasUsed"          gencodec:"required"`
	Time        uint64         `json:"timestamp"        gencodec:"required"`
	Extra       []byte         `json:"extraData"        gencodec:"required"`
	MixDigest   common.Hash    `json:"mixHash"`
	Nonce       BlockNonce     `json:"nonce"`

	// BaseFee was added by EIP-1559 and is ignored in legacy headers.
	BaseFee *big.Int `json:"baseFeePerGas" rlp:"optional"`

	// WithdrawalsHash was added by EIP-4895 and is ignored in legacy headers.
	WithdrawalsHash *common.Hash `json:"withdrawalsRoot" rlp:"optional"`

	// ExcessDataGas was added by EIP-4844 and is ignored in legacy headers.
	ExcessDataGas *uint64 `json:"excessDataGas" rlp:"optional"`

	// DataGasUsed was added by EIP-4844 and is ignored in legacy headers.
	DataGasUsed *uint64 `json:"dataGasUsed" rlp:"optional"`
}

block.go中，区块头通过CreateBloom函数来创建区块头的Bloom域。func NewBlock中调用CreateBloom：

if len(receipts) == 0 {
    b.header.ReceiptHash = EmptyReceiptsHash  
} else {  
    b.header.ReceiptHash = DeriveSha(Receipts(receipts), hasher) 
    b.header.Bloom = CreateBloom(receipts) // 调用CreateBloom创建区块头的bloom filter
}

CreateBloom函数的实现：

// CreateBloom creates a bloom filter out of the give Receipts (+Logs)
func CreateBloom(receipts Receipts) Bloom {
	buf := make([]byte, 6)
	var bin Bloom
    // 遍历区块中所有收据
	for _, receipt := range receipts {
        // 遍历收据下的所有Log。 旧版本中，这段代码被单独抽离成一个LogsBloom函数
		for _, log := range receipt.Logs {
			bin.add(log.Address.Bytes(), buf)
            // 遍历Log下的所有topic
			for _, b := range log.Topics {
				bin.add(b[:], buf)
			}
		}
	}
	return bin
}

// LogsBloom returns the bloom bytes for the given logs
func LogsBloom(logs []*Log) []byte {
	buf := make([]byte, 6)
	var bin Bloom
	for _, log := range logs {
		bin.add(log.Address.Bytes(), buf)
		for _, b := range log.Topics {
			bin.add(b[:], buf)
		}
	}
	return bin[:]
}

// Bloom9 returns the bloom filter for the given data
func Bloom9(data []byte) []byte {
	var b Bloom
	b.SetBytes(data)
	return b.Bytes()
}