feat: Graph methods for circuit analysis (part 1) #7948

DanielKotov · 2024-08-13T17:48:36Z

Create graph description for Ultra Circuit Builder.

The original idea was to create to directed graph for arithmetic circuit, that bases on Ultra Arithmetization.

The constructor creates graph based on blocks for ultra: arithmetic, elliptic, delta range and lookup. In the time of this process gate counter for every variable depends on gate. Also was created algorithm for finding connected components using depth first search algorithm.

Tests from ultra_curcuit_builder were being used for testing the prototype.

summary: there's a constructor for creating graph for Ultra Circuit Builder with additional algorithm for analyzing Circuit.

Rumata888

Please address the comments and resubmit for review

barretenberg/cpp/src/barretenberg/boomerang_value_detection/.gitignore

barretenberg/cpp/src/barretenberg/smt_verification/circuit/standard_circuit.test.cpp

Rumata888 · 2024-08-13T18:00:56Z

barretenberg/cpp/src/barretenberg/stdlib_circuit_builders/standard_circuit_builder.cpp

@@ -473,6 +473,57 @@ void StandardCircuitBuilder_<FF>::fix_witness(const uint32_t witness_index, cons
    ++this->num_gates;
 }

+template <typename FF> void StandardCircuitBuilder_<FF>::print_boomerang_variables()


Please add comment about how this function works

barretenberg/cpp/src/barretenberg/circuit_checker/standard_circuit_builder.test.cpp

barretenberg/cpp/src/barretenberg/boomerang_value_detection/graph_description.test.cpp

Rumata888 · 2024-08-13T18:03:54Z

barretenberg/cpp/src/barretenberg/boomerang_value_detection/graph_description.test.cpp

+    StandardCircuitBuilder circuit_constructor = StandardCircuitBuilder();
+    fr a = fr::one();
+    circuit_constructor.add_public_variable(a);
+    Graph graph = Graph(circuit_constructor);


You are not checking graph structure in any of these tests, so they aren't doing anything. Please add checks of graph structure

barretenberg/cpp/src/barretenberg/boomerang_value_detection/graph.cpp

Rumata888 · 2024-08-13T18:06:26Z

barretenberg/cpp/src/barretenberg/boomerang_value_detection/graph.cpp

