技术解读：高效的链上动态 Merkle Tree

编按：本文是QuarkChain创始人&CEO周期博士在以太坊技术论坛ethresear.ch发布的一篇技术文章，介绍了一个高效的Merkle tree方案设计。

原文链接：

https://ethresear.ch/t/efficient-on-chain-dynamic-merkle-tree/11054

简介

• 链上包含性验证；
• 链上添加/就地更新；
• O(1) 存储空间成本；
• 更新/添加操作的 O(1) 存储写入成本。

背景

• 将树的根哈希存储在链上
• 使用链下计算证明用户奖励
• 用户通过链上提交证明来获取奖励

基本想法

1. 给定 LeafIndex、oldLeafHash、newLeafHash、oldRootHash、proof
2. 用 oldLeafHash 和 proof 计算 rootHash。如果计算出的rootHash != oldRoothHash，则包含验证失败；否则继续
3. 使用 newLeafHash 和 proof 计算 newRootHash，其中证明被重用，newRootHash 将是更新后树的根哈希

应用

Merklized ERC20

• 链上投票——治理提案投票可以廉价地使用 ERC20 快照并根据快照计算链上投票，而不需要保留 ERC20 余额变化（Compound）或链下快照的所有历史记录。
• 远程流动性挖掘——远程链上的合约对本地 ERC20 用户进行空投/流动性挖矿，其中 ERC20 快照通过去中心化预言机定期转发到另一条链。

QuarkChain/DynamicMerkleTree/blob/abe6c7ee8f2fef105649943d5e329e5f5e697f8d/contracts/MerklizedERC20.sol

/SPDX-License-Identifier: MITpragma solidity ^0.8.0;<br />import "hardhat/console.sol";<br />import "@openzeppelin/contracts/token/ERC20/IERC20.sol";import "@openzeppelin/contracts/token/ERC20/extensions/IERC20Metadata.sol";import "@openzeppelin/contracts/utils/Context.sol";<br />import "./DynamicMerkleTree.sol";<br />contract MerklizedERC20 is Context, IERC20, IERC20Metadata {    mapping(address => uint256) private _balances;<br />    mapping(address => uint256) private _indices1;<br />    uint256 private _totalSupply;<br />    string private _name;    string private _symbol;

作者：鲨丁信息科技；来自链得得内容开放平台“得得号”，本文仅代表作者观点，不代表链得得官方立场凡“得得号”文章，原创性和内容的真实性由投稿人保证，如果稿件因抄袭、作假等行为导致的法律后果，由投稿人本人负责得得号平台发布文章，如有侵权、违规及其他不当言论内容，请广大读者监督，一经证实，平台会立即下线。如遇文章内容问题，请联系微信：chaindd123。