Introduction

Original link:

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

Introduction

Following the stateless client idea of ​​Ethereum 2.0, we have implemented an efficient on-chain dynamic Merkle tree (Merkle tree):

On-chain containment verification;
On-chain addition/in-place update;
O(1) storage space cost;
background

background

Merkle trees are widely used to authenticate a large number of members on the chain with extremely low storage costs, such as Uniswap on-chain airdrops. There is no need to upload a large amount of airdrop information (eg, address, quantity) for all users on the chain, and airdrops can significantly save costs in the following ways:

Store the root hash of the tree on-chain
Proof of User Rewards Using Off-Chain Computation
Users get rewards by submitting proofs on the chain

Additionally, the on-chain dynamic Merkle tree is gaining interest. The well-known accounting firm Ernst & Young (EY) has developed a dynamic Merkle tree (https://github.com/EYBlockcha...5). It saves tree storage cost by storing only "boundary" nodes instead of all nodes of the tree, however, the write cost of adding operations is O(log2(N)), which can consume considerable gas on the EVM.

basic idea

Similar to existing static Merkle trees that use Merkle proofs to verify inclusion, the basic idea of ​​on-chain dynamic trees is to reuse Merkle proofs to update the root hash of the tree after inclusion verification. The steps for tree updating are as follows:

Given LeafIndex, oldLeafHash, newLeafHash, oldRootHash, proof
Calculate rootHash with oldLeafHash and proof. If computed rootHash != oldRoothHash, containment verification fails; otherwise continue
Compute newRootHash using newLeafHash and proof, where proof is reused, newRootHash will be the root hash of the updated tree

application

application

Merklized ERC20

The ERC20 standard can be modified to Merklize a tree of (account, balance). Merkle proofs are required for any mint/burn/transfer operations. Merklized ERC20 applications may:

On-Chain Voting - Governance Proposal Voting can cheaply use ERC20 snapshots and compute on-chain votes based on snapshots, without keeping all history of ERC20 balance changes (Compound) or off-chain snapshots.
Remote liquidity mining - contracts on remote chains perform airdrops/liquidity mining on local ERC20 users, where ERC20 snapshots are regularly forwarded to another chain through a decentralized oracle.

Sample code can be found here:
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;