# State-change authentication schemes as a decentralized identity and key management solution automated by Ethereum's Account Abstraction

## Abstract
In this technical proposal, we describe a solution to two simultaneously important problems in current web3 massive scaling endeavour, which account abstraction tackles individually but need to still be compatibly solved:

- **<ins>The key/identity management problem</ins>:** Store and retrieve private keys or their (threshold-cryptographic) shares in a trustless and non-custodial way, and
- **<ins>The UX-abstraction problem</ins>:** Be user-friendly to a diverse and scalable user-base by abstracting enough detail without sacrificing user choice and autonomy.

As our solution, we propose the **<ins>State-Observing Network</ins>**: A peer-to-peer network with ephemeral emergent MixNet sub-networks which stores secrets in a trustless, decentralized manner, easily interfaced with end-users by Account Abstraction wallets, allowing them to have temporary, revocable and distributed identities, while still being retroactively compatible with any other wallet in the platform.

This is achieved by developing several internal structures, among which we find:

1. **<ins>Authenticator groups</ins>:** Which execute our own developed family of authentication schemes: State-change authentication schemes (SCAS)
2. **<ins>Shared-state groups</ins>:** Which keeps consensual shared state to respond to a highly-scalable parallel number of users while keeping balance to the power inside the network.

## Motivation

We believe there are, across several other important problems to solve, two really ubiquitous issues which are holding back massive scaling of web3 technologies:

- <ins>The identity management problem</ins>, more intuitively thought as a "key management problem" which is comprised by:
- Key (identity) retrieval mechanisms and
- Key (identity) theft protection mechanisms
- <ins>The UX abstraction problem</ins>, which Ethereum's account abstraction infrastructure already allows for an ecosystem of layered solutions.

In order to scale significantly further the web3 ecosystem, it is not enough to solve both problem in isolation, but actually be solve them in a **compatible manner**: That is, managing users blockchain identity (being a private key or otherwise) should be an abstracted enough experience to allow smooth diverse adoption, while still preserving its security, retrieval and theft mitigation guarantees, and users' freedom of choice.

We describe further both components of the first problem to illustrate our approach in co-solving them along with a good enough UX.

### The key (identity) management problem

Currently, there is no good way to retrieve a lost private key without relying on either:

- A custodial/semi-custodial solution, which defeat the purpose of decentralization most of the time and requires trusting a third party.
- A threshold cryptosystem, which doesn't solve the problem completely since there is still a need to trust the parties who store the shards and wrap the cryptographic details securely and UX-friendly enough.

Thus, a totally non-custodial, trustless storage for either the complete private key or at least some shard(s) is still needed.

The origin of several bad UX features of current non-custodial and trustless solutions come from the locality of its design. That is, to maximize user autonomy and decentralization, current solutions still demand a significant amount of responsibility and liability from the user.

This may be solved by introducing a decentralized network (infrastructure), equipped an trustless operative layer. Given that, the second component of key management, key theft mitigation, should be also solved by this operative layer. In particular, it should not introduce vulnerability vectors which instead increase the risk.

### The key (identity) theft problem

Let's define key (identity) theft as the event of some unintended party gaining privilege to act on behalf of some user by use of their identity. We note that this definition includes even unintended thefts, but also it does not imply that theft requires the unintended party to be able to act on behalf of some user and not only hold what user's identity was.

This subtle point suggests a traditional solution to provide agent's identities with privilege revocability and temporality: Using sessions keys (identities).

Now, this requirement is usually fulfilled by some cryptographic scheme to produce temporary and revocable representations of the true permanent key (identity). Nevertheless, even if that is possible to achieve within the Account Abstraction ecosystem, it is:

- Neither <ins>retroactive</ins>: Non-AC compatible wallets wouldn't have this benefit),
- Nor is it <ins>non-local</ins>: Implying the existence of substantial UX obstacles, coming from liabilities and responsibilities demanded from the user.

Thus, our approach seeks to produce a: Trustless, fully decentralized (and thus, non-custodial), retroactively-compatible infrastructure to represent user's identity securely enough to not introduce vulnerabilities and flexibly enough to provide a session management layer for temporality and revocability.

## Overview

### Infrastructure

Even with the theoretical properties agreed upon, and actually a theoretical framework for its design [available](https://docsend.com/view/dbk48wukd3ivd3ad), the implementation process of our solution will bring challenges, specially concerning some parameters tuning and potential performance optimization.

To be precise in the scope of this implementation project, we enumerate once more the objective properties and which ones of those are going to be prioritized across the roadmap. We want a decentralized infrastructure which simultaneously is:

- Trustless
- Non-custodial
- Compatible with any public-key infrastructure
- Allow users to have temporary and revocable identity.

Our solution, the state-observing network, is a peer-to-peer network with ephemeral emergent MixNet sub-networks to ensure anonymous communications of shards of secrets (where a secret may be a whole private key or a shard of it) from mixed batches from multiple users into authenticator network nodes we call observers.

These authenticator groups are just one of the sub-structures the state-observing network has to provide the properties previously mentioned. In particular the authenticator groups are in charge of holding shards of secrets and participate in a MPC-based collective authentication process for sending back the shards to the authenticated users through some MixNet structure which hides even the truly needed participants of the MPC with a zero knowledge communication layer.

The "authenticated users" should prove to the entire authenticator group their identity with a authentication scheme (or rather, some member of a family of authentication schemes) we call State-change authentication scheme (SCAS).

### Scope of the project

The project scopes the construction of one instance of a SCAS by using a cryptographically-enhanced wrapper for some statistical information *well enough behaved* for it to serve as reliable source of identity, given some user-base.

The SCAS will be used to build the authenticator groups infrastructure and logic needed for prototyping the end-to-end workflow for users to securely store and conveniently retrieve their secrets from the network. This should be enough - and is one of our objectives - to achieve the needed interfaces for any other SCAS to be plug-and-play.

On other hand, the state-observing network has another sub-structure, namely

- The state-sharing groups, who are in charge of keeping consensus con state-information for a scalable number of users to be authenticated in parallel as well as keeping balance to the authenticator groups power, and
- The ephemeral MixNet sub-networks, who need to emerge in an organized manner to respond to anonymity demands from network operations, while not disrupting current information flow.

These two will also be further developed and at least prototyped for the specific SCAS example we will be implementing.

Also, as part of the project, we are going to keep developing the general threat models theory for our infrastructure to have better insights into the security limitations on each edge case, to learn how to better manage them.

## Objectives

- [ ] Build our state-observing network for one specific State-change authentication scheme (SCAS).
- [ ] Build and test the needed interfaces for any other SCAS to be plug-and-play seamlessly on the live state-observing network.
- [ ] Solve the private key management and UX problem in web3 with satisfactory security and user acceptance as measured by precisely defined threat models and user autonomy and choices.
- [ ] Provide the infrastructure as an open-source contribution to the ecosystem

## Outcomes
The finished product can be defined with the following traits:

- Client side functions for the SCAT delivery and batch preparations for secret distribution.
- Client side application for observers (network nodes) with the ability to manage received batches and SCAS-challenge back when asked to retreive.
- Peer-to-peer network infrastructure with ephemeral emergent MixNet sub-networks generation algorithm to ensure anonymous communications of shards of secrets
- Interfaces automatizing the whole SCAS-managed decentralized identity by using Ethereum's Account Abstraction (AC).

## Project Team
How many people are working on this project?

Three people

Please list their names and roles for the project as well as how many hours per month will each person work on this project?

Felipe Flores - CTO - 10 hours
Leonel Obando - Head of Science - 20 hours
Victor Amaya - Tech Lead - 15 hours

## Team background

Felipe is a mathematician and physicist who has developed mathematical models for actuarial risk management, specifically in long-term stochastic dynamical systems simulations for normative, operational, and financial scenarios. He also focuses on cybersecurity risk management, including network penetration testing, infrastructure vulnerability analysis, and risk quantification for different threat models.

Victor is a Web 2.0 developer who transitioned to Web 3.0. He has implemented more than 10 EVM and non-EVM blockchains in Dippi API, as well as developed our core API infrastructure, built using Docker, TypeScript, and Solidity.

Leonel is our head of science and a professor in applied mathematics, with a strong background in number theory. His main focus is on developing proofs for our theoretical theorems.

## Methodology
The 5 month plan is distributed as follows:

1. Skeleton apps for both client apps, with testing suites requiring the MVP functionality as a layout for a test-driven development workflow. At this stage we expect the following:
- Have every final MVP feature explicitly described by our tests.
- Have a network testing suite as well, showing the initial security expectations of the network.
- Have enough dummy functions to begin to pass some of the tests, specially mocking up the batches.
- Have a well-designed profile for the expected user capabilities and needs, as well as a overall threat model.
- Mock the ephemereal local MixNet generation with a static one for the time being.
2. Focus completely on the observer client app, until achieving a minimal satisfactory passing state on our test suite. At this stage we expect the following:
- Complete successful end-to-end processing of the mocked batches by first receiving them, storing them, passing the expected proof-of-spacetime challenges and respond retrieval requests by producing SCAS challenges and verify them.
- Shared-state generation.
- MPC protocols for authenticator groups collaboration
- Any peer-to-peer and mixnet basic operations needed at this stage.
3. Focus completely on the requester client functions achieving a minimal satisfactory passing state on our test suite, as well as the network operations needed for peer to. At this stage we expect the following:
- Encryption and splitting of secrets into SCAT compatible format ready.
- The Account Abstraction interface layer complete. This includes a simple front-end to test the end-to-end user experience.
- SCAS authentication input from the user well tested from the expected device types.
- Any peer-to-peer and mixnet basic operations needed at this stage.
4. Focus on the network connections protocol layers for peer-to-peer functionality. This would be done mostly by re-using existing libraries and infrastructures but we expect at this stage to:
- Have all the remaining peer-to-peer needed operations working.
- Complete the ephemeral emergent MixNet sub-networks generation algorithms.
- Stress and security testing for each of the component as we integrate everything together.
5. Complete testing of the partial integrated parts into the final cohesive product. At this stage we expect to have time dedicated to additional security testings, bug fixing and edge cases testing, as well as polishing the user experience

The work tasks distribution will be done by specializing tasks according to the team background, since our development will be composed pretty uniformly of the following categories:
- Frontend development (Victor Amaya)
- Backend development (Victor Amaya and Felipe Flores)
- Security design and analysis (Leonel Obando and Felipe Flores)
- Security attacks testing (Leonel Obando)
- Cryptography programming (Leonel Obando and Felipe Flores)

## Timeline
- 5 months, distributed as described on the methodology section.

## Budget
- 40k distributed across the work loads of the members and server costs.

## Technical background
### Theory: Blockchain-like time series.

**Def 1. (Stochastic Process)** Let ($\Omega, \mathcal{F}, P$) a probability space, $(S, \Sigma)$ be a measurable space and $(T, \leq)$ a totally ordered set. A stochastic process is a family $\{X_t\}_{t \in T}$ of measurable functions $X: \Omega \to S$.

**Remark.** When $(T, \leq, d)$ is additionally a metric space with distance $d$ and satisfies that $T = \{t_i\}_{i \in \mathbb{Z}^+}$ with $d(t_i,t_{i+1}) = c$ for every $i \in \mathbb{Z}^+$ and constant $c$, we say it is an $c$-spaced stochastic process. From now on we are going to work only with $c$-spaced stochastic processes for some $c$, sometimes left implicit.

**Def 2. (Time series)** Let $\{X_t\}_{t \in T}$ be a stochastic process. Then, for a finite sequence of events $\Omega_{[t_0,t_f]} := \{\omega_t\}_{t=t_0}^{t_f} \subset \Omega$, the sequence of evaluations $\{X_t(\omega_t)\}_{t=t_0}^{t_f} \subset S$ is called the $\Omega_N$-time series of the stochastic process.

**Remark.** The sequence of events $\Omega_{[t_0,t_f]}$ is usually omitted when not specifically relevant, and the evaluations $\{X_t(\omega_t)\}_{t=t_0}^{t_f}$ are then simplified to the notation $\{x_t\}_{t=t_0}^{t_f}$. Additionally, given that $N := |\Omega_{[t_0, t_f]}|$, we can re-index the time series as $\{x_t\}_{t=0}^{N}$ and called it an $N$-step time series.

**Remark.** Since $T$ is totally ordered, we can find a bijective mapping $B$ from $T$ into $\{0,1, \ldots, |\Omega_{[t_0, t_f]}|\}$ such that notation like "$t-1$" makes sense even without an algebraic structure on $T$, since we understand $t-1$ as the only element in $T$ such that $B(t-1) < B(t)$ but $B(s) < B(t-1)$ for every other $s \neq t-1$ such that $B(s) < B(t)$. Analogously, we tag each element in $T = \{N, N-1, \ldots, t, t-1, \ldots, 2, 1\}$ in that same way.

**Def 3. (words in an alphabet)** Given a non-empty set $\Sigma$, called an *alphabet*, we call an element $w = (w_1, \ldots, w_n) \in \Sigma^n$ an $n$-length word and is written by concatenation as $w_1w_2\ldots w_n$. The space of all words over $\Sigma$ is denoted as

$$
\sigma^* := \bigcup_{i \in \mathbb{Z}^+} \Sigma^i
$$

**Def 4. (Hash function)** Given an alphabet $\Sigma$, we call $H: \Sigma^* \to \Sigma^N$ an $N$-fixed size $(P, \epsilon)$-collision resistant hash function over $\Sigma$ if, when equipping $(\Sigma^*, \mathcal{F}, P)$ with the probability measure $P$ and $\Sigma^N$ with its power set as $\sigma$-algebra, it satisfies:

$$
P(\{w \in \Sigma^* : \exists\, \tilde{w} \neq w \text{ such that } H(\tilde{w}) = H(w) \}) < \epsilon
$$

**Def 5. (Blockchain-like time series)** Given
- $\{x_t\}_{t=0}^{N}$, a $N$-step $S$-valued time series,
- $H: \Sigma^* \to \Sigma^M$, an $M$-fixed size hash function,
- $w_0 \in \Sigma^*$, a word called seed,
- $C: \Sigma^M \times S \to \Sigma^*$, called block aggregation function,

we call $b_t := (w_t, x_t) \in \Sigma^M \times S$ blocks, where $w_t := H(C(w_{t-1}, x_{t-1}))$ for $t \in \{1, \ldots, N\}$, and the collection $\{b_t\}_{t=0}^N$ an $N$-sized blockchain-like time series (BLTS).

Let's build an authentication scheme for a user-base $\Gamma$ by leveraging the BLTS structure. Start with a SCAS-compliant network $\mathcal{O}$, and let $s \in \Sigma^*$ be a secret to be stored safely. First split the secret into sub-secrets $\{s_i\}_{i=0}^{N_s}$ to be sent to $N_s \sim U(\{m_{s,\min},\ldots,m_{s,\max}\})$ randomly selected observers $\{v_i\}_{i=1}^K \subset \mathcal{O}$. Then, let $\{X_t^u\}_{t \in T}$ be a stationary stochastic process associated to some user $u \in \Gamma$, and produce $N_s$ time series from it, each from a different and randomly generated size $N_{ts}^k \sim U(\{m_{ts,\min},\ldots,m_{ts,\max}\})$ for $k \in \{1,\ldots,N_s\}$.

More precisely, a family:

$$
\mathcal{F}\mathcal{T}_u := \left\{\mathcal{T}^{u,k}\right\}_{k=0}^{N_s} := \left\{\{x_t^{u,k}\}_{t=0}^{N_{ts}^k}\right\}_{k=0}^{N_s}
$$

of time series are generated and used to build $N_s$ BLTS from a set of seeds $\{w_{0,k}\}_{k=1}^{N_s} \subset \Sigma^M$:

$$
\mathcal{F}\mathcal{B}\mathcal{T}_u =
\left\{\{b_t\}_{t=0}^{N_{ts}^k}\right\}_{k=0}^{N_s} =
\left\{\left\{(w_t, x_t^{u,k})\right\}_{t=0}^{N_{ts}^k}\right\}_{k=0}^{N_s}
$$

For each BLTS $\{b_t\}_{t=0}^{N_{ts}^k} \in \mathcal{F}\mathcal{B}\mathcal{T}_u$ we sent the first half, $\{b_t\}_{t=0}^{\lfloor N_{ts}^k/2\rfloor}$ to the $k$-th observer. This alone should provide a statistical significance sufficiently low to be safe the required authentication tolerance can't be achieved

When authenticating, the user $u$ should produce a continuation of each stochastic process realization for $s$ more steps: $\{x_t^{u,k}\}_{t=N_{ts}^k}^{N_{ts}^k+s}$ and produce the corresponding blockchain continuation for the BLTS: $\{x_t^{u,k}\}_{t=N_{ts}^k}^{N_{ts}^k+s}$