Wasm-friendly Field arithmetic

[mitschabaude]

Why

Webassembly doesn't support:

• native 64x64-bit multiplication which preserves the full 128-bit result
  • note: adding this to Wasm is currently in the proposal stage
• addition with a carry flag, or multiplication with an additional summand, etc

These limitation cause arkworks implementations of finite field arithmetic, on which our proof system entirely depends, to suffer a huge efficiency loss in Wasm compared to native.

Example: 5x slow-down for a chain of Poseidon hashes #2633

Meanwhile, results from Zprize '22 and '23, and our own prototyping informed by that, showed that more efficient field implementations are possible despite the lack of certain instructions. The most significant change here is to switch to redundant field representations:

• 9 limbs of 29 bits each (instead of 8 x 32), or
• 5 limbs of 51 bits each (instead of 4 x 64)

Both of these enable multiplication algorithms that avoid a significant portion (but not all) of the overhead cost of emulating native 64x64 -> 128 multiplication, and recover much of the gap to native speed.

This issue is about bringing such improvements to our proof system.

How

Pratyush discusses the possibility of supporting alternative backends within arkwork's own Fp implementation here: arkworks-rs/algebra#769
Currently, this is deemed not possible because the bit layout of field elements is hard-coded to 4 x 64 bits.

Therefore, the only possible way forward I see is to implement our own version of Fp.

TODO: figure out how much of arkworks we can still reuse. I.e. algorithms that only depend on abstract Field operations, like square root or inverse, could be reusable (as long as they don't rely on the hard-coded bit layout assumption)