IPA verifier is O(nlogn) #857
Labels
Comments
lucasxia01
added a commit
to AztecProtocol/aztec-packages
that referenced
this issue
Feb 23, 2024
Adds the pow poly bench. This PR was supposed to also optimize the pow poly computation, but I measured that it takes around 45ms of the whole 6-iter client IVC benchmark, so its not worth doing for now. Links a couple of optimization issues to the codebase: AztecProtocol/barretenberg#857 and AztecProtocol/barretenberg#864.
|
fixed in AztecProtocol/aztec-packages#9420 |
lucasxia01
added a commit
to AztecProtocol/aztec-packages
that referenced
this issue
Oct 29, 2024
eccvm_recursive_verifier_test measurements (size-512 eccvm recursive verification) Old: 876,214 New: 678,751 The relative performance delta should be much greater for large eccvm instances as this PR removes an nlogn algorithm. This PR resolves issue [#857](AztecProtocol/barretenberg#857) and issue [#1023](AztecProtocol/barretenberg#1023) (single batch mul in IPA) Re: [#1023](AztecProtocol/barretenberg#1023). The code still performs 2 batch muls, but all additional * operator calls have been combined into the batch muls. It is not worth combining both batch muls, as it would require a multiplication operation on a large number of scalar multipliers. In the recursive setting the scalars are bigfield elements - the extra bigfield::operator* cost is not worth combining both batch_mul calls. Additional improvements: removed unneccessary uses of `pow` operator in ipa - in the recursive setting these were stdlib::bigfield::pow calls and very expensive removed the number of distinct multiplication calls in ipa::reduce_verify_internal cycle_scalar::cycle_scalar(stdlib::bigfield) constructor now more optimally constructs a cycle_scalar out of a bigfield element. New method leverages the fact that `scalar.lo` and `scalar.hi` are implicitly range-constrained to remove reundant bigfield constructor calls and arithmetic calls, and the process of performing a scalar multiplication applies a modular reduction to the imput, which makes the explicit call to `validate_scalar_is_in_field` unneccessary --------- Co-authored-by: lucasxia01 <[email protected]>
AztecBot
pushed a commit
that referenced
this issue
Oct 30, 2024
eccvm_recursive_verifier_test measurements (size-512 eccvm recursive verification) Old: 876,214 New: 678,751 The relative performance delta should be much greater for large eccvm instances as this PR removes an nlogn algorithm. This PR resolves issue [#857](#857) and issue [#1023](#1023) (single batch mul in IPA) Re: [#1023](#1023). The code still performs 2 batch muls, but all additional * operator calls have been combined into the batch muls. It is not worth combining both batch muls, as it would require a multiplication operation on a large number of scalar multipliers. In the recursive setting the scalars are bigfield elements - the extra bigfield::operator* cost is not worth combining both batch_mul calls. Additional improvements: removed unneccessary uses of `pow` operator in ipa - in the recursive setting these were stdlib::bigfield::pow calls and very expensive removed the number of distinct multiplication calls in ipa::reduce_verify_internal cycle_scalar::cycle_scalar(stdlib::bigfield) constructor now more optimally constructs a cycle_scalar out of a bigfield element. New method leverages the fact that `scalar.lo` and `scalar.hi` are implicitly range-constrained to remove reundant bigfield constructor calls and arithmetic calls, and the process of performing a scalar multiplication applies a modular reduction to the imput, which makes the explicit call to `validate_scalar_is_in_field` unneccessary --------- Co-authored-by: lucasxia01 <[email protected]>
|
Closed by above PR |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
We currently inefficiently compute G^(0) in nlogn time where n is the length of the polynomial.
We can reduce this to to O(n) time by precomputing coefficients, which should be also parallelizable.
The text was updated successfully, but these errors were encountered: