In modern digital systems, users routinely interact with services that need to maintain state about them - from subscription services tracking usage limits to authentication systems recording login attempts. However, this state management traditionally requires users to trust service providers with their personal data, creating significant privacy concerns.
Anonymous credential systems (like U-Prove, Idemix, and zkSNARK-based approaches) allow users to prove properties about themselves without revealing their identity. However, these systems have a critical limitation: they are fundamentally stateless. Once issued, a credential cannot be updated - it can only be replaced with a newly issued credential. This requires reconnecting with the issuer for any state change, defeating true client-side state management.
Systems like Privacy Pass and rate-limiting tokens enable anonymous access while preventing abuse. However, these are often single-use tokens that can only be consumed once, not updated. This forces a choice between maintaining state centrally (sacrificing privacy) or issuing new credentials for each state change (sacrificing efficiency).
Due to these limitations, many systems resort to trusted server-based approaches, storing user state on servers and asking users to trust that their privacy won’t be violated. This creates an unnecessary gap between theoretical privacy protection and practical implementations.
Anonymous State Machines (ASMs) address these limitations by enabling:
Intuitively, an Anonymous State Machine is a way for a server to store state on the client, all the while updating and querying that state and keeping it authenticated by ensuring updates proceed according to a set of server-defined rules.
An Anonymous State Machine consists of the following types and protocols:
A state is a vector { v_i } ∈ [n]. There are state variables which are known to the issuer at issuance time P ⊆ [n]. There is a well known function Γ(v, τ) = { v_i } ∈ [n] for any transition τ ∈ T. There are two well known predicates:
Issuance takes place between a client and an issuer.
The issuer has:
The client has:
The issuance protocol:
By the end, the client will have an authentication code σ associated with { v_i }, k, r, without the issuer learning the client’s private state values or nullifier.
Transition takes place between a client and an issuer. The issuer maintains a database db of seen nullifiers.
The issuer has:
The client has:
The transition protocol:
By the end, the client will have an authentication code σ’ associated with Γ(v, τ), k’, r’ for new nullifier k’ and blinding factor r’. The issuer will be certain that:
Client Issuer
| |
| === ISSUANCE PROTOCOL === |
| |
|------- Request Initial State ------------>|
| |
|<---- Request public state vars {v_i}i∈P --|
| |
|-- Generate: |
| - secret blinding factor r |
| - secret nullifier k |
| - private state vars {v_i}i∈[n]\P |
| |
|-- Compute zero-knowledge proof ψ(v) ----->|
| (proves initial state is valid) |-- Verify ψ(v) is satisfied
| | (without learning private values)
| |
|<------ Issue Authentication Code σ -------|
| (for state v, nullifier k, r) |
| |
| === TRANSITION PROTOCOL === |
| |
|-- Generate: |
| - new secret blinding factor r' |
| - new secret nullifier k' |
| |
|-- Create proof of valid state with |
| authentication code σ |
| |
|-------- Transition Request -------------->|
| with: |
| - nullifier k (revealed) |-- Check if nullifier k
| - transition τ | exists in database
| - proof of valid state |-- If exists, reject
| - proof that ρ(v,τ) is satisfied | If not, add to database
| - commitment to: |
| * new nullifier k' |-- Verify state proof
| * new blinding factor r' |-- Verify ρ(v,τ) is satisfied
| * new state Γ(v,τ) |-- Compute new state Γ(v,τ)
| |
|<----- New Authentication Code σ' ---------|
| (for new state Γ(v,τ), |
| new nullifier k', new blinding r')|
| |
Anonymous State Machines provide a cryptographic solution to a fundamental tension in privacy-preserving systems: how to maintain updateable state without sacrificing privacy. Unlike traditional anonymous credential systems that can only be replaced but not updated, ASMs enable genuine stateful operations while preserving anonymity.
An Anonymous State Machine protocol allows an issuer to:
This model enables privacy-preserving state management where:
Anonymous State Machines can transform applications that currently require trusted servers for state management. By moving state to the client side while ensuring cryptographic integrity, ASMs enable:
This approach provides a powerful framework for privacy-preserving protocols where state needs to be maintained and validated while minimizing data exposure to the issuer.
The following examples demonstrate how Anonymous State Machines can be applied to real-world problems.
The Anonymous Credit Tokens are an example of an Anonymous State Machine. The state is a single element vector which contains the number of credits. The function Γ(v, τ) = v - τ, and the predicate ρ(v, τ) = v - τ ≤ 2l, where l is the maximum number of bits allowed in token denominations.
Advantages:
An Anonymous State Machine can implement privacy-preserving access control systems. In this example, the state vector v contains a set of permission flags v = [v_1, v_2, …, v_n] where each v_i represents a different permission (e.g., read, write, admin). The transition function Γ(v, τ) updates permissions based on authorized actions, where τ might represent “grant write access” or “revoke admin privileges”. The predicate ρ(v, τ) ensures that only authorized parties can modify permissions (e.g., only users with admin privileges can grant new permissions). This allows a client to prove they have specific permissions without revealing their identity or the full set of permissions they hold.
Advantages:
An Anonymous State Machine can power a private voting system where voters can prove their eligibility without revealing their identity. The state is a single element vector containing the index of the current election. Transitions increment this index by 1, representing a vote in the current election.
In this system, when a voter casts a ballot, their vote is bound to the transition validity proof in the Fiat-Shamir transform by including it as an input to a hash function. The transition includes the election index, so the predicate ρ(v, τ) verifies that the transition is valid for the current election index (preventing votes in past or future elections), while the transition function Γ(v, τ) = v + 1 moves to the next election. This ensures that each eligible voter can only vote once per election while keeping their identity anonymous.
Advantages:
An Anonymous State Machine can implement a privacy-preserving loyalty program that protects customer purchase history while allowing point redemption. The state vector consists of [total_points, tier_status], where total_points tracks accumulated rewards and tier_status represents the customer’s loyalty level (e.g., bronze, silver, gold).
The transition function Γ(v, τ) handles three types of transitions:
The predicate ρ(v, τ) ensures valid transitions by verifying:
The tier verification transition is particularly useful as it allows customers to selectively disclose only their loyalty tier to service providers (e.g., to access tier-specific benefits) without revealing their point balance or consuming their token. This transition uses a nullifier that can be regenerated deterministically for specific service providers, allowing repeated verification while maintaining unlinkability between different providers.
Advantages: