Potential transaction model

[bobbinth]

I'd like to start discussing how the rollup itself could look like because for the design decisions beyond Miden VM v0.2 we'd need to have a pretty good understanding of what we are building towards.

To this end, I'll try to describe some of the thoughts I've accumulated over time. These are not meant as comprehensive descriptions. Some details may be omitted for brevity, while other details may be omitted because I have not thought them through yet. In all cases, these are just preliminary thoughts, subject to drastic changes.

First, here are high-level design goals I have for Polygon Miden:

1. Parallel transaction execution where causally independent transactions can be processed in parallel. I believe this is needed to achieve ultimate scalability.
2. Support for composable smart contracts via safe but Turing-complete language. This is needed to support safer wallets, DeFi, DAOs, and many other cool use cases.
3. Native support for multiple assets where the environment itself ensures asset safety, allows fee payments in multiple assets etc.
4. Privacy which includes ability to engage in private transactions as well as have privacy-preserving smart contracts.
5. Ethereum compatibility which includes ability to reuse Solidity smart contracts (with as few modifications as possible) on Polygon Miden, as well as support for such user-facing tools as MetaMask.

Not all of these goals will be address in this note, and some may be addressed only superficially. A more detailed and expanded look into these is left for future discussions.

The architecture

The architecture described below is loosely modeled after the actor model. In this model there are actors who communicate with each other via message passing. In our context an actor is an account, and messages are notes. Both accounts and notes can hold value (or assets). All of these are described below.

Assets

An asset is a way to represent a unit of value. I am not going to go too deeply into describing how assets work, but at the high level there are two types of assets: fungible and non-fungible. All assets have a unique identifier (e.g., something like a 24-byte value). Fungible assets also have an amount, while non-fungible assets have a serial number.

An example of a fungible asset could be ETH. In this case, an asset could be 1 ETH, where 1 is the amount and ETH stands in for an asset ID. An example of a non-fungible asset could be a collectable where the ID defines a collection and a serial number specifies an item in that collection (there could also be other ways to define an NFT).

Accounts

An account is an entity which holds assets and defines rules of how these assets can be transferred. The diagram below illustrates basic components of an account.

In the above:

• ID is a unique identifier (e.g., 32 bytes) of an account which does not change throughout its lifetime. This is not the same as address as accounts do not have addresses.
• Storage is user-defined data which can be stored in an account. The exact mechanism is TBD. For example, this could be a key-value map or an index-based array.
• Vault is collection of assets stored in an account. In this collection all fungible assets with the same ID are grouped together, and all non-fungible assets are represented as individual entries.
• Code is a collection of functions which define an external interface for an account.

Functions exposed by the account have the following properties:

• Functions are actually roots of Miden program MASTs (i.e., 32-byte hash). Thus, function identifier is a commitment to the code which is executed when a function is invoked.
• Only account functions have mutable access to an account's storage and vault. Said another way, the only way to modify an account's internal state is through one of account's functions.
• Account functions can take parameters and can create new notes.

Notes

A note is a way of transferring assets between accounts. A note consists of a vault and a script as shown in the diagram below.

A note's vault is basically the same as an account's vault. However, unlike an account, a note has a single executable script. This script is also a root of a Miden program MAST. A script is always executed in the context of a single account, and thus, may invoke account's functions. For example, a simple script could look like this:

begin
  push.123
  call.0x123456    # this may correspond to `function1`
end

The above will push value 123 onto the stack and then call a function with MAST root 0x123456 (assuming such function exists in the account). A few other things to note about note scripts:

• A note script can take parameters (passed via the stack). This could be one way to pass such environment variables as block hash, account ID etc. to a script.
• A note script does not have to call any of account's functions. More generally, a note's script can call zero or more of an account's function.
• A script is not explicitly tied to any specific account. For example, the above script can be executed against any account which exposes a function with root 0x123456. However, it is possible to tie scripts to accounts explicitly. For example, if we wanted to make sure a script can be executed against an account with ID 0x9876, we could do something like this:

use std.account;

begin
  exec.account::get_id
  push.0x9876
  eqw
  assert
  push.123
  call.0x123456
end

