Network transactions

[Mirko-von-Leipzig]

Network transactions are a major unsupported feature where users may submit a public transaction which the network should execute when some user-defined conditions are met. The transactions must be public since they'll be executed and proven by the node operator.

There are some open questions regarding this feature, which we should discuss and then iterate on a design.

I'll enumerate my initial questions here, but will initialize discussion threads for them below.

1. How do we minimize DoS vectors? What are possible concerns.
2. Possible conditions.
3. Fee structuring.
4. Implementation.

[Mirko-von-Leipzig]

Design attempt 1

1. Add a new RPC endpoint add_network_transaction.
2. Network transaction is submitted to mempool.
3. Mempool holds transaction until conditions are met.
4. Mempool spawns task to execute and prove transaction.
5. Mempool forgets the network transaction entirely.
6. Completed transaction is placed back in the mempool via the conventional Mempool::add_transaction method.

This elides error handling etc, but I think is fairly simple. What can occur is that the network transaction conflicts with another transaction submitted before the network transaction completes. This could be prevented around by marking the appropriate state inputs in some way, but that seems more complex for no good reason aka no reason to prefer the network transaction over the other.

This does raise the question of transaction selection/acceptance strategies, but in this case probably the operator could design a more general system where the mempool can evict transactions if an incoming conflicting transaction is deemed more valauable.

Transaction execution and proving can of course be delegated etc, and that design is orthogonal to this.

[bobbinth]

Accounts would be flagged on code creation/update. Though this might be awkward since we'll have to scan every output note for matching tags against some list of accounts? What would such a tag look like in practice?

As @igamigo mentioned above, identifying if a note is for a specific account should be relatively straight-forward:

1. We care only about public notes - so, private notes can be ignored.
2. The first two bits of the note tag are enough to tell if a note is intended for network consumption.
3. The next 30 bits of the tag identify the account the note is intended for. There is a small chance that there could be a collision here - i.e., two "network accounts" have the same 30 bit prefix in their IDs, but I think this should be relatively easy to handle.

Also, to simplify things, we can make the process only "forward-looking". That is, when a network account is created, we don't scan any of the existing notes but start tracking only the incoming notes.

If the public account list is expected to be short-ish then we can just store it permanently in memory, otherwise we'll need to reach out to the store each time we encounter such a note which may or may not be an issue.

Hard to say - may be thousand or millions of such accounts. I probably would add a field in the database to mark network accounts as such. This way, when the node starts up it can just get a list of network accounts from the store. Similarly, we could attach some extra data to notes intended for public consumption to make re-starting the server easier.

If anyone can deploy a shared/network account, doesn't this also become a DoS vector?

Good point. We could probably have some kind of LRU-cache-like system where only the accounts which have some activity are kept in memory. This could be a future improvement though.

Also, since network accounts are public by definition, cost of creating them would be higher than for private accounts. We could try to structure the fee system to make it prohibitively expensive to create a large number of public accounts in a short period of time. Though this needs to be much better thought through.

[Mirko-von-Leipzig]

Some follow-up question, how are these network notes validated? Is the following correct and enough:

1. Target account exists and is public/network account e.g. SELECT accounts.is_network FROM accounts WHERE accounts.id = <input>
2. Note can be applied to the account. This is less clear to me, and partially still undefined iiuc. I don't really understand notes well enough to know what's possible. The final result would be a new proven transaction, consuming the note.

Given that we're limiting the notes to known types, what are pre-execution validation that can be performed ahead of time? So far I've only listed that the account exists and is a network account. The note should also be of the limited subset that we've defined - does this somehow have to match up to the account's components and/or state?

Beyond these checks, is the final decision basically just: can this note be executed against the account's current state?

[PhilippGackstatter]

Further up in this thread we were discussing how to identify network accounts, so this feels like the best place to follow up on that.

The node somehow needs to identify network accounts so it can track notes that were sent to it and build network transactions from them.
We previously discussed adding a mark or tag to account IDs to identify those. My initial question was whether this would have to be part of the account ID, or couldn't be detected from the account's code:

