Decide on `NOTE_MAX_SIZE` and deduplicate note scripts

[PhilippGackstatter]

One thing we could consider is to allow relatively large note script sizes but scale the fee for these superlinearly. The main reason for this is that we really need only one public note with a given script to put the full script on-chain. All subsequent notes could contain just an External MAST node referring to this script. This will be possible because the node could keep track of only the most "complete" version of the script. We will need to update some logic on the node for this - and also to provide an easy way to figure out if one MAST forest is a strict subset of another.

Originally posted by @bobbinth

I guess the main benefit is to:

• only store full note scripts once
• reduce the size of transactions, batches or blocks when the full note script isn't needed.

The second point requires replacing a full note script with an External node if we know it already exists or isn't needed by whoever requested it, but the first point alone could also be done purely at the node DB level without changing anything about the rest of the system, afaict.

I imagine the client would always need to download a note with a full script from the node, for transaction execution, so the node may have to provide an API that allows for that.

Context: #2651 (comment)

cc @Mirko-von-Leipzig for node visibility

[bobbinth]

I think the only change we need to make to support this at the protocol level would be to add a method to the OutputNote struct to replace the MAST in the note script with a single external node pointing to the same MAST.

The node API already allows retrieving note scripts by root - so, I think we should be good on that front here (by @Mirko-von-Leipzig please confirm).

One thing we would need to make sure we do handle on the node side is to have a more robust way of updating the note_scripts table - to make sure we don't replace the more complete version of the script with a less complete one. I believe we already have an issue for this in the node.

[Mirko-von-Leipzig]

0xMiden/node#1188 tracks this on the node side.

The node API already allows retrieving note scripts by root - so, I think we should be good on that front here (by @Mirko-von-Leipzig please confirm).

Yes, we have the very literal GetNoteScriptByRoot gRPC endpoint.

---

What's unclear to me is how we can determine whether an incomplete note script should be merged with another incomplete one, to hopefully form a more complete one.

iiuc the note script is a tree of MAST roots, where any branch can be omitted if its not required for a particular transaction's execution. So for each script we can track which roots are omitted and then merge them in if we see them?

Or is this more a recursive exercise where we split each script into tiny pieces?

[bobbinth]

What's unclear to me is how we can determine whether an incomplete note script should be merged with another incomplete one, to hopefully form a more complete one.

iiuc the note script is a tree of MAST roots, where any branch can be omitted if its not required for a particular transaction's execution. So for each script we can track which roots are omitted and then merge them in if we see them?

Or is this more a recursive exercise where we split each script into tiny pieces?

I think we may be able to simplify things, at least initially. For example - we can reject partially overlapping MAST forests. The rule can be something like:

• If we've never seen a script with such MAST root before, we insert it into the database.
• If a script with the same root is already in the DB, we replace it only if it is a strict subset of the script set for the note.

Obviously, the second part is the most complicated one, and it itself splits into 2 cases:

• Are the two scripts equal?
• If they are not equal, is the stored script a subset of the incoming script.

To check if the two scripts are equal we need to check two things:

• Are the roots of the scripts the same.
• Do both scripts have an identical set of External nodes.

To check the second condition more efficiently, we may want to store a set of external nodes (or their hash) for each note script in the database. Then, the equality check could even be done in the DB.

Once we've identified that the scripts have the same root, but have a different set of External nodes, we'll need to do a deeper analysis to figure out if one is a subset of the other. This will probably require deserializing the script from the database and executing some analysis code. The code itself shouldn't be too complicated - but I also haven't thought it through it yet (cc @huitseeker).

[Mirko-von-Leipzig]

To check the second condition more efficiently, we may want to store a set of external nodes (or their hash) for each note script in the database. Then, the quality check could even be done in the DB.

Once we've identified that the scripts have the same root, but have a different set of External nodes, we'll need to do a deeper analysis to figure out if one is a subset of the other. This will probably require deserializing the script from the database and executing some analysis code. The code itself shouldn't be too complicated - but I also haven't thought it through it yet (cc @huitseeker).

Yes that's what I was driving at; some cheap way we can analyze without reading the full script each time. One alternative is to keep a large LRU of recent scripts, which means we can check these easily since they're already loaded. One probably wants to do that separately for caching reasons in any case. Ideally I would prefer to have caching just for caching and have a separate, more intelligent database merging strategy.