Unified stdlib procedures call and VM instructions syntax

[hackaugusto]

What is this proposing?

Remove the need for the exec. syntax in front of stdlib procedures calls.

Why?

This would unify the concept of instructions and stdlib procedures. The idea is to enable the following:

1. More than 255 VM instructions
2. Smart contract pre-compiles
3. Rollout a different set of optimized VM instructions

255 VM instructions

This limit exists because the instructions are represented using a single byte, and the space is close to run out.

Once we run out these are the options:

1. Never add a new instruction again.
2. Maintain backwards compatibility by using variable encoding, and signal that with an extension byte (we no longer can use an extension bit, like in UTF8).
3. Break backwards compatibility
   1. Replace instructions
   2. Extend the size from a byte to something else (this proposal falls in this category)

Smart contract pre-compiles

This point is analogous but not the same as smart contract precompiles, it makes more sense to call it pre-compile opcodes.

The VM has a few optimized opcodes already, like u32 arithmetic. However, it is unclear what users will need since there is no user code yet. The idea here is to allow the procedures in the stdlib to be optimized in a backwards compatible manner, this is only useful for on-chain account, which would otherwise need to replace their code to benefit of new optimizations (updating the code will likely not be supported for all accounts, e.g. token faucets).

Note: This is ofcourse limited in impact, we can only add optimized opcodes for what is in the standard library. So, for example, if a new procedure is added to the stdlib because we want to introduce a precompile, then existing code would not be calling it and would not benefit from the change. I don't know how to fix this issue besides having a comprehensible stdlib that would increase the likely hood of this approach working.

Modify set of optimized instruction

In a future release it may be the case that we need to replace some internal data structures/algorithm. In that case we most likely will want to preserve the behavior of the existing code, albeit running slower, and add optimized operations for the new data structures. This proposal achieves this by allowing for de-optimizing instructions in a backwards compatible, for example, by replacing a rpohash with non-native operations.

Downsides

1. This will increase the size of the MASL, since the instructions size would increase from a byte to a word (possible optimization describe below)

Implementation

1. At the MASM level this would remove the exec. prefix from stdlib calls.
2. At the MASL level this would remove the u8 instruction representation in favor of a stdlib_call to a procedure. This is what causes the increase in the MASL size.
   1. To greatly reduce this cost, we just have to introduce an array of hashes to the MASL binary, then instead of having stdlib_call.0x1234 which would be at least one word in length, we would have stdlib_call.<index> which can be significantly smaller.
3. The address of the the stdlib_call would not be content addressable, as in the value of the hash stdlib_call.0x1234 is not the instructions used in the procedure, but the procedure name.
4. This does not affect the opcodes, only the instructions. So the opcodes packing, MAST hashing, and all the existing VM constraints would be unaltered.

prelude prefix

The idea above allows the implementation of a stdlib procedure to change, but never its semantics. To allow for semantic changes there could be a versioned prelude, e.g. prelude::v1, deployed code would always refer to the previous prelude with the previous semantics, and new code would be compiled against prelude::v2 with the new semantics.

procedure hash

Because the code is no longer content addressed, this type of upgrade should be limited to the stdlib, user code would not be upgradable like this.

The idea is that the VM and the stdlib are maintained together and already trusted/auditable. So this type of addressing should be okay.

Procedure -> opcode translation

It would be very similar to what is done today in the Assembler, the difference is that the translation would be done in the procedure instead of the instruction level.

This proposal does not affect operation encoding/decoding, the program/MAST hashing, and any of the VM constraints, the proposal is exclusively about how to handle stdlib procedures.

Out of scope

1. Define which instructions should be optimized, that is a lot of work and not the intention here. The goal here is to make it possible to add new native opcodes in a backwards compatible way
2. Proofs would not be compatible, because changes to the procedures would change the program hash.

[bobbinth]

I'd probably hold off on this for now and revisit when/if we ran out of instruction space.

The idea here is to allow the procedures in the stdlib to be optimized in a backwards compatible manner,

This won't really work because changing procedures in meaningful ways will also change MAST roots and this will result in account interface commitment to be out of sync with assembly code. One thing that we will need to solve at some point is versioning: a .masm program should somehow specify which version of stdlib (or any other library) it was compiled against and which version of the assembler was used.

[hackaugusto]

This won't really work because changing procedures in meaningful ways will also change MAST roots and this will result in account interface commitment to be out of sync with assembly code

We could commit to the assembly instead of the mast root, no? Humm, I suppose then it becomes an issue on how to perform the unhashing? maybe both the assembly and the mast would need to be unhashed to prove one is related to the other for some version?

[bobbinth]

I thinking proving that Miden assembly source corresponds to a given MAST root would be super complicated - we'd basically have to run the Assembler within the VM and this will take a lot of time. Nodes can do that outside of the VM though and there could be strategy of how to deal with notes/accounts where masm code doesn't match the MAST root.