賬号狀态存儲在MPT中的應用

關于MPT，這篇文章已經有很詳細的介紹了：https://ethfans.org/posts/merkle-patricia-tree-in-detail 。是以本文不聊MPT的相關内容，隻聊聊賬号在MPT中是怎麼存儲的。

World State，也就是世界狀态，主要就是用來存儲賬戶的狀态的。可以根據塊号查詢某個賬戶的曆史資訊（餘額，交易數），也可以通過最新塊号查詢很久都沒有交易的賬戶資訊都是通過這個世界狀态來實作的。而這些狀态的存儲都是通過MPT來實作的。為了友善了解，會先說代碼邏輯，然後以示例的方式展示賬戶的存儲和更新過程。

既然state中存儲了賬戶的資訊，又能根據塊來查詢賬戶資訊，那是如何根據塊号來定位到賬戶資訊的呢。來看接口

func (s *PublicBlockChainAPI) GetBalance(ctx context.Context, address common.Address, blockNr rpc.BlockNumber) (*big.Int, error) {
	state, _, err := s.b.StateAndHeaderByNumber(ctx, blockNr)
	if state == nil || err != nil {
		return nil, err
	}
	b := state.GetBalance(address)
	return b, state.Error()
}

查詢賬戶餘額的時候，需要先根據塊号來找到對應的state。塊頭中有一個Root字段，存儲的就是目前塊在MTP中的索引，是以這裡的state是通過header.root來定位的。

func (b *HpbApiBackend) StateAndHeaderByNumber(ctx context.Context, blockNr rpc.BlockNumber) (*state.StateDB, *types.Header, error) {
	if blockNr == rpc.PendingBlockNumber {
		block, state := b.hpb.miner.Pending()
		return state, block.Header(), nil
	}
	// Otherwise resolve the block number and return its state
	header, err := b.HeaderByNumber(ctx, blockNr)
	if header == nil || err != nil {
		return nil, nil, err
	}
	stateDb, err := b.hpb.BlockChain().StateAt(header.Root)
	return stateDb, header, err
}

現在知道了Root是入口，那接下來看看這個Root是如何生成的，以及賬戶資訊是如何與Root關聯起來的。為了簡化模型，咱們從零開始，假設現在一個鍊，剛做了初始化，塊0的Root為0x18f74973，此時該root下沒有關聯賬戶。然後設定了挖礦賬戶為0x000001。開啟挖礦，第一個塊挖出來了。現在要對挖礦賬戶進行獎勵了。

現在要解決的問題是

1、什麼時候對挖礦賬戶進行獎勵？

2、如何對挖礦賬戶添加獎勵呢？

3、如何将賬戶與Root關聯起來的。

第一個問題簡單，既然是挖礦，當然是當塊要寫入到鍊中的時候進行獎勵。這個不用細說。看第二個問題，如何如何對挖礦賬戶添加獎勵呢？看代碼，添加獎勵是通過statedb的AddBalance接口進行的。如果statedb中能查到賬戶對應的state_object，就使用查到的，如果查不到就建立一個對應的object。

func (self *StateDB) AddBalance(addr common.Address, amount *big.Int) {
	//log.Error("AddBalance", "addr", addr)
	stateObject := self.GetOrNewStateObject(addr)
	if stateObject != nil {
		stateObject.AddBalance(amount)
	}
}
func (self *StateDB) GetOrNewStateObject(addr common.Address) *stateObject {
	stateObject := self.getStateObject(addr)
	if stateObject == nil || stateObject.deleted {
		stateObject, _ = self.createObject(addr)
	}
	return stateObject
}

看一下statedb與stateobject的資料結構

type StateDB struct {
	db   Database
	trie Trie
	stateObjects      map[common.Address]*stateObject
	stateObjectsDirty map[common.Address]struct{}
	dbErr error
	refund *big.Int
	thash, bhash common.Hash
	txIndex      int
	logs         map[common.Hash][]*types.Log
	logSize      uint
	preimages map[common.Hash][]byte
	journal        journal
	validRevisions []revision
	nextRevisionId int
	lock sync.Mutex
}
type Account struct {
	Nonce    uint64
	Balance  *big.Int
	Root     common.Hash // merkle root of the storage trie
	CodeHash []byte
}
type stateObject struct {
	address  common.Address
	addrHash common.Hash // hash of hpb address of the account
	data     Account
	db       *StateDB
	dbErr error
	trie Trie // storage trie, which becomes non-nil on first access
	code Code // contract bytecode, which gets set when code is loaded
	cachedStorage Storage // Storage entry cache to avoid duplicate reads
	dirtyStorage  Storage // Storage entries that need to be flushed to disk
	dirtyCode bool // true if the code was updated
	suicided  bool
	touched   bool
	deleted   bool
	onDirty   func(addr common.Address) // Callback method to mark a state object newly dirty
}

