Tracking issue: core functionality for Miden VM constraints

[grjte]

Goal(s)

• functionality for defining ~90% of constraints for Miden VM and Polygon Zero
• codegen for hardware acceleration
• improved testing for code correctness

Details

Functionality for Miden VM & Polygon Zero

In order to define the constraints on the stack overflow column in Miden VM we need a way to declare public input vectors of unknown size

We need to make the process of defining boundary constraints more flexible for Polygon Zero. We can do this by making it possible for them to define lagrange polynomials directly. This requires:

• enabling declaration of validity constraints (constraints against a single row that don't follow the boundary constraint convenience syntax used by Miden VM)
• giving access to the x value in each row via a new built-in $x

Codegen for hardware acceleration

1. Add Sub to the IR
2. Implement codegen option for generic constraint evaluation format #56

Improved testing

We need unit tests for the IR and the codegen modules. We should come up with a good setup (possibly using an external tool) that keeps our tests simple and readable and can be used for all codegen cases.

Tasks

Preview Give feedback

We're having trouble rendering your tasklist, it's most likely has one of the following formatting errors:

• indented tasks (i.e. nested tasklist; support for this is coming!)
• an empty task (i.e. - [ ] on a line by itself)
• any empty new lines (before/after the tasklist or in between tasks)
• duplicate issue/pr links
• a draft task exceeds 512 characters

Please check the tasklists documentation for more information. 🔗 Feedback Discussion

Thank you for participating in the Private Beta ❤️

1. Add Sub to IR #68
   IR v0.2 +2
   
2. merge boundary constraints into AlgebraicGraph and support variables #106
   +0
   
3. Consider making trace reference more general in the IR #54
   enhancement v0.2 +2
   
4. Add validity constraints #84
   IR parser v0.2 +3
   

Tasks

Preview Give feedback

We're having trouble rendering your tasklist, it's most likely has one of the following formatting errors:

• indented tasks (i.e. nested tasklist; support for this is coming!)
• an empty task (i.e. - [ ] on a line by itself)
• any empty new lines (before/after the tasklist or in between tasks)
• duplicate issue/pr links
• a draft task exceeds 512 characters

Please check the tasklists documentation for more information. 🔗 Feedback Discussion

Thank you for participating in the Private Beta ❤️

1. Remove Neg operation from IR #108
   IR good first issue +2
   
2. Implement codegen option for generic constraint evaluation format #56
   codegen +1
   

Working group:

@Al-Kindi-0, @grjte, @Overcastan, @tohrnii

Workflow

• Discussion should happen here or in the related sub-issues.
• PRs should only be merged by the coordinator, to ensure everyone is able to review.
• Aim to complete reviews within 24 hours.
• When a related sub-issue is opened:
  • add it to the list of sub-issues in this tracking issue
• When opening a related PR:
  • request review from everyone in this working group
• When a sub-issue is completed:
  • close the related issue with a comment that links to the PR where the work was completed

Coordinator: @tohrnii

The working group coordinator ensures scope & progress tracking are transparent and accurate. They will:

• Merge approved PRs after all working group members have completed their reviews.
  • add the PR # to the relevant section of the current tracking PR.
  • close any completed sub-issue(s) with a comment that links to the PR where the work was completed
• Monitor workflow items and complete anything that slips through the cracks.
• Monitor scope to see if anything is untracked or unclear. Create missing sub-issues or initiate discussion as required.
• Monitor progress to see if there's anything which isn't moving forward. Initiate discussion as required.
• Identify PRs with especially significant changes and add @grjte and @bobbinth for review.

[bobbinth]

In order to define the constraints on the stack overflow column in Miden VM we need a way to declare public input vectors of unknown size

One thing I realized is that I don't think this will be enough. Assuming we have such vectors, we won't be able to use them since we can't iterate over all elements in such vectors. To address this, we'll need to implement iterators.

[bobbinth]

• enabling declaration of validity constraints (constraints against a single row that don't follow the boundary constraint convenience syntax used by Miden VM)

This might be as simple as renaming transition_constraints into integrity_constraints (or something similar) as described in #53. In the IR, we should still probably have a single algebraic DAG, but we could mark entry points as transition vs. validity constraints.

[grjte]

This might be as simple as renaming transition_constraints into integrity_constraints (or something similar) as described in #53. In the IR, we should still probably have a single algebraic DAG, but we could mark entry points as transition vs. validity constraints.

Agreed about the single DAG & continuing the discussion from #53. We just need to separate #53 into 2 different issues and then we can add the issue for validity constraints here & move this discussion into it. I think @tohrnii is doing that while adding/updating the other sub-issues we need for this task

[grjte]

Two points came up for discussion in PR #63

1. Do we want to use column-major or row-major form for matrices? (reference)
2. Having constants in uppercase looks a bit strange inside the source section. Alternatively, we could define constants at the top of the file instead of having a separate source section. Something like the following:

const EXAMPLE = 5

[tohrnii]

@grjte There's #89 to track 2 and bobbinth also likes this approach. This also makes me wonder if we should also decide on a place to discuss issues that come up during reviews. Maybe we should do that in the corresponding sub-issue and then only open a new issue for that if it doesn't get resolved only through discussions there. What do you think?

[grjte]

This also makes me wonder if we should also decide on a place to discuss issues that come up during reviews. Maybe we should do that in the corresponding sub-issue and then only open a new issue for that if it doesn't get resolved only through discussions there. What do you think?

Yes, discussing in the corresponding sub-issue makes sense, let's do that! I meant to put it in the corresponding tracking issue (#77), but accidentally put it in here instead, sorry!

[Dominik1999]

Was there any progress here last week? Do you need anything to be unblocked?

[tohrnii]

@Dominik1999 Issue 54 was completed last week and 56 will probably be completed this week. Nothing seems to be a blocker at the moment.

[Dominik1999]

@tohrnii still all good here?

[tohrnii]

@Dominik1999 I think we should be able to complete most of the must haves by end of next week.