Potential execution model

[bobbinth]

This note is a followup on #192 and #222. One of the things that I didn't cover in these notes is the description of who are the network participants, what are their roles, and how their actions result in transaction execution.

In this note I will describe a simplified centralized model, primarily because I want to avoid talking about things like consensus, P2P network etc. As with previous notes, this is just a high-level description and a lot of details and specifics are missing, frequently because they are yet to be thought out.

In the centralized model, we have the following entities:

• L1 contract - this is a smart contract on Ethereum which keeps track of the current state of the L2 network.
• Block producer - this is an entity which produces blocks and submits them to the L1 contract. In a centralized model there is only one block produce, but in a decentralized model there would be many block producers.
• Clients - these are users who initiate transactions and submit them to the block producers. In a decentralized model, clients would submit transactions to the network and these transactions would be gossiped to other nodes.

In the decentralized model we'd also have full nodes, validators etc. - but as mentioned above, I'm skipping them for now. Also, in this note, I will focus on clients and block producers, and will leave details on L1 contract to future notes.

Transaction aggregation

As mentioned above, a block producer collects transactions from the clients and aggregates them into a block. Since we are building a ZK rollup, this block needs to be accompanies by a ZK proof attesting that all transactions in the block have been executed correctly. Graphically, this could look something like this:

Where $a_0$, $n_0$, and $x_0$ are the commitments to the account, note, and nullifier databases before the transactions in the block have been executed, and $a_i$, $n_i$, and $x_i$ are the commitments to the same databases after the transactions have been executed.

One way to generate this ZK proof is to execute transactions one by one on the VM and output a single proof of their execution. This would look something like this:

This approach works and it is a very efficient way to generate a ZK proof. But it has a few drawbacks:

1. Resource accounting becomes difficult - i.e., figuring out how much a given transaction should pay in relation to other transactions is highly non-trivial.
2. Supporting privacy is problematic - this is because the block producer must know both the data and the code that were involved in a transaction (otherwise, they won't be able to execute the tx).

Another approach could look something like this:

In this approach, we assume that execution of each transaction has already been proven (which works well in our transition model). So, the program which gets executed on the VM to generate a block level proof would need to do the following:

1. Verify that transaction inputs are valid - i.e., notes consumed by the transaction haven't been consumed previously, the account state is current etc.
2. Verify the transaction-level proof.
3. Apply transaction outputs to the current state - i.e., update account DB with the new account state, insert new nullifiers into the nullifier DB etc.
4. Repeat the above steps for the next transaction.

We will call the program which performs the above steps os kernel.

In this model, resource accounting is greatly simplified for two reasons:

• First, each transaction is self-contained and doesn't affect costs for other transactions. These costs are also much easier to estimate (i.e., I think we can get away without a complicated gas model).
• Second, complexity of ZK proof verification is logarithmic in the size of the computation. So, even for transactions which are vastly different in their execution complexity, costs of proof verification would be very similar.

We can take this approach further: instead of aggregating individual transaction proofs, we can aggregate batches of already aggregated transactions like so:

Assuming batches are non-overlapping, the above would work just as well as the case with individual transaction proofs. Though, obviously, os kernel would need to be slightly different.

It would be very interesting to see if we can make this work for overlapping batches - i.e., the same transaction is included in multiple batches.

Transaction execution

In the section above we assumed that each transaction already comes with a ZK proof attesting to its correct execution. But how do these ZK proofs get generated, and who generates them?

As mentioned in the previous notes, there are two types of transactions: (1) local transactions and (2) network transactions.

For local transactions, clients initiating the transactions also generate the proofs of their execution. So, no additional work needs to be performed by the network. Local transactions may be useful for two reasons:

1. They would enable privacy as neither the account state nor account code are needed to verify the ZKP.
2. They should be cheaper (i.e., lower fees) as ZKPs are already generated by the clients.

For network transactions, the block producer would generate the proofs. Network transactions may be useful for two reasons:

1. Clients may not have sufficient resources to generate ZK proofs (this may be especially relevant for mobile devices - at least for the near future).
2. Executing many transactions against the same public account by different clients would be challenging as the account state would change after every transaction. In this case, block producer can act as a "synchronizer" as they can execute transactions sequentially and feed the output of the previous transaction into the subsequent one.

In both cases, the entity generating a transaction proof would need to execute the same program on the VM (i.e., the program which executes a prologue, note scripts, epilogue etc. - as described in tx model note). We will call this program a tx kernel.

Block producer could also "outsource" tx proof generation to others as all proofs could be generated independently in parallel. Though, in cases when many transactions are executed against the same account, the block producer would also need to provided additional info (i.e., before/after account states) to such helpers (or another option could be to give all transactions which touch a particular account to the same helper).

Block producers will probably need to be compensated for the proof generation for network transactions. Thus, clients submitting network transactions would need to include a higher fee. The amount of the extra fee may be determined by the market, but more thinking is needed on how it can be made easy to estimate.

Transaction batching

Verifying a STARK proof within the VM should be relatively efficient (though, this has not been implemented it) - but it is still a pretty costly operation. I don't know what the actual numbers will come out to be, but I don't think it will be desirable to verify more than 100 proofs inside a single larger proof (at least for the near future).

However, if we are able to batch transactions, each batch could contain 100 transactions (or w/e the number that makes sense), and the block-level proof would contain 100 batch proofs. This way, each block could fit 10K transactions, which will be processed in batches of 100 in parallel.

To generate transaction batches we will also need to have a separate program. We will call this program ag kernel.

We can also take the batching approach a step further and add more recursion layers (i.e., batches of batches) - but this will complicate both the ag kernel and the os kernel quite a bit. So, my thinking is that at least initially, we don't try to do that.

Another interesting benefit of batching is that we may be able to use it to support proof generation on resource-constraint devices. One of the reasons why proof generation for transactions will be expensive is that to do recursive proof aggregation we need to build lower-level proofs using arithmetization-friendly hash functions (i.e., Rescue Prime in our case). These hash functions are not very efficient (i.e., probably 30x less efficient than BLAKE3) and will dominate proof generation costs.

However, with batching, we can allow the following:

1. Clients generate their tx proofs using BLAKE3 or SHA256 hash functions - which should be significantly faster than using Rescue Prime or similar.
2. Batch producer verifies these proofs and outputs a batch proof which uses Rescue Prime as the hash function.
3. Block producer aggregates batches as before. The fact that some tx proofs were built using non-arithmetization-friendly hashes is transparent to them.

Recursively verifying proofs built using BLAKE3/SHA256 would be quite a bit more expensive - so, such transactions would need to include higher fee - but there could be use cases where this may be justified.

VM implications

To support the the above model, it seems like we may actually need 3 separate kernels:

• tx kernel to execute individual transactions.
• ag kernel to aggregate transaction proofs into batch proofs.
• os kernel to build block-level proofs (this would include aggregating batches but probably some other logic too).

[frisitano]

Thank you for this! This brings a lot of clarity to your vision of the execution model. I have one particular curiosity with this. I wonder if the requirement that all the transactions passed to the os kernel must already be proven could introduce undesirable latency properties for the system as a block can only be produced once all proofs have been produced.

As we are aware proof generation is far more time consuming that just running a program, this makes it undesirable to wait for proving before a block can be produced. As you have alluded to in your description - transactions touching the same state must be processed sequentially to ensure that pre-transaction state is known. Proof generation can take place in parallel and via a decentralised set of network participants provided that the pre-transaction state is known.

I wonder if you had considered a system that works as follows. The block producer selects a set of both local and network transactions from the transaction pool and executes the state transitions associated with the transactions. They produce a block which contains initial database state commitments, ordered network and local transactions and also final database state commitments. The block producer would only execute the state transitions and would not do any proving at this point. They would then publish this unproven block. This will allow the blockchain to proceed with block production without having to wait for proof generation to complete. Once a block has been publish the network provers now have an ordered set of transactions and initial + final database commitments. Under the model you described you could have prover_n generate proofs for transactions n to n+100. This may include both generating proofs for network transactions by running the tx kernel and also aggregating proofs using the ag kernel. These batch proofs would then be passed to the os kernel as you described. This system would allow new blocks to be produced and could give users fast guarantees of finality even before proofs have been generated. I believe this is a similar construct to the one that starkent have implemented.

I also wonder if you had considered the implications of the note based model on MEV. Are there any potential mitigation strategies like ordering transactions based on the lowest note serial number they consume?

[bobbinth]

Great questions! The short answer: if we can manage it, I'd like to avoid splitting sequencing and proof generation. I think having them done at the same time is conceptually simpler and more flexible. But if once we have the basic pieces in place, we find out that the latency is unacceptably high, we will reconsider.

A slightly longer answer.

I like to think about latency as in roughly 3 categories:

1. Very fast: sub 1-second latency
2. Fast: sub 10-second latency
3. Slow: 10+ second latency

[The above are applicable to moderately small transactions - i.e., under $1000. Obviously, if we are transferring hundreds of thousands or millions of dollars, much higher latencies may be acceptable].

My hope is that even with coupled execution and proof generation we can stay in the fast category. It may require significant hardware (e.g., each network transaction may need to be proven on a dedicated 64-core machine, or something like that) but overall, I hope that tx proofs will take a couple of seconds (on many machines), tx batch aggregation will take a couple of seconds (also on many machines), and the final block proof generation will also be a couple of seconds (on a single machine). So, overall execution + block production time will be somewhere between 5 and 10 seconds. This, of course, depends on many things such as TPS, split between public and private transactions, types of crypto primitives used etc. - and more importantly, all of this still needs to be benchmarked.

Achieving sub-second latency is a very different challenge. In a centralized (or even semi-centralized) setting, it actually should not be too difficult to do (even without trust assumptions). But in a decentralized setting, I think this is still an open question regardless of whether we decouple sequencing and proof generation (e.g., even propagating a transaction over a peer-to-peer network may take over a second). So, for now, we are not trying to solve this problem.

Regarding MEV: to be honest, I haven't spent much time on this. I think MEV mitigation may be complicated, not so much because of the note-based model, but because of the multi-asset model which prevents hiding of asset amounts in public transactions. But much more thinking is needed to see how much of problem it is, and whether the note-based model actually offers any advantages here.

[maxgillett]

I wonder if there is a way to generalize the proposed execution model to enable more than one type of transaction and state model. This can act as a hedge against the possibility that the currently proposed models fail to satisfy the needs of all applications and users.

It is easy to observe that different types of applications benefit from different state and transaction representations. For example, a payments-focused rollup would benefit greatly from the proposed actor-message architecture. In such a setting, transaction processing is highly parallelizable, and little to no coordination is needed with the sequencer, as notes containing assets can be produced and consumed asynchronously. However, a rollup hosting DeFi protocols requires a large degree of composibility. For example, an exchange aggregator may need to split a large trade across several DEXs in order to obtain the best execution price -- an interaction which is cumbersome in a note-based transaction model.

Instead of enshrining one particular state model, it should be possible to allow multiple state models with completely different properties to coexist. Each state model would be associated with its own set of potentially unique block and transaction kernels that constrain the space of allowable state transitions. The basic implementation idea is to introduce an independent block producer for each environment (I'll use "environment" from now on to refer to both the state and transaction model), along with a block batcher role, which exists one level beneath the block producer. The block batcher is responsible for verifying single block proofs for each environment and batching them into a single superblock. The block batcher would also generate a new proof attesting that the set of state commitments was correctly reduced to a smaller set, which is then submitted to L1. Note that the block batcher does not need to know the full state of each environment, only their initial state commitments, and that different block producers can operate in parallel as they evolve the state for isolated environments.

Bridging between environments can be solved by deploying smart contracts that validate the appropriate authenticated state representations of source and destination environments, as has been described elsewhere in the context of L3s. It can also be enshrined through the definition of block kernel functions that mediate creation/destruction/yanking of state across environments. For example, to bridge an asset from environment 1 to environment 2, either a block kernel function or account/smart contract would verify that a transaction locking an asset in environment 1 was executed before creating its equivalent representation in environment 2.

Reading through the above, it might seem that I'm describing an L2/L3 architecture, but this approach differs in some key ways. In a typical L2/L3 design, the L2 is a general-purpose execution layer, where developers can deploy arbitrary smart contract logic, including verifiers for L3 rollups. In those designs, the L2 acts as a kind of intermediate settlement layer for deployed L3 rollups, and their liveness also depends on that of the L2 block producer. In the execution model described in this comment, there is no enshrined general-purpose L2 execution layer. Instead, the block batcher serves to efficiently aggregate and verify state transition proofs for multiple isolated enviroments, and can even facilitate their bridging. The currently proposed state and transaction models could exist as the first of these environments, and more can be added at a later time by upgrading the batcher kernel. This design places all environments on an equal footing, where each environment can use L1 as a direct settlement layer. This approach shares some similarities with Tezos' vision of enshrined rollups described here.

Another interesting feature of this archiecture is that VMs other than the Miden VM could be used at the level of block production or transaction execution. The only requirements are that the batcher can efficiently verify the proof of VM execution, and a whitelisted kernel exists for that VM at the appropriate level. This could potentially allow for radically different environments to live alongside each other, such as a zkEVM, with kernel-based bridging that is settled on L1 (not IOU-based) and provided at a fraction of the cost as having to move assets from one rollup to another on L1.

[bobbinth]

I was thinking about something similar as well - though, I didn't take it quite as far as heterogeneous state models. Also, in my mind, the order of batching and block production was reversed from what you've described above.

Specifically, I was thinking we could have multiple transaction kernels. Each kernel would enforce specific semantics. For example, the model that we've been discussing so far assumes that a kernel takes a $n$ notes and $1$ account as inputs, and outputs $m$ notes and a new state for the account. But this could be expanded in various ways:

• Another kernel could take a single note as input, and output a new account. This could be a good way to create new accounts.
• Yet another kernel could take $n$ notes and $m$ accounts as inputs, and output $k$ notes and updated states for all $m$ accounts. This kernel could support direct cross-account calls.

Over time, we could add more kernels to handle different situations (e.g., a kernel that verifies zkEVM execution across multiple involved accounts).

Each transaction, when created, will specify which tx kernel it targets. Then, when we aggregate transaction into a batch, the aggregation kernel will be able handle different tx kernels. This way, as single transaction batch could contain transactions executed with different kernels.

From the standpoint of final block production, the fact that different tx kernels are involved is completely transparent. To produce a block we still just verify some number of batch proofs.

I think the above model achieves the goal of supporting different interaction and execution models between accounts, but it is probably not as flexible as what you've described. At the same time, it is probably not as complex. Though, we should think through both of these claims to see if they are actually true.

[frisitano]

I am naturally more aligned with the model that @maxgillett suggested with multiple environments with different state models and state transition functions. It's an interesting idea to allow multiple transaction kernels to exist in a single environment, however I suspect that to achieve an optimized system the state model should be designed around the execution model. Whilst it may be possible to have a zkEVM transaction kernel alongside the standard Miden kernel we may find that the zkEVM kernel will inherit additional complexity due to working with a state model which may not be well suited. Ultimately I see this as a trade off between architectural complexity (multiple environments each with their own state model and state transition kernel) vs state transitions function / transaction kernel complexity (single environment with a single state model and multiple state transition kernels).

Regarding the design of the batch / block kernels I think this is a trade off between generality and optimization. For example two different environments with two different state models will likely have two different state update representations that are need to be posted to the base layer. If the batch and block kernels are state model aware then they could potentially provide optimizations by aggregating updates across accounts. If the batch / block kernels are state model naive then they will not be able to apply these optimizations and would have to post raw update data to the base layer incurring higher settlement costs but they would be more general purpose. Maybe this could be overcome by allowing for pluggable modules for the batch / block kernel which provide this aggregation logic for each state model but this likely increases complexity and may not be practical.