# Keystore Design

## Introduction

Though smart contract wallet offers many flexibity and possibility to manage wallets, the current AA wallet implementation faces a few UX issues that prevent it from mass adoption.

- Currently AA wallets have different addresses on different chains. So users cannot receive any fund before they deploy their wallets on a new chain, or otherwise they will potentially lose the fund.
- With the trend of more L2s, it becomes harder for users and wallets to maintain the signing keys across all chains.

To solve these two issues, we propose to a keystore-centric AA wallet design. The goals of the keystore include:

- Users can have the same AA wallet address across all EVM-compatible chains using the keystore and be able to bind AA wallets with different addresses for non-EVM-compatible chains
- The keystore should be generic that can be compatible to different AA wallet implementations.
- The keystore should be minimal that doesn’t incur much overhead and cost
- The solution can be integrated with Ethereum and L2s
- The design should provide a cheap way to update keys in the keystore.

## Design Overview

In essence, the keystore is a database that stores users' signing keys to their smart contract wallets. Ethereum and L2 chains all need the read access to it in order to deploy AA wallets, while some chains have the write access to update the keys. The design of the keystore comes to the following questions.

1. Where to keep the keystore storage?
- We argue that the keystore contract should be deployed on Ethereum. It’s the easiest way for L2s to read the keystore since all L2s already have the access to Ethereum via RPC providers or running a L1 client. The latency for L2s to sync the keystore is shorter than having keystore on any L2. If the keystore is kept on any L2 (even a minimal keystore L2), the sync latency and liveness highly depends on the finality of that L2, making the UX worse for other L2s and Ethereum.
2. Who has the permission to update keys in the keystore?
- Every user should own their signing keys in the keystore. Because we want to make the keystore minimal and be compatible with different AA wallets, the keystore should not bind to any particular key verification implementation. Given that AA wallet has the authentication logic, naturely we should rely on the AA wallet to verify user identity and update the keys in the keystore.
3. How to make the key update cheaper?
- Since we keep the keystore contract on Ethereum while we still want to have a cheap way to update keys, we want to allow users to give the permission to one L2 for key updates in parallel with the key updates on Ethereum. The reason to only allow one L2 to be the key-update chain is to avoid the data racing between L2s. Once the L2 state is finalized on Ethereum, the key updates submitted on L2 can be materialized at the keystore contract on Ethereum. Ideally the key-update L2 should be a zk-Rollup so that the latency to finalize the key updates can be minimal.

The following figure shows an overview of the keystore architecture.


A few things to note in this design:
- `L1Keystore` is the main storage that holds the user signing keys. `L2Keystore` is a proxy of the `L1Keystore` that allows wallets on L2s to read the keys.
- L2s need to have a system contract that holds the L1 blockhashes and state roots. `L2Keystore` will use [`L1Blocks` contract](#L1Blocks-system-contract) and the [`l1Sload` precompile](#l1Sload-precompile) to load the keys from `L1Keystore`.
- For EVM-compatible chains, we utilize `CREATE3`(see more details [here](#CREATE3)) to derive the same account address across all EVM-compatible chains. We first deploy a universal `AccountFactory` contract to the same address across on all chains. Then the `AccountFactory` contract is used to deploy all user wallet contracts via `CREATE3`. More details will be describe in the [`AccountFactory` contract](#AccountFactory-contract) section. Note that in the figure the `User Wallet` and `AccountFactory` in the "L2 Chain A (EVM compatible)" have the same addresses as the ones on Ethereum.
- For non-EVM-compatible chains, the keystore provides an interface that allows users to bind different addresses to their accounts.

## Contracts
<!--
### Pre-requisites

- Deploy the `CREATE3Factory` contract to the same address across all EVM-compatible chains.
- Use `CREATE3Factory` contract to deploy the `AccountFactory` contract to a deterministic address across all EVM-compatible chains.
- L2s need to provide a contract that allows smart contract to read the latest Ethereum state root with a reasonable delay.
-->

### **`L1Keystore` contract**

// L1 keystore contract
contract L1Keystore {
  struct WalletEntry {
    address owner;
    // mapping from chain id to implementation address
    mapping(uint64 => address) implementations;
  }
    
  struct UserAccount {
    // key-value map storage
    mapping(bytes32 => bytes32) keys;
    // mapping from chain id to the deployed contract address, only needed for non-EVM compatible chain
    mapping(uint64 => bytes32) bindings;
    // a L2 rollup contract that can update this account
    // address l2KeyUpdate;
  }
  
  // The universal address of AccountFactory contract
  immutable address accountFactory;
  // The wallet registry contract
  immutable address walletRegistry
  
  // Reserved keys
  uint256 constant _SALT_KEY = xx;
  uint256 constant _WALLET_ID_KEY = yy;
  uint256 constant _INITDATA_HASH_KEY = zz;
  uint256 constant _L2_UPDATE_ADDRESS = ww;

  // mapping from AA wallet addr to user account storage
  mapping(address => UserAccount) accounts;
  // mapping from wallet id to wallet registration entry
  mapping(bytes32 => WalletEntry) walletRegistry;
  
  modifier canWrite(address account) {
    require (msg.caller == account || msg.caller == accounts[account].keys[_L2_UPDATE_ADDRESS]);
  }

  function registerAccount(
      bytes32 salt, 
      bytes32 walletId,
      bytes32[] initKeys,
      bytes32[] initValues,
      bytes memory initdata, 
      address l2Rollup
  ) returns address {
    // validate inputs
    require(salt != 0, "invalid salt");
    require(initKeys.len() == initValues.len());
    require(walletRegistry[walletId].owner != 0, "wallet is not registered");
    
    address addr = CREATE3.getDeployed(salt, accountFactory);
    require(accounts[addr].keys[_SALT_KEY] == 0, "account already existed");
    // Write the special keys
    accounts[addr].keys[_SALT_KEY] = salt;
    accounts[addr].keys[_WALLET_ID_KEY] = walletId;
    accounts[addr].keys[_INITDATA_HASH_KEY] = keccak256(initdata);
    // Write the initial keys
    for (int i = 0; i < initKeys.len(); i++) {
      accounts[addr].keys[initKeys[i]] = initValues[i];
    }
    // If specified, allow a L2 chain to update the keys for this account
    if (l2Rollup != 0) {
      accounts[addr].keys[_L2_UPDATE_ADDRESS] = l2Rollup;
    }
    return addr;
  }

  function loadKey(address account, bytes32 key) returns bytes32 {
    return accounts[account].keys[key];
  }
  
  function writeKey(address account, bytes32 key, bytes32 value) canWrite(account) {  
    require(accounts[account].keys[key] == 0);
    accounts[account].keys[key] = value;
  }

  function updateKey(address account, uint256 key, uint256 oldValue, uint256 newValue) canWrite(account) {
    require(key != _SALT_KEY, "salt cannot be updated");
    require(accounts[account].keys[key] == oldValue);
    accounts[account].keys[key] = newValue;
  }
  
  function updateAccess(address account, address oldUpdateContract, address newUpdateContract) canWrite(account) {
    updateKey(address, _L2_UPDATE_ADDRESS, oldUpdateContract, newUpdateContract);
  }
  
  function getWalletImplementation(address account) returns address {
    bytes32 walletId = accounts[account].keys[_WALLET_ID_KEY];
    assembly {
      let chainId := chainid();
    }
    address impl = walletRegistry[walletId].implementations[chainId];
    require(impl != 0, "implementation is not registered");
    return impl;
  }
    
  function bindAddress(address account, uint64 chainId, bytes32 address) canWrite(account) {
    accounts[account].bindings[chainId] = address;
  }
}

The `L1Keystore` contract is mainly a storage layer that serves as the single source of truth for all user keys. Note that this contract stores the key mappings for all users from different AA wallets. It doesn’t add any constraints to data format and layout. The interpretation of the keys stored in the contract is up to the AA wallet implementation.

More specifically, it stores the following data fields:

- `keyStorage`: a mapping from user account address to its own key store entry. The user wallet contract will read the keys from the keystore contract to verify user identity. There are 3 reserved keys in every user’s key store entry.
- `_SALT_KEY`: stores the salt value that determines the user account address. This value is read-only and cannot be modified after the initial setup in order to achieve the same address on new chains in the future..
- `_WALLET_ID_KEY`: stores the wallet ID in the wallet registry that is used to load the wallet implementation address.
- `_INITDATA_HASH_KEY`: stores the Keccak digest of init data that is used to initialize the wallet contract.
<p>
The reason to store the wallet ID and initdata hash in the keystore is to prevent others from front-running the wallet deployment on a chain with (malicious) implementation contract address or initialization data to possess user account address on a new chain.
</p>
- `keyUpdateAccess`: a mapping from user account address to a L2 rollup contract that is allowed to update the keys for the user. This entry can be empty, meaning that the key can be only updated by the user wallet contract on Ethereum.
- `walletRegistry`: a mapping from wallet ID to the wallet registration entry. The entry contains a mapping from chain ID to the wallet implementation address. Each entry can be updated by `owner`, a AA wallet project controlled address.

The `L1Keystore` wallet provides the following functions:

- `registerAccount` is used to register a new account in the keystore and return the new address for this account. The following parameters need to be provided to this function:
- `salt`: a value used to decide the deterministic contract address for the user account.
- `walletID`: the wallet ID of the AA wallet implementation.
- `initKeys` and `initValues`: the initial signing keys and values to be stored in the user keystore. The `initKeys` specifies the location to store the `initValues` in the user keystore entry.
- `initdata`: the initdata to initialize the AA wallet implementation. It can be the metadata other than user signing keys that doesn't need to be stored in the keystore.
- `l2Rollup`: the L2 rollup contract address that can update the user keystore entry. If a user doesn't want to give the permission to any L2, she can just pass `0x0` to this parameter.
- `loadKey` loads the value given the user account and a key. This function can be called by everyone.
- `writeKey` and `updateKey` writes a new value and updates an existing value in the user keystore respectively. This function can be only called by the user wallet contract or a L2 rollup contract if specified. The `updateKey` function requires users to provide the old value to prevent the data racing.
- `updateAccess` updates the key-update contract access to the user account, only allowing user contract or the previous L2 rollup contract.
- `getWalletImplementation` returns the wallet implementation address based on the chain id.

### EVM-Compatible Chain

#### `L2Keystore` Contract

// L2 keystore contract
contract L2Keystore {
  immutable address l1Keystore;
  immutable address l2Messenger;
    
  uint256 constant _UPDATE_KEY_GAS_LIMIT = xx;
    
  modifier canWrite(address account) {
    require(msg.caller == account);
  }
  
  function registerAccount(
      bytes32 salt, 
      bytes32 walletId,
      bytes32[] initKeys,
      bytes32[] initValues,
      bytes memory initdata, 
      address l2Rollup
  ) returns address {
    revert("registerAccount is not supported on L2");
  }
  
  function loadKey(address account, bytes32 key) returns bytes32 {
    bytes32 slot = _computeKeySlot(account, key);
    // l1Sload is a new precompile that allows the smart contract to trustlessly read a storage slot from L1 state root without a merkle proof.
    return l1Sload(l1Keystore, slot);
  }

  function writeKey(address account, bytes32 key, bytes value) canWrite(account) {
    require(loadKey(account, key) == 0);
    bytes _message = abi.encodeCall(IKeystore.writeKey, (account, key, value));
    l2Messenger.sendMessage(l1Keystore, 0, _message, _WRITE_KEY_GAS_LIMIT);
    emit WriteKey(account, key, value);
  }
  
  function updateKey(address account, bytes32 key, bytes oldValue, bytes32 newValue) canWrite(account) {
    require(key != _SALT_SLOT);
    require(loadKey(account, key) == oldValue);
    bytes _message = abi.encodeCall(IKeystore.updateKey, (account, key, oldValue, newValue));
    l2Messenger.sendMessage(l1Keystore, 0, _message, _UPDATE_KEY_GAS_LIMIT);
    emit UpdateKey(account, key, oldValue, newValue);
  }
  
  function getWalletImplementation(address account) returns address {
    bytes32 walletId = keyStorage[account][_WALLET_ID_KEY];
    assembly {
      let chainID := chainid();
    }
    bytes32 slot = keccak256(walletId . chainId . _WALLET_REGISTRY_SLOT);
    address impl = address(l1Sload(l1Keystore, slot));
    require(impl != 0, "implementation is not registered");
    return impl;
  }

  function _computeKeySlot(address account, bytes32 key) internal view returns bytes32 {
    // ...
  }
}

The `L2Keystore` contract serves as a proxy of the L1 keystore contract. This contract relies on the L2 chain to provide access to L1 state root so that it can load the keys from the `L1Keystore` contract. The overall functions of `L2Keystore` are the same as the `L1Keystore` but with slight difference.
- `registerAccount` is not supported on L2s.
- `loadKey` uses the `l1Sload` precompile to load a storage slot using the current L1 state root stored on the L2. The `l1Sload` precompile provides a convenient way to access the L1 storages without providing Merkle proofs. This precompile will be proved by the zkEVM circuit.
- `writeKey` and `updateKey` will encode the key update to a message and send to the L2 bridge. After the L2 is finalized on the Ethereum, the message can be then executed to materialize the update. These two functions can only be called by the user account on L2s.

#### `AccountFactoryEvm` Contract

// deploy on all EVM-compatible chains
contract AccountFactoryEvm {
  immutable address keystore;
  uint256 constant _SALT_KEY = xx;
  uint256 constant _WALLET_ID_KEY = yy;
  uint256 constant _INITDATA_HASH_KEY = zz;

  function createAccount(address account, bytes memory initdata) {
    // get the salt from the account
    bytes32 salt = keystore.loadKey(account, _SALT_KEY);
    // verify the initdata is correct
    bytes32 initdataHash = loadKeystore(account, _INITDATA_HASH_KEY);
    require(keccak256(initdata) == initdataHash);
    // get the wallet implementation address
    bytes32 walletId = keystore.loadKey(account, _WALLET_ID_KEY);
    address impl = keystore.getWalletImplementation(walletId);
    
    // deploy the user account
    bytes memory creationCode = abi.encodePacked(
      type(ERC1967Proxy).creationCode,
      abi.encode(
        impl, 
        abi.encodeCall(
          IAccount.initialize,
          initdata
        )
      )
    );
    address proxy = CREATE3.deploy(salt, creationCode, msg.value);
    require(proxy == account);
  }
}

The `EvmAccountFactory` contract is deployed on all EVM-compatible chains. It should have the same address across all chains. It provides one single function `createAccount`. The function takes the `account` address and the contract initialize data `initdata` as input and then loads the `salt` and wallet contract implementation address from the L1 or L2 keystore contract to deploy the user contract. One thing to note is that the user account needs to pre-exist in the keystore before the contract being deployed.

### Non-EVM-Compatible Chain

#### `L2Keystore` Contract

// L2 keystore contract
contract L2Keystore {
  // for non-EVM compatible chain
  modifier canWrite(address account) {
    assembly {
      let _chainId := chainid();
    }
    bytes32 _bind = l1Sload(l1Keystore, _computeBindingSlot(account, _chainId));
    require(msg.caller == account || bytes32(msg.caller) == _bind);
  }
    
  function _computeBindingSlot(address account, uint64 chainId) internal view returns bytes32 {
    // ...
  }
}

The majority of the `L2Keystore` contract for non-EVM-compatible chains is the same as that for EVM-compatible chains. The only difference is that the write permission to user account now allows both the account address and the binded address specified on L1.

#### `AccountFactoryNonEvm` Contract

// deploy on all EVM-compatible chains
contract AccountFactoryNonEvm {
  immutable address keystore;
  uint256 constant _SALT_KEY = xx;
  uint256 constant _WALLET_ID_KEY = yy;
  uint256 constant _INITDATA_HASH_KEY = zz;

  function createAccount(address account, bytes memory initdata) returns address {
    // get the salt from the account
    bytes32 salt = keystore.loadKey(account, _SALT_KEY);
    // verify the initdata is correct
    bytes32 initdataHash = loadKeystore(account, _INITDATA_HASH_KEY);
    require(keccak256(initdata) == initdataHash);
    // get the wallet implementation address
    bytes32 walletId = keystore.loadKey(account, _WALLET_ID_KEY);
    address impl = keystore.getWalletImplementation(walletId);
    
    // deploy the user account
    address proxy = new ERC1967Proxy{salt: salt}(
      impl,
      abi.encodeCall(
        IAccount.initialize,
        // include the account addr in the keystore
        abi.encode(account, initdata)
      )
    );
    return address;
  }
}

## Workflow

### Account Creation

This figure outlines the account creation workflow.
1. AA wallet operator first registers the wallet implementation in the wallet registry to the `L1Keystore` contract.
2. Upon the user request, the AA wallet operator calls `registerAccount` to the `L1Keystore` contract to register a new user account with the init keys and other information.
3. (Optional) AA wallet operator calls `AccountFactory` on the Ethereum to deploy the user wallet contract.
4. L2 syncs the latest L1 state root that contains the new user registration to a L2 system contract.
5. AA wallet operator now calls `AccountFactory` contract on L2 to deploy the user wallet contract on L2.

### Key Update on L1


(will add description)

### Key Update on L2


(will add description)

## Wallet Example

contract FooEvmAccount is IAccount, UUPSUpgradeable, Initializable {
  /// The ERC-4337 entry point singleton
  IEntryPoint public immutable entryPoint;
  /// The keystore contract
  IKeystore public immutable keystore;
  /// Signature verifier contract
  Verifier public immutable verifier;
  
  constructor(IEntryPoint _entryPoint, IKeystore _keystore, Verifier _verifier) {
    entryPoint = _entryPoint;
    keystore = _keystore;
    verifier = _verifier;
    _disableInitializers();
  }
  
  function initialize() public virtual initializer {
  }
    
  function validateUserOp(
    UserOperation calldata userOp,
    bytes32 userOpHash,
    uint256 missingAccountFunds
  ) onlyEntryPoint returns (uint256 validationData) {
    bytes messageToVerify = _encodeMessage(userOp);
    if (_validateSignature(messageToVerify, userOp.signature)) {
      return _SIG_VALIDATION_SUCCEED;
    }
    return _SIG_VALIDATION_FAILED;
  }
    
  function _validateSignature(
    bytes memory message,
    bytes calldata signature
  ) private view returns (bool) {
    // First byte identifies the keySlot
    uint8 keySlot = uint8(signature[0]);

    // Load the signature from keystore
    uint256 x = uint256(keystore.loadKey(address(this), keccak256(keySlot, 0));
    uint256 y = uint256(keystore.loadKey(address(this), keccak256(keySlot, 1));

    return verifier.verifySignature(message, signature, x, y);
  }

## L2 Protocol Changes

### `L1Blocks` system contract

In this design, the `L2Keystore` contract on L2s needs to read the storage slots in the `L1Keystore` contract. This requires L2s to provide trustless L1 access to the contract.

In order to achieve this, we introduce a system contract `IL1Blocks` that provides interfaces to read L1 blockhashes and state roots. The `L1Blocks` contract should hold a ring buffer of `N` blockhashes and state roots where `N` can be decided by each L2.

interface IL1Blocks {    
    function latestBlockNumber() external view returns uint256;
    
    function l1Blockhash(uint256 number) external view returns bytes32;
    
    function latestL1Blockhash() external view returns bytes32;
    
    function l1Stateroot(uint256 number) external view returns bytes32;
    
    function latestL1Stateroot() external view returns bytes32;
}

This contract is read-only from externals and can be only updated by system transactions generated by L2 seqeuencers. To lift the trust of the honesty of L2 sequencers, the L2 proofs need to verify that the blockhashes and state roots in the system transactions are correct.
- For zkRollups, the blockhashes need to be exposed to the public inputs of validity proofs and then compare with the blockhashes read directly on L1. More details will be introduced in a separate doc.
- For opRollups, the fraud proof need to perform a similar check such that the blockhashes in the system transactions are the same as those read on Ethereum.

### `l1Sload` precompile

The `l1Sload` precompile allows smart contracts to read a L1 storage slots without providing Merkle proofs. This precompile is important such that AA wallets don't need to supply the Merkle proofs to read keys from `L2Keystore` contract. It not only reduces the overhead of AA wallets to construct a transaction but reduces the tx cost and tx calldata size.

The `l1Sload` returns the storage value against the latest state root in the `L1Blocks` contract given the contract address and storage key.

**Inputs**

| Stack | Name | Description |
|:-----:|:----:|:-----------:|
| Top - 0 | `address` | The contract address |
| Top - 1 | `key` | The storage key |

**Output**

| Stack | Name | Description |
|:-----:|:----:|:-----------:|
| Top - 0 | `value` | The storage value based on the latest state root in the `L1Blocks` |

The sequencer is responsible for providing the storage value given the latest state root in the `L1Blocks`. To prevent the sequencer from giving wrong values, the L2 proof system needs to construct a valid Merkle proof from the value to the state root stored in the `L1Blocks` contract.

## FAQ

## Appendix

### `CREATE3`

`CREATE3` can deploy a contract to a deterministic address. It first uses `CREATE2` with a fixed init code to deploy a proxy contract to a deterministic address, and then call the proxy contract to deploy the desired contract via `CREATE`.

The contract address deployed by `CREATE3` is computed as follows
- First, a proxy contract is deployed by the contract using `CREATE2`. The proxy address is

    proxy_addr = keccak256(0xff + deployer_address + salt + keccak256(PROXY_BYTECODE))[12:]

Because the `PROXY_BYTECODE` is fixed, the `proxy_addr` depends on the `salt` and `deployer_address`. Given that we can have the same `deployer_address`, the `proxy_addr` only depends on the `salt`.
- Then the actual contract is deployed by the proxy contract via `CREATE`. The contract address is

    deployed_addr = keccak256(rlp([proxy_addr, proxy_nonce]))

The `proxy_nonce` is 1 since the proxy contract is newly deployed. Therefore, the `deployed_addr` depends on the `proxy_addr`, which consequently depends only on the `salt`.

**Reference**
- `CREATE3` [contract](https://github.com/transmissions11/solmate/blob/main/src/utils/CREATE3.sol)
- `CREATE3Factory` [contract](https://github.com/ZeframLou/create3-factory/blob/main/src/CREATE3Factory.sol)