StarkNet Account Abstraction Model - Part 1

Overview

This post outlines the goals and model of account abstraction to be used in Starknet. We look to collect feedback and implement the model, possibly in phases, in Starknet Alpha. This is the first of two posts describing current thoughts.

At a high level, account abstraction refers to the abstraction of the concept of accounts and related mechanisms from the core protocol of the chain. So while identifying users is key to the system’s operation, we look to allow flexibility and extensibility in aspects relating to how accounts are verified and operate. We expect this to enable innovation in areas we can’t anticipate when defining the core protocol.

We describe the design choices and their rationale, with the known tradeoffs. Familiarity with Starknet and its underlying technology is assumed.

Goals

Similar to other account abstraction models suggested in Ethereum and other systems, we aim to provide flexibility in the Starknet protocol. Specifically in some key components of the protocol:

  1. Signature abstraction: allow different account contracts to use different signature validation schemes.
  2. Payment abstraction:
    • Allow different models of payment for transactions. For example, payment by another party/contract.
    • Better UX: don’t mandate a specific token (native or contract-defined) to be used for paying for transactions.

Model

Complete abstraction of the account, i.e., all transactions are sent to contracts that have complete freedom in how transactions are validated and executed, will achieve the above-stated goals. It will, however, result in confusing UX (e.g., hard to guarantee transaction uniqueness) and might open the door to attacks on sequencers.

We, therefore, maintain a model where accounts are still represented by contracts, so-called “account contracts”, but provide a more defined structure to this interaction. We follow, in spirit, the model proposed in EIP-4337 for Ethereum, with applicable changes made to accommodate the difference in Starknet and Cairo.

The gist of the mechanism is an account contract interface and a definition of its interaction with the Starknet OS and the sequencer node when handling a given transaction and including it in a block. The proposed interface requires an account contract to implement a validate and execute functions separately, with specific semantics and constraints on their operation. When used by the Starknet OS and sequencer, this allows the sequencer to validate a transaction and get paid for it with minimal risk.

Paying for Transactions

Paying for transactions is done by a specific token known to the OS. This is either a native token or some other known ERC20 implementation. At this point (StarkNet Alpha), Starknet will use ETH, implemented as an ERC-20 contract, for paying for transactions.

The Starknet OS handles payment for transactions under the correct conditions (see below). It is not left to the account contract implementation. This allows the OS to guarantee payment and avoid some of the risks to the sequencer executing the transactions.

Nonces

We see little value in abstracting the nonce itself from the protocol. Also, not guaranteeing a well-defined behavior (validation) of nonces creates issues with ensuring transaction uniqueness.

Therefore, nonces are defined as part of the contract state and part of the transaction structure and signature and behave similarly to how they are provided in the Ethereum protocol. In other words, transaction nonces are guaranteed to be sequentially increasing. The Starknet OS validates this.

A sequencer should limit the number of transactions per account (contract) it accepts into the pool. This is to prevent abuse of the pool as a means to DoS the sequencer or otherwise limit the resource usage per account.

A Simple Transaction Flow

We now describe a basic transaction flow, as depicted in the following diagram:

Simple Txn Flow

A transaction is sent to an address where an account contract is deployed to be executed and added to a block.

Note that the flow above describes the flow involving the OS. In practice, the sequencer doesn’t run the OS when executing each transaction. The OS is used to generate the proof and provides the necessary guarantees.

Adding Transaction to a Block

When a transaction is picked to be added to a block, the sequencer picks it and executes it. The execution of the transaction happens in two stages: the sequencer first asks the account contract to validate the transaction and then asks the account contract to execute it. These two stages are encoded in two separate functions in the account contract - validate and execute. The distinction between these stages allows Starknet OS to guarantee payment to the sequencer.

When an account contract successfully validates the transaction, the fee is collected (verified by the OS), so the sequencer is guaranteed to receive the payment, even if the transaction fails later during execution. When a transaction fails validation, no fee is paid; otherwise, this can be a potential attack vector by a malicious sequencer. Both validate and execute functions are part of the account contract code, encoded in Cairo, and therefore are proven as part of the block.

To prevent attacks by implementing a malicious account contract implementation, the validation function is constrained:

  1. The number of steps in the validate function is limited.
  2. The validate function cannot access the storage of other contracts (outside the account contract).

The first constraint prevents abuse of the sequencer before successfully validating a transaction and getting paid for it. The second constraint addresses a potential risk where an attacker might fill the transaction pool (“mempool”) with many transactions and then invalidate them with a single operation that changes some storage in a 3rd party contract by making sure that transaction gets included first. Ensuring that validation depends only on local storage makes such an attack more expensive. It will require an attacker to invalidate storage separately per account, i.e., many storage updates. So the cost of such an attack is proportional to the potential damage.

Simulation

Transactions to be included in a block are picked from the available transaction pool. To prevent a DoS attack using the mempool (the Starknet transaction pool) - filling the pool with apriori invalid transactions, we first mandate that a node accepting a transaction simulates locally against the known state before it adds it to the mempool and broadcasts it to other nodes, namely to sequencers.

txn simulation

When a node receives a transaction, it runs the validation function (a function call) by the designated account contract. This is analogous to the initial transaction verification (signature, nonce, etc.) done in the core Ethereum protocol. It allows validation of transaction information, signature, and the ability to pay. A transaction is not considered a failed transaction if it does not pass this validation; it’s simply not accepted in the network.

The simulation should verify that the validation function accesses the state it can access or otherwise doesn’t behave in a way that is not allowed by validation, e.g., running forbidden system calls.

Upon successfully completing the simulation, the transaction can be entered into the pool and propagated in the network.


So far we covered only the basic flow of adding a transaction. This achieves the goal of abstracting the signature. In the next part, we’ll address the topic of fee abstraction and potential extensions.

28 Likes

Sounds great. As for the note about " The validate function cannot access the storage of other contracts (outside the account contract)" - what about other type of non-interactive invalidation, such as dependency on certain block number? So an attacker inputs a million valid transactions for validation, and the transactions get invalid only at certain block, before they are executed? Or are such transactions still considered ‘valid’?

4 Likes

This might be addressed in the next post you alluded to, but I’m curious about 2 things regarding TX cost:

  1. Does executing validate count towards TX fees?

  2. How does the OS know the TX cost before it executes it (the “Pay for txn” step is before the “Execute txn” step)?

6 Likes

What do you mean by “Add txn failure to the batch”? Aren’t “failed” transactions unprovable?

3 Likes

We would like to avoid a situation where a transaction’s validity is defined by “outside” information; i.e. not intrinsic to the account or the transaction itself.

A block number is an example of such external information. So validate should not be able to rely on it.
An account contract is therefore limited also in the system calls it can make, one of which is getting the block number.

3 Likes

The whole topic of fees and the exact mechanism is still tbd.

In the current mechanism (being implemented for StarkNet Alpha), the main driver of cost is the information sent to L1, and the fee paid is sent as part of the transaction. So it’s less of an issue.

3 Likes

This assumes we can, as mentioned here.

Even if we don’t we’ll need to have some (proven) operation that is implied by the failure, e.g. the red fee.

4 Likes

It is mentioned above that the validation function implemented by an account contract will be limited to some number of steps but couldnt find any exact description of this - in what way is this function limited ?

For instance, what if we have an account contract that implements IAccount interface as well as IERC721 interface - then we could issue an NFT to the public key initialising the account contract and is_valid_signature could check whether the signing public key is the owner of the said NFT which was minted on initialization. This could turn an account into a more general blockchain primitive where account ownership could be transferred independent of the wallet perhaps - and also transfer of ownership of an account could become as simple as transferring the NFT (transferring ownership could also be accomplished by simply changing the stored public key in the account contract but just trying to understand whether this is feasible). Is this right ? or have I misunderstood this concept

3 Likes

