主要涉及代码

• trie
• core
• core/rawdb
• core/state
• ethdb/leveldb

需要掌握的知识点

• StateDB Trie Account stateObject

• 账户数据如何存储在Trie中

  • 账户数据的存储是使用SecureTrie中的，主要是使用keecak512(key)作为真实的key存在levelDB中。
  • 由于key为[]byte类型，范围为0 ~ 255。为了fullNode数组长度不会太大浪费空间，会将key拆成nibble（以太坊定义一个nibble == 二分之一个byte），这样将数组定义的长度256将为16个（数组最后一个用来存值）。将key拆成nibble的过程中，在最后加了一个结尾符号16，其主要目的是为了区分扩展节点与叶子节点。比如分别将key1:646f65t，key2:646f67t作为key插入。第一次key1:646f65t为叶子节点，再插入key2则以key1，key2的公共key:646f6作为扩展节节点，val为分支节点。其主要作用是这样设计在内存方便访问。

    func keybytesToHex(str []byte) []byte {
    l := len(str)*2 + 1
    var nibbles = make([]byte, l)
    for i, b := range str {
    nibbles[i*2] = b / 16
    nibbles[i*2+1] = b % 16
    }
    nibbles[l-1] = 16
    return nibbles
    }

  • nonce, balance, mptRoot, codeHash 以RLP形式编码作为value存在Trie中

• 账户数据在Trie中的更新

• 如何将Trie存到levelDB中去。 trie.Commit

  • 使用多线程将整棵树未计算的哈希计算出来。trie.Hash()
  • 将需要提交的数据进行处理，主要是计算节点的数据大小，key由nibble转byte，处理完成之后将节点数据转为leaf通过通道的方式发动到内存数据库，内存数据库缓存过来的数据以及更新脏值相关信息。committer.commit(), committer.store()，database.insert()
  • 内存数据库将发送过来的值缓存到内存中。committer.commitLoop()
  • 每出一个新快，执行数据库的引用与解引用(为了释放Trie树？)，执行数据库的写操作最终落盘。直接进行写入：database.Commit()。根据条件比如是超过了缓存在数据库中规定的大小进行写入：database.Cap()
    
    

INFO [08-04|15:35:18.248] Imported new chain segment               blocks=66   txs=7350    mgas=510.504  elapsed=8.028s      mgasps=63.587  number=7,784,332 hash=502762..81558d age=2y2mo4w   dirty=1.29GiB
INFO [08-04|15:35:46.992] Imported new chain segment               blocks=28   txs=3249    mgas=199.757  elapsed=28.744s     mgasps=6.949   number=7,784,360 hash=cbaf6e..4e2f11 age=2y2mo4w   dirty=1.29GiB
INFO [08-04|15:36:13.773] Imported new chain segment               blocks=1    txs=127     mgas=7.999    elapsed=26.781s     mgasps=0.299   number=7,784,361 hash=89e47e..d59274 age=2y2mo4w   dirty=1.29GiB
INFO [08-04|15:36:16.295] Deep froze chain segment                 blocks=212  elapsed=19.035s     number=7,694,360 hash=e06e45..9d1dcb
WARN [08-04|15:51:24.291] Checkpoint challenge timed out, dropping id=45c593da62c28562 conn=staticdial         addr=220.249.16.230:30303  type=Geth/v1.10.3-unstabl...
WARN [08-04|15:52:06.513] Checkpoint challenge timed out, dropping id=45c593da62c28562 conn=staticdial         addr=220.249.16.230:30303  type=Geth/v1.10.3-unstabl...
WARN [08-04|15:56:06.553] Served eth_coinbase                      conn=172.16.0.117:64612 reqid=725  t="27.802µs"   err="etherbase must be explicitly specified"
WARN [08-04|15:56:09.695] Served eth_coinbase                      conn=172.16.0.117:56266 reqid=846  t="21.357µs"   err="etherbase must be explicitly specified"
WARN [08-04|15:56:10.500] Served eth_coinbase                      conn=172.16.0.117:56266 reqid=850  t="36.374µs"   err="etherbase must be explicitly specified"
INFO [08-04|15:56:27.571] Persisted trie from memory database      nodes=5,832,133  size=1.20GiB    time=20m22.96008813s  gcnodes=31,170,856 gcsize=12.01GiB  gctime=2m25.98558795s  livenodes=231,435 livesize=-255228038.00B

// trie/trie.go 517
// 注意：
// SecureTrie 的 kv 对
// key: "secure-key-" + keecak256(key)
// value: key
func (t *Trie) Commit(onleaf LeafCallback) (root common.Hash, err error) {
  ...
    if db.preimages != nil {
        rawdb.WritePreimages(batch, db.preimages) // 将 key 与 keecak512(key) 写入到leveldb中
    }
  ...
}

// trie/trie.go 517
// 这里将nodeFlag即key:hash(node), value:RLP([node.key, node.value])存入数据库中。为了节省空间，node.key是使用将nibble转为byte即调用hexToCompact后的key。
func (db *Database) commit(hash common.Hash, batch ethdb.Batch, uncacher *cleaner, callback func(common.Hash)) error {
  ...
    rawdb.WriteTrieNode(batch, hash, node.rlp()) // 将 keecak256(key) 与 节点数据写入到leveldb中
  ...
}

• 如何将数据从levelDB中读取出来恢复到Trie中

  // trie/trie.go 499
  func (t *Trie) resolveHash(n hashNode, prefix []byte) (node, error) {
  hash := common.BytesToHash(n)
  if node := t.db.node(hash); node != nil {
      return node, nil
  }
  return nil, &MissingNodeError{NodeHash: hash, Path: prefix}
  }

• MPT的证明

开发模式的genesis配置

core/genesis.go 415

func DeveloperGenesisBlock(period uint64, faucet common.Address) *Genesis {
    // Override the default period to the user requested one
    config := *params.AllCliqueProtocolChanges
    config.Clique = &params.CliqueConfig{
        Period: period,
        Epoch:  config.Clique.Epoch,
    }

    // Assemble and return the genesis with the precompiles and faucet pre-funded
    return &Genesis{
        Config:     &config,
        ExtraData:  append(append(make([]byte, 32), faucet[:]...), make([]byte, crypto.SignatureLength)...),
        GasLimit:   11500000,
        BaseFee:    big.NewInt(params.InitialBaseFee),
        Difficulty: big.NewInt(1),
        Alloc: map[common.Address]GenesisAccount{
            common.BytesToAddress([]byte{1}): {Balance: big.NewInt(1)}, // ECRecover
            common.BytesToAddress([]byte{2}): {Balance: big.NewInt(1)}, // SHA256
            common.BytesToAddress([]byte{3}): {Balance: big.NewInt(1)}, // RIPEMD
            common.BytesToAddress([]byte{4}): {Balance: big.NewInt(1)}, // Identity
            common.BytesToAddress([]byte{5}): {Balance: big.NewInt(1)}, // ModExp
            common.BytesToAddress([]byte{6}): {Balance: big.NewInt(1)}, // ECAdd
            common.BytesToAddress([]byte{7}): {Balance: big.NewInt(1)}, // ECScalarMul
            common.BytesToAddress([]byte{8}): {Balance: big.NewInt(1)}, // ECPairing
            common.BytesToAddress([]byte{9}): {Balance: big.NewInt(1)}, // BLAKE2b
            faucet:                           {Balance: new(big.Int).Sub(new(big.Int).Lsh(big.NewInt(1), 256), big.NewInt(9))},
        },
    }
}

状态数中账户结构

core/state/state_object.go 102

type Account struct {
    Nonce    uint64
    Balance  *big.Int
    Root     common.Hash // Merkle Patricia Tree 的根节点Hash值,默认空值。
    CodeHash []byte
}

• Nonce：如果是外部账户，nonce代表从此账户地址发送的交易序号。如果是合约账户，nonce代表此账户创建的合约序号
• Balance：此地址拥有Wei的数量, 1Ether=10^18Wei
• Root: Merkle Patricia Tree 的根节点Hash值,默认空值。
• CodeHash：此账户EVM代码的hash值。对于合约账户，就是被Hash的代码；对于外部拥有账户，c是一个空字符串的Hash值

MPT 空节点计算方式

emptyRoot = common.HexToHash("56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421")

