Improve Carry Handling of BigInt and Field Arithmetic

[moven0831]

Description

• During Refactor Metal EC Backend #20 , it has been observed that the current implementation inadequately handles basic BigInt and Field arithmetic operations. This sub-issue aims to identify and resolve these shortcomings to ensure robust and accurate arithmetic processing within the EC backend.

Problems Identified

• BigInt Arithmetic:

  • Addition & Subtraction: Inconsistent handling of carry-over and borrow across arbitrary limb sizes.
  • Multiplication: Inefficient algorithms leading to performance bottlenecks for large numbers.
  • Division: Limited support for division operations, especially with varying limb sizes.

• Field Arithmetic:

  • Addition & Subtraction: Incorrect handling when results exceed or fall below the field boundaries.
  • Modular Reduction: Inadequate implementation causing results to sometimes lie outside the defined field.
  • Overflow Handling: Lack of mechanisms to manage arithmetic operations that exceed field limits.

Goals

1. Enhance BigInt Operations:

   • Implement reliable addition and subtraction methods that correctly manage carry-over and borrowing for arbitrary limb sizes.
   • Optimize multiplication algorithms to improve performance for large BigInt values.
   • Develop comprehensive division functionalities supporting various limb sizes.

2. Strengthen Field Operations:

   • Ensure addition and subtraction operations correctly handle cases where results exceed field boundaries by implementing proper modular reduction.
   • Refine modular reduction techniques to guarantee all results remain within the defined field.
   • Introduce overflow handling mechanisms to manage arithmetic operations exceeding field limits gracefully.

3. Testing & Validation:

   • Create extensive test suites covering a wide range of scenarios for both BigInt and Field operations, including edge cases.
   • Validate the correctness and performance of the improved arithmetic operations through benchmarking and testing.

Acceptance Criteria

• Functionality:

  • All BigInt arithmetic operations (addition, subtraction, multiplication, division) function correctly across various limb sizes.
  • All Field arithmetic operations maintain results within the defined field boundaries under all tested scenarios.

• Testing:

  • Comprehensive test suites pass without errors, covering typical and edge-case scenarios for both BigInt and Field operations.

References

• main issue: Refactor Metal EC Backend #20
• https://github.com/geometryxyz/msl-secp256k1

[moven0831]

Proposed Comment Update:

• Fix ff.metal and refactor rust test #29
• Test/metal/bigint #26

I've traced the discrepancy in addition results to how carries are handled in the GPU’s bigint_add_wide() function. Specifically, it stores the carry in the most significant limb, causing a mismatch with Arkworks’s field arithmetic behavior.

• When $a + b > p$, the Metal side computation matches Arkworks as expected.
• When $a + b \le p$, the Metal function sets the carry incorrectly, requiring an additional modular adjustment on the CPU side.

Since the bigint_add_wide() function in mopro-msm/src/msm/metal_msm/shader/bigint/bigint.metal records the carry incorrectly in the MSB:

result.limbs[NUM_LIMBS] = carry;  // this records carry in MSB

This behavior leads to mismatched results during field arithmetic when a + b <= p.

Switching to bigint_add_unsafe (which aligns more closely with Arkworks’s implementation) fixes the issue and ensures consistent results across both CPU and GPU paths.