Ethreal

English Version

Ethreal is a puzzle in zkctf hosted by scalebit. At that time, I understood the code of this puzzle quickly, but I couldn't find its vulnerability. I was stuck and couldn't solve it in the end, so I will give a comprehensive summary here.

The original code of this puzzle is on github, which contains Solidity and Golang codes. Solidity is the topic, and we need to call the register and mint of the contract. golang is auxiliary code that helps us generate proofs and call contracts. I am not familiar with the Go language. I can only understand the logic, but rewriting it is more troublesome.

The problem is that if we follow the default settings in Golang, we can only mint 9. To finally solve the problem, we need to mint 20.

Let’s take a look at the contract logic first:

Pairing.sol

Implemented functions related to BN254 elliptic curves G1 and G2.
PRIME_Q:

$21888242871839275222246405745257275088696311157297823662689037894645226208583$ is the base field's Modulus.

G1Point:

$(x,y)$
G2Point:

$(x_i=x_0[i]\cdot z+x_1[i],y_i=y_0[i]\cdot z+y_1[i])$. Please note that the coefficient of the extended domain

$z$ is

$x_0$
negate():

$-P$
plus():

$P_1+P_2$
mulScalar():

$s\cdot P$
pairing():

$e(A_1,-A_2)\cdot e(B_1,B_2)=1$ if

$e(A_1,A_2)=e(B_1,B_2)$

Constants.sol

Given srs, the prove key (in

${\mathbb{G}}_1$) has 17 elements and the verify key (in

${\mathbb{G}}_2$) has 2 elements.

PRIME_Q:

$21888242871839275222246405745257275088696311157297823662689037894645226208583$
PRIME_R:

$21888242871839275222246405745257275088548364400416034343698204186575808495617$ is the scalar field's Modulus.
bn254_b_coeff:

$3$, used in

$Y^2=X^3+3$

SRS_G1_X[17], SRS_G1_Y[17],
SRS_G2_X_0[2], SRS_G2_X_1[2],
SRS_G2_Y_0[2], SRS_G2_Y_1[2],

SRS:

$(G_1,\tau \cdot G_1,{\tau }^2\cdot G_1,...{\tau }^{16}\cdot G_1,G_2,\tau \cdot G_2)$

KZGVerifier.sol

$G_1=\text{SRS\_G1\_0}$

$G_2=\text{g2Generator}$

$\tau G_2=\text{SRS\_G2\_1}$

• g1Check:
  $y_P=x_P^3+3$
• verify(_commitment,_proof,_index,_value):
  • check _commitment(
    $C$), _proof(
    $H$) in
    ${\mathbb{G}}_1$, _index(
    $i$), _value(
    $v$) in base field, This should be an error in the code. It should be checking that
    $i$ and
    $v$ are in the scalar field.
  • commitmentMinusA:
    $C-v\cdot G_1$
  • negProof:
    $-H$
  • indexMulProof:
    $i\cdot H$
  • check
    $e(iH+C-v{G}_1,G_2)=e(H,\tau G_2)$
  • We find the relationship of the corresponding scalar elements in the pairing relationship:
    $ih(\tau )+f(\tau )-v=h(\tau )\cdot \tau$. If you are not familiar with this step, you can refer to what is the KZG PCS. Then according to
    $v=f(i)$,
    $f(x)-f(i)=h(x)(x-i)$
• verifySoulBox:
  • check _commitment(
    $C$), _proof(
    $H$) in
    ${\mathbb{G}}_1$.
  • commitmentMinusA:
    $C-S$
  • negProof:
    $-P$
  • indexMulProof:
    $i\cdot H=0H=\mathcal{O}$
  • check
    $e(C-S,G_2)\cdot e(-H,\tau \cdot G_2)=1$
  • $C=S+\tau \cdot H$
• fr_inverse:
  $a^{-1}=a^{r-1}\mathrm{mod}r$,
  $r$ = PRIME_R
• fr_pow:
  $a^{\text{power}}\mathrm{mod}r$
• fr_div:
  $a/b\mathrm{mod}r$
• fr_mul_add:
  $a\cdot b+c\mathrm{mod}r$
• getBarycentricWeights and evaluateBarycentricPolynomial, use for evaluating the poly defined in xValues, yValues, and return
  $y=f(x)$

