0xMiden / 0xMiden/protocol

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

Abierto
#3,025 6 comentarios 0 reacciones 0 asignados Ver en GitHub
kernels
Lenguaje dominante
Rust
Estrellas
132
Forks
167
Merge medio
1 d 23 h
PR fusionados (30 d)
110

Descripción

## 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

Guía de contribución

Abrir la guía de contribución

Evaluación

Este issue todavía no se ha evaluado.

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.