Chain-wide public code registry

[bobbinth]

Currently, we have two issues with how public account/note script code is included in the chain, and it would be good to fix both before mainnet as fixing these after would be quite complicated (if not impossible):

1. With both account code and note script, we commit only to procedure roots. While these are enough to commit to the semantics of the underlying program, they are insufficient to describe the shape of the code. For example, a procedure root could point to a single External node, or it could have the full MAST under it.
2. Code duplication - every account and note script is expected to carry full code, even if the same code already exists on chain. We kind of solved this for note scripts by requiring only the first note to carry the full script, but for accounts we don't have a solution yet (and even for notes, the solution could be improved).

Code commitments

A potential way to address the first issue is to change our code commitment methodology. A key observation here is that MAST of a procedure is fully specified by the procedure root + a set of external nodes in the underlying MAST (cc @huitseeker and @Al-Kindi-0 to double-check me on this). This means, that we can define note script and account code commitments as follows:

pub struct NoteScriptCommitment {
    root: NoteScriptRoot,

    /// This would be a sorted list of external nodes on which the note script depends -
    /// e.g., roots of the core or standard library procedure.
    deps: Vec<ProcedureRoot>,

    /// Could be computed as hash(root, hash(deps)) - or maybe just hash(root, dpes)
    commitment: Word,
}

pub struct AccountCodeCommitment {
    procedures: Vec<AccountProcedureRoot>,

    /// This would be a sorted list of all external nodes on which the account procedures depend -
    /// e.g., roots of the core or standard library procedure.
    deps: Vec<ProcedureRoot>,

    /// Could be computed as hash(hash(procedures), hash(deps)) -
    /// or maybe just hash(procedures, dpes)
    commitment: Word,
}

Implementing the above shouldn't be too difficult - we would need to update the transaction kernel and all relevant off-chain code, but it shouldn't cause any fundamental issues.

This solves the first problem, but it doesn't solve the second (code duplication), but before I get to a potential way to solve it, let's first look into some other checks that we need to do with the public code.

Code completeness

One of such checks that the node performs is figuring out if the submitted public code can be executed. We can't guarantee this in principle, but we try to make as many checks as possible. For example, we verify that MAST is well-formed. We can also perform one extra check (which I'm not sure if we do now): we could check that we know of all external nodes referenced by a note script or account code. Currently, these would be check against procedures in core and standard library, and for note scripts, also roots of the previously committed note scripts.

But such checks on the node could be potentially expensive - so, it would be great if the user could prove that all external nodes are known to the node. One way to do this is to include a commitment to all known code in the block header. Then, during a transaction, the user would need to make sure all external procedures of their code are covered by this commitment. The commitment could be a simple map:

PROCEDURE_ROOT |-> 0/1

Where value 1 would indicate the a procedure with this root is known to the network.

As mentioned above, we'd include this map into the block header - in a way, it could be parallel to account and nullifier trees (we could call it something like code_tree_root).

This tree would be initialized with roots for procedures from the core and standards libraries, and any time a new note script appears on-chain, it would be added to the tree.

Notice that this eliminates the problem of needing to merge note scripts, because for a script to appear on-chain, it needs to prove that all of its dependencies are already on-chain - i.e., there is no way to "hide" a part of the public script from the network (which maybe something we can relax in the future, if needed).

Any time we do a network upgrade, we'd need to populate the tree with the roots of new core and standards library procedures - which I don't think is a problem (and maybe even a good thing). We can also introduce other values beyond 0 and 1 to mark some previously introduced procedures as deprecated or forbidden (e.g., due to known bugs).

De-duplicating account code

We could apply the above approach to account code as well. Specifically, whenever a new public account gets created, we'd do the following:

1. Make sure that all external references are already in the network code tree - this would be done in the transaction kernel.
2. Add all procedures from the new account to the network code tree - this would be done in the block kernel (when the transaction creating the account is included in the chain).

Then, all subsequent accounts that export the same procedures could replace already "registered" procedures with External nodes (similar to how we do this with note scripts).

The net effect is that the "network code tree" would be a commitment to all code known to the network, and if a procedure is present in this tree, creating a note or an account with such procedures would be very cheap (from code standpoint).

Network code patches

