Perform a single batch_mul in recursive IPA #1023
Comments
|
This might actually not be needed, closing for now |
|
heya I noticed this because it was referenced in the code still. I don't think it's useful because all of the scalars that go into the G mom would need to be multiplied by alpha_0 ...I think. In the recursive setting these are bigfield elements so very expensive. I did make a PR that removes all of the isolated Commitment::operator* calls though and rolls them into the two batch_mul calls 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]>
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: