Optimize full-width u64 multiplications for wasm target

The main bottleneck of the cryptography we're using is the full-width u64 multiplication. In the case of wasm it compiles into __multi3 function that is relatively slow. One easy way to target this problem (probably not the best though) is to replace:

(x as u128) * (y as u128)

with

// x = x_1 * 2^32 + x_0
let x_0 = (x as u32) as u64;
let x_1 = x >> 32;

// y = y_1 * 2^32 + y_0
let y_0 = (y as u32) as u64;
let y_1 = y >> 32;

// x * y = (x_1 * 2^32 + x_0)(y_1 * 2^32 + y_0) = x_1*y_1 * 2^64 + (x_1*y_0 + x_0 * y_1)*2^32 + x_0*y_0 = 
// = z_2 * 2^64 + z_1 * 2^32 + z_0
let z_0 = x_0 * y_0;
let z_2 = x_1 * y_1;

let z_1 = u128::from(x_0 * y_1) + u128::from(x_1 * y_0);

(u128::from(z_2) << 64) + (z_1 << 32) + u128::from(z_0)

for wasm target.

It may not look clear but this way we're replacing one u128 multiplication with four u64 multiplications and a couple additions.

This optimization in the fawkes-crypto leads to speeding up synchronization time by ~15 % and improves proving time a bit. Similarly, we can implement it in phase2-bn254 and it can improve proving time by ~ 13 %.

zkBob / fawkes-crypto

Optimize full-width u64 multiplications for wasm target #16