以太坊智能合约中Merkle树的算法原型解析
这几天在日本大阪正在举办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。
来源： 星想法
使用前馈电容器降低输出噪声
基于边缘路由器ER805的星汉云管理网络解决方案
小米推出“小米有品·家” 加入了很多智能家居设备
场效应管厂商：深圳市晶导电子有限公司简介
研究发现：Win10 快捷方式一短字符串会损坏任何硬盘
以太坊智能合约中Merkle树的算法原型解析
securecrt和xshell的区别
华为云服务治理—隔离仓的作用
LED回收的重要性和必要性
20多年发展，物联网将是下一个风口！
一加8 Pro保护壳曝光 后置竖排三摄且未保留3.5mm耳机孔
麒麟960与高通骁龙821之间有着怎样的差距？
新能源汽车电源之锂硫电池利弊谈
如何使用Arduino Processing和Wekinator按钮更改声音播放器的音高
内置T6963C液晶显示模块在MSP430中的控制技术
联发科获多家手机 / 平板 / 笔记本厂商 Wi-Fi 7订单
2022年有什么蓝牙耳机？2022年最好的蓝牙耳机排行榜
曼富图越野者登山套装评测 最适合爱好登山的摄影用户使用
LED灯盘的实际电路怎么看
高速PCB设计中详细布局的六大步骤解析
在以太坊上，传统的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。
来源： 星想法
使用前馈电容器降低输出噪声
基于边缘路由器ER805的星汉云管理网络解决方案
小米推出“小米有品·家” 加入了很多智能家居设备
场效应管厂商：深圳市晶导电子有限公司简介
研究发现：Win10 快捷方式一短字符串会损坏任何硬盘
以太坊智能合约中Merkle树的算法原型解析
securecrt和xshell的区别
华为云服务治理—隔离仓的作用
LED回收的重要性和必要性
20多年发展，物联网将是下一个风口！
一加8 Pro保护壳曝光 后置竖排三摄且未保留3.5mm耳机孔
麒麟960与高通骁龙821之间有着怎样的差距？
新能源汽车电源之锂硫电池利弊谈
如何使用Arduino Processing和Wekinator按钮更改声音播放器的音高
内置T6963C液晶显示模块在MSP430中的控制技术
联发科获多家手机 / 平板 / 笔记本厂商 Wi-Fi 7订单
2022年有什么蓝牙耳机？2022年最好的蓝牙耳机排行榜
曼富图越野者登山套装评测 最适合爱好登山的摄影用户使用
LED灯盘的实际电路怎么看
高速PCB设计中详细布局的六大步骤解析