Epic: Big Integers

[guipublic]

Problem

In noir, the size of integers types are restricted to half of the field modulus. However to implement cryptographic schemes, for instance those based on EC operations, we need to support integers with bigger size.

Solution

Usual techniques for big integers consists into representing the big integers with smaller limbs, to use non-determinism to compute the result of an operation (+,*,-..) and to add constraints asserting the result is valid.
The solution described here suggest some efficient constraints to check the result: https://blog.polygon.technology/wp-content/uploads/2022/10/casting-3.pdf

Tasks

Beta Give feedback

1. Add big integer opcode #4040
   enhancement +1
   
2. Differentiate bigint structures per moduli #4257
   enhancement +1
   
3. Document BigInt struct #4205
   documentation +1
   
4. feat: Add support for uint256 to DSL bigint AztecProtocol/aztec-packages#5327
   +0
5. Add support for custom BigInt Moduli AztecProtocol/aztec-packages#4676
   C-barretenberg +1
6. Add support for custom modulus in the bigint opcode #4404
   enhancement +1

Alternatives considered

We should check whether or not it would be easy/efficient to implement big integers using a noir implementation, although I believe having big integers as a native noir type does make sense considering how useful it is.
It could be also interesting to see how big integers are implemented in Barretenberg

[michaelneuder]

Agreed that this would be very useful! For a noir implementation of sha256, for example, having a u512 would be important because each chunk of the message is processed in 512 bit pieces. I tried using u512 only to realize that that size of integer is not supported: https://github.com/michaelneuder/crypto-primitives/blob/14ff0241182a7fac84c5e66ad4ddc8e75182b7bc/sha256/sha256/src/main.nr#L10.

[okuyiga]

I'm working on an implementation of this here https://github.com/okuyiga/noir-mul-mod-non-determinstic

[Savio-Sou]

Update:
AztecProtocol/aztec-packages#5327 was closed 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 and maintain it accordingly; if you reader are interested, do reach out.

[Savio-Sou]

This Epic in this repository is therefore no longer relevant, as the aim has shifted towards a standalone BigUInt library implementing the specs linked above. Closing as not planned.