Epic: Folding

[vezenovm]

Problem

With folding becoming a popular new recursion technique among SNARK proving systems we should implement a clean interface for backends to handle folding multiple ACIR function calls as they see fit.

We currently inline all function calls in ACIR. We pass one ACIR blob to the backend essentially representing a single ACIR function.

Happy Case

ACIR/ACVM circuits should support multiple function calls that backends can implement how they see fit (either by folding or inlining those calls).

Tasks

Beta Give feedback

1. ACIR: Call opcode #4427
   ACIR/ACVM enhancement +2
   
2. ACIR gen / ACVM: Handle non-inlined ACIR functions #4428
   acir-gen enhancement ssa +3
3. ACIR gen: Enable complex outputs to ACIR function calls #4608
   acir-gen enhancement +2
4. Enable numeric generic inputs for non-inlined ACIR #4826
   compiler compiler frontend enhancement +3
5. ACVM JS: Handle executing multiple circuits #4645
   ACIR/ACVM enhancement js +3
6. Noir JS: Utilize new program execution functions from ACVM JS #4706
   enhancement js +2
7. ACIR gen / ACVM: Handle predicates in non-inlined ACIR #4707
   acir-gen enhancement +2
8. ACIR gen: Handle recursive ACIR calls #4616
   acir-gen enhancement +2

Nice to have:

Tasks

Beta Give feedback

1. Nargo: Expand info cmd to support multiple circuits #4697
   bug +1
   
2. Nargo: Handle non-inlined Acir circuit info for contract functions #4720
   enhancement nargo +2
3. Allow querying the gates in a Program in a single request to the backend. #4851
   +0
   

Project Impact

Blocker

Impact Context

This is needed for meaningfully fast client recursion by not only Aztec but any Noir program. Without folding backends can only implement vanilla IVC recursion which is significantly more expensive and restricts users.

Workaround

None

Workaround Description

No response

Additional Context

Both issues #4427 and #4428 will most likely be implemented in https://github.com/AztecProtocol/aztec-packages as they are both breaking changes.

Would you like to submit a PR for this Issue?

None

Support Needs

No response

[vezenovm]

I am going to close #4851 in the nice-to-have list above with the creation of #4962. I wanted to check on removing #4720 as well. #4962 states we plan to remove nargo info entirely. Does this include for ACIR opcodes? Or do we expect an info command from the backend to include this as part of their report? @TomAFrench

[TomAFrench]

I think that it makes sense to for the backend to return both the opcodes and constraints rather than trying to stitch them together from two different tools. Having a json response from the backend is the priority so we can maintain usage of the noir-gates-diff action but we'll need to have some form of report at some point.

[TomAFrench]

We can close #4851 but can you open an issue in aztec-packages for adding a human readable report for bb gates?

[vezenovm]

We can close #4851 but can you open an issue in aztec-packages for adding a human readable report for bb gates?

Looks like you made it here AztecProtocol/aztec-packages#6168?

[TomAFrench]

That's slightly different as I'm just wanting to get the JSON report as an MVP for this feature so we don't brick the github action. A human readable report can come in a separate PR imo.

[TomAFrench]

Feel free to tackle in the same PR if that's more convenient.

[vezenovm]

A human readable report can come in a separate PR imo.

Ah I didn't see the distinction for human readable report I'll make a separate issue

[vezenovm]

Issue to replace #4720 can be found here (AztecProtocol/aztec-packages#6190). Human readable report issue can be found here (AztecProtocol/aztec-packages#6189)

[vezenovm]

All issues in this epic have been completed. If new bugs or features come up, they will be created as separate issues.