Skip to content

Proofs with Bad Scalar format in MSM #137

@Hakkush-07

Description

@Hakkush-07

What does not work: Groth16 verifier for some proofs (native, hinted, chunked), namely for proofs with a bad public input.

Bad Scalar: If the 12-bit chunk representation of a scalar (public input) contains a 0 (zero) chunk, it fails. For example, that includes small public inputs starting with a few zero bits.

The Reason: The functions calculating alpha and bias, affine_double_line_coeff and affine_add_line_coeff, work with non-infinity curve points. However, infinity points are provided as inputs to these function in case of a bad scalar.

Affine curve points have x and y coordinates. Infinity should also have a representation, and it is given (x, y) = (0, 0), which does not actually correspond to a valid point.

  • affine_add_line_coeff(infinity, infinity): attempts to divide by 0, fails at script generation stage.
  • affine_add_line_coeff(infinity, a): works but gives wrong results because of the incorrect numerical representation of infinity. Script is generated, but fails with correct inputs.
  • affine_double_line_coeff(infinity): attempts to add infinity to infinity, fails at script generation stage.

A Possible Solution: Adding if checks to both rust calculation part and scripts.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions