這幾天在日本大阪正在舉辦Devcon 5。議題中有個(gè)topic吸引我的眼球：

在以太坊上，傳統(tǒng)的Merkle樹（深度為33）添加一個(gè)葉子節(jié)點(diǎn)，除了計(jì)算33次Hash函數(shù)外，還需要更新33個(gè)節(jié)點(diǎn)（也就是需要讀并且更新33個(gè)存儲空間）。而更新一個(gè)節(jié)點(diǎn)的存儲費(fèi)用是昂貴的。更新33個(gè)256bit的存儲，大約需要180w的GAS費(fèi)用。

Shrubs就提出了一種Merkle樹的變種，每次添加一個(gè)葉子節(jié)點(diǎn)，只需要O（1）次存儲更新。這種變種的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樹的原因。

1. 核心算法

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)的序號。選擇左邊節(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è)添加過程如下面動圖效果（橙色連線代表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;

}

}

}

2. 性能分析

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)，需要2^n*n次計(jì)算。Shrubs變種Merkle樹添加所有的葉子節(jié)點(diǎn)，只需要（1+2+.。.+n） = （n*（n-1））/2次計(jì)算

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樹用多個(gè)子樹的樹根來代表一個(gè)Merkle樹。每次添加一個(gè)葉子節(jié)點(diǎn)，只需要O（1）次存儲更新，平均情況下，只需要9.6w的GAS。使用Groth16算法，證明葉子節(jié)點(diǎn)在樹上，也只需要不到50w的GAS。
來源： 星想法?