0%

《7天以太坊源码解读》 — 7、MPT树初探

在介绍 MPT树 之前,先介绍一下 Merkle树

>>> Merkle树

比特币中用到了 Merkle树,记录了一个块中所有的交易。Merkle树的根节点的值保存在每个区块的区块头中,可以通过区块头中的这个值来确定交易数据的完整性。

具体算法文字说不清楚,可以参考代码 https://github.com/pefish/go-blkchain-merkle-tree.git

>>> SPV节点利用Merkle树验证交易的真实性

因为 Merkle树 的特点,SPV节点可以不需要下载所有区块链数据,仅仅同步所有区块头来验证给定交易的真实性(比特币中交易达到6个确认即可表示这笔交易真是有效)

SPV节点是如何验证的:

  1. SPV节点自身会设置一个布隆过滤器,来接受指定地址的相关交易
  2. 收到交易后,需要去验证交易是否真实有效。向全节点发送 获取这笔交易的merkle区块信息 的请求
  3. 全节点收到请求后,向自身区块链数据库查询这笔交易对应的区块,然后根据区块数据得到一颗 Merkle树,根据 Merkle树 得到这个交易的验证路径。把验证路径以及交易所在的区块高度返回给SPV节点
  4. SPV收到验证路径后,根据它算出Merkle树的根节点hash,然后用算出来的hash跟自己同步到的hash对比,如果相等,则表示交易处于块当中
  5. 验证块是否达到了6个确认数

如果第4、5步都验证成功的话,说明这笔交易真实有效

这里可能有人有疑问:全节点收到请求后,全节点自己验证然后返回验证结果给SPV不就好了吗?

这里涉及到信任问题,全节点应当是不受信任的。那通过SPV节点自己计算就可以解决信任问题吗?答案是的。根据 Merkle树 的特性,全节点是没有办法通过构造验证路径,来达到根hash相等的目的 的。

>>> MPT树

以太坊中的trie包实现了Merkle Patricia Tries,简称MPT

MPT实际上包含了三种数据结构,分别是Trie树, Patricia Trie(前缀树),以及上面讲到的Merkle树。是这三种树的结合体

以太坊中每个区块头中都有3个MPT树的根hash,stateRoot(状态树根)、transactionsRoot(交易树根)、receiptsRoot(收据树根)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
type Header struct {
ParentHash common.Hash `json:"parentHash" gencodec:"required"`
UncleHash common.Hash `json:"sha3Uncles" gencodec:"required"`
Coinbase common.Address `json:"miner" gencodec:"required"`
Root common.Hash `json:"stateRoot" gencodec:"required"`
TxHash common.Hash `json:"transactionsRoot" gencodec:"required"`
ReceiptHash common.Hash `json:"receiptsRoot" gencodec:"required"`
Bloom Bloom `json:"logsBloom" gencodec:"required"`
Difficulty *big.Int `json:"difficulty" gencodec:"required"`
Number *big.Int `json:"number" gencodec:"required"`
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 common.Hash `json:"mixHash"`
Nonce BlockNonce `json:"nonce"`
}

相关代码的入口是在 trie/trie.go 中

下面是新建树的函数,初始化Trie结构,没什么好讲的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func New(root common.Hash, db *Database) (*Trie, error) {
if db == nil {
panic("trie.New called without a database")
}
trie := &Trie{
db: db,
}
if root != (common.Hash{}) && root != emptyRoot {
rootnode, err := trie.resolveHash(root[:], nil)
if err != nil {
return nil, err
}
trie.root = rootnode
}
return trie, nil
}

MPT中有下面几种节点

1
2
3
4
5
6
7
8
9
10
11
12
13
type (
fullNode struct { // 分支节点
Children [17]node // Actual trie node data to encode/decode (needs custom encoder)
flags nodeFlag
}
shortNode struct { // 扩展节点
Key []byte
Val node
flags nodeFlag
}
hashNode []byte // hash节点,只存hash,hash对应节点,对应关系存放在数据库中。例如根节点
valueNode []byte // 值节点,只存值。例如所有叶子节点
)

MPT的结构大致如下:
MPT结构

下面分析 通过当前节点、key以及pos获取节点 的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func (t *Trie) tryGet(origNode node, key []byte, pos int) (value []byte, newnode node, didResolve bool, err error) {
switch n := (origNode).(type) {
case nil:
return nil, nil, false, nil
case valueNode: // 值节点
return n, n, false, nil
case *shortNode: // 扩展节点
if len(key)-pos < len(n.Key) || !bytes.Equal(n.Key, key[pos:pos+len(n.Key)]) {
// key not found in trie
return nil, n, false, nil
}
value, newnode, didResolve, err = t.tryGet(n.Val, key, pos+len(n.Key)) // pos加上key的长度,找寻val指向的节点
if err == nil && didResolve {
n = n.copy()
n.Val = newnode
}
return value, n, didResolve, err
case *fullNode: // 分支节点
value, newnode, didResolve, err = t.tryGet(n.Children[key[pos]], key, pos+1) // pos加上1,找寻pos对应的节点
if err == nil && didResolve {
n = n.copy()
n.Children[key[pos]] = newnode
}
return value, n, didResolve, err
case hashNode: // hash节点
child, err := t.resolveHash(n, key[:pos]) // 通过hash找到对应的子节点
if err != nil {
return nil, n, true, err
}
value, newnode, _, err := t.tryGet(child, key, pos)
return value, newnode, true, err
default:
panic(fmt.Sprintf("%T: invalid node: %v", origNode, origNode))
}
}

从上面代码也可以基本推断出 MPT的数据结构,如果想深入探索其结构,可以深入研究其代码,这里只是做了个导读

文章仅供参考,若有错误,还望不吝指正 !!!




微信关注我,及时接收最新技术文章