zk-promises: Anonymous Moderation, Reputation, & Blocking from Anonymous Credentials with Callbacks

A novel framework called zk-promises is introduced, enabling stateful anonymous credentials with Turing-complete state machines and asynchronous callbacks. This allows for robust moderation, such as banning or reputation updates, for anonymous users without compromising their privacy, using zk-objects and zero-knowledge proofs to ensure state integrity.

September 23, 2025 4 min read

zk-promises: Anonymous Moderation, Reputation, & Blocking from Anonymous Credentials with Callbacks — source: https://www.youtube.com/watch?v=WCNyWjenepE

The central challenge addressed is enabling negative feedback—such as downvotes, reputation docking, or banning—for anonymous users in a way they cannot evade without being de-anonymized. The proposed solution, zk-promises, is an anonymous credential scheme with callbacks that allows for expressive, stateful interactions. It ensures that even malicious users must correctly update their own private state in response to asynchronous moderation actions.

Core Concepts: zk-objects and Callbacks

The foundation of zk-promises is the zk-object, a piece of client-side state that can be programmed with arbitrary logic. This object’s integrity is maintained through zero-knowledge proofs (ZKPs), which guarantee that any state transition is valid according to the pre-defined rules.

The process for a user to update their state and interact with a service works as follows:

A user holds their state (the zk-object) locally.
To perform an action, the user generates a ZKP proving that a state transition is valid. For example, they prove they are transitioning from a valid state SI to a new state SI+1.
This proof, along with a commitment to the new state and a nullifier for the old state, is sent to the server.
The server verifies the ZKP and checks that the nullifier for the old state SI has not been seen before. This prevents the user from rolling back their state or creating forks.
If the checks pass, the server signs the commitment to the new state SI+1, validating it for future interactions.

While zk-objects ensure correct state transitions initiated by the user, they do not inherently allow for third-party updates. This is where callbacks come in.

Callbacks are a form of asynchronous negative feedback. A server can issue a callback to a user, which can be an arbitrary function that mutates the user’s zk-object.

To implement this, each user action is associated with a random, unique tag. If a moderator decides an action was abusive, they post the corresponding tag to a public callback board.

To be considered valid, a user must periodically scan this board for any callbacks associated with their past actions.
When authenticating, the user must prove in zero-knowledge that they have scanned recently and have correctly applied any relevant callbacks to their zk-object.
This mechanism ensures that users cannot evade punishments like bans or reputation loss, as they are forced to process these updates to continue interacting with the system.

Technical Implementation and Efficiency

A naive implementation of scanning the callback board would be inefficient in a ZKP. To optimize this, the system uses a more advanced data structure:

Instead of a single list, the callback board is split into two Merkle trees: one containing the IDs of all issued callbacks and another tracking the ranges of IDs that have not been called.
To prove a callback has or has not been issued, a user only needs to provide a single Merkle membership proof for one of the two trees, which is significantly more efficient.

The system also addresses the indefinite growth of callback lists and state trees through mechanisms like callback expiry, pruning of old states, and epoch-based trees.

Addressing Sybil Attacks and Limitations

The programmability of zk-objects provides a defense against Sybil attacks, where a user simply creates a new account to evade punishment. The system can be designed to make new accounts less useful by requiring:

A minimum account age.
A certain reputation level to perform high-value actions.
Rate-limiting for new or low-reputation accounts.

A noted limitation is that the system cannot force a user to come online and process a “ban” callback. However, it ensures that if they wish to perform any future actions, they must first accept the punishment.

During the Q&A, a potential privacy leak was discussed: observing the callback board could link a specific callback to a user’s recent action. The proposed mitigation is to have the user reveal a hash of the tag and a secret nonce in public, while privately sending the nonce to the server for verification, breaking the public linkability.

Performance and Applications

Benchmarks of a Rust implementation demonstrate the system’s practicality. With complex logic including multi-dimensional reputation and rate-limiting, key operations are efficient:

Client Authorization: ~300-400 ms
Single Callback Scan: ~400-600 ms (amortized to ~150 ms with follow-up work)
Server Verification: ~2.8 ms (or 0.7 ms with batching)

These performance metrics suggest that zk-promises are feasible for real-world applications such as anonymous forums, Tor bridges, and risk scoring for cryptocurrency addresses.