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

bug: omitted automatic reductions for Div, Inverse and Sqrt in field emulation #867

Closed
ivokub opened this issue Oct 17, 2023 · 0 comments · Fixed by #870
Closed

bug: omitted automatic reductions for Div, Inverse and Sqrt in field emulation #867

ivokub opened this issue Oct 17, 2023 · 0 comments · Fixed by #870
Assignees
Labels
bug Something isn't working P1: High Issue priority: high

Comments

@ivokub
Copy link
Collaborator

ivokub commented Oct 17, 2023

There was an edge case in #866 which is due to not automatically reducing before division operation.

Description

We keep track of the overflows and usually reduce before the overflow of the result would overflow the scalar field. But division does many things internally:

  1. result using hint
  2. multiplication of the result and divisor
  3. equality check of previous and dividend

The problem appears in step 3 - the overflow of of the result is already 189, but inside equality check we have to add the subtraction padding, adding two bits of overflow, so we are at 191 bits. But this is overflow only, so the whole limb is on 255 bits, which is the same than bls12-381 scalar field modulus width. We get a scalar field overflow and nothing works anymore.

The issue has always been around, it only appears more clearly when we have a lot of limbs because right now the multiplication overflow (step 2) depends on the number of limbs. And in #866 unreduced values have 37+ limbs, so overflow grows very quickly.

Expected Behavior

We check if all the intermediate values do not overflow the scalar field.

Possible Fix

Use the auto-reduce machinery for division. The issue also appears for Sqrt and Inverse, so should also add auto-reduce for those methods.

@ivokub ivokub added bug Something isn't working P1: High Issue priority: high labels Oct 17, 2023
@ivokub ivokub self-assigned this Oct 17, 2023
@yelhousni yelhousni mentioned this issue Oct 17, 2023
9 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working P1: High Issue priority: high
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant