-
Notifications
You must be signed in to change notification settings - Fork 234
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
feat: biggroup_goblin handles points at infinity + 1.8x reduction in ECCVM size #9366
Merged
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
greatly improved performance of goblin biggroup subtraction and negation
…mber of translator rows as well as eccvm rows
… to have 0/0 as their x/y coordinates, but a `NativeGroup::AffineElement` at infinity does not follow this standard
zac-williamson
changed the title
feat: biggroup_goblin handles points at infinity + 4x reduction in ECCVM size
feat: biggroup_goblin handles points at infinity + ~2x reduction in ECCVM size
Oct 30, 2024
codygunton
changed the title
feat: biggroup_goblin handles points at infinity + ~2x reduction in ECCVM size
feat: biggroup_goblin handles points at infinity + 1.8x reduction in ECCVM size
Oct 30, 2024
Changes to public function bytecode sizes
🧾 Summary (100% most significant diffs)
Full diff report 👇
|
codygunton
approved these changes
Oct 30, 2024
|
||
// if the output is at infinity, this is represented by x/y coordinates being zero | ||
// because they are all 136-bit, we can do a cheap zerocheck by first summing the limbs | ||
auto op2_is_infinity = (x_lo.add_two(x_hi, y_lo) + y_hi).is_zero(); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
We'll want a correctness check of this at some point.
rahul-kothari
pushed a commit
that referenced
this pull request
Nov 1, 2024
🤖 I have created a release *beep* *boop* --- <details><summary>aztec-package: 0.62.0</summary> ## [0.62.0](aztec-package-v0.61.0...aztec-package-v0.62.0) (2024-11-01) ### Features * Token private mint optimization ([#9606](#9606)) ([e8fadc7](e8fadc7)) ### Bug Fixes * **k8s:** Boot node long sync ([#9610](#9610)) ([1b85840](1b85840)) * Multi-node metrics working ([#9486](#9486)) ([fd974e1](fd974e1)) * Stop bot in case of tx errors ([#9421](#9421)) ([6650641](6650641)) ### Miscellaneous * Replacing unshield naming with transfer_to_public ([#9608](#9608)) ([247e9eb](247e9eb)) * Token partial notes refactor pt. 1 ([#9490](#9490)) ([3d631f5](3d631f5)) </details> <details><summary>barretenberg.js: 0.62.0</summary> ## [0.62.0](barretenberg.js-v0.61.0...barretenberg.js-v0.62.0) (2024-11-01) ### Features * Faster square roots ([#2694](#2694)) ([722ec5c](722ec5c)) </details> <details><summary>aztec-packages: 0.62.0</summary> ## [0.62.0](aztec-packages-v0.61.0...aztec-packages-v0.62.0) (2024-11-01) ### ⚠ BREAKING CHANGES * **avm:** use 32 bit locations ([#9596](#9596)) * Unique L1 to L2 messages ([#9492](#9492)) ### Features * Add increment secret oracles ([#9573](#9573)) ([97a4c0c](97a4c0c)) * **avm:** Use 32 bit locations ([#9596](#9596)) ([5f38696](5f38696)) * Barebones addressbook for tagging ([#9572](#9572)) ([6526069](6526069)) * Biggroup_goblin handles points at infinity + 1.8x reduction in ECCVM size ([#9366](#9366)) ([9211d8a](9211d8a)) * Faster square roots ([#2694](#2694)) ([722ec5c](722ec5c)) * Fixed private log size ([#9585](#9585)) ([755c70a](755c70a)) * Removing register recipient in e2e tests as it is unnecessary now ! ([#9499](#9499)) ([9f52cbb](9f52cbb)) * Reorg test ([#9607](#9607)) ([54488b3](54488b3)) * Simulate validateEpochProofQuoteHeader in the future ([#9641](#9641)) ([284c8f8](284c8f8)) * Spartan proving ([#9584](#9584)) ([392114a](392114a)) * Sync tagged logs ([#9595](#9595)) ([0cc4a48](0cc4a48)) * Token private mint optimization ([#9606](#9606)) ([e8fadc7](e8fadc7)) * Unique L1 to L2 messages ([#9492](#9492)) ([4e5ae95](4e5ae95)), closes [#9450](#9450) ### Bug Fixes * E2e event logs test ([#9621](#9621)) ([737c573](737c573)) * E2e labels ([#9609](#9609)) ([ed1deb9](ed1deb9)) * Ensuring translator range constraint polynomials are zeroes outside of minicircuit ([#9251](#9251)) ([04dd2c4](04dd2c4)) * EventMetadata class implementation for serialisation ([#9574](#9574)) ([bdff73a](bdff73a)) * Force bb-sanitizers true ([#9614](#9614)) ([39cda86](39cda86)) * **k8s:** Boot node long sync ([#9610](#9610)) ([1b85840](1b85840)) * Multi-node metrics working ([#9486](#9486)) ([fd974e1](fd974e1)) * Remove all register recipient functionality in ts ([#9548](#9548)) ([2f7127b](2f7127b)) * Remove unnecessary ivpk references in ts ([#9463](#9463)) ([0c5121f](0c5121f)) * Resolution of bugs from bigfield audits ([#9547](#9547)) ([feace70](feace70)) * Stop bot in case of tx errors ([#9421](#9421)) ([6650641](6650641)) * Typing of artifacts ([#9581](#9581)) ([c71645f](c71645f)) ### Miscellaneous * Add guides to get_e2e_jobs.sh ([#9624](#9624)) ([8891ead](8891ead)) * Add sender to encode and encrypt ([#9562](#9562)) ([8ce6834](8ce6834)) * Add signed int deserialization to decoder ([#9557](#9557)) ([0435d00](0435d00)) * Bb sanitizers on master ([#9564](#9564)) ([747bff1](747bff1)) * Cleaning up token test utils ([#9633](#9633)) ([325bdb0](325bdb0)) * Disable breaking e2e_event_logs test ([#9602](#9602)) ([cf2ca2e](cf2ca2e)) * Dont generate vks for simulated circuits ([#9625](#9625)) ([366eff3](366eff3)) * Fixing broken sample-dapp tests ([#9597](#9597)) ([5e52900](5e52900)) * Nuking `Token::privately_mint_private_note(...)` ([#9616](#9616)) ([bf53f5e](bf53f5e)) * Pass on docker_fast.sh ([#9615](#9615)) ([1c53459](1c53459)) * Remove outgoing tagging field in logs ([#9502](#9502)) ([c473380](c473380)) * Replace relative paths to noir-protocol-circuits ([288099b](288099b)) * Replacing unshield naming with transfer_to_public ([#9608](#9608)) ([247e9eb](247e9eb)) * Token partial notes refactor pt. 1 ([#9490](#9490)) ([3d631f5](3d631f5)) </details> <details><summary>barretenberg: 0.62.0</summary> ## [0.62.0](barretenberg-v0.61.0...barretenberg-v0.62.0) (2024-11-01) ### ⚠ BREAKING CHANGES * **avm:** use 32 bit locations ([#9596](#9596)) ### Features * **avm:** Use 32 bit locations ([#9596](#9596)) ([5f38696](5f38696)) * Biggroup_goblin handles points at infinity + 1.8x reduction in ECCVM size ([#9366](#9366)) ([9211d8a](9211d8a)) * Faster square roots ([#2694](#2694)) ([722ec5c](722ec5c)) * Spartan proving ([#9584](#9584)) ([392114a](392114a)) ### Bug Fixes * Ensuring translator range constraint polynomials are zeroes outside of minicircuit ([#9251](#9251)) ([04dd2c4](04dd2c4)) * Resolution of bugs from bigfield audits ([#9547](#9547)) ([feace70](feace70)) ### Miscellaneous * Bb sanitizers on master ([#9564](#9564)) ([747bff1](747bff1)) * Pass on docker_fast.sh ([#9615](#9615)) ([1c53459](1c53459)) </details> --- This PR was generated with [Release Please](https://github.com/googleapis/release-please). See [documentation](https://github.com/googleapis/release-please#release-please).
AztecBot
added a commit
to AztecProtocol/barretenberg
that referenced
this pull request
Nov 2, 2024
🤖 I have created a release *beep* *boop* --- <details><summary>aztec-package: 0.62.0</summary> ## [0.62.0](AztecProtocol/aztec-packages@aztec-package-v0.61.0...aztec-package-v0.62.0) (2024-11-01) ### Features * Token private mint optimization ([#9606](AztecProtocol/aztec-packages#9606)) ([e8fadc7](AztecProtocol/aztec-packages@e8fadc7)) ### Bug Fixes * **k8s:** Boot node long sync ([#9610](AztecProtocol/aztec-packages#9610)) ([1b85840](AztecProtocol/aztec-packages@1b85840)) * Multi-node metrics working ([#9486](AztecProtocol/aztec-packages#9486)) ([fd974e1](AztecProtocol/aztec-packages@fd974e1)) * Stop bot in case of tx errors ([#9421](AztecProtocol/aztec-packages#9421)) ([6650641](AztecProtocol/aztec-packages@6650641)) ### Miscellaneous * Replacing unshield naming with transfer_to_public ([#9608](AztecProtocol/aztec-packages#9608)) ([247e9eb](AztecProtocol/aztec-packages@247e9eb)) * Token partial notes refactor pt. 1 ([#9490](AztecProtocol/aztec-packages#9490)) ([3d631f5](AztecProtocol/aztec-packages@3d631f5)) </details> <details><summary>barretenberg.js: 0.62.0</summary> ## [0.62.0](AztecProtocol/aztec-packages@barretenberg.js-v0.61.0...barretenberg.js-v0.62.0) (2024-11-01) ### Features * Faster square roots ([#2694](AztecProtocol/aztec-packages#2694)) ([722ec5c](AztecProtocol/aztec-packages@722ec5c)) </details> <details><summary>aztec-packages: 0.62.0</summary> ## [0.62.0](AztecProtocol/aztec-packages@aztec-packages-v0.61.0...aztec-packages-v0.62.0) (2024-11-01) ### ⚠ BREAKING CHANGES * **avm:** use 32 bit locations ([#9596](AztecProtocol/aztec-packages#9596)) * Unique L1 to L2 messages ([#9492](AztecProtocol/aztec-packages#9492)) ### Features * Add increment secret oracles ([#9573](AztecProtocol/aztec-packages#9573)) ([97a4c0c](AztecProtocol/aztec-packages@97a4c0c)) * **avm:** Use 32 bit locations ([#9596](AztecProtocol/aztec-packages#9596)) ([5f38696](AztecProtocol/aztec-packages@5f38696)) * Barebones addressbook for tagging ([#9572](AztecProtocol/aztec-packages#9572)) ([6526069](AztecProtocol/aztec-packages@6526069)) * Biggroup_goblin handles points at infinity + 1.8x reduction in ECCVM size ([#9366](AztecProtocol/aztec-packages#9366)) ([9211d8a](AztecProtocol/aztec-packages@9211d8a)) * Faster square roots ([#2694](AztecProtocol/aztec-packages#2694)) ([722ec5c](AztecProtocol/aztec-packages@722ec5c)) * Fixed private log size ([#9585](AztecProtocol/aztec-packages#9585)) ([755c70a](AztecProtocol/aztec-packages@755c70a)) * Removing register recipient in e2e tests as it is unnecessary now ! ([#9499](AztecProtocol/aztec-packages#9499)) ([9f52cbb](AztecProtocol/aztec-packages@9f52cbb)) * Reorg test ([#9607](AztecProtocol/aztec-packages#9607)) ([54488b3](AztecProtocol/aztec-packages@54488b3)) * Simulate validateEpochProofQuoteHeader in the future ([#9641](AztecProtocol/aztec-packages#9641)) ([284c8f8](AztecProtocol/aztec-packages@284c8f8)) * Spartan proving ([#9584](AztecProtocol/aztec-packages#9584)) ([392114a](AztecProtocol/aztec-packages@392114a)) * Sync tagged logs ([#9595](AztecProtocol/aztec-packages#9595)) ([0cc4a48](AztecProtocol/aztec-packages@0cc4a48)) * Token private mint optimization ([#9606](AztecProtocol/aztec-packages#9606)) ([e8fadc7](AztecProtocol/aztec-packages@e8fadc7)) * Unique L1 to L2 messages ([#9492](AztecProtocol/aztec-packages#9492)) ([4e5ae95](AztecProtocol/aztec-packages@4e5ae95)), closes [#9450](AztecProtocol/aztec-packages#9450) ### Bug Fixes * E2e event logs test ([#9621](AztecProtocol/aztec-packages#9621)) ([737c573](AztecProtocol/aztec-packages@737c573)) * E2e labels ([#9609](AztecProtocol/aztec-packages#9609)) ([ed1deb9](AztecProtocol/aztec-packages@ed1deb9)) * Ensuring translator range constraint polynomials are zeroes outside of minicircuit ([#9251](AztecProtocol/aztec-packages#9251)) ([04dd2c4](AztecProtocol/aztec-packages@04dd2c4)) * EventMetadata class implementation for serialisation ([#9574](AztecProtocol/aztec-packages#9574)) ([bdff73a](AztecProtocol/aztec-packages@bdff73a)) * Force bb-sanitizers true ([#9614](AztecProtocol/aztec-packages#9614)) ([39cda86](AztecProtocol/aztec-packages@39cda86)) * **k8s:** Boot node long sync ([#9610](AztecProtocol/aztec-packages#9610)) ([1b85840](AztecProtocol/aztec-packages@1b85840)) * Multi-node metrics working ([#9486](AztecProtocol/aztec-packages#9486)) ([fd974e1](AztecProtocol/aztec-packages@fd974e1)) * Remove all register recipient functionality in ts ([#9548](AztecProtocol/aztec-packages#9548)) ([2f7127b](AztecProtocol/aztec-packages@2f7127b)) * Remove unnecessary ivpk references in ts ([#9463](AztecProtocol/aztec-packages#9463)) ([0c5121f](AztecProtocol/aztec-packages@0c5121f)) * Resolution of bugs from bigfield audits ([#9547](AztecProtocol/aztec-packages#9547)) ([feace70](AztecProtocol/aztec-packages@feace70)) * Stop bot in case of tx errors ([#9421](AztecProtocol/aztec-packages#9421)) ([6650641](AztecProtocol/aztec-packages@6650641)) * Typing of artifacts ([#9581](AztecProtocol/aztec-packages#9581)) ([c71645f](AztecProtocol/aztec-packages@c71645f)) ### Miscellaneous * Add guides to get_e2e_jobs.sh ([#9624](AztecProtocol/aztec-packages#9624)) ([8891ead](AztecProtocol/aztec-packages@8891ead)) * Add sender to encode and encrypt ([#9562](AztecProtocol/aztec-packages#9562)) ([8ce6834](AztecProtocol/aztec-packages@8ce6834)) * Add signed int deserialization to decoder ([#9557](AztecProtocol/aztec-packages#9557)) ([0435d00](AztecProtocol/aztec-packages@0435d00)) * Bb sanitizers on master ([#9564](AztecProtocol/aztec-packages#9564)) ([747bff1](AztecProtocol/aztec-packages@747bff1)) * Cleaning up token test utils ([#9633](AztecProtocol/aztec-packages#9633)) ([325bdb0](AztecProtocol/aztec-packages@325bdb0)) * Disable breaking e2e_event_logs test ([#9602](AztecProtocol/aztec-packages#9602)) ([cf2ca2e](AztecProtocol/aztec-packages@cf2ca2e)) * Dont generate vks for simulated circuits ([#9625](AztecProtocol/aztec-packages#9625)) ([366eff3](AztecProtocol/aztec-packages@366eff3)) * Fixing broken sample-dapp tests ([#9597](AztecProtocol/aztec-packages#9597)) ([5e52900](AztecProtocol/aztec-packages@5e52900)) * Nuking `Token::privately_mint_private_note(...)` ([#9616](AztecProtocol/aztec-packages#9616)) ([bf53f5e](AztecProtocol/aztec-packages@bf53f5e)) * Pass on docker_fast.sh ([#9615](AztecProtocol/aztec-packages#9615)) ([1c53459](AztecProtocol/aztec-packages@1c53459)) * Remove outgoing tagging field in logs ([#9502](AztecProtocol/aztec-packages#9502)) ([c473380](AztecProtocol/aztec-packages@c473380)) * Replace relative paths to noir-protocol-circuits ([288099b](AztecProtocol/aztec-packages@288099b)) * Replacing unshield naming with transfer_to_public ([#9608](AztecProtocol/aztec-packages#9608)) ([247e9eb](AztecProtocol/aztec-packages@247e9eb)) * Token partial notes refactor pt. 1 ([#9490](AztecProtocol/aztec-packages#9490)) ([3d631f5](AztecProtocol/aztec-packages@3d631f5)) </details> <details><summary>barretenberg: 0.62.0</summary> ## [0.62.0](AztecProtocol/aztec-packages@barretenberg-v0.61.0...barretenberg-v0.62.0) (2024-11-01) ### ⚠ BREAKING CHANGES * **avm:** use 32 bit locations ([#9596](AztecProtocol/aztec-packages#9596)) ### Features * **avm:** Use 32 bit locations ([#9596](AztecProtocol/aztec-packages#9596)) ([5f38696](AztecProtocol/aztec-packages@5f38696)) * Biggroup_goblin handles points at infinity + 1.8x reduction in ECCVM size ([#9366](AztecProtocol/aztec-packages#9366)) ([9211d8a](AztecProtocol/aztec-packages@9211d8a)) * Faster square roots ([#2694](AztecProtocol/aztec-packages#2694)) ([722ec5c](AztecProtocol/aztec-packages@722ec5c)) * Spartan proving ([#9584](AztecProtocol/aztec-packages#9584)) ([392114a](AztecProtocol/aztec-packages@392114a)) ### Bug Fixes * Ensuring translator range constraint polynomials are zeroes outside of minicircuit ([#9251](AztecProtocol/aztec-packages#9251)) ([04dd2c4](AztecProtocol/aztec-packages@04dd2c4)) * Resolution of bugs from bigfield audits ([#9547](AztecProtocol/aztec-packages#9547)) ([feace70](AztecProtocol/aztec-packages@feace70)) ### Miscellaneous * Bb sanitizers on master ([#9564](AztecProtocol/aztec-packages#9564)) ([747bff1](AztecProtocol/aztec-packages@747bff1)) * Pass on docker_fast.sh ([#9615](AztecProtocol/aztec-packages#9615)) ([1c53459](AztecProtocol/aztec-packages@1c53459)) </details> --- This PR was generated with [Release Please](https://github.com/googleapis/release-please). See [documentation](https://github.com/googleapis/release-please#release-please).
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This PR adds support for biggroup_goblin handling elliptic curve points at infinity
This feature is used to optimize the ECCVM instructions created when running a recursive protogalaxy verifier.
Instead of performing size-2 scalar multiplications for every witness/commitment, additional random challenges are generated in order to evaluate two large batch multiplications.
The technique implemented is described in https://hackmd.io/T1239dufTgO1v8Ie7EExlQ?view
In the case of ClientIVCRecursionTests.ClientTubeBase where the number of circuits is set to four, this reduces the size of the ECCVM execution trace size by 45%, which is good enough to reduce the log dyadic size of the ClientIVCVerifier by 1/2.