当前位置:首页 > 物联网 > 区块链
[导读] 这几天在日本大阪正在举办Devcon 5。议题中有个topic吸引我的眼球: 在以太坊上,传统的Merkle树(深度为33)添加一个叶子节点,除了计算33次Hash函数外,还需

这几天在日本大阪正在举办Devcon 5。议题中有个topic吸引我的眼球:

在以太坊上,传统的Merkle树(深度为33)添加一个叶子节点,除了计算33次Hash函数外,还需要更新33个节点(也就是需要读并且更新33个存储空间)。而更新一个节点的存储费用是昂贵的。更新33个256bit的存储,大约需要180w的GAS费用。

Shrubs就提出了一种Merkle树的变种,每次添加一个叶子节点,只需要O(1)次存储更新。这种变种的Merkle树,不只是用一个树根节点来“代表”整棵树。而是用一系列节点(个数等于深度)来”代表“整棵树,保证所有的叶子节点都能”索引“到这些节点。在变种的Merkle上,每一层选择一个节点。在添加叶子节点的时候,在不破坏其他“子树”的根的前提下,只要更新到离该叶子节点最近的子树根即可。

可以想象成,Shrubs的变种Merkle树,其实是由一棵棵的子树的树根组成。这些子树能覆盖所有的已经添加的叶子节点。这些子树的树根可以代表一棵完整的Merkle树(唯一性)。而且通过子树的路径证明,就能证明某个叶子节点在这颗完整的Merkle树上。因为每次只需要更新子树的树根,所以,每次添加叶子节点只需要一次节点数据的更新。

这些子树的树根,又能推导出整个merkle树最右边的path。这也是,Shrubs的说明中,用merkle树的最右边path代表merkle树的原因。

1. 核心算法

Shrubs的变种Merkle树的算法原型昨天更新到Github上,地址如:https://github.com/celo-org/shrubs

核心算法逻辑在contracts/MerkleTreeLib.sol中的insert和verify函数。

1. 插入节点

insert函数实现了叶子节点的插入逻辑。filled_subtrees就是每个选择的子树的根。insert函数的主要逻辑,就是选择子树,更新子树的根。

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计算):

1.2 验证节点

verify函数是验证某个叶子节点在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 数据更新

Shrubs变种Merkle树,每次添加节点,只需要更新一个子树的树根。从数据更新角度,算法复杂度O(1)。

2.2 hash计算

从hash计算的角度,在添加左节点时,无需hash计算。在添加右节点时,hash计算和选择的子树深度相等。越靠右的节点,子树选择也高,hash计算也越多。即使这样,也比传统的Merkle树计算量小。

假设Merkle树的树高是n,则传统Merkle树添加所有的叶子节点,需要2^n*n次计算。Shrubs变种Merkle树添加所有的叶子节点,只需要(1+2+.。.+n) = (n*(n-1))/2次计算

3. 测试结果

在Devcon5上,Shrubs公开了变种Merkle树的测试结果。叶子插入的gas消耗,平均情况下,9.6w。

图中,Shrubs最坏情况下的GAS消耗应该不是168w,应该在40w左右。

如果使用Groth16零知识证明的话,大约需要不到50w的GAS(EIP1008情况下)。

值得一提的是,使用Groth16零知识证明,需要将所有的子树的树根作为public input。

总结:

为了解决以太坊智能合约中Merkle树更新存储开销较大的问题,Shrubs提出了一种新型的Merkle树变种。这种变种的Merkle树用多个子树的树根来代表一个Merkle树。每次添加一个叶子节点,只需要O(1)次存储更新,平均情况下,只需要9.6w的GAS。使用Groth16算法,证明叶子节点在树上,也只需要不到50w的GAS。
来源: 星想法 

本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

9月2日消息,不造车的华为或将催生出更大的独角兽公司,随着阿维塔和赛力斯的入局,华为引望愈发显得引人瞩目。

关键字: 阿维塔 塞力斯 华为

加利福尼亚州圣克拉拉县2024年8月30日 /美通社/ -- 数字化转型技术解决方案公司Trianz今天宣布,该公司与Amazon Web Services (AWS)签订了...

关键字: AWS AN BSP 数字化

伦敦2024年8月29日 /美通社/ -- 英国汽车技术公司SODA.Auto推出其旗舰产品SODA V,这是全球首款涵盖汽车工程师从创意到认证的所有需求的工具,可用于创建软件定义汽车。 SODA V工具的开发耗时1.5...

关键字: 汽车 人工智能 智能驱动 BSP

北京2024年8月28日 /美通社/ -- 越来越多用户希望企业业务能7×24不间断运行,同时企业却面临越来越多业务中断的风险,如企业系统复杂性的增加,频繁的功能更新和发布等。如何确保业务连续性,提升韧性,成...

关键字: 亚马逊 解密 控制平面 BSP

8月30日消息,据媒体报道,腾讯和网易近期正在缩减他们对日本游戏市场的投资。

关键字: 腾讯 编码器 CPU

8月28日消息,今天上午,2024中国国际大数据产业博览会开幕式在贵阳举行,华为董事、质量流程IT总裁陶景文发表了演讲。

关键字: 华为 12nm EDA 半导体

8月28日消息,在2024中国国际大数据产业博览会上,华为常务董事、华为云CEO张平安发表演讲称,数字世界的话语权最终是由生态的繁荣决定的。

关键字: 华为 12nm 手机 卫星通信

要点: 有效应对环境变化,经营业绩稳中有升 落实提质增效举措,毛利润率延续升势 战略布局成效显著,战新业务引领增长 以科技创新为引领,提升企业核心竞争力 坚持高质量发展策略,塑强核心竞争优势...

关键字: 通信 BSP 电信运营商 数字经济

北京2024年8月27日 /美通社/ -- 8月21日,由中央广播电视总台与中国电影电视技术学会联合牵头组建的NVI技术创新联盟在BIRTV2024超高清全产业链发展研讨会上宣布正式成立。 活动现场 NVI技术创新联...

关键字: VI 传输协议 音频 BSP

北京2024年8月27日 /美通社/ -- 在8月23日举办的2024年长三角生态绿色一体化发展示范区联合招商会上,软通动力信息技术(集团)股份有限公司(以下简称"软通动力")与长三角投资(上海)有限...

关键字: BSP 信息技术
关闭
关闭