feat: swap polys to facilitate dynamic trace overflow #9976

ledwards2225 · 2024-11-14T19:59:35Z

Update PG/ClientIvc so that during accumulation we can handle a circuit that overflows the nominal structured trace (and potentially increases the dyadic size of the accumulator) without knowing about the size of the overflow in advance. (A previous PR makes it possible to overflow arbitrarily as long as ClientIvc is initialized with the proper overflow capacity). Ensure the ExecutionTraceTracker is updated correctly when encountering a circuit that overflows and also ensure that the tracker is used appropriately in Protogalaxy.

maramihali · 2024-11-26T17:16:02Z

...erg/cpp/src/barretenberg/plonk_honk_shared/execution_trace/execution_trace_usage_tracker.hpp

+        // need to determine the dyadic size for this. We call the size function on the current circuit which will have
+        // the same fixed block sizes but might also have an overflow block potentially influencing the dyadic circuit
+        // size.
+        size_t dyadic_circuit_size = circuit.blocks.get_structured_dyadic_size();


This was the major issue: The fixed sizes are set using the trace settings so the overflow block was 0 and hence the dyadic_circuit_size was not computed correctly. This was leading us to not take into account the lookup contributions at the end of the current circuit trace in PG. Modifying the fixed_sizes to include the overflow block is not easily possible in the current design and it makes sense to compute the dyadic_circuit_size using the current circuit. It will have the same TraceSetting (hence the same sizes also contained in the fixed_sizes structure ) but also the correct size of the overflow block. I expect we might be able to get rid of the fixed_sizes structure as a follow up or do something a bit cleaner in a follow up

maramihali · 2024-11-26T17:16:56Z

...erg/cpp/src/barretenberg/plonk_honk_shared/execution_trace/execution_trace_usage_tracker.hpp

+        info("");
+    }
+
+    void print_previous_active_ranges()


when i was printing the active ranges it wasn't reflecting everything due to the lookup and databus caveat so I think it made sense to refine the labels

barretenberg/cpp/src/barretenberg/stdlib/primitives/biggroup/biggroup.test.cpp

…or while cleaning up

maramihali · 2024-11-27T12:52:53Z

barretenberg/cpp/src/barretenberg/client_ivc/client_ivc.cpp


+    // The commitment key is initialised with the number of points determined by the trace_settings' dyadic size. If a


This is the caveat with overflowing circuits and having a single CIVC commitment key, maybe this could be refined in a follow up PR but seemed the easiest solution as it is. In the ideal case when we never overflow we still can benefit from having a single commitment key

codygunton · 2024-11-27T14:57:25Z

barretenberg/cpp/src/barretenberg/client_ivc/client_ivc.cpp

-    } else {
-        proving_key = std::make_shared<DeciderProvingKey>(circuit, trace_settings);
-    }
+    proving_key = std::make_shared<DeciderProvingKey>(circuit, trace_settings);


Also: please fuse this into the previous line if we're not conditionally defining (though I don't understand why we did that to begin with...)

because at first round of client ivc we were also initializing the tracker but i discovered this could be included in the constructor of civc

codygunton · 2024-11-27T15:01:18Z

barretenberg/cpp/src/barretenberg/client_ivc/client_ivc.test.cpp

+TEST_F(ClientIVCTests, DynamicOverflow)
+{
+    // Define trace settings with zero overflow capacity
+    ClientIVC ivc{ { SMALL_TEST_STRUCTURE, /*overflow_capacity=*/0 } };


If small tests structure changes behind the scenes, this test could silently break (i.e., it may continue to pass but cease to test what it's supposed to). Will you please define a new trace structure in this file for use in these two tests only?

barretenberg/cpp/src/barretenberg/commitment_schemes/commitment_key.hpp

codygunton · 2024-11-27T15:03:10Z

...erg/cpp/src/barretenberg/plonk_honk_shared/execution_trace/execution_trace_usage_tracker.hpp

@@ -72,8 +72,11 @@ struct ExecutionTraceUsageTracker {
        }

        // The active ranges must also include the rows where the actual databus and lookup table data are stored.
-        // (Note: lookup tables are constructed at the end of the trace; databus data is constructed at the start).
-        size_t dyadic_circuit_size = fixed_sizes.get_structured_dyadic_size();
+        // (Note: lookup tables are constructed at the end of the trace; databus data is constructed at the start) so we


This comment will break if the ordering in the trace structure ever changes--there's little chance that the person changing the structure remembers this comment exists, if they ever knew.

a way to make this more robust is to update the active ranges as we are constructing the DeciderProvingKey so if the position of the rows changes it is obvious that the tracker's active ranges also need to be updated, will add an issue.

...erg/cpp/src/barretenberg/plonk_honk_shared/execution_trace/execution_trace_usage_tracker.hpp

barretenberg/cpp/src/barretenberg/plonk_honk_shared/relation_checker.hpp

codygunton · 2024-11-27T15:27:20Z

barretenberg/cpp/src/barretenberg/protogalaxy/protogalaxy.test.cpp

+     */
+    static void test_fold_with_virtual_size_expansion()
+    {
+        uint32_t overflow_capacity = 0; // consider the case where the overflow is not known until runtime


Same as above--if test correctness depends on a particular trace structure, we need to guard against that structure changing silently by putting the structure in the test (or test suite).

codygunton · 2024-11-27T15:34:41Z

barretenberg/cpp/src/barretenberg/protogalaxy/protogalaxy_prover_internal.hpp

@@ -113,7 +113,8 @@ template <class DeciderProvingKeys_> class ProtogalaxyProverInternal {
     */
    std::vector<FF> compute_row_evaluations(const ProverPolynomials& polynomials,
                                            const RelationSeparator& alphas_,
-                                            const RelationParameters<FF>& relation_parameters)
+                                            const RelationParameters<FF>& relation_parameters,
+                                            const bool use_prev_accumulator_tracker = false)


Why is this boolean needed here now?

This function is used in two situations, perturbator computation in which we use the active ranges from the previous accumulator and if we manually want to compute the evaluations for each row of an accumulator

maybe it should be default true and optional false?

barretenberg/cpp/src/barretenberg/ultra_honk/mega_honk.test.cpp

codygunton · 2024-11-27T15:37:37Z

barretenberg/cpp/src/barretenberg/ultra_honk/mega_honk.test.cpp

+    using Flavor = TypeParam;
+    using Builder = Flavor::CircuitBuilder;
+
+    TraceSettings trace_settings{ SMALL_TEST_STRUCTURE };


github-actions · 2024-11-27T17:33:21Z

Changes to public function bytecode sizes

Generated at commit: ad3a0cd0286d32d482e7930d177be8317db07345, compared to commit: 7d5c33d1f046e1b8b3f367ff1682b9fd6272e2fd

🧾 Summary (100% most significant diffs)

Program	Bytecode size in bytes (+/-)	%
AvmTest::bulk_testing	+30 ❌	+0.13%
AvmTest::public_dispatch	-9 ✅	-0.01%

Full diff report 👇

Program	Bytecode size in bytes (+/-)	%
AvmTest::bulk_testing	23,104 (+30)	+0.13%
AvmTest::public_dispatch	60,762 (-9)	-0.01%

github-actions · 2024-11-27T17:37:52Z

Changes to circuit sizes

Generated at commit: ad3a0cd0286d32d482e7930d177be8317db07345, compared to commit: 7d5c33d1f046e1b8b3f367ff1682b9fd6272e2fd

🧾 Summary (100% most significant diffs)

Program	ACIR opcodes (+/-)	%	Circuit size (+/-)	%
private_kernel_empty	-1 ✅	-0.16%	-1 ✅	-0.00%
rollup_base_public	-2 ✅	-0.00%	-8 ✅	-0.00%
private_kernel_reset	-2 ✅	-0.00%	-2 ✅	-0.00%
rollup_block_root	-1 ✅	-0.02%	-13 ✅	-0.00%
rollup_merge	-1 ✅	-0.03%	-13 ✅	-0.00%
rollup_base_private	-2 ✅	-0.00%	-83 ✅	-0.00%
private_kernel_tail_to_public	-2 ✅	-0.01%	-1 ✅	-0.00%
private_kernel_reset_4_4_4_4_4_4_4_4_1	-2 ✅	-0.01%	-3 ✅	-0.00%
private_kernel_inner	-3 ✅	-0.01%	-3 ✅	-0.01%
private_kernel_tail	-2 ✅	-0.05%	-1 ✅	-0.01%
private_kernel_init	-2 ✅	-0.01%	-3 ✅	-0.01%

Full diff report 👇

Program	ACIR opcodes (+/-)	%	Circuit size (+/-)	%
private_kernel_empty	612 (-1)	-0.16%	901,639 (-1)	-0.00%
rollup_base_public	447,125 (-2)	-0.00%	3,997,443 (-8)	-0.00%
private_kernel_reset	84,027 (-2)	-0.00%	618,037 (-2)	-0.00%
rollup_block_root	4,489 (-1)	-0.02%	2,739,652 (-13)	-0.00%
rollup_merge	3,419 (-1)	-0.03%	1,827,046 (-13)	-0.00%
rollup_base_private	197,673 (-2)	-0.00%	2,658,579 (-83)	-0.00%
private_kernel_tail_to_public	17,384 (-2)	-0.01%	29,504 (-1)	-0.00%
private_kernel_reset_4_4_4_4_4_4_4_4_1	32,385 (-2)	-0.01%	86,491 (-3)	-0.00%
private_kernel_inner	37,549 (-3)	-0.01%	56,879 (-3)	-0.01%
private_kernel_tail	4,131 (-2)	-0.05%	12,514 (-1)	-0.01%
private_kernel_init	21,407 (-2)	-0.01%	34,503 (-3)	-0.01%

codygunton

Thanks!

🤖 I have created a release *beep* *boop* --- <details><summary>aztec-package: 0.65.2</summary> ## [0.65.2](aztec-package-v0.65.1...aztec-package-v0.65.2) (2024-11-28) ### Features * New proving broker ([#10174](#10174)) ([6fd5fc1](6fd5fc1)) </details> <details><summary>barretenberg.js: 0.65.2</summary> ## [0.65.2](barretenberg.js-v0.65.1...barretenberg.js-v0.65.2) (2024-11-28) ### Miscellaneous * **barretenberg.js:** Synchronize aztec-packages versions </details> <details><summary>aztec-packages: 0.65.2</summary> ## [0.65.2](aztec-packages-v0.65.1...aztec-packages-v0.65.2) (2024-11-28) ### Features * Fee foresight support ([#10262](#10262)) ([9e19244](9e19244)) * New proving broker ([#10174](#10174)) ([6fd5fc1](6fd5fc1)) * Sequential insertion in indexed trees ([#10111](#10111)) ([bfd9fa6](bfd9fa6)) * Swap polys to facilitate dynamic trace overflow ([#9976](#9976)) ([b7b282c](b7b282c)) ### Bug Fixes * Don't store indices of zero leaves. ([#10270](#10270)) ([c22be8b](c22be8b)) * Expect proper duplicate nullifier error patterns in e2e tests ([#10256](#10256)) ([4ee8344](4ee8344)) ### Miscellaneous * Check artifact consistency ([#10271](#10271)) ([6a49405](6a49405)) * Dont import things that themselves import jest in imported functions ([#10260](#10260)) ([9440c1c](9440c1c)) * Fix bad merge in integration l1 publisher ([#10272](#10272)) ([b5a6aa4](b5a6aa4)) * Fixing sol warnings ([#10276](#10276)) ([3d113b2](3d113b2)) * Pull out sync changes ([#10274](#10274)) ([391a6b7](391a6b7)) * Pull value merger code from sync ([#10080](#10080)) ([3392629](3392629)) * Remove default gas settings ([#10163](#10163)) ([c9a4d88](c9a4d88)) * Replace relative paths to noir-protocol-circuits ([654d801](654d801)) * Teardown context in prover coordination test ([#10257](#10257)) ([7ea3888](7ea3888)) </details> <details><summary>barretenberg: 0.65.2</summary> ## [0.65.2](barretenberg-v0.65.1...barretenberg-v0.65.2) (2024-11-28) ### Features * Sequential insertion in indexed trees ([#10111](#10111)) ([bfd9fa6](bfd9fa6)) * Swap polys to facilitate dynamic trace overflow ([#9976](#9976)) ([b7b282c](b7b282c)) ### Bug Fixes * Don't store indices of zero leaves. ([#10270](#10270)) ([c22be8b](c22be8b)) ### Miscellaneous * Pull value merger code from sync ([#10080](#10080)) ([3392629](3392629)) </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-package: 0.65.2</summary> ## [0.65.2](AztecProtocol/aztec-packages@aztec-package-v0.65.1...aztec-package-v0.65.2) (2024-11-28) ### Features * New proving broker ([#10174](AztecProtocol/aztec-packages#10174)) ([6fd5fc1](AztecProtocol/aztec-packages@6fd5fc1)) </details> <details><summary>barretenberg.js: 0.65.2</summary> ## [0.65.2](AztecProtocol/aztec-packages@barretenberg.js-v0.65.1...barretenberg.js-v0.65.2) (2024-11-28) ### Miscellaneous * **barretenberg.js:** Synchronize aztec-packages versions </details> <details><summary>aztec-packages: 0.65.2</summary> ## [0.65.2](AztecProtocol/aztec-packages@aztec-packages-v0.65.1...aztec-packages-v0.65.2) (2024-11-28) ### Features * Fee foresight support ([#10262](AztecProtocol/aztec-packages#10262)) ([9e19244](AztecProtocol/aztec-packages@9e19244)) * New proving broker ([#10174](AztecProtocol/aztec-packages#10174)) ([6fd5fc1](AztecProtocol/aztec-packages@6fd5fc1)) * Sequential insertion in indexed trees ([#10111](AztecProtocol/aztec-packages#10111)) ([bfd9fa6](AztecProtocol/aztec-packages@bfd9fa6)) * Swap polys to facilitate dynamic trace overflow ([#9976](AztecProtocol/aztec-packages#9976)) ([b7b282c](AztecProtocol/aztec-packages@b7b282c)) ### Bug Fixes * Don't store indices of zero leaves. ([#10270](AztecProtocol/aztec-packages#10270)) ([c22be8b](AztecProtocol/aztec-packages@c22be8b)) * Expect proper duplicate nullifier error patterns in e2e tests ([#10256](AztecProtocol/aztec-packages#10256)) ([4ee8344](AztecProtocol/aztec-packages@4ee8344)) ### Miscellaneous * Check artifact consistency ([#10271](AztecProtocol/aztec-packages#10271)) ([6a49405](AztecProtocol/aztec-packages@6a49405)) * Dont import things that themselves import jest in imported functions ([#10260](AztecProtocol/aztec-packages#10260)) ([9440c1c](AztecProtocol/aztec-packages@9440c1c)) * Fix bad merge in integration l1 publisher ([#10272](AztecProtocol/aztec-packages#10272)) ([b5a6aa4](AztecProtocol/aztec-packages@b5a6aa4)) * Fixing sol warnings ([#10276](AztecProtocol/aztec-packages#10276)) ([3d113b2](AztecProtocol/aztec-packages@3d113b2)) * Pull out sync changes ([#10274](AztecProtocol/aztec-packages#10274)) ([391a6b7](AztecProtocol/aztec-packages@391a6b7)) * Pull value merger code from sync ([#10080](AztecProtocol/aztec-packages#10080)) ([3392629](AztecProtocol/aztec-packages@3392629)) * Remove default gas settings ([#10163](AztecProtocol/aztec-packages#10163)) ([c9a4d88](AztecProtocol/aztec-packages@c9a4d88)) * Replace relative paths to noir-protocol-circuits ([654d801](AztecProtocol/aztec-packages@654d801)) * Teardown context in prover coordination test ([#10257](AztecProtocol/aztec-packages#10257)) ([7ea3888](AztecProtocol/aztec-packages@7ea3888)) </details> <details><summary>barretenberg: 0.65.2</summary> ## [0.65.2](AztecProtocol/aztec-packages@barretenberg-v0.65.1...barretenberg-v0.65.2) (2024-11-28) ### Features * Sequential insertion in indexed trees ([#10111](AztecProtocol/aztec-packages#10111)) ([bfd9fa6](AztecProtocol/aztec-packages@bfd9fa6)) * Swap polys to facilitate dynamic trace overflow ([#9976](AztecProtocol/aztec-packages#9976)) ([b7b282c](AztecProtocol/aztec-packages@b7b282c)) ### Bug Fixes * Don't store indices of zero leaves. ([#10270](AztecProtocol/aztec-packages#10270)) ([c22be8b](AztecProtocol/aztec-packages@c22be8b)) ### Miscellaneous * Pull value merger code from sync ([#10080](AztecProtocol/aztec-packages#10080)) ([3392629](AztecProtocol/aztec-packages@3392629)) </details> --- This PR was generated with [Release Please](https://github.com/googleapis/release-please). See [documentation](https://github.com/googleapis/release-please#release-please).

swapping in folding appears to work

560373c

ledwards2225 self-assigned this Nov 14, 2024

ledwards2225 marked this pull request as ready for review November 14, 2024 19:59

ledwards2225 added 20 commits November 15, 2024 20:56

WiP; dyadic size bump tst failing without real clues

981074c

Merge branch 'master' into lde/swap_polys

090e720

Merge branch 'master' into lde/swap_polys

2eded0b

changes from other PR; test passes if overflow is set in advance

d06c1e8

WiP debug with check circuit shows decider sumcheck failure

b4cb9de

add test that proves out dynamic virtual size increase

a7231ef

move relation checker to pk inspector

0cf3757

add proper relation checker class

f7e8fc7

debug

35c15a0

WiP virtual size increase pg test

515fe8b

basic pg test passes after replacing cir size with vir size

e07eb4d

correctly set circuit size in pg verifier; pg decide test passes

7d4ba63

Merge branch 'master' into lde/swap_polys

ba7bfd5

turn off debugging check circuit calls

559bb2e

comments and fix build error

916fc98

corrctly set circuit size in pg rec verifier

b23cd91

comments and cleanup

864ee3a

add some debug utility in ivc tests

bfb2a70

debug stuff

2494af1

comments

531c0d1

maramihali self-assigned this Nov 21, 2024

maramihali added the crypto cryptography label Nov 21, 2024

maramihali added 4 commits November 26, 2024 13:01

loads of cleanup and execution trace tracker needs fixing

0b582eb

fixed

d781974

cleanup and enable parallelisation

0b714d2

create todos

c9e6af0

maramihali reviewed Nov 26, 2024

View reviewed changes

maramihali added 6 commits November 26, 2024 17:23

make a folding test utils

90277ab

Merge remote-tracking branch 'origin/master' into lde/swap_polys

0891578

undo comment

9f05f0b

revert submodule changes

c13923b

some constifying

48052d0

unused variable error when building everything

681c1e6

maramihali requested a review from codygunton November 26, 2024 18:08

now both builds work

1f79b46

maramihali reviewed Nov 27, 2024

View reviewed changes

barretenberg/cpp/src/barretenberg/stdlib/primitives/biggroup/biggroup.test.cpp Show resolved Hide resolved

maramihali added 2 commits November 27, 2024 12:12

wopsie, I removed the commitment key from DeciderProvingKey construct…

e7d8499

…or while cleaning up

fix commitment ket caveat

1f4df0f

maramihali reviewed Nov 27, 2024

View reviewed changes

codygunton requested changes Nov 27, 2024

View reviewed changes

update PR based on review

cd92b66

maramihali requested a review from codygunton November 27, 2024 17:44

remove extra boolean in compute_row_evaluations

067cbb0

codygunton approved these changes Nov 27, 2024

View reviewed changes

codygunton merged commit b7b282c into master Nov 27, 2024
71 checks passed

codygunton deleted the lde/swap_polys branch November 27, 2024 20:22

AztecBot mentioned this pull request Nov 27, 2024

chore(master): Release 0.65.2 #10258

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

feat: swap polys to facilitate dynamic trace overflow #9976

feat: swap polys to facilitate dynamic trace overflow #9976

ledwards2225 commented Nov 14, 2024 •

edited by maramihali

Loading

maramihali Nov 26, 2024 •

edited

Loading

maramihali Nov 26, 2024

maramihali Nov 27, 2024

codygunton Nov 27, 2024

maramihali Nov 27, 2024

codygunton Nov 27, 2024

codygunton Nov 27, 2024

maramihali Nov 27, 2024

codygunton Nov 27, 2024

codygunton Nov 27, 2024

maramihali Nov 27, 2024

maramihali Nov 27, 2024

codygunton Nov 27, 2024

github-actions bot commented Nov 27, 2024 •

edited

Loading

github-actions bot commented Nov 27, 2024 •

edited

Loading

codygunton left a comment


		// The commitment key is initialised with the number of points determined by the trace_settings' dyadic size. If a

feat: swap polys to facilitate dynamic trace overflow #9976

feat: swap polys to facilitate dynamic trace overflow #9976

Conversation

ledwards2225 commented Nov 14, 2024 • edited by maramihali Loading

maramihali Nov 26, 2024 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

github-actions bot commented Nov 27, 2024 • edited Loading

Changes to public function bytecode sizes

🧾 Summary (100% most significant diffs)

github-actions bot commented Nov 27, 2024 • edited Loading

Changes to circuit sizes

🧾 Summary (100% most significant diffs)

codygunton left a comment

Choose a reason for hiding this comment

ledwards2225 commented Nov 14, 2024 •

edited by maramihali

Loading

maramihali Nov 26, 2024 •

edited

Loading

github-actions bot commented Nov 27, 2024 •

edited

Loading

github-actions bot commented Nov 27, 2024 •

edited

Loading