constantine icon indicating copy to clipboard operation
constantine copied to clipboard

Assembly backend for >= 384-bit primes

Open mratsim opened this issue 5 years ago • 3 comments

The current assembly backend is restricted to up to 384-bit primes (6 limbs) as otherwise it requires register spilling.

https://github.com/mratsim/constantine/blob/7f0f5117607707f3698ba14a151039c9ccee7c0b/constantine/arithmetic/limbs_montgomery.nim#L302-L311

For Zero-Knowledge one-layer proof composition, a curve needs to be embedded in another as in it's modulus should be the order of the other, for example this is the case of BLS12-377 + CP6-782 (Zexe) or BLS12-377 + BW6-761 (Celo) see #93, the embedding curve has a large prime field for which there is no assembly at the moment.

Similarly, the curve MNT4-753 and MNT6-753 for recursive proofs are also much larger than 384-bit.

mratsim avatar Oct 13 '20 20:10 mratsim

Kilic's impl produces very good results for these limbs > 6

jon-chuang avatar Oct 14 '20 17:10 jon-chuang

Did you measure the performance against Goff? It seems quite simple https://github.com/ConsenSys/goff/blob/fa7dd55e/asm/amd64/element_mul.go#L70-L83

mratsim avatar Oct 14 '20 18:10 mratsim

Goff's method is naive push and pop, so I assume slow. Kilic splits up the inner loop so there is less data movement

jon-chuang avatar Oct 14 '20 18:10 jon-chuang