0xMiden / 0xMiden/protocol

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

Aperta
#3,025 6 commenti 0 reazioni 0 assegnatari Vedi su GitHub
kernels
Lingua principale
Rust
Stelle
132
Fork
167
Merge medio
1g 23h
PR unite (30g)
110

Descrizione

## 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: https://github.com/0xMiden/protocol/pull/3022

Guida per i contributori

Apri la guida per i contributori

Valutazione

Questa issue non è ancora stata valutata.

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.