MintGem

     struct DepositInfo {
         bool registered;
         uint256 nonce;
         Pairing.G1Point commitment;
         Pairing.G1Point soulBox;
         uint256[] collectedY;
         bool escaped0;
         bool escaped1;
     }

• getCollectedY: return DepositInfo.collectedY
• register: _commitment(
  $C$), _proof(
  $H$), _soulBox(
  $S$)
  • check registered is false
  • check verifySoulBox(
    $C,H,S$)
  • new DepositInfo with
    $C,S$
• getNonce: nonce
• mint: _proof(
  $H$), _value(
  $v$)
  • check registered is true
  • check KZGVerifier.verify with (
    $C$,
    $H$, nonce,
    $v$)
  • collectedY.push(value)
  • calculate the polynomial
    $f(x)$ with lagrange interpolation in [(1, v1), (2, v2), (3, v3), ....]
  • calculate soul
    $s=f(0)$
  • soulBox(
    $S$):
    $S=s\cdot G_1$
  • require S.x != DepositInfo.soulBox.x

Attack principle

Why can't we mint gems over polynomial

$f(x)$ degrees? Because polynomials of degree

$n$ we only need

$(n+1)$ points to recover the polynomial, which ultimately leads to S.x ==DepositInfo.soulBox.x, that is, we can recover the correct

$f(0)$. The SRS in the contract only gives 17

$G1$ points, and the degree of our polynomial is at most 16.

Attack methods:

1. Suppose we want to attack KZGVerifier.verify:
   $f(i)G_1=C+iH-\tau H$, where
   $f(i)$ (i.e. parameter value),
   $H$ (i.e. parameter proof) is the input we can decide on.
   $H=\frac{f(i)G_1-C}{i-\tau }$ we can set any
   $f(i)$ and find the corresponding
   $H$ if we know the
   $\tau$, if we are random Generating an incorrect
   $f(i)$ will never restore the correct
   $f(0)$, and then we can mint infinitely. This is actually how the first place winner do. He searched GitHub and found
   $\tau$ in the test code of some ZK projects.
2. Suppose we want to attack KZGVerifier.verifySoulBox:
   $S=C-\tau H$, where
   $C$ (i.e. parameter _commitment),
   $H$ (i.e. parameter _proof),
   $S$ (i.e. Parameter _soulBox), we can all decide.
   $C$ should only enter the correct commitment, because it will affect the verification of subsequent pairing. Then even if we don't know
   $\tau$, we can construct
   $H=G_1$,
   $S=C-\tau G_1$ to pass the verification of verifySoulBox, because
   $\tau G_1$ is the second point of srs! Personally, I prefer this method, which has a wider scope of application. The second place is to use this method, and clearly state that the vulnerability is The contract does not verify whether the caller has knowledge of the discrete logarithm of
   $S$, that is,
   $S=s{G}_1$, the contract does not check whether the caller knows
   $s$. The third person also uses this method, and pointed out in the article he cited that this scheme can be used for RLN (Rate-Limiting Nullifier), More efficient than zksnark solution (1ms vs 1s). And he cited another article describing the vulnerability in detail.

PoC

Based on the second attack method, we use Rust and Foundry to reproduce the entire attack process.
Suppose

$(x_0,y_0)$ is on

$f(x)$, then we can find the coefficient of

$h(x)$ based on the coefficients of

$x_0$ and