We could take the above a step further and make addition of new code to the "network code tree" explicit. Specifically, we could add a new element to the transaction outputs: new_code_commitment. This commitment could be a simple sequential hash of procedure roots for procedures that need to be added to the network code tree. These procedures would be identified as follows:

• Any account procedures for newly created public accounts that are not already in the network code tree.
• Any note script for public notes that is not already in the network code tree.

This would also imply that the actual MAST code included with transaction would not be in the AccountCode or NoteScript struct, but rather in a transaction-level object - e.g., PublicCodePatch. This could look something like:

pub struct PublicCodePatch {
    /// A list of new procedures to be added to the network code tree as a result of a transaction
    procedures: Vec<ProcedureRoots>,

    /// Code for all procedures in the `procedures` field
    mast: MastForest,
}

---

To summarize:

• The above approach should solve all our problems with code commitments, and make the network more efficient - but it is also a pretty fundamental change that we need to do before mainnet. Specifically:
• We'll need to introduce a new "top-level" database - "network code registry" (other name suggestions are welcome), and update transaction/batch/block kernels to work with this.
• A bunch of Rust code would also need to be updated, and there are certainly some open questions that I'm not thinking of now (e.g., how does this affect the client or the private notes/accounts).

So, any feedback is welcome.

[Mirko-von-Leipzig]

This sounds great; and would help a bunch in the node.

Question: does a tx fail if its trying to insert new code that already exists? Or does this become a no-op?

[bobbinth]

Question: does a tx fail if its trying to insert new code that already exists? Or does this become a no-op?

I was thinking it would be a no-op.

[PhilippGackstatter]

Code commitments & completeness

To take a concrete example, a P2ID note code commitment would be specified by:

• its script root: miden::standards::notes::p2id::main
• external references: miden::standards::wallets::basic::receive_asset, miden::protocol::active_note::get_assets, ...

In a fresh network, when the first P2ID note is created, the transaction kernel:

• proves that all external references are in the code tree.
• computes the size of the newly added public data for the purpose of fee calculation. This is the size of the MAST of the script root (see code size below), plus 32 bytes for each external reference.
• appends the script root to the tx-level NEW_CODE_COMMITMENT (depending on if we go with the tx-level construct).

One attack scenario is:

• An attacker replaces a part of the p2id::main MAST with an external node, i.e. hides a part of the tree. This results in an additional external node, so the note code commitment is different than that of a "regular" P2ID note, but importantly, the p2id::main MAST root remains unchanged.
• The node receives the transaction and since it's the first time it sees the p2id::main MAST root, it inserts P2ID_SCRIPT_ROOT |-> 1 into the code tree, but would actually only have a part of the underlying MAST.
• Second non-malicious user creates a "regular" P2ID note with the expected note code commitment of that note, but since p2id::main is already tracked in the code tree, the complete version of that MAST root isn't propagated to the note.

The situation is now: The P2ID_SCRIPT_ROOT appears as tracked by the node, but the node only has part of the underlying MAST. I believe this would work because we don't actually have a guarantee of completeness at the procedure level, i.e. p2id::main has the same MAST root whether it's an external node or the "full" MAST. If that second user now retrieves the note from the node, they will get incomplete code.

I think potential work arounds are:

• we'd have to track note code commitments in the code tree rather than procedure roots in order to avoid this scenario, because only it guarantees completeness, but MAST roots do not. For notes, this seems fine, but for accounts it would mean we only have code deduplication when one creates an account with code that already exists in exactly that form on-chain, so it is less general.
• the node may still have to merge code to produce the most complete version of a given procedure root, but this defeats a large part of the proposal since transactions would still have to include all code so the node can do the merge.

But I think we're trying to work around the fundamental problem/feature of MAST that an external node referencing X has the same commitment as X itself, and it seems like we may have to go deeper to solve this.

Code size

I think computing the code size is related to the way we commit to code. The commitment methodology should allow the kernel to compute the size without the user being able to cheat by replacing a part of a MAST with an external node. I think the proposed methodology should set us up for computing the size of the underlying MAST, but afaict it does require us to implement MAST hashing, i.e. what MastNodeExt::digest does, hashing basic block nodes, call nodes, loop nodes, etc. The code of a note or account would be provided as advice input and the tx kernel would use this input to compute 1) the set of account procedures or the note script root, 2) the total byte size of these and 3) the set of external nodes. This should make it impossible to cheat the code size in any way. The important part is that the size and the set of external nodes is computed from the same input, otherwise this opens the door for mast node replacement.

I think we wouldn't need this in a centralized setting. For now, the kernel could assume that the data is valid, take a size hint, ... The "Rust protocol code" would implement a check that the script size hint provided to the tx kernel matches the size of the NoteScript provided with the transaction. In a decentralized setting though, it'd be valuable for a tx to prove that the computed fee and the code commitment were correct.

Fees

I think the impact on fees is that we'd need to reflect the cost of adding the public code to the network plus the hash computations required for insertion into the code tree. Could be via a new base fee or by destructuring the costs into "data" + "computation".

PublicCodePatch

This would also imply that the actual MAST code included with transaction would not be in the AccountCode or NoteScript struct, but rather in a transaction-level object - e.g., PublicCodePatch. This could look something like:

If the code is no longer in AccountCode or NoteScript, it seems this would make an Account or Note object incomplete, which seems undesirable. Or at least, we'd need some convenient way to recover the complete objects from a ProvenTransaction.

I think the alternative is to leave the actual code in AccountCode and NoteScript and have PublicCodePatch only contain the sequential hash of the newly added procedures. To get the underlying procedures, there could be a method like ProvenTransaction::added_procedures_iter or similar.

Summary

To summarize:

• I think procedure MAST roots are still susceptible to replacement :(
• I think we should set this commitment computation up so we can compute the size and commitment easily in the future without breaking anything, but that seems possible. For now, we shouldn't need this and can use a Rust-level check instead.
• I'm not sure about the impact of PublicCodePatch on NoteScript and AccountCode and would have a preference towards leaving the concrete code where it is now.

[PhilippGackstatter]

I think if we change the code tree to track NoteScriptCommitment and AccountProcedureCommitment, it should work. The latter would be defined as:

pub struct AccountProcedureCommitment {
    procedure: AccountProcedureRoot,

    /// This would be a sorted list of all external nodes on which the account procedures depend -
    /// e.g., roots of the core or standard library procedure.
    deps: Vec<ProcedureRoot>,

    /// Could be computed as hash(procedure, hash(deps)) - or maybe just hash(procedure, deps)
    commitment: Word,
}

Basically, this is the same as the proposed AccountCodeCommitment but at the individual procedure level rather than at account level. This gets us a commitment to an account procedure that cannot hide necessary parts of the code. When creating an account, a user provides a list of AccountProcedureCommitments to the tx kernel, from which to create the account code. The tx kernel:

• validates the preimage of each procedure commitment.
• adds the AccountProcedureRoot to the public interface.
• (optional) validates the dependencies of each procedure are in the code tree.
• computes the code commitment as hash(procedure_commitments).

As an example, say we create an account with a BasicWallet:

• BasicWallet consists of receive_asset and move_asset_to_note.
• Taking the former as an example, receive_asset depends on the external node behind native_account::add_asset.
• So, its procedure commitment would be RECEIVE_ASSET_COMMITMENT = hash(RECEIVE_ASSET_PROC_ROOT, NATIVE_ACCOUNT_ADD_ASSET_PROC_ROOT).
• The overall code commitment would then be hash(RECEIVE_ASSET_COMMITMENT, MOVE_ASSET_TO_NOTE_COMMITMENT).

Tracing through account creations:

First creation

When the first BasicWallet account is created, a RECEIVE_ASSET_COMMITMENT |-> 1 entry is added to the code tree.
(We can consider mapping it to RECEIVE_ASSET_PROC_ROOT instead, if this helps with anything, but I don't see any potential).

Importantly, if the creator of the first transaction is malicious and attempts to hide a part of the RECEIVE_ASSET_PROC_ROOT, the set of external nodes would be different and so the RECEIVE_ASSET_COMMITMENT would be different. This would not prevent an honest user from registering the "real" receive_asset procedure. So, we can only let users insert procedure commitments (incl. their external nodes), but not procedure roots.

Second creation

When the second BasicWallet account is created, the inclusion of RECEIVE_ASSET_COMMITMENT in the code tree is proven and so the user replaces the full code with an external reference to RECEIVE_ASSET_PROC_ROOT in its actual code.

Dependency checks

When we track RECEIVE_ASSET_COMMITMENT instead of RECEIVE_ASSET_PROC_ROOT in the code tree, checking for a P2ID note's dependency on RECEIVE_ASSET_PROC_ROOT becomes trickier. We can no longer just check that RECEIVE_ASSET_PROC_ROOT is in the code tree. Instead, we need to check for RECEIVE_ASSET_COMMITMENT. In practice, the P2ID note creator would need to have the code of BasicWallet to determine that NATIVE_ACCOUNT_ADD_ASSET_PROC_ROOT is a dependency of it, in order to compute RECEIVE_ASSET_COMMITMENT.

If RECEIVE_ASSET_COMMITMENT is not yet in the code tree, the creation would not be allowed. The user would have to inline the code instead to avoid the external node (but then make sure that code's dependencies are available).

The difference to the original proposal is that we'd need to go one level deeper (to get the dependencies of external nodes).

I think it's technically feasible, just not in a short amount of time.

Where commitments are computed

Caveat: Afaict, for now, the computation of RECEIVE_ASSET_COMMITMENT would have to be done off-chain because to verifiably get the set of external nodes from RECEIVE_ASSET_PROC_ROOT in the tx kernel, requires traversing MAST in MASM (see also code size topic above). Specifically, tracking external nodes of a procedure and hashing MAST to a procedure root.

I assume this is not fundamentally impossible, but not something we can do in a short amount of time, afaict cc @huitseeker. Once we have this, we could compute and check this in the tx kernel, which I think should be the long-term goal.

Variant: Commitments to AccountComponents

Just mentioning this: There is a variant of the above where we commit to account components, e.g. receive_asset and move_asset_to_note in one commitment. I don't see any particular advantage to this though, other than tracking fewer entries in the code tree. It would have slightly worse deduplication properties: If someone creates a BasicWallet2 with receive_asset + move_asset_to_note_v2, then this would be a completely new entry. In the AccountProcedureCommitment approach, receive_asset would be deduplicated and only move_asset_to_note_v2 would be a new entry.

So, essentially, we should be able to commit either to procedures, components or entire accounts. Procedures have the finest granularity and the best deduplication properties, while incurring the most entries in the code tree.

Private Accounts

Would private accounts use this registry? The dependency checks only make sense for public accounts and deduplicating code for private accounts is probably not a goal either. So, I'm assuming private accounts would be entirely unaffected by the proposed changes.

Summary

I think if we track AccountProcedureCommitment and NoteScriptCommitment in the code tree, we should be able to safely achieve deduplication.
Dependency checking becomes a bit harder. So, whether it is worth the complexity remains to be seen. Though we can implement this post-mainnet in any case.

[bobbinth]

One attack scenario is:

• An attacker replaces a part of the p2id::main MAST with an external node, i.e. hides a part of the tree. This results in an additional external node, so the note code commitment is different than that of a "regular" P2ID note, but importantly, the p2id::main MAST root remains unchanged.
• The node receives the transaction and since it's the first time it sees the p2id::main MAST root, it inserts P2ID_SCRIPT_ROOT |-> 1 into the code tree, but would actually only have a part of the underlying MAST.
• Second non-malicious user creates a "regular" P2ID note with the expected note code commitment of that note, but since p2id::main is already tracked in the code tree, the complete version of that MAST root isn't propagated to the note.

The situation is now: The P2ID_SCRIPT_ROOT appears as tracked by the node, but the node only has part of the underlying MAST. I believe this would work because we don't actually have a guarantee of completeness at the procedure level, i.e. p2id::main has the same MAST root whether it's an external node or the "full" MAST. If that second user now retrieves the note from the node, they will get incomplete code.

I don't think this would be a problem for two reasons:

1. If the external node that replaced some subtree in p2id::main is not already in the code tree, the node would reject the transaction.
2. If the node already has p2id::main in the code tree, it would just silently ignore the new MAST - i.e., we already know of this procedure, so, the code tree doesn't need to change.

I think computing the code size is related to the way we commit to code. The commitment methodology should allow the kernel to compute the size without the user being able to cheat by replacing a part of a MAST with an external node. I think the proposed methodology should set us up for computing the size of the underlying MAST, but afaict it does require us to implement MAST hashing, i.e. what MastNodeExt::digest does, hashing basic block nodes, call nodes, loop nodes, etc. The code of a note or account would be provided as advice input and the tx kernel would use this input to compute 1) the set of account procedures or the note script root, 2) the total byte size of these and 3) the set of external nodes. This should make it impossible to cheat the code size in any way. The important part is that the size and the set of external nodes is computed from the same input, otherwise this opens the door for mast node replacement.

