Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Issue in g1_powers_check rust implementation #158

Open
asanso opened this issue Dec 13, 2022 · 2 comments
Open

Issue in g1_powers_check rust implementation #158

asanso opened this issue Dec 13, 2022 · 2 comments

Comments

@asanso
Copy link

asanso commented Dec 13, 2022

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
Copy link
Collaborator

kustosz commented Dec 13, 2022

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
Copy link
Author

asanso commented Dec 13, 2022

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants