Add support for custom BigInt Moduli

[michaelelliot]

I’ve been using the new BigInt feature in Noir, and was able to decrypt an RSA signature using a 2048 bit modulus.

However, while it successfully decrypted the RSA signature (confirmed via println), it also produced the error: The backend encountered an error: Assertion failed. See bigint_constraint.cpp#L360

Currently the barretenberg backend only supports 6 different moduli for foreign field arithmetic, and so although it appeared to work, this couldn't be used for creating actual proofs with constraints.

The current approach works well for BN254, ECDSA, EdDSA and other signature algorithms/curves with a fixed modulus, but not so much for non-curve algorithms like RSA, where the modulus changes with each keypair.

Some questions:

• Is it possible to add support for arbitrary moduli, specifiable in Noir, or does each modulus need to be hardcoded into the backend prover?
• Is it possible to use a foreign field size that's larger than the native field size in foreign field arithmetic?
• Is it possible to add support for a larger modulus (e.g. 512 bits) by using more 64bit limbs? See bigint_constraint.cpp#L309 (Or would this be restricted by the BN254 native field size?)

Related:

• Differentiate bigint structures per moduli
• Add big integer opcode #4040
• feat!: Add big int opcodes (without implementation) AztecProtocol/aztec-packages#4050
• feat: implement bigint in Noir, using bigint opcodes AztecProtocol/aztec-packages#4198
• chore: add bigint solver in ACVM and add a unit test for bigints in Noir AztecProtocol/aztec-packages#4415

[signorecello]

Seems like this won't happen after all @Savio-Sou ? This seems critical for RSA thus passport verification, zkEmail, and some other things (cc @joeandrews)

[Savio-Sou]

We closed #5327 due to Barretenberg team's concern on merging the PR.

Meanwhile, we've come up with a design spec that should be implementable in pure Noir.

We're looking for a community team to implement the specs and maintain the library. (Readers interested, do reach out.)

[Savio-Sou]

That said, this Issue is no longer relevant to live in this repository as the aim shifts towards a standalone BigUInt library implementing the specs linked above.

Closing this as not planned accordingly.