Zero-allocation hash_to_prime via custom U256/U512

cambrian / accumulator

Cryptographic accumulators in Rust.

https://cambrian.github.io/accumulator

MIT License

133 stars 34 forks source link

Zero-allocation hash_to_prime via custom U256/U512 #27

Closed eddiew closed 5 years ago

eddiew commented 5 years ago

Improves runtime for hash_to_prime from 380us to 320us while keeping the function signature unchanged.

whaatt commented 5 years ago

Looks good at a general glance (but haven't dug into the gmp calls yet) and seems to pass existing tests.

Without digging deeper, the only two suggestions I have are:

rename u256.rs to u_types.rs since the U512 type can still leak from U256 ops
add more tests for U256 -- it's likely correct since it passes all of our "integration" tests but more U256 tests are something we eventually want

will wait for @lucasege to look through this as well

lucasege commented 5 years ago

I agree with Sanj's suggestions - although if you think the current tests offer sufficient coverage then it might not be worth too much time to add redundant tests.

My only suggestion is regarding some functions in gmp which have undefined behavior on certain inputs, such as mpz_invert which has undefined behavior when op2 is zero. Up to you how/if we want to handle this, just want us to be aware of it.

eddiew commented 5 years ago

Your reviews should be addressed in the latest commits. I went with uint.rs instead of u_types.rs, and we could still add more tests but I think what we have now is ok.

Good point re undefined behavior - most of the time the programs will crash with SIGFPE if bad inputs are given to gmp functions. But since this really only can occur for functions that take a modulus and the modulus happens to be 0, I don't think it's worth checking at runtime. I left comments in places where that might happen though