Batch input-notes commitment: nullifier order (ProposedBatch) vs transaction order (kernel)
- 主要語言
- Rust
- 星號
- 132
- 分支
- 167
- 平均合併
- 1 天 23 小時
- 30 天內合併 PR
- 110
描述
## 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
貢獻指南
評估
這個 Issue 還沒有評估資料。