以太坊智能合約中Merkle樹的算法原型解析
這幾天在日本大阪正在舉辦Devcon 5。議題中有個topic吸引我的眼球:
在以太坊上,傳統(tǒng)的Merkle樹(深度為33)添加一個葉子節(jié)點,除了計算33次Hash函數(shù)外,還需要更新33個節(jié)點(也就是需要讀并且更新33個存儲空間)。而更新一個節(jié)點的存儲費用是昂貴的。更新33個256bit的存儲,大約需要180w的GAS費用。
Shrubs就提出了一種Merkle樹的變種,每次添加一個葉子節(jié)點,只需要O(1)次存儲更新。這種變種的Merkle樹,不只是用一個樹根節(jié)點來“代表”整棵樹。而是用一系列節(jié)點(個數(shù)等于深度)來”代表“整棵樹,保證所有的葉子節(jié)點都能”索引“到這些節(jié)點。在變種的Merkle上,每一層選擇一個節(jié)點。在添加葉子節(jié)點的時候,在不破壞其他“子樹”的根的前提下,只要更新到離該葉子節(jié)點最近的子樹根即可。
可以想象成,Shrubs的變種Merkle樹,其實是由一棵棵的子樹的樹根組成。這些子樹能覆蓋所有的已經(jīng)添加的葉子節(jié)點。這些子樹的樹根可以代表一棵完整的Merkle樹(唯一性)。而且通過子樹的路徑證明,就能證明某個葉子節(jié)點在這顆完整的Merkle樹上。因為每次只需要更新子樹的樹根,所以,每次添加葉子節(jié)點只需要一次節(jié)點數(shù)據(jù)的更新。
這些子樹的樹根,又能推導(dǎo)出整個merkle樹最右邊的path。這也是,Shrubs的說明中,用merkle樹的最右邊path代表merkle樹的原因。
1. 核心算法
Shrubs的變種Merkle樹的算法原型昨天更新到Github上,地址如:https://github.com/celo-org/shrubs
核心算法邏輯在contracts/MerkleTreeLib.sol中的insert和verify函數(shù)。
1. 插入節(jié)點
insert函數(shù)實現(xiàn)了葉子節(jié)點的插入邏輯。filled_subtrees就是每個選擇的子樹的根。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é)點初始化。在新插入一個節(jié)點時,找到它最低的左節(jié)點作為選擇的子樹,并更新樹根。current_index是每一層上節(jié)點的序號。選擇左邊節(jié)點是通過current_index%2==0實現(xiàn)。
以深度為4的Merkle樹為例,添加第一個葉子節(jié)點后,各個子樹的樹根如下(青色節(jié)點是初始化的filled_subtrees節(jié)點,藍色是更新的節(jié)點):
添加第二和三個葉子節(jié)點分別如下:
整個添加過程如下面動圖效果(橙色連線代表hash計算):
1.2 驗證節(jié)點
verify函數(shù)是驗證某個葉子節(jié)點在Merkle樹上的示例。只要能給定一條路徑,能計算出一個子樹根即可。
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;
}
}
}
2. 性能分析
2.1 數(shù)據(jù)更新
Shrubs變種Merkle樹,每次添加節(jié)點,只需要更新一個子樹的樹根。從數(shù)據(jù)更新角度,算法復(fù)雜度O(1)。
2.2 hash計算
從hash計算的角度,在添加左節(jié)點時,無需hash計算。在添加右節(jié)點時,hash計算和選擇的子樹深度相等。越靠右的節(jié)點,子樹選擇也高,hash計算也越多。即使這樣,也比傳統(tǒng)的Merkle樹計算量小。
假設(shè)Merkle樹的樹高是n,則傳統(tǒng)Merkle樹添加所有的葉子節(jié)點,需要2^n*n次計算。Shrubs變種Merkle樹添加所有的葉子節(jié)點,只需要(1+2+.。.+n) = (n*(n-1))/2次計算
3. 測試結(jié)果
在Devcon5上,Shrubs公開了變種Merkle樹的測試結(jié)果。葉子插入的gas消耗,平均情況下,9.6w。
圖中,Shrubs最壞情況下的GAS消耗應(yīng)該不是168w,應(yīng)該在40w左右。
如果使用Groth16零知識證明的話,大約需要不到50w的GAS(EIP1008情況下)。
值得一提的是,使用Groth16零知識證明,需要將所有的子樹的樹根作為public input。
總結(jié):
為了解決以太坊智能合約中Merkle樹更新存儲開銷較大的問題,Shrubs提出了一種新型的Merkle樹變種。這種變種的Merkle樹用多個子樹的樹根來代表一個Merkle樹。每次添加一個葉子節(jié)點,只需要O(1)次存儲更新,平均情況下,只需要9.6w的GAS。使用Groth16算法,證明葉子節(jié)點在樹上,也只需要不到50w的GAS。
來源: 星想法?