Proposal: Separate local vs network notes at the protocol level (a.k.a. network notes without nullifiers)

[mmagician]

TL;DR

• Introduce a new Network Note DB for network notes
  • An SMT keyed by network_note_id with value as {empty / created / spent}
  • The SMT root becomes a fourth state commitment (alongside Account DB, Local Note MMR, Nullifier DB).
• Keep the current double-spend prevention design for local notes:
  • Local note commitments still inserted into the Note DB MMR (append-only).
  • Local note spends still use the Nullifier DB for double-spend protection.

0. Intro

Triggered by the discussion around NoteTag / NoteAttachment in #2109, I kept coming back to the split between local and network notes:

• Local notes – consumed in locally proven transactions by users.
• Network notes – consumed by the operator.

While some ideas in #2109 already push in the direction of some separation via NoteType and separate metadata structs, I think we could take this a step further and treat these as two distinct note classes at the protocol level, most importantly with distinct double-spend protection mechanisms.

The key motivation is to reduce the growth rate of the nullifier tree by not inserting nullifiers for network notes.

This discussion is somewhat complementary to #2109. It would function sort of like a Bitcoin-style UTXO set for network notes - but with a cryptographically backed data structure (SMT), so its root can be included in the L2 state commitment succinctly.

1. Motivation / observations

From reviewing #2109:

• There is a lot of structure that’s shared between local and network notes:

  • Concept of NoteTag for discovery & routing.
  • NoteAttachment as a general mechanism to carry extra data.
  • The fact they’re both “notes” in the UTXO sense, i.e. one-off consumable objects.

• But there are also obvious differences:

  • Local notes need to work well in constrained client-side environment with the persistent witness property (download the note inclusion proof once, it never goes stale).
  • Network notes are executed by the operator who doesn't care about persistent witness - the operator can be assumed to always have easy access to the latest state.
  • Network notes are always public: no need to pay the same mechanism price for privacy as for local private notes, since there's no privacy to start with.

Right now, both note families share the same data structures:

• All new notes (local + network) are registered via their commitment in the Note DB MMR.
• All consumed notes produce a nullifier inserted into the Nullifier DB.

This is simple and uniform, but has two downsides:

1. Nullifier DB growth – every consumption, including obviously-public network notes, contributes to nullifier state size increase.
2. Conceptual overload – the nullifier mechanism is primarily there to:
   • decouple “existence” from “spendability” for offline proving (persistent witness), and
   • preserve unlinkability for private notes,

But network notes need neither of these two properties.

2. Recap: why the current model works well for local notes

Just to restate the local note side, because it’s important for what follows:

• Note DB is an append-only MMR of note commitments.
  • Append-only ⇒ the Merkle path (note inclusion proof) for a given note never becomes stale.
  • A user can cache the path once (e.g. when they receive the note) and later generate a local tx proof without needing an updated Note DB root.
• Nullifier DB is an SMT keyed by nullifier.
  • Mutable structure.
  • Double-spend prevention for notes is: nullifier ∉ NullifierDB before block, then insert it.

So to consume a note, the user needs, among other things:

• A cached MMR note inclusion proof.
• The ability to compute the nullifier (which is later checked for uniqueness)

The local tx proof proves inclusion in Note DB + correct nullifier computation; then at block construction the protocol handles the nullifier part (non-membership + finally the insertion into the Nullifier DB).

3. Proposal: explicit separation of Local vs Network notes

The high-level idea:

• Local notes
  • Keep exactly today’s mechanism
• Network notes
  • Commitments stored separately, in a new Network Note DB.
  • Double-spend via a simple flag in this Network Note DB, no need for a separate nullifier tree.

So we’d end up with four top-level state commitments:

1. Account DB (unchanged)
2. Local Note DB (existing Note MMR; but now only for local note commitments)
3. Nullifier DB (existing data structure, but now only for local note nullifiers)
4. Network Note DB (new)

Network notes would not contribute to the Nullifier DB at all ✅
As discussed in some calls, it's hard to predict what mainnet usage of network vs. local notes would look like. But it is likely that network notes will be used heavily alongside local notes, and the nullifier state growth is the one we cannot reduce.

3.1 Network Note DB structure

• Data structure:
  A sparse Merkle tree (SMT)

• Key:
  network_note_id (can use the same ID as we use today)

• Value:
  Can be as small as an empty/created/spent enum (SMT starts off with all keys initialized to empty)

• State commitment:
  The root of this SMT becomes an additional state component, alongside the existing Account DB, Local Note DB (MMR), and Nullifier DB.

3.2 Network Note DB lifecycle

• Creation of a network note

  • "empty-membership" proof in the Network Note DB (show that value under network_note_id is empty).

  • State transition updates leaf to:

    network_note_id → { created }
    

• Consumption of a network note

  • "created-membership" proof in Network Note DB (network_note_id → { created })

  • State transition updates leaf to:

    network_note_id → { spent }
    

• Double-spend prevention

  • Any later attempt to consume the same network_note_id will see spent and fail.

No nullifier is generated for network notes; the consumption is tracked directly in this SMT.

---

4. Why not reuse the note-ID SMT for public local notes as well?

One tempting thought: “If this works for network notes, can we use the same trick for public local notes and avoid nullifiers there too?”

We could, but we'd lose the persistent witness guarantee for public local notes, making client-side more costly due to an extra trip to the RPC needed.

5. Shared bits

Even with this split, there is still room for shared structure, e.g. for NoteTag / NoteAttachment that can be used by both note families where it makes sense. As such, this proposal is somewhat complementary to #2109 as mentioned at the start.

6. Open questions

