aztec-packages icon indicating copy to clipboard operation
aztec-packages copied to clipboard

feat: Graph methods for circuit analysis (part 1)

Open DanielKotov opened this issue 1 year ago • 1 comments

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.

DanielKotov avatar Aug 13 '24 17:08 DanielKotov

Changes to circuit sizes

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

🧾 Summary (100% most significant diffs)

Program ACIR opcodes (+/-) % Circuit size (+/-) %
rollup_block_merge 0 ➖ 0.00% -12 ✅ -0.00%
rollup_root 0 ➖ 0.00% -12 ✅ -0.00%
rollup_block_root 0 ➖ 0.00% -24 ✅ -0.00%
parity_root 0 ➖ 0.00% -36 ✅ -0.00%
rollup_merge 0 ➖ 0.00% -24 ✅ -0.00%
rollup_base_private 0 ➖ 0.00% -1,476 ✅ -0.05%
rollup_base_public 0 ➖ 0.00% -1,476 ✅ -0.06%
parity_base 0 ➖ 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%

github-actions[bot] avatar Aug 13 '24 18:08 github-actions[bot]