這裡我們重點關注的是data account，account中存儲了賬号的Balance，即餘額。至此可知，statedb中有了挖礦賬戶對應的stateobject，并存儲在stateObjects中，對于新賬戶是在createObject時放入stateObjects中的。

現在看第3個問題，如何将上面的stateObjects更新到MPT中。在更新獎勵的時候，會統一将statedb中的資料進行送出，代碼如下：通過IntermediateRoot–>Finalise–>updateStateObject,然後傳回s.trie.Hash()，即Root。

func (s *StateDB) Finalise(deleteEmptyObjects bool) {
	for addr := range s.stateObjectsDirty {
		stateObject := s.stateObjects[addr]
		if stateObject.suicided || (deleteEmptyObjects && stateObject.empty()) {
			s.deleteStateObject(stateObject)
		} else {
			stateObject.updateRoot(s.db)
			s.updateStateObject(stateObject)
		}
	}
	s.clearJournalAndRefund()
   }

func (s *StateDB) IntermediateRoot(deleteEmptyObjects bool) common.Hash {
	s.Finalise(deleteEmptyObjects)
	return s.trie.Hash()
}

現在看看updateStateObject是如何處理的。

func (self *StateDB) updateStateObject(stateObject *stateObject) {
	addr := stateObject.Address()
	data, err := rlp.EncodeToBytes(stateObject)
	if err != nil {
		panic(fmt.Errorf("can't encode object at %x: %v", addr[:], err))
	}
	self.trie.TryUpdate(addr[:], data)
}

通過trie.TryUpdate将addr與encode後的stateobject更新到trie中。看下TryUpdate的細節。代碼如下

func (t *Trie) TryUpdate(key, value []byte) error {
	k := keybytesToHex(key)
	if len(value) != 0 {
		log.Warn("zzz TryUpdate", "key", key, "v", value, "k", k)
		_, n, err := t.insert(t.root, nil, k, valueNode(value))
		if err != nil {
			return err
		}
		t.root = n
	} else {
		_, n, err := t.delete(t.root, nil, k)
		if err != nil {
			return err
		}
		t.root = n
	}
	return nil
}

func (t *Trie) insert(n node, prefix, key []byte, value node) (bool, node, error) {
	if len(key) == 0 {
		if v, ok := n.(valueNode); ok {
			return !bytes.Equal(v, value.(valueNode)), value, nil
		}
		return true, value, nil
	}
	switch n := n.(type) {
	case *shortNode:
		matchlen := prefixLen(key, n.Key) //找到key與n.key前幾位重合的長度
		if matchlen == len(n.Key) { //如果key包含了n.Key
			dirty, nn, err := t.insert(n.Val, append(prefix, key[:matchlen]...), key[matchlen:], value)
			if !dirty || err != nil {
				return false, n, err
			}
			return true, &shortNode{n.Key, nn, t.newFlag()}, nil
		}
		// Otherwise branch out at the index where they differ.
		branch := &fullNode{flags: t.newFlag()}
		var err error
		_, branch.Children[n.Key[matchlen]], err = t.insert(nil, append(prefix, n.Key[:matchlen+1]...), n.Key[matchlen+1:], n.Val)
		if err != nil {
			return false, nil, err
		}
		_, branch.Children[key[matchlen]], err = t.insert(nil, append(prefix, key[:matchlen+1]...), key[matchlen+1:], value)
		if err != nil {
			return false, nil, err
		}
		// Replace this shortNode with the branch if it occurs at index 0.
		if matchlen == 0 {
			return true, branch, nil
		}
		return true, &shortNode{key[:matchlen], branch, t.newFlag()}, nil
case *fullNode:
	dirty, nn, err := t.insert(n.Children[key[0]], append(prefix, key[0]), key[1:], value)
	if !dirty || err != nil {
		return false, n, err
	}
	n = n.copy()
	n.flags = t.newFlag()
	n.Children[key[0]] = nn
	return true, n, nil

case nil:
	return true, &shortNode{key, value, t.newFlag()}, nil

case hashNode:
	rn, err := t.resolveHash(n, prefix)
	if err != nil {
		return false, nil, err
	}
	dirty, nn, err := t.insert(rn, prefix, key, value)
	if !dirty || err != nil {
		return false, rn, err
	}
	return true, nn, nil

default:
	panic(fmt.Sprintf("%T: invalid node: %v", n, n))
}

}

