Batch input-notes commitment: nullifier order (ProposedBatch) vs transaction order (kernel)

[mmagician]

Problem

ProposedBatch::input_notes() is sorted by InputNoteCommitment::nullifier, and its commitment() hashes the notes in that nullifier order.

The batch kernel instead reconstructs the input notes by walking the pre-image chain anchored in BATCH_ID (BATCH_ID -> (tx_id, account_id) tuples -> per-tx INPUT_NOTES_COMMITMENT -> (nullifier, note_id) tuples), which yields the notes in transaction-ID (batch) order. So the kernel's INPUT_NOTES_COMMITMENT equals ProposedBatch::input_notes().commitment() only when transaction order already coincides with nullifier order.

The two need to agree on one order. Two options:

Option A — re-sort in MASM

Sort the absorbed (nullifier, note_id) tuples by nullifier inside the kernel before hashing.

• Interface: unchanged. ProposedBatch::input_notes().commitment() stays nullifier-ordered; the kernel is made to match it.
• Pros: keeps the canonical nullifier-sorted commitment; no Rust API change; commitment is independent of intra-batch transaction ordering.
• Cons: an in-VM sort of 4-felt-keyed words is complex and likely expensive, and it sits on the hot proving path.

Option B — commit in transaction order

Define the batch input-notes commitment as the hash of the notes in transaction order (what the kernel already produces) and change ProposedBatch to derive its commitment the same way.

• Interface: ProposedBatch's input-notes commitment is computed by hashing the notes in transaction order (notes may still be exposed nullifier-sorted for lookup, but the committed sequence is transaction-ordered).
• Pros: kernel stays simple and cheap (no sort).
• Cons: the commitment becomes dependent on intra-batch transaction ordering (same notes, different tx order → different commitment); diverges from the nullifier-sorted convention; requires changing the ProposedBatch/InputNotes commitment derivation.

---

Other ideas are welcome!

Reference: #3022

[bobbinth]

I think option B is probably the right approach here because the complexity/efficiency of the batch kernel is one of the main guiding criteria for us.

Having said that, we should probably sketch out the high level algorithm of the batch kernel to make sure we in fact simplify or make things more efficient with this change. Here is how I think it could work:

