Add finite field operations to AVM

[javerett]

Problem

Currently the AVM only supports bigints up to 512 bits, which is insufficient for performing RSA operations. Additionally, there are a few opcodes which are necessary to enable RSA based zero-knowledge proofs without excessive gas costs.

Solution

To enable operations on larger fields, the b*, b+, etc operations could be expanded to support larger input sizes(at least 2048 bits, but ideally 4096, or leave it unlimited). To account for the increased cost, perhaps a dynamic cost related to the input size would work. A divMod operation would also be helpful, to save gas cost recomputing a value that the division algorithm generates for free.

Additionally, there are a few operations which would be useful for working with RSA groups and for other general crypto operations.

• Modular exponentiation modPow(base: bytes, exponent: bytes, modulus: bytes): bytes
• Generation of given bit length prime derived from a seed value hashToPrime(value: bytes, length: uint): bytes
• Checking if a number is prime isPrime(value: bytes): uint

hashToPrime can likely be done on server and validated on chain if isPrime is available, lowering costs.

For primality validation, Baillie–PSW would be ideal as it has no known counterexamples. For generating primes with hashToPrime, a possible algorithm is to concatenate a uint counter to the end of the input value, hash the combined byte arrays generating length bits, set the lowest and highest order bits to ensure it's an odd prime of the correct length, and then test primality as above. If the value is prime, return it, else increment the counter and repeat

[michaeldiamant]

@javerett Thanks for documenting the need. No estimate on timing, but we'll likely take a closer look when picking up https://github.com/algorand/go-algorand/issues/4036.

[javerett]

After running some more tests on my end, this ends up being too expensive for my particular use case, the need to validate on browser has pushed me towards a BLS based system. This remains a useful extension, however unless there is other interest, I'd put this at a very low priority.

I figured RSA would make the implementation a lot easier, but the performance is at least an order of magnitude off so I've halted work on that design for now

[algoanne]

Given the above comment, I'll close this until interest resurfaces (if ever).