How to do first iteration of ProtoGalaxy #740
Comments
lucasxia01
added a commit
to AztecProtocol/aztec-packages
that referenced
this issue
Feb 20, 2024
This work makes the first iteration of protogalaxy more efficient by removing the perturbator computation in just the first iteration. We can do this because in the first iteration, there is no accumulator, so we're just folding instances together. Because of this, we can assume that f_i(\omega) is 0 for all i. This seems suspicious, but this assumption is fine because if the instances were not valid (some f_i(\omega) is not 0), folding invalid instances would yield an invalid accumlator so it wouldn't matter in the end. Normally, we can't do this because f_i(\omega) for a correct accumulator is not all 0s, as \omega is some folded thing. Fixes AztecProtocol/barretenberg#740.
AztecBot
pushed a commit
that referenced
this issue
Feb 21, 2024
This work makes the first iteration of protogalaxy more efficient by removing the perturbator computation in just the first iteration. We can do this because in the first iteration, there is no accumulator, so we're just folding instances together. Because of this, we can assume that f_i(\omega) is 0 for all i. This seems suspicious, but this assumption is fine because if the instances were not valid (some f_i(\omega) is not 0), folding invalid instances would yield an invalid accumlator so it wouldn't matter in the end. Normally, we can't do this because f_i(\omega) for a correct accumulator is not all 0s, as \omega is some folded thing. Fixes #740.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
At the first iteration of PG protocol there is no accumulator (i.e.
InstancewithFoldingParamsset) and there are two ways to go through the protocol. Writing down notes from a conversation with Zac.Option 1 (more expensive)
Transform an Instance into an Accumulator: this can be done by having the verifier send a challenge
betato the prover and prover computesvec{beta}as powers ofbetaand then run the protocol as usual. ('betais referred to as the gate separation challenge in the codebase).Option 2
Run the protocol with an empty accumulator. This saves us the work ok computing
F(the perturbator polynomial) at the first iteration and soF(alpha) = 0. Thenvec{beta*)will be entirely dependent of challengesalphaanddelta. The rest of the iteration runs as normal.The text was updated successfully, but these errors were encountered: