0%

一种新型的Merkle树

介绍

在Devcon05会议上,其中一个分享Shrubs - A New Gas Efficient Privacy Protocol介绍了一种新的Merkle树。

传统的Merkle数在插入节点时每一层要计算一次Hash并更新相应节点,一个N层的Merkle树需要计算N次Hash,更新N个节点,在以太坊上N=33,大约需要180W gas. 而这种新Merkle树在插入节点时没必须更新全部节点直到根节点,最坏的情况才计算N次Hash,每次只需要更新一个节点。

这种新的Merk树的状态不是由根Hash决定的,而是由一系列子树的树根决定的,也就是说这些子树的跟代表了一根完整的Merkle树。证明某个叶子节点在这棵Merkle树上,只需要子树的Merkle Path证明即可,不需要完整到Merkle树根的Path证明。这些子树的树根,又能推导出整个merkle树最右边的path,所以可以用merkle树的最右边path代表merkle树的原因。

算法

新Merkle树的算法原型在Github. 核心的算法是节点插入和验证。

插入节点

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
function insert(uint256 leaf) internal {
uint32 leaf_index = next_index;
uint32 current_index = next_index;
next_index += 1;

uint256 current_level_hash = leaf;
uint256 left;
uint256 right;

bool all_were_right = true;
for (uint8 i = 0; i < levels; i++) {
if (current_index % 2 == 0) {
left = current_level_hash;
right = zeros[i];
filled_subtrees[i] = current_level_hash;
break;
} else {
left = filled_subtrees[i];
right = current_level_hash;
}
current_level_hash = HashLeftRight(left, right);
current_index /= 2;
}
tree_leaves.push(leaf);
}

filled_subtrees采用空节点初始化。在新插入一个节点时,找到它最低的左节点作为选择的子树,并更新树根。current_index是每一层上节点的序号。选择左边节点是通过current_index%2==0实现。

以深度为4的Merkle树为例,添加第一个叶子节点后,各个子树的树根如下(青色节点是初始化的filled_subtrees节点,蓝色是更新的节点):

添加第二和三个叶子节点分别如下:

整个添加过程如下面动图效果(橙色连线代表hash计算):

avatar)

可以发现在添加左子节点时,不需要进行Hash计算,在添加右子节点时,越往右越多。N层的Merkle树,添加全部叶子节点时,需要计算的Hash次数为0+1+0+2+0+3+..+0+N=N(N+1)/2.

传统的Merkle树插入全部叶子节点时需要n*2^n次Hash计算。

验证节点

给定待验证叶子节点和Merkle Path,如果能计算得到某个子树根,说明该节点在Merkle树上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function verify(uint256 leaf, uint256[] memory path, uint32 leaf_index) internal {
uint32 current_index = leaf_index;
uint256 current_level_hash = leaf;
uint256 left;
uint256 right;
for (uint8 i = 0; i < levels; i++) {
if (mode == 0 && filled_subtrees[i] == current_level_hash) {
emit LeafVerified(leaf, leaf_index, i, true);
return;
}
if (current_index % 2 == 0) {
left = current_level_hash;
right = path[i];
} else {
left = path[i];
right = current_level_hash;
}
current_level_hash = HashLeftRight(left, right);
current_index /= 2;
}
}
}

本文主要参考零知识证明 - 一种新型的Merkle树(Shrubs)这篇公众号文章,这个公众号干货还是很多的。