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

details about scalar_mul? #197

Closed
PayneJoe opened this issue Jul 8, 2023 · 3 comments
Closed

details about scalar_mul? #197

PayneJoe opened this issue Jul 8, 2023 · 3 comments

Comments

@PayneJoe
Copy link

PayneJoe commented Jul 8, 2023

As commented within code above scalar_mul:

/// A gadget for scalar multiplication, optimized to use incomplete addition law.
/// The optimization here is analogous to https://github.com/arkworks-rs/r1cs-std/blob/6d64f379a27011b3629cf4c9cb38b7b7b695d5a0/src/groups/curves/short_weierstrass/mod.rs#L295,
/// except we use complete addition law over affine coordinates instead of projective coordinates for the tail bits

I have three questions:

  1. diving into code, split index is approximately located at G::Base::NUM_BITS - 2, why?

  2. why do not use complete addition law over projective coordinates within which field inversion disappears as arkworks-rs/r1cs-std do?

  3. other point representation methods such as NAF or GLV would outperform the binary representation here?

@srinathsetty
Copy link
Collaborator

Hi @PayneJoe thanks for your interest!

  1. The details of this choice are described in the referenced arkworks link. Please let me know if you have further questions.
  2. Right, but moving to projective involves additional code (our code already had complete addition laws for affine coordinates implemented). There may be some gain from using projective coordinates, but Nova does only two scalar muls (so it wasn't clear it was worth investing time for that).
  3. Yes, certainly.

More on (2) and (3). We took a pragmatic approach, so there may be optimizations to be done. We are happy to accept PRs if it makes the code smaller while maintaining the same performance and/or make the performance better.

@huitseeker
Copy link
Contributor

I believe the references are:

@PayneJoe
Copy link
Author

PayneJoe commented Jul 27, 2023

Hi @PayneJoe thanks for your interest!

  1. The details of this choice are described in the referenced arkworks link. Please let me know if you have further questions.
  2. Right, but moving to projective involves additional code (our code already had complete addition laws for affine coordinates implemented). There may be some gain from using projective coordinates, but Nova does only two scalar muls (so it wasn't clear it was worth investing time for that).
  3. Yes, certainly.

More on (2) and (3). We took a pragmatic approach, so there may be optimizations to be done. We are happy to accept PRs if it makes the code smaller while maintaining the same performance and/or make the performance better.

Suppose that addition within scalar_mul is Acc = Acc + P, prime modular is q

Still not clear why the lower range [0, G::Base::NUM_BITS - 2) of scalarkwould make sure that point Acc and point P are constrained within safe distance, namely to say point Acc is [2, q - 1) times point P or point P is [2, q - 1) times point Acc? How about the other ranges such as [0, G::Base::NUM_BITS - 1) or [0, G::Base::NUM_BITS - 3) or ...?

I run a test using curve y^2 = x^3 + 4x + 20 over F_29(5 bits length), while its order is 37(6 bits length). It turns out that the edge cases(Acc == P or Acc == -P) always appears in the highest bit(k = 36 or 37). Indeed it's safe within bits [0, 3), but it's also safe within bits [0, 4).

Am I missing something else about that? Appreciated in advance @srinathsetty @huitseeker

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

No branches or pull requests

3 participants