Internal Consistency Evaluators Errors using BigInt ops

[MatteoMer]

Aim

I'm working on implementing a square and multiply algorithm using BigInt.

I am using the same structure as the fields implemented in the stdlib by implementing the BigField trait and also Add,Sub,Mul,Div,Eq ops traits.

My implementation is like this (it's a bit hacky but should work I think)

fn mod_pow(self, exponent: PrimeField) -> PrimeField {
        let mut result = PrimeField::one(); // Initialize result as 1 within the modulus field
        let mut base = PrimeField::from_le_bytes(self.to_le_bytes());
        let two = PrimeField::from_le_bytes([2].as_slice()); // Used to check if exponent is odd

        // Prepare the exponent for iteration
        let exp_bytes = exponent.to_le_bytes();
        let mut exp = PrimeField::from_le_bytes(exp_bytes);

        for _ in 0..256 {
            // Hack to find if the number is odd since we don't have the modulo operator available 
            if (exp/two) * two != exp {
                result = result * base;
            }

            // Square the base in every loop iteration
            base = base * base;

            exp = exp / two;
        }

        result
    }

I'm running this test

#[test]
fn test_mod_pow() {
    let two = PrimeField::from_le_bytes([2].as_slice());
    let three = PrimeField::from_le_bytes([3].as_slice());
    let eight = PrimeField::from_le_bytes([8].as_slice());

    assert(two + PrimeField::one() == three);

    let two_pow_three = two.mod_pow(three);
    assert_eq(two_pow_three, eight);
}

I'm wondering if it's because the BigInt are mutable?

Expected Behavior

In the best case: It should run my test and work or at least give a proper error (the error today tells me to open an issue!)

Bug

It crashes with this error message:

[stark_verifier_noir] Testing field::test_mod_pow... error: Internal Consistency Evaluators Errors:

                    This is likely a bug. Consider opening an issue at https://github.com/noir-lang/noir/issues
  ┌─ /Users/matteo/projects/stark-verifier-noir/src/field.nr:1:1
  │
1 │ use dep::std::bigint::{BigInt, BigField};
  │ - ICE: "big integer" should be a constant
  │
  = Call stack:
    1. /Users/matteo/projects/stark-verifier-noir/src/field.nr:111:25
    2. /Users/matteo/projects/stark-verifier-noir/src/field.nr:54:26
    3. /Users/matteo/projects/stark-verifier-noir/src/field.nr:85:20

For information:

• line 111 is the test: let two_pow_three = two.mod_pow(three);
• line 54 is result = result * base;
• line 85 is the Mul ops: inner: self.inner.bigint_mul(other.inner)

To Reproduce

Not sure, will investigate more but I think it happens when a mutable BigInt is passed as an argument to the blackbox function

1. Create two mutables BigInt
2. Try to use bigint_mul on them?

Project Impact

Blocker

Impact Context

I would say it's a blocker because I can't really integrate an easy version of the square and multiply algorithm, which would be handy to have to implement more complex algorithm.

I think in general, it's necessary to have a better clarity on the error message, so people don't get stuck too long on this!

Workaround

None

Workaround Description

No response

Additional Context

No response

Installation Method

Binary (noirup default)

Nargo Version

nargo version = 0.26.0 noirc version = 0.26.0+a0f7474ae6bd74132efdb945d2eb2383f3913cce (git version hash: a0f7474, is dirty: false)

NoirJS Version

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response

[MatteoMer]

btw, if you guys know what to do/where to look but don't have much time, I would happy to send a PR with a bit of guidance!

[vezenovm]

@MatteoMer Could you provide a reproduction with the PrimeField implementation? Or a smaller example? It makes it easier for us to debug. Otherwise to reproduce we have to rewrite your program using one of our types that implements the BigField trait.

[vezenovm]

@guipublic This looks to be because we return witnesses from the blackbox for BigIntToLeBytes. So this code:

       // Prepare the exponent for iteration
       let exp_bytes = exponent.to_le_bytes();
       let mut exp = PrimeField::from_le_bytes(exp_bytes);

would give an internal error. I switched it to just the following but am still getting an error about big integer inputs not being a constant when attempting to convert a big integer to bytes for the assert_eq check.

        let mut exp = exponent;
        if (exp/two) * two != exp {
            result = result * base;
        }

[MatteoMer]

Hey @vezenovm , sure! here's my entire file

use dep::std::bigint::{BigInt, BigField};
use dep::std::ops::{Add, Sub, Mul, Div};
use dep::std::cmp::Eq;

global MODULUS = [1, 0, 0, 0, 161, 254, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255].as_slice();

struct PrimeField {
    inner: BigInt,
}

trait PrimeFieldTrait {
    fn zero() -> Self;
    fn one() -> Self;
    fn mod_pow(self, other: Self) -> Self;
}

impl BigField for PrimeField {
    fn from_le_bytes(bytes: [u8]) -> PrimeField {
        PrimeField {
            inner: BigInt::from_le_bytes(bytes, MODULUS)
        }
    }
    fn to_le_bytes(self) -> [u8] {
        self.inner.to_le_bytes()
    }
    
}

impl PrimeFieldTrait for PrimeField {
    fn zero() -> PrimeField {
        PrimeField {
            inner: BigInt::from_le_bytes([0].as_slice(), MODULUS)
        }
    }

    fn one() -> PrimeField {
        PrimeField {
            inner: BigInt::from_le_bytes([1].as_slice(), MODULUS)
        }
    }

    fn mod_pow(self, exponent: PrimeField) -> PrimeField {
        let mut result = PrimeField::one(); // Initialize result as 1 within the modulus field
        let mut base = PrimeField::from_le_bytes(self.to_le_bytes());
        let two = PrimeField::from_le_bytes([2].as_slice()); // Used to check if exponent is odd

        // Prepare the exponent for iteration
        let exp_bytes = exponent.to_le_bytes();
        let mut exp = PrimeField::from_le_bytes(exp_bytes);

        for _ in 0..256 {
            // If the current least significant bit of exp is 1, multiply the result by the base
            if (exp/two) * two != exp {
                result = result * base;
            }

            // Square the base in every loop iteration
            base = base * base;

            // Right shift the exponent by 1 (equivalent to dividing by 2 in this context)
            exp = exp / two;
        }

        result
    }
}

impl Add for PrimeField { 
    fn add(self: Self, other: PrimeField) -> PrimeField {
        PrimeField {
            inner: self.inner.bigint_add(other.inner)
        }
    }
}
impl Sub for PrimeField { 
    fn sub(self: Self, other: PrimeField) -> PrimeField {
        PrimeField {
            inner: self.inner.bigint_sub(other.inner)
        }
    }
}
impl Mul for PrimeField { 
    fn mul(self: Self, other: PrimeField) -> PrimeField {
        PrimeField {
            inner: self.inner.bigint_mul(other.inner)
        }

    }
}
impl Div for PrimeField { 
    fn div(self: Self, other: PrimeField) -> PrimeField {
        PrimeField {
            inner: self.inner.bigint_div(other.inner)
        }
    }
}
impl Eq for PrimeField {
    fn eq(self: Self, other: PrimeField) -> bool {
        self.inner.check_32_bytes(other.inner)
    }
}

#[test]
fn test_mod_pow() {
    let two = PrimeField::from_le_bytes([2].as_slice());
    let three = PrimeField::from_le_bytes([3].as_slice());
    let eight = PrimeField::from_le_bytes([8].as_slice());

    assert(two + PrimeField::one() == three);

    let two_pow_three = two.mod_pow(three);
    assert_eq(two_pow_three, eight);
}