Airdrop with KZG

Solution from https://twitter.com/developeruche

The Goal is to release merkle proof system used for airdrop verification with KZG commitment.

This is how I implemented it and got stuck when trying to implement the solidity verifier.

1. I get all the address of the valid address and amount, concat it and obtain the hash of the concat.
2. I map each of these hashes to a field element… giving me a vector of field element.
3. I interpolated each of this field elements to get a polynomial. (this polynomial's degree is very huge, for the Optimism Airdrop I used as a case study, I was a 268K degree polynomial.
4. Commit to the polynomial
5. Push the polynomial commitment onchain
6. Generate proof function to be used by users
7. User can now call the contract and the contract verification logic would carry out the validity assations

• BN256's order:
  $r$
• $U=[({\text{addr}}_i,v_i)],i\in \{0,\dots ,n-1\}$
• $h_i=h({\text{addr}}_i|v_i)\mathrm{mod}r$
• $H=\{(w^i,h_i)\}$,
  $w$ is the root of unity
• $f(x)=R.\text{lagrange\_polynomial}(H)=a_0+a_{1}x+\cdots +a_{n-1}{x}^{n-1}$
• $C=C_{f(x)}=f(\tau )G_1=a_0{G}_1+a_1\tau G_1+a_2{\tau }^2{G}_1+\cdots a_{n-1}{\tau }^{n-1}{G}_1$

The contract need to prove point

$(w^i,h_i)$ is in

$y=f(x)$

1. Setup:
   • Owner generates the
     $U$ with order, and compute
     $f(x),w,C$
   • Owner set the
     $C$ in the contract.
2. User generate the proof in frontend:
   • User login
     ${\text{addr}}_i$ with wallet
   • Server computes
     $q(x)=\frac{f(x)-h_i}{x-w^i}$,
     $P=C_{q(x)}=q(\tau )G_1$, return the
     $(w^i,v_i,P)$ according to
     ${\text{addr}}_i$
3. User call contract's verify with
   $i,v_i,P$:
   • Contract compute
     $h_i=h(\text{msg.sender}|v_i)\mathrm{mod}r$, and check
     $e(C-h_i{G}_1+w^{i}P,G_2)=e(P,\tau G_2)$