TryUpdate的邏輯是判斷value的長度，如果大于0就是插入操作，否則就進行删除。這裡重點關注插入操作。在插入操作中涉及到4中node類型。fullnode,shortnode,hashnode,valuenode。看下定義

type (
	fullNode struct {
		Children [17]node 
		flags    nodeFlag
	}
	shortNode struct {
		Key   []byte 
		Val   node   
		flags nodeFlag
	}
	hashNode  []byte
	valueNode []byte
)

fullnode雖然定義了17個children，但是隻用了前16個，node可以是4種中任意類型。MPT是默克爾樹與字首樹的合并，就是通過這4中node來實作的。繼續看下insert的操作。

因為現在隻有一個賬戶需要更新，而且在insert時傳入的node類型為nil(因為塊0的root沒有關聯賬号)，是以會走到case nil分支，生成一個shortnode，這時，root下對應的就是挖礦賬号0x000001的資訊。假設塊1的Root為0x9eae6bdf，那此時的關聯關系為0x9eae6bdf：[shortnode{0x000001:data}],data是經過編碼的stateobject，包含了account資訊，另外，這裡先忽略nodeflag，之後用到時再說。

需要補充說明的是，塊1的Root是在賬号更新完畢後才生成的，是以演化過程是塊0的Root對應一個空：block(0).Root:[] ，中間過程：block(0).Root:[shortnode{0x000001:data}]，最後根據shortnode{0x000001:data}計算出新的block(1).Root，并更新成block(1).Root，然後寫入資料庫。如此一來，查詢餘額的時候就可以根據塊号1，找到block(1).Root,然後找到shortnode{0x000001:data}，然後根據位址0x000001找到data，從data中解析出餘額。

假如繼續挖礦塊2，礦工0x000002挖到了礦，根據上面的insert代碼，對0x000002的賬戶更新過程變成了如下

1、塊1的root下關聯了礦工0x000001的賬戶，而且是shortnode類型，是以走到shortnode分支。

此時狀态為：block(1).Root:[shortnode{0x000001:data}]

2、賬戶0x000001與賬戶0x000002有着共同的字首0x00000,長度為5,與賬戶0x000001的賬戶長度6不相等，是以不是同一個賬戶。

3、生成一個fullnode，将賬号0x000001寫入到fullnode中。

此時fullnode為 fullnode{ 0:nil, 1:shortnode{0x1:data},2:nil,3:nil…15:nil,16:nil }

4、将賬号0x000002寫入到fullnode中。

此時fullnode為fullnode{ 0:nil, 1:shortnode{0x1:data},2:shortnode{0x2:data},3:nil…15:nil,16:nil }

5、因為matchlen不等于0，是以将shortnode更新後傳回。

此時狀态為：block(1).Root:[ shortnode{0x00000:fullnode{0:nil, 1:shortnode{0x1:data},2:shortnode{0x2:data},3:nil…15:nil,16:nil}} ]

6、然後根據賬戶資訊重新計算出新塊的Root，并将block(2).Root:[ shortnode{0x00000:fullnode{0:nil, 1:shortnode{0x1:data},2:shortnode{0x2:data},3:nil…15:nil,16:nil}} ]寫入到資料庫中。

假設上面的賬戶2與賬戶1沒有重疊的字首，就會傳回一個fullnode。有興趣的可以自己寫一寫。node内部的shortnode可能會合并為一個fullnode，也可能會包含一個fullnode。Root對應的值以hashnode的方式存儲，上面的data就是以valuenode的方式存儲。

這裡就會産生一個問題了，根據以上内容可知，随着賬戶的增多，Root對應的node也會越來越大，那每次更新到資料庫的值也就越來越大。如何避免呢？

資料量的增長是無法避免的，但可以緩解，這是就需要用到nodeflag了。看看nodeflag是什麼：

type nodeFlag struct {
	hash  hashNode // cached hash of the node (may be nil)
	gen   uint16   // cache generation counter
	dirty bool   
}
func (t *Trie) newFlag() nodeFlag {
	return nodeFlag{dirty: true, gen: t.cachegen}
}

