0xMiden / 0xMiden/protocol

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

Đang mở
#3,025 6 bình luận 0 reaction 0 người được giao Xem trên GitHub
kernels
Ngôn ngữ chính
Rust
Star
132
Fork
167
Merge trung bình
1 ngày 23 giờ
Pull request đã merge (30 ngày)
110

Mô tả

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

Hướng dẫn đóng góp

Mở hướng dẫn đóng góp

Đánh giá

Issue này chưa được đánh giá.

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.