Open qwang98 opened 2 months ago
@georgwiese @pacheco Thoughts? :)
I think this makes sense, in particular once we reduce the "fixed" cost of doing ecalls, which is quite high right now. I don't know about the proving cost for each approach (accelerate ec VS modular operations) but we can measure and compare once we have everything in place.
Background
ec_add
andec_double
. 2. acceleratemodmul
andmodadd
only, which are the most time consuming component ofec_add
andec_double
. 3. Do both 1 and 2.modmul
syscall, which is called extensively by 2, spends most rows in register copying from and to memory. *3 has limited potential for improvement because not many non-ec operations callsmodmul
, so any improvement would be marginalThe issue
modmul
currently has two syscalls on the affine submachine, which is why we propose to reducemodmul
andmodadd
to one syscall in this issue. This change would mostly benefit *2, if we can create a submachine just formodmul
andmodadd
and remove all ec operations in the current arith machine.Basic proposal
Additional proposal to reduce column C
eq0
constraint is justso we can just remove the
product
term for the add operation and remove thex2f
term for the product operation. This has the advantage of shaving off the 16 C columns.Additional proposal to reduce columns Q and R
modmul
13k times, for 64 rows per call, this would be 832k rows. Currently the main machine has 3.1 million rows, but after further optimization this might go below 832k rows.Other potential optimizations
modmul
andmodadd
will return remainder that's smaller than the modulus. This is enforced as an assertion on the Rust level of thek256
crate fieldmul
function. We could consider enforcing this in less than constraints in the submachine, but I'm not sure how to efficiently do it for numbers with 16 limbs.