Folding Goblin polynomials not in the ProverPolynomials #753
Assignees
Milestone
Comments
|
includes folding linearly dependent relations |
maramihali
added a commit
to AztecProtocol/aztec-packages
that referenced
this issue
Feb 2, 2024
Adds the missing functionality to be able to fold `GoblinUltra` instances to PG prover and verifier (both native and recursive). On one hand, this includes committing to the additional witness polynomials ( ECC op wires and data bus related polynomials) as well as computing and committing to the log derivativee inverses similar to the pre-sumcheck rounds in the UltraProver We also need to add extra functionality to be able to fold linearly dependent relations. Such relations (in our codebase, just one subrelation part of the data bus relations) operate on the entire execution trace rather than a single row. They don't have to hold at each row in part which implies that we won't multiply them by the pow polynomial. This requires us to make modifications just to the perturbator (F polynomial). The combiner (`G` polynomial) makes use of the `accumulate` function, which is implemented for every subrelation we have which, in the case of linearly dependent relations, does not use the `scaling_factor` provided as argument. In the perturbator, we accumulate the evaluation of the full honk relation at each row and return a vector of `FF`. We modify it to add to the value at index 0 (representing row 0) also the `linear_dependent_contribution` (the value of the linear dependent subrelation over the entire execution trace) _batched_ by its coresponding batching challenge `alpha` (recall we have a batching challenge for each subrelation). Otherwise than that the protocol remains unchanged. Closes AztecProtocol/barretenberg#753.
AztecBot
pushed a commit
that referenced
this issue
Feb 3, 2024
Adds the missing functionality to be able to fold `GoblinUltra` instances to PG prover and verifier (both native and recursive). On one hand, this includes committing to the additional witness polynomials ( ECC op wires and data bus related polynomials) as well as computing and committing to the log derivativee inverses similar to the pre-sumcheck rounds in the UltraProver We also need to add extra functionality to be able to fold linearly dependent relations. Such relations (in our codebase, just one subrelation part of the data bus relations) operate on the entire execution trace rather than a single row. They don't have to hold at each row in part which implies that we won't multiply them by the pow polynomial. This requires us to make modifications just to the perturbator (F polynomial). The combiner (`G` polynomial) makes use of the `accumulate` function, which is implemented for every subrelation we have which, in the case of linearly dependent relations, does not use the `scaling_factor` provided as argument. In the perturbator, we accumulate the evaluation of the full honk relation at each row and return a vector of `FF`. We modify it to add to the value at index 0 (representing row 0) also the `linear_dependent_contribution` (the value of the linear dependent subrelation over the entire execution trace) _batched_ by its coresponding batching challenge `alpha` (recall we have a batching challenge for each subrelation). Otherwise than that the protocol remains unchanged. Closes #753.
TomAFrench
pushed a commit
to AztecProtocol/aztec-packages
that referenced
this issue
Feb 7, 2024
Adds the missing functionality to be able to fold `GoblinUltra` instances to PG prover and verifier (both native and recursive). On one hand, this includes committing to the additional witness polynomials ( ECC op wires and data bus related polynomials) as well as computing and committing to the log derivativee inverses similar to the pre-sumcheck rounds in the UltraProver We also need to add extra functionality to be able to fold linearly dependent relations. Such relations (in our codebase, just one subrelation part of the data bus relations) operate on the entire execution trace rather than a single row. They don't have to hold at each row in part which implies that we won't multiply them by the pow polynomial. This requires us to make modifications just to the perturbator (F polynomial). The combiner (`G` polynomial) makes use of the `accumulate` function, which is implemented for every subrelation we have which, in the case of linearly dependent relations, does not use the `scaling_factor` provided as argument. In the perturbator, we accumulate the evaluation of the full honk relation at each row and return a vector of `FF`. We modify it to add to the value at index 0 (representing row 0) also the `linear_dependent_contribution` (the value of the linear dependent subrelation over the entire execution trace) _batched_ by its coresponding batching challenge `alpha` (recall we have a batching challenge for each subrelation). Otherwise than that the protocol remains unchanged. Closes AztecProtocol/barretenberg#753.
michaelelliot
pushed a commit
to Swoir/noir_rs
that referenced
this issue
Feb 28, 2024
) Adds the missing functionality to be able to fold `GoblinUltra` instances to PG prover and verifier (both native and recursive). On one hand, this includes committing to the additional witness polynomials ( ECC op wires and data bus related polynomials) as well as computing and committing to the log derivativee inverses similar to the pre-sumcheck rounds in the UltraProver We also need to add extra functionality to be able to fold linearly dependent relations. Such relations (in our codebase, just one subrelation part of the data bus relations) operate on the entire execution trace rather than a single row. They don't have to hold at each row in part which implies that we won't multiply them by the pow polynomial. This requires us to make modifications just to the perturbator (F polynomial). The combiner (`G` polynomial) makes use of the `accumulate` function, which is implemented for every subrelation we have which, in the case of linearly dependent relations, does not use the `scaling_factor` provided as argument. In the perturbator, we accumulate the evaluation of the full honk relation at each row and return a vector of `FF`. We modify it to add to the value at index 0 (representing row 0) also the `linear_dependent_contribution` (the value of the linear dependent subrelation over the entire execution trace) _batched_ by its coresponding batching challenge `alpha` (recall we have a batching challenge for each subrelation). Otherwise than that the protocol remains unchanged. Closes AztecProtocol/barretenberg#753.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
No description provided.
The text was updated successfully, but these errors were encountered: