Potential state model

[bobbinth]

This note is a follow up on #192. In that note I briefly touched on how the state of the rollup can be represented to support the described transaction model, and in this note I'd like to expand on this.

The goals that we'd like to achieve with the state model are as follows:

1. We'd like to reduce "state bloat" as much as possible. Ideally, we'd like the size of the sate to grow in proportion to the number of active accounts (as opposed to the number of total accounts or, worse, the number of transactions).
2. We'd like state transition to be very easily provable with ZKPs, ideally in a recursive manner. This is needed to submit efficient transition proofs to the L1, but also makes it easier for new nodes to join the network.

As with the previous note, all the same caveats apply: these are just preliminary thoughts, and a lot of details have been omitted either for brevity or because they are still to be figured out.

As mentioned in #192 (reply in thread), the system maintains 3 databases to describe the state:

1. A database of accounts.
2. A database of notes.
3. A database of nullifiers for already consumed notes.

Before describing these in detail, it would make make sense to go over the higher-level logic of how the chain makes progress.

State transition

For simplicity, let's imagine a simple centralized model:

• There is a single operator who collects transactions from users.
• This operator puts collected transactions into blocks.
• The blocks get submitted to Ethereum L1, and once a block is included in the L1 chain, the rollup chain is assumed to have moved to the next state.

A block which the operator produces could look something like this:

A few notes about the above:

• state updates contain only the hashes of changes. For example, for each account which was updated, we'd record a tuple ([account id], [new account hash]).
• The included zk proof attests that given a state commitment from the previous block, there was a sequence of valid transactions executed that resulted in the new state commitment, and also output included state updates.
• The block also contains full account and note data for public accounts and notes. For example, if account 123 is a public account which was updated, in the state updates section we'd have a records for it as (123, 0x456..). The full new state of this account (which should hash to 0x456..) would be included in a separate section.

Then, to verify that this block describes a valid transition, we'd do the following:

1. Compute hashes of public account and note states.
2. Make sure these hashes match records in the state updates section.
3. Verify the included ZKP against the following public inputs:
   • State commitment from the previous block.
   • State commitment from the current block.
   • State updates from the current block.

The above can be performed by an L1 contract for a full rollup mode. Or, if we skip the first two steps and put only state updates (without full account/note state) on L1, this would be something in between a rollup and validium.

This structure has another nice property: it is very easy for a new node to sync up to the current state from genesis. The new node would need to do the following:

1. Download only the first parts of the blocks (i.e., without full account/note states) starting at the genesis up until the latest block.
2. Verify all ZKPs in the downloaded blocks. This will be super quick (exponentially faster than re-executing original transactions) and can also be done in parallel.
3. Download the current states of account, note, and nullifier databases.
4. Verify that the downloaded current state matches the state commitment in the latest block.

Overall, state sync would be dominated by the time needed to download the data. There are ways to dramatically optimize this part as well (e.g., recursive state proofs) - but I'll leave these for another note.

State components

As mentioned above, the state consists of 3 components: account, note, and nullifier databases. These databases need to be represented by authenticated data structures (e.g., Merkle trees), such that we can easily prove that items were added to or removed from a database, and a commitment to the database would be very small.

Account database

Account states could be recorded in a Sparse Merkle tree (or a variation thereof) which maps account IDs to account hashes, where account hash is computed as hash([account ID], [storage root], [vault root], [code root]).

There could be two types of accounts:

• Public accounts where all account data is stored on-chain. Transactions executed against such accounts must be network transactions - i.g., transactions executed by the network.
• Private accounts where only the hashes of accounts are stored on-chain. Transactions executed against such accounts must be local transactions - i.e., transactions where the user submits a ZKP to the network attesting to the correct execution of the transactions. (it is possible to relax this condition so that users could execute network transactions against private accounts, in which case, all account data would need to be included in a specific transaction - but for simplicity, I won't consider this here).

It is important to note that fees for local transactions will probably be much lower than fees for network transactions (because for a local transaction, the network just needs to verify a ZKP). Thus, users are incentivized to use private accounts, unless they indeed need the functionality offered by public accounts.

A potential concern could be that losing a state of a private account would mean loss of funds (as the user won't be able to execute transactions) in a similar manner as a loss of a private key would. But this problem can be easily mitigated by storing encrypted account state in a cloud or backing it up somewhere else. Unlike storing private keys in the cloud, this would not compromise privacy or security of an account.

Having many (or even most) of the accounts be private is very beneficial for the network as a private account contributes only 64 bytes to the global state (32 bytes account ID + 32 bytes account hash). Or, said another way, 1 billion private accounts takes up only $60$ GB of state.

The situation with public accounts is a bit more challenging - but our model has very nice properties here too.

First, observe that to verify validity of state transition we do not need to know full account states (i.e., we just need to know hashes of the state so that we can verify ZKPs). We need to know full account states only to execute public transactions agains them.

Thus, as a node, we could chose to discard full states for public accounts which haven't been used for some time. All this means is that we won't be able to execute transactions against these accounts, but if someone else execute a transaction against them, we can still verify that the state transition was valid (and we'll get the new full state of the account with the latest block).

It is important to note that the decision when to discard full account states does not need to be a part of the protocol - every node could decide for themselves. For example, there could be nodes which prune full state very aggressively, and in effect, they would only be able to include private transactions in their blocks. There could also be nodes which decide to keep full account states for years - so that they could execute transactions which few other nodes could (presumably for a higher fee).

This approach eliminates the need for complicated mechanisms such as state rent. The longer a public account remains unused, the fewer nodes would want to keep its full state. The fewer nodes keep its full, state, the higher fees can be demanded for executing transactions against this account. Thus, the nodes which chose to keep full states longer should get naturally compensated for their services.

Note database

Notes could be recorded in an append-only accumulator similar to the one described here. Using such an accumulator is important for two reasons:

1. Membership witnesses against such an accumulator needs to be updated very infrequently.
2. Old membership witnesses can be extended to be used with a new accumulator value, but this extension does not need to be done by the original witness holder.

Both of these properties are needed for supporting local transactions and private accounts.

Notes database could look as shown on the diagram below. Here, the database contains $7$ notes: $1$ through $7$, and the commitment to this database are the roots of individual trees (a, b, 7). Thus, the size of the commitment grows logarithmically with the number of items in it.

As with accounts, there could be two types of notes:

• Public notes where the entire note content is recorded in the state. Such notes can be consumed either in local or in network transactions - but in either case, they don't provide any privacy guarantees (i.e., it will be trivial to figure out which account consumed such notes).
• Private notes where only a note's hash is recorded in the state. Such notes can be consumed only in local transactions (though it is possible to relax this condition).

As with accounts, there would be a strong incentive to use private notes as they would result in lower fees. This is also beneficial to the network as a private note adds only 64 bytes to the state (32 bytes when it is produced, and 32 bytes when it is consumed).

Using an append-only accumulator means that we can't remove individual elements from it. This would seemingly mean that the size of the note database would grow indefinitely. Moreover, at high tps, it would grow very quickly: at 1K tps we'd be adding about 1TB/year to the database.

However, we need to explicitly store only the unconsumed public notes and enough info to construct membership proofs against them. Private notes, as well as public notes which have already been consumed, can be safely discarded. Such notes would still remain in the accumulator, but there is no need to store them explicitly as the append-only accumulator can be updated without knowing all items stored in it. This would reduce actual storage requirements to a fraction of the database's nominal size.

Moreover, since notes are not meant as long-lived objects, we can impose some lifetimes restrictions on them. For example, we could say that the system will store only $2^{35}$ most recent notes (a note not consumed in this timeframe becomes un-spendable). This can be easily done by discarding old commitment roots once the number of roots exceeds 35. At 1K tps this would mean that notes would be discarded after about 1 year, but this would also mean that the size of the note database will never grow beyond about 1TB.

Nullifier database

With nullifier database we want to achieve the following properties:

1. We need to be able to check that a given nullifier is not in the database. This is needed to ensure that notes consumed in a transaction haven't been already consumed.
2. We need to be able to prove that a given nullifier is not in the database. This is needed for state transition proofs we want to submit to L1.
3. We need to be able to add new nullifiers to the database. This would be done by an operator at the time when they create a new block.

To satisfy these properties we can use a Sparse Merkle tree which maps nullifiers to block heights at which they were created. For example, in the diagram below, the tree contains 2 nullifiers: nullifier 01 was inserted into the database at block height $4$, while nullifier 10 was inserted into the database at block height $5$.

To prove that nullifier 11 is not in the database we need to provide a Merkle path to its node, and then show that the value in that node is $0$. In our case nullifiers would be 32 bytes each, and thus, the height of the Sparse Merkle tree would need to be 256.

To be able to add new nullifiers to the database, operators needs to maintain the entire nullifier set - otherwise they would not be able to compute the new root of the tree. This presents a challenge similar to the one we encountered with the note database: the set of nullifiers seemingly needs to grow indefinitely. Worse, unlike with notes, we cannot discard any nullifiers at all.

However, the fact that notes are short-lived can be again used to our advantage. Specifically, if we know that notes "expire" after 1 year, we can safely discard all nullifiers which have been created more than 1 year ago. This also puts a maximum on the size of the nullifier set.

However, unlike with the note accumulator, removing nullifiers from the nullifier tree is more complicated: we can't just discard one of the old roots, we need to remove nullifiers from the tree one by one. Generating proofs that nullifiers have been removed correctly (i.e., the block height of removed nullifiers was smaller than block height from a year ago) would involve non-negligible amount of work. To make sure operators do this work, they may need to be incentivized (e.g., via a small payment for each removed nullifier).

Evaluation

Assuming the above model works, we get the following:

1. The state size depends primarily on two things:
   a. Number of active public accounts. Inactive accounts and private accounts do contribute a little bit to the state - but their contribution would be small (64 bytes per account).
   b. TPS - the higher the TPS the more notes and nullifiers we need to store. But the overall requirements are not huge. At 100 TPS, note and nullifier databases are unlikely to grow over 100 GB, and at 1K TPS, they are unlikely to get over 1TB. We can of course make the window during which notes remain live smaller (e.g. 6 months, or even 3 months) and in that case, state size would drop proportionally.
2. State transition shouldn't be too difficult to verify with a ZKP. We should be able to write a Miden VM program which takes the initial state and a set of transaction proofs as inputs, and outputs a new state together with a proof of the state transition.
3. Besides being able to verify state transition on L1 we also get a nice benefit that new nodes can sync up to the state pretty quickly as all they need to do is download data and verify ZKPs - no need to re-execute any of the past transactions.
4. Holding the entire state is not required for verifying validity of state transition. Thus, nodes may chose to drop various part of the state (e.g., some nodes may chose not to store states of public accounts, other nodes may chose to store states of specific public accounts etc.).

[frisitano]

Could you elaborate on the capabilities of state transitions which are generated off-chain and ZKP is submitted for on-chain verification. It would appear to me that there are some limitations to this model. For example, lets say we have some on-chain DEX with shared state and two users / accounts want to interact with this contract. Both users would use the DEX state as a precondition when generating the ZKP and therefore this would result in a race condition.

[bobbinth]

I'm planning to write another note describing the execution model in more detail, but to answer briefly:

The main reason interacting with a shared state is not an issue is because of our approach to the transaction model. In this model, interactions between two accounts actually require 2 transactions: one outgoing transaction and one incoming transaction. So, the example with a public DEX could work as follows:

Let's say we have a DEX account d and this account has an exchange() endpoint which can be called to exchange asset x for asset y. What this would actually mean is that when exchange() is invoked by a note's script, it would add a note's asset x to its vault, then remove asset y from its vault and create a new note with y and script root specified by the original note.

In the two-user scenario this would work as follows:

1. Transaction 1: user A sends note1 from their account to account d. This note specifies that 100 x should be exchanged for some number of y at the current price, and this amount of y should be put into a note with script root r1.
2. Transaction 2: user B sends note2 from their account to account d. This note specifies that 100 y should be exchanged for some number of x at the current price, and this amount of y should be put into a note with script root r2.
3. Transaction 3: a block producer executes a transaction which consumes note1 and note2. The result of this transaction is that note3 (with script root r1) and note4 (with script root r2) are created.
4. Transaction 4: user A consumes note3 which adds asset y to their account.
5. Transaction 5: user B consumes note4 which adds asset x to their account.

Note that in this model, the only transaction which updates a shared state is transaction 3, and this transaction is created by the block producer. Thus, there is only one entity which updates the shared state at a given time.

Also, in the above model:

• Transactions 1, 2, 4, and 5 could be local transactions, accompanied by ZKPs generated by users.
• Transaction 3 would have to be a network transaction. It could also be accompanied by a ZKP but this ZKP would be generated by the block producer at the time when they crate a new block.

[frisitano]

I have a follow up question on this... which network participant would be responsible for constructing transaction 3 that consumes note1 and note2 and what is the incentive for doing so?

[bobbinth]

Block producer would need to construct this transaction and then execute it immediately. They can outsource proof generation to others as described in the other note, but the execution cannot be outsourced.

As for the incentive, presumably, constructing and executing this transaction would yield fees which the block produce would be able to claim. Otherwise, there would be no incentive for the block producer to perform this task.

[frisitano]

I wonder how the incentive could be implemented. Possibly embedded into the scripts of note1 and note2? There would also need to be some mechanic to signal to block producers that an account wants to opt in to on-chain sequencing of notes targeting the account. I also wonder how the target account for each note is determined seeing as the intent is to constrain the target account inside of the note script. Maybe something more explicit like an optional field for this could help - ([vault root], [script root], [serial num], [Optional(target account)])? It kind of seems like MEV by design to incentivise block producers to construct and execute the transactions.

[bobbinth]

Yes, the logic for paying fees could be part of the scripts - but it could be in either in the account or in the note. For example, there could be pay_fee procedure which could be called both from note and from account context. In some situations, pay_fee could be called from the not script, and then, the fee would come from the note's vault. In other situations, pay_fee could be called as a part of an account's function, and then the payment would come from the account's vault (this effectively means that the account is paying the fee on behalf the note).

Note that the call to pay_fee would be a part of either account code or note script - so, the block producer does not have a say in when/how it gets called. The tricky part is figuring out how notes/accounts can estimate the appropriate fee amount which is not too high, but also not too low. This is still something we need to think through, but I think there should be good solutions here.

It kind of seems like MEV by design to incentivise block producers to construct and execute the transactions.

I'm not sure I'd go as far as saying this. I think about this as just being fees that are paid to the block producer for processing transactions. Ideally, these fees should not depend on where in the sequence a transaction is placed.

There would also need to be some mechanic to signal to block producers that an account wants to opt in to on-chain sequencing of notes targeting the account.

This would be a part of an account's interface (i.e., specified by the code_root). An account could have functions which can be called by anyone (in such a case, a block producer could execute them), but it could also could have functions which could be executed only by holders of some private key (e.g., such functions would check a signature against some public key stored in the account's storage before doing anything else). Figuring out if a particular note's script can be executed against a specific account should be fairly straightforward - scan the opcodes and for any call opcodes, look up the hash of called function in the account interface table, and then try to execute the script. If this proves to be too difficult, we might need introduce some other means of signaling by including additional metadata into a note.

I also wonder how the target account for each note is determined seeing as the intent is to constrain the target account inside of the note script.

This can be done implicitly from inside a note's script (as I described in #192) - but this would also require scanning through the code. To make this task simpler, we could also add some tags or markers to a note. In general, this will need to be solved for a different use case: P2P transfers. A sender should be able to mark a transaction as intended for some user to make it simpler for the recipient to determine that the transaction was sent to them.

[frisitano]

It kind of seems like MEV by design to incentivise block producers to construct and execute the transactions.

I'm not sure I'd go as far as saying this. I think about this as just being fees that are paid to the block producer for processing transactions. Ideally, these fees should not depend on where in the sequence a transaction is placed.

Yeah you're right - MEV isn't the right term. Conceptually I was thinking of it as some latent value that the block producer can extract via the construction and execution of transactions - however in this case it's just extracting fees, no additional surplus.

This would be a part of an account's interface (i.e., specified by the code_root). An account could have functions which can be called by anyone (in such a case, a block producer could execute them), but it could also could have functions which could be executed only by holders of some private key (e.g., such functions would check a signature against some public key stored in the account's storage before doing anything else). Figuring out if a particular note's script can be executed against a specific account should be fairly straightforward - scan the opcodes and for any call opcodes, look up the hash of called function in the account interface table, and then try to execute the script. If this proves to be too difficult, we might need introduce some other means of signaling by including additional metadata into a note.

This can be done implicitly from inside a note's script (as I described in #192) - but this would also require scanning through the code. To make this task simpler, we could also add some tags or markers to a note. In general, this will need to be solved for a different use case: P2P transfers. A sender should be able to mark a transaction as intended for some user to make it simpler for the recipient to determine that the transaction was sent to them.

This makes sense, having additional metadata associated with the note that signals target account and desire for block producer sequencing should do the trick.

[frisitano]

Thank you for the explanation this makes a lot of sense and helps build an appreciation for the possibilities enabled by the actor based transaction model - very exciting. It's now got me thinking about how sharding would work under this transaction and data model. I would guess that notes could simply be passed between shards enabling sharded execution of transactions. However I'm not so clear on how the data model would relate to a sharded architecture. Would each shard manage a partition of the accounts, notes and nullifiers databases? Could you elaborate on how you see the data / transaction model working with a sharded architecture please?

[bobbinth]

I am not sure I have a great answer here. First, to clarify what could be meant by sharding. I think there are two different ways (or maybe more) to define it:

1. Data sharding - where nodes don't need to keep the full state, but block production is still performed by one node at a time.
2. Execution sharding - where nodes don't need to keep the full state, and also blocks can be produced in parallel by multiple nodes.

Data sharding

If we are talking about data sharding, the accounts and notes databases don't need to be sharded explicitly. As described above, a node is free to select which public account states they want to keep in their database (i.e., they can discard all account states which haven't been touched for a while). They do need to keep 64 bytes per account - but that's relatively small, and I'm not sure there will be a need to shard this. The notes database can be compacted pretty easily as well - and I don't think there will be a need to shard it explicitly either.