If I see that some account has a procedure with MAST root 0x1234 in its account code which is a known procedure doing push.1 exec.account::incr_nonce (i.e. it increments the nonce without authentication) then wouldn't that be enough for an operator or user to determine that an account is such a "shared account"?
This would guarantee that an account can be updated. On the other hand, if we introduce the mark, then without additional checks it will be just a hint and not a guarantee that an account can be updated (for example, what if the account has the mark but does not export 0x1234?)

I still think this holds. If we have to look at the code anyway to make sure the account can be permissionlessly updated (i.e. without authentication), then how useful is the tag? We could add a rule like "network accounts always expose a permissionless increment nonce procedure", that we always add to the account's code, but I don't think such special rules are good ideas - they are inflexible and add complexity.

Right now, I think the protocol doesn't have the concept of network transactions, it only has generic transactions. If we start introducing network transactions into the protocol, then I think it'd be preferable if that integration resulted in some guarantees (like a network account being guaranteed to be updatable), rather than just hints.

One other such place where network transactions may need protocol support are fees (e.g. being able to recall notes sent to network accounts which never get included in a transaction, but the sender wants to have their fees back). See also: 0xMiden/protocol#1217 (comment). But here too, I'm not sure if special rules that sidestep the note's script are a good idea due to the complexity and surprising nature of it.

[bobbinth]

I think there are a few separate but related things. For example, we could still have both - ability to identify a network account solely by its ID and some coder requirements imposed on the network account.

Regarding code requirements, my initial thinking was that network transactions would not actually need any transaction scripts - i.e., the block producer would just execute notes against the network account. But this probably limits the flexibility of the design. Assuming the block producer does need to include a transaction script into the transaction, it is probably natural for this script to be responsible for authentication.

To make this script as simple as possible, we could require that it calls just a single procedure on the account. The simplest such procedure could be just incrementing the nonce. But we'd probably want to have more options in the future. For example, we may want to have a procedure which allows the block producer to increment the nonce in the last 5 minutes of every hour, but in the remaining time, incrementing the nonce may require a signature (or be a multi-sig).

We could probably treat such procedures similarly to have we treat well-known notes. That is, there would be a set of well known procedures that every network account must expose. We could start with a very small set (maybe 1 or 2 procedures) and then expand it over time. We still would need to answer some questions (e.g., how to make such scripts detectable but still pretty generic, what happens if an account exposes more than 1 such procedure) - but I think we can work through them.

So, to summarize - I think defining a set of well-known authentication procedures which must be exposed by network accounts may be a good thing.

Separately for this, I think it still may be desirable to include a bit (or maybe update account type definitions) to indicate that an account is intended to be a network account. The benefits of this include:

1. Very straight forward "first-pass" filtering for the node to filter out accounts which are definitely not intended to be network accounts.
2. Ability to specify accounts which may allow anyone to update them (i.e., have the well-known authentication procedure), but for some reason are not intended to be monitored by the network.
3. A simple way to check in the kernel if an account is intended to be a network account.

The last point may be import for the following:

• Ensuring that network notes are directed towards network account.
• Potentially charging higher fees for creating network account (e.g., it could be 10x the base fee of a regular public account).

On the negative side, I think there is some more complexity to be added to the account ID - i.e., adding meaning to one extra bit and ensuring that account storage mode is Public when this bit is set. Though, we could consider making this a variant of StorageMode. That is, we'd have Private, Public, and now Network accounts (and in the future Encrypted accounts as well).

[PhilippGackstatter]

For the AccountID I think the reasoning makes sense. I agree that having an unambiguous way to check if an account is a network account is useful in the kernel, for fee and validation reasons, to check if a note is targetted at such an account as well as in the node for filtering. I've opened an issue in miden-base for this: 0xMiden/protocol#1261.

Regarding the well-known procedures I'm not sure yet. It seems inflexible to define these as part of the protocol.

That is, there would be a set of well known procedures that every network account must expose.

If we require that the entire set must be exposed, how does the tx script determine which one it actually should call? I'm thinking users will want to define exactly what happens as part of the update, where their code can determine if an update should be accepted. And that would require calling a custom account procedure. I wonder if we could define the method to-be-called from the tx script to use dynamic dispatch, e.g. roughly:

export.update_network_account
    push.UPDATE_MAST_ROOT_STORAGE_SLOT_IDX exec.account::get_item
    # => [UPDATE_MAST_ROOT]
    dynexec
end

Then the MAST root of update_network_account is stable and a tx script (e.g. from the network tx builder) can hardcode it. Users are however free to update which procedure this effectively delgates to via dynamic dispatch and a MAST root stored in an account storage slot.

[Mirko-von-Leipzig]

I'll doodle my ideas for design here, pending some feedback in the above thread.

Network accounts

I'm currently only designing wrt querying whether a specific account exists and is a network account.

Add a flag column identifying an account as a network account. If we care about more than just the boolean true/false, then we could also consider an enum via bits.

I assume here that there is a pre-execution validation query. The alternative is that we have something like GetNetworkAccount which returns the state required by the note execution as well?

Performance of the above query can be improved in several cumulative ways.

1. Add a bloom filter to the store for this query. Filter would be kept in memory and either built from scratch on startup, or could be persisted with each block update. The latter shouldn't be difficult so we probably may as well avoid the startup costs. This essentially means false queries never hit the disk - true queries would always still need to confirm. But at least this is a nice DoS minimizer. The same bloom filter construction could also be used on the network note's handler side to prevent the RPC to the store for even less impact. Side note: this could also be used to reject add_transaction requests on non-existent accounts if we think that's an issue.
2. LRU cache for recently active accounts. Could also just be part of the regular accounts cache. This would probably include state so could just be the same cache overall.

Network notes

Simple flag, as above? So we can re-assemble the list of network notes for sending out for execution. Unclear who should be responsible for this - probably whoever is in charge of posting them in the first place.

Validation

Do we reject origin transactions which generate an invalid network note? We probably don't want to do this, since we cannot fully validate the note without executing iiuc? But we could reject them if the note's target account is invalid.

Execution

I would like to keep execution completely separate from the block-producer. The upside is that its decoupled and doesn't interfere with mempool logic etc. The downside is that doing some sort of advanced scheduling with the mempool becomes harder/impossible though we could still connect them somehow.

We could send the note off for execution at several points during the origin transaction's lifecycle:

1. accepted by the mempool
2. selected for a batch
3. part of a proven batch
4. selected for a block
5. proven block
6. committed block

This does imply the mempool is responsible for identifying these notes and sending them off for execution. I'm undecided if I like this. One alternative is to drop the responsibility back to add_transaction which should identify these outputs notes, and once the origin tx is accepted by the mempool, post the notes for execution.

Boils down to: do we want to cater for network notes acting on in flight data? This would include multiple sequential inflight network notes - is this a valid and desired use case? I can't really answer that.

Another alternative is to add a network note scanner to the block builder, which could emit them once the block is safely committed.

A further issue with out-of-band execution is that the target account's current state might be in the mempool still. So while the generated transaction would be valid, the state isn't trivially available to the out-of-band executer without mempool IO.

The simplest solution here is to avoid all this, and say that network transactions are executed wrt chain tip and not inflight state. This let's us simply post the note for execution without any validation - the executor does everything based on the store data via the conventional RPC entry-point. This would imply the note sending should occur at block committal by the block-builder, or having the executors scan for such notes themselves via the store.

[bobbinth]

Some more thoughts:

