Benchmarking: k256 falls short to fiat-crypto and crypto-bigint

[ycscaly]

fiat-crypto synthesizes field arithmetic, so it's all specialized to the properties of a particular field modulus.

There is a formal verification versus performance tradeoff, yes. We opt for better performance because that seems to interest our users more than formal verification.

Hopefully in the future fiat-crypto will improve performance and add features like lazy normalization.

I ran some benchmarking, and was really surprised at the results. I published the code so you can see that I haven't made any mistakes.

But results are (full trace is found in the readme file of the repo):

• fiat-crypto field arithmetic is faster (add: 3.6ns vs 5.2ns, mul: 22ns vs 28ns) than k256
• crypto-bigint::Residue arithmetic faster (add: 3.8ns vs 5.2ns, mul: 27ns vs 28ns) than k256 (but slower than fiat-crypto

How can this be explained? perhaps there's some error on my side?

Originally posted by @ycscaly in https://github.com/RustCrypto/crypto-bigint/issues/158#issuecomment-1507431728

[tarcieri]

cc @fjarri

[tarcieri]

I don't think a whole lot of work has been done on optimizing the scalar field in k256. If either of these are faster it might be worth considering switching.

[fjarri]

I don't think it is entirely correct to compare Residue and k256::Scalar multiplication, because for Residue you have to factor in conversion/retrieval time. I expect Residue would be faster when you have to do a long series of calculations, but Scalar is optimized for one-off operations.

[tarcieri]

Aah yes, Residue and fiat-crypto are both using Montgomery form internally, and there's a penalty to convert in and out of Montgomery form

[ycscaly]

Aah yes, Residue and fiat-crypto are both using Montgomery form internally, and there's a penalty to convert in and out of Montgomery form

Convert from which form to Montgomery form? And where does that penalty take place? When would I need to switch back?

[tarcieri]

The other form is "canonical form" and is a normal integer.

The fiat-crypto methods are named: fiat_*_from_montgomery, fiat_*_to_montgomery

[ycscaly]

Thanks. I didn't know about these different forms, would research more.

I'll update my benchmarking code and update this issue accordingly, after-which I assume it could be closed.