User-centric Private State Management (PSM) on Celestia

# User-centric Private State Management (PSM) on Celestia > _**Pre-reading**: This document assumes the reader understands [Verifiable Encryption (VE)](https://github.com/celestiaorg/pda-proxy/blob/main/doc/verifiable_encryption.md) that is fundamental to the protocols described below._ ## Why? The web3 industry is moving away from it's original form where all state of the network was stored by all participants and publicly readable. We now are emerging into a world where state is mostly offchain and thus putting the responsibility of maintaining it , not the network. (TODO concrete examples ) If user state is lost by all parties, it is likely that their account is "frozen" and irrecoverable, perhaps even as much as the protocol itself being unable to progress globally. One solution to the state management issue is to post all protocol data publicly and ensure data availability (DA) over that data - this is what many ZK rollup constructions do today... **But what if we don't want protocol state to be publicly readable?** Then DA alone is not enough, we need a way to obtain DA properties on private data. ## Intrducing the Problem Zero Knowledge Proof (ZKP) protocols allow for application specific state to be separated completely from a (general public) blockchain's state while _proving correct state transition functions (STFs) on hidden state_ and connecting with global public state onchain. If protocol operators (POs) are not cooperative in user requests (censorship, downtime, etc.) users may be unable to progress on their own accord offchain, or force an exit of a the protocol onchain. In most cases today, users depend completely on POs to maintain their offchain state, and users may not even have a means to obtain or reason about it themselves. In ZKP protocols, without user-specific state and the ability to prove a valid STF on that state offchain, there is no way for the user to update their state independent of the POs. ## Goal Enable user-specific encryption of their state, stored publicly, and accessible to users and POs even under hostile conditions using Celestia for DA. - Users **must** be able to determine if offchain global state for a protocol includes their account state. - Users **must** be able to selectively disclose and make proofs about their latest state (and **may** be able to do so for historical state as well). - Protocols **should** ensure user encrypted state is posted on Celestia before progressing global state. - Users **should** be able to progress the protocol by proving a correct STF on their state onchain without any POs involvement - enabling "forced" state updates via proofs on their state (likely to "exit" the protocol, like taking tokens out, etc.). Desired properties of encryption: - Encryption schemes **should** provide means to enable [forward secrecy](https://en.wikipedia.org/wiki/Forward_secrecy) properties on state. - Existing Key Management Systems (KMS) should be easy to integrate for POs and users. - Users **should** have the ultimate control of encryption keys used, rather than relying on POs to create, distribute, and maintain them. ### Initial use cases A few related ideas: - **Much more advanced ideas we can learn a lot from: https://www.inkandswitch.com/keyhive/notebook/#layers** - https://github.com/0xMiden/miden-proposals/issues/3#issuecomment-3013845161 - CLOB DEX that has trusted POs progressing all state with ZKPs, and wants private user state backups and ways to force include transactions (later is out of scope, but should be kept in mind) ### Why not \<some other storage\>? > Where should state be stored? IPFS? Matrix? Centralized cloud? All of them? Some example use cases that need DA: - Enforce that a protocol _cannot_ progress private user state data is not made avalible. Thus you ensure users can always exit (or maybe force include any transaction type into the protocol). They are guaranteed DA for a (30 day, soon 14 day) window to be able to get the data needed to exit if the DEX is not cooperating and/or down. - Users can make proofs about their private state, know to be publicly accessible where you would be able to build in protocol mechanisms to check for such a message on Celestia. Example: "I hold X tokens on this private DEX. Force exit these tokens from the protocol." - _TODO: Something related to shared state with multiple user operations_ ### Why not just authenticated encryption ([AEAD](https://en.wikipedia.org/wiki/Authenticated_encryption)) ? While you can prove that some public data was embedded into the encryption operation, you cannot constrain the plaintext at all. You must fully trust the publisher that some associated data like the hash of the plaintext didn't lie in creating the ciphertext. It's quite possible to commit a "hash" of _something_ into the AEAD object, but that hash is not required to be related to the plaintext in any way. Verifiable Encryption (VE) enforces that some ciphertext has plaintext with specific properties (like the plaintext hash), and constrains the it to be constructed correctly (using a specific key, nonce, algorithm used, etc.) ## Assumptions - POs are able to read global protocol state & know all protocol state and per-user encryption keys. - All user state is accounted for in a Merkle Tree ($T$) that uses some State Transition Function (STF) protocol that progresses $T^n \rightarrow T^{n+1}$. - POs with global protocol state can _prove publicly_ that the STF indeed used the state (or state update) that is fully described by $T$ and has root $R$. - Likely requires a ZKP of the STF. - $T$ has a Merkle Root ($R$) that any user can obtain a Merkle Proof ($\gamma_{user}$) for that proves inclusion in $T$. - Users coordinate with PO to establish a means of generating a $user$-specific symmetric key ($s\_key_{user}$) that the PO stores for all users, and each user stores for themselves. - $s\_key_{user}$ may be generated via standard [key exhange protocols](https://en.wikipedia.org/wiki/Key_exchange), such as ECDH or ML-KEM. You may encrypt "to an address" with something like https://gitlab.com/nuke-web3/ecies-demo/ or https://github.com/str4d/rage . ## Protocol Outline (ZK Enforced)  ```mermaid flowchart TD subgraph MerkleHashes["Tree $$\ (T)$$"] Root["Root $$\ (R)$$"] L1["$$H(H_{1},H_{2})$$)"] L2["$$H(H_{3},H_{4})$$)"] LH1["$$H_{user=1}$$ = Leaf Hash"] LH2["$$H_{2}$$"] LH3["$$H_{3}$$"] LH4["$$H_{4}$$"] Root --> L1 Root --> L2 L1 --> LH1 L1 --> LH2 L2 --> LH3 L2 --> LH4 end subgraph POonly["PO known states (NOT on Celestia)"] D1["$$state_{user=1}$$"] D2["$$state_2$$"] D3["$$state_3$$"] D4["$$state_4$$"] end LH1 --> D1 LH2 --> D2 LH3 --> D3 LH4 --> D4 PD1["$$ZKP(encrypted(state_1), H_1)$$"] PD2["$$ZKP(encrypted(state_2), H_2)$$"] PD3["$$ZKP(encrypted(state_3), H_3)$$"] PD4["$$ZKP(encrypted(state_4), H_4)$$"] D1 -- "$$VE(state_{user=1},s\_key_{user=1})$$" --> PD1 D2 -- "$$VE(state_{2},s\_key_{2})$$" --> PD2 D3 -- "$$VE(state_{3},s\_key_{3})$$" --> PD3 D4 -- "$$VE(state_{4},s\_key_{4})$$" --> PD4 subgraph EncryptedStates["VE of states (on Celestia)"] PD1 PD2 PD3 PD4 end PD1 .-> LH1 ``` Similar to the [optimistic](#Protocol-Outline-Optimistic) construction, but instead of the previous $encrypt(\gamma_{user}, s\_key_{user})$ operation, we opt to publicly disclose the Merkle Tree $T$. We also only encrypt the leaves (user-specific state data) as we **assume there is no need to hide the remaining tree structure** as no state information is disclosed in it[^assume_public_tree_structure]. [^assume_public_tree_structure]: The overhead of encrypting the full merkle proofs is redundant and costly if there is no problem revealing all but the leaves publicly. (If that is an issue, replacing $encrypt(\gamma_{user}, s\_key_{user})$ with $verifiably_encrypt(\gamma_{user}, s\_key_{user})$) in full would work too. ```mermaid flowchart TD User[/"User"\] DA[("Celestia Data Availability")] subgraph " " direction TB PO[/"Protocol Operator (PO)"\] -- "$$verifiably\_encrypt(state_{user}, s\_key_{user})$$" --> EncProofPerUser["User encrypted $$\ ZKP(state_{user}, H_{user})\ $$ packets"] PO -- "Tree $$\ T\ $$ of user states, leaves omitted" --> ZKP["$$T$$"] end ZKP --> DA EncProofPerUser --> DA subgraph " " direction TB User -- "$$verify(ZKP) \rightarrow H_{user} \ \ \&\& \ \ decrypt(state_{user}, s\_key_{user})$$" --> UserProof["$$(state_{user}, H_{user})$$"] end EncProofPerUser -- "Receive update (happy path)" --> User DA -- "Receive update (fallback)" --> User ``` 1. PO *verifiably* encrypts $user$'s state ($state_{user}$) with $user$-specific symmetric key ($s\_key_{user}$), and commits to it's hash $H_{user}$ that is included in $T$ with root $R$ . - Verify ZKP so users know it's unmodified upon decryption 2. PO produces a ZKP _for each user_ with: 1. Input = $state_{user}$ and associated $s\_key_{user}$ 2. Hash the state to arrive at identical leaf hash ($H_{user}$) 3. Commit $H_{user}$ in VE as "anchor" to $T$ that contains $H_{user}$ 3. PO submits to DA: - $T$ - ZKP of Verifiably Encrypted user states proving $T$ as public "anchor" that all $H_{user}$ reference, 4. User obtains ZKP of their encrypted state data from PO (happy case) or DA (if P0 is misbehaving) 5. User verifies ZKP to obtain $(encrypted(state),$H_{user}$)$ 6. User decrypts to obtain $state_{user}$ 7. User knows $state_{user}$ is included in $T$ with root $R$, thus affirming their state is in $T$ that only POs know globally. With [Blobstream](https://docs.celestia.org/how-to-guides/blobstream), we may enforce DA happens in protocol, ensuring state data was published on DA layer before progressing on any EVM chain.[^gather_blobs_proving_completion] [^gather_blobs_proving_completion]: Important practical note: with [Blobstream](https://docs.celestia.org/how-to-guides/blobstream) integration, POs *should* never be able to leave any user in an irrecoverable state. BUT this may be impractical to block progress on, as encrypted user data packets need to be *simultaneously* gathered and all verified. Tooling like the [equivalency service](https://github.com/celestiaorg/eq-service) could be adapted for that purpose: to prove a multi-blob, and even multi-block inclusion of all those packets into one succinct (i.e. groth16) verification on the EVM. ## User-Controlled Key Management Protocol In the [original vision of VE protocol-centric models](https://github.com/celestiaorg/pda-proxy/blob/main/doc/verifiable_encryption.md), the POs would be the the only parties who had sole access of the symmetric keys to encrypt with, and thus undefined methods for key recovery (threshold decryption, MPC, etc.) was required. In user-centric models, users **must** know the keys for normal operations, and thus no key recovery mechanism is generally required as all the keys needed are already shared with parties that need them. We can go further to enforce that encryption keys are generated and held by users in such a fashion that POs cannot progress without using the user's defined key selection to encrypt with: 0. Protocol defines public key ($P\_key_{pub}$) that *only* POs have the private key for ($P\_key_{secret}$), 1. User creates new symmetric encryption key $s\_key_{user}$. 2. User performs _asymmetric_ VE (e.g., RSA, ElGamal, or ECIES type protocol inside zkVM): $VE_{asymmetric}(P\_key_{pub}, s\_key_{user}) = ZKP(P\_key_{pub}, hash(s\_key_{user}), encrypted(s\_key_{user}))$ - In this case, the VE anchor = $hash(s\_key_{user})$ - thus anyone with the proof can verify that POs should have ability to decrypt $s\_key_{user}$ and hash(s\_key_{user}). 4. User publishes $VE_{asymmetric}$ on DA. 5. POs watch DA for user proofs, and are _forced_ to use any new or updated key in protocol. - Protocols don't have "force inclusion by DA" yet as far as authors are aware, this would need to built, but there is strong demand for a force inclusion path that DA can provide (more details TBA). 7. POs post all future VE _for per-user encrypted state_ using the forced user-controlled key. - The $hash(s\_key_{user})$ is reported in state related VE, and must be latest forced user-controlled key hash or else protocol can't progress (blobstream enforced). - (Only needed if updates not blocking protocol) A way for user to halt protocol if somehow update for state was missed? Thus there is no protocol controlled key, just a set of user keys the protocol is forced to use. --- ## Reference Only > **_Below is not intended for use, as the ZK workflow above is better in every case, so the author believes._** ### Protocol Outline (Optimistic)  ```mermaid flowchart TD User[/"User"\] DA[("Celestia Data Availability")] subgraph " " direction TB PO[/"Protocol Operator (PO)"\] -- "$$encrypt(\gamma_{user}, s\_key_{user})$$" --> EncProofPerUser["User encrypted $$ (\gamma_{user}, R) $$ packets"] PO -- "STF w/ tree T user states ZKP commit Merkle root R" --> ZKP["STF ZKP(R)"] end ZKP --> DA EncProofPerUser --> DA subgraph " " direction TB User -- "$$decrypt((\gamma_{user}, R), s\_key_{user})$$" --> UserProof["$$(\gamma_{user}, R)$$"] end EncProofPerUser -- "Receive update (happy path)" --> User DA -- "Receive update (fallback)" --> User UserProof -- "Verify state included in ZKP(R)" --> DA ``` 1. PO encrypts $user$'s Merkle Proof ($\gamma_{user}$) for $T$ and root $R$ with $user$-specific symmetric key ($s\_key_{user}$) = User's _encrypted_ Merkle Proof = $encrypt({\gamma_{user}},s\_key_{user})$ - Use MAC so users know it's unmodified upon decryption 2. PO produces a ZKP with: 1. Input = All $k$ user _unencrypted_ states 2. Merklize the per-user states to arrive at identical $R$ 3. Commit Merkle root in VE as "anchor" $R$ 4. \<Protocol specific STF here, in same proof or in parallel, latter connected or aggregated.\> 5. ... 3. PO submits to DA: - ZKP proving $R$ as public "anchor" that all $\gamma_{user}$ reference - Encrypted user states $encrypt({\gamma_{user}},s\_key_{user})$ 4. User obtains $encrypt({\gamma_{user}},s\_key_{user})$ data from PO (happy case) or DA (fallback) 5. User decrypts to obtain $\gamma_{user}$ 6. User check $\gamma_{user}$ and DA root $R$, and DA thus affirming their state is in $T$ that only POs know globally. With [Blobstream](https://docs.celestia.org/how-to-guides/blobstream), we may enforce DA happens in protocol, ensuring state data was published on DA layer before progressing on any EVM chain.[^gather_blobs_proving_completion] **Note:** the users should have a way to dispute if the PO passes an un-decryptable or invalid $(\gamma_{user}, R)$ payload. This version of the protocol does not enforce correct encryption... thus motivating:

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.