nodeflag中重點關注下gen和dirty，gen可以認為是node生成的時間，dirty表示node是否被修改。還記得前文介紹的s.trie.Hash()，看看Hash()都做了什麼，代碼如下

func (t *Trie) Hash() common.Hash {
	hash, cached, _ := t.hashRoot(nil)
	t.root = cached
	log.Warn("zzz Hash", "hashnode", common.BytesToHash(hash.(hashNode)))
	return common.BytesToHash(hash.(hashNode))
}
func (t *Trie) hashRoot(db DatabaseWriter) (node, node, error) {
	if t.root == nil {
		log.Warn("zzz hashRoot", "emptyRoot", hashNode(emptyRoot.Bytes()))
		return hashNode(emptyRoot.Bytes()), nil, nil
	}
	h := newHasher(t.cachegen, t.cachelimit)
	defer returnHasherToPool(h)
	log.Warn("zzz hashRoot", "Root", t.root)
	return h.hash(t.root, db, true)
}
func (h *hasher) hash(n node, db DatabaseWriter, force bool) (node, node, error) {
	// If we're not storing the node, just hashing, use available cached data
	if hash, dirty := n.cache(); hash != nil {
		if db == nil {
			return hash, n, nil
		}
		if n.canUnload(h.cachegen, h.cachelimit) {.
			cacheUnloadCounter.Inc(1)
			return hash, hash, nil
		}
		if !dirty {
			return hash, n, nil
		}
	}
	collapsed, cached, err := h.hashChildren(n, db)
	if err != nil {
		return hashNode{}, n, err
	}
	hashed, err := h.store(collapsed, db, force)
	if err != nil {
		return hashNode{}, n, err
	}
	cachedHash, _ := hashed.(hashNode)
	switch cn := cached.(type) {
	case *shortNode:
		cn.flags.hash = cachedHash
		if db != nil {
			cn.flags.dirty = false
		}
	case *fullNode:
		cn.flags.hash = cachedHash
		if db != nil {
			cn.flags.dirty = false
		}
	}
	return hashed, cached, nil
}

Hash()的作用是将root對應的值以hashnode的形式傳回，其中調用了hashRoot函數，該函數中又主要是調用hash函數，注意hash函數中有個canUnload函數調用，如果canUnload成立，則直接傳回node ，在往下看，通過store函數将node進行存儲并傳回存儲node的hash值。canUnload的判斷标準看代碼，cachelimit預設是120。

func (n *nodeFlag) canUnload(cachegen, cachelimit uint16) bool {
	return !n.dirty && cachegen-n.gen >= cachelimit
}

而cachegen是在每次執行committo函數調用時加1，n.gen是建立node時設定的，代碼如下：

func (t *Trie) CommitTo(db DatabaseWriter) (root common.Hash, err error) {
	hash, cached, err := t.hashRoot(db)
	if err != nil {
		return (common.Hash{}), err
	}
	t.root = cached
	t.cachegen++
	return common.BytesToHash(hash.(hashNode)), nil
}

也就是每經過120次調用後，沒有修改的node将被hash代替，這樣就降低了存儲的量。

get,delete操作都是根據key一層層往下找，找到取出或者删除，搞懂了insert,這兩個的邏輯上就不複雜了。

到這裡，賬戶在MPT中的應用就結束了。

賬号狀态存儲在MPT中的應用

繼續閱讀

Hyperledger Fabric（術語表）

多站點單點登入實作方案

Why and How zk-SNARK Works 1: Introduction & the Medium of a Proof

Cisco官方網站悄然換标

火币鍊轉賬

火币鍊節點監聽記錄火币鍊節點監聽記錄

世鍊投研| 僅一個月追趕DeFi？火币生态鍊Heco有何過人之處？

HyperGraph(HGT)—Heco生态鍊3月最重磅項目釋出

币安鍊、火币鍊提前預知配對合約位址方法Solidity代碼

區塊鍊可能會如何改變音樂行業？

fabric go語言鍊碼打包并在其他Peer節點部署

比特币下跌與加密貨币的關聯效應（附代碼）

在擁有比特币之前了解區塊鍊錢包開發

npm start 啟動和webstorm中的綠色箭頭啟動node服務導緻的差異

2021-09-30一碼在手安全無憂從農田到餐桌，全流程追溯四大子產品，助力客戶實作品牌化

寫作一段時間後，我的反思