• One of the first things the batch kernel would do is to lay out all the necessary supporting structures in memory. For example, these would include the anchor block header, the chain MMR associated with this block etc. It would also include some structures that would get filled out as the kernel progresses - these are the ones we'll need to define more precisely as we think through the logic.
• Then, the kernel will start walking through the (tx_id, account_id) tuples to verify the batch_id input commitment. This basically means it'll be processing one transaction at a time. I believe with some recent changes, the way the batch ID is built is in the dependency order: if transaction A depends on transaction B then A comes after B (if this is not the case, we should update the batch ID commitment methodology.
• For each transaction, the batch kernel needs to verify that:
  • The transaction builds on the latest known state of the account. This would probably require keeping a map of AccountId |-> AccountStateHash. Naively we can use an SMT for this - but that would probably be way too expensive. So, we might have to use something like a LinkMap or maybe something else.
  • The input notes of the transaction are either authenticated or have been produced by some prior transaction (and haven't been consumed by some prior transaction yet). This could also be done with an SMT-based map, but again, that's probably prohibitively expensive, and we'd need to do something else.
  • Verify the transaction proof.
• Once all transactions have been processed:
  • Append transaction's input notes (the ones that are not erased) to the input notes commitment.
  • Insert transactions output notes (the ones that haven't been erased) into the batch note tree.
  • Probably some other stuff I'm not thinking about now.

---

A big part of the complexity here will come from the fact that we cannot use simple SMT-based maps (the hashing overhead of these will be just too expensive - especially if we move to something like Blake3-based hashing). So, we'll need to rely on some non-deterministic tricks to make things not too complicated and pretty efficient.

For example, to address the need to track latest account states, we could do the following:

In the first phase of the kernel (laying out supporting structures in memory), the kernel could get a list of all accounts updated by the batch non-deterministically. The kernel then would lay out the following structure in memory:

[[acct_id_1_suffix, acct_id_1_prefix, 0, 0, ZERO], [acct_id_2_suffix, acct_id_2_prefix, 0, 0, ZERO], ...]

Basically, two words per account: first word contains account ID and the second word for tracking account state and initialized to an empty word.

At this point, the kernel will verify that the list of account IDs does not contain duplicates - for this, the list would need to be sorted by ID.

Then, as we process each transaction, we'd do the following:

• Do a non-deterministic lookup in this list for an account that the transaction is being executed against. This would give us a pointer to the account entry. This should always succeed because the promise was that all accounts are present in this list at most once.
• If account state is ZERO, this must be the first transaction that is touching this account. In this case, we just update the state to the account's output state from the transaction.
• If account state is not ZERO:
  • We first make sure that the state matches the input account state of the transaction (and abort if it doesn't).
  • We then update the state to the transaction's output account state.

This way, this list always tracks the latest account state after a given transaction - and enforcing account update dependency DAG becomes pretty easy.

Also, at the end, we naturally get a list of accounts' final states sorted by account ID (and if we wanted, with minor modifications we could change that to (account_id, initial_state_hash, final_state_hash) pretty easily - e.g., in case we need this as a batch kernel output.

---

The main reason I described the above is that maybe something similar will have to be done for input/output notes which will end up with naturally sorting nullifiers - or something similar. But I haven't actually thought through the mechanics there enough to know if that's the case.

[bobbinth]

Thinking more about the input notes, maybe the solution could look something like this:

In the beginning of the batch kernel (let's call this the kernel "prologue" to keep things consistent with the tx kernel), in addition to the list of updated accounts, we'd get a list of all input notes. These notes would be laid out in memory like so:

[[NULLIFIER1, erasure, consumption, 0, 0], [NULLIFIER2, erasure, consumption, 0, 0], ...]

Where erasure and consumption are flags defined as follows:

• erasure is set to:
  • 0 we do not expect the note to be produced by any transaction in this batch.
  • 1 if we expect the note to be produced by a transaction in this batch.
  • 2 if we've verified that the note has been produced by a transaction in this batch.
• consumption is set as follows:
  • 0 we haven't yet verified that the note has been consumed by a transaction in this batch.
  • 1 we have verified that the note has been consumed by a transaction in this batch.

Initially, the values for erasure would be 0 or 1, and for consumption only 0.

In the prologue, the batch kernel will verify that the list of nullifiers does not contain duplicates - for this, the nullifiers will need to be sorted.

Then, as we process each transaction, the kernel will do the following:

For each input note:

• Look up the note non-deterministically by its nullifier. This would give us a pointer to the note entry.
• If the note's consumption flag is set to 1 (i.e., the note has been consumed by some prior transaction), error out. Otherwise, set the consumption flag to 1.
• If the note's erasure flag is set to 1 (i.e., the note is expected to be produced in this batch, but we haven't seen a transaction that produced it yet), error out.

For each output note:

• Look up the note non-deterministically by its nullifier. This will also need to handle the case when the output note is not in the list of input notes.
• If the output note is in the input note list:
  • If erasure == 1, set it to 2, otherwise, error out.

After all notes have been processed, in the batch kernel epilogue, we'll need to go over the list of input notes again and check that:

• consumption flag for all notes is set to 1 - i.e., all claimed input notes have been consumed in some transaction.
• erasure flag is not set to 1 for any note - i.e., all notes that were claimed to be erased, have been erased.
• For any note with erasure == 0, we have an authentication path against the chain MMR (though, this can be done in the prologue too).

---

The above approach will give a list of input notes sorted by nullifier, though, this list will have "holes" in it (i.e., notes with erasure == 2 which have been erased in the batch).

Something similar we'll probably need to do for the output notes - but I haven't thought about this yet.

[PhilippGackstatter]

I think we probably don't need to change the input notes commitment, if we set up the batch in MASM similar to the batch in Rust. Then, we'll end up with the same outcome and the same commitments.

I think @bobbinth's approach for aggregating accounts seems good. I believe next to tracking initial and final state commitments, we'll also need to merge account patches in the kernel (so we can compute the aggregated patch commitment per account), which I think will be easiest by factoring out the delta/patch logic of the tx kernel into a shared library and reusing/extending it.

I wrote up the approach based on mirroring ProposedBatch a while ago but forgot to update and post it. It's a high-level sketch:

#! Inputs:  [BLOCK_COMMITMENT, TRANSACTIONS_COMMITMENT]
#! Outputs: [INPUT_NOTES_COMMITMENT, OUTPUT_NOTES_SMT_ROOT, batch_expiration_block_num]
#!
#! Where:
#! - BLOCK_COMMITMENT is the commitment to the batch's reference block.
#! - TRANSACTIONS_COMMITMENT is the sequential hash over [(TRANSACTION_ID, account_id_{suffix, prefix})].
#! - INPUT_NOTES_COMMITMENT is the sequential hash of `[(NULLIFIER, EMPTY_WORD_OR_NOTE_COMMITMENT)]` where `EMPTY_WORD_OR_NOTE_COMMITMENT` is `hash(NOTE_ID || NOTE_METADATA_COMMITMENT)` for unauthenticated notes.
#! - OUTPUT_NOTES_SMT_ROOT is the root of the SMT with leaves hash(NOTE_ID || NOTE_METADATA_COMMITMENT).
#! - batch_expiration_block_num is the highest number of the block into which the batch can be included.
pub proc main
  # 0. Hash advice inputs and check against public inputs.
  # ---------------------------------------------------------------------------------------------

  # 1. Check for empty or duplicate transactions.
  # -> Data structures: sorted_array?
  # ---------------------------------------------------------------------------------------------

  # 2. Verify block header and partial blockchain match.
  # -> Data structures: MMR
  # ---------------------------------------------------------------------------------------------

  # 3. Verify all block references from the transactions are in the partial blockchain, except
  #    for the batch's reference block.
  # -> Data structures: None
  # ---------------------------------------------------------------------------------------------

  # 4. Aggregate individual tx-level account updates into a batch-level account update - one per
  #    account.
  # -> Data structures: LinkMap (through account delta logic)
  # ---------------------------------------------------------------------------------------------

  # 5. Check that all transaction's expiration block numbers are greater than the reference
  #    block and compute `batch_expiration_block_num`.
  # -> Data structures: None
  # ---------------------------------------------------------------------------------------------

  # 6. Create input and output note set of the batch (`InputOutputNoteTracker`).
  #    - Check for duplicate input notes.
  #    - Check for duplicate output notes.
  #    - Authenticate unauthenticated notes.
  #    - Erase notes that are consumed and created in this batch.
  # -> Data structures: MMR (note auth) & sorted_array or LinkMap
  # ---------------------------------------------------------------------------------------------

  # 7. Compute the INPUT_NOTES_COMMITMENT based on all input notes without erased notes.
  # -> Data structures: LinkMap (iteration)
  # ---------------------------------------------------------------------------------------------

  # 8. Compute the OUTPUT_NOTES_SMT_ROOT based on all output notes without erased notes.
  # -> Data structures: BatchNoteTree MASM port
  # ---------------------------------------------------------------------------------------------

  # 9. Verify transaction ZK proofs.
  # -> Data structures: None?
  # ---------------------------------------------------------------------------------------------
end

Notes

• If we go with this approach, the input notes commitment would be built by iterating the link map from the InputOutputNoteTracker, and it would be naturally sorted by nullifier already, so we should get the same commitment as ProposedBatch.
• sorted_array refers to miden::core::collections::sorted_array.
• We'll need a BatchNoteTree MASM port built on mtree_* VM instructions.
  • We'll also need BlockNoteTree eventually, so makes sense to have something that is parametric over tree depth.
• We'll need to factor out the link map from the tx kernel into a library, so we can use it from both tx, batch (and block) kernels. I have a half-written idea for this, but seems lower priority (?)
• Constructing a LinkMap from advice inputs.
  • That way, the host can easily provide account patches as advice input.
• Where can we outsource work to the host? E.g. InputOutputNoteTracker needs a simple way to compare the input and output note set against each other.
  • Host could provide sorted list of input and output notes and batch logic checks that all input/output notes in all transactions are 1) contained in that sorted list and 2) are only marked once as "exists" and 3) the total number of notes in the set and the number of notes that was iterated matches. Though we'd also need to make sure that no note is left marked "non-existent" - so this just a first idea.

I think the bottom line is that even computing the input notes commitment in the batch kernel now is tricky. I think changing the way we compute the commitments now would be the wrong choice as we should be able to match the Rust logic later more easily.

[bobbinth]

We'll need to factor out the link map from the tx kernel into a library, so we can use it from both tx, batch (and block) kernels. I have a half-written idea for this, but seems lower priority (?)

I'm hoping we can avoid link maps for this and maybe just rely on sorted arrays.

[bobbinth]

Now putting input and output notes together:

Let's say in addition to laying out input notes as I described in #3025 (comment), we also lay out all output notes as follows:

[[NULLIFIER1, will_be_erased, is_created, 0, 0], [NULLIFIER2, will_be_erased, is_created, 0, 0], ...]

Both will_be_erased and is_created flags are initialized to 0.

Then, the kernel would work roughly like so:

Prologue

We first lay out all the output notes in memory and make sure there are no duplicates. This means the output note list is sorted by the nullifier and we just need to check that $nullifier_n < nullifier_{n+1}$.

Then we lay out input notes in memory and also make sure that there are no duplicates. As we lay the notes out, for each note that has erasure == 1, we find a corresponding output note (it is guaranteed to exist), and set will_be_erased for this note to 1. This guarantees that every output note which is marked for erasure has a corresponding input note.

Transaction processing

As we process each transaction, we do the following:

For each input note:

• Look up the note non-deterministically by its nullifier in the input notes list. This would give us a pointer to the note entry.
• If the note's consumption flag is set to 1 (i.e., the note has been consumed by some prior transaction), error out. Otherwise, set the consumption flag to 1.
• If the note's erasure flag is set to 1 (i.e., the note is expected to be produced in this batch, but we haven't seen a transaction that produced it yet), error out.

For each output note:

• Look up the note non-deterministically by its nullifier in the output notes list. This would give us a pointer to the note entry.
• If the note's is_created flag is set to 1 (i.e., the note has been created in some prior transaction), error out. Otherwise, set is_created to 1.
• If the note's will_be_erased is set to 1, find the corresponding note in the input notes list`. This would give us a pointer to the note entry, then:
  • If erasure == 1, set it to 2, otherwise, error out.

Epilogue

Iterate over the input note list and for every note:

• Make sure that consumption == 1 - i.e., all claimed input notes have been consumed in some transaction.
• If erasure == 1, error out (the note that was claimed to be erased, wasn't).
• If erasure == 0, verify that the note is authenticated - i.e., we have a proof against chain MMR. Then, add the note to the inputs note commitment for the transaction.

Iterate over output note list and for every output note:

• Make sure is_created == 1 - i.e., all claimed output notes have been created by some transaction.
• If will_be_erased == 0, insert the output note into the batch note tree (for this, we may also need to track note ID for each output note).

---

I believe the above should achieve all our goals and should be relatively efficient. But let me know if you find any holes in the logic.

[mmagician]

I think we can simplify the erasure flag on the input notes, and reduce the flag to just 0(not erased) and 1(erased). This requires a small flip to how we indicate erasure, namely instead of providing the erasure = 1 hint on the input notes, we initialize will_be_erased = 1 for output notes instead (AFAIU, these hints are non-deterministic). Then

• output notes with will_be_erased == 1 change the erasure flag of the matching input note 0 -> 1. (error out if already set to 1)
• in the epilogue,
  • we verify that input notes with erasure == 0 are authenticated
  • we exclude input notes with erasure == 1 from calculating INPUT_NOTES_COMMITMENT

This also guarantees that:

• output notes marked as will_be_erased == 1 have a corresponding input note that is going to be erased
• input notes with erasure == 1 have been marked by some matching erased output note
  Which are the two guarantees we need AFAIU.

EDIT: Correction to my comment above about collapsing the input-note erasure flag to 0/1: that simplification drops the ordering/cycle check.

The two properties I listed are correspondence guarantees only (input and output notes have a matching counterpart). They say nothing about when the creating transaction ran. @bobbinth third state is a temporal gate that enforces created-before-consumed notes and rejects circular dependencies.

With a pure 0/1 flag driven by the non-deterministic will_be_erased hint, cycles are no longer prevented.