$f(x)$. (Why is this done here? Because I am using the bn256 mod in halo2curve (the bn254 curve in the previous article). It does not have a native implementation of polynomial commitment, so it needs to be written manually. If you use arkworks, it may be more convenient:

• f.len() = n -> f.degree = n-1
• $f(x)=a_{n-1}{x}^{n-1}+a_{n-2}{x}^{n-2}+\cdots +a_{1}x+a_0$
• $\begin{array}{rl}h(x)& =\frac{f(x)-y_0}{x-x_0}\\ & =(a_{n-1}{x}^{n-1}-a_{n-1}{x}_0{x}^{n-2}+a_{n-1}{x}_0{x}^{n-2}+a_{n-2}{x}^{n-2}+\cdots +a_0-y_0)/(x-x_0)\\ & =(a_{n-1}{x}^{n-2}(x-x_0)+(a_{n-1}{x}_0+a_{n-2})x^{n-2}+\cdots +a_0-y_0)/(x-x_0)\\ & =a_{n-1}{x}^{n-2}+((a_{n-1}{x}_0+a_{n-2})x^{n-2}+\cdots +a_0-y_0)/(x-x_0)\\ & =a_{n-1}{x}^{n-2}+((a_{n-1}{x}_0+a_{n-2})x^{n-2}-(a_{n-1}{x}_0+a_{n-2})x_0{x}^{n-3}+(a_{n-1}{x}_0+a_{n-2})x_0{x}^{n-3}+a_{n-3}{x}^{n-3}+\cdots +a_0-y_0)/(x-x_0)\\ & =a_{n-1}{x}^{n-2}+(a_{n-1}{x}_0+a_{n-2})x^{n-3}+((a_{n-1}{x}_0+a_{n-2})x_0{x}^{n-3}+a_{n-3}{x}^{n-3}+\cdots +a_0-y_0)/(x-x_0)\\ & =a_{n-1}{x}^{n-2}+(a_{n-1}{x}_0+a_{n-2})x^{n-3}+((a_{n-1}{x}_0+a_{n-2})x_0+a_{n-3})x^{n-4}+(((a_{n-1}{x}_0+a_{n-2})x_0+a_{n-3})x_0+a_{n-4})x^{n-5}\end{array}$
• $h(x)=b_{n-1}{x}^{n-2}+b_{n-2}{x}^{n-3}+\cdots +b_{2}x+b_1+\frac{b_0}{x-x_0}$
• $b_{n-1}=a_{n-1}$
• $b_{n-2}=a_{n-1}{x}_0+a_{n-2}$
• $b_{n-3}=a_{n-1}{x}_0^2+a_{n-2}{x}_0+a_{n-3}$
• $b_{n-4}=a_{n-1}{x}_0^3+a_{n-2}{x}_0^2+a_{n-3}{x}_0+a_{n-4}$
• $b_1=a_{n-1}{x}_0^{n-2}+a_{n-2}{x}_0^{n-3}+a_{n-3}{x}_0^{n-4}+a_{n-4}{x}_0^{n-5}+\cdots +a_1$
• $b_0=0$

Let’s use sage to verify it and pass the verification:

r = 21888242871839275222246405745257275088548364400416034343698204186575808495617
Fr = GF(r)

R.<x> = PolynomialRing(Fr, 'x')
points = [(1,3),(3,7),(19,23), (20, 24)]
f = R.lagrange_polynomial(points)
# 19520216596230932581243139626618330122828219713821317177859509581595384769483*x^3 + 119041320881932900331515540018065882060 52619235313983590432356662874562515160*x^2 + 5056056101974569422682649280337206818699768384891423137871807399823066874721*x + 7 296080957279758407415468581752425029516121466805344781232734728858602831873

p = (f-23)/(x-19)
# 19520216596230932581243139626618330122828219713821317177859509581595384769483*x^2 + 106881185953133302985823092381811840344 66598990846426126893567541398128709848*x + 11136123566374368095528873098464227676629869607229210455565753007205235901280

Fr(19520216596230932581243139626618330122828219713821317177859509581595384769483)*Fr(19) + Fr(119041320881932900331515540018065 88206052619235313983590432356662874562515160)
# 10688118595313330298582309238181184034466598990846426126893567541398128709848

Fr(19520216596230932581243139626618330122828219713821317177859509581595384769483)*Fr(19)*Fr(19) + Fr(119041320881932900331515540 01806588206052619235313983590432356662874562515160)*Fr(19) + 505605610197456942268264928033720681869976838489142313787180739982 3066874721
# 11136123566374368095528873098464227676629869607229210455565753007205235901280

Then use rust to generate proofs etc:

// f(x) = a_0 + a_1 x + a_2 x^2 + ...
// y = f(x)
// h(x) = (f(x) - y_0) / (x - x_0)
// H = h(\tau) * G
pub fn open(f: &[Fr], x: Fr, srs: &[G1Affine]) -> (Fr, G1Affine) {
     let mut y = Fr::zero();
     let mut x_pow = Fr::one();
     for a in f.iter() {
         y += x_pow * a;
         x_pow *= x;
     }
     let mut h = vec![Fr::zero(); f.len() - 1];
     let len = h.len();
     for (i, a) in f.iter().skip(1).rev().enumerate() {
         if i == 0 {
             h[len - 1 - i] = *a;
         } else {
             h[len - 1 - i] = h[len - i] * x + a;
         }
     }

     let proof = h
         .iter()
         .zip(srs.iter())
         .fold(G1Affine::identity(), |acc, (a_i, g_i)| {
             (acc + g_i * a_i).into()
         });

     (y,proof)
}

pub fn commit(f: &[Fr], srs: &[G1Affine]) -> G1Affine {
     f.iter()
         .zip(srs.iter())
         .fold(G1Affine::identity(), |acc, (a_i, g_i)| {
             (acc + g_i * a_i).into()
         })
}

// e(C- yG1, G2) = e(H, \tau G2 - xG2)
pub fn verify(commit: G1Affine, y: Fr, proof: G1Affine, x: Fr, tau_g2: G2Affine) -> bool {
     let y_g1: G1Affine = (G1Affine::generator() * y).into();
     let lhs = Bn256::pairing(&(commit - y_g1).into(), &G2Affine::generator());

     let x_g2: G2Affine = (G2Affine::generator() * x).into();
     let rhs = Bn256::pairing(&proof, &(tau_g2 - x_g2).into());
     lhs == rhs
}

We first randomly generate a polynomial of degree 16, then generate the corresponding commitment and proof according to normal conditions and hack conditions, and print them out. Then use these data to create test in forge:

     function testNormal() external {
         mint.register(
             Pairing.G1Point(
                 0x0fa67f58acfdcf1b7b8529868df096fa97ce8a4147546b6c3f15a299b7484f76,
                 0x09b521d1fc0fb731d9522de51b8a1ea9aaa67ab863b6c3db9da0e2785af1d1a2
             ),
             Pairing.G1Point(
                 0x2b23e467ea98dcba7e033afc15697dfa4db2328c3f9d4fc112900687e9192fba,
                 0x0961852c4759acb47308d23ddd8b0f464848c54e5ab98f50f2a62cefc144c555
             ),
             Pairing.G1Point(
                 0x2bc5228f3e5e11ba4536ae9315811c424d9f7e5bbc3c3ab4124c9bf8492c9c16,
                0x1fac4e67bdcfd2b11d889fda0c9a99b6ceefbbe3acdcf7a2e418a6a68b7219ba
            )
        );

        (
            Pairing.G1Point[20] memory proofs,
            uint256[20] memory values
        ) = getData();

        for (uint i = 0; i < 16; i++) {
            mint.mint(proofs[i], values[i]);
        }

        vm.expectRevert("Soul dispersed");
        mint.mint(proofs[16], values[16]);

        assertFalse(mint.isSovled());
    }

    function testHack() external {
        mint.register(
            Pairing.G1Point(
                0x0fa67f58acfdcf1b7b8529868df096fa97ce8a4147546b6c3f15a299b7484f76,
                0x09b521d1fc0fb731d9522de51b8a1ea9aaa67ab863b6c3db9da0e2785af1d1a2
            ),
            Pairing.G1Point(
                0x0000000000000000000000000000000000000000000000000000000000000001,
                0x0000000000000000000000000000000000000000000000000000000000000002
            ),
            Pairing.G1Point(
                0x1820f5d55d603c14b534fff86db54c5fecfde13464ba660be352c3b6a87451c3,
                0x04fefd0113a6a5290731bacf1d9be2463c8d9290d34973e93ea596555fce41a6
            )
        );

        (
            Pairing.G1Point[20] memory proofs,
            uint256[20] memory values
        ) = getData();

        for (uint i = 0; i < 20; i++) {
            mint.mint(proofs[i], values[i]);
        }

        assertEq(mint.isSovled(), true);
    }

Finally, the hack is successful:

forge test -vvv
[⠢] Compiling...
[⠒] Compiling 2 files with 0.8.19
[⠢] Solc 0.8.19 finished in 1.81s
Compiler run successful!

Running 3 tests for test/MintNFT.t.sol:MintTest
[PASS] testEvaluateBarycentricPolynomial() (gas: 84270)
Logs:
  18569430475105882587588266137607568536673111973893317399460219858819262702947
  18569430475105882587588266137607568536673111973893317399460219858819262702947
  80084422859880547211683076133703299733277748156566366325829078699459944778998
  80084422859880547211683076133703299733277748156566366325829078699459944778998

[PASS] testHack() (gas: 6325794)
[PASS] testNormal() (gas: 4965218)
Test result: ok. 3 passed; 0 failed; 0 skipped; finished in 104.51ms
Ran 1 test suites: 3 tests passed, 0 failed, 0 skipped (3 total tests)

The complete source code is at https://github.com/flyq/Ethereal

中文版本

Ethreal 是一个 scalebit 主办的 zkctf 里面的一个 puzzle。这个题目当时我比较快的看懂了它的代码，但是却找不到它的漏洞，一直被卡着，最后也没解出来，因此在这里全面的总结一下。

这道题目的原题在 github 上，里面包含Solidity和Golang的代码。其中Solidity是题目，我们需要调用合约的 register 和 mint。golang 是辅助代码，帮助我们生成证明，调用合约。

问题是如果按照 Golang 里面的默认设置，我们只能 mint 9个，要最终解决题目，我们需要mint 20个。

先看一下合约逻辑：

Pairing.sol

实现了 BN254 椭圆曲线 G1 和 G2 相关的函数。
PRIME_Q:

$21888242871839275222246405745257275088696311157297823662689037894645226208583$ is the base field's Modulus.

G1Point:

$(x,y)$
G2Point:

$(x_i=x_0[i]\cdot z+x_1[i],y_i=y_0[i]\cdot z+y_1[i])$ 要注意扩域 z 的系数是 x_0
negate():

$-P$
plus():

$P_1+P_2$
mulScalar():

$s\cdot P$
pairing():

$e(A_1,-A_2)\cdot e(B_1,B_2)=1$ if

$e(A_1,A_2)=e(B_1,B_2)$

Constants.sol

给出了 srs，其中 prove key（G_1）有 17 个元素，verify key（G_2）有 2 个元素。

PRIME_Q:

$21888242871839275222246405745257275088696311157297823662689037894645226208583$
PRIME_R:

$21888242871839275222246405745257275088548364400416034343698204186575808495617$ is the scalar field's Modulus.
bn254_b_coeff:

$3$, used in

$Y^2=X^3+3$

SRS_G1_X[17], SRS_G1_Y[17],
SRS_G2_X_0[2], SRS_G2_X_1[2],
SRS_G2_Y_0[2], SRS_G2_Y_1[2],

SRS:

$(G_1,\tau \cdot G_1,{\tau }^2\cdot G_1,...{\tau }^{16}\cdot G_1,G_2,\tau \cdot G_2)$

KZGVerifier.sol

$G_1=\text{SRS\_G1\_0}$

$G_2=\text{g2Generator}$

$\tau G_2=\text{SRS\_G2\_1}$

• g1Check:
  $y_P=x_P^3+3$
• verify(_commitment,_proof,_index,_value):
  • check _commitment(
    $C$), _proof(
    $H$) in
    ${\mathbb{G}}_1$, _index(
    $i$), _value(
    $v$) in base field, 这里应该是题目的一个错误，这里应该是检查 i，v 位于 scalar field。
  • commitmentMinusA:
    $C-v\cdot G_1$
  • negProof:
    $-H$
  • indexMulProof:
    $i\cdot H$
  • check
    $e(iH+C-v{G}_1,G_2)=e(H,\tau G_2)$
  • 我们找到该pairing关系中对应的 scalar 元素的关系：
    $ih(\tau )+f(\tau )-v=h(\tau )\cdot \tau$。如果你对这一步不熟悉，可以参考 what is the KZG PCS。然后根据
    $v=f(i)$，
    $f(x)-f(i)=h(x)(x-i)$
• verifySoulBox:
  • check _commitment(
    $C$), _proof(
    $H$) in
    ${\mathbb{G}}_1$.
  • commitmentMinusA:
    $C-S$
  • negProof:
    $-P$
  • indexMulProof:
    $i\cdot H=0H=\mathcal{O}$
  • check
    $e(C-S,G_2)\cdot e(-H,\tau \cdot G_2)=1$
  • $C=S+\tau \cdot H$
• fr_inverse:
  $a^{-1}=a^{r-1}\mathrm{mod}r$,
  $r$ = PRIME_R
• fr_pow:
  $a^{\text{power}}\mathrm{mod}r$
• fr_div:
  $a/b\mathrm{mod}r$
• fr_mul_add:
  $a\cdot b+c\mathrm{mod}r$
• getBarycentricWeights and evaluateBarycentricPolynomial, use for evaluating the poly defined in xValues, yValues, and return
  $y=f(x)$

MintGem

    struct DepositInfo {
        bool registered;
        uint256 nonce;
        Pairing.G1Point commitment;
        Pairing.G1Point soulBox;
        uint256[] collectedY;
        bool escaped0;
        bool escaped1;
    }

• getCollectedY: return DepositInfo.collectedY
• register: _commitment(
  $C$), _proof(
  $H$), _soulBox(
  $S$)
  • check registered is false
  • check verifySoulBox(
    $C,H,S$)
  • new DepositInfo with
    $C,S$
• getNonce: nonce
• mint: _proof(
  $H$), _value(
  $v$)
  • check registered is true
  • check KZGVerifier.verify with （
    $C$,
    $H$, nonce,
    $v$）
  • collectedY.push(value)
  • calculate the polynomial
    $f(x)$ with lagrange interpolation in [(1, v1), (2, v2), (3, v3), ....]
  • calculate soul
    $s=f(0)$
  • soulBox(
    $S$):
    $S=s\cdot G_1$
  • require S.x != DepositInfo.soulBox.x

攻击原理

为什么我们无法 mint 超过多项式

$f(x)$ degree 的宝石？因为 n 次多项式我们只需要 (n+1) 个点就能恢复出多项式，最后导致 S.x ==DepositInfo.soulBox.x，即我们能够恢复出正确的

$f(0)$。而合约里面 SRS 只给出 17 个

$G1$ 点，我们的多项式的 degree 最多为 16.

攻击手段：

1. 假设我们要攻击 KZGVerifier.verify：
   $f(i)G_1=C+iH-\tau H$，其中
   $f(i)$(即参数 value)，
   $H$(即参数 proof) 是我们能够决定的输入。
   $H=\frac{f(i)G_1-C}{i-\tau }$ we can set any
   $f(i)$ and find the corresponding
   $H$ if we know the
   $\tau$，如果我们随机生成一个错误的
   $f(i)$, 则永远无法恢复出正确的
   $f(0)$，然后我们可以无限 mint。实际上这就是第一名获得者的方法。他通过搜索 GitHub，在某些 ZK 项目方的测试代码里面找到了
   $\tau$。
2. 假设我们要攻击 KZGVerifier.verifySoulBox:
   $S=C-\tau H$，其中
   $C$(即参数 _commitment)，
   $H$(即参数 _proof)，
   $S$(即参数 _soulBox)，我们都可以决定。
   $C$ 应该只能输入正确的承诺，因为会影响后面的 pairing 的验证。然后即使我们不知道
   $\tau$，我们可以构造
   $H=G_1$,
   $S=C-\tau G_1$ 来通过 verifySoulBox 的验证，因为
   $\tau G_1$ 就是 srs 的第二个点！个人更喜欢这个方法，适用范围更广。第二名就是使用这个方法，并且明确说明该漏洞是合约没有验证调用者是否拥有
   $S$ 的离散对数的知识，即
   $S=s{G}_1$，合约没有检查调用者是否知道
   $s$。第三位也是使用该方法，并且在他引用的文章中指出该方案可以用于 RLN(Rate-Limiting Nullifier)，相比 zksnark 方案更高效（1ms vs 1s）。而且他引用的另外一篇文章详细描述该漏洞。

PoC

我们基于第二个攻击手段，使用 Rust 和 Foundry 来复现整个攻击过程。
假设

$(x_0,y_0)$ 在

$f(x)$ 上，则我们可以根据

$x_0$ 以及

$f(x)$ 的系数求出

$h(x)$ 的系数。（为什么这里这么搞，因为我使用的是 halo2curve 里面的 bn256 mod (即前文中的 bn254 曲线)，它并没有原生的多项式承诺的实现，因此需要手动写，如果使用 arkworks，可能方便点：

• f.len() = n -> f.degree = n-1
• $f(x)=a_{n-1}{x}^{n-1}+a_{n-2}{x}^{n-2}+\cdots +a_{1}x+a_0$
• $\begin{array}{rl}h(x)& =\frac{f(x)-y_0}{x-x_0}\\ & =(a_{n-1}{x}^{n-1}-a_{n-1}{x}_0{x}^{n-2}+a_{n-1}{x}_0{x}^{n-2}+a_{n-2}{x}^{n-2}+\cdots +a_0-y_0)/(x-x_0)\\ & =(a_{n-1}{x}^{n-2}(x-x_0)+(a_{n-1}{x}_0+a_{n-2})x^{n-2}+\cdots +a_0-y_0)/(x-x_0)\\ & =a_{n-1}{x}^{n-2}+((a_{n-1}{x}_0+a_{n-2})x^{n-2}+\cdots +a_0-y_0)/(x-x_0)\\ & =a_{n-1}{x}^{n-2}+((a_{n-1}{x}_0+a_{n-2})x^{n-2}-(a_{n-1}{x}_0+a_{n-2})x_0{x}^{n-3}+(a_{n-1}{x}_0+a_{n-2})x_0{x}^{n-3}+a_{n-3}{x}^{n-3}+\cdots +a_0-y_0)/(x-x_0)\\ & =a_{n-1}{x}^{n-2}+(a_{n-1}{x}_0+a_{n-2})x^{n-3}+((a_{n-1}{x}_0+a_{n-2})x_0{x}^{n-3}+a_{n-3}{x}^{n-3}+\cdots +a_0-y_0)/(x-x_0)\\ & =a_{n-1}{x}^{n-2}+(a_{n-1}{x}_0+a_{n-2})x^{n-3}+((a_{n-1}{x}_0+a_{n-2})x_0+a_{n-3})x^{n-4}+(((a_{n-1}{x}_0+a_{n-2})x_0+a_{n-3})x_0+a_{n-4})x^{n-5}\end{array}$
• $h(x)=b_{n-1}{x}^{n-2}+b_{n-2}{x}^{n-3}+\cdots +b_{2}x+b_1+\frac{b_0}{x-x_0}$
• $b_{n-1}=a_{n-1}$
• $b_{n-2}=a_{n-1}{x}_0+a_{n-2}$
• $b_{n-3}=a_{n-1}{x}_0^2+a_{n-2}{x}_0+a_{n-3}$
• $b_{n-4}=a_{n-1}{x}_0^3+a_{n-2}{x}_0^2+a_{n-3}{x}_0+a_{n-4}$
• $b_1=a_{n-1}{x}_0^{n-2}+a_{n-2}{x}_0^{n-3}+a_{n-3}{x}_0^{n-4}+a_{n-4}{x}_0^{n-5}+\cdots +a_1$
• $b_0=0$

我们用 sage 验证一下，并通过验证：

r = 21888242871839275222246405745257275088548364400416034343698204186575808495617
Fr = GF(r)

R.<x> = PolynomialRing(Fr, 'x')
points = [(1,3),(3,7),(19,23), (20, 24)]
f = R.lagrange_polynomial(points)
# 19520216596230932581243139626618330122828219713821317177859509581595384769483*x^3 + 11904132088193290033151554001806588206052619235313983590432356662874562515160*x^2 + 5056056101974569422682649280337206818699768384891423137871807399823066874721*x + 7296080957279758407415468581752425029516121466805344781232734728858602831873

p = (f-23)/(x-19)
# 19520216596230932581243139626618330122828219713821317177859509581595384769483*x^2 + 10688118595313330298582309238181184034466598990846426126893567541398128709848*x + 11136123566374368095528873098464227676629869607229210455565753007205235901280

Fr(19520216596230932581243139626618330122828219713821317177859509581595384769483)*Fr(19) + Fr(11904132088193290033151554001806588206052619235313983590432356662874562515160)
# 10688118595313330298582309238181184034466598990846426126893567541398128709848

Fr(19520216596230932581243139626618330122828219713821317177859509581595384769483)*Fr(19)*Fr(19) + Fr(11904132088193290033151554001806588206052619235313983590432356662874562515160)*Fr(19) + 5056056101974569422682649280337206818699768384891423137871807399823066874721
# 11136123566374368095528873098464227676629869607229210455565753007205235901280

然后使用 rust 来生成证明等：

// f(x) = a_0 + a_1 x + a_2 x^2 + ...
// y = f(x)
// h(x) = (f(x) - y_0) / (x - x_0)
// H = h(\tau) * G
pub fn open(f: &[Fr], x: Fr, srs: &[G1Affine]) -> (Fr, G1Affine) {
    let mut y = Fr::zero();
    let mut x_pow = Fr::one();
    for a in f.iter() {
        y += x_pow * a;
        x_pow *= x;
    }
    let mut h = vec![Fr::zero(); f.len() - 1];
    let len = h.len();
    for (i, a) in f.iter().skip(1).rev().enumerate() {
        if i == 0 {
            h[len - 1 - i] = *a;
        } else {
            h[len - 1 - i] = h[len - i] * x + a;
        }
    }

    let proof = h
        .iter()
        .zip(srs.iter())
        .fold(G1Affine::identity(), |acc, (a_i, g_i)| {
            (acc + g_i * a_i).into()
        });

    (y, proof)
}

pub fn commit(f: &[Fr], srs: &[G1Affine]) -> G1Affine {
    f.iter()
        .zip(srs.iter())
        .fold(G1Affine::identity(), |acc, (a_i, g_i)| {
            (acc + g_i * a_i).into()
        })
}

// e(C- yG1, G2) = e(H, \tau G2 - xG2)
pub fn verify(commit: G1Affine, y: Fr, proof: G1Affine, x: Fr, tau_g2: G2Affine) -> bool {
    let y_g1: G1Affine = (G1Affine::generator() * y).into();
    let lhs = Bn256::pairing(&(commit - y_g1).into(), &G2Affine::generator());

    let x_g2: G2Affine = (G2Affine::generator() * x).into();
    let rhs = Bn256::pairing(&proof, &(tau_g2 - x_g2).into());
    lhs == rhs
}

我们先随机生成 16 次多项式，然后按照正常情况以及hack情况生成对应的commitment 以及 proof 等，并打印出来。然后在 forge 里面使用这些数据建立 test:

    function testNormal() external {
        mint.register(
            Pairing.G1Point(
                0x0fa67f58acfdcf1b7b8529868df096fa97ce8a4147546b6c3f15a299b7484f76,
                0x09b521d1fc0fb731d9522de51b8a1ea9aaa67ab863b6c3db9da0e2785af1d1a2
            ),
            Pairing.G1Point(
                0x2b23e467ea98dcba7e033afc15697dfa4db2328c3f9d4fc112900687e9192fba,
                0x0961852c4759acb47308d23ddd8b0f464848c54e5ab98f50f2a62cefc144c555
            ),
            Pairing.G1Point(
                0x2bc5228f3e5e11ba4536ae9315811c424d9f7e5bbc3c3ab4124c9bf8492c9c16,
                0x1fac4e67bdcfd2b11d889fda0c9a99b6ceefbbe3acdcf7a2e418a6a68b7219ba
            )
        );

        (
            Pairing.G1Point[20] memory proofs,
            uint256[20] memory values
        ) = getData();

        for (uint i = 0; i < 16; i++) {
            mint.mint(proofs[i], values[i]);
        }

        vm.expectRevert("Soul dispersed");
        mint.mint(proofs[16], values[16]);

        assertFalse(mint.isSovled());
    }

    function testHack() external {
        mint.register(
            Pairing.G1Point(
                0x0fa67f58acfdcf1b7b8529868df096fa97ce8a4147546b6c3f15a299b7484f76,
                0x09b521d1fc0fb731d9522de51b8a1ea9aaa67ab863b6c3db9da0e2785af1d1a2
            ),
            Pairing.G1Point(
                0x0000000000000000000000000000000000000000000000000000000000000001,
                0x0000000000000000000000000000000000000000000000000000000000000002
            ),
            Pairing.G1Point(
                0x1820f5d55d603c14b534fff86db54c5fecfde13464ba660be352c3b6a87451c3,
                0x04fefd0113a6a5290731bacf1d9be2463c8d9290d34973e93ea596555fce41a6
            )
        );

        (
            Pairing.G1Point[20] memory proofs,
            uint256[20] memory values
        ) = getData();

        for (uint i = 0; i < 20; i++) {
            mint.mint(proofs[i], values[i]);
        }

        assertEq(mint.isSovled(), true);
    }

最后，成功hack成功：

forge test -vvv
[⠢] Compiling...
[⠒] Compiling 2 files with 0.8.19
[⠢] Solc 0.8.19 finished in 1.81s
Compiler run successful!

Running 3 tests for test/MintNFT.t.sol:MintTest
[PASS] testEvaluateBarycentricPolynomial() (gas: 84270)
Logs:
  18569430475105882587588266137607568536673111973893317399460219858819262702947
  18569430475105882587588266137607568536673111973893317399460219858819262702947
  80084422859880547211683076133703299733277748156566366325829078699459944778998
  80084422859880547211683076133703299733277748156566366325829078699459944778998

[PASS] testHack() (gas: 6325794)
[PASS] testNormal() (gas: 4965218)
Test result: ok. 3 passed; 0 failed; 0 skipped; finished in 104.51ms
Ran 1 test suites: 3 tests passed, 0 failed, 0 skipped (3 total tests)

完整源码在 https://github.com/flyq/Ethereal