以太坊状态树

以太坊状态树(State Trie)是以太坊区块链中的一种数据结构,用于存储网络中所有账户的状态信息。在以太坊中,每个账户都有一个状态,包括账户的余额(以太币数量)、合约代码、以太币的存储空间等。这些账户状态被组织成一个树状结构,称为状态树(State Trie)。

欧易
欧易(OKX)

全球三大交易所之一,注册领50U数币盲盒,币圈常用的交易平台!

币安
币安(Binance)

币安交易所是世界领先的数字货币交易平台,注册领100U。



什么是以太坊状态树?

以太坊状态树(State Trie)是以太坊区块链中的一种数据结构,用于存储网络中所有账户的状态信息。在以太坊中,每个账户都有一个状态,包括账户的余额(以太币数量)、合约代码、以太币的存储空间等。这些账户状态被组织成一个树状结构,称为状态树(State Trie)。

状态树是一种基于Merkle树结构的特殊数据结构,它由多个节点组成,每个节点都包含了一组账户的状态信息。根节点代表整个状态树的根,通过递归地计算子节点的哈希值,可以验证整体数据的完整性和一致性。

在以太坊网络中,每个区块都包含了一组交易信息,这些交易可能会改变账户的状态。当一个新的区块产生时,状态树会根据这些交易来更新账户的状态信息。以太坊使用状态树来记录账户的当前状态,以确保所有节点在任何时间点上都能达成一致。

通过状态树,以太坊网络可以实现账户之间的转账、智能合约的执行以及存储数据等功能。状态树的设计使得以太坊具有高度的安全性和可扩展性,同时也保证了网络中数据的透明性和不可篡改性。

trie tree

trie,来自retrieval(信息检索)中间的几个字母,一般叫做字典树、前缀树,也是一种key-value的存储结构。

trie树存储的是字符串,例如以下几个单词在trie树的存储:

General
Genesis
Go
God
Good

tries的性质:

以太坊状态树

在trie中,每个节点的分支数目取决于key中每个元素的取值范围。以上面例子中的单词为例,每个单词后面的字母都是小写,所以一个节点的分叉数目(branding factor)最多有26个。再加上一个结束标志位,表示到这个地方这个单词就结束了。

trie的查找效率取决于key的长度,key的值越长,查找需要访问内存的次数就越多。

以太坊和比特币的地址是不通用的,两个地址的格式、长度都不同。有一点是类似的,以太坊中的地址也是公钥取哈希转换得来的。但是以太坊中的地址,是在公钥取了哈希之后,进行截取,只保留后面160bit的地址。

以太坊中,key存储的地址,value存储的余额等账户状态。

在以太坊中,160bit的地址表示成40个16进制的数,所以trie分叉数目是17个(16进制的16个数+1个结束标志符)。

trie的优势:

与哈希函数相比,在trie树中,只要两个字符串不同,那么一定会映射到两个不一样的分支,所以不会出现碰撞的情况。

与Merkle tree相比,同样的输入以不同的顺序插入Merkle tree中,得到的是两个不同的Merkle tree。但是在trie树中,只要是相同的输入,不管以什么样的顺序,最后插入trie中构造出来的树是一样的。

trie有很好的局部更新性,如果要修改某个key,只需要访问这一个key对应的分支即可。

trie的缺点:

对于图中E、N这样只有一个子节点的“一脉单传”的节点,在存储上有一些浪费。如果将这些只有一个子节点的节点进行合并,可以减少存储上的开销,同时也提高了查找的效率。

Patricia tree

Patricia tree(也称为patricia trie),就是经过了路径压缩的trie tree,所以也称“压缩前缀树”。

例如上面例子中的trie tree,经过路径压缩后,变为以下样子:

以太坊状态树

对于Patricia Tree,如果新插入一个单词,原来压缩的路径可能需要扩展开来。

如果键值分布比较稀疏(整棵树中的单词数量不多,但是每个单词都很长),此时适合使用Patricia Tree进行路径压缩。

例如以下几个单词:

misunderstanding
decentralization
disintermediation

在trie tree中的存储:

以太坊状态树

在patricia tree中的存储:

以太坊状态树

对于以太坊,地址是160位的,所以共有2的160次方种可能,值域空间非常非常大,所以其结构也非常非常稀疏。

以太坊的地址之所以要设计的很长、很稀疏,就是为了防止地址出现碰撞。看上去似乎有些浪费,但这是去中心化系统防止冲突的唯一方法。

所以以太坊的地址的数据结构要使用patricia tree。

