Add a number of bits in the modulus builtin function

[kevaundray]

Problem

Some applications may require knowledge of the number of bits in the modulus, which is known by the compiler.

Solution

Use a builtin attribute to expose the number of bits in the modulus. We can also expose the modulus as a byte array.

Alternatives considered

(Describe any alternative solutions you have considered.)

Additional context

(If applicable.)

[vezenovm]

Do you think it would be better to expose the modulus as a byte array or an array of u64? The modulus for ark_bn254::Fr is represented as four u64s in the arkworks crate, so some people might want to reason about it this way. I could expose both modulus_byte_array and modulus_u64_array as well.

This is another place where a big int impl native to Noir would be helpful. We could just have a modulus() builtin method that returns a BigInt and then on that big int we have utility methods that allow for to_bytes_le, to_byte_be, to_u64_digits, etc. Similar to what we have for fields.

[kevaundray]

For the original issue, I think a modulus_bits method would solve it sufficiently.

I'd prefer modulus_be_byte_array , mainly because the 4 u64s is an implementation detail of arkworks, so 8 u32s would also not be bad or 2 u128s if that type is supported by the programming language.

Looking at it again, getting the number of bits from the modulus byte array seems pretty cumbersome, so perhaps we should have both modulus_bits and modulus_be_byte_array, what do you think?

A bigint package seems like a good idea, perhaps we could put it into ACIR since the partial witness generator also requires BigInt and it could be re-exported. This requires another issue though for discussion methinks.

[vezenovm]

Looking at it again, getting the number of bits from the modulus byte array seems pretty cumbersome, so perhaps we should have both modulus_bits and modulus_be_byte_array, what do you think?

This is good in my opinion. I originally did make a modulus_bits method as fetching the number of bits from the byte array seemed inefficient. I then was going to make a modulus_byte_array method and realized that there are many potential alternatives. Perhaps for now, a single method modulus_be_byte_array would be good. We can then reassess if applications require the modulus in a different form and/or when we create a native bigint package.

[vezenovm]

One point of clarification. If you look at PR #697, I made modulus_bits just return the number of bits in the modulus as per the issue description rather than a bit array of the modulus itself. By modulus_bits did you mean a bit array of the modulus? Users can then fetch the size of the modulus in bits by taking the array len of this bit array.

[vezenovm]

Users can then fetch the size of the modulus in bits by taking the array len of this bit array

This actually is not possible yet as we do not have fully working slices. modulus_bits must return a [u1] as we can have different sized fields. This will panic when evaluating the arraylen builtin as the NamedGeneric will be unbound. I think this can be changed once we have numeric generics and/or true slices implemented (#606).

[jfecher]

If the number of elements returned is truly unknown then we'd need true slices. I'm assuming though that it'd be known based on the the number of bits in the input type, in which case it'd be comptime. We could likely make it work in that case with a special check.

[vezenovm]

I'm assuming though that it'd be known based on the the number of bits in the input type, in which case it'd be comptime. We could likely make it work in that case with a special check.

Do you mean known when the modulus bits array is passed to std::array:len? I want to be able to do the below.

#[builtin(modulus_be_bits)]
fn modulus_be_bits() -> [u1] {}

fn modulus_num_bits() -> comptime Field {
   let bits = modulus_be_bits();
   std::array::len(bits)
}