×
  • 澳门新莆京娱乐网站
  • 问卷调查
  • 问卷调查系统
  • 区块链
  • 大数据
  • 数据中心
  • 创建问卷
问卷调查系统工具软件推荐
区块链

一种新型的Merkle树(Shrubs)

                 right = zeros[i];

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


         uint256 right;


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


         uint32 leaf_index = next_index;

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

             current_index /= 2;

3. 测试功效


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


         if (mode == 0 && filled_subtrees[i] == current_level_hash) {


         for (uint8 i = 0; i < levels; i++) {

2.1 数据更新

       }


总结:


以深度为4的Merkle树为例,添加第一个叶子节点后,各个子树的树根如下(青色节点是初始化的filled_subtrees节点,蓝色是更新的节点):

添加第二和三个叶子节点别离如下:

function verify(uint256 leaf, uint256[] memory path, uint32 leaf_index) internal {


         current_index /= 2;


           right = current_level_hash;


       uint32 current_index = leaf_index;

           return;


           right = path[i];

         tree_leaves.push(leaf);

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

         uint256 current_level_hash = leaf;


             }


             if (current_index % 2 == 0) {


       uint256 left;

             current_level_hash = HashLeftRight(left, right);

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

 }

verify函数是验证某个叶子节点在Merkle树上的示例。只要能给定一条路径,能计较出一个子树根即可。

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

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


     }

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。

人已赞赏
区块链

以太坊2.0的跨分片:它会影响DeFi的可组合性吗?

2019-10-10 0:00:00

区块链

一秒搞懂比特币“断绝见证”!

2019-10-12 0:00:00

问卷调查系统工具软件推荐
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
有新消息 消息中心
搜索
XML 地图 | Sitemap 地图