Miden VM status

As of March 2024:

Miden VM is still work-in-progress. I would consider it to be at alpha stage of software development. While the core of the VM is working fine and is well-optimized, some pieces haven't been implemented and/or will be refactored.

Missing pieces

1. While the entire constraint system for Miden VM is described in the docs, some constraints have not been implemented yet. The biggest representative of this are the decoder constraints (but there are some others as well). Implementing these constraints is just a matter of effort, but we haven't put in this effort as the constraints are very likely to change quite a bit with some of the refactorings mentioned below. Once implemented, the constraints will have very minor impact on the prover performance (e.g., this may slow down the VM by less than 5%).
2. Some sections of docs may be missing or outdated. This is especially relevant to the sections mentioned in these issues: #389, #483, #758, #813.
3. There is a soundness bug in one of memory operation constraints (specifically, in constraints for MSTORE operation). We haven't addressed this as we are planning to refactor the memory subsystem to enable element-addressable memory (see here).
4. There is a bug in the implementation of the kernel procedure table (see here).
5. Recursive verifier is incomplete (and is actually currently broken). To complete this, we need to finish AirScript and optimize MASM backend.

Future refactorings

1. Handling of virtual tables and communications busses (currently implemented using multiset checks and LogUp) will likely change. Specifically, we are planning to migrate to GKR+LogUp based implementations for these (see here). This is one of the reasons why the code dealing with auxiliary column construction is currently pretty messy.
   a. This change will also affect the recursive verifier - so, the work on that is on hold until GKR+LogUp is implemented.
2. Memory subsystem will likely be refactored to support element-addressable memory (see here).
3. We are also considering adding first-class support for read-only memory (see here).
4. We will try to reduce the total number of operations natively supported by the VM. This will affect the decoder design and will lead to improved prover performance. As a part of this refactoring we will try to reduce the number of main trace columns from the current 70 to 64.
5. We've also discussed adding support for full-fledged component model in Miden VM (see here) - but this may be something for the long-term future (especially if we land on an acceptable solution for rodata segments).
6. We plan to migrate to the Plonky3 prover/verifier in the medium term (e.g., by the end of summer or early fall).
7. The VM is currently using Rescue Prime Optimized (RPO) as the native hash function. We may switch to RPX hash function (appendix C in this) if we gain enough confidence in it (audits for RPX are in progress).