As mentioned above, the user is not able to cheat "by construction" - any procedure that has external nodes (e.g., dependencies) that are not already in the code tree would be reject (i.e., the transaction would not be accepted by the node).

I also don't think there is a need to compute the size of the code in the kernel. The size could be provided non-deterministically to compute the fees, and nothing else really needs to happen. If the fees were computed incorrectly (the user tried to underspecify the size of the code), the transaction would be rejected by the network (because the fees would not be sufficient).

If the code is no longer in AccountCode or NoteScript, it seems this would make an Account or Note object incomplete, which seems undesirable. Or at least, we'd need some convenient way to recover the complete objects from a ProvenTransaction.

These are already "incomplete" because they rely on the core and standards libraries - though, of course, these are well-known libraries that everyone is expected to have. Overall, having such incomplete code in ProvenTransaction shouldn't really be an issue - the network will be able to reconstruct the full code from the data it has in the code tree.

But there is a related problem (and I think the main open question for this proposal): when a client requests to get account code or note script from the node, what does the node return? We could return just the list of interface procedure roots, but that would mean that the client needs to make additional requests to retrieve all dependencies - which would be expensive.

We could return the complete MAST (i.e., not external nodes) - but that may be too much code (in terms of bandwidth) and probably expensive to do on the node.

We could be a bit more intelligent and not return subtrees for procedures from core/standards libraries - but that also may be expensive for the node (i.e., it's not a simple read from disk and serialize - but rather requires a traversal of the entire MAST forest of the public code)

[PhilippGackstatter]

If the external node that replaced some subtree in p2id::main is not already in the code tree, the node would reject the transaction.

Ah, that's right. I somehow didn't combine the code tracking with the dependency check in my mind. So when a user attempts to create a P2ID note with a subtree replaced by an external node, this is actually a feature, not a bug. It's the same replacement as if this was a part of the core or standards library. If the external node exists in the code tree, the network doesn't need to see that subtree, so a user would want to remove it from the tree in order to save on the code size they need to pay for. Since the tx kernel checks that all external nodes are already in the code tree, this prevents a user from publishing only a partial procedure MAST.

That prevents the attack I described, thanks for clarifying!

There is also the opposite scenario, where a user publishes more data than would be necessary. This goes against natural incentives (user needlessly pays more), so maybe we can ignore this scenario. It could still happen due to race conditions or a suboptimal client implementation. So, the node may want to check that the received MAST is already as deduplicated as it can be. This may happen naturally if the received MAST is merged into a single, large MastForest.

I also don't think there is a need to compute the size of the code in the kernel. The size could be provided non-deterministically to compute the fees, and nothing else really needs to happen. If the fees were computed incorrectly (the user tried to underspecify the size of the code), the transaction would be rejected by the network (because the fees would not be sufficient).

In a centralized setting I agree this check can be done at the node API level (in "Rust", not ZK-proven). But in my mind, all such checks are temporary and to-be-replaced with in-kernel checks since we want the full protocol to be provable.

So, in general (e.g. when decentralizing), to check at the batch/block level that a tx paid enough fees for each of the procedures it added to the code tree, we need an in-kernel computation of the fees, so that a batch or block becomes trustless. Afaict, the alternative is to let the block builder rely on unverifiable advice input to get the code size.

Presumably, we can also keep this check at "Rust" level (unproven) and resolve such conflicts through consensus, but I'm not sure what the full implications would be.

We could be a bit more intelligent and not return subtrees for procedures from core/standards libraries - but that also may be expensive for the node

I think we assume that all nodes and clients have all versions of the core and standards libraries, so this seems like the best approach conceptually. Maybe user code can be kept separately from core and standards libraries, so that they are separate by construction and the node only returns code from the "user code" MastForest.