← Back to blogs
// TECHNICAL WRITING

Understanding Polynomial Commitment KZG using Airdrop Distribution (Part 1)

Understanding Polynomial Commitment KZG using Airdrop Distribution (Part 1) — thumbnail

// · · 3 min read

cryptography zero knowledge

In this dynamic world of cryptocurrencies, airdrops have become a popular method for distributing tokens to a wide audience. However, traditional airdrop methods often work fine, but we could make it better (more efficient for the claimers). Traditional airdrops employ a Merkle proof system whose verification has a complexity of O(log n) and, as the saying goes, "we only care about verification complexity, the provers can burn down their servers". In this article, we explore a revolutionary approach using KZG polynomial commitment, focusing on its application in airdrop distribution.

This article is divided into 2 posts. This very post introduces you to how airdrops are done in production using one of the biggest airdrops in the DeFi space, Optimism's Airdrop, with a little lazy twist. Let's make a deep dive.

Airdropping with the Merkle Proof System

We would be airdropping tokens of varying amounts to over 200k valid addresses used in Optimism's airdrop using the Merkle Proof System. But first, let's discuss what a Merkle tree is and how it operates.

A Merkle tree is a way to organize data in a tree structure for efficient verification and integrity checks. In blockchain, it's like a puzzle where each piece of data (like a valid user address) is a puzzle piece, and the Merkle tree combines these pieces in a way that makes it easy to prove if a specific piece belongs to the puzzle without showing the entire puzzle. It helps ensure data hasn't been tampered with, and it's a key part of blockchain's security. With this, a user is able to prove that their address is part of the valid users' addresses and be sure of the integrity of the airdrop recipients after the commitment (Merkle root) has been done.

I advise you watch the video: youtube.com/watch?v=n6nEPaE7KZ8

Let's Airdrop!

This airdrop has two stages: creating the tree and proofs, then verifying the proofs.

The airdrop data is structured as the address to be airdropped and the amount to be airdropped. But this poses a problem: how do we make this a leaf in the Merkle tree? To solve this, we hash the address and the amount together to get the leaf that is added to the Merkle tree.

const encodedData = defaultAbiCoder.encode(
  ['address', 'uint256'],
  [
    row[0],
    row[1].trim()
  ]);

const hash = keccak256(encodedData);
leaves.push(hash);

Now that we have all these leaves, we can build the tree.

const merkleTree = new MerkleTree(leaves, keccak256, { sortPairs: true });
const rootHash = merkleTree.getHexRoot();

After getting the tree and its root, the root is stored in the verifying smart contract and is used to verify any user's claim. Storing the root in the smart contract gives credibility that the valid set of addresses for this airdrop has not been manipulated after this "commitment".

We can now explore the later stage: the verification stage and payout. The verification phase happens in the smart contract — a function takes in the data to construct a leaf, plus a proof that the constructed leaf is a member of the tree whose root is stored in the smart contract, and then makes the payout. This is how the function looks:

function claim(bytes32[] calldata proof, address _to, uint256 _amount) external {
    address requestor = msg.sender;

    if (!verify(proof, requestor, _amount)) revert InvalidProof();
    if (claimed[requestor]) revert AlreadyClaimed();
    claimed[requestor] = true;

    handlePayment(_to, _amount);
}

Here is an example of how this smart contract function would be called:

let claimCall = contract.claim(
  [
    "0x8bc39765f21e398418940c7f1c88ccb9fdff6601d645f71c61feb5d805a24203",
    "0xa3f7c983f98efe6c38c82451dbbbca59caf529e9c4818c9cc92b1bf648e7cb6b",
    "0x1c3599af9db3dc400adcddd39d6c28b15056d4be06e1c6186025f08fd8008493",
    "0x904a2fcb4c2b1d75f584dd2e470c53bbd1b12e1474174928d68261766602a4d2"
    // ...18 proof elements total
  ],
  "0xcB67fF716717FCe7aCE371804eae96C1c88A81dC",
  ethers.parseEther("amount")
);

To emphasize the efficiency of this algorithm: this tree, having over 260k leaves, only needs 18 leaves to prove the membership of a leaf (complexity of O(log n)).

With this knowledge, we'll explore achieving the same objective in "constant time" using KZG commitment.

"To verify a KZG commitment, we would need just one point in G2 of a BLS12-381 elliptic curve…" — think about it.

Explore How This Is Achieved (Part 2)

Continue to Part 2: Understanding Polynomial Commitment (KZG) using Airdrop Distribution.

Code for the Merkle Proof Airdrop

The sample Solidity contract and the script for generating the tree, root, and proof are available in this repository.

← Back to blogs