tendermint默克尔树

发表于   |   分类于   |     |   阅读次数   |   浏览 次

默克尔树概述

在ABCI应用响应Commit请求消息时，需要计算并返回当前状态的哈希，以便Tendermint 将其打包到下一个区块头里（app_hash字段）。

但是，如果我们还按原来的方法计算一个总体哈希，例如：hash: = tmhash.Sum(state)， 就存在一个问题 —— 当查询某个特定账户的状态数据时，如何验证该状态是未被篡改的？

显然，单独返回整个状态的哈希是不够的，但是我们也不可能将整个账户表提供给 客户端以便其重算哈希进行验证，因为其中包含了其他用户的账户信息。

这就是默克尔树（Merkle Tree）的用武之地：不需要提供完整的数据（例如整个账户表）， 就可以验证某个数据（例如账户A的状态）是否属于该数据集。

在默克尔树中，叶节点对应于各状态的哈希值，根节点则对应于整个状态的哈希， 中间各层的节点则分别由前一层节点两两结对后计算哈希得到。

例如，下图给出了4个账户状态时的默克尔树的构成：

merkle-tree

基于默克尔树的生成过程，我们只需要这个树的一部分节点，就可以验证某个状态（例如账户A 的状态）与整体哈希（Hash(ABCD)）的对应关系，这部分节点就被称为默克尔证据/Merkle Proot。 例如上图中，对于账户A的状态而言，Hash(B)和Hash(CD)就是其证据 —— 因为利用账户A本身的数据， 以及证据节点，就可以重算出根节点，从而确认指定账户状态与给定状态哈希的对应关系。

计算默克尔哈希

在tendermint中内置了默克尔树的一个简单实现，可以计算有序集合（切片）和无序集合（映射表） 的默克尔树根哈希：

merkle-tree

Hasher接口

使用crypto/merkle包计算数据集合的默克尔哈希，要求集合中的成员实现Hasher接口。例如， 我们使用下面的结构来满足这一需求：

1
2
3
4
5
6
7
type sh struct{
  value string
}

func (h sh) Hash() []byte {
  return tmhash.Sum([]byte(h.value))
}

现在，我们可以根据集合是有序还是无序，来分别计算其默克尔哈希了。

有序集合的哈希计算

有序集合（例如：切片）中各成员有确定性的先后顺序，因此可以直接使用SimpleHashFromHashers() 方法进行计算。例如：

1
2
3
data := []merkle.Hasher{ &sh{"one"},&sh{"two"},&sh{"three"},&sh{"four"} }
hash := merkle.SimpleHashFromHashers(data)
fmt.Printf("root hash => %x\n",hash)

无序集合的哈希计算

无序集合（例如：映射表）的各成员没有确定性的先后顺序，因此需要首先进行确定排序，重组为有序 集合后才能使用SimpleHashFromHashers()方法计算该集合的默克尔哈希。对于键类型为string、值类型 为Hasher的映射表而言，可以直接使用SimpleHashFromMap()方法。例如：

1
2
3
4
5
6
7
data := map[string]merkle.Hasher{
  "tom":&sh{"actor"},
  "mary":&sh{"teacher"},
  "linda":&sh{"scientist"},
  "luke":&sh{"fisher"}}
hash := merkle.SimpleHashFromMap(data)
fmt.Printf("root hash => %x\n",hash)

状态的默克尔证据

在使用默克尔树时，如果需要验证某个数据是否属于一个特定的集合，除了待验证的数据自身， 还需要以下数据：

数据集合的根哈希：表征特定的数据集合
数据的默克尔证据：配合待验证数据重算根哈希，以便于给定的根哈希比较
tendermint的crypto/merkle包提供了简单的方法返回集合中每个成员对应的默克尔 证据以及集合的根哈希：

merkle-tree
数据聚合中每个成员对应的默克尔证据就是一个SimpleProof实例，因此可以直接调用 其Verify()方法进行验证。

同样，获取数据成员的默克尔证据也分为有序集合与无序集合两种情况。

有序集合成员的默克尔证据

使用SimpleProofsFromHashers()方法获取有序集合（例如：切片）中各成员的默克尔证据， 成员必须实现Hasher接口，该方法返回两个值：根哈希以及默克尔证据数组。

还是利用前一节的sh类型，下面的代码展示了如何获取切片中各成员的默克尔证据：

