乐趣区

关于区块链:技术解读高效的链上动态-Merkle-Tree

jiezi


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

原文链接：

https://ethresear.ch/t/effici…

简介

遵循以太坊 2.0 的无状态客户端的思维，咱们实现了一个高效的链上动静 Merkle tree（默克尔树）：

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

背景

Merkle tree 宽泛用于以极低存储老本在链上大量成员身份验证，例如 Uniswap 链上空投。无需上传链上所有用户大量的空投信息（比方，地址、数量），空投能够通过以下形式显著节省成本：

将树的根哈希存储在链上
应用链下计算证实用户处分
用户通过链上提交证实来获取处分

此外，链上动静 Merkle tree 正在引起人们的趣味。驰名的会计事务所安永（Ernst & Young，EY) 开发了一种仅能在链上增加的动静 Merkle tree (https://github.com/EYBlockcha… 5)。它通过只存储“边界”节点而不是树的所有节点来节俭树的存储老本，然而，增加操作的写入老本为 O(log2(N))，这可能会在 EVM 上耗费相当大的 gas。

根本想法

相似于现有的动态 Merkle tree，它应用默克尔证实来验证蕴含性，链上动静树的根本思维是在蕴含验证后重用默克尔证实来更新树的根哈希。树更新的步骤如下：

给定 LeafIndex、oldLeafHash、newLeafHash、oldRootHash、proof
用 oldLeafHash 和 proof 计算 rootHash。如果计算出的 rootHash != oldRoothHash，则蕴含验证失败；否则持续
应用 newLeafHash 和 proof 计算 newRootHash，其中证实被重用，newRootHash 将是更新后树的根哈希

请留神，只有 newRootHash 被写入区块链，因而空间和写入的老本是 O(1)。

利用

Merklized ERC20

ERC20 规范能够批改为 Merklize（账户，余额）的树。任何造币 / 销毁 / 转移操作都须要 Merkle 证实。Merklized ERC20 的利用或者能够：

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

示例代码能够在这里找到：
https://github.com/QuarkChain…

/SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "hardhat/console.sol";

import "@openzeppelin/contracts/token/ERC20/IERC20.sol";
import "@openzeppelin/contracts/token/ERC20/extensions/IERC20Metadata.sol";
import "@openzeppelin/contracts/utils/Context.sol";

import "./DynamicMerkleTree.sol";

contract MerklizedERC20 is Context, IERC20, IERC20Metadata {mapping(address => uint256) private _balances;

    mapping(address => uint256) private _indices1;

    uint256 private _totalSupply;

    string private _name;
    string private _symbol;
退出移动版