零知识证明 - 一种新型的Merkle树(Shrubs)

区块链资讯星想法2019-10-11 11:11:26  阅读 -评论 0

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

零知识证明 - 一种新型的Merkle树(Shrubs)

以太坊上,传统的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节点,蓝色是更新的节点):
零知识证明 - 一种新型的Merkle树(Shrubs)

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

零知识证明 - 一种新型的Merkle树(Shrubs)

整个添加过程如下面动图效果(橙色连线代表hash计算):

零知识证明 - 一种新型的Merkle树(Shrubs)

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。
零知识证明 - 一种新型的Merkle树(Shrubs)

图中,Shrubs最坏情况下的GAS消耗应该不是168w,应该在40w左右。
如果使用Groth16零知识证明的话,大约需要不到50w的GAS(EIP1008情况下)。
零知识证明 - 一种新型的Merkle树(Shrubs)

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

声明:链世界登载此文仅出于分享区块链知识,并不意味着赞同其观点或证实其描述。文章内容仅供参考,不构成投资建议。投资者据此操作,风险自担。此文如侵犯到您的合法权益,请联系我们kefu@lianshijie.com

参与讨论 (0 人参与讨论)

相关推荐

比特币中的密码学:哈希函数五大特性和挖矿原理

比特币中的密码学:哈希函数五大特性和挖矿原理

比特币本身是密码学发展的产物,利用了密码学中的很重要的“单向散列函数”以及数字签名两大技术来构建,今天我们来集中精力讲解单向散列函数的5种重要的特性,以及比特币挖矿相关的技术原理。本文总结了单数散列函数也就是哈希函数的特性,这就是很多区块链应用的基础以及比特币加密挖矿的基本原理。

比特币中的密码学:哈希函数的五大特性和挖矿原理

比特币中的密码学:哈希函数的五大特性和挖矿原理

比特币本身是密码学发展的产物,利用了密码学中的很重要的“单向散列函数”以及数字签名两大技术来构建,今天我们来集中精力讲解单向散列函数的5种重要的特性,以及比特币挖矿相关的技术原理。这就是哈希函数一个非常重要的特性。本文总结了单数散列函数也就是哈希函数的特性,这就是很多区块链应用的基础以及比特币加密挖矿的基本原理。

中信银行打造“区块链”信用证结算!

中信银行打造“区块链”信用证结算!

科技不会改变金融的实质,但却能让金融服务更高效,能让资金供、需方信息不对称的问题更好地解决。近期,中信银行首个区块链项目——基于区块链的国内信用证信息传输系统(简称BCLC)(一期)成功上线,这是国内银行业第一次将区块链技术应用于信用证结算领域。 据中信银行国际业务部总经理助理张栩青介绍,将现在流行的区块链技术应用在国内信用证中,改变了银行传统信用证业务模式,信用证的开立、通知、交单、承兑报文

中国信息技术部门成立区块链研究实验室

中国信息技术部门成立区块链研究实验室

暴走时评:本月初,中国政府对国内的ICO和数字货币交易所的打击在世界范围内引起了强大反响,但政府已经多次声明不会将区块链与数字货币划等号,依然非常重视区块链技术在中国的发展。鉴于中国工业和信息化部成立了一个专门研究区块链的实验室,这一论调也得到了进一步的证实。 虽然中国政府最近在大力打击比特币交易所和ICO,但仍然致力于开发区块链在其他领域的潜力。 据财新网报道,中国工业和信息化部已经成立了一

 分布式账本中的生命科学

分布式账本中的生命科学

生物科学是医学领域涉及遗传研究,疾病预防和生活方式治疗(lifestyle treatments)的学科。它已经存在了很长时间,但区块链技术的基础设施应用给该学科提供了重大进步的可能性。 根据Pistoia Alliance进行的2016年6月份高级制药和生命科学领袖调查,83%的受访者表示,他们预计在五年内将全面采用区块链技术。 Pistoia Alliance是一个全球性的非营利组织,致

区块链vs.核能:日本最大电力公司东京电力(TEPCO)寻求使用区块链减轻对核电的依赖

区块链vs.核能:日本最大电力公司东京电力(TEPCO)寻求使用区块链减轻对核电的依赖

东京电力公司 (TEPCO) 对于能源过度中心化的风险可以说绝不陌生。 也许最著名的就是2011年发生的福岛核电站事故,这个日本最大的能源公司如今正在寻求区块链技术来防止这种灾难再次发生。 然而,从使用微型风车的分布式风力发电到用于存储在电力成本低时购买的电力的智能电池,可替代能源项目一直以来都属于个人慈善事业。 然而,TEPCO风险投资部门主管Jeffrey Char认为区块链能够帮助为这

继证监会发表代币发行声明之后,香港交易所Gatecoin将下线部分ICO币

继证监会发表代币发行声明之后,香港交易所Gatecoin将下线部分ICO币

经过一系列监管以及合规审查后,香港交易所Gatecoin将会下线那些被金融监管部门定性为"证券"的代币。 香港加密货币交易所Gatecoin透露,如果在该平台交易的ICO代币在法律上符合"证券"定义,他们就会下线这些代币。据巴比特上月报道,香港主要的金融监管部门证券及期货事务监察委员会(SFC)表达了对ICO这种日渐普及的募资模式的担忧。 尽管ICO中售卖的数字代币通常都被定义为虚拟商品,但

IBM与超级账本共同加入去中心化身份基金会(DIF),推动创建区块链ID行业标准

IBM与超级账本共同加入去中心化身份基金会(DIF),推动创建区块链ID行业标准

IBM与超级账本已经签署协议加入去中心化身份基金会(DIF),这个于今年初成立的联盟旨在帮助推动基于区块链的ID系统的互操作性和标准。 这两个企业区块链大佬加入了这个有各种企业组成的团体,其中包括像微软和埃森哲这样的大企业,还有像Civic和Gem这样的创业公司,以及像uPort和Sovrin这样的开源项目。 DIF执行主管告诉Coindesk说: "这应该是一个信号,表明在这一领域有广泛的

麦妖榜
更新日期 2019-09-03
排名用户贡献值
1牛市来了30910
2BitettFan24187
3等待的宿命23810
4区块大康20369
5六叶树20310
6linjm122719429
7天下无双16192
8lizhen00215280
9让时间淡忘14586
10yelanyi050511349
返回顶部 ↑