# naive interpretation of sequence v2

## what problem does lazy octopus (v1.5) solve?

Signing into Sequence currently requires a transaction to be mined on a blockchain, specifically the auth chain, Polygon. We do this because we use it as a low-cost, super reliable data availability layer for recovering wallet configs from image hashes.

The goals of lazy octopus (v1.5) are:
1. Reduce the time needed to sign a user into Sequence. The time needed to mine the auth chain transaction is the biggest factor to sign-in time.
2. Reduce our own costs because Horizon currently pays for the user's on-chain config updates on Polygon.

Lazy octopus abstracts away the choice of data availability layer. It does this by adding the following features:
1. Wallet config approval signatures that approve a new wallet config as being valid, e.g. a signature signed by config A that changes the valid config to config B (side note: in the sequence.js codebase, these are referred to as "presigned configs")
2. Chained signatures that allow us to concatenate together valid signatures for different wallet configs to produce new valid signatures

In other words, signatures now validate transitively. If a user has:
1. A signature signed by config A that approves config B
2. A signature signed by config B that approves config C

Then concatenating (1) and (2) together yields a signature by config A that approves config C (implementation detail: the actual concatenation happens in reverse order, newest signatures first, (2) then (1)).

This generalizes further. Suppose a wallet has on-chain config X, but the owner doesn't have sufficient signing power for X. However, if they have sufficient signing power for a counterfactual off-chain config Y, then they can still create valid on-chain signatures using Y as long as they still possess a sequence of signatures starting from X that eventually approves config Y, e.g.:

1. A signature signed by current on-chain config X that approves counterfactual config A
2. A signature signed by counterfactual config A that approves counterfactual config B
3. A signature signed by counterfactual config B that approves counterfactual config C
4. A signature signed by counterfactual config C that approves counterfactual config Y
5. A signature signed by counterfactual config Y that signs a transaction bundle that updates the wallet's image hash to config Y's image hash and sends 100 USDC to Bob

## what new challenges does this introduce?

If a user cannot sign for any counterfactual config reachable from their wallet's current on-chain config X, including X itself, then they have lost all access to their wallet. This can happen if they suffer a data loss where critical approval signatures are lost, or they lose their keys for every counterfactual wallet config state reachable from config X.

The choice of data availability provider(s) is the weakest link in the system. The wallet inherits the performance and reliability characteristics of the availability provider(s) that are chosen. In the worst case, a poor choice of data availability provider will lead to users being permanently locked out of their wallets. A poor choice of provider in the best case results in a system of similar performance and reliability to Sequence v1 in production today.

## what problems does sequence sessions (or config tracker implementations) solve?

Sequence sessions (and config trackers more generally) is one of multiple potential backup redundancy solutions for the event that a user's device suffers from a data loss incident. Abstractly, it is a key-value store that holds verfiably valid data and fulfills reverse lookup requests for digest preimages.

It can:
1. Retrieve the wallet config for an image hash, which will no longer be stored on an auth chain
2. Recover the aforementioned wallet config approval signatures needed for a user to sign data using a counterfactual off-chain wallet config
3. Recover the initial wallet config that a wallet was deployed with
4. Verifiably identify all wallets that a particular signer has ever signed a message for
5. Recover migration transactions needed to upgrade a wallet to a new version

It validates incoming data and decomposes it into different types of primitive objects:
1. Wallet configs, indexed by config image hash
2. Wallet config subtrees, indexed by subtree image hash
3. Deployed wallet configs, indexed by wallet address
4. Message digests, indexed by subdigest
5. Signer signatures, indexed by signer-subdigest
6. Migration transactions, indexed by wallet address, chain ID, starting version, and starting image hash

## what problems does v2 solve?

v1 wallet configs are structured as linear lists of signer-weight pairs where all signers need to be included in a signature even if they don't contribute signing power. In pathological cases, these signatures become expensive in terms of calldata and signature validation costs.

v2 introduces substantial changes:
1. Instead of structuring wallet configs as lists, they're structured as Merkle trees
2. Signatures can optionally be chain-agnostic, meaning they can be replayed on any chain
3. Signatures can have nested threshold signatures
4. Signatures can validate independently from a wallet's current on-chain config

Re-structuring wallet configs as Merkle trees allows signatures to be greatly optimized by pruning large signature subtrees that don't contribute signing power, and replacing them with functionally equivalent Merkle hash nodes.

Chain-agnostic signatures allow users to sign wallet config approvals that will validate on any chain, enabling chain-agnostic counterfactual wallet configs. Without this ability, the user would have to create distinct signatures for every wallet config approval and for every chain, including new chains not yet known.

Nested threshold signatures allow for logically organized subsets of signers to be limited in their collective signing power. An example usage is limiting the power of external wallet recovery providers, e.g. in the following config with threshold 2:
1. User signer A (weight=1)
2. User signer B (weight=1)
3. Nested group (weight=1, threshold=2)
a. External signer C (weight=1)
b. External signer D (weight=1)
c. External signer E (weight=1)

signers C, D, and E cannot collude to create valid signatures without A or B, and A or B individually requires the cooperation of two of C, D, and E.

Config-independent signatures allow for short persistent signatures that remain valid even after a wallet's config is updated on-chain. One application of these is ensuring that signatures created for OpenSea orders remain valid until those orders are filled.

## other observations

v2 wallet configs include a checkpoint, which can also be conceptually described as a wallet config nonce. The purpose of this is to guarantee that a wallet can only ever be updated to a newer config with a higher nonce, and never updated to an older config with lower nonce.

v2 wallet config approval signatures can be decomposed into the individual signatures made by the approving signers. These signatures can potentially be reconstructed into a new valid signature for a different wallet config. Because of this property, it's entirely possible to prune redundant subsignatures from a chained signature for even more calldata and execution gas savings.

E.g.: This chain of three sequential config approvals:
1. Signers {1, 3} of config {1, 2, 3} (threshold=2) approve config {4, 5, 6} (threshold=1)
2. Signer {5} of config {4, 5, 6} (threshold=1) approves config {2, 3, 7} (threshold=2)
3. Signers {2, 3} of config {2, 3, 7} (threshold=2) approve config {8, 9} (threshold=2)

can be pruned to a single equivalent signature reconstructed using signature (3):
1. Signers {2, 3} of config {1, 2, 3} (threshold=2) approve config {8, 9} (threshold=2)

Multiple wallet configs might share common subtrees. We strive to reduce data duplication by indexing those subtrees and storing references.