這幾天在日本大阪正在舉辦Devcon 5王带。議題中有個(gè)topic吸引我的眼球：
Shrubs - A New Gas Efficient Privacy Protocol
在以太坊上留夜，傳統(tǒng)的Merkle樹（深度為33）添加一個(gè)葉子節(jié)點(diǎn)，除了計(jì)算33次Hash函數(shù)外蚕愤，還需要更新33個(gè)節(jié)點(diǎn)（也就是需要讀并且更新33個(gè)存儲(chǔ)空間）晦溪。而更新一個(gè)節(jié)點(diǎn)的存儲(chǔ)費(fèi)用是昂貴的瀑粥。更新33個(gè)256bit的存儲(chǔ)，大約需要180w的GAS費(fèi)用三圆。
Shrubs就提出了一種Merkle樹的變種狞换，每次添加一個(gè)葉子節(jié)點(diǎn)，只需要O(1)次存儲(chǔ)更新舟肉。這種變種的Merkle樹修噪，不只是用一個(gè)樹根節(jié)點(diǎn)來“代表”整棵樹。而是用一系列節(jié)點(diǎn)（個(gè)數(shù)等于深度）來”代表“整棵樹路媚，保證所有的葉子節(jié)點(diǎn)都能”索引“到這些節(jié)點(diǎn)黄琼。在變種的Merkle上，每一層選擇一個(gè)節(jié)點(diǎn)整慎。在添加葉子節(jié)點(diǎn)的時(shí)候脏款，在不破壞其他“子樹”的根的前提下，只要更新到離該葉子節(jié)點(diǎn)最近的子樹根即可裤园。
可以想象成撤师，Shrubs的變種Merkle樹，其實(shí)是由一棵棵的子樹的樹根組成拧揽。這些子樹能覆蓋所有的已經(jīng)添加的葉子節(jié)點(diǎn)剃盾。這些子樹的樹根可以代表一棵完整的Merkle樹（唯一性）。而且通過子樹的路徑證明淤袜，就能證明某個(gè)葉子節(jié)點(diǎn)在這顆完整的Merkle樹上痒谴。因?yàn)槊看沃恍枰伦訕涞臉涓哉∠郏看翁砑尤~子節(jié)點(diǎn)只需要一次節(jié)點(diǎn)數(shù)據(jù)的更新积蔚。
這些子樹的樹根，又能推導(dǎo)出整個(gè)merkle樹最右邊的path烦周。這也是库倘，Shrubs的說明中临扮，用merkle樹的最右邊path代表merkle樹的原因。
01核心算法
Shrubs的變種Merkle樹的算法原型昨天更新到Github上教翩，地址如下：
https://github.com/celo-org/shrubs
核心算法邏輯在contracts/MerkleTreeLib.sol中的insert和verify函數(shù)杆勇。
1. 插入節(jié)點(diǎn)
insert函數(shù)實(shí)現(xiàn)了葉子節(jié)點(diǎn)的插入邏輯。filled_subtrees就是每個(gè)選擇的子樹的根饱亿。insert函數(shù)的主要邏輯蚜退，就是選擇子樹，更新子樹的根彪笼。
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采用空節(jié)點(diǎn)初始化钻注。在新插入一個(gè)節(jié)點(diǎn)時(shí)，找到它最低的左節(jié)點(diǎn)作為選擇的子樹配猫，并更新樹根幅恋。current_index是每一層上節(jié)點(diǎn)的序號(hào)。選擇左邊節(jié)點(diǎn)是通過current_index%2==0實(shí)現(xiàn)泵肄。
以深度為4的Merkle樹為例捆交，添加第一個(gè)葉子節(jié)點(diǎn)后，各個(gè)子樹的樹根如下（青色節(jié)點(diǎn)是初始化的filled_subtrees節(jié)點(diǎn)腐巢，藍(lán)色是更新的節(jié)點(diǎn)）：
添加第二和三個(gè)葉子節(jié)點(diǎn)分別如下：
整個(gè)添加過程如下面動(dòng)圖效果（橙色連線代表hash計(jì)算）：
1.2 驗(yàn)證節(jié)點(diǎn)
verify函數(shù)是驗(yàn)證某個(gè)葉子節(jié)點(diǎn)在Merkle樹上的示例品追。只要能給定一條路徑，能計(jì)算出一個(gè)子樹根即可冯丙。
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;
}
}
}
02性能分析
2.1 數(shù)據(jù)更新
Shrubs變種Merkle樹肉瓦，每次添加節(jié)點(diǎn)，只需要更新一個(gè)子樹的樹根胃惜。從數(shù)據(jù)更新角度泞莉，算法復(fù)雜度O(1)。
2.2 hash計(jì)算
從hash計(jì)算的角度船殉，在添加左節(jié)點(diǎn)時(shí)戒财，無需hash計(jì)算。在添加右節(jié)點(diǎn)時(shí)捺弦，hash計(jì)算和選擇的子樹深度相等。越靠右的節(jié)點(diǎn)孝扛，子樹選擇也高列吼，hash計(jì)算也越多。即使這樣苦始，也比傳統(tǒng)的Merkle樹計(jì)算量小寞钥。
假設(shè)Merkle樹的樹高是n，則傳統(tǒng)Merkle樹添加所有的葉子節(jié)點(diǎn)陌选，需要2n*n次計(jì)算理郑。Shrubs變種Merkle樹添加所有的葉子節(jié)點(diǎn)蹄溉，只需要(1+2+4+...+2(n-1)) = (2^n)-1次計(jì)算
03測(cè)試結(jié)果
在Devcon5上，Shrubs公開了變種Merkle樹的測(cè)試結(jié)果您炉。葉子插入的gas消耗柒爵，平均情況下，9.6w赚爵。
圖中棉胀，Shrubs最壞情況下的GAS消耗應(yīng)該不是168w，應(yīng)該在40w左右冀膝。
如果使用Groth16零知識(shí)證明的話唁奢，大約需要不到50w的GAS（EIP1008情況下）。
值得一提的是窝剖，使用Groth16零知識(shí)證明麻掸，需要將所有的子樹的樹根作為public input。
總結(jié)：
為了解決以太坊智能合約中Merkle樹更新存儲(chǔ)開銷較大的問題赐纱，Shrubs提出了一種新型的Merkle樹變種脊奋。這種變種的Merkle樹用多個(gè)子樹的樹根來代表一個(gè)Merkle樹。每次添加一個(gè)葉子節(jié)點(diǎn)千所，只需要O(1)次存儲(chǔ)更新狂魔，平均情況下，只需要9.6w的GAS淫痰。使用Groth16算法最楷，證明葉子節(jié)點(diǎn)在樹上，也只需要不到50w的GAS待错。
附上籽孙，好朋友從現(xiàn)場(chǎng)發(fā)回的其他照片，也分享給小伙伴們（圖片中有一些地方有錯(cuò)誤火俄，發(fā)現(xiàn)錯(cuò)誤的小伙伴留言犯建，有獎(jiǎng)勵(lì)～）：
