# Session based ZK identities

ZK suffers from the same problem as crypto generally: private keys are king. It's impossible to build robust web applications using the private key (single master secret) model. If a user loses their private key, or has it compromised, the account is **permanently** lost. _The javascript browser execution environment cannot be considered safe enough to handle a private key._

In web authentication users expect session based authentication with the ability to

- view active sessions
- log out all other sessions
- create a new session via offline recovery

Most importantly, the account must be recoverable if the browser stored tokens are compromised or lost.

Luckily with ZK we have the flexibility to design a system to do this. This document is loosely based on the terminology of semaphore, but otherwise shares little with the semaphore key structure.

## High level goals

- Recoverable accounts: if a session token is compromised the user can always regain control
- Easy detection: the user should easily be able to see compromised tokens
- Low friction: the user shouldn't have to store or manipulate sensitive keys beyond backup codes
- ZK compatible: external protocols should be able to use the system with minimal complexity

## Semaphore sessions

This system is built with the following requirements:

1. Allow a user to have multiple active session tokens
2. Allow a user to see the last time a token was used
3. Allow a user to disable one or many session tokens
4. Allow a user to recover their account if all sessions have been compromised or lost
- Using backup codes similar to github/npm/etc 2fa recovery
5. Allow any session token to be used directly in a ZK proof interchangeably
6. Provide an identity secret that is common to all session tokens

A user identity structure might look like this:

{
    pubkey: uint256,
    backupTreeRoot: uint256,
    identityRoot: uint256
}

### List of terms

**pubkey**: A constant public identifier for the identity. This does not change.
**commitment**: The hash of the current identity secret.
**s0**: A secret share that can be combined with any session token to form the identity secret. This changes when a backup code is used.
**sessionTreeRoot**: The root of the session tree. Each leaf of this tree is the hash of a session token. Each session token is a secret share. Combine any token with **s0** to calculate the secret.
**backupTreeRoot**: The root of a tree containing all backup codes. This does not change.
**identityRoot**: `H(pubkey, H(sessionTreeRoot, H(S, s0, shareCount)))` - used as a single identifier for the identity state.
**secret (S)**: A cryptographically strong identity secret. May change over time. Based on `s0` and a `sessionToken`.
**share count**: The number of shares that have been created for the current `s0` value. This value is initialized to 3 (2 shares are created upon registration).

A user can calculate the secret by calculating the slope of a line that intercepts both `s0` and a `sessionToken`. The y intercept of this line is the identity secret. `s0` and all session tokens for an identity should exist on the same line. (See [Shamir's secret sharing](https://en.wikipedia.org/wiki/Shamir%27s_secret_sharing))

### Operations

Given the above structure we can start to define operations.

### Sign up/Register

A user registers by building a ZK proof that accepts the following inputs:
- `s0`: The initial secret share, should be a strong random value
- `sessionToken`: The initial session token, should be a strong random value
- `backupTreeRoot`: The root of a merkle tree filled with random elements. Alternatively this root could be constructed in ZK (with all backup codes being inputs).

Given these inputs the `H(sessionToken)` will be inserted into an empty tree to determine the `sessionTreeRoot`. The following values will be revealed:
- `H(sessionTreeRoot, H(S, s0, 3))`: used to calculate the identity root onchain. The value `3` is the initial share count value. This will be incremented each time a new session token is created.
- `backupTreeRoot`: Used for recovery

Onchain this proof will be verified and a _unique_ `pubkey` should be assigned to the new identity. The `identityRoot` will be calculated by hashing the assigned `pubkey` with the output hash above. The `backupTreeRoot` should be stored and associated with the `pubkey`. The user can now make auth proofs using `sessionToken`.

The contract should maintain a merkle tree of all identitity roots to allow for anonymous authentication. All examples in this document use non-anonymous authentication but can be extended to be anonymous - with the exception of account recovery operations.

### Authenticate

A user authenticates with a `pubkey` by proving the pre-image of a leaf in the session tree.

This proof accepts the following inputs:
- `sessionToken`: The token the user is authenticating with
- `sessionTreeIndices`: Merkle proof indices
- `sessionTreeSiblings`: Merkle proof siblings
- `pubkey`: The identity public key
- `s0`: The initial secret share

The proof should prove that `H(sessionToken)` exists in a tree with root `sessionTreeRoot`. The identity root should be output as a public signal.

This proof is verified by checking that the output matches a valid onchain identity root.

### Sign in a new session

A user signs in a new session using either an existing session or a backup code.

#### Signing in from an existing session

The existing session calculates the current identity secret `S` and shares this with the new session context.

The user then makes a proof with the following inputs:
- `S`: The current identity secret
- `s0`: The current initial secret share
- `sessionToken`: The new session token to activate
- `sessionTreeIndices`: Merkle proof indices
- `sessionTreeSiblings`: Merkle proof siblings
- `pubkey`: The identity public key
- `oldSessionTreeRoot`: The current session tree root (without the new session token)

The proof will verify that `S`, `s0`, and `sessionToken` all exist on the same line. If they do `H(sessionToken)` will be inserted into the `sessionTree` and an updated identity root will be revealed.

This proof should output the old identity root (using `oldSessionTreeRoot`), and a new identity root. The new identity root should only be accepted if the old identity root is valid.

#### Signing in using a backup code

If all session tokens have been lost or are otherwise inaccessible a backup code can be used to create a new session token.

The user makes a proof with the following inputs:
- `s0`: A _new_ initial session share
- `sessionToken`: A _new_ session token to activate
- `pubkey`: The identity public key
- `backupCode`: A valid, unused, backup code
- `backupTreeIndices`: Merkle proof indices
- `backupTreeSiblings`: Merkle proof siblings

The proof will calculate a new `sessionTreeRoot` containing only `sessionToken`. **All existing tokens will be de-activated.** A new identity secret is calculated based on `s0` and `sessionToken`.

The proof outputs a new identity root, and a `backupCodeNullifier` (`H(backupCode`).

To verify this proof the `backupCodeNullifier` must not have been seen before.

If the proof is valid the existing identity root for `pubkey` should be replaced.

### Signout a single session

A user can choose to de-activate a single session token by authenticating and then updating the `sessionTreeRoot` in ZK, removing an entry.

### Signout all other sessions

A user can sign out all other sessions by building a ZK proof that proves authorization and updates the `sessionTreeRoot` to include a single entry: the current session token.

## Open questions

How to get historical identity secrets?
- Symmetrically encrypted linked list of secrets
- Secrets change when the session tree is reset
- Encode in backup codes

Can `backupTreeRoot` function as `pubkey`?

## State of this document

This document is a basic description of a functional protocol. Some notes about data availability (for constructing merkle proofs) are not yet included.