零知识证明 – 一种新型的Merkle树(Shrubs)
这几天在日本大阪正在举办Devcon 5。议题中有个topic吸引我的眼球:
Shrubs – A New Gas Efficient Privacy Protocol
在以太坊上,传统的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树的原因。
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.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次计算
在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。
附上,好朋友从现场发回的其他照片,也分享给小伙伴们(图片中有一些地方有错误,发现错误的小伙伴留言,有奖励~):
比推快讯
更多 >>- Base发布2024年第6轮Base建设者资助名单
- PADO与ArweaveAO合作发起可验证机密计算VCC
- 基于以太坊区块链的影视支付平台FilmChain完成280万欧元融资,Holt InterXion领投
- 企业忠诚度平台Superlogic完成760万美元战略轮融资,Amex Ventures等参投
- 俄罗斯国家杜马金融市场委员会主席:数字金融资产可能取代法定货币用于国际支付
- RWA及证券型代币服务提供商Cspro完成战略轮融资,Taisu Ventures参投
- SolanaAI项目gm.ai发布gmID
- ETH跌破2900美元
- BTC跌破60000美元
- 美联储Bostic重申预计今年将进行一次降息
- 美联储Kashkari:可能要等到2025年才能降息
- 隐私优先移动运营商Cape完成6100 万美元融资,A-Star 和 a16z 共同领投
- 10x Research联创:比特币在未来几周内可能会跌至 50,000 美元
- Kraken收购TradeStation Crypto,以扩大在美国的监管许可范围
- Avail公布空投资格查询网站,空投总量为 6 亿枚 AVAIL
- BTC跌破63,000美元,日内涨幅收窄至1.83%
- 前迪士尼高管旗下公司Galactic Group推出Web3游戏工作室
- Mango Markets 开发者因操纵协议窃取1.1亿美元而被判有罪
- 数据:87.4%的Solana网络验证者已更新至V1.17.31
- 消息人士:Coinbase纽约新办公室面积翻倍,租约 11 年
- Tether CEO:正在努力建立关系以获得四大会计师事务所的审计
- Uniswap 基金会:v4核心合约将进入审计,预计将于今年晚些时候部署
- 美联储Bostic:在年底之前我们不会降低利率
- Coinbase国际交易所和 Coinbase Advanced 将上线WIF永续合约
- Optimism:第四轮Retro Funding将拨出1000万枚OP奖励Superchain开发者
- 德意志银行:比特币减半利好已被部分消化,预计随后不会出现大幅反弹
- 赵长鹏:教育游戏项目Giggle Academy的目标年龄将从2-3岁开始,持续 18 年或更长
- CryptoQuant研究主管:目前比特币交易者的未实现利润率基本为零,抛压可能正在下降
- 币安Web3钱包推出zkLink Nova空投活动,100万枚ZKL代币可供领取
- Peter Thiel 支持的Layer N 推出流动性计划,并获Amber Group 2000 万美元赠款
- 以太坊协议Heroglyphs发布白皮书V0,拟用新代币激励 ETH 独立质押者
- Arbitrum社区提议更改扩展计划以允许在任何区块链上部署新的Orbit链
- Blast生态SocialFi交易卡游戏fantasy.top完成Pre-Seed轮融资
- 比特币突破64000美元,日内涨超5%
- Nexo联创:BTC价格或在8个月内翻倍
- Tether 宣布成立四个新部门,以扩展除稳定币之外的业务
- MerlinSwap推出esMP代币,将于4月22日开启esMP质押活动
- 美联储威廉姆斯:如果数据支持,美联储将会加息
比推专栏
更多 >>观点
项目
比推热门文章
- Base发布2024年第6轮Base建设者资助名单
- PADO与ArweaveAO合作发起可验证机密计算VCC
- 基于以太坊区块链的影视支付平台FilmChain完成280万欧元融资,Holt InterXion领投
- 企业忠诚度平台Superlogic完成760万美元战略轮融资,Amex Ventures等参投
- 俄罗斯国家杜马金融市场委员会主席:数字金融资产可能取代法定货币用于国际支付
- 又一个不眠夜,比特币第四次减半后何去何从?
- 减半后才是真正牛市?回顾历次减半前后比特币价格变化
- 专访神鱼:本轮牛市或无「山寨季」,关注模块化区块链发展
- 从集中化到协作:去中心化人工智能的案例
- Runes 协议上线在即,一文盘点 10 个 Runes 代打工具