Dapp状态去哪了 🔗

世界状态 🔗

我们知道区块链每一笔执行成功的交易，背后都对应着世界状态的变化；可以是资产所有权的变更，亦或是账户余额的变化。作为dapp开发人员，你可能只关心自己合约的状态，而整个区块链是如何组织和存储世界状态的呢？

状态读写抽象 🔗

如果写过智能合约，我们会发现绝大多数的区块链底层都提供了最基础的KV存储模型。

Fabric中的状态读写接口 🔗

如果你开发过Fabric的chaincode，你肯定使用过下面的接口。非常明确的将状态读写接口暴露给chaincode开发人员。

	// GetState returns the value of the specified `key` from the
	// ledger. Note that GetState doesn't read data from the writeset, which
	// has not been committed to the ledger. In other words, GetState doesn't
	// consider data modified by PutState that has not been committed.
	// If the key does not exist in the state database, (nil, nil) is returned.
	GetState(key string) ([]byte, error)

	// PutState puts the specified `key` and `value` into the transaction's
	// writeset as a data-write proposal. PutState doesn't effect the ledger
	// until the transaction is validated and successfully committed.
	// Simple keys must not be an empty string and must not start with a
	// null character (0x00) in order to avoid range query collisions with
	// composite keys, which internally get prefixed with 0x00 as composite
	// key namespace. In addition, if using CouchDB, keys can only contain
	// valid UTF-8 strings and cannot begin with an underscore ("_").
	PutState(key string, value []byte) error

查看底层处理状态读写的代码，我们可以看到底层的存储接口增加了namespace的前缀，这个namespace实际上对应的是chaincodeID。

func (q *queryExecutor) getState(ns, key string) ([]byte, []byte, error) {
	if err := q.checkDone(); err != nil {
		return nil, nil, err
	}
	versionedValue, err := q.txmgr.db.GetState(ns, key)
	if err != nil {
		return nil, nil, err
	}
	val, metadata, ver := decomposeVersionedValue(versionedValue)
	if q.collectReadset {
		q.rwsetBuilder.AddToReadSet(ns, key, ver)
	}
	return val, metadata, nil
}

// SetState implements method in interface `ledger.TxSimulator`
func (s *txSimulator) SetState(ns string, key string, value []byte) error {
	if err := s.checkWritePrecondition(key, value); err != nil {
		return err
	}
	s.rwsetBuilder.AddToWriteSet(ns, key, value)
	return nil
}

Solidity中的状态变量 🔗

而你如果使用Solidity编写过智能合约，你可能会发现并没有明确的状态读写接口，但是你一定会用到State Variables。状态变量的读写在EVM的执行过程中会对应到指令码SLOAD和SSTORE。

contract ExampleContract { 
    uint storedData; // State variable
    event Sent ( msg ); 
    constructor () public {}
    
    function method ( uint x) public { 
        storeData = x;
        emit Sent ('Success');
   }
}

查看hyperledger/burrow项目实现的EVM，我们可以看到实际底层也是类似的KV存储。同样的我们发现在底层存储中增加了params.Callee这样一个类似的namespace，这里对应的其实是合约账户地址。

case SLOAD: // 0x54
    loc := stack.Pop()
    data := LeftPadWord256(maybe.Bytes(st.CallFrame.GetStorage(params.Callee, loc)))
    stack.Push(data)
    c.debugf("%v {0x%v = 0x%v}\n", params.Callee, loc, data)

case SSTORE: // 0x55
    loc, data := stack.Pop(), stack.Pop()
    maybe.PushError(engine.UseGasNegative(params.Gas, engine.GasStorageUpdate))
	maybe.PushError(st.CallFrame.SetStorage(params.Callee, loc, data.Bytes()))
    c.debugf("%v {%v := %v}\n", params.Callee, loc, data)

状态数据库 🔗

前面我们已经知道了合约中的状态读写接口是怎么和区块链底层关联的，但是状态又是如何持久化到状态数据库中的呢？绝大部分的区块链都是使用的KV数据库来作为状态数据库，但是也有一些区块链支持关系数据库和文档数据库等。

我们这里只介绍KV状态数据库，下面以Fabric和Go-ethereum为例子来看看它们是如何处理的。因为KV是非常简单的模型，我们只要搞清楚KEY和VALUE是如何编解码的，我们就能理解整个区块链中的状态管理。

Fabric数据库中的KEY和VALUE 🔗

首先我们需要知道Fabric中有channel和chaincode的概念，每一个channel对应于一条独立的区块链，每一个chaincode对应于一个独立的智能合约。在内存中Fabric会使用多级Map的数据结构来组织整个状态数据，而其实底层只使用一个KV数据库作为状态数据库。

