Generalized Nonces (WIP)

[lrettig]

Overview

This proposal outlines our design for generalized nonces. A nonce is a unique value included in a transaction that serves three purposes:

1. To prevent the same transaction from being replayed multiple times (replay protection)
2. To allow transactions to be replaced by higher-fee transactions (replace by fee)
3. To ensure transactions for a given account are executed in a specific order (transaction ordering)

Hand-in-hand with account unification and the abstraction and generalization of many of the core concepts and functions of the account model "into the VM" in specialized smart contracts (dubbed "principal accounts" in Spacemesh), this proposal presents a scheme whereby principal accounts can implement nonce schemes in a variety of fashions.

Background: https://community.spacemesh.io/t/nonce-schemes-and-account-unification/202

Goals and motivation

• make it easy for most accounts to implement a standard nonce scheme familiar to developers of other smart contract platforms
• at the same time, allow developers to experiment and implement many novel forms of nonce schemes, subject to certain constraints
• work within the constraints of the unified account model, such as immutable account state
• work within the constraints of the transaction selection mechanism
• make it as easy as possible for miners to manage mempools, including filtering and dropping transactions invalidated by other transactions with conflicting nonces
• support both single-tenant and multi-tenant use cases of principal accounts

High-level design

Each account has a nonce value stored in its state. The account can choose to interpret this value any way it likes through the use of new handler methods used to sort new transactions, check transaction validity, and perform state updates. Miners use these handler methods to filter and sort new transactions as they enter the mempool.

Prior art

• Ethereum: sequential int nonces
• NEAR, Polkadot, Avax, Cosmos SDK: like Ethereum
• Solana: uses recentBlockhash (must be < ~60 secs old) rather than a nonce, see:
  • https://solana.wiki/docs/solidity-guide/transactions/#nonce
  • https://docs.solana.com/offline-signing/durable-nonce
• Algorand: Transactions contain first valid and last valid fields (specifying rounds, which are like layers), no nonce. References
  • https://pipaman.medium.com/algorand-transactions-15b3a4fa33f3
  • https://developer.algorand.org/docs/get-details/transactions/#setting-first-and-last-valid
• Flow: uses "sequence numbers", which are associated with keys, not accounts (an account may have multiple keys). See https://docs.onflow.org/concepts/transaction-signing/.

Proposed implementation

We add a 32 byte nonce value to the state of each principal account. Each principal account also implements four handler methods:

• noncevalidity(tx) -> [true, false]
• nonceupdate(tx)
• noncethreshold(tx) -> [layerstart, layerend, cmax, noncemask]
• compare(tx_a, tx_b) -> [-1, 0, 1]

A nonce scheme needs to specify:

• The account state (required for nonce verification)
• The transaction data (required for nonce verification)
• Four algorithms:
  • New transaction filter: should a new transaction be accepted into the mempool. The new transaction filter may use both the state of the ledger and the current contents of the mempool.
  • Sorting algorithm: given a set of transactions from the same account, how should they be sorted in a layer.
  • Validity predicate: is a transaction valid, given the current state of the ledger.
  • State update: given that a transaction is valid, how to update the account state.

Miners apply the new transaction filter to every new transaction they receive in gossip, and ignore transactions that don’t pass the filter (the filter can specify that an existing mempool transaction should be replaced by the new one).

Once transactions are collected into a unified transaction block, transactions from the same account are sorted using the sorting algorithm (e.g., if the block contains the transactions A1,B1,A2,A3,B2, from accounts A and B, and the sorting algorithm specified that A1,A2,A3 should be in the order A2,A3,A1, then the sorted transactions would be A2,B1,A3,A1,B2).

After sorting, transactions are executed in order:

• first the validity predicate is computed. If the transaction doesn’t satisfy the validity predicate (at the point at which it is executed) the transaction is discarded. Otherwise,
• verify is executed. If verify fails, the transaction is discarded. Otherwise,
• the state update algorithm is executed for that transaction.

Implementation plan

tbd

Questions

• most of the generalized nonce algorithms can be specified as principal account handler methods "inside the VM", but filtering is different, both because it relies upon access to the entire mempool (data which are not available inside the VM), and because it's "subjective" on the part of miners. How do we handle this?

Dependencies and interactions

tbd

Stakeholders and reviewers

tbd

Testing and performance

tbd