I guess you could do something like that.
But do you see here a problem with the validate function limited in steps?

3 Likes

No problem with limiting validation steps, infact I think having this constraint is actually a good decision. I went ahead and hacked a simple version of a token gated account here. I have another question though. How do you intend to collect the fees - like is the sequencer going to call some function in the Account contract to collect the fees (I am assuming its going to be an ERC20) ? I was thinking of an implementation of sponsored accounts and knowing the fee collection mechanism would help a lot.

2 Likes

What are the restrictions preventing nonce abstraction to be implemented at the account contract level: Nonce abstraction · Issue #354 · OpenZeppelin/cairo-contracts · GitHub? I think this would make certain transactions much more efficient in the current naive way that nonces are implemented in account contracts.

2 Likes

Not sure what you mean by restrictions.
It’s a design choice, to simplify things like guaranteeing transaction uniqueness.

3 Likes

Is it possible to use another token for payment after the alpha phase? Do you have such a goal in total?

2 Likes

That is one of the goals for the paymaster mechanism.
You would need to have a paymaster contract that supports this of course.

2 Likes

Hello,

I’ll make a case for nonce abstraction, or at least for the possibility to have more flexibility in nonce management.
Nonce management is hard when you need to send a large number of transactions from a single account, and you can’t multicall them.

  • At least four projects I know have faced this issue (the starknet Edu team, the Empiric team, the Rules team and the snapshot team). And in the Ethereum world it is a widespread problem 1 2 3.
  • If your backend has various processes that need to access the same ressources / wallet, it is quite hard to figure out which nonce to use. Using an incorrect nonce will get your transaction rejected, or stalled.
  • The option is basically “Have all your workload executed sequentially, or have multiple wallets”. But having more wallets, dealing with more keys and adding more permissions in your smart contracts are not necessarily a good thing.

I think nonce abstraction is very useful in the future, but even more so today

  • There is no notion of mempool, so if a transaction is waiting for inclusion but hasn’t been included yet, it is impossible to detect it
  • There is an implicit guarantee of ordering of transactions when I send them to the feeder, but any glitch on StarkWare’s end will mess up ordering and will invalidate all the transactions I sent. This will get worse with optimistic paralelization
  • A transaction with a incorrect nonce is not only bounced back, it is prohibited from being re sent again. Meaning that if I craft a batch of 1k txs, send them at once, and a glitch / error happens at tx 5, all 995 remaining transactions will be discarded AND I have to craft them again and change their payload.
  • This means that currently it is not safe to send more than 1 transaction per block using the same account. That’s little.

A relatively simple solution would be to have the nonce be a two dimensional object. Instead of using [nonce], the wallet/os would use [index, nonce] to check the unicity of a transaction.

  • The OS can still validate that for [index], [nonce] is sequentally incremented
  • It allows operators that need to fire a large number of transactions in paralel to assign indexes to queues, and deal with nonces separately
  • It comes at no cost for regular users. Most users will use index 0 and increment the same nonce, using no extra storage in their contract compared to using a single nonce
8 Likes

Thanks for posting this, Henri. I completely agree and want to continue the conversation by:

  1. adding a bit more color on why use nonces in general and which of those properties might be relaxed
  2. describing our use case
  3. describing a different potential solution (not mutually exclusive).

Why use nonces?

As I think about it, there are two reasons to use nonces: A. they prevent replay attacks, such that resending a payload that has already been sent will not result in a valid transaction. B. They guarantee ordering and completeness of transactions, i.e. sometimes we want to make sure that a second transaction we send can only be accepted if the previous transaction has already been included.

Our use case (at Empiric)

In our case at Empiric (oracle data feeds), we only need property A. but not property B. At Empiric, we have many data publishers that sign their own data and then publish it directly on-chain. This data is published at a high frequency and by many different entities each running on distributed, highly redundant systems.

We need the replay attack guarantee, because otherwise resending past valid data update transactions could lead to draining the funds from our data partners via recurring gas fees.

We do not however need the ordering and completeness guarantees, in fact we actively don’t want them. As Henri describes, it is difficult to ascertain the correct nonce to use given potentially pending transactions and the possibility that transactions sent a few seconds ago may or may not be valid. For instance, a transaction may seem valid locally, but fail because of insufficient gas if the fee changes from the estimate_fee call to posting the transaction (this has happened multiple times). Older data is automatically excluded by logic in our contracts, so we are not worried about old transactions being resent.

Potential suggestion

We currently use timestamps as nonces and simply check that the last stored nonce is less than the nonce of the new transaction being validated. This guarantees transaction uniqueness but allows many transactions to be sent simultaneously and only the most recent transaction will be included.

If I understand the proposed nonce validation by the sequencer properly, checking inequality rather than old_nonce = nonce + 1 would have identical complexity, and the former (proposed here) is strictly more flexible. Contracts that wanted the ordering and completeness guarantee could still check it (similar to the way account contracts check both that and uniqueness today).

PS: Henri’s multi-dimensional nonce structure would also work in theory, in that we could just use index as a timestamp and ignore the second dimension of the nonce. However it would be suboptimal in that we wouldn’t store one timestamp nonce but rather add a new storage slot at every update, which would be quite expensive over the long run.

2 Likes

I like the timestamp solution a lot, but how do you ensure the timestamp sent by the user is correct?
What if “by mistake” the users sends a timestamp 2h in the future, does that mean that then his account is “blocked” for two hours?
And if you rely on the get_block_timestamp existing in the library then it shouldn’t be used since (at the moment) it can be (on purpose?) changed by the sequencer.
Or you just assume the user is sending the correct timestamp?

4 Likes

You are correct in that currently we do not have any checks on the timestamp. For now we just assume the user sends the correct timestamp (we need this assumption for the oracle anyway as all data our partners send is timestamped itself, regardless of transaction validation), with two caveats:

First: If a user sent a timestamp 2 hours in the future (not an unlikely scenario given timezones etc), the account would in practice be blocked but in theory you could just move to using timestamp + 2 hours as the nonce and keep on (in practice blocked because SDKs and wallets might not make this easy to do for most users without going to manipulating raw transactions).

Second: My understanding is that (quoting @Ohad-StarkWare): “when StarkNet is decentralized, timestamps in the frequency of seconds will be enforced at the L2-consensus level”. This was from a conversation 1.5 months ago, would be curious to know if this is this still the plan?

3 Likes

Hi all,

We worked on some schemes to help improve the “nonce” approach:

It involved two protocols:

Multi Nonce = It required two nonces and created a mapping index → nonce. It allows you to define a set of queues and enforce sequential ordering for each queue. It is handy if you want to maintain some ordering, but still support concurrent transactions.

Bitflip = It required a two nonces. Again it is an index → nonce approach, but the goal is to “flip the bits” in the nonce. So you can send X concurrent transactions per queue and require minimal storage updates.

I’d recommend, if possible, to abstract away the nonce concept to allow people to experiment with different approaches. You could implement a basic “sequential nonce” that is plug and playable, but allow others to implement different schemes (like the above) to really benefit from it.

4 Likes

Another approach to nonce abstraction might be to have the system maintain, per (account) contract, the last T nonces accepted (call it LastNonces)

Then, when a transaction is validated, we assert that the nonce in the transaction is higher than the minimum of LastNonces.
Of course, a successful transaction execution will update LastNonces, so it’s always at most T nonces long.

So now we can send several transactions, at most T, to be accepted in parallel.

The size of LastNonces, i.e. value of T, can be decided per account.
And we can even have API in the account contract to allow the owner of the account to change it (with some built-in limitation for safety), allowing for more transactions to be executed in parallel.

This is a bit less robust than the structured nonce approach (2 numbers). For example, I can’t group transactions into different groups.
On the other hand, it’s simpler, and keeps the transaction API the same.

thoughts?

1 Like