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

[perf] KZG verify #220

Merged
merged 1 commit into from
Jul 27, 2022
Merged

[perf] KZG verify #220

merged 1 commit into from
Jul 27, 2022

Conversation

yelhousni
Copy link
Collaborator

@yelhousni yelhousni commented Jul 13, 2022

KZG verification algorithm consists in some scalar multiplications and then a pairing computation. The scalar multiplications are best implemented using Jacobian coordinates while the pairing is best implemented using mixed affine and projective coordinates. The ScalarMul() API makes unnecessary conversions between affine and Jacobians which costs some unnecessary inverses. Few solutions:

  • This PR implements a ScalarMul() functions that takes an affine point and returns a Jacobian.
  • [ ] Implementing the pairing with only projective coordinates and implementing the ScalarMul() in projective too (no conversions at all). This is implemented in perf/kzg-verify-proj branch but it is worth it only if the Hamming weight of the Miller loop size is less than 6 (perf threshold for mixed add/dbl vs. proj add/dbl). This is not the case for the curve in gnark-crypto. Also it duplicates the pairing code.
  • we can also implement a custom BatchFromJacobian() functions that takes elements from both G1 (Fp) and G2 (Fp2 or Fp4).

@yelhousni
Copy link
Collaborator Author

On gnark side Consensys/gnark#342

@gbotrel
Copy link
Collaborator

gbotrel commented Jul 15, 2022

Q: why the refactor ScalarMultiplication to ScalarMul ?

@yelhousni
Copy link
Collaborator Author

I added on gnark-crypto a function ScalarMulUnconverted that takes an affine point and outputs a Jacobian to get rid of an unnecessary conversion (inverse) in KZG verifier. So ScalarMultiplicationUnconverted is too long ^^ and also in std/ we use ScalarMul so that is coherent.

@gbotrel gbotrel merged commit 37274b4 into develop Jul 27, 2022
@gbotrel gbotrel deleted the perf/kzg-verify branch July 27, 2022 15:31
@gbotrel gbotrel restored the perf/kzg-verify branch July 27, 2022 15:32
@gbotrel
Copy link
Collaborator

gbotrel commented Jul 27, 2022

Mmhh accidentally merged too fast I think, not that the name change is big, but it impacts user of the lib for no big reasons.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants