State Model - HackMD

## Introduction We are proposing a zkVM-based state model to handle state transitions securely and efficiently while preserving privacy. In our system, state consists of Application Data, Accounts, Signers, Notes, and Note Nullifiers, each represented by a sparse Merkle tree (SMT) or a Merkle tree. Our zkVM executes the state transition function, and it takes signed transactions and verifies their validity before applying them to the state. ### Roadmap * Push private UTXO state model for later * Privacy for users against public observers * Use single sequencer validium model * Escape hatch via forced inclusion * On-chain actions Goals: - Flexible and dynamic authorization mechanisms - High throughput - Ability to customize application logic The state consists of the following data structures: - Application Data: a sparse Merkle tree (SMT) - Accounts: a SMT - Signers: a SMT - Notes: a Merkle tree - Note Nullifiers: a SMT TODO: - SMT in Rust - Specify state model more in detail - State model sketch in Rust - Signers / Account etc. ## Application Data Application data (persistent storage used by the wallet program to store mutable parameters) is stored in sparse Merkle tree. ## Accounts Accounts are stored in a sparse Merkle tree, where the key refers to the ID of the account, and the value stores the hash of the account data. ### Account data Each account stores the following data: - A list of approved signers `[signer_0, ...]` - **Public assets**: a map from asset ID to balance information - **Private assets**: private assets are stored as notes. No information about private assets for an account is stored in account data. ### Account Management in zkVM Our zkVM has opcodes for account management, such as create_account, add_signer, remove_signer, deposit, withdraw, and transfer. These opcodes enable creation of accounts, signer management, and asset management respectively. Methods Creation: - `create_account([signer_id]) -> account_id` - Creates a new account with the provided list of approved signers, and returns the new account id Signer management: - `add_signer(account_id, signer_id)` - Adds a signer to the account's list of approved signers. - `remove_signer(account_id, signer_id)` - Removes a signer from the accounts's list of approved signers. TODO: Should this category of functions be restricted to a higher privledged group of signers? Asset management: - `deposit(account_id, asset_id, balance)` - Deposit the asset balance into a user's account. - `withdraw()` - Deposit the asset balance into a user's account. - `transfer(from_account_id, to_account_id, asset_id, balance, expiration_date)` - Creates a new note with the supplied note data. ## Signers  The field `signer_id` determines the subroutine in the state transition function that the sequencer should run. 1. An ECDSA verification key 2. An EdDSA verification key 3. A zk verification key for some Valida program, which takes input the message to be verified. In either case above, there is an verificaiton algorithm checking whether the signer has signed on some message $m$. Note that our transaction circuit will need to implement the verification algorithm for each method above. ## Notes We store private assets in *Notes*. Notes are stored in an (append-only) Merkle tree. Note nullifiers are stored in an epoch-based sparse Merkle tree. ### Note data Each note stores the following data: - *Owner account ID*: The account that is permitted to consume a note and absorb the balance into it's account data. - *Expiration date*: The date after which the sender can consume the note back into its account state. - *Asset id*: The id of the asset represented in this note - *Amount*: The amount of asset represented in this note - *Random nonce*: A piece of fixed randomness to ensure that the commitment of this note hides the contents of the note. We will describe how this nonce is determined separately. ### Note Management in zkVM Note management in zkVM involves creating and managing private assets or notes. Here's how it could be implemented: * `create_note`: This operation creates a new note tied to an owner account. The zkVM instruction would generate a new note ID, calculate the note hash (which includes the asset ID, amount, owner account ID, expiration date, and random nonce) and store the note hash in the Notes tree. * `consume_note`: This operation allows the owner of a note to consume the note and add its value to their account balance. The zkVM would validate the note ownership, check the note's validity against the note hash in the Notes tree, and update the account's balance. * `update_note`: This operation updates a note's attributes like its expiration date or amount. The zkVM would validate the request, check the note's validity, update the note data, and compute and store the new note hash in the Notes tree. ## Circuits Circuits ensure that state updates are done correctly. We use the term circuits here but they can be implemented in a vm like Valida. ### Private spend ("JoinSplit") The private spend circuit declares a tuple `(asset_id, value)` as well as a sequence of nullifiers `nf_0, ...` that represent spent notes in the private spend, as well as a sequence of new note commitments. A private spend circuit is proved client-side. ## zkVM Approach State transitions in the zkVM are carried out using specific instructions to handle state changes. These state transitions could include private spends, public spends, account creation, account updates, and more. Here's a detailed view of how the zkVM could handle application logic: 1. Input Validation: The zkVM takes the proposed state transition as an input and validates it against the current state. It verifies the signers of the transaction, the integrity of the data, and the balance sufficiency for the operation. 2. Transaction Processing: The zkVM executes the state transition using its set of instructions. This could involve creating accounts, adding signers, depositing or withdrawing assets, transferring assets, or creating and managing notes. 3. State Update: Once the state transition is validated and processed, the zkVM updates the state. This could involve updating the application data tree, the accounts tree, the signers tree, the notes tree, or the note nullifiers tree. 4. Output Generation: After processing the transaction and updating the state, the zkVM generates the new state and outputs any external actions (like asset withdrawals or external contract calls) to be executed. ### Private spend When switching from this circuit-based approach to a zkVM-based approach, the execution of such a transaction would change. In a zkVM, operations are encapsulated in instructions rather than circuits. The verification of a JoinSplit transaction would happen within the VM using a sequence of zkVM instructions that replace the previous circuit. In the context of zkVM, the specific handling of a private spend might look something like this: * Nullifier Checking: zkVM would include instructions to check the nullifiers against a set of unspent notes maintained in the state. This step ensures that the spent notes are indeed unspent and belong to the spender. * Value Conservation: zkVM would enforce a rule that the total value of spent notes must equal the total value of new notes being created. This could be achieved through instructions that sum the values of spent notes and newly created notes, comparing them for equality. * Proof Verification: zkVM would contain instructions to verify the zero-knowledge proof, ensuring that the spender has knowledge of the spent notes' secret values (which prove ownership) without revealing them. * State Update: After verification, zkVM would execute instructions to update the set of unspent notes by removing the spent notes (referenced by their nullifiers) and adding the new notes. We would need Valida to support these operations and to store the necessary data (like the set of unspent notes). Additionally, while the original document mentions that the private spend proof is generated client-side, in the zkVM-based approach, the VM itself would be responsible for the generation and verification of these proofs. The client would only be required to provide the necessary inputs. ### Application logic The application logic circuit is responsible to update the state. Public Inputs: * `prior_state`: Represents all trees (Application Data, Accounts, Signers, Notes, Note Nullifiers) in the previous state. It is used to validate the correctness of the transition. * `external_actions`: A collection of interactions with the external environment that affect the state. This includes actions like asset withdrawals and calls to external contracts. Functions: * `validate_transactions`: This function verifies the correctness of all transactions included in the state transition. This includes checking transaction signatures, ensuring sufficient account balances, and validating transfers. * `apply_transactions`: Applies all valid transactions to the `prior_state`. This function updates the account balances, generates new notes, and modifies signers as per the transactions. * `handle_external_actions`: Handles the effect of `external_actions` on the state. This might include updating the state based on asset withdrawals or any effects due to calls to external contracts. * `generate_new_state`: Generates the `new_state` by applying the results of `apply_transactions` and `handle_external_actions` to the `prior_state`. Outputs: * `new_state`: The updated state, resulting from applying the transactions and handling external actions. It includes updated versions of all trees (Application Data, Accounts, Signers, Notes, Note Nullifiers). * `transaction_receipts`: A list of receipts for each processed transaction. These receipts could include information like the updated account balances, new notes generated, and any changes in signers. * `external_action_receipts`: A list of receipts for each processed external action. These receipts document the impact of the external actions on the state. By organizing the application logic in this way, we can ensure that each state transition is processed in a controlled and predictable manner, which is essential for maintaining the integrity of our system.