0xPolygonMiden / miden-vm

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

Permit child `MastNodeId`s to exceed the `MastNodeId`s of their parents #1542

Closed PhilippGackstatter closed 2 weeks ago

PhilippGackstatter commented 1 month ago

Describe your changes

Permit child MastNodeIds to exceed the MastNodeIds of their parents during deserialization. This came up in the context of #1534 (see this comment chain for details).

Deserialization seems to be the only place where we had a requirement on the mentioned property, judging by the uses of MastNodeId::from_u32_safe.

A new constructor for MastNodeId was introduced that is similar to the existing one, except that it checks against a total expected node count of the forest instead of the current node count of the forest. This allows child IDs to exceed their parent's IDs, such as in a forest like

[Join(1, 2), Block(foo), Block(bar)]

However, we still want forests like this to fail during deserialization:

[Block(foo), Join(0, 2)]

And the added constructor handles these scenarios and both are tested.

Checklist before requesting a review

bobbinth commented 1 month ago

I'm wondering if we should try the approach I described in https://github.com/0xPolygonMiden/miden-vm/pull/1534#discussion_r1811370694 before going with this direction.

PhilippGackstatter commented 2 weeks ago

@plafer @bitwalker Do you want to go ahead with this PR? I just rebased and it's ready from my side.