以太坊状态树

以太坊状态树（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。