+}
+
+template <typename FF>
+void Graph_<FF>::connect_all_variables_in_vector(const std::vector<uint32_t>& variables_vector,


Why are you still using zero index if you need to check that it's not a constant variable?

barretenberg/cpp/src/barretenberg/boomerang_value_detection/graph.cpp

AztecBot

⚠️ Performance Alert ⚠️

Possible performance regression was detected for benchmark 'C++ Benchmark'.
Benchmark result of this commit is worse than the previous benchmark result exceeding threshold 1.05.

Benchmark suite	Current: `2744ba4`	Previous: `7f6dba2`	Ratio
`nativeconstruct_proof_ultrahonk_power_of_2/20`	`5168.177880000002` ms/iter	`4750.393791999997` ms/iter	`1.09`
`commit(t)`	`4428680062` ns/iter	`3767372954` ns/iter	`1.18`

This comment was automatically generated by workflow using github-action-benchmark.

CC: @ludamad @codygunton

github-actions · 2024-08-13T18:14:23Z

Changes to circuit sizes

Generated at commit: 163db00603fa968ad17c926e17dfbbeba68c0f9d, compared to commit: 86b249022167762fb9558aedf579f5648097592a

🧾 Summary (100% most significant diffs)

Program	%	Circuit size (+/-)	%
rollup_block_merge	0.00%	-12 ✅	-0.00%
rollup_root	0.00%	-12 ✅	-0.00%
rollup_block_root	0.00%	-24 ✅	-0.00%
parity_root	0.00%	-36 ✅	-0.00%
rollup_merge	0.00%	-24 ✅	-0.00%
rollup_base_private	0.00%	-1,476 ✅	-0.05%
rollup_base_public	0.00%	-1,476 ✅	-0.06%
parity_base	0.00%	-36 ✅	-0.12%

Full diff report 👇

Program	ACIR opcodes (+/-)	%	Circuit size (+/-)	%
rollup_block_merge	5,057 (0)	0.00%	1,911,809 (-12)	-0.00%
rollup_root	5,041 (0)	0.00%	1,911,795 (-12)	-0.00%
rollup_block_root	4,021 (0)	0.00%	2,857,288 (-24)	-0.00%
parity_root	5,031 (0)	0.00%	3,801,549 (-36)	-0.00%
rollup_merge	3,415 (0)	0.00%	1,909,442 (-24)	-0.00%
rollup_base_private	345,125 (0)	0.00%	3,272,730 (-1,476)	-0.05%
rollup_base_public	345,984 (0)	0.00%	2,314,712 (-1,476)	-0.06%
parity_base	4,298 (0)	0.00%	30,695 (-36)	-0.12%

…n CMakeLists.txt

…mmit

…es and sha256 were testted

barretenberg/cpp/src/barretenberg/boomerang_value_detection/graph.cpp

barretenberg/cpp/src/barretenberg/boomerang_value_detection/graph.hpp

… some naming changes

barretenberg/cpp/src/barretenberg/boomerang_value_detection/graph.hpp

barretenberg/cpp/src/barretenberg/boomerang_value_detection/graph.cpp

barretenberg/cpp/src/barretenberg/stdlib_circuit_builders/standard_circuit_builder.cpp

barretenberg/cpp/src/barretenberg/boomerang_value_detection/graph.cpp

barretenberg/cpp/src/barretenberg/boomerang_value_detection/graph.hpp

barretenberg/cpp/src/barretenberg/boomerang_value_detection/graph.cpp

barretenberg/cpp/src/barretenberg/stdlib/hash/blake2s/blake2s.test.cpp

barretenberg/cpp/src/barretenberg/boomerang_value_detection/graph.cpp

Sarkoxed · 2024-11-01T14:33:39Z

barretenberg/cpp/src/barretenberg/boomerang_value_detection/graph.cpp

+}
+
+/**
+ * @brief this method removes false cases in lookup table for a given gate


yet another false cases occurrence

barretenberg/cpp/src/barretenberg/boomerang_value_detection/graph.cpp

Sarkoxed

LGTM

sha256 tests

Rumata888

We'll need to document the tests and functionality more, but let's merge it in for now

* master: (81 commits) feat: Encode static error strings in the ABI (#9552) chore: redo typo PR by donatik27 (#9693) chore: update install instructions for foundry to display version of rust to install (#9653) chore: disable bench upload until #9692 fix: earthly-ci in bench-e2e (#9689) chore: redo typo PR by cypherpepe (#9687) chore: redo typo PR by youyyytrok (#9686) chore: redo typo PR by mdqst (#9685) chore: redo typo PR by mdqst (#9684) feat: adding tags to encrypted logs (#9566) fix: enable gerousia e2e test (#9677) git subrepo push --branch=master noir-projects/aztec-nr git_subrepo.sh: Fix parent in .gitrepo file. [skip ci] chore: replace relative paths to noir-protocol-circuits git subrepo push --branch=master barretenberg chore: redo typo PR by dsarfed (#9667) fix: bench e2e jobs (#9662) fix: Fix random for Mac users (#9670) feat: Graph methods for circuit analysis (part 1) (#7948) feat: Faster random sampling (#9655) ...

DanielKotov requested a review from Rumata888 August 13, 2024 17:48

Rumata888 changed the title ~~dk/boomerang value~~ feat: Graph methods for circuit analysis Aug 13, 2024

Rumata888 changed the title ~~feat: Graph methods for circuit analysis~~ feat: Graph methods for circuit analysis (part 1) Aug 13, 2024

Rumata888 requested changes Aug 13, 2024

View reviewed changes

AztecBot reviewed Aug 13, 2024

View reviewed changes

DanielKotov requested a review from Rumata888 August 23, 2024 15:21

DanielKotov and others added 15 commits October 2, 2024 16:43

graph decription for ultra circuit builder

f3ab6af

update_edges_for_sorted_variabes, cause it's useless now

10508e1

git ignore was added

314f4f0

remove some commentaries from tests

346f1bc

remove all commentaries from another directiories and add my module i…

8375f46

…n CMakeLists.txt

forget to return fr(2) in standard_circuit_builder.cpp in the last co…

86339b2

…mmit

static analyzer based on graph description for UltraCircuitBuilder. a…

ddf3e98

…es and sha256 were testted

tests for sha256 and blake2s

0779bbb

fixes

8a52e6d

variables gate counts metric for AES and sha256

0956684

remove changes from blake2s tests and circuit_builder_base

637c203

variables gate count for sha256 + tests

ff5df64

remove some changes from workspace

aef2249

update for sha256 for PR

bda8275

last commit

d9486f2

DanielKotov force-pushed the dk/boomerang_value branch from 24d4529 to d9486f2 Compare October 2, 2024 16:52

final version of UltraCircuit graph description for PR

20eb663

DanielKotov requested a review from Sarkoxed October 9, 2024 12:08

Sarkoxed requested changes Oct 11, 2024

View reviewed changes

add commentaries for every class methods, data sturctures and tests +…

ad369c8

… some naming changes

DanielKotov requested a review from Sarkoxed October 21, 2024 14:37

Sarkoxed requested changes Oct 21, 2024

View reviewed changes

other changes for PR again

6e2933f

DanielKotov requested review from Sarkoxed and AztecBot October 28, 2024 15:29

Sarkoxed requested changes Oct 30, 2024

View reviewed changes

add comments + inline + this to all class member functions

445e02e

Sarkoxed reviewed Nov 1, 2024

View reviewed changes

Sarkoxed approved these changes Nov 1, 2024

View reviewed changes

DanielKotov and others added 5 commits November 1, 2024 17:56

corrected Sasha's comments + renamed tests + removed some info from

d0f4fd4

sha256 tests

Merge remote-tracking branch 'origin/master' into dk/boomerang_value

2c842f6

graph methods for circuit analysis

af9f73a

remove my useless solution for standard circuit builder and tests for it

0e238ff

cleanup

14b6f32

Rumata888 approved these changes Nov 1, 2024

View reviewed changes

Rumata888 enabled auto-merge (squash) November 1, 2024 21:42

Rumata888 merged commit eeea55a into master Nov 1, 2024
46 checks passed

Rumata888 deleted the dk/boomerang_value branch November 1, 2024 22:12

AztecBot mentioned this pull request Nov 1, 2024

chore(master): Release 0.63.0 #9651

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

feat: Graph methods for circuit analysis (part 1) #7948

feat: Graph methods for circuit analysis (part 1) #7948

DanielKotov commented Aug 13, 2024

Rumata888 left a comment

Rumata888 Aug 13, 2024

Rumata888 Aug 13, 2024

Rumata888 Aug 13, 2024

AztecBot left a comment

github-actions bot commented Aug 13, 2024 •

edited

Loading

Sarkoxed Nov 1, 2024

Sarkoxed left a comment

Rumata888 left a comment

feat: Graph methods for circuit analysis (part 1) #7948

feat: Graph methods for circuit analysis (part 1) #7948

Conversation

DanielKotov commented Aug 13, 2024

Rumata888 left a comment

Choose a reason for hiding this comment

Rumata888 Aug 13, 2024

Choose a reason for hiding this comment

Rumata888 Aug 13, 2024

Choose a reason for hiding this comment

Rumata888 Aug 13, 2024

Choose a reason for hiding this comment

AztecBot left a comment

Choose a reason for hiding this comment

⚠️ Performance Alert ⚠️

github-actions bot commented Aug 13, 2024 • edited Loading

Changes to circuit sizes

🧾 Summary (100% most significant diffs)

Sarkoxed Nov 1, 2024

Choose a reason for hiding this comment

Sarkoxed left a comment

Choose a reason for hiding this comment

Rumata888 left a comment

Choose a reason for hiding this comment

github-actions bot commented Aug 13, 2024 •

edited

Loading