feat(ssa): Expand feature set of the Brillig constraint check

[rkarabut]

Description

This PR resolves a number of issues that came up in the initial introduction of the Brillig constraint check, expanding its feature set.

Problem

#6698, #6706, #6713, #6735

Summary

Resolves #6698 by creating and maintaining additional tainted value sets for every result array element, #6713 by tracking EnableSideEffectsIf condition values, and #6735 along with #6706 by introducing a quick pass gathering information on Brillig calls. New tests for every issue are included.

As fixing #6698 makes the check_underconstrained_regression test program (correctly) issue a bug warning now, the program has been updated to properly constrain the involved array elements.

Additional Context

Documentation

Check one:

• No documentation needed.
• Documentation included in this PR.
• [For Experimental Features] Documentation to be submitted in a separate PR.

PR Checklist*

• I have tested the changes locally.
• I have formatted the changes with Prettier and/or cargo fmt on default settings.

[github-actions]

Execution Memory Report

Program	Peak Memory
keccak256	74.630
workspace	123.190
regression_4709	315.940
ram_blowup_regression	512.570
rollup-root	498.700
rollup-merge	473.340
rollup-block-root	1230.000
rollup-block-merge	498.710
rollup-base-public	734.390
rollup-base-private	590.800
private-kernel-tail	180.840
private-kernel-reset	245.440
private-kernel-inner	208.840

[github-actions]

Compilation Memory Report

Program	Peak Memory
keccak256	77.560
workspace	123.870
regression_4709	424.070
ram_blowup_regression	1460.000
rollup-root	601.600
rollup-merge	494.440
rollup-block-root-single-tx	16060.000
rollup-block-root-empty	489.060
rollup-block-root	16070.000
rollup-block-merge	601.590
rollup-base-public	2380.000
rollup-base-private	1140.000
private-kernel-tail	207.250
private-kernel-reset	584.400
private-kernel-inner	294.620

[github-actions]

Compilation Report

Program	Compilation Time	%
sha256_regression	1.190s	15%
regression_4709	0.821s	2%
ram_blowup_regression	17.200s	6%
rollup-root	3.622s	1%
rollup-merge	2.112s	1%
rollup-block-root-single-tx	137.000s	-6%
rollup-block-root-empty	2.068s	-1%
rollup-block-root	138.000s	-1%
rollup-block-merge	3.746s	6%
rollup-base-public	48.040s	73%
rollup-base-private	14.320s	40%
private-kernel-tail	0.966s	-4%
private-kernel-reset	6.480s	7%
private-kernel-inner	2.058s	-1%

[github-actions]

Execution Report

Program	Execution Time	%
sha256_regression	0.052s	-2%
regression_4709	0.001s	0%
ram_blowup_regression	0.601s	1%
rollup-root	0.104s	0%
rollup-merge	0.007s	0%
rollup-block-root	38.900s	1%
rollup-block-merge	0.104s	0%
rollup-base-public	1.224s	0%
rollup-base-private	0.455s	0%
private-kernel-tail	0.019s	0%
private-kernel-reset	0.313s	0%
private-kernel-inner	0.067s	-2%

[TomAFrench]

This is a pretty brutal increase, we may need to switch off this check by default if this is unavoidable.

[rkarabut]

This is a pretty brutal increase, we may need to switch off this check by default if this is unavoidable.

Indeed, would have to look into it

[TomAFrench]

#6698, #6706, #6713, #6735

Can you mark which of these this PR closes? I'd like to avoid dangling issues.

[rkarabut]

Can you mark which of these this PR closes? I'd like to avoid dangling issues.

Should be all of them

[github-actions]

⚠️ Performance Alert ⚠️

Possible performance regression was detected for benchmark 'Compilation Time'.
Benchmark result of this commit is worse than the previous benchmark result exceeding threshold 1.20.

Benchmark suite	Current: 4835e11	Previous: b3a8f39	Ratio
rollup-base-public	33.16 s	26.7 s	1.24
rollup-base-private	12.86 s	10.022 s	1.28

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

CC: @TomAFrench

[rkarabut]

@TomAFrench should we merge with the current (greatly reduced but still out there) performance hit? I've dealt with the main culprit which turned out to be an actual bug but the check is still slower now just because of increased complexity. I believe I can bring it further down with some optimization, or otherwise make certain new features optional. The question is, do we need that in this PR or can it be taken care of separately?

[rkarabut]

@TomAFrench with the latest fixes and optimizations as well as introducing limiting constraint search depth, only rollup-base-private seems to be slightly exceeding the 1.2 compilation time threshold on CI at the time:

Is this alright? If so I'll ask @michaeljklein to review the changes introduced and merge.

PS: also, I think the lookback feature (resolving #6735) can be made optional. It doesn't show any new bugs in rollup-base-public at the moment, its security impact is questionable, but judging by my performance experiments it increases the compilation time significantly.

[TomAFrench]

Currently testing this on rollup-block-root

[TomAFrench]

Merging this but we're likely going to have to make this pass opt-in due to it hanging on larger circuits.

[rkarabut]

Merging this but we're likely going to have to make this pass opt-in due to it hanging on larger circuit

Let's see if disabling just the lookback part helps. I'll make an issue for this