0xPolygonMiden / miden-vm

STARK-based virtual machine
MIT License
632 stars 161 forks source link

Fix operation batch flags constraints #1495

Closed plafer closed 2 months ago

plafer commented 2 months ago

Fixes the operation batch flag constraints, as well as a minor fix in the op group table auxiliary constraints.

bobbinth commented 2 months ago

One simplification idea: we could get rid of op_batch flags entirely by always adding 8 operation groups to the op_group table. The cost of this is that for empty groups we'd need to execute a single noop operation (so, in the worst case, 7 noops in total). But it will make the constraint system simpler and will allow us to get rid of 3 columns (I think).

bobbinth commented 2 months ago

Or maybe there is a half-way solution where we have a single flag which basically says "add either 4 or 8" groups. In this case, the constraints are also quite a bit simpler, we get rid of 2 columns, and the worst case cost is 3 extra noops per span.