1
2
3
data := []sh{sh("one"),sh("two"),sh("three"),sh("four")}
root,proofs := merkle.SimpleProofsFromHashers(data)
fmt.Printf("proof for one => %+v\n",proofs[0])

在返回结果中的默克尔证据数组，其成员顺序与输入数据一致。

一旦获取了某个数据的默克尔证据、结合数据集合的根哈希，就可以验证这个数据是否属于 给定的根哈希对应的数据集合了。例如：

1
2
3
4
5
6
valid := proofs[0].Verify(
    0,              // 要验证的数据在集合中的序号
    4,              // 集合成员总数
    data[0].Hash(), // 要验证的数据的哈希
    root           // 集合的根哈希)
fmt.Printf("data[0] is valid? => %t\n",valid)

无序集合成员的默克尔证据

同样，没有确定性成员顺序的映射表，需要使用SimpleProofsFromMap()方法计算每个 成员的默克尔证据，其返回结果是三个值：根哈希、成员默克尔证据映射表和排序后的 成员键。例如：

1
2
3
4
5
6
7
data := map[string]sh{
  "tom":sh("actor"),
  "mary":sh("teacher"),
  "linda":sh("scientist"),
  "luke":sh("fisher")}
root,proofs,keys := merkle.SimpleProofsFromMap(data)
fmt.Printf("proof for tom => %+v\n",proofs["tom"])

由于在计算映射表的默克尔证据时首先将无序的键值对转化为了KVPair结构并 进行排序，因此其成员时，也需要首先将其转换为KVPair类型，而不能仅使用键值对 中的值部分：

kvpair := merkle.KVPair{Key:[]byte("tom"),Value: data["tom"].Hash()}
然后根据该成员在排序后的顺序号（keys中的位置），进行验证，例如：

1
2
3
4
5
6
valid := proofs[key].Verify(
    3,            // 要验证的数据键在keys中的序号
    4,              // 集合成员总数
    kvpair.Hash(), // 要验证的数据的哈希
    root           // 集合的根哈希)
fmt.Printf("data["tom"] is valid? => %t\n",valid)

升级代币状态机

基于默克尔树，我们可以升级代币状态机，在hash.go代码中实现与默克尔计算相关 的三个方法：

merkle-hash-support

首先扩展int类型，实现Hasher接口：

1
2
3
4
5
6
type Balance int

func (b Balance) Hasher() []byte {
  v,_ := codec.MarshalBinary(b)
  return tmhash.Sum(v)
}

stateToHasherMap()方法将应用的状态集合转换为Hasher映射表，以便进行默克尔计算：

1
2
3
4
5
6
7
8
func (app *TokenApp) stateToHasherMap() map[string]merkle.Hasher {
  hashers := map[string]merkle.Hasher{}
  for addr,val := range app.Accounts { 
    balance := Balance(val)
    hashers[addr] = &balance
  }
  return hashers
}

getRootHash()方法计算应用状态的默克尔哈希：

1
2
3
4
func (app *TokenApp) getRootHash() []byte {
  hashers := app.stateToHasherMap()
  return merkle.SimpleHashFromMap(hashers)  
}

getProofBytes()方法获取指定地址状态的默克尔证据：

1
2
3
4
5
6
7
func (app *TokenApp) getProofBytes(addr string) []byte {
  hashers := app.stateToHasherMap()
  _,proofs,_ := merkle.SimpleProofsFromMap(hashers)
  bz,err := codec.MarshalBinary(proofs[addr])
  if err != nil  { return  []byte{} }
  return bz
}

当提交状态修改时，我们可以利用这些方法向tendermint返回根哈希：

1
2
3
4
func (app *TokenApp) Commit() (rsp types.ResponseCommit){
  rsp.Data = app.getRootHash()
  return
}

当查询状态时，也可以利用这些方法返回状态的证据：

1
2
3
4
5
6
7
func (app *TokenApp) Query(req types.RequestQuery) (rsp types.ResponseQuery) {
  addr := crypto.Address(req.Data)
  rsp.Key = req.Data
  rsp.Value,_ = codec.MarshalBinary(app.Accounts[addr.String()])
  rsp.Proof = app.getProofBytes(addr.String())
  return
}

坚持原创技术分享，您的支持将鼓励我继续创作！