其中KEY的编码是将内存中的层级结构铺平，由channelID，chaincodeID和用户自己定义的key拼接而成。

channelID + chaincodeID + user_defined_key

而VALUE的编码则是和RWSet紧密相关，可通过官方文档Read-Write set semantics章节了解RWSet的概念。

根据下面的proto数据结构定义，可以看出实际数据库中的VALUE除了包含用户自定义的Value，还包括了Version和Metadata两个附加的值，而Version的值实际上是Height编码后的内容。

type DBValue struct {
	Version              []byte   `protobuf:"bytes,1,opt,name=version,proto3" json:"version,omitempty"`
	Value                []byte   `protobuf:"bytes,2,opt,name=value,proto3" json:"value,omitempty"`
	Metadata             []byte   `protobuf:"bytes,3,opt,name=metadata,proto3" json:"metadata,omitempty"`
	XXX_NoUnkeyedLiteral struct{} `json:"-"`
	XXX_unrecognized     []byte   `json:"-"`
	XXX_sizecache        int32    `json:"-"`
}

type Height struct {
	BlockNum uint64
	TxNum    uint64
}

Go-ethereum数据库中的KEY和VALUE 🔗

如果稍微了解过Ethereum，应该知道Ethereum中有一个特别的数据结构PATRICIA MERKLE TREES。MPT实际被应用到多个模块，而和状态密切相关的，主要是World State Trie和Storage Trie。

虽然PATRICIA MERKLE TREES有Branch node，Extension node和Leaf node等多种类型(不讨论NULL节点)；同时在Ethereum中每一个Address都对应了一棵World State Trie，并且如果Address是一个合约地址，还同时对应了一棵Storage Trie。但是对于状态数据库中的KEY和VALUE编码，实际上可以只用一条统一的规则描述。

𝑘𝑒𝑐𝑐𝑎𝑘 (𝑅𝐿𝑃 (𝑛𝑜𝑑𝑒)) → 𝑅𝐿𝑃 (𝑛𝑜𝑑𝑒)

𝑘𝑒𝑐𝑐𝑎𝑘是Ethereum使用的hash算法，而𝑅𝐿𝑃是Ethereum使用的编解码格式。

• Extension 𝑛𝑜𝑑𝑒 ≡ [𝐻𝑃 (𝑝𝑟𝑒𝑓𝑖𝑥 + 𝑝𝑎𝑡ℎ), 𝑘𝑒𝑦]
• Branch 𝑛𝑜𝑑𝑒 ≡ [𝑏𝑟𝑎𝑛𝑐ℎ𝑒𝑠, 𝑣𝑎𝑙𝑢𝑒]
• Leaf 𝑛𝑜𝑑𝑒 ≡ [𝐻𝑃 (𝑝𝑟𝑒𝑓𝑖𝑥 + 𝑝𝑎𝑡ℎ), 𝑣𝑎𝑙𝑢𝑒]

𝐻𝑃代表的是Hex Prefix Encoding，𝑝𝑟𝑒𝑓𝑖𝑥指的是用于区分不同的Extension和Leaf的node的标志位。

从上述的规则我们可以看到，Ethereum的状态数据库是把所有MPT的节点进行了存储，而对应KEY是节点编码后的hash值，而VALUE就是节点编码的实际值。

内存中的状态 🔗

前面我们说到了面向用户的状态读写抽象和状态是如何被持久化到数据库中的，下面我们来说一说位于两者中间的内存中的状态。

全局缓存 🔗

类似操作系统或者数据库系统，为了提升效率，区块链会将状态数据库中的数据在内存中进行缓存。全局的缓存通常是一个有序Map的数据结构，缓存的内容实际就是数据库中的KEY和VALUE。

区块执行时的状态 🔗

区块的执行实际就是执行该区块中的全部交易，交易在执行时都是从当前最新的世界状态中去读取数据，而将对状态的变更先更新到当前执行上下文的内存数据结构中；当全部交易执行完成后，将当前上下文中变更了的状态整个提交到状态数据库和全局缓存中。下面我们还是以Fabric和Go-ethereum为例子来看看它们分别是怎么处理的。

Fabric内存中的状态表示 🔗

Fabric的整体执行流程是Execute->Orderer->Validate方式，因此它的交易内容中的RWSet，实际上是该交易执行时读写过的状态，每笔交易执行时读取的状态都是以上一个区块提交后的世界状态为基准，写入的状态则写入到当前交易上下文的WSet中。因为所有交易的读取都是以上一个区块提交后的世界状态为基准，所以可能存在状态更新冲突的交易（还是参考Read-Write set semantics），在Validate阶段进行MVCC验证过程中，会保证冲突的交易只有一笔能够成功。而验证完后的结果实际上就得到了一个Batch对象，保存了所有成功交易变更过的状态的集合。

