0xMiden / 0xMiden/protocol

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

未關閉
#3,025 6 則留言 0 個 reaction 已指派 0 人 在 GitHub 檢視
kernels
主要語言
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 還沒有評估資料。

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。