[Feature] Necessity of OP_ADD, OP_SUB, OP_INV sub-bigint-syscalls

[weikengchen]

[Feature] Necessity of OP_ADD, OP_SUB, OP_INV sub-bigint-syscalls

[weikengchen]

The fact that ADD, SUB are slow also causes a mismatch about optimization. Many optimization techniques deployed in existing Rust code is around reducing multiplications and encouraging simpler additions and subtractions. The situation with RISC Zero at the moment, with the OP_MULTIPLY sub-syscall being very privileged, is different.

[weikengchen]

Below is the benchmark result for the examples/src/ecdsa in 0.20.1

Field operations:
add: 173 cycles
mul: 39 cycles
mul_single: 48 cycles
square: 39 cycles
negate: 31 cycles
invert: 9328 cycles

Scalar operations:
add: 225 cycles
mul: 147 cycles
square: 147 cycles
negate: 123 cycles
invert: 18294 cycles
invert_vartime: 17201 cycles

Group operations:
lincomb: 925349 cycles

[weikengchen]

Addition (without modular reduction) is about 4x overhead of modular multiplication right now. If it may overflow (this is always the case for secp256k1, but ed25519 offers some delay), another addition to fix the gap is needed, making it 8x.

This leads to a situation as follows: most of the curve formulas become equivalent in terms of performance because they usually have 6-7 adds. There are alternative representations that have even more adds, but does not seem to have any result that goes lower.

Optimization, therefore, would be mainly about NAF representations, endomorphisms, windows etc.