search

herumi / mcl

a portable and fast pairing-based cryptography library
BSD 3-Clause "New" or "Revised" License
452 stars 152 forks source link

Questions regarding backend implementation #36

Closed ghost closed 5 years ago

ghost commented 5 years ago

Hi @herumi

I am interested in contributing to the repo to attempt to provide faster signature verification. For this, I wanted to understand the underlying implementation of the miller_loop and finalexp functions. As far as I understand, these functions are implemented in the llvm IR. I am having some trouble understanding what is going on. Do you have more high-level code on the miller_loop and finalexp implementation?

Kind regards

ghost commented 5 years ago

Also, I have written Rust wrappers for mcl and bls. Would you like me to push a pull request for these?

herumi commented 5 years ago

The pairing is written in C++ ; mcl/bn.hpp

But some detail is a little different. Maybe, there are no complete documents about it.

bn.hpp requires some elementary arithmetic operations such as Fp::add, mul, etc. For these functions, you can select some way:

herumi commented 5 years ago

I have written Rust wrappers for mcl and bls. Would you like me to push a pull request for these?

Thank you. Does it use bn.h and is put in {mcl,bls}/ffi/rust/*? I'll see your code.

ghost commented 5 years ago

Yes, I used bindgen using bn.h and then I wrapped the generated code in some nice functions that accept references for the mclBn.. types. I measured performance in Rust and it's the same as in C++

ghost commented 5 years ago

Also, a few more questions:

  1. Do you think we could benefit from making use of AVX2 intrinsics for computing the miller loop and finalexp?
  2. Does this group make use of Montgomery ladder or wNAF tricks to speed up public key generation?
  3. If one component of the pairing is fixed, e.g. in the context of verifying a BLS signature, do you believe it would make sense to optimize further than precomputing the G2 coefficients (https://eprint.iacr.org/2010/342.pdf)?
herumi commented 5 years ago

Do you think we could benefit from making use of AVX2 intrinsics for computing the miller loop and finalexp?

I tried to use AVX before but it was slower than the current code. I'll try again for a new CPU later.

Does this group make use of Montgomery ladder or wNAF tricks to speed up public key generation?

G2::mul() uses GLV method.

do you believe it would make sense to optimize further than precomputing the G2 coefficients?

I do not know.