Implement batch kernel in MASM

[PhilippGackstatter]

What should be done?

Implement the transaction batch kernel in Miden Assembly.

How should it be done?

This may have to be divided into smaller tasks, but the high-level goals are:

• Add batch kernel to miden-lib, add it to build.rs and export it as a (Transaction)BatchKernel struct in Rust, similar to the existing TransactionKernel.
• Add utility functions for preparing the stack inputs, advice inputs as well as parsing the outputs of the batch kernel. The inputs were discussed in Define batch kernel inputs/outputs #919.
• Implement checks and computations from ProposedBatch::new in MASM.
• Add the resulting ExecutionProof from executing the batch kernel to ProvenBatch.

When is this task done?

When the batch kernel execution can be proven in MASM.

Additional context

No response

[PhilippGackstatter]

The block kernel doesn't require that account state transitions are provided in a sorted order, instead it creates the order itself. The batch kernel does require that transactions are ordered in this sense:
If we have some tx 1 and 2 against the same account starting with state commitment X and X -> 1 -> Y -> 2 -> Z, then 1 must come before 2 in the batch inputs.

I haven't thought this through completely and I'm not sure if it's necessary to have, but just for future consideration: I'm thinking if we need to implement the "sorting" of state transitions for the block kernel anyway, maybe it is possible to have a shared MASM module that does this and it could also be used in the batch kernel to lift the restriction for ordering. The benefit may be that we can have a single "account state aggregator" in MASM which would work for both batch and block kernel and results in less code overall. To test whether this is possible and makes sense, we could try to refactor the AccountUpdateAggregator to try and work for both batch and block.

[bobbinth]

Good idea! Overall, one possible approach to verify the consistency of account updates is to have the prover provide the correct order of updates and write it out in memory. The layout could look something like this:

[account_id_prefix, account_id_suffix, 0, 0, UPDATE1_INIT, UPDATE1_FINAL, UPDATE2_INIT, UPDATE2_FINAL, ...]

Then, we'd need to guarantee 3 things:

• All updates coming from a given set of transactions/batches are in this list.
• No additional updates are in this list.
• The list is internally consistent:
  • Final state of update $n$ is equal to initial state of update $n-1$.
  • An account ID appears only once.

This is just an idea - there could be other ways of doing this too.