ETH交易树和收据树

发布时间:2024-06-28 14:12:09

在以太坊网络中,所有的交易都被记录在一个称为区块(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()
}

最新专题

  • LEO币历史价格走势图
    LEO币历史价格走势图

    LeoToken是一种区块链项目,致力于构建一个去中心化的金融生态系统。LeoToken项目的主要目标是提供支付、借贷、稳定币等金融服务,通过智能合约和区块链技术,实现金融服务的自动化和跨境支付的便捷性。LeoToken所处的赛道是金融科技领域,该领域利用区块链技术和数字货币创新金融服务模式,颠覆传统金融体系。通过区块链的去中心化特性和智能合约的自动化执行,LeoToken项目可以提供更高效、更安全的金融服务,同时降低成本和提升用户体验。本专题带您回顾LEO币历史价格走势图与LEO币历史最高价最低价,希望对您带来帮助。

    加密货币专题 2024-07-03 10:01 990
  • LINK币历史价格走势图
    LINK币历史价格走势图

    Chainlink是一个区块链项目,旨在连接区块链智能合约与外部数据源和服务。它通过引入预言机(Oracle)的概念来解决智能合约无法直接访问外部数据的问题。预言机充当了区块链与外部世界沟通的桥梁,将外部数据传输到区块链上,为智能合约提供实时和准确的信息。Chainlink的预言机可以连接各种数据源,包括互联网API、传感器数据、天气信息等。通过这种方式,智能合约可以访问并利用这些外部数据,从而扩展了区块链应用的可能性。例如,基于天气数据的保险产品、基于运输数据的智能合约等都可以通过Chainlink的预言机实现。本期专题带您回顾LINK币历史价格走势图与LINK历史最高价最低价,希望对你带来帮助。

    加密货币专题 2024-07-03 09:54 752
  • DOT币历史价格走势图
    DOT币历史价格走势图

    波卡(Polkadot)是一个由以太坊联合创始人之一加文·伍德(Gavin Wood)创建的区块链项目。波卡的目标是构建一个多链架构的区块链网络,旨在解决现有区块链网络的扩展性、互操作性和治理性等问题。波卡引入了一种创新的多链架构,通过主网络(Relay Chain)连接多条平行链(Parachains),每条平行链可以根据自身需求进行定制化,从而实现各种不同的功能和性能。这种架构有效地提高了整个网络的扩展性,使得系统能够更好地处理大量交易和数据。本期专题带大家回顾波卡DOT币历史价格走势图与DOT币历史最高价最低价,希望对您有帮助。

    加密货币专题 2024-07-03 09:44 1087
  • BCH币历史价格走势图
    BCH币历史价格走势图

    Bitcoin Cash (BCH)是比特币的一个硬分叉项目,旨在解决比特币网络拥堵和交易费用高涨的问题。它于2017年8月从比特币区块链中分叉出来,其首要目标是提高比特币的吞吐量,降低交易成本,并加速交易确认时间。Bitcoin Cash的支持者认为,通过增加区块大小限制,网络将能够处理更多交易,并提高整体的可扩展性。本文为您带来BCH币历史行情价格走势图以及BCH币历史最高价最低价,希望对您有所帮助。

    加密货币专题 2024-07-03 09:37 1517
  • AVAX币历史价格走势图
    AVAX币历史价格走势图

    Avalanche是一个开源的区块链平台,旨在解决现有区块链网络中的可伸缩性、安全性和去中心化之间的平衡问题。其采用了一种名为Avalanche Consensus的共识算法,该算法被认为是一种快速、高效、安全且具有高度去中心化的共识协议。本专题主要介绍AVAX币历年来的价格行情(最高价,最低价)及AVAX币历史行情价格走势图。

    加密货币专题 2024-07-03 09:27 569
  • OKB币历史价格走势图
    OKB币历史价格走势图

    OKB币是OKEx交易所发行的代币,而OKEx是全球知名的加密货币交易平台。OKB币是基于以太坊区块链发行的代币,具有类似于数字货币的特性,可以在OKEx平台上用于支付交易手续费、参与平台治理和其他用途。OKB币在OKEx生态系统中扮演着重要的角色,拥有一定的使用场景和功能。

    加密货币专题 2024-07-03 09:17 934
  • BTG币最新价格,BTG币最新消息
    BTG币最新价格,BTG币最新消息

    BTG全称BitcoinGold,也有人称之为BitcoinGPU,起源是一个由开发者组织发起的一个反对segwit2x的活动:“NO2X”。 BTG是对比特币区块链进行硬分叉得到的一种新的数字货币,其主要特点为: 类似于Bitcoin Cash,BTG也会添加SIGHASH_FORKED(一种硬分叉后的安全机制)。

    加密货币专题 2024-06-28 17:43 640
  • ROSE币最新价格,ROSE币最新消息
    ROSE币最新价格,ROSE币最新消息

    Oasis Labs借助区块链技术构建的新型云计算平台不仅具备了可扩展性,还解决了传统云计算平台存在的隐私保护问题。通过实现分布式架构和数据加密,Oasis Labs为用户提供了更加安全和可靠的云计算服务,助力用户更好地管理和保护自己的数据。随着区块链技术不断发展和完善,相信Oasis Labs的新型云计算平台将在未来得到更广泛的应用和认可。

    加密货币专题 2024-06-27 18:47 618