feat: Protogalaxy Decider and complete folding tests #3657

maramihali · 2023-12-12T12:59:57Z

This PR introduces the Protogalaxy decider, now having a complete proof of concept of the folding protocol for Ultra instances. To enable this, sumcheck has been modified to work with the same power polynomial as in protogalaxy paper and can be initialised with a custom target_sum. Moreover, we now use different batching challenges for each subrelation in sumcheck, essential to ensure a reasonable degree of the combiner polynomial.

Additional: Minor bug fixed in the computation of \vec{\beta*}.

Resolves AztecProtocol/barretenberg#772.
Resolves AztecProtocol/barretenberg#691.

Checklist:

Remove the checklist to signal you've completed it. Enable auto-merge if the PR is ready to merge.

If the pull request requires a cryptography review (e.g. cryptographic algorithm implementations) I have added the 'crypto' tag.
I have reviewed my diff in github, line by line and removed unexpected formatting changes, testing logs, or commented-out code.
Every change is related to the PR description.
I have linked this pull request to relevant issues (if any exist).

maramihali · 2024-01-08T17:17:10Z

.circleci/config.yml

@@ -240,17 +240,6 @@ jobs:
          name: "Test"
          command: cond_spot_run_test barretenberg-x86_64-linux-clang-assert 32 ./scripts/bb-tests.sh



we don't have honk_tests anymore

codygunton

Leaving a partial review at EOD so you have the choice to work on this tomorrow.

barretenberg/cpp/src/barretenberg/polynomials/pow.hpp

codygunton · 2024-01-08T22:26:19Z

