Prover/Adding Initial Compiler for Permutation Query #386
Conversation
arijitdutta67
added
enhancement
arijitdutta67
had a problem deploying
to
docker-build-and-e2e
GitHub Actions
Error
Codecov ReportAll modified and coverable lines are covered by tests ✅
Additional details and impacted files@@ Coverage Diff @@
## prover/limitless-top-level #386 +/- ##
=============================================================
Coverage 70.20% 70.20%
Complexity 1072 1072
=============================================================
Files 306 306
Lines 12322 12322
Branches 1178 1178
=============================================================
Hits 8651 8651
Misses 3179 3179
Partials 492 492
*This pull request uses carry forward flags. Click here to find out more. |
prover/protocol/distributed/compiler/permutation/permutation.go
Outdated
Show resolved
Hide resolved
arijitdutta67
requested a deployment
to
docker-build-and-e2e
GitHub Actions
Waiting
| "github.com/consensys/linea-monorepo/prover/utils" | ||
| ) | ||
|
|
||
| type GrandProduct struct { |
There was a problem hiding this comment.
Don't forget the document the query
| ID ifaces.QueryID | ||
| Numerator [][]ifaces.Column // stores A as multi-column | ||
| Denominator [][]ifaces.Column // stores B as multi-column | ||
| Alpha coin.Info // randomness for random linear combination in case of multi-column, to be provided by the |
There was a problem hiding this comment.
The value of alpha will be different for every term in the product. Same for beta.
There was a problem hiding this comment.
My plan was to generate one GrandProduct query for each individual permutation query. As a result, for a particular permutation query, the value of alpha and beta will be the same. These values will be used by the sub-provers.
However, for different queries, the alphas and betas will be different. Later, the aggregator can batch verify these grand product queries by checking $Z_{1,1}\cdotsZ_{1,l_1}Z_{2,1}\cdotsZ_{2,l_2}\cdots = 1$, where ith permutation query -> ith GrandProduct query -> split among l_i sub-provers. Will this work?
| // randomness beacon | ||
| Beta coin.Info // randomness for the grand product accumulation, to be provided by the | ||
| // randomness beacon | ||
| Z symbolic.Expression // aimed at storing the expressions (Ai + \beta_i)/(Bi + \beta_i) |
There was a problem hiding this comment.
redundant: Z can be constructed from the other fields
| } | ||
|
|
||
| // Reduce a permutation query into a GrandProduct query | ||
| comp.InsertGrandProduct(round, q.Name(), q.A, q.B, alpha, beta) |
There was a problem hiding this comment.
It's not one per Permutation but one for the whole wizard at once
Soleimani193
force-pushed
the
prover/limitless-top-level
branch
from
16fbcd9 to
2cae000
Compare
| "github.com/consensys/linea-monorepo/prover/protocol/wizard" | ||
| ) | ||
|
|
||
| func IntoGrandProduct(comp *wizard.CompiledIOP) { |
There was a problem hiding this comment.
Changes considering that we will skip the preparation phase:
AddGdProductQuery(initialComp, moduleComp, disc, targetModuleName)
Soleimani193
force-pushed
the
prover/limitless-top-level
branch
from
3cec11b to
08b8b32
Compare
prover/protocol/distributed/compiler/permutation/permutation.go
Outdated
Show resolved
Hide resolved
prover/protocol/distributed/module_discoverer/module_discoverer.go
Outdated
Show resolved
Hide resolved
This PR implements issue(s) #383
Checklist