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

Improve commitment cost in Quarks/hybrid grand product argument #444

Open
GUJustin opened this issue Aug 13, 2024 · 0 comments
Open

Improve commitment cost in Quarks/hybrid grand product argument #444

GUJustin opened this issue Aug 13, 2024 · 0 comments

Comments

@GUJustin
Copy link
Contributor

About 93% of the factors arising the Lasso grand product arguments are 1. We are currently not leveraging this fact when committing to the partial products in the Hybrid or Quarks grand product argument. That is, the prover is currently paying one group operation to commit to each 1. These should actually be "free" to commit to.

To achieve this, in pre-processing we should pre-compute the product of all group elements in the entire commitment key, obtaining a result G (we can, say, include G in the SRS, if we are using HyperKZG as the polynomial commitment). G is the commitment to the all-1s vector. Hence, G is like "pretending" that all gates in all the grand product circuits are 1. Then when we go to commit to a gate of value i, we instead commit to i-1, getting a result H. The final commitment is G*H.

This is a much faster way to compute the same commitment that we compute today. For Quarks, this modification should reduce commitment costs by a factor of 2 or more.

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

1 participant