keccak256(RLP.encode("")) ==> keccak256([0x80]) ==> "56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421"

MPT 中 hashRoot 计算

x    1    x    x    4    5    6    x    8    x    10    x    x    13    14    15    x
                    |
x    x    2    x    x    x    x    7    x    x    x     x    x    x     x     x     x

H1 = HASH( RLP(1:KV) )
H2 = HASH( RLP(4->2:KV) )
H3 = HASH( RLP(4->7:KV) )
H4 = HASH( RLP([NIL, NIL, H2, NIL, ..., H3, ...., NIL]) )
...
RootHash = HASH( RLP([NIL, H1, NIL, NIL, H4, ..., HASH(RLP(15:KV)), NIL]) )

进行hashRoot的时候，会将nibble恢复成byte进行哈希计算。其主要原因是为了节省空间存在levelDB中。其大概流程是：首先去掉结尾标识符。如果有结尾标识符，则存在第1个byte的第从左往右边第6个位(即代码的左移5个位)。如果nibble的长度是个奇数，首先在第一个byte的第5个位职位1作为标记符。然后将第一个nibble复制第一个byte的后四位。如果是偶数，则第一个byte的后4位置为0。代码如下：

func hexToCompact(hex []byte) []byte {
    terminator := byte(0)
    if hasTerm(hex) {
        terminator = 1
        hex = hex[:len(hex)-1]
    }
    buf := make([]byte, len(hex)/2+1)
    buf[0] = terminator << 5 // the flag byte
    if len(hex)&1 == 1 {
        buf[0] |= 1 << 4 // odd flag
        buf[0] |= hex[0] // first nibble is contained in the first byte
        hex = hex[1:]
    }
    decodeNibbles(hex, buf[1:])
    return buf
}

一个细节：如果 RLP 编码后的数据小于 32 byte， 则不做哈希直接返回。但是为了保住跟哈希能算，根哈希计算小于32byte也会强制计算。

levelDB 中的key对

levelDB相关

#include <iostream>
#include <sstream>
#include <string>
#include <chrono>

#include "leveldb/db.h"

using namespace std;

int main(int argc, char **argv)
{
  // Set up database connection information and open database
  leveldb::DB *db;
  leveldb::Options options;
  options.create_if_missing = true;

  leveldb::Status status = leveldb::DB::Open(options, "./testdb", &db);

  if (false == status.ok())
  {
    cerr << "Unable to open/create test database './testdb'" << endl;
    cerr << status.ToString() << endl;
    return -1;
  }

  {
    auto start = std::chrono::steady_clock::now();
    leveldb::WriteOptions writeOptions;
    for (unsigned int i = 0; i < 1000000; ++i)
    {
      ostringstream keyStream;
      keyStream << "012345678901234567890123456789" << i;

      ostringstream valueStream;
      valueStream << "0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789";

      db->Put(writeOptions, keyStream.str(), valueStream.str());
    }
    auto end = std::chrono::steady_clock::now();
    std::chrono::duration<double, std::micro> elapsed = end - start;
    cout << "write 100w :" << (double)elapsed.count() / 1000000 << "s" << endl;
  }

  {
    auto start = std::chrono::steady_clock::now();
    std::string val = "";
    for (unsigned int i = 0; i < 1000000; ++i)
    {
      ostringstream keyStream;
      keyStream << "012345678901234567890123456789" << i;
      db->Get(leveldb::ReadOptions(), keyStream.str(), &val);
    }
    auto end = std::chrono::steady_clock::now();
    std::chrono::duration<double, std::micro> elapsed = end - start;
    cout << "read 100w :" << (double)elapsed.count() / 1000000 << "s" << endl;
  }

  // Close the database
  delete db;
}

write 100w :4.30719s (100 / 4.30 == 23.2w)
read 100w :1.79004s (100 / 1.79 == 55.8w)
read 100w :1.63528s (key值不存在)

官网
fillseq      :       1.765 micros/op;   62.7 MB/s
fillsync     :     268.409 micros/op;    0.4 MB/s (10000 ops)
fillrandom   :       2.460 micros/op;   45.0 MB/s
overwrite    :       2.380 micros/op;   46.5 MB/s
1 / 2.460 == 40.6w

