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.

Sign up for GitHub

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

Jump to bottom

More efficient powering by constant #55

Open
4 tasks
weikengchen opened this issue Mar 2, 2021 · 5 comments · May be fixed by #72
Open
4 tasks

More efficient powering by constant #55

weikengchen opened this issue Mar 2, 2021 · 5 comments · May be fixed by #72
Labels
D-easy Difficulty: easy T-feature Type: new features T-performance Type: performance improvements

Comments

@weikengchen
Copy link
Member

Summary

How many constraints should it be to compute x^{255}?

How many constraints should it be to compute x^{257}?

In our current implementation, the cost of powering by constants is as follows:

L = len of binary representation
N = num of ones in the binary representation
cost = L - 1 + N - 1

So, powering by 255 is more expensive than 257.

Yet, to compute x^{255}, why not compute x^{256}, and then go down to x^{255}, which only takes one constraint?

Problem Definition

The more efficient powering by constant would examine the NAF form (https://en.wikipedia.org/wiki/Non-adjacent_form), which, not just considering the binary representation, but a representation with alphabet -1, 0, 1.

This, indeed, gives a better performance for powering by constant.

Proposal

Enhance the powering by constant by first computing the NAF form, and then write down the constraints accordingly.

Relationship to Poseidon

Although this issue pops up during the implementation of Poseidon, it is semi-useful for Poseidon.

On the one hand, for Poseidon, if the cost of computing x^{255} and x^{257} is the same, it would always prefer 257 for alpha (ignoring the fact that 257 is also a prime, and 255 is not).

On the other hand, it might also be useful for Poseidon. For example, 7 = 8 - 1 is not that expensive indeed, and 7 may be a suitable prime.

cc'ed authors who have touched fields/mod.rs in the past: @ValarDragon @Pratyush

For Admin Use

  • Not duplicate issue
  • Appropriate labels applied
  • Appropriate contributors tagged
  • Contributor assigned/self-assigned
@weikengchen weikengchen added T-feature Type: new features D-easy Difficulty: easy help wanted labels Mar 2, 2021
@daira
Copy link
Contributor

daira commented Mar 2, 2021 •
edited
Loading

For specific applications, it may be useful to provide an optimized addition-subtraction [*] chain. This is because such a chain for a given scalar and field (especially where the field order has low Hamming weight) can be significantly more efficient than the NAF one, because NAF doesn't take into account repeating patterns in the binary representation. For example here are various useful addition chains for the Pasta curves: zcash/zcash#4883 (the chains for 1/5 and 1/7 are more efficient than NAF).

Incidentally, why use 255 or 257 as the power for Poseidon? It's optimized for small powers.

[*] Only addition chains are useful outside the circuit, but including subtraction could be useful inside.

@weikengchen
Copy link
Member Author

weikengchen commented Mar 2, 2021 •
edited
Loading

@daira Got it! Great points. An addition chain is a better idea.

Regarding the Poseidon with alpha = 257, this is because, in Marlin or Fractal, the proving time is quasi-linear to the number of non-zero entries in the R1CS matrices, rather than quasi-linear to the number of constraints, therefore:

  • the linear combination part of Poseidon, add-key and mix, is not free.
  • optimizing for this, which would desire fewer rounds, leads to alpha = 257.

Updated 4/4/21: If the MDS matrix is circular, smaller alpha wins again. So the case of 255/257 is indeed not needed.

@weikengchen
Copy link
Member Author

And another note from the optimized addition-subtraction chain from Daira's note:

  • Addition chain is very useful in computing x^{-3} x^{-5}, as in the case of Rescue, outside the constraint system.
  • Inside the constraint system, we would consider the addition-subtraction chain, since subtraction (division) has the same overhead in the constraint system.

Addition-subtraction chains are not easy to find. But for a number of our applications, the developer can find the chain outside and hardcode it. We should also give the developers the option to make do with the NAF form.

@weikengchen
Copy link
Member Author

I think the part of the addition-subtraction chain would be about the interface. Should FpGadget take that into consideration, or should a separate Gadget handle this?

@weikengchen
Copy link
Member Author

Updated related to the previous statement on Poseidon---if one uses a circular matrix it would no longer be the issue---a smaller alpha would often give you the smallest cost when even the constraint system weight is being considered.

@weikengchen weikengchen linked a pull request Jul 4, 2021 that will close this issue
Open
6 tasks
@Pratyush Pratyush added T-performance Type: performance improvements and removed help wanted labels Sep 9, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
D-easy Difficulty: easy T-feature Type: new features T-performance Type: performance improvements
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Implement pow-by-constant with NAF for FpVar arkworks-rs/r1cs-std
3 participants
@daira @Pratyush @weikengchen