// UpdateBatch encapsulates the updates to Public, Private, and Hashed data.
// This is expected to contain a consistent set of updates
type UpdateBatch struct {
	PubUpdates  *PubUpdateBatch
	HashUpdates *HashedUpdateBatch
	PvtUpdates  *PvtUpdateBatch
}

// PubUpdateBatch contains update for the public data
type PubUpdateBatch struct {
	*statedb.UpdateBatch
}

// UpdateBatch encloses the details of multiple `updates`
type UpdateBatch struct {
	ContainsPostOrderWrites bool
	Updates                 map[string]*nsUpdates
}

type nsUpdates struct {
	M map[string]*VersionedValue
}

这里我们不讲HashedUpdateBatch和PvtUpdates(与其内部其他特性有关)，我们可以看到PubUpdates实际上就是一个两级的Map结构，外层的KEY就是chaincodeID，内层的KEY就是用户在调用PutState方法传入的KEY。这里我们没有看到channelID这个维度，是因为每个channel实际上都是独立的区块链，所以一个区块中是不可能包含其他channel的状态变更的，在最后Batch写入状态数据库的时候会统一的把这个区块所在的channelID拼接上。

Go-ethereum内存中的状态表示 🔗

MERKLE PATRICIA TRIE简介 🔗

在MPT中有三种node类型(不考虑NULL节点)

• Branch – a 17-item node [𝑖0,𝑖1, …,𝑖15, 𝑣𝑎𝑙𝑢𝑒]
• Extension – A 2-item node [𝑝𝑎𝑡ℎ, 𝑘𝑒𝑦]
• Leaf – A 2-item node [𝑝𝑎𝑡ℎ, 𝑣𝑎𝑙𝑢𝑒]

The Branch node is used where branching takes place, i.e. keys at certain character position starts to differ. First 16 items are used for branching, which means that this node allows for 16 possible branches for 0 ′ 𝐹 hex character. This concept is familiar from the Memory Trie structures, where branching was constructed as a column in a table. The 𝑖∀position contains a link to a child node whenever the child exists, i.e. this position corresponds with a next character (hex 0 ′ 𝐹 ) in a key. The 17th item stores a value and it is used only if this node is terminating (for a certain key).

我们可以看到Branch节点的前16个item会存储child node的指针（实际就是child node的𝑘𝑒𝑐𝑐𝑎𝑘 (𝑅𝐿𝑃 (𝑛𝑜𝑑𝑒))），所以我们可以通过这个指针从状态数据库或者是全局缓存中加载并解码得到child node对象，以此类推我们可以在内存中逐步构建出MPT（实际上我们只会加载本次区块执行过程中所有交易读写过的节点）。而最后一个item是用来存储value的，这个value存储的不是一个节点指针而是一个实际的值。value可以看后面一个例子。

The Extension node is where the compression takes place. Whenever there is a part common for multiple keys, this part is stored in this node. In other words, it prevents descending several times should it follow only one path. This node, in other words, resembles a Patricia feature of number of bits to skip.

Extension的作用非常明显，就是用于减少path上公共前缀的存储，压缩path。其中path item存储的是公共前缀，value是存储的是一个节点指针，同样可以根据这个指针加载出新的节点。

The Leaf node terminates the path in the tree. It also uses a compression as it groups common suffixes for keys in the 𝑝𝑎𝑡ℎ, which is a concept re-used again from Memory Trie.

Leaf用于存储实际的值。

从下面这个例子可以直观的看到Branch node中value存储的是KEY正好匹配到EXTENSION公共前缀对应的值。同时Leaf node中的前缀10代表的path是偶数长度的叶子节点类型（关于前缀的部分可以参考Yellow Paper中 Appendix C. Hex-Prefix Encoding部分）。

MPT的构建 🔗

Go-ethereum内存中的状态表示其实之前已经提到了，就是World State Trie和Storage Trie。Go-ethereum中的状态变量和状态数据库中存储的KEY和VALUE看起来似乎没有明显的关联，用户不需要自己定义KEY，那状态变量的值是怎么跑到Storage Trie的节点里的呢？

我们从下面这张整体的图中，我们可以看到Storage Trie的root是存储在对应的World State Trie的node里的，而World State Trie的root是存储在对应的Block header里的。

当我们执行一个新的区块时，我们需要从上一个区块的Block header中取出最新的World State Trie的root，这个root实际上就是𝑘𝑒𝑐𝑐𝑎𝑘 (𝑅𝐿𝑃 (𝑛𝑜𝑑𝑒))，这样我们就可以从状态数据库或者是全局缓存中加载出World State Trie的𝑅𝐿𝑃 (𝑛𝑜𝑑𝑒)，解码后我们就得到了实际的root node对象。以此类推，我们就可以从root node开始，通过节点中存储的child node指针，加载出需要用到的World State Trie节点。因为World State Trie的Leaf node中存储的value实际上就是Go-ethereum中的Account对象，当这个Account对象对应的是一个合约的时候，它的storageRoot字段存储的就是Storage Trie的root。同理，我们就可以加载出用到的Storage Trie节点。

World State Trie中的KEY和VALUE 🔗

World State Trie中的KEY和VALUE可以描述为

𝑘𝑒𝑐𝑐𝑎𝑘 (𝑎𝑑𝑑𝑟𝑒𝑠𝑠) → 𝑅𝐿𝑃 (𝐴)

KEY的值是20字节的Address生成32字节的哈希，然后经过HEX编码后，映射到World State Trie的路径。而Leaf节点中存储的值是𝑅𝐿𝑃 (𝐴)，这个A就是我们前面提到的Account对象。

Account对象中包含如下属性

• nonce 是一个自增的整数，对于外部账号，这个值代表从这个地址发出过的交易数；而对于合约账号，这个值代表合约的创建次数。
• balance 代表账户中的余额。
• storageRoot 外部账户这个值为空，合约账号这个值存储了Storage Trie的根节点哈希。
• codeHash 外部账户这个值为空，合约账号这个值对应合约源代码的哈希。

Storage Trie中的KEY和VALUE 🔗

Storage Trie的KEY和VALUE是最复杂的，因为这里和Solidity的数据类型布局紧密相关，用一个通用的方式描述如下

𝑘𝑒𝑐𝑐𝑎𝑘 (𝑖𝑛𝑑𝑒𝑥) → 𝑅𝐿𝑃 (𝑠𝑙𝑜𝑡)

Storage Trie中的Leaf节点存储的值就是slot，这个slot实际上就是一个长度32的字节数组，而index就是用于定位这个slot的值（可能就是slot的序号，也可能是(序号+key)）。slot的序号就是根据我们Solidity代码中定义的State Variables的顺序产生。

KEY的实际值就是index的哈希，然后经过HEX编码后，我们就能将KEY映射成Storage Trie的path，然后将slot存储到Storage Trie的Leaf节点中。

下面看看不同类型的slot的例子，更详细的描述请参考Solidity官方文档layout_in_storage章节。

• Statically Sized Variables

  

定长类型的变量会根据类型长度，多个变量共享或者单个变量独占一个slot。

• Maps

  

Map的index包含了用户key，从这个布局中我们就能看到实际上并没有存储用户key的原值，同时也没有存储Map的size，所有我们在Solidity中不能直接迭代mapping。

• Dynamic Arrays

  

动态数组的index包含了数组中的位置，同时还存储了数组的size。

• Byte Arrays and String

  

对于字节数组和字符串，如果长度小于32，就用一个slot存储，同时最后一个字节存储实际长度。如果长度更长，则使用和动态数组一样的方式存储。

MPT的提交 🔗

在区块所有交易执行完成后，所有成功执行的交易导致变化过的MPT节点，最后会统一更新到状态数据库和全局缓存。根据Ethereum数据库中的KEY和VALUE的内容，我们知道了对于底层数据库来说实际只会新插入数据（状态膨胀问题）。同时我们还要注意，因为Leaf中的值改变了，导致Leaf节点内容变化了，Leaf节点的hash也变化了，意味着Branch节点中的节点指针也变化了，所以Branch节点的内容实际也变化了，以此类推，一直会得到一个变化了的root。这个正是MPT结构中Merkle tree的体现，利用这个性质，我们可以通过Merkle proof来证明MPT节点的存在性。所以MPT是一种Authenticated Storage，对于拥有Light client的链来说，是一种必要的属性。

结语 🔗

随着Fabric和Go-ethereum的不断更新迭代，上述内容可能会过时，但是不妨碍我们了解到区块链中对于状态管理的整体的设计思路。实际上针对状态膨胀问题Go-ethereum已经在从hash-based state scheme切换到path-based state scheme，而另一个数据结构Verkle trie将很可能替换MPT用于解决proof size过大的问题。有兴趣的朋友可以自行了解。

纸上得来终觉浅，我创建了一个项目verkle用来学习verkle trie，主要参考go-verkle。目前代码只实现了很少的一部分，有兴趣的朋友可以一起来动动手。