ethereum / kzg-ceremony-sequencer

MIT License
83 stars 27 forks source link

Issue in `g1_powers_check` rust implementation #158

Open asanso opened 1 year ago

asanso commented 1 year ago

The pairing equality called as part of test_verify_g1 should fail but this is not the case. The reason behind it is a bit "subtle" see below:

The test:

    #[test]
    fn test_verify_g1() {
        let powers = [rand_g1().into()];
        let tau = rand_g2().into();
        let _ = BLST::verify_g1(&powers, tau);
    }

samples two random elements in G1 and G2 having two different $\tau$: $\tau_1G1$ and $\tau_2G2$ so, as said, the pairing check is supposed to fail. Both the implementations of verify_g1(BLST and Arkworks) used the Vitalik's batch optimization for Fast verification of multiple BLS signatures. With a furher optimization (due the fact the second input of the pairing is always the same). Looking at the BLST implementation of verify_g1:

   fn verify_g1(powers: &[crate::G1], tau: crate::G2) -> Result<(), crate::CeremonyError> {
        // Parse ZCash format
        let powers = powers
            .into_par_iter()
            .map(|p| blst_p1_affine::try_from(*p))
            .collect::<Result<Vec<_>, _>>()?;
        let tau = blst_p2_affine::try_from(tau)?;
        let tau = p2_from_affine(&tau);

        // Compute random linear combination
        let (factors, sum) = random_factors(powers.len() - 1);
        let g2 = unsafe { *blst_p2_generator() };

        let lhs_g1 = p1s_mult_pippenger(&powers[1..], &factors[..]);
        let lhs_g2 = p2_to_affine(&p2_mult(&g2, &sum));

        let rhs_g1 = p1s_mult_pippenger(&powers[..factors.len()], &factors[..]);
        let rhs_g2 = p2_to_affine(&p2_mult(&tau, &sum));

        // Check pairing
        if pairing(&lhs_g1, &lhs_g2) != pairing(&rhs_g1, &rhs_g2) {
            return Err(CeremonyError::G1PairingFailed);
        }

        Ok(())
    }

we note that powers.len() = 1 so:

  1. When let (factors, sum) = random_factors(powers.len() - 1); is called sum is equal to 0
  2. Due a peculiar choice of p1s_mult_pippenger
    if bases.is_empty() {
        // NOTE: Without this special case the `blst_p1s_mult_pippenger` will
        // SIGSEGV.
        return blst_p1_affine::default();
    }

the G1 generator is returned.

The pairing equality than becomes:

$e(g_1, 0) \stackrel{?}{=} (g_1, 0)$

kustosz commented 1 year ago

Powers arrays of length one is a verifiably illegal state of this sequencer, so this not a security concern for this particular service. That being said, in the interest of this code being potentially reusable for other purposes, a PR with a fix is welcome :).

asanso commented 1 year ago

I am aware the length of the array used in the Ethereum PoT is way bigger .