# 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) \mod r$
- $H = \{(w^i, h_i)\}$, $w$ is the root of unity
- $f(x) = R.\text{lagrange_polynomial}(H) = a_0 + a_1x + \cdots + a_{n-1} x^{n-1}$
- $C = C_{f(x)} = f(\tau)G_1 = a_0G_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) \mod r$, and check $e(C-h_iG_1 + w^iP, G_2) = e(P, \tau G_2)$