barretenberg/cpp/src/barretenberg/polynomials/pow.hpp

 namespace barretenberg {

 /**
 * @brief Succinct representation of the `pow` polynomial that can be partially evaluated variable-by-variable.
- * pow(X) = ∏_{0≤l<d} ((1−X_l) + X_l⋅ζ_l)
+ * pow(X_0,X_1,..,X_d) = \prod_{0≤l<d} ((1−X_l) + X_l⋅β_l) for a vector {β_0,...,β_{d-1}}
 *
 * @details Let


Could you add a sentences saying you're describing sumcheck?

codygunton · 2024-01-08T22:29:32Z

barretenberg/cpp/src/barretenberg/polynomials/pow.hpp

- *   We can also see it as the multi-linear extension of the vector (1, ζ, ζ², ...).
+ * - pow(X) = ∏_{0≤l<d} ((1−X_l) + X_l⋅β_l) is the multilinear polynomial whose evaluation at the i-th index
+ *   of the full hypercube, equals ∏ β_j where j are the bits set to 1 in the binary representation of i
+ *   We can also see it as the multi-linear extension of the vector \vec{β}.
 *
 * - At round l, we iterate over all remaining vertices (i_{l+1}, ..., i_{d-1}) ∈ {0,1}^{d-l-1}.


Round 0: $2^d = 2^{d-0}$ vertices.
Round 1: $(2^d)/2 = 2^{d-1}$ vertices
...
Round $\ell$: $2^{d-\ell}$ vertices, right? Are you off by one?

Also: I find this a little confusing. You're taking about sumcheck right? Rather than "remaining vertices" I'd just say we iterate over a boolean hypercube of $\dim$ $(d-l)$ (this is naturally a subcube of the full $\dim$ $d$ one). Based on how the execution trace fold, it's more like 'the start' of the full cube. -- or convince me otherwise!

Remaining vertices was a term already in the description, but your suggestion is definitely better, thanks, Also the off by one was in master but yeah it is an off by one

Tried to further clarify things.

codygunton

Part 2

barretenberg/cpp/src/barretenberg/polynomials/pow.hpp

barretenberg/cpp/src/barretenberg/sumcheck/instance/prover_instance.hpp

barretenberg/cpp/src/barretenberg/protogalaxy/protogalaxy_prover.hpp

barretenberg/cpp/src/barretenberg/protogalaxy/protogalaxy_verifier.cpp

barretenberg/cpp/src/barretenberg/protogalaxy/decider_verifier.cpp

barretenberg/cpp/src/barretenberg/protogalaxy/decider_prover.cpp

codygunton · 2024-01-09T20:08:44Z

barretenberg/cpp/src/barretenberg/sumcheck/sumcheck_round.hpp

    {
-        // Precompute the vector of required powers of zeta
-        // TODO(luke): Parallelize this
+        // Compute the constant contribution of pow polynomials for each edge as the product of c_l and the elements of


Can you add more to this comment? Seems like it would be helpful but I'm still confused e.g. c_l is not very explicitly defined anywhere.

c_l (the notation was already there) is the partial_evaluation_result in the pow polynomial. I renamed it from partial_evaluation_constant to partial_evaluation_result since it's not a constant, it gets updated at every round. Updated the comment

🤖 I have created a release *beep* *boop* --- <details><summary>aztec-packages: 0.18.0</summary> ## [0.18.0](aztec-packages-v0.17.0...aztec-packages-v0.18.0) (2024-01-16) ### ⚠ BREAKING CHANGES * Remove `Directive::Quotient` ([#4019](#4019)) * define key type in maps ([#3841](#3841)) * implement keccakf1600 in brillig ([#3914](#3914)) * add blake3 opcode to brillig ([#3913](#3913)) * Remove opcode supported from the backend ([#3889](#3889)) ### Features * `PartialStateReference` and `StateReference` structs ([#3827](#3827)) ([3ba0369](3ba0369)) * `StateDiffHints` ([#3919](#3919)) ([8774795](8774795)), closes [#3916](#3916) * Acir cleanup ([#3845](#3845)) ([390b84c](390b84c)) * Add ACIR opcodes for ECADD and ECDOUBLE ([#3878](#3878)) ([537630f](537630f)) * Add blake3 opcode to brillig ([#3913](#3913)) ([34fad0a](34fad0a)) * Add data availability oracle ([#3897](#3897)) ([5441753](5441753)), closes [#3890](#3890) * Add str support for args + add name/symbol/decimal to token ([#3862](#3862)) ([0bf5d8c](0bf5d8c)) * Bench bb in pr's, docker shell utils ([#3561](#3561)) ([5408919](5408919)) * Benchmark protogalaxy prover ([#3958](#3958)) ([5843722](5843722)) * Benchmarks for basic functionality and IPA improvements ([#4004](#4004)) ([fd1f619](fd1f619)) * Body hash as buffer in TS + minor cleanup ([#4012](#4012)) ([e28a6bf](e28a6bf)) * Bootstrap cache v2 ([#3876](#3876)) ([331598d](331598d)) * Counters in private functions ([#3850](#3850)) ([23bbf75](23bbf75)) * Generate json blocks for tests ([#3923](#3923)) ([a09fd2a](a09fd2a)) * Implement keccakf1600 in brillig ([#3914](#3914)) ([a182381](a182381)) * Parallel IPA ([#3882](#3882)) ([7002a33](7002a33)) * Pil lookups w/ xor table example ([#3880](#3880)) ([544d24e](544d24e)) * Poseidon2 stdlib impl ([#3551](#3551)) ([50b4a72](50b4a72)) * Protogalaxy Decider and complete folding tests ([#3657](#3657)) ([cfdaf9c](cfdaf9c)) * Reexport `protocol_types` from `aztec-nr` ([#3926](#3926)) ([9bd22f7](9bd22f7)) * Relations vs widgets benchmarking ([#3931](#3931)) ([3af64ef](3af64ef)) * Remove opcode supported from the backend ([#3889](#3889)) ([1fd135c](1fd135c)) * Reorganize acir composer ([#3957](#3957)) ([e6232e8](e6232e8)) * Replace bitwise ORs in `U256:from_bytes32` with addition ([#3947](#3947)) ([efd7660](efd7660)) * Standalone calldata test ([#3842](#3842)) ([7353a35](7353a35)) * Sync with main noir repo ([#3939](#3939)) ([69c7e99](69c7e99)) * Update noir ([#3979](#3979)) ([271de71](271de71)) * Verify state hash is correct before publishing to L1 ([#3915](#3915)) ([a53c261](a53c261)) ### Bug Fixes * **aztec-nr:** Broken nargo url ([#3925](#3925)) ([034bc30](034bc30)) * Back out the buggy branch condition ([#3988](#3988)) ([9f61ed1](9f61ed1)) * Bb unnecessary env var ([#3901](#3901)) ([f127e5a](f127e5a)) * Broken links by paterson1 ([#3902](#3902)) ([6783aaa](6783aaa)) * **cli:** Unbox command should run as release ([#3974](#3974)) ([80c3805](80c3805)) * **cli:** Unbox should set up the accounts package ([#3972](#3972)) ([065e988](065e988)) * Docusaurus start command ([#3968](#3968)) ([87c0b07](87c0b07)) * Dont spam logs with yarn install ([#4027](#4027)) ([949c5ab](949c5ab)) * Fix compilation of `token` box ([#3981](#3981)) ([0f994d0](0f994d0)) * Mirror_noir_subrepo.yml erroring ([#3954](#3954)) ([2ac1b9c](2ac1b9c)) * Quote the glob string for ignore branches for protocol-circuits-gate-diff ([#3990](#3990)) ([a43889d](a43889d)) * Reprocess notes in pxe when a new contract is added ([#3867](#3867)) ([ccbff99](ccbff99)) * Segment tree insertion stats by depth ([#4029](#4029)) ([2787bae](2787bae)) * Store blockhash alongside blocks ([#3950](#3950)) ([12b07fa](12b07fa)), closes [#3870](#3870) * Swap branch exclusion for release-please on report gates diff workflow ([#3994](#3994)) ([70b2ffd](70b2ffd)) * Typos in authwit.md by czepluch ([#3921](#3921)) ([4b9d0f4](4b9d0f4)) * Yellowpaper docusaurus start command ([#3969](#3969)) ([4977cbc](4977cbc)) ### Miscellaneous * Add a link back to `aztec-packages` in noir sync PR ([#4018](#4018)) ([7d89f3b](7d89f3b)) * Catch up note processors could be synced more efficiently ([#3933](#3933)) ([df54f33](df54f33)) * **ci:** Require boxes CI to succeed ([#3983](#3983)) ([93cbea1](93cbea1)) * Cleanup duplicated methods for structs after traits ([#3912](#3912)) ([60b59da](60b59da)) * Cleanup sandbox dependent tests ([#3861](#3861)) ([158c5be](158c5be)) * Codegen acir opcodes after renaming arithmetic to assertzero ([#3896](#3896)) ([c710ce1](c710ce1)) * Define key type in maps ([#3841](#3841)) ([cf15adb](cf15adb)) * Delete the compiler from `noir-compiler` ([#3959](#3959)) ([9aa0986](9aa0986)) * Deploy canary release of bb.js to npm via CCI ([#3917](#3917)) ([bdeb10c](bdeb10c)) * Do not fail jq dependencies check for package with no deps ([#3894](#3894)) ([22c65bf](22c65bf)) * Do not pass redundant txNullifier when computing notes ([#3943](#3943)) ([9355cda](9355cda)) * Do not run CCI on release-please branches ([#3984](#3984)) ([c38dbd2](c38dbd2)) * **docs:** Fix ts code in token bridge tutorial ([#3888](#3888)) ([f53f8ed](f53f8ed)) * **docs:** Move map keys to new release in migration guide ([#3977](#3977)) ([6356d94](6356d94)) * **docs:** Update missing @aztec/accounts missing import in testing.md ([#3903](#3903)) ([755668a](755668a)) * Document `witness_buf_to_witness_data` ([#3940](#3940)) ([fbaa726](fbaa726)) * End to end test node & pxe persistence ([#3911](#3911)) ([6164ccd](6164ccd)) * Enforce immutable yarn installs in CI ([#3964](#3964)) ([f3104ac](f3104ac)) * Fix rust tests ([#3963](#3963)) ([a907c3b](a907c3b)) * Fix sidebar index links ([#3942](#3942)) ([984f1f8](984f1f8)) * Git subrepo commit (merge) noir ([#3955](#3955)) ([2c2bc69](2c2bc69)) * Introduce EventSelector class ([#3960](#3960)) ([7315f2c](7315f2c)) * Investigate P2P test ([#3929](#3929)) ([0fca2c4](0fca2c4)) * Move types to circuit-types ([#3967](#3967)) ([f81b7c0](f81b7c0)) * Persistence uses TokenContract ([#3930](#3930)) ([1a052c4](1a052c4)) * Pull in noir from upstream ([#3904](#3904)) ([ab07e7e](ab07e7e)) * Recreated types package without circuits.js dependency ([#3970](#3970)) ([fc1d539](fc1d539)) * Refactor serialisation functions and sibling paths ([#3980](#3980)) ([1a936fc](1a936fc)) * Remove 'extern template's, expand macros ([#3953](#3953)) ([5fe9908](5fe9908)) * Remove `Directive::Quotient` ([#4019](#4019)) ([824d76f](824d76f)) * Remove sandbox and cli npm pkgs ([#3567](#3567)) ([a8cf1bf](a8cf1bf)) * Reorganize benchmarks ([#3909](#3909)) ([730766b](730766b)) * Replace `AztecU128` with `U128` ([#3951](#3951)) ([e3b288d](e3b288d)) * Replace relative paths to noir-protocol-circuits ([2c25f04](2c25f04)) * Replace relative paths to noir-protocol-circuits ([0c8b770](0c8b770)) * Replace relative paths to noir-protocol-circuits ([d3819ba](d3819ba)) * Standardise toml parsers ([#3910](#3910)) ([963035f](963035f)) * Sync noir ([#4025](#4025)) ([4e90d7b](4e90d7b)) * Sync Noir repo ([#4020](#4020)) ([876603e](876603e)) * **yellowpaper:** Cleanup avm sidebar, fix filename case ([#3952](#3952)) ([5211060](5211060)) * Yp docs sidebar (with some auto-formatting) ([#3893](#3893)) ([f7b007a](f7b007a)) ### Documentation * Noir git subrepo usage ([#3962](#3962)) ([2e4c9de](2e4c9de)) * Streamlined pr template ([#3932](#3932)) ([5ec1559](5ec1559)) * **yellowpaper:** Avm call pointers, bytecode lookups, circuit io ([#3898](#3898)) ([45e1ed2](45e1ed2)) * **yellowpaper:** Avm circuit architecture ([#3934](#3934)) ([6aed1d0](6aed1d0)) * **yellowpaper:** First draft of avm circuit memory ([#3865](#3865)) ([f689297](f689297)) * **yellowpaper:** Logs ([#4016](#4016)) ([d734c79](d734c79)) * **yellowpaper:** Update AVM spec for with "daGasLeft", some cleanup ([#3956](#3956)) ([a9537fb](a9537fb)) </details> <details><summary>barretenberg.js: 0.18.0</summary> ## [0.18.0](barretenberg.js-v0.17.0...barretenberg.js-v0.18.0) (2024-01-16) ### Features * Bootstrap cache v2 ([#3876](#3876)) ([331598d](331598d)) ### Bug Fixes * Dont spam logs with yarn install ([#4027](#4027)) ([949c5ab](949c5ab)) </details> <details><summary>barretenberg: 0.18.0</summary> ## [0.18.0](barretenberg-v0.17.0...barretenberg-v0.18.0) (2024-01-16) ### ⚠ BREAKING CHANGES * Remove `Directive::Quotient` ([#4019](#4019)) * implement keccakf1600 in brillig ([#3914](#3914)) * add blake3 opcode to brillig ([#3913](#3913)) * Remove opcode supported from the backend ([#3889](#3889)) ### Features * Acir cleanup ([#3845](#3845)) ([390b84c](390b84c)) * Add ACIR opcodes for ECADD and ECDOUBLE ([#3878](#3878)) ([537630f](537630f)) * Add blake3 opcode to brillig ([#3913](#3913)) ([34fad0a](34fad0a)) * Bench bb in pr's, docker shell utils ([#3561](#3561)) ([5408919](5408919)) * Benchmark protogalaxy prover ([#3958](#3958)) ([5843722](5843722)) * Benchmarks for basic functionality and IPA improvements ([#4004](#4004)) ([fd1f619](fd1f619)) * Bootstrap cache v2 ([#3876](#3876)) ([331598d](331598d)) * Implement keccakf1600 in brillig ([#3914](#3914)) ([a182381](a182381)) * Parallel IPA ([#3882](#3882)) ([7002a33](7002a33)) * Pil lookups w/ xor table example ([#3880](#3880)) ([544d24e](544d24e)) * Poseidon2 stdlib impl ([#3551](#3551)) ([50b4a72](50b4a72)) * Protogalaxy Decider and complete folding tests ([#3657](#3657)) ([cfdaf9c](cfdaf9c)) * Relations vs widgets benchmarking ([#3931](#3931)) ([3af64ef](3af64ef)) * Remove opcode supported from the backend ([#3889](#3889)) ([1fd135c](1fd135c)) * Reorganize acir composer ([#3957](#3957)) ([e6232e8](e6232e8)) * Standalone calldata test ([#3842](#3842)) ([7353a35](7353a35)) ### Bug Fixes * Bb unnecessary env var ([#3901](#3901)) ([f127e5a](f127e5a)) ### Miscellaneous * Codegen acir opcodes after renaming arithmetic to assertzero ([#3896](#3896)) ([c710ce1](c710ce1)) * Document `witness_buf_to_witness_data` ([#3940](#3940)) ([fbaa726](fbaa726)) * Remove 'extern template's, expand macros ([#3953](#3953)) ([5fe9908](5fe9908)) * Remove `Directive::Quotient` ([#4019](#4019)) ([824d76f](824d76f)) * Reorganize benchmarks ([#3909](#3909)) ([730766b](730766b)) </details> --- This PR was generated with [Release Please](https://github.com/googleapis/release-please). See [documentation](https://github.com/googleapis/release-please#release-please).

🤖 I have created a release *beep* *boop* --- <details><summary>aztec-packages: 0.18.0</summary> ## [0.18.0](AztecProtocol/aztec-packages@aztec-packages-v0.17.0...aztec-packages-v0.18.0) (2024-01-16) ### ⚠ BREAKING CHANGES * Remove `Directive::Quotient` ([#4019](AztecProtocol/aztec-packages#4019)) * define key type in maps ([#3841](AztecProtocol/aztec-packages#3841)) * implement keccakf1600 in brillig ([#3914](AztecProtocol/aztec-packages#3914)) * add blake3 opcode to brillig ([#3913](AztecProtocol/aztec-packages#3913)) * Remove opcode supported from the backend ([#3889](AztecProtocol/aztec-packages#3889)) ### Features * `PartialStateReference` and `StateReference` structs ([#3827](AztecProtocol/aztec-packages#3827)) ([3ba0369](AztecProtocol/aztec-packages@3ba0369)) * `StateDiffHints` ([#3919](AztecProtocol/aztec-packages#3919)) ([8774795](AztecProtocol/aztec-packages@8774795)), closes [#3916](AztecProtocol/aztec-packages#3916) * Acir cleanup ([#3845](AztecProtocol/aztec-packages#3845)) ([390b84c](AztecProtocol/aztec-packages@390b84c)) * Add ACIR opcodes for ECADD and ECDOUBLE ([#3878](AztecProtocol/aztec-packages#3878)) ([537630f](AztecProtocol/aztec-packages@537630f)) * Add blake3 opcode to brillig ([#3913](AztecProtocol/aztec-packages#3913)) ([34fad0a](AztecProtocol/aztec-packages@34fad0a)) * Add data availability oracle ([#3897](AztecProtocol/aztec-packages#3897)) ([5441753](AztecProtocol/aztec-packages@5441753)), closes [#3890](AztecProtocol/aztec-packages#3890) * Add str support for args + add name/symbol/decimal to token ([#3862](AztecProtocol/aztec-packages#3862)) ([0bf5d8c](AztecProtocol/aztec-packages@0bf5d8c)) * Bench bb in pr's, docker shell utils ([#3561](AztecProtocol/aztec-packages#3561)) ([5408919](AztecProtocol/aztec-packages@5408919)) * Benchmark protogalaxy prover ([#3958](AztecProtocol/aztec-packages#3958)) ([5843722](AztecProtocol/aztec-packages@5843722)) * Benchmarks for basic functionality and IPA improvements ([#4004](AztecProtocol/aztec-packages#4004)) ([fd1f619](AztecProtocol/aztec-packages@fd1f619)) * Body hash as buffer in TS + minor cleanup ([#4012](AztecProtocol/aztec-packages#4012)) ([e28a6bf](AztecProtocol/aztec-packages@e28a6bf)) * Bootstrap cache v2 ([#3876](AztecProtocol/aztec-packages#3876)) ([331598d](AztecProtocol/aztec-packages@331598d)) * Counters in private functions ([#3850](AztecProtocol/aztec-packages#3850)) ([23bbf75](AztecProtocol/aztec-packages@23bbf75)) * Generate json blocks for tests ([#3923](AztecProtocol/aztec-packages#3923)) ([a09fd2a](AztecProtocol/aztec-packages@a09fd2a)) * Implement keccakf1600 in brillig ([#3914](AztecProtocol/aztec-packages#3914)) ([a182381](AztecProtocol/aztec-packages@a182381)) * Parallel IPA ([#3882](AztecProtocol/aztec-packages#3882)) ([7002a33](AztecProtocol/aztec-packages@7002a33)) * Pil lookups w/ xor table example ([#3880](AztecProtocol/aztec-packages#3880)) ([544d24e](AztecProtocol/aztec-packages@544d24e)) * Poseidon2 stdlib impl ([#3551](AztecProtocol/aztec-packages#3551)) ([50b4a72](AztecProtocol/aztec-packages@50b4a72)) * Protogalaxy Decider and complete folding tests ([#3657](AztecProtocol/aztec-packages#3657)) ([cfdaf9c](AztecProtocol/aztec-packages@cfdaf9c)) * Reexport `protocol_types` from `aztec-nr` ([#3926](AztecProtocol/aztec-packages#3926)) ([9bd22f7](AztecProtocol/aztec-packages@9bd22f7)) * Relations vs widgets benchmarking ([#3931](AztecProtocol/aztec-packages#3931)) ([3af64ef](AztecProtocol/aztec-packages@3af64ef)) * Remove opcode supported from the backend ([#3889](AztecProtocol/aztec-packages#3889)) ([1fd135c](AztecProtocol/aztec-packages@1fd135c)) * Reorganize acir composer ([#3957](AztecProtocol/aztec-packages#3957)) ([e6232e8](AztecProtocol/aztec-packages@e6232e8)) * Replace bitwise ORs in `U256:from_bytes32` with addition ([#3947](AztecProtocol/aztec-packages#3947)) ([efd7660](AztecProtocol/aztec-packages@efd7660)) * Standalone calldata test ([#3842](AztecProtocol/aztec-packages#3842)) ([7353a35](AztecProtocol/aztec-packages@7353a35)) * Sync with main noir repo ([#3939](AztecProtocol/aztec-packages#3939)) ([69c7e99](AztecProtocol/aztec-packages@69c7e99)) * Update noir ([#3979](AztecProtocol/aztec-packages#3979)) ([271de71](AztecProtocol/aztec-packages@271de71)) * Verify state hash is correct before publishing to L1 ([#3915](AztecProtocol/aztec-packages#3915)) ([a53c261](AztecProtocol/aztec-packages@a53c261)) ### Bug Fixes * **aztec-nr:** Broken nargo url ([#3925](AztecProtocol/aztec-packages#3925)) ([034bc30](AztecProtocol/aztec-packages@034bc30)) * Back out the buggy branch condition ([#3988](AztecProtocol/aztec-packages#3988)) ([9f61ed1](AztecProtocol/aztec-packages@9f61ed1)) * Bb unnecessary env var ([#3901](AztecProtocol/aztec-packages#3901)) ([f127e5a](AztecProtocol/aztec-packages@f127e5a)) * Broken links by paterson1 ([#3902](AztecProtocol/aztec-packages#3902)) ([6783aaa](AztecProtocol/aztec-packages@6783aaa)) * **cli:** Unbox command should run as release ([#3974](AztecProtocol/aztec-packages#3974)) ([80c3805](AztecProtocol/aztec-packages@80c3805)) * **cli:** Unbox should set up the accounts package ([#3972](AztecProtocol/aztec-packages#3972)) ([065e988](AztecProtocol/aztec-packages@065e988)) * Docusaurus start command ([#3968](AztecProtocol/aztec-packages#3968)) ([87c0b07](AztecProtocol/aztec-packages@87c0b07)) * Dont spam logs with yarn install ([#4027](AztecProtocol/aztec-packages#4027)) ([949c5ab](AztecProtocol/aztec-packages@949c5ab)) * Fix compilation of `token` box ([#3981](AztecProtocol/aztec-packages#3981)) ([0f994d0](AztecProtocol/aztec-packages@0f994d0)) * Mirror_noir_subrepo.yml erroring ([#3954](AztecProtocol/aztec-packages#3954)) ([2ac1b9c](AztecProtocol/aztec-packages@2ac1b9c)) * Quote the glob string for ignore branches for protocol-circuits-gate-diff ([#3990](AztecProtocol/aztec-packages#3990)) ([a43889d](AztecProtocol/aztec-packages@a43889d)) * Reprocess notes in pxe when a new contract is added ([#3867](AztecProtocol/aztec-packages#3867)) ([ccbff99](AztecProtocol/aztec-packages@ccbff99)) * Segment tree insertion stats by depth ([#4029](AztecProtocol/aztec-packages#4029)) ([2787bae](AztecProtocol/aztec-packages@2787bae)) * Store blockhash alongside blocks ([#3950](AztecProtocol/aztec-packages#3950)) ([12b07fa](AztecProtocol/aztec-packages@12b07fa)), closes [#3870](AztecProtocol/aztec-packages#3870) * Swap branch exclusion for release-please on report gates diff workflow ([#3994](AztecProtocol/aztec-packages#3994)) ([70b2ffd](AztecProtocol/aztec-packages@70b2ffd)) * Typos in authwit.md by czepluch ([#3921](AztecProtocol/aztec-packages#3921)) ([4b9d0f4](AztecProtocol/aztec-packages@4b9d0f4)) * Yellowpaper docusaurus start command ([#3969](AztecProtocol/aztec-packages#3969)) ([4977cbc](AztecProtocol/aztec-packages@4977cbc)) ### Miscellaneous * Add a link back to `aztec-packages` in noir sync PR ([#4018](AztecProtocol/aztec-packages#4018)) ([7d89f3b](AztecProtocol/aztec-packages@7d89f3b)) * Catch up note processors could be synced more efficiently ([#3933](AztecProtocol/aztec-packages#3933)) ([df54f33](AztecProtocol/aztec-packages@df54f33)) * **ci:** Require boxes CI to succeed ([#3983](AztecProtocol/aztec-packages#3983)) ([93cbea1](AztecProtocol/aztec-packages@93cbea1)) * Cleanup duplicated methods for structs after traits ([#3912](AztecProtocol/aztec-packages#3912)) ([60b59da](AztecProtocol/aztec-packages@60b59da)) * Cleanup sandbox dependent tests ([#3861](AztecProtocol/aztec-packages#3861)) ([158c5be](AztecProtocol/aztec-packages@158c5be)) * Codegen acir opcodes after renaming arithmetic to assertzero ([#3896](AztecProtocol/aztec-packages#3896)) ([c710ce1](AztecProtocol/aztec-packages@c710ce1)) * Define key type in maps ([#3841](AztecProtocol/aztec-packages#3841)) ([cf15adb](AztecProtocol/aztec-packages@cf15adb)) * Delete the compiler from `noir-compiler` ([#3959](AztecProtocol/aztec-packages#3959)) ([9aa0986](AztecProtocol/aztec-packages@9aa0986)) * Deploy canary release of bb.js to npm via CCI ([#3917](AztecProtocol/aztec-packages#3917)) ([bdeb10c](AztecProtocol/aztec-packages@bdeb10c)) * Do not fail jq dependencies check for package with no deps ([#3894](AztecProtocol/aztec-packages#3894)) ([22c65bf](AztecProtocol/aztec-packages@22c65bf)) * Do not pass redundant txNullifier when computing notes ([#3943](AztecProtocol/aztec-packages#3943)) ([9355cda](AztecProtocol/aztec-packages@9355cda)) * Do not run CCI on release-please branches ([#3984](AztecProtocol/aztec-packages#3984)) ([c38dbd2](AztecProtocol/aztec-packages@c38dbd2)) * **docs:** Fix ts code in token bridge tutorial ([#3888](AztecProtocol/aztec-packages#3888)) ([f53f8ed](AztecProtocol/aztec-packages@f53f8ed)) * **docs:** Move map keys to new release in migration guide ([#3977](AztecProtocol/aztec-packages#3977)) ([6356d94](AztecProtocol/aztec-packages@6356d94)) * **docs:** Update missing @aztec/accounts missing import in testing.md ([#3903](AztecProtocol/aztec-packages#3903)) ([755668a](AztecProtocol/aztec-packages@755668a)) * Document `witness_buf_to_witness_data` ([#3940](AztecProtocol/aztec-packages#3940)) ([fbaa726](AztecProtocol/aztec-packages@fbaa726)) * End to end test node & pxe persistence ([#3911](AztecProtocol/aztec-packages#3911)) ([6164ccd](AztecProtocol/aztec-packages@6164ccd)) * Enforce immutable yarn installs in CI ([#3964](AztecProtocol/aztec-packages#3964)) ([f3104ac](AztecProtocol/aztec-packages@f3104ac)) * Fix rust tests ([#3963](AztecProtocol/aztec-packages#3963)) ([a907c3b](AztecProtocol/aztec-packages@a907c3b)) * Fix sidebar index links ([#3942](AztecProtocol/aztec-packages#3942)) ([984f1f8](AztecProtocol/aztec-packages@984f1f8)) * Git subrepo commit (merge) noir ([#3955](AztecProtocol/aztec-packages#3955)) ([2c2bc69](AztecProtocol/aztec-packages@2c2bc69)) * Introduce EventSelector class ([#3960](AztecProtocol/aztec-packages#3960)) ([7315f2c](AztecProtocol/aztec-packages@7315f2c)) * Investigate P2P test ([#3929](AztecProtocol/aztec-packages#3929)) ([0fca2c4](AztecProtocol/aztec-packages@0fca2c4)) * Move types to circuit-types ([#3967](AztecProtocol/aztec-packages#3967)) ([f81b7c0](AztecProtocol/aztec-packages@f81b7c0)) * Persistence uses TokenContract ([#3930](AztecProtocol/aztec-packages#3930)) ([1a052c4](AztecProtocol/aztec-packages@1a052c4)) * Pull in noir from upstream ([#3904](AztecProtocol/aztec-packages#3904)) ([ab07e7e](AztecProtocol/aztec-packages@ab07e7e)) * Recreated types package without circuits.js dependency ([#3970](AztecProtocol/aztec-packages#3970)) ([fc1d539](AztecProtocol/aztec-packages@fc1d539)) * Refactor serialisation functions and sibling paths ([#3980](AztecProtocol/aztec-packages#3980)) ([1a936fc](AztecProtocol/aztec-packages@1a936fc)) * Remove 'extern template's, expand macros ([#3953](AztecProtocol/aztec-packages#3953)) ([5fe9908](AztecProtocol/aztec-packages@5fe9908)) * Remove `Directive::Quotient` ([#4019](AztecProtocol/aztec-packages#4019)) ([824d76f](AztecProtocol/aztec-packages@824d76f)) * Remove sandbox and cli npm pkgs ([#3567](AztecProtocol/aztec-packages#3567)) ([a8cf1bf](AztecProtocol/aztec-packages@a8cf1bf)) * Reorganize benchmarks ([#3909](AztecProtocol/aztec-packages#3909)) ([730766b](AztecProtocol/aztec-packages@730766b)) * Replace `AztecU128` with `U128` ([#3951](AztecProtocol/aztec-packages#3951)) ([e3b288d](AztecProtocol/aztec-packages@e3b288d)) * Replace relative paths to noir-protocol-circuits ([2c25f04](AztecProtocol/aztec-packages@2c25f04)) * Replace relative paths to noir-protocol-circuits ([0c8b770](AztecProtocol/aztec-packages@0c8b770)) * Replace relative paths to noir-protocol-circuits ([d3819ba](AztecProtocol/aztec-packages@d3819ba)) * Standardise toml parsers ([#3910](AztecProtocol/aztec-packages#3910)) ([963035f](AztecProtocol/aztec-packages@963035f)) * Sync noir ([#4025](AztecProtocol/aztec-packages#4025)) ([4e90d7b](AztecProtocol/aztec-packages@4e90d7b)) * Sync Noir repo ([#4020](AztecProtocol/aztec-packages#4020)) ([876603e](AztecProtocol/aztec-packages@876603e)) * **yellowpaper:** Cleanup avm sidebar, fix filename case ([#3952](AztecProtocol/aztec-packages#3952)) ([5211060](AztecProtocol/aztec-packages@5211060)) * Yp docs sidebar (with some auto-formatting) ([#3893](AztecProtocol/aztec-packages#3893)) ([f7b007a](AztecProtocol/aztec-packages@f7b007a)) ### Documentation * Noir git subrepo usage ([#3962](AztecProtocol/aztec-packages#3962)) ([2e4c9de](AztecProtocol/aztec-packages@2e4c9de)) * Streamlined pr template ([#3932](AztecProtocol/aztec-packages#3932)) ([5ec1559](AztecProtocol/aztec-packages@5ec1559)) * **yellowpaper:** Avm call pointers, bytecode lookups, circuit io ([#3898](AztecProtocol/aztec-packages#3898)) ([45e1ed2](AztecProtocol/aztec-packages@45e1ed2)) * **yellowpaper:** Avm circuit architecture ([#3934](AztecProtocol/aztec-packages#3934)) ([6aed1d0](AztecProtocol/aztec-packages@6aed1d0)) * **yellowpaper:** First draft of avm circuit memory ([#3865](AztecProtocol/aztec-packages#3865)) ([f689297](AztecProtocol/aztec-packages@f689297)) * **yellowpaper:** Logs ([#4016](AztecProtocol/aztec-packages#4016)) ([d734c79](AztecProtocol/aztec-packages@d734c79)) * **yellowpaper:** Update AVM spec for with "daGasLeft", some cleanup ([#3956](AztecProtocol/aztec-packages#3956)) ([a9537fb](AztecProtocol/aztec-packages@a9537fb)) </details> <details><summary>barretenberg.js: 0.18.0</summary> ## [0.18.0](AztecProtocol/aztec-packages@barretenberg.js-v0.17.0...barretenberg.js-v0.18.0) (2024-01-16) ### Features * Bootstrap cache v2 ([#3876](AztecProtocol/aztec-packages#3876)) ([331598d](AztecProtocol/aztec-packages@331598d)) ### Bug Fixes * Dont spam logs with yarn install ([#4027](AztecProtocol/aztec-packages#4027)) ([949c5ab](AztecProtocol/aztec-packages@949c5ab)) </details> <details><summary>barretenberg: 0.18.0</summary> ## [0.18.0](AztecProtocol/aztec-packages@barretenberg-v0.17.0...barretenberg-v0.18.0) (2024-01-16) ### ⚠ BREAKING CHANGES * Remove `Directive::Quotient` ([#4019](AztecProtocol/aztec-packages#4019)) * implement keccakf1600 in brillig ([#3914](AztecProtocol/aztec-packages#3914)) * add blake3 opcode to brillig ([#3913](AztecProtocol/aztec-packages#3913)) * Remove opcode supported from the backend ([#3889](AztecProtocol/aztec-packages#3889)) ### Features * Acir cleanup ([#3845](AztecProtocol/aztec-packages#3845)) ([390b84c](AztecProtocol/aztec-packages@390b84c)) * Add ACIR opcodes for ECADD and ECDOUBLE ([#3878](AztecProtocol/aztec-packages#3878)) ([537630f](AztecProtocol/aztec-packages@537630f)) * Add blake3 opcode to brillig ([#3913](AztecProtocol/aztec-packages#3913)) ([34fad0a](AztecProtocol/aztec-packages@34fad0a)) * Bench bb in pr's, docker shell utils ([#3561](AztecProtocol/aztec-packages#3561)) ([5408919](AztecProtocol/aztec-packages@5408919)) * Benchmark protogalaxy prover ([#3958](AztecProtocol/aztec-packages#3958)) ([5843722](AztecProtocol/aztec-packages@5843722)) * Benchmarks for basic functionality and IPA improvements ([#4004](AztecProtocol/aztec-packages#4004)) ([fd1f619](AztecProtocol/aztec-packages@fd1f619)) * Bootstrap cache v2 ([#3876](AztecProtocol/aztec-packages#3876)) ([331598d](AztecProtocol/aztec-packages@331598d)) * Implement keccakf1600 in brillig ([#3914](AztecProtocol/aztec-packages#3914)) ([a182381](AztecProtocol/aztec-packages@a182381)) * Parallel IPA ([#3882](AztecProtocol/aztec-packages#3882)) ([7002a33](AztecProtocol/aztec-packages@7002a33)) * Pil lookups w/ xor table example ([#3880](AztecProtocol/aztec-packages#3880)) ([544d24e](AztecProtocol/aztec-packages@544d24e)) * Poseidon2 stdlib impl ([#3551](AztecProtocol/aztec-packages#3551)) ([50b4a72](AztecProtocol/aztec-packages@50b4a72)) * Protogalaxy Decider and complete folding tests ([#3657](AztecProtocol/aztec-packages#3657)) ([cfdaf9c](AztecProtocol/aztec-packages@cfdaf9c)) * Relations vs widgets benchmarking ([#3931](AztecProtocol/aztec-packages#3931)) ([3af64ef](AztecProtocol/aztec-packages@3af64ef)) * Remove opcode supported from the backend ([#3889](AztecProtocol/aztec-packages#3889)) ([1fd135c](AztecProtocol/aztec-packages@1fd135c)) * Reorganize acir composer ([#3957](AztecProtocol/aztec-packages#3957)) ([e6232e8](AztecProtocol/aztec-packages@e6232e8)) * Standalone calldata test ([#3842](AztecProtocol/aztec-packages#3842)) ([7353a35](AztecProtocol/aztec-packages@7353a35)) ### Bug Fixes * Bb unnecessary env var ([#3901](AztecProtocol/aztec-packages#3901)) ([f127e5a](AztecProtocol/aztec-packages@f127e5a)) ### Miscellaneous * Codegen acir opcodes after renaming arithmetic to assertzero ([#3896](AztecProtocol/aztec-packages#3896)) ([c710ce1](AztecProtocol/aztec-packages@c710ce1)) * Document `witness_buf_to_witness_data` ([#3940](AztecProtocol/aztec-packages#3940)) ([fbaa726](AztecProtocol/aztec-packages@fbaa726)) * Remove 'extern template's, expand macros ([#3953](AztecProtocol/aztec-packages#3953)) ([5fe9908](AztecProtocol/aztec-packages@5fe9908)) * Remove `Directive::Quotient` ([#4019](AztecProtocol/aztec-packages#4019)) ([824d76f](AztecProtocol/aztec-packages@824d76f)) * Reorganize benchmarks ([#3909](AztecProtocol/aztec-packages#3909)) ([730766b](AztecProtocol/aztec-packages@730766b)) </details> --- This PR was generated with [Release Please](https://github.com/googleapis/release-please). See [documentation](https://github.com/googleapis/release-please#release-please).

) This PR introduces the Protogalaxy decider, now having a complete proof of concept of the folding protocol for Ultra instances. To enable this, sumcheck has been modified to work with the same power polynomial as in protogalaxy paper and can be initialised with a custom `target_sum`. Moreover, we now use different batching challenges for each subrelation in sumcheck, essential to ensure a reasonable degree of the combiner polynomial. Additional: Minor bug fixed in the computation of \vec{\beta*}. Resolves AztecProtocol/barretenberg#772. Resolves AztecProtocol/barretenberg#691.

maramihali and others added 30 commits October 23, 2023 14:47

wip wip wip

6313f15

styuff

40cedd0

how do I do this?

c7cc936

pain

59c69f2

pain

aed27df

wip that works

265f248

Merge branch 'master' into mm/pg-plumbing

44da63f

cleanup

7ffc364

Merge branch 'master' into mm/combiner-quotient

62df97a

comment test

9d1b5c6

comment test

42ac7e2

Merge remote-tracking branch 'origin/master' into mm/combiner-quotient

75221fb

Add weirder test

bc63909

Use clearer type names

7d3e01b

wip

2287a76

pr review additions

86963a5

Merge branch 'master' into mm/combiner-quotient

a816c4b

fix formatting

91ca591

add missing issue

abb6ed2

Merge branch 'mm/combiner-quotient' into mm/pg-fold-alpha

81f7d89

wip that doesn't work

73068a6

wip

a86a9b4

subrelation number

a51d686

add stuff

df7a62c

confusion

1ff05b6

pain

1ed19f2

compiles

dea27c1

Merge branch 'master' into mm/pg-fold-alpha

05bf621

works

073db88

Merge branch 'master' into mm/pg-fold-alpha

e9079f3

maramihali added 2 commits December 21, 2023 22:19

cleanup

a8812f6

fix idx overflow

8cb1d9e

maramihali force-pushed the mm/pg-decider branch from 2fade37 to 8cb1d9e Compare December 22, 2023 13:24

maramihali added 3 commits January 8, 2024 13:59

Merge branch 'master' into mm/pg-decider

4900dae

debug

be3a223

remove computation of power polynomial at values on the verifier side

deb239e

maramihali commented Jan 8, 2024

View reviewed changes

update tests and comments

ecf84ce

maramihali force-pushed the mm/pg-decider branch from 5775a01 to ecf84ce Compare January 8, 2024 18:00

maramihali requested a review from codygunton January 8, 2024 18:22

maramihali force-pushed the mm/pg-decider branch from fac2ea3 to ecf84ce Compare January 8, 2024 20:18

Merge branch 'master' into mm/pg-decider

5cc73f1

codygunton reviewed Jan 8, 2024

View reviewed changes

codygunton requested changes Jan 9, 2024

View reviewed changes

Merge branch 'master' into mm/pg-decider

4c4d664

maramihali requested a review from codygunton January 10, 2024 16:09

resolve review comments

65c6aeb

maramihali force-pushed the mm/pg-decider branch from fc2303a to 65c6aeb Compare January 10, 2024 16:31

fix formatting

4f7d79b

codygunton approved these changes Jan 11, 2024

View reviewed changes

Merge remote-tracking branch 'origin/master' into mm/pg-decider

7ae0880

codygunton enabled auto-merge (squash) January 11, 2024 14:32

Merge branch 'master' into mm/pg-decider

066f35c

codygunton merged commit cfdaf9c into master Jan 11, 2024
78 of 81 checks passed

codygunton deleted the mm/pg-decider branch January 11, 2024 15:26

AztecBot mentioned this pull request Jan 11, 2024

chore(master): Release 0.18.0 #3892

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

feat: Protogalaxy Decider and complete folding tests #3657

feat: Protogalaxy Decider and complete folding tests #3657

maramihali commented Dec 12, 2023 •

edited

Loading

maramihali Jan 8, 2024

codygunton left a comment

codygunton Jan 8, 2024

codygunton Jan 8, 2024 •

edited

Loading

maramihali Jan 10, 2024

maramihali Jan 10, 2024

codygunton left a comment

codygunton Jan 9, 2024

maramihali Jan 10, 2024

		@@ -240,17 +240,6 @@ jobs:
		name: "Test"
		command: cond_spot_run_test barretenberg-x86_64-linux-clang-assert 32 ./scripts/bb-tests.sh

feat: Protogalaxy Decider and complete folding tests #3657

feat: Protogalaxy Decider and complete folding tests #3657

Conversation

maramihali commented Dec 12, 2023 • edited Loading

Checklist:

maramihali Jan 8, 2024

Choose a reason for hiding this comment

codygunton left a comment

Choose a reason for hiding this comment

codygunton Jan 8, 2024

Choose a reason for hiding this comment

codygunton Jan 8, 2024 • edited Loading

Choose a reason for hiding this comment

maramihali Jan 10, 2024

Choose a reason for hiding this comment

maramihali Jan 10, 2024

Choose a reason for hiding this comment

codygunton left a comment

Choose a reason for hiding this comment

codygunton Jan 9, 2024

Choose a reason for hiding this comment

maramihali Jan 10, 2024

Choose a reason for hiding this comment

maramihali commented Dec 12, 2023 •

edited

Loading

codygunton Jan 8, 2024 •

edited

Loading