Executing this script will have give the same result as executing the earlier simpler script, but this script cannot be executed against any other account.

Transaction model

Asset transfers between accounts are done by executing transactions. A transaction is always executed against a single account (it may be possible to relax this condition, but this would require more thinking). It can consume zero or more notes, and it may produce zero or more notes as shown in the diagram below.

In addition to specifying inputs and outputs, a transaction must also include a single executable script. This script has a well-defined structure which must do the following:

1. Build a single unified vault for all inputs.
2. Execute scripts of all input notes (the scripts are executed one after another).
3. Execute an optional user-defined script.
4. Build a single unified vault for all outputs.
5. Make sure the unified input and output vaults contain the same set of assets.

The last point ensures that a transaction does not create or destroy any assets.

Under this model transferring assets between accounts requires two transactions as shown in the diagram below.

The first transaction invokes a function on account_a (e.g., "send" function) which creates a new note and also updates the internal state of account_a. The second transaction consumes the note which invokes a function on account_b (e.g., "receive" function), which also updates the internal state of account_b.

It is important to note that both transactions can be executed asynchronously: first transaction1 is executed, and then, some time later, transaction2 can be executed. This opens up a few interesting possibilities:

• Owner of account_b two may wait until there are many notes sent to them and process all incoming notes in a single transaction.
• A note script may include a clause which allows the source account to consume the note after some time. Thus, if account_b does not consume the note after the specified time, the funds can be returned. This mechanism could be used to make sure funds sent to non-existent accounts are not lost.
• Neither sender nor the recipient need to know who the other side is. From the sender's perspective they just need to create note1 (and for this they need to know the assets to be transferred and the root of the note's script) - they don't need any information on who will eventually consume the note. From the recipients perspective, they just need to consume note1. They don't need to know who created it.
• Both transactions can be executed "locally" - e.g., we could generate a ZKP proving that transaction1 was executed and submit it to the network. The network can verify the proof without the need for executing the transaction itself. Same can be done for transaction2. Moreover, we can mix and match - e.g., transaction1 can be executed locally, but transaction2 can be executed by the network, or vice-versa.

Wallet example

Let's consider a simple wallet example. An account implementing such a wallet would define two external functions: send and receive.

The send function would be responsible for sending funds out of the account. It could take the following inputs:

• Asset to be sent - e.g., asset ID and amount.
• Recipient - this could be a root of a note's script. Anyone able to execute this script would be able to claim the assets.
• Certificate - this could be a signature against an account's public key. Basically, something that proves that the owner of the account is authorizing this transfer. This can actually be provided as a non-deterministic input.

The function would verify that the certificate is valid, that the account has the specified asset, and then would remove the asset from the account's vault and create a note as [asset, recipient]. The note's script could be something similar to what was sketched out earlier (e.g., it could tie the note to a specific account ID).

The receive function would be responsible for accepting assets into an account. It would would be fairly simple: take an asset as an input and add it to the account's vault.

One thing to note is that having these send and receive functions should be sufficient to support atomic swaps (e.g., a note which invokes both send and receive functions as a part of its script). This could enable a lot of interesting use cases. For example, this can be used to simulate a network-wide decentralized exchange without needing any 3rd party smart contracts. However, this is outside of the scope of this note (and requires a bit more additional thinking).

Evaluation

Assuming the above architecture works, what does it give us?

1. We get parallel transaction execution: every transaction affects only a single account state, and the inputs consumed by a transaction are explicitly defined - so, no complicated logic needed to figure which transactions can be processed in parallel. Moreover, we actually get the ability to do local transaction execution which takes things to a whole new level.
2. We retain the ability to write expressive smart contracts. In many ways these contracts can actually be more powerful than what is possible on Ethereum today, but in some ways they may be more limiting (e.g., it is not immediately obvious to me how to support flash loans).
3. Third, we get native multi-asset support. On the fungible asset front things should be fairly straight-forward. However, there is still some thinking needed to make sure non-fungible assets are compatible with Ethereum NFTs etc.
4. It should be relatively straight-forward to support both private transactions and privacy-preserving smart contracts. Though, much more thinking is needed about the exact details.
5. Figuring out how to make this architecture Ethereum-compatible requires much more thinking. For simple contracts it should be relatively easy. But supporting cross-contract calls might require some changes (e.g., we might have to allow multiple accounts per transaction or do something entirely different). Or we might have to allow accounts with mutable code, or maybe something entirely different.

