Merkle tree proof

1. 引言

前序博客有：

• Merkle tree及其在区块链等领域的应用

推荐 直观形象展示Merkle tree的网站。

Merkle proof又名Merkle path，为重新计算merkle root所需的最小节点数。 如上图，为了证明node2在root hash为65C7C87E2731AE97D0BE89EA3299A544FD28DE6A的Merkle tree中，仅需提供Node 1，Node 34和Node 567，即可生成root Node 1234567。

Merkle tree proof相关代码实现有：

• https://github.com/iden3/iden3js（JavaScript）
• https://github.com/weijiekoh/semaphore-merkle-tree（TypeScript）
• https://github.com/appliedzkp/incrementalquintree（TypeScript）
• https://github.com/filecoin-project/merkletree（Rust）
• https://github.com/sitano/merkle_light（Rust）
• https://github.com/0xProject/OpenZKP/tree/master/crypto/merkle-tree （Rust）
• https://github.com/ing-bank/zkrp（Go）
• https://github.com/zcash/librustzcash/blob/master/zcash_primitives/src/merkle_tree.rs （Rust）
• https://github.com/wealdtech/go-merkletree/（Go）
• https://github.com/mit-dci/utreexo（Go），详细参看博客 Utreexo：比特币UTXO merkle tree proof以节约节点存储空间。
• https://github.com/aszepieniec/stark-anatomy/blob/master/code/merkle.py（Python）

2. stark-anatomy中merkle proof解析

针对的代码为：

• https://github.com/aszepieniec/stark-anatomy/blob/master/code/merkle.py（Python）

详细的merkle proof测试用例见test_merkle()：【运行指定测试文件并显示打印日志pytest test_merkle.py -s。运行指定测试用例并显示打印日志pytest test_merkle.py::test_merkle -s。】 1）构建具有64个leaf的merkle tree：

	n = 64
    leafs = [urandom(int(urandom(1)[0])) for i in range(n)]
    root = Merkle.commit_(leafs)

	H = blake2b

    def commit_( leafs ):
        assert(len(leafs) & (len(leafs)-1) == 0), "length must be power of two"
        if len(leafs) == 1:
            return leafs[0]
        else:
            # 对左右leaf未做hash运算，直接拼接再hash。递归调用。
            return Merkle.H(Merkle.commit_(leafs[:len(leafs)//2]) + Merkle.commit_(leafs[len(leafs)//2:])).digest()

	def commit( data_array ):
		# 对最底层的data分别进行hash运算，生成的为leafs。
        return Merkle.commit_([Merkle.H(bytes(da)).digest() for da in data_array])

2）Open第 i i i个leaf的path：

	def open_( index, leafs ):
        assert(len(leafs) & (len(leafs)-1) == 0), "length must be power of two"
        assert(0