We probably will need to execute notes against their target accounts incrementally (e.g., first execution note1, account goes from state A to B, then execute note2, account gos from B to C) without persisting the results. We currently don't have this capability - but it shouldn't be too complex to add (we'll need to build an implementation of the DataStore interface that can handle this).

There is a concern about the cost of executing notes (as it could get pretty expensive). But there are a couple of mitigating circumstances:

• Network transactions don't require signature verifications and so should take up very few cycles. In most cases this could be under 8K cycles. We could even put a limit on the cycle count at 32K or something like that and this should cover 95% of use cases (I think).
• We just need to execute the code and not prove it. If we can get Miden VM execution speed to 100MHz (see 0xPolygonMiden/miden-vm#1558, we'd be able to execute between 1K and 10K notes per second on a single core. cc @plafer.

[Mirko-von-Leipzig]

The ordering is fully up to the network tx builder. It is probably a good strategy to try to keep it close to the ordering of the origin transactions - but that's not required.

This is only really possible if we only process network notes from committed blocks. Otherwise the tx builder has no real way of knowing when a tx will be committed, nor in what order. We can provide hints as the origin tx status changes but that is a lot of complexity on both ends for a small latency gain and potential for large rollbacks.

We just need to execute the code and not prove it.

Why do we not need to prove it? The end result is still a transaction with a proof submitted to the block-producer or no?

How would the tx builder track the account's state? Are network accounts only allowed to change via network notes? If not, then normal txs could disrupt things quite dramatically if they're in flight.

[bobbinth]

This is only really possible if we only process network notes from committed blocks. Otherwise the tx builder has no real way of knowing when a tx will be committed, nor in what order. We can provide hints as the origin tx status changes but that is a lot of complexity on both ends for a small latency gain and potential for large rollbacks.

I was thinking that the network tx builder (NTB) would build a transaction that consumes notes a, b, c and submit this transaction to the mempool. From this point on, it would just follow the usual mempool flow - i.e., it would be a part of the mempool dependency graph and so will progress behind transactions generating notes a, b, and c. If any of these transactions gets reverted, the network transaction will get reverted as well and NTB will be notified of this.

But I do agree that working only with committed notes simplifies things significantly, and we should probably start with this simplifying assumption and try to relax it after the basic flow has all been worked out.

Why do we not need to prove it? The end result is still a transaction with a proof submitted to the block-producer or no?

Yes, we will need to prove the final result - but for checking purposes we need only to execute (e.g., can note b be executed after note a).

How would the tx builder track the account's state? Are network accounts only allowed to change via network notes? If not, then normal txs could disrupt things quite dramatically if they're in flight.

Good question! I haven't thought too much about it - but we can make this simplifying assumption initially. That is, once created, network accounts are fully managed by the network and can be updated only via transactions issued by the NTB. We can relax this in the future - but this would require some conflict resolution strategies which require more thinking.

[Mirko-von-Leipzig]

I was thinking that the network tx builder (NTB) would build a transaction that consumes notes a, b, c and submit this transaction to the mempool. From this point on, it would just follow the usual mempool flow - i.e., it would be a part of the mempool dependency graph and so will progress behind transactions generating notes a, b, and c. If any of these transactions gets reverted, the network transaction will get reverted as well and NTB will be notified of this.

This would work but does mean that a b c are now all bound via the mempool graph so one gives up a bit of control. It might surprise the owner of a that his network transaction is now delayed due to other factors.

Yes, we will need to prove the final result - but for checking purposes we need only to execute (e.g., can note b be executed after note a).

Ah okay I see, essentially a vm or prover missing piece to build a transaction as a sequence of notes? I would think this is already supported since a transaction can have multiple input notes - but I guess maybe they cannot be built incrementally to avoid a failing note?

Thanks I think I have enough to go on :) I think large chunks of this are possible to build already.

[bobbinth]

Ah okay I see, essentially a vm or prover missing piece to build a transaction as a sequence of notes? I would think this is already supported since a transaction can have multiple input notes - but I guess maybe they cannot be built incrementally to avoid a failing note?

This is currently possible but only "atomically". That is, I can try to execute a transaction that consumes notes a, b, and c - but if the script of b fails, for some reason, the entire transaction is aborted. Ideally, we'd be able to execute these incrementally and only once we know that a, b, and c can be executed in this sequence, we create and prove a single transaction that consumes them. There could be other ways of handling this though.

[Mirko-von-Leipzig]

Tracking issue #692. We can re-open if there are any major requirement changes.