For the nullifier database the story is different: there is no easy way to compact it (a node must always keep track of all active nullifiers), and I actually don't know of a good way to shard it. So, either some other design or a different cryptographic accumulator primitive is needed here to achieve sharding. One potentially mitigating factor here is that with the design described in the original note, the size of the nullifier database is dependent only on TPS. So, with current off-the-shelf hardware, 1K TPS may work fine, and then as hardware improves, it can be increased to 10K TPS and beyond.

Execution sharding

If we are talking about execution sharding, account database is pretty easy to shard since in the current model a transaction can involve only a single account. However, sharding note and nullifier databases would be quite challenging, and I don't know of a good way to do it. It also seems to me that execution sharding would have challenges on other front too (e.g., consensus).

There is also another approach to sharding execution: sharding only transaction proof generation and maybe batching of proofs using recursion. The challenging part here would be to figure out how to reward those who do this work in a decentralized setting.

[frisitano]

Ok thank you for clarifying - I was referring to execution sharding but was struggling to understand how it would work with this data model.

I think distributing proof generation makes a lot of sense and it's a very interesting topic. As you say the incentivisation scheme is challenging however there may be insights and ideas that can be taken from other models like PoS. If we ignore the incentivisation and assume we have a set of honest and reliable provers how do you envision the optimal utilisation of this prover set? Also diving into the the process of batching proofs via recursion - how does this look? I would naively assume that proof merging consists of producing a proof that attests to the verification of child proofs? Can we batch an arbitrary number of proofs at once?

[bobbinth]

I tried to answer some of these questions in #261 - but let me know if I missed anything.

[frisitano]

Thank you @bobbinth! Will give it a read :)