Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimize full-width u64 multiplications for wasm target #16

Open
AllFi opened this issue Jul 13, 2023 · 1 comment
Open

Optimize full-width u64 multiplications for wasm target #16

AllFi opened this issue Jul 13, 2023 · 1 comment
Assignees
Labels

Comments

@AllFi
Copy link

AllFi commented Jul 13, 2023

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 %.

@AllFi AllFi changed the title Replace one u128 multiplication with four u64 multiplications for wasm target Optimize full-width u64 multiplications Jul 13, 2023
@AllFi AllFi added the PR label Jul 13, 2023
@AllFi
Copy link
Author

AllFi commented Jul 13, 2023

Related PR: #15

@AllFi AllFi changed the title Optimize full-width u64 multiplications Optimize full-width u64 multiplications for wasm target Jul 13, 2023
@AllFi AllFi self-assigned this Jul 13, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant