Merkle tree for non-membership proof

1. 引言

Merkle tree相关前序博客有：

• Merkle tree及其在区块链等领域的应用
• Merkle tree proof【基于Merkle tree的membership proof，或existenceProof】

基于Merkle tree的non-membership proof或NonExistenceProof 相关代码实现见：

• github.com/confio/ics23

//
//NonExistenceProof takes a proof of two neighbors, one left of the desired key,
//one right of the desired key. If both proofs are valid AND they are neighbors,
//then there is no valid proof for the given key.
type NonExistenceProof struct {
	Key   []byte          `protobuf:"bytes,1,opt,name=key,proto3" json:"key,omitempty"`
	Left  *ExistenceProof `protobuf:"bytes,2,opt,name=left,proto3" json:"left,omitempty"`
	Right *ExistenceProof `protobuf:"bytes,3,opt,name=right,proto3" json:"right,omitempty"`
}

基于Merkle tree的membership proof复杂度为 O ( log ⁡ n ) O(\log n) O(logn)。 若Merkle tree未排序，则证明non-membership proof的复杂度为 O ( n ) O(n) O(n)，但是，若采用sorted Merkle tree，则可仅查找non-element相邻的2个叶子节点，并证明这2个叶子节点是邻居，即可证明non-element不再该sorted Merkle tree中。

2. Merkle tree

以对数字集 { 6 , 3 , 9 , 0 , 8 , 4 , 7 , 2 } \{6,3,9,0,8,4,7,2\} {6,3,9,0,8,4,7,2}的Merkle tree为例：

            R
        /       \
     N12          N34
    / \           / \
  N1    N2     N3     N4
 /  \   / \    / \    / \
6   3   9  0  8   4  7   2

N为Merkle tree中的节点，每个节点为其底层2个节点的拼接值哈希，有 N=hash(N_left | N_right)。R为该Merkle tree的root hash，可作为该数据集的commitment值发布。 为了证明某元素在该数据集内，仅需要公开某些哈希值。如证明0在该数据集内：

           R
       /       \
     N12           N34
    / \
  N1     N2
       / \
      9   0 

proof中仅需包含9、N1、N34即可重构出root hash R。【仅公开一个该数据集内的一个元素和相应的一个branch】

3. Sorted Merkle tree

将第2节中的数据集先排序构建的的即为Sorted Merkle tree，可用于证明某元素不在该数据集内。 仍然以对数字集 { 6 , 3 , 9 , 0 , 8 , 4 , 7 , 2 } \{6,3,9,0,8,4,7,2\} {6,3,9,0,8,4,7,2}为例，相应的Sorted Merkle tree为：

            R
        /       \
     N12          N34
    / \           / \
  N1     N2     N3    N4
 /  \   / \    / \    / \
0   2   3  4  6   7  8   9

为证明1不在该数据集内：

            R
        /       \
     N12          N34
    / \           
  N1     N2    
 /  \   
0   2   

proof中仅需包含0、2、N2、N34，由于0