# Introduction to the Keystore Rollup

At the intersection of scaling and account abstraction efforts on Ethereum, two of [The Three Transitions](https://vitalik.eth.limo/general/2023/06/09/three_transitions.html), the Keystore Rollup may become crucial infrastructure to support global-scale Ethereum. Recently, Vitalik’s original proposal for a [minimal rollup dedicated for keystores](https://notes.ethereum.org/@vbuterin/minimal_keystore_rollup) has been iterated on by Base with a more formal [specification](https://hackmd.io/@mdehoog/mksr). While the existing writing is detailed, I want to provide an introduction for those less familiar with the cryptography at play. This post is an attempt to introduce the idea and fundamental logical blocks of a Keystore Rollup without involving the underlying cutting-edge cryptography required to implement it.

## What does a Keystore Rollup solve?

First, a primer on the current state of using Etheruem. Motivated by the need to reduce transaction costs, rollups have started to become default locations to deploy new dApps. Unfortunately, this has introduced new friction in users first having to bridge ETH over into the rollup to pay for transaction on the network. Account abstraction, specifically [EIP-4337](https://eips.ethereum.org/EIPS/eip-4337)’s implementation, is poised to help solve this problem by providing new ways for users to pay for gas with less friction, potentially receiving complete subsidies too. As the number of rollup options accelerates (aided by patterns like Modular DA and L3s), smart contract accounts must continue to deploy on every new network a user wants to transact on.

Our root problem starts with the isolation of a rollups state with other rollups. Specifically, the state that accounts need to authenticate user operations e.g. an owner key. The ability for smart contract accounts to hold state empowers functionality like key rotation and recovery, but also comes with a complication of syncing state updates across all networks.

In the diagram below, consider our user just added a passkey on their phone to control an account while on the go. The change was applied on the Optimism network, but not on Base or Scroll.


**If a user has a smart contract account on many networks and wants to change their permissions, how do the changes apply everywhere securely and cheaply?**

## Existing solutions

The current approach to remedy this is to propagate the same state changes to all chains. If a user changes state on any network, the wallet provider takes responsibility for making the same change to all other networks (hopefully giving the user a way to sign only one approval that can be reused once per-network).


While initially satisfactory, this propagation process runs into a handful of problems.

First is a complexity problem. Because the user shouldn’t be burdened by keeping track of permissions across networks, the developers need to build out a way to submit these transactions, manage pending state logic, handle fallbacks of failed submissions, and more. While the user does not incur this cost directly, they do in the form of less developer teams supporting such a feature and opportunity cost on other improvements.

Second is a cost problem. Should an account provider submit transactions on all networks for the user, each transaction incurs a fee. If rollups provide 10-100x cost savings compared to Ethereum, but a permission change needs propagation to 10-100 networks, we haven’t really saved anything on fees. To get around this, providers only submit permission changes on an as-needed basis when the user makes their next transaction on a network. This remedies cost in the near term while rollup adoption is still in infancy, but will run into the same problem if we have a future of 10-100s of rollups that users engage with. This optimization also adds more to our first problem of developer complexity.

Third is a security problem. Submitting permission updates on an as-needed basis is secure when adding new permissions like in our mobile passkey example, but what happens if a key becomes leaked and needs to be removed? Permission revoking changes like these leave a user vulnerable if left unapplied on networks. Even if permission revoking was applied immediately, it still would require the account provider team to be diligent about eagerly applying changes on unknown networks to be released in the future. Accounting for networks that do not yet exist also feeds back into the complexity and cost problems.

Consider the example below of an account rotating the original controlling key on Base network, but Optimism and Scroll are left unchanged.


Fundamentally, this approach is flawed because a user-initiated permission change scales differently than applying updates on the networks they use (1 change, N networks). Existing adjustments and optimizations are just bandaids around this mismatch.

## Keystore Rollup

In anticipation of an increasingly multi-chain user experience, the future of account permissions is to colocate account state on one network, the Keystore Rollup. All accounts, regardless of what other networks they need to transact on, refer to the Keystore Rollup to authenticate users. Instead of storing mutable permissions in the account smart contract, an immutable link to a “virtual account” id is stored which contains the actual permission data on the Keystore Rollup.


By concentrating state in one place, changing this source of truth can automatically reflect on all other networks. Complexity is reduced by removing the need to manage state across multiple networks and propagate duplicate transactions to make permission changes. Cost is reduced by removing these duplicated transaction fees. Security is improved by guaranteeing immediate application of removed permissions and removing data availability assumptions of offchain permission change requests.

This is not without new problems though, the first of which is overcoming state isolation between rollups mentioned earlier.

**How do we use the Keystore Rollup’s state in other rollups?**

### Execute a User Operation

This is where our magic cryptography comes in to play with zero-knowledge proofs. This section will intentionally omit implementation details while trying to preserve the intuition of the different components of the verification process. Consider the concrete example of executing a user operation on an L2, requiring a verification process using the Keystore Rollup.

At a high level, we need to verify 4 things when executing a user operation:

1. The user operation is signed by a key or set of keys
2. The key or keys are valid for the virtual account
3. The virtual account’s state is validated by Ethereum
4. The virtual account controls our account smart contract

#### Verify signing keys

Just like a normal smart contract account, a user operation is converted into a message hash (defined in EIP-4337) and this hash is signed by a private key, yielding a signature. Multiple private key and signing methods are supported, for example a normal Ethereum wallet using the secp256k1 elliptic curve or a Webauthn Passkey using the secp256r1 elliptic curve. Using elliptic curve cryptography, the public signature and message hash can be used together to recover the public key that was used to sign. Therefore, given a user operation and a signature, we can verify the public key(s) that signed it.

#### Verify keys on virtual account

Verifying a key or keys control a virtual account can be done with two approaches dubbed “inclusion” and “exclusion”.

Inclusion is when a virtual account’s state is non-empty and we compare the keys' membership in it. Being agnostic to the schema and location of this state, consider it like a mapping from a virtual account id to a bytes array. For a simple example of a single key that owns an account, just directly compare the key extracted from our user operation signature against the stored value. For verifying a set of keys, for example one user-owned and one service-owned for a dual-factor authentication, compare that both keys exist in the bytes array. Different teams making their account implementations can choose how they want to organize this stored data for their verification product features.

Note that this approach relies on state existing in the Keystore Rollup for the virtual account. While a valid way to use the system, we also want to support verification for virtual accounts without writing *any* state to its mapping to start with. We want this for full compatibility with EIP-4337’s goals for [first-time account creation](https://eips.ethereum.org/EIPS/eip-4337#first-time-account-creation):

> It is an important design goal of this proposal to replicate the key property of EOAs that users do not need to perform some custom action or rely on an existing user to create their wallet; they can simply generate an address locally and immediately start accepting funds.
>

To achieve this, we need to support verifying without a new transaction, therefore without any state for that virtual account in the Keystore Rollup.

Exclusion — verifying a key or keys control a virtual account that *does not* have any state attached to it — is performed through intentional construction of the virtual account id. Simply by hashing the intended initial state of a virtual account, we can generate an identifier that is effectively guaranteed to correspond with the initial state. If one were to change the initial state, the hash output would change, thereby representing a different account. Our verification process is then show (1) the virtual account state is empty and (2) our key is contained in an initial state that generates the virtual account id. The ability to verify virtual account state without storing it explicitly implies we only need to add an account to the Keystore Rollup when we first update the state, i.e. the first key addition or rotation. This reduces the cost to start using the Keystore Rollup because no initialization transaction is needed.

Sample pseudo-code for validating an account's single owner key:

state[account] == key || // inclusion condition
state[account] == bytes("") && account == hash(key) // exclusion condition

#### Verify virtual account on Ethereum

Verifying this virtual account’s state, empty or not, is validated on Ethereum involves deeper understanding of how blockchain state is structured with [merkle trees](https://brilliant.org/wiki/merkle-tree/) and rollup architecture. Vitalik’s deep dive into the [proof scheme options](https://vitalik.eth.limo/general/2023/06/20/deeperdive.html#what-kinds-of-proof-schemes-can-we-use) for this step is recommended for those wanting more details. As a simple explanation, we will continue with a merkle tree model and intuit other proof options as black boxes of essentially proving the same relationships with different methods.

All of Ethereum’s state can be represented as one massive merkle tree, the root and branches of which can be used to prove any state on Ethereum. One subset of Ethereum’s state belongs to our Keystore Rollup smart contract that stores merkle roots of the rollup. Contained in the Keystore Rollup root, we have our Keystore smart contract that stores a merkle tree containing all virtual account state. To prove a given virtual account state is in Ethereum requires (1) proving that state’s inclusion or exclusion in the Keystore contract root, (2) proving the Keystore contract’s root is included in the Keystore Rollup’s root, and (3) proving the Keystore Rollup’s root is included in Ethereum’s root.


**With a claim of Ethereum’s root, how does the rollup we are executing the user operation on verify if this root is correct or not?**

Again, Vitalik’s deep dive into [accessing the recent Ethereum state root](https://vitalik.eth.limo/general/2023/06/20/deeperdive.html#how-does-l2-learn-the-recent-ethereum-state-root) will provide more complete details.

While currently in [Optimism’s R&D](https://github.com/ethereum-optimism/ecosystem-contributions/issues/76), the easiest option for L2 smart contract developers would be to access the state root directly in Solidity as a new keyword of sorts, enabling a direct comparison with our proof’s claimed root.

Without this convenience, the default approach leverages existing deposit/messaging features of rollup stacks to push the new Ethereum root via a bridge periodically. This requires submitting a new transaction on Ethereum, picked up by an indexer and forwarded with a new L2 transaction. While functional, this approach requires frequent updates, meaning frequent expensive L1 transactions.


A potential improvement to this approach is to leverage a tool like [Proof of Consensus](https://blog.succinct.xyz/proof-of-consensus/). By using zero-knowledge proofs, we can substitute the L1 message transactions with an offchain proving layer. Rollups host [Light Client](https://ethereum.org/en/developers/docs/nodes-and-clients/light-clients/) smart contracts that verify these proofs and update the latest Ethereum root. In doing so, only one transaction is needed on the L2, removing the expensive origin transaction on L1 in the message bridge pattern.


#### Verify virtual account on deployed account

Given our construction of accounts using the Keystore Rollup, accounts are tied a virtual account id immutably, for example by a constructor argument storing an immutable variable. If we need to check a virtual account controls our smart contract account, we just compare the input value with our stored value.

### Update Keystore Rollup state

Updating account state is fortunately much simpler, because we both validate and apply the request in the same execution environment. Effectively, we only concern ourselves with the first two steps of the user operation verification process:

1. The user operation is signed by a key or set of keys
2. The key or keys are valid for the virtual account

The first step involves parsing the signing keys from the signature and hash of the request. The second step involves proving via inclusion (non-empty state comparison) or exclusion (empty state, hash comparison). If both steps pass, our user is able to update their virtual account’s permissions.

Updating permissions on a virtual account will alter the state root of the Keystore smart contract, thereby altering the Keystore Rollup root, and finally altering Ethereum's root. This nullifies any future attempts to submit user operations with an invalid account state, guaranteeing that our new permissions apply on all networks.

### Other Considerations

The exact rollup construction will be influenced by optimizing along the same complexity, cost, and security dimensions mentioned before in addition to others. To prompt a few questions:

- How will sequencers and provers be selected and incentivized?
- How will the rollup be censorship resistant?
- How can the rollup extend to support privacy via [stealth addresses](https://vitalik.eth.limo/general/2023/01/20/stealth.html)?