Merkle Proof Verification

import { Keccak256 } from '@tevm/voltaire/Keccak256';
import { Address } from '@tevm/voltaire/Address';
import { Hex } from '@tevm/voltaire/Hex';
import * as Hash from '@tevm/voltaire/Hash';

// Define airdrop allowlist addresses
const allowlist = [
  "0x742d35Cc6634C0532925a3b844Bc9e7595f251e3",
  "0xf39Fd6e51aad88F6F4ce6aB8827279cffFb92266",
  "0x70997970C51812dc3A010C7d01b50e0d17dc79C8",
  "0x3C44CdDdB6a900fa2b585dd299e03d12FA4293BC",
  "0x90F79bf6EB2c4f870365E785982E1f101E93b906",
  "0x15d34AAf54267DB7D7c367839AAf71A00a2C6A65",
  "0x9965507D1a55bcC2695C58ba16FB37d819B0A4dc",
  "0x976EA74026E726554dB657fA54763abd0C3a0aa9"
];

// Create leaf nodes by hashing each address
const leaves = allowlist.map(addr => {
  const normalized = Address.from(addr);
  return Keccak256(normalized);
});

// Build Merkle tree and get root
const root = Hash.merkleRoot(leaves);
const rootHex = Hex.fromBytes(root);

// Generate proof for a specific address (index 2)
const targetIndex = 2;
const targetAddress = allowlist[targetIndex];

// For a complete Merkle proof, we need sibling hashes at each level
// This is a simplified example - in production use a full Merkle tree library
function generateProof(leaves: Uint8Array[], index: number): Uint8Array[] {
  const proof: Uint8Array[] = [];
  let currentLevel = [...leaves];
  let currentIndex = index;

  while (currentLevel.length > 1) {
    const siblingIndex = currentIndex % 2 === 0 ? currentIndex + 1 : currentIndex - 1;

    if (siblingIndex < currentLevel.length) {
      proof.push(currentLevel[siblingIndex]);
    }

    // Move to next level
    const nextLevel: Uint8Array[] = [];
    for (let i = 0; i < currentLevel.length; i += 2) {
      const left = currentLevel[i];
      const right = currentLevel[i + 1] || left;
      const combined = new Uint8Array(64);
      combined.set(left, 0);
      combined.set(right, 32);
      nextLevel.push(Keccak256(combined));
    }
    currentLevel = nextLevel;
    currentIndex = Math.floor(currentIndex / 2);
  }

  return proof;
}

const proof = generateProof(leaves, targetIndex);

// Verify proof by reconstructing root from leaf + proof
function verifyProof(
  leaf: Uint8Array,
  proof: Uint8Array[],
  root: Uint8Array,
  index: number
): boolean {
  let computed = leaf;
  let currentIndex = index;

  for (const sibling of proof) {
    const combined = new Uint8Array(64);

    if (currentIndex % 2 === 0) {
      combined.set(computed, 0);
      combined.set(sibling, 32);
    } else {
      combined.set(sibling, 0);
      combined.set(computed, 32);
    }

    computed = Keccak256(combined);
    currentIndex = Math.floor(currentIndex / 2);
  }

  // Compare computed root with expected root
  return computed.every((byte, i) => byte === root[i]);
}

const targetLeaf = Keccak256(Address.from(targetAddress));
const isValid = verifyProof(targetLeaf, proof, root, targetIndex);

// Verify an address NOT in the allowlist fails
const invalidAddress = "0x0000000000000000000000000000000000000001";
const invalidLeaf = Keccak256(Address.from(invalidAddress));
const isInvalid = verifyProof(invalidLeaf, proof, root, targetIndex);

// Solidity contract for on-chain verification
contract MerkleAllowlist {
    bytes32 public immutable merkleRoot;

    constructor(bytes32 _merkleRoot) {
        merkleRoot = _merkleRoot;
    }

    function verify(bytes32[] calldata proof, address account)
        public view returns (bool)
    {
        bytes32 leaf = keccak256(abi.encodePacked(account));
        return MerkleProof.verify(proof, merkleRoot, leaf);
    }
}