• @bobbinth has surfaced an idea of hybrid accounts which sometimes act as network and sometimes as local accounts. I think this proposal would still support both modes. Specifically, there would be nothing preventing local accounts from consuming network notes in principle, with the caveat that they might need to re-query the note inclusion proof.
• for most use cases, the client should never need to track network notes (as they're intended for network accounts). But there might be some edge cases where e.g. the note needs to be re-claimable, in which case the local account should consume the network note, running into a similar issue as outlined above. On the other hand, this sort of makes me think that maybe re-claimable network notes are a bit hacky, and what we should employ instead is conditional logic in network notes (e.g. try to execute a bridge-out action, and if failed, created a P2ID payback note to the user - with both execution paths encoded within the same note script, i.e. one of the paths must succeed)

[PhilippGackstatter]

I think this is an interesting and well-thought through proposal. Thank you for describing it so clearly!

The part I'm primarily thinking about is the premise that nullifier trees are growing constantly. If we can solve this differently, e.g. conceptually have a new nullifier tree every x months or something like that, would implementing this proposal still make sense? Or in other words, is there a second motivation?

So, at first glance, if we could solve the nullifier growth at a more fundamental level, so it does not only slow down but is somehow reset at regular intervals, this would benefit the Miden protocol at large.

[bobbinth]

So, at first glance, if we could solve the nullifier growth at a more fundamental level, so it does not only slow down but is somehow reset at regular intervals, this would benefit the Miden protocol at large.

We already have a conceptual solution for this described in 0xMiden/miden-vm#356 - we haven't implemented it yet because nullifier tree wouldn't be an issue for the first year. So, the plan is to implement this after mainnet.

Overall, I think the main question is whether we expect public notes to be a sizable or a small fraction of the overall note set. For example, if public notes will be 10% of notes, then treating them separately would not have a meaningful impact on the entire system. But if they are 80% of all notes, the impact would be quite significant.

[PhilippGackstatter]

We already have a conceptual solution for this described in 0xMiden/miden-vm#356 - we haven't implemented it yet because nullifier tree wouldn't be an issue for the first year.

In my understanding, that would reduce the set of nullifiers the node needs to keep track of back to 0 on a regular basis, which is good. I was thinking about the constantly growing set of nullifiers (i.e. primarily a leaf becoming full = 1024 entries or the chance of collision), but statistically that seems to not even remotely be an issue in any reasonable timeframe, with reasonable assumptions (1000 tps, 1 note per tx).

So, assuming the number of nullifiers the node needs to keep track of is not a problem due to nullifier tree rotation, and the total set of nullifiers is also not an issue, what would be the main benefit of reducing the growth rate for nullifiers?

[mmagician]

So, assuming the number of nullifiers the node needs to keep track of is not a problem due to nullifier tree rotation, and the total set of nullifiers is also not an issue, what would be the main benefit of reducing the growth rate for nullifiers?

There are two approaches to proving that a note has not been spent:

1. The user supplies the nullifier, and the block producer provides a non-membership proof
2. The user supplies both the nullifier and the non-membership proof

We currently use 1., i.e. store the full set of nullifiers with the block producer and the user does not need to worry about providing non-membership proofs. IIU the proposal C, with the epoch-based nullifier rotation proposal, we'd be moving towards approach 2 (actually, depending on the implementation details, possibly a hybrid 1 + 2 where the block producer maintains the nullifiers for the current epoch, but not previous epochs). This means the responsibility of providing non-membership proofs is now on the user:

• who stores the full nullifier trees for the previous epochs? We now need a new entity: an archive node.
• assuming the user can access archival data for previous epochs, they need to provide M-many non-membership proofs, one for each epoch since their note's inclusion. Here we run into a natural trade-off: the more often we rotate the trie, the less work the block producer needs to perform (and store less data), but the more non-membership proofs the user has to provide. There's probably good parameters for both parties (and likely these are parameters that can be updated with an easy protocol upgrade), but it's still worth highlighting this trade-off. Regardless: having less nullifiers overall leads to better UX (directly impacting proving speed) and/or BlockProducerX (directly impacting block times).

Two conclusions from this:

1. There are still many open questions on the epoch-based nullifier rotation proposal
2. Epoch-based nullifier database miden-vm#356 lessens, but does not eliminate the benefits to reducing the overall number of nullifiers in the system

[Mirko-von-Leipzig]

This seems reasonable though I question this assumption

Network notes – consumed by the operator.

My understanding was that network notes (and therefore network transactions) can be consumed (and produced) by anyone. Right now we have restricted it so that network transactions can only be produced internally within the node, but this is an artificial limitation which we were planning on removing.

Network notes & transactions look like they'll feature centrally in the bridging design as well, so iiuc it must be possible for anyone to create them.

[Mirko-von-Leipzig]

As operator, we also reserve the right to blacklist network accounts or even specific account/note scripts if they're deemed misbehaving. In such cases users will want to still self-run these.

We also want specialized network transaction operators which are builders specialized to certain network account types, which they can hyper optimise.

[mmagician]

Network notes & transactions look like they'll feature centrally in the bridging design as well, so iiuc it must be possible for anyone to create them.

Any script can create network notes - it would not change under this proposal. The proposal only optimizes for the consumption of network notes under the assumption you mention of "Network notes – consumed by the operator". But:

Specifically, there would be nothing preventing local accounts from consuming network notes in principle, with the caveat that they might need to re-query the note inclusion proof.

[Mirko-von-Leipzig]

Thanks, makes sense. I just want to ensure we're thinking of the network transaction builder as a separate entity to the operator as they probably will be.