# Solidity Account Circuits

*Special thanks to Michael de Hoog for his review and feedback.*

Please read this [Introduction to the Keystore Rollup](https://hackmd.io/@ilikesymmetry/intro-keystore-rollup) for context if you are not familiar.

This work builds on the [Minimal Keystore Rollup specification](https://hackmd.io/@mdehoog/mksr), and seeks to improve the DevX for writing and auditing account authentication patterns.

Currently, implementing validation for Keystore updates requires writing zk circuits. However, the number of people who understand and can write zk circuits is small. This barrier to developers risks reduced adoption of the Keystore Rollup.

Additionally, these "Account Circuits" are not involved in validating signatures for user operations, just Keystore updates. This causes a divergence in account authentication where a Solidity contract and a zk circuit are responsible different halves of the same question: "can you control this account?". While enabling flexibility, a simpler and unified authentication option should exist for account developers.

To achieve this, I propose a circuit construction that enables developers to write simple Solidity libraries. The same library is used onchain for signature validation and offchain for proving keystore updates. This system fits within the existing specification with no required changes.

----

The problems stated above stem from the performance needs of the Keystore Rollup.

Because Keystore state needs to be proved on a per-user-operation basis, proofs will be requested as the user is trying to transact. In this environment, proving needs to be done *fast*. Ideally, less than a half-second including networking time to feel instantaneous to the user. To reach this performance, the circuit construction needs to be as efficient as possible without compromising on cheap onchain verification cost.

One efficiency tradeoff chosen is to only prove the state of an account, not its signature validation logic. By proving less, proving can be done faster. This minimal proof design means that signature validation needs to take place onchain in the account smart contract at execution-time.

When validating a user operation, the account recovers a signer from the signature and verifies this signer can represent it via a Keystore state proof. This state proof is done with an onchain zk verifier contract and is what connects the Keystore Rollup's state to this user operation's network.

Our intuition is to copy the same validation logic done in-contract for transactions to be used in-circuit for Keystore updates. This implies a bridge between computation done by the EVM and a zk circuit; essentially, we need a zkEVM.

However, zkEVMs are difficult to build and expensive to prove. We can remediate both of these by being stricter with our requirements for our Account Circuit.

Fortunately, we do not actually need to prove the entirety of the EVM. We don't need to use storage, call external contracts, or emit events. We just need to prove computation written in Solidity, leveraging the EVM's stack and a subset of opcodes. Solidity already has an abstraction catered to this need: libraries. Libraries can only support pure functions (no storage) and has built-in linting and compilation assistance for developers. Our approach is to write libraries to contain a signature validation process and leverage a single zk circuit to prove the result of these validations.

**What could this library look like?**

We only need to prove one computation, so only a single function interface is needed to determine if a signature is valid. We take inspiration from [EIP-1271](https://eips.ethereum.org/EIPS/eip-1271) and add an another argument to provide configuration to compare against the signer(s), enabling this function to be pure.

interface IValidatorLibrary {
    function isValidSignature(
        bytes32 hash, 
        bytes calldata signature, 
        bytes calldata config
    ) external pure returns (bool);
}

For example, a simple validation assuming a single owner would take in the owner's address as extra data. The library would be response for performing ECDSA recovery on the signature and comparing the signer to the provided owner.

import {ECDSA} from "@open-zeppelin/contracts/cryptography/ECDSA.sol";

library SingleOwnerValidator {
    function isValidSignature(
        bytes32 hash, 
        bytes calldata signature, 
        bytes calldata config
    ) external pure returns (bool) {
        address owner = abi.decode(config, (address));
        (address signer, ECDSA.RecoverError err, ) = ECDSA.tryRecover(hash, signature);
        return err == ECDSA.RecoverError.NoError && signer == owner;
    }
}

Note that the library’s only goal is to prove that this owner signed the hash. Proving that the account uses this library and owner is done by the Keystore. We just need validation libraries to know how to connect an account's Keystore data to a validation logic over message hashes and signatures.

### Circuit construction

An account's Keystore state has two parts:
1. A verification key for the Account Circuit
2. 256 bytes of data to be used by the Account Circuit

A verification key is generated from a circuit's construction and is independent from the inputs. If the circuit changes, so does the verification key. This enables us to verify which exact circuit an account uses. The verification key will be generated for us after completing our circuit construction.

We only need 64 bytes of data for our Solidity Account Circuit:
1. 32 bytes for a `codeHash`, a hash of a smart contract's bytecode
2. 32 bytes for a `configHash`, a hash of the configuration passed into the Validator Library

Therefore, the value stored in the Keystore Rollup for our account state is:

stateHash = hash(hash(SAC_VK), hash([codeHash, configHash]))

Note that `SAC_VK` stands for "Solidity Account Circuit verification key" and the actual implementation has more nuances around hash function selection and a slight transformation of our data array.

If we change the Validator Library being used for validation, the `codeHash` will change, therefore updating our account state value. If we change the configuration argument for the Validator Library (e.g. changing owners), the `configHash` will change, therefore updating our account state value. If an account no longer wants to use the Solidity Account Circuit, it can change the verification key to a different circuit, therefore updating our account state value.

For standardization, the existing specification requires Account Circuits to take two public inputs:
1. `currentData`, the currently used 256 bytes of logic-dependent data
2. `newStateHash`, the new state hash for the new verification key and data

We can customize the private inputs, for which we choose:
1. `bytecode`, the bytecode of our Validator Library
2. `signature`, signature bytes to recover signer(s) from
3. `config`, configuration bytes to compare signers with

Our circuit will prove:
- `bytecode` hashes to `codeHash`
- `config` hashes to `configHash`
- `codeHash` and `configHash` match `currentData`
- running `isValidSignature(newStateHash, signature, config)` on `bytecode` returns `true`

The actual implementation of this circuit is out of scope for now and needs more work. At a high level, it would be most convenient to start with a fork of an audited zkEVM implementation. We only need to keep the bytecode execution circuits and can strip out everything else. Even within execution, we can reduce clutter further by banning specific opcodes that are not needed in our context (e.g. `SLOAD`, `SSTORE`).

With a complete Account Circuit, we are able to fulfill the need of validating account state changes. Verifications of this proof will be composed with other circuits to prove individual transactions up to a final update to the Keystore's root. By constructing our circuit to compute a subset of the EVM, we are able to pass contract bytecode into our proofs and enable a Solidity-based developer experience.

**How do we apply this system to onchain user operation validation?**

### Onchain signature validation

Our second goal is to unify the validation process for both Keystore updates and user operations. Reusing the same library implementation gives us a direct path to do this.

A naive implementation would be to utilize the library directly in an account contract implementation. However, this integration is inflexible and risks diverging with the Keystore update validation. Within the Keystore, if an account's `codeHash` is changed, that means a new Validator Library should be used to validate user operations. Also, this kind of change is meant to apply to all networks immediately and automatically.

The solution is to leverage a method for deterministic contract deployment addresses.

Instead of writing a single Validator Library’s logic into our account, we write a general approach to determine its location and then call it externally. Our variable input is the library's `codeHash` and with it we need to map to an address. Leveraging the `CREATE2` opcode, we can do just this by using a "library factory" that can give us deterministic deployment addresses that depend on the contract's bytecode, a salt, and the factory's address. The salt should be a fixed standard agreed upon in the community (let's assume simply `0` for now). The factory address also needs to be consistent, for which we choose the [deterministic deployment proxy](https://github.com/Arachnid/deterministic-deployment-proxy/tree/master). It is a simple contract that deploys contracts using `CREATE2` and itself is deployed with ["Nick’s method"](https://yamenmerhi.medium.com/nicks-method-ethereum-keyless-execution-168a6659479c). This method enables anyone to permissionlessly deploy the deployment proxy to the same address, which itself lets anyone permissionlessly deploy contracts to the same across EVM networks. To determine a library's address, we pass in our dynamic `codeHash` with fixed `salt` and `deployer` values.

import {Create2} from "@open-zeppelin/contracts/utils/Create2.sol";

interface IValidatorLibrary() {
    function isValidSignature(bytes32 hash, bytes calldata signature, bytes calldata config) external pure returns (bool);
}

abstract contract LibraryValidation {
    internal constant SALT = 0;
    internal constant DETERMINISTIC_DEPLOYER = 0x4e59b44847b379578588920ca78fbf26c0b4956c;

    fuction _validateSignature(
        bytes32 codeHash,
        bytes32 hash, 
        bytes memory signature,
        bytes memory config
    ) internal pure returns (bool) {
        address lib = Create2.computeAddress(SALT, codeHash, DETERMINISTIC_DEPLOYER);
        return IValidatorLibrary(lib).isValidSignature(hash, signature, config);
    }
}

This sample abstract contract can be used by an account implementation to dynamically call a Validator Library given its `codeHash`. In this scheme, if the `codeHash` or `configHash` are updated in the Keystore, onchain validation will also update accordingly. Note that we still need to verify that a given `codeHash` or `config` are the valid state for an account.

### Onchain state verification

In addition to validating the user operation signature, we must also verify the claimed state of the account (library and config) in the Keystore. We do this by using an onchain SNARK verifier corresponding to the "State Circuit". Verifying Keystore Rollup state requires the Keystore `root`, `virtualAccount` id (recall construction from `originalStateHash` to support exclusion proofs), hash of account `data`, and `stateProof` bytes.

// below code forked from a draft implementation made at Base

import {Initializable} from "@openzeppelin-upgrades/packages/core/contracts/Initializable.sol";

interface IKeyStore {
    function root() external view returns (bytes32);
}

interface IVerifier {
    function verify(bytes calldata proof, uint256[] calldata publicInputs) external view returns (bool);
}

abstract contract StateVerification is Initializable {
    IKeyStore public immutable keyStore;
    IVerifier public immutable stateVerifier;
    uint256 public virtualAccount; // same as 'originalKey' in minimal keystore rollup spec
   
    constructor(address store, address verifier) {
        require(keyStore != address(0) && verifier != address(0));
        keyStore = IKeyStore(store);
        stateVerifier = IVerifier(verifier);
    }
    
    function initialize(bytes32 originalStateHash) external initializer {
        virtualAccount = uint256(originalStateHash);
    }
  
    function _verifyState(bytes32 codeHash, bytes32 configHash, bytes memory stateProof) internal view {
        uint256[] memory data = new uint256[](8);
        state[0] = codeHash;
        state[1] = configHash

        uint256[] memory publicInputs = new uint256[](3);
        publicInputs[0] = virtualAccount;
        publicInputs[1] = uint256(keyStore.root());
        publicInputs[2] = uint256(keccak256(abi.encodePacked(data)) >> 8);
        require(stateVerifier.verify(stateProof, publicInputs));
    }
}

This sample abstract contract can be used by an account implementation to call a State Verifier contract to verify `codeHash` and `configHash` values for an account.

### Complete onchain authentication

Combining both signature validation and state verification, we can complete account authentication. Here is a sample of using both abstract contracts together in an account implementatio for user operations.

import "@account-abstraction/core/BaseAccount.sol";

contract KeyStoreAccount is BaseAccount, LibraryValidation, StateVerification {
	constructor(address keyStore, address stateVerifier) StateVerification(keyStore, stateVerifier) {}
    
    function _validateSignature(
        UserOperation calldata userOp, 
        bytes32 userOpHash
    ) internal override returns (uint256 validationData) {
        (bytes32 codeHash, bytes memory signature, bytes memory config, bytes memory stateProof) =
            abi.decode(userOp.signature, (bytes32, bytes, bytes, bytes));
        bytes32 hash = userOpHash.toEthSignedMessageHash();

        if (!_validateSignature(codeHash, hash, signature, config)) {
            return SIG_VALIDATION_FAILED;
        }

        _verifyState(codeHash, keccak256(config), stateProof);

        return 0;
    }
}

### Complete developer experience

The end-to-end experience as an account developer wanting to utilize the Keystore Rollup follows:
- First write or choose a base account implementation
- Write a Validator Library, requiring a single `isValidSignature(bytes32,bytes,bytes)` function
- Deploy the library using the deterministic deploy proxy on all networks of interest
- Note that Foundry supports this natively with `new Contract{salt: SALT}()` syntax in scripts
- Update the base account implementation to use the `LibraryValidation` and `StateVerification` abstract contracts
- Combine the the `codeHash`, `signature`, `config`, and `stateProof` all within the user operation's single `signature` field when submitting to a bundler

In just a few simple steps that stick to common tools, we are able to empower all Solidity developers to write their own unique account validation that is compatible with the Keystore Rollup. By doing so, we maximize the opportunity for the Keystore Rollup to gain developer adoption and accellerate a transition to better multi-chain UX.

We also provide a simpler starting point for account developers to build securely by synchronizing validation logic across Keystore updates and user operations. This keeps developers at ease and users more protected while experimenting with the new potential of the Keystore Rollup.

### Topics needing expansion

The largest uncertainty of this system is in actually implementing the reduced EVM for our Solidity Account Circuit logic. As mentioned earlier, zkEVMs are hard and this is expected to be the most effort-intensive part. While this circuit only needs to be proved for making keystore updates, it is still important for it to be efficient and not bloat the proving time for new rollup blocks. Future work is needed to prototype a functional circuit, profile proving times, and optimize if needed to not hinder rollup validity proofs.

The performance of zk provers is improving rapidly and proving times should continue to decrease. Our original assumptions that minimal circuits are needed to reach performance targets may not be true in the near future. With more relaxed performance constraints, it is possible that we could compose the Account and State Circuit proofs together and still prove within 1 second. Doing so would resolve the issue of diverging validation for user operations and Keystore updates. Reusing the same circuit would resolve this problem for all circuit constructions (not just our Solidity one) and remove the need for our `CREATE2` deployment system for libraries, another win for DevX. Regardless, the existence of a Solidity Account Circuit would still provide the benefits of writing validation logic in Solidity.

This investigation also motivates a standard RPC for Keystore Rollup nodes. When preparing user operations, we both need a way to request generation of state proofs and in the context of the Solidity Account Circuit, a simple way to prepare private inputs like fetching bytecode from a deployed library. Future work is needed to write an initial specification for relevant RPCs and this new node role's interaction with bundlers and paymasters.