And just to re-iterate what was said in the intro, the above description glosses over a lot of details. For example:

• There are almost no implementation details on how account, notes, assets are to be represented.
• This does not describe how new accounts can be created.
• This does not describe how new assets can be created or destroyed.
• This does not describe how metering and fees would work.
• This assumes that we have some functionality in Miden VM which we currently don't (e.g., storage and privileged access to it for some functions).

These and many other topics are left for future discussions.

[maxgillett]

Just posting a few random thoughts below:

• It seems that smart contracts are analogous to accounts, and conventional EVM transactions to notes. So if a bunch of users wanted to interact with a smart contract account, they would independently generate notes which could then be sequentially ordered within the inputs of a single transaction and processed together. If a contract needs to call another account (and so on), I imagine that the contract would generate a note in the output that needs to be consumed in the context of the callee. Maybe these calls could consist of "dynamically" chained inputs and outputs within a single transaction so that notes can be consumed atomically? There could be a separate "input" access list so that the transaction remains parallelizable without having to simulate its effects.

• Just to clarify in the asset transfer example, in principle is anyone able to construct transaction2 to execute note1 in the context of account_b? Is it up to the receive function of account_b (or the note's script) to restrict note consumption to certain transaction signers?

• I wonder if assets could be implemented by introducing a Resource actor with the same components as an account. Assets could then be introduced as messages that can only be produced or consumed by the resource. The resource could specify a collection of functions that can potentially mint or burn the asset, and also govern how assets can be joined or split. This could allow for native fractionalization of NFTs and semi-fungible tokens, and possibly makes it easier to port an asset that needs to conform to the ERC20 specification for backwards compatibility.

• I also wonder if vaults (both in accounts and notes) could contain both assets and accounts for better isolation and composability. For example, to interact with a lending protocol you would create a new account with code implementing the required interface, transfer the required assets to it, and place the account within your vault (or another custodian's account). You could imagine situations in which it's useful to move accounts around as a primitive (for example, Gearbox Protocol).

[bobbinth]

So if a bunch of users wanted to interact with a smart contract account, they would independently generate notes which could then be sequentially ordered within the inputs of a single transaction and processed together.

Yes, that's how I thought about it as well.

If a contract needs to call another account (and so on), I imagine that the contract would generate a note in the output that needs to be consumed in the context of the callee. Maybe these calls could consist of "dynamically" chained inputs and outputs within a single transaction so that notes can be consumed atomically?

Yes, having these "chained" transactions could be a very good way to simulate how Ethereum works. In my original thinking I imagined that transactions consume already existing notes (i.e., created in prior blocks). It should be possible to relax this and say that newly created notes can be consumed as well - thought, more thinking is needed to understand potential implications.

Is it up to the receive function of account_b (or the note's script) to restrict note consumption to certain transaction signers?

Yes, that's the idea. A note can be consumed in a transaction involving any account as long as the note's script can be executed successfully in the context of that account. There are a couple of things worth noting though:

• The fact that we use "call-by-hash" convention (because we use MAST) ensures that we know exactly which code will be executed. So, when a note's script invokes a function (e.g., send or receive) we know what the effects of that invocation will be. This, for example, is not the case in Ethereum where calls are made by function signature (e.g., two accounts could have receive functions with the same function signatures but different execution semantics).
• In the above article I didn't describe how to do replay protection. I'd imaging accounts would also need to have something like a nonce or a sequence number. Then, when calling send function, the signature provided by the tx originator would need to cover this nonce as well.

I wonder if assets could be implemented by introducing a Resource actor with the same components as an account. Assets could then be introduced as messages that can only be produced or consumed by the resource.

This is roughly how I was thinking about it as well. In theory, any account can produce assets of its own type. For example, we could take the first 24 bytes of an account's ID and say that this is an ID for a "native" account asset. Then, there could be some special logic during comparison of unified input/output vaults to exempt assets with "native" IDs from the constraints I described in the article.

It might make sense to impose some other restrictions on accounts which are able to produce (or destroy) assets - but that could be a topic for another discussion.

I also wonder if vaults (both in accounts and notes) could contain both assets and accounts for better isolation and composability.

Oh, interesting! I haven't consider this - so, will need to spend some time thinking about potential implications. Two things to note for now:

• This does bring a question about how accounts are created (which I didn't cover in the original article). This is still something that needs to be thought through.
• In the architecture I described account ownership model can be really flexible. For example, an account does not need to be tied to a single public key. In fact, the public key of an account could be stored in it storage, and the account can expose a function which would allow updating its public key (essentially transferring ownership of an account between entities). There could be more complex models too when joint ownership can be established for a period of time (or until some conditions are met).

[bobbinth]

A bit more explanation of how transaction execution works. As I mentioned in the original article, transaction execution consists of several steps. These steps (grouped slightly differently) are described below:

1. Prologue: during this step we build a single unified vault all all transaction inputs (account + notes).
2. Execution: during this step we first execute scripts of all input notes (one after another), and then execute an optional user-defined script (called tx script).
3. Epilogue: during this step we build a single unified vault of all transaction outputs (account + notes), and make sure it contains the same assets as the input vault.

Using the above convention, we can put together a few call diagrams for various transactions. For example, a transaction which sends money out of a wallet may look like so.

This transaction does not consume any notes but has tx script which calls the send function. Send function then creates an output note (not pictured).

A call diagram for a transaction which receives funds into a wallet may look like so:

As opposed to the previous transaction, this transaction consumes a single note (note1) but does not have a tx script.

A transaction could also consume several notes at the same time. A call diagram for such a transaction may look like so:

Or a transaction can consume notes and produce notes a the same time. The transaction below does one of each.

Note that this transaction is not atomic: consumed and produced notes are not related to each other. Thus, this transaction could have be easily broken up into two independent transactions. To make a transaction atomic, we'd have to have a single note which invokes both send and receive functions, similar to how it is shown on the diagram below.

[snjax]

In ZeroPool we use an account-based model close to this one. So, the transaction has one account input, one account output, and arbitrary note input and output. The advantage in comparison with fully UTXO-based models (like sapling) that's we publish only one nullifier per account. The disadvantage is that we can spend notes only in chronological order. We reach it by storing the interval of spent notes inside the account and incrementing this interval in any transaction.

For private transactions, the anonymity set is corresponding to one Merkle tree. @bobbinth are you planning to build fully private transactions (with hidden both amounts and transaction graph) or just hidden amounts? In the 1st case, there are some issues with scalability, because all notes and accounts should be put inside one Merkle tree. We are using Poseidon hash, it is not so fast.

Also, the logic of nullifiers (one nullifier per account like in ZeroPool or one nullifier per note like ZCash or something else) seems to be not generalizable by arbitrary scripts.

Is the main purpose of using the account-notes-based model in Miden privacy or scalability?

[maxgillett]

I was thinking about this some more, and I'm not sure what I proposed works. There still needs to be some kind of public record of the supplied account's state transition, even if the state is not made public, which preserves linkability. I suppose accounts could also have a nullifier of some kind so that they work similar to notes, and can also be "consumed" and created within a transaction, but this might have other implications for the model. How are you thinking about the mechanics of account state in the example above in terms of state transitions and hiding/revealing state?

[bobbinth]

I'm wondering if there's a way to break account linkability if a note's preimage is revealed (in the scenario above, account1 is linked to note2 once it's consumed in a transaction that's not executed locally). I'm assuming that this would have to occur when interacting with any public smart contract account.

Yes, you are correct. When sending an "unshielded" note the model I described would make it trivial to link accounts to notes. More thinking is need on how to best avoid this.

This doesn't prevent the potential linking of a revealed note's vault contents with a revealed account state change, but this could be dealt with before any reveal by splitting notes (and their vault contents) in subsequent locally executed transactions that don't have account side effects.

I'm thinking there could be two types of accounts:

1. Accounts with public state, where the actual state is stored on chain. These would be similar to how accounts work in public blockchains.
2. Accounts with private state, where only the hash of the account is stored on chain. The hash could be defined as something like hash([account ID], [storage root], [vault root], [code root]).

In case of private accounts, their state would not need to be made public for locally executed transactions (i.e., public inputs would be account ID and account hash, and the actual state would be provided as a witness). Thus, it should not be possible to observe an account's vault changes for such transactions.

I suppose accounts could also have a nullifier of some kind so that they work similar to notes, and can also be "consumed" and created within a transaction, but this might have other implications for the model. How are you thinking about the mechanics of account state in the example above in terms of state transitions and hiding/revealing state?

Yes, it could be done this way but there are a few additional considerations.

First, in the context of locally executed transactions, proving that something is in the global state (e.g., via a Merkle path against a state root) presents two challenges:

1. The client needs to be able to generate an up-to-date witness against the root. This may require constantly observing the chain (or syncing to the latest state).
2. The proof should not become stale between the time the client submits a transaction and the time the network includes it into a block.

In case of low-latency chains, when state roots change with every block, addressing the above may be tricky. However, if the underlying data structure is an append-only log (e.g., something similar to this) the problem becomes much simpler:

1. Generating an up-to-date witness would require very little chain observation, and it may be possible to eliminate the need to observe the chain entirely.
2. The "lifetime" of proofs is much greater, and it should be possible to make it so that the proofs never become stale (though, there might be some tradeoffs here).

With the above in mind, I was hoping to do the following:

• Account states are recorded in something like a Sparse Merkle tree (i.e., account id -> account hash).
• Notes are recorded in an append-only log similar to the one mentioned above.
• Nullifiers are recorded in something like a Sparse Merkle tree (i.e., nullifier -> block height), where block height is the height of the block at which the nullifier was added to the tree.
• Proofs for local transactions need to prove inclusion only against the note tree.

[bobbinth]

Another (admittedly hacky) way to handle this might be to use a "firewall" account.

Let's say we have an account a which wants to interact with a public smart contract c. Instead of sending a note directly to c, a sends a note to a "firewall" account b. This account has a well-defined public interface with the only function to take an incoming note and output the same but "unshielded" note (minus fees etc.). The interaction graph would be as follows:

a  -- note1 (shielded) --> b --> note2 (public) -> c

In the above, both note1 and note2 could be outputs of local transactions - thus, the link between a and note1 is not revealed. Moreover, b does not need to maintain any state, or really do anything note/account-specific - thus, there could be just a single account b for the whole network to use.

The downsides of this approach (besides being hacky) are:

• The user needs to submit two transactions, and thus this option would be more expensive than the single-transaction one.
• There probably should be some delay between generating note1 and note2, otherwise, some level of linkablity is still probably possible.

Another application of this mechanism: transactions between two private accounts such that the recipient cannot identify the sender.

[snjax]

@bobbinth here is the description of account-based privacy https://www.youtube.com/watch?v=f885LTdgJVs, https://ethereum-magicians.org/t/account-based-private-transaction-engine/4833.

If at least one of the accounts is private, the transaction between them looks safe in terms of privacy also.

Could you show the description and/or implementation of 64bit Poseidon?

[snjax]

There could be some improvements in implementation for better compliance. For example, in ZeroPool the account roughly looks like
(public_key, amount), and the nullifier is H (H(account), H(H(account), private_key, merkle_path)).

So, for compliance, it's enough to disclose account fields and intermediate hash H(H(account), private_key, merkle_path) without any spending-sensible data.

Also, we are using diversified public keys, like in ZCash. In general elliptic cryptography for the private key s we get public key as ecmul(generator, s), for the private key s and diversifier d we get diversified public key (d, ecmul(hash_to_point(d), s)).

Diversified public keys allow to user build a set of multiple public keys for one private key (and only the owner can connect it together). Also, the user can find encrypted incoming notes for all diversified public keys with one simple check.

Also, there is one more trick to using the intermediate key to prove and encrypt-decrypt, and the spending key to sign. We suppose the proving device is not so trusted as a hardware wallet, but a hardware wallet cannot prove transactions.