MPT

MPT:即Merkle Patricia Trie。

把所有的账户组合成一个trie tree,通过路径压缩变为Patricia trie,然后将指针换成哈希指针,变成Merkle Patricia trie。最后可以计算出一个根哈希值,写到block header中。

有了根哈希值,就可以防止整棵树被篡改。另外,还可以提供Merkle Proof,可以证明账户的状态余额。而且,还可以证明某个账户在MPT树中不存在。

以太坊中的MPT

Modified MPT

以太坊中使用的不是原生的MPT,而是修改后的Modified MPT。

Modified MPT对MPT做了一些修改,但是这些修改不是很本质的修改。

Modified MPT示例:

以太坊状态树

节点值变化时新建分支

每次发布一个新的区块时,这个树中有一些节点的值会发生变化,这些改变不是在原地改的,而是新建一些分支,原来的状态其实是保留下来的。

所以系统中每个全节点,需要维护的不是一个MPT,而是每次出现新区块时都要新建一个MPT。只不过这些状态树中大部分节点是共享的,只有少部分发生变化的节点是要新建分支的。

每个区块都保存当时的MPT状态的原因

为什么要在每个区块都记录一个MPT(即记录MPT的各个区块时候历史状态),而不是直接在MPT中修改账户最终的状态(只维护一棵MPT树,直接更新状态)?主要是为了出现分叉时候的undo。

以下图为例,如果区块3记录了A转给B账户10 ETH,如果不记录历史状态,直接将A账户余额减去了10 ETH。

而分叉的区块2没有打包该交易,等区块2后面的区块4再打包该交易时,就无法再得到账户A在区块1发布时候的余额。

以太坊状态树

如果只是像比特币那样简单的A转账给B账户10 ETH,那么区块4可能还可以通过区块3上的转账脚本进行反推。可是以太坊支持智能合约,其脚本是图灵完备的,区块3中的脚本内容可能非常复杂,导致无法进行反推回区块1发布时的A账户余额。

以太坊中代码的数据结构

区块头:来源

// Header represents a block header in the Ethereum blockchain.
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"`
    // bloomfilter,布隆过滤器,和收据树相关,提供了一种高效的查询符合某种条件的交易的执行结果
    Bloom           Bloom          `json:"logsBloom"        gencodec:"required"`
    // 挖矿难度,和比特币一样会根据需要调整
    Difficulty      *big.Int   	   `json:"difficulty"       gencodec:"required"`
    Number          *big.Int       `json:"number"           gencodec:"required"`
    // GasLimit、GasUsed和汽油费相关,智能合约要消耗汽油费,类似比特币中的交易费
    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、Nonce和挖矿相关。Nonce有些类似比特币的Nonce,也是要猜符合难度要求的随机数。
    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"`
}

区块体:

// Body is a simple (mutable, non-safe) data container for storing and moving
// a block's data contents (transactions and uncles) together.
type Body struct {
	Transactions []*Transaction
	Uncles       []*Header
	Withdrawals  []*Withdrawal `rlp:"optional"`
}

区块整体结构:

// Block represents an entire block in the Ethereum blockchain.
type Block struct {
    // block header
	header       *Header
    // 叔父区块的block header。一个区块可以有多个叔父区块
	uncles       []*Header
    // 交易列表
	transactions Transactions
    
	withdrawals  Withdrawals

	// caches
	hash atomic.Value
	size atomic.Value

	// These fields are used by package eth to track
	// inter-peer block relay.
	ReceivedAt   time.Time
	ReceivedFrom interface{}
}

该区块最后真正在网上发布时候的信息结构:

// "external" block encoding. used for eth protocol, etc.
type extblock struct {
	Header      *Header
	Txs         []*Transaction
	Uncles      []*Header
	Withdrawals []*Withdrawal `rlp:"optional"`
}

MPT中value的存储

状态树中,key保存的是账户的地址,value保存的是序列化后的账户的状态。

账户的状态在保存进MPT树之前,需要先用RLP编码进行序列化,然后再进行存储。

RLP(Recursive Length Prefix),是一种序列化方法,特点是极简单。

谷歌的protobuf(全称protocal buffer,简称pb)是一个很常用的序列化库。和protobuf等这些常见的序列化方式相比,RLP的理念就是越简单越好。

RLP只支持一种类型nested array of bytes(一个个字节组成的数组,可以嵌套)。以太坊中的其他类型(int、hash等)最后都要转换成nested array of bytes。

© 版权声明

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...