readrandom  : 16.677 micros/op;  (approximately 60,000 reads per second)
readseq     :  0.476 micros/op;  232.3 MB/s
readreverse :  0.724 micros/op;  152.9 MB/s
1 / 16.677 == 5.99w

depth == 20，仅仅读取出来，2 ^ 21 / 1000000 * 1.79 == 3.75s，还有RLP解码。

--dev 模式 chainId

params/config.go

    AllCliqueProtocolChanges = &ChainConfig{big.NewInt(1337), big.NewInt(0), nil, false, big.NewInt(0), common.Hash{}, big.NewInt(0), big.NewInt(0), big.NewInt(0), big.NewInt(0), big.NewInt(0), big.NewInt(0), big.NewInt(0), big.NewInt(0), big.NewInt(0), nil, nil, nil, &CliqueConfig{Period: 0, Epoch: 30000}}

开发进度

已完成的开发

• 二叉默克尔树的定义
• 二叉默克尔树插入(更新)
• 二叉默克尔树删除
• 二叉默克尔树修改
• 二叉默克尔树的哈希计算
• 二叉默克尔树的哈希节点采用mmap内存映射方式实现
  • 持久化到硬盘中
  • 从硬盘恢复到内存中
• 二叉默克尔树持久化到levelDB中
  • 持久化每次只持久化修改的部分
• 叶子节点从levelDB恢复到内存中
  • 读取
  • 解码
• 在内存中跑通一个节点，对MPT的修改只保存在内存中，没有持久化到leveldb中

  core/state/database.go 131
  func (db *cachingDB) OpenTrie(root common.Hash) (Trie, error) {
  tr, err := trie.NewSecure(root, db.db)
  //tr, err := trie.NewBinary(root, db.db, 1)
  if err != nil {
    return nil, err
  }
  return tr, nil
  }

• 将上层调用初始化MTP的代码，替换成使用修改过后的BinaryMPT。因为代码逻辑有多处根据stateRoot来初始化MPT，改为单例模式初始化BinaryMPT。
• 二叉默克尔树与状态数据库之间的交互(将MPT持久化到leveldb中)
  • 持久化地方
  • 创世区块
  • 出块：跑通一个节点，使用 --gcmode archive --cache.snapshot 0 模式将修改过后的数据能持久化到levelDB中。但是还有点小问题，RLP编解码有问题，存进去的数据有部分还无法解码(应该是节点编码有问题)。如：A7640000A056E81F171BCC55A6FF8345E692C0F86E5B48E01B996CADC001622FB5E363B421A0C5D2460186F7233C927E7DB2DCC703C0E500B653CA82273B7BFAD8045D85A470A470A470A470A470
• 调通智能合约的调用(BMPT与MPT的底层数据库共用同一个，所以在调用数据库逻辑的时候，需要区分是BMPT还是MPT)
  • 合约数据的查询

  • 合约数据的持久化

• 完善BinaryMPT单例的模式
  • 将BMPT里面实例化的以前的单例模式去掉，改为树形结构使用单例。为可以提供多颗BMPT做好准备

• 实现在内存中的历史数据查询，即实现了对纪录的修改保存。

  type DiffLeaf struct {
  Index uint32
  Leaf  binaryLeaf
  }
  
  type Alter struct {
  PreRoot   [32]byte
  CurRoot   [32]byte
  DiffLeafs []DiffLeaf
  }
  
  binaryRoot := t.binaryRoot() // 当前的最新root
  trieRoot := t.trieRoot()     // 初始化的root
  // 这是要查历史数据
  if binaryRoot != trieRoot {
      for _, alter := range t.bt.alters {
          if alter.PreRoot == trieRoot {
              for _, diffLeaf := range alter.DiffLeafs {
                  if diffLeaf.Index == uint32(leafIndex) {
                      return diffLeaf.Leaf
                  }
              }
          }
      }
      leaf = make([]binaryNode, 0, 0)
  }

• 实现将每个区块对应的修改值进行RLP编码并存到leveldb

• 完成从leveldb加载每个区块对应的修改值并进行RLP解码还原到内存中

  // f90340a05a013a87733553966400242399dee3760877fead2cd87287747155e47a854acba050fe07922f57ae3b4553201bfd7c11aca85e1541f91db8e62dca9c418dc5feaef902fbf9015102f9014df87d94b44719dc13fc46773e8cfcf79fa2f1ef2e8dcc57b866f86401a0fffffffffffffffffffffffffffffffffffffffffffffffa943935b75e584a37a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470f86594c08c699d71038eb9a2e6bb1f4139017887dc2fe8b84ef84c808853444835ec580000a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470f86594c2bcdc28760bda2315c77a3587e47c9c996c6d27b84ef84c808853444835ec580000a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470f8d201f8cff866945e17555c1ed3bb5010aa9386d56ca823a0f33d19b84ff84d068903e7327d55c1a44000a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470f865946af797299b61969e2a1b5a35c605cd7216b5d119b84ef84c80881bc16d674ec80000a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470f8d103f8cef86594cf7e747bec87dd652c9eef91645de965b481a241b84ef84c80886124fee993bc0000a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470f86594dea01d44ae5a38dcf83425605b8d587bf93ebb28b84ef84c808829a2241af62c0000a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
  // alters retrieves a alters from leveldb
  func (db *Database) resolveAlters(hash common.Hash) []Alter {
  alters := make([]Alter, 0, 0)
  root := hash
  count := 0
  for {
    count++
  
    cur := rawdb.ReadAlters(db.diskdb, root)
    if len(cur) == 0 {
      break
    }
    alter := Alter{}
  
    elems, rest, err := rlp.SplitList(cur)
    if err != nil {
    }
  
    cur = elems
    elems, rest, err = rlp.SplitString(cur)
    copy(alter.PreRoot[0:], elems)
  
    cur = rest
    elems, rest, _ = rlp.SplitString(cur)
    copy(alter.CurRoot[0:], elems)
  
    cur = rest
    elems, rest, err = rlp.SplitList(cur)
  
    cur = elems
    for {
      var diffLeaf DiffLeaf
      index := make([]byte, 0, 0)
      next := make([]byte, 0, 0)
  
      elems, rest, err = rlp.SplitList(cur)
      next = append(next, rest...)
      cur = next
  
      index, rest, err = rlp.SplitString(elems)
      diffLeaf.Index = uint32(bytesToInt(index))
  
      elems, rest, err = rlp.SplitList(rest)
  
      leaf := make([]binaryNode, 0, 0) // 如果叶子节点是空的，默认为空数组
      cur := elems
      for {
        var node binaryNode
        key := make([]byte, 0, 0)
        val := make([]byte, 0, 0)
  
        elems, rest, err = rlp.SplitList(cur)
        next := rest
        cur = rest
  
        if len(elems) > 0 {
          elems, rest, err = rlp.SplitList(elems)
          key, rest, err = rlp.SplitString(rest)
          val, rest, err = rlp.SplitString(rest)
          node.Key = key
          node.Val = val
          leaf = append(leaf, node)
        }
  
        if len(next) == 0 {
          break
        }
      }
      diffLeaf.Leaf = leaf
      alter.DiffLeafs = append(alter.DiffLeafs, diffLeaf)
  
      if len(next) == 0 {
        break
      }
    }
    alters = append(alters, alter)
    copy(root[:], alter.PreRoot[:])
  
    // 最多支持回滚10个
    if count >= 10 {
      break
    }
  }
  return alters
  }

  正在开发中

• 持久化到硬盘中的条件判断
  • 以当前未写入链上的数据大小之和为条件进行判断，比如大于10兆进行写一次。
  • 根据区块个数进行判断，比如每100个区块进行写入一次
• 对levelDB数据进行清理
  • 保留10个历史区块数据(目前按10个做，可做为一个可配参数)
  • 每出10个区块，清理内存中前10个区块的历史数据
  • 每进行一次持久化，清理上一次写入leveldb中的数据
• 区块的回滚
  • 链分叉回滚
  • 因为链挂掉或强制停止链等情况导致数据不一致的链回滚

待开发的功能

• 叶子节点每个元素分开存储(优化功能)
• 二叉默克尔树迭代器
• 二叉默克尔树的证明

开发备注

• 如果构建的时候将整个哈希节点从leveldb加载进来，是否加载最后一层然后再计算比从leveldb中加载要快。