소개

원본 링크:

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

소개

이더리움 2.0의 상태 비저장 클라이언트 아이디어에 따라 효율적인 온체인 동적 머클 트리(Merkle 트리)를 구현했습니다.

온체인 봉쇄 검증;
온체인 추가/인플레이스 업데이트;
O(1) 저장 공간 비용;
배경

배경

머클 트리는 Uniswap 온체인 에어드롭과 같이 매우 낮은 스토리지 비용으로 체인의 많은 구성원을 인증하는 데 널리 사용됩니다. 체인의 모든 사용자에 대해 많은 양의 에어드랍 정보(예: 주소, 수량)를 업로드할 필요가 없으며 에어드랍은 다음과 같은 방식으로 비용을 크게 절감할 수 있습니다.

트리의 루트 해시를 온체인에 저장
오프 체인 계산을 사용한 사용자 보상 증명
사용자는 체인에 증명을 제출하여 보상을 얻습니다.

또한 온체인 동적 Merkle 트리가 관심을 받고 있습니다. 저명한 회계법인 Ernst & Young(EY)은 동적 머클 트리(https://github.com/EYBlockcha...5). 트리의 모든 노드 대신 "경계" 노드만 저장하여 트리 저장 비용을 절약하지만 추가 작업의 쓰기 비용은 O(log2(N))이므로 EVM에서 상당한 가스를 소비할 수 있습니다.

기본 아이디어

머클 증명을 사용하여 포함을 확인하는 기존의 정적 머클 트리와 마찬가지로 온체인 동적 트리의 기본 아이디어는 머클 증명을 재사용하여 포함 확인 후 트리의 루트 해시를 업데이트하는 것입니다. 트리 업데이트 단계는 다음과 같습니다.

주어진 LeafIndex, oldLeafHash, newLeafHash, oldRootHash, 증명
oldLeafHash 및 증명으로 rootHash를 계산합니다. 계산된 rootHash != oldRoothHash인 경우 포함 확인이 실패하고 그렇지 않으면 계속 진행합니다.
newLeafHash를 사용하여 newRootHash를 계산하고 증명이 재사용되는 경우 newRootHash는 업데이트된 트리의 루트 해시가 됩니다.

애플리케이션

애플리케이션

Merklized ERC20

ERC20 표준은 (계정, 잔액)의 트리를 Merklize로 수정할 수 있습니다. 발행/소각/전송 작업에는 Merkle 증명이 필요합니다. Merklized ERC20 애플리케이션은 다음을 수행할 수 있습니다.

온체인 투표 - 거버넌스 제안 투표는 ERC20 잔액 변경(복합) 또는 오프체인 스냅샷의 모든 이력을 유지하지 않고 ERC20 스냅샷을 저렴하게 사용하고 스냅샷을 기반으로 온체인 투표를 계산할 수 있습니다.
원격 유동성 마이닝 - 원격 체인의 계약은 로컬 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;