Efficient On-Chain Dynamic Merkle Tree

Editor’s note: This article is a technical article published by QuarkChain founder & CEO Dr. Zhou on the Ethereum technology forum ethresear.ch, introducing an efficient on-chain dynamic Merkle tree solution.

Original link:

Abstract

Following the stateless client idea, we implement an efficient on-chain dynamic Merkle tree with

  • on-chain inclusive verification;
  • on-chain append / in-place update;
  • O(1) cost in storage space;
  • O(1) storage write cost for update / append operations.

Background

Static Merkle tree is widely used on-chain to verify the membership of a large group with a very low storage cost, e.g., Uniswap on-chain airdrop. Instead of uploading the airdrop info (address, amount) of all users on-chain, which can be extremely costly, the airdrop can significantly save the cost by

  • storing the root hash of the tree on-chain
  • verifying/distributing the reward for a user upon user’s collection with an off-chain computed proof.

Further, the on-chain dynamic Merkle tree is gaining interest. Ernst & Young (EY) has developed an on-chain append-only dynamic Merkle tree (https://github.com/EYBlockchain/timber 6). It saves the storage cost of the tree by only storing “frontier” nodes instead of all the nodes of the tree, however, the write cost of append operation is O(log2(N)), which may consume considerable gas on EVM.

Basic Idea

Similar to the existing static Merkle tree, which uses proof to verify inclusion, the basic idea of the on-chain dynamic tree is to reuse the proof to update the root hash of the tree after inclusion verification. The steps of a tree update are:

  1. Given leafIndex, oldLeafHash, newLeafHash, oldRootHash, proof
  2. Calculate rootHash with oldLeafHash and proof. If the calculated rootHash != oldRoothHash, inclusion verification failed; otherwise continue
  3. Calculate newRootHash with newLeafHash and proof, where proof is reused and newRootHash will be the root hash of the tree after the update.

Note that only newRootHash is written to blockchain so that the cost of space and write is O(1).

Applications

Merklized ERC20

The ERC20 standard can be modified to Merklize the tree of (account, balance). Any mint/burn/transfer operations will require Merkle proof. The applications of the Merklized ERC20 maybe

  • On-chain voting — a governance proposal voting can cheaply take a snapshot of the ERC20 and count the vote on-chain based on snapshot instead of maintaining all history of ERC20 balance change (Compound) or off-chain snapshot.
  • Remote liquidity mining — a contract on a remote chain performs airdrop/liquidity-mining of the local ERC20 users, where the ERC20 snapshots are periodically forwarded to another chain via decentralized oracle.

Example code can be found here:

--

--

--

QuarkChain provides a secure, decentralized and scalable blockchain solution to deliver 100,000+ on-chain TPS

Recommended from Medium

Blockchaining Banks — A strategist’s guide to letting go and enjoying the ride

RiveX at Singapore Fintech and Blockchain Week

End-to-End MongoDB GraphQL Database, Chainlink External Adapter, and Oracle Contract on Ethereum

What is Thinkium

Choosing a Uniswap V3 Price Range: The Fundamentals

SXP Swap is live!

Real-World Blockchain Applications

TOP Network ✖ Blockchain Infinity AMA Recap

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
QuarkChain

QuarkChain

https://www.quarkchain.io

More from Medium

SNXweave Weekly Recap

Introducing Flexible Mass Payouts in Multiple Tokens

Announcing our Partnership with Symbiosis: Transforming Multi-Chain Liquidity

OXY/MAPS: Team Update