jolt
jolt copied to clipboard
Improve commitment cost in Quarks/hybrid grand product argument
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.