Skip to content

BN254 MSM does not crash with (0, 0) for Standard and Turbo Composers #188

Open
@suyash67

Description

@suyash67

In the recursive verification circuit, we aggregate the proof verification by computing $P_0, P_1$. To compute $P_0$, we perform the BN254 MSM operation on a vector of group elements and scalars inside the circuit using the function bn254_endo_batch_mul_with_generator .

auto opening_result = g1_ct::template bn254_endo_batch_mul_with_generator(
big_opening_elements, big_opening_scalars, opening_elements, opening_scalars, batch_opening_scalar, 128);
opening_result = opening_result + double_opening_result;
for (const auto& to_add : elements_to_add) {
opening_result = opening_result + to_add;
}
opening_result = opening_result.normalize();

Similarly, the MSM to compute $P_1$ uses the function wnaf_batch_mul.

g1_ct rhs = g1_ct::template wnaf_batch_mul<128>(rhs_elements, rhs_scalars);
rhs = rhs + PI_Z;
rhs = (-rhs).normalize();

But the problem is: if any of the elements in the rhs_elements contain $(0,0)$ as its $x,y$-coordinate (btw $(0,0)$ isn't point on the curve) then the composer should catch that and throw an error. Ideally, there should be an assertion failure in the division function msub_div in the bigfield module. This doesn't happen when using Standard or Turbo composers. It fails at the correct assertion when using Ultraplonk though.

I wrote a quick test to confirm this is a problem with the MSM operation in the circuit. This only tests wnaf_batch_mul function.

HEAVY_TYPED_TEST(stdlib_biggroup, wnaf_batch_mul_bug)
{
// This test should fail for turbo and standard but it doesn't.
if constexpr (TypeParam::use_bigfield) {
GTEST_SKIP();
} else {
TestFixture::test_wnaf_batch_mul_bug();
}
}

Questions:

  1. Is this the expected behaviour or are we missing some checks?
  2. Is this a problem because we don't allow overflows while constructing fq_ct points?

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions