TL;DR: Two more DoS mechanisms for Mix were explored beyond those in #598 — Blend’s Proof of Quota (PoQ) and ZXAD. Both are per-member rate-limiting solutions similar to RLN, but without slashing. Any per-member rate limit needs Sybil resistance, which RLN gets from a membership tree with staked registration. PoQ and ZXAD have their own, but on Mix they inherit the same tree. So there is one RLN family, with four constructions: live (A), cached (B), pre-computed (C), pre-computed with slashing (D). D is the one novel piece — it precomputes and keeps slashing, which C (adapted PoQ and ZXAD) lacks. On performance, precompute’s gain would be latency: for forwarded traffic it drops the delay floor live proving forces. So cached RLN is the shipped answer today, D the longer-term target.
Why the candidates are RLN-family
RLN does two jobs at once. Sybil resistance — a membership tree with staked registration makes each member costly to forge. Rate-limiting — the nullifier quota caps how much each member may send. The limit is per member, so the second rests on the first: it bounds total traffic only if acquiring new membership is costly — otherwise an attacker just registers more.
Both PoQ and ZXAD rate-limit per member too and have their own Sybil resistance mechanisms. PoQ caps each node to a quota of one-time keys, gated by membership. ZXAD caps each client to a quota of tokens, gated by a one-per-person credential. Adapt them to Mix and they inherit the membership tree as the Sybil layer — the gravity well that makes them RLN-family.
One way out is to rate-limit per message rather than per member — proof of work, or a VDF — which separates DoS from Sybil. #598 assessed both and set them aside: proof of work penalizes a mobile device far more than a well-resourced attacker, and a VDF’s verify-vs-compute advantage collapses at Mix’s short per-hop delays. So within Mix as it stands, the space is effectively RLN. The rest of this post maps that space.
The shared base
All four constructions share the RLN-v2 base and differ only in what happens after it.
Each staked member has a secret a_0, publishes a commitment to it as a leaf in a Merkle tree, and per epoch derives, for each slot k, a slope a_1 from the secret and a one-time nullifier from that slope. Together these define a line y = a_0 + a_1·x, where x = H(P) is the hash of the outgoing packet. One point on this line computationally hides a_0; two points from the same slot (same nullifier) reveal a_0, which is tied to the stake and slashed. That is the whole rate-limit-and-punish mechanism.
A caveat for all four: with free routing, a reused slot can land on different nodes, so cross-node detection is done over a DoS-protected coordination layer, where nodes share seen nullifiers and the points needed for slashing.
What changes is how the proof is produced and how the packet is bound to it.
A — RLN
Each hop generates a fresh zero-knowledge proof for the packet it forwards. The proof shows the prover is a member, is within quota (k < limit), and that the revealed share y = a_0 + a_1·x is correct for this exact packet — x = H(P) is a public input, so it is baked into the proof. Tampering with the packet breaks verification at the next hop; reusing a slot reveals a_0 and slashes. The cost is that the proof is generated live, on the forwarding path.
B — Cached RLN
Exactly A, but faster. Most of the work — the membership part — does not change between messages, so the prover computes it once and reuses it. The version already in zerokit runs around 60–70 ms on a modern laptop and is free, with no downside beyond a cheap per-root refresh. (A more aggressive optimization, Dynark, goes further but pays a heavy cost when the membership tree changes, and is not yet implemented.) Note that B is the practical way to be fast and keep slashing — it is the baseline the precompute constructions should be measured against, not live RLN.
C — Pre-computed
Here the whole authorization is prepared ahead of time as a token, so there is no proving at send time. Offline, the prover generates a one-time key and a proof binding it to their membership; the token carries no packet, so it can be built in idle moments. To send, the prover signs the packet with that key. It is fast — but pushing the packet out of the proof costs slashing: reuse now shows the same nullifier twice, so a duplicate can be detected and dropped, but the secret can no longer be recovered. This is PoQ (and ZXAD), adapted to Mix.
D — Pre-computed with slashing
D keeps C’s precomputed token but restores slashing, by binding the packet with a share instead of a signature. Offline, the prover commits the two line coefficients as Pedersen commitments C_0 = g^{a_0}·h^{r_0} and C_1 = g^{a_1}·h^{r_1}, with fresh blinds r_0, r_1. These are homomorphic — raising C_1 to the public value x and multiplying gives a commitment to the share itself:
C_0 · C_1^x = g^{(a_0 + a_1·x)} · h^{(r_0 + r_1·x)} = g^y · h^{r_y}
So at send time the prover reveals two numbers y, r_y — no proving — and each hop checks that one equation. The check does two jobs at once: it authenticates the share as a real point on the committed line, and it binds that point to this packet through x. Reuse a slot, and two points reveal a_0, exactly as in RLN. In one line: D is C with the signature swapped for a share.
D works on one condition: the commitments must be tied to the registered secret — built inside the proof from the same a_0 as the membership check — or a cheater commits a fake secret and slashing hits nothing. The rest is detail: the commitments live on an embedded curve (Baby Jubjub), so the line runs in a slightly smaller field. Building the commitments in-circuit roughly doubles proving time, but that cost is offline; on the wire it is about 352 B. A full construction — the commitment scheme, the field bridge, and the security argument — will follow in a companion post.
Is precompute actually worth it for Mix?
The Mix RLN spec floats pre-computed proofs as a possible replacement for live RLN — and the gain is real, just not the obvious one. A node can already prebuild proofs for the packets it originates or sends as cover, where the contents are known ahead. The hard case is forwarded traffic: the packet isn’t known until it arrives, so the proof is made live. Proving runs alongside the mixing delay, so it adds no latency by itself — the cost is the floor it forces on that delay: unless each hop delays at least as long as proving takes, the near-constant proof time becomes a fingerprint linking its incoming and outgoing packets. At the shipped defaults that floor stacks ~100 ms on a ~100 ms mean, doubling the per-hop delay (sizing it for slower hardware is still open).
Precompute removes the floor’s reason: the token carries no packet, so even forwarded traffic needs no live proof — just a signature (C) or a share (D) at send time. Throughput is another matter: the mix node is single-threaded, and proving runs on the same loop that forwards packets, so a precomputed pool built in the background would still block forwarding while it is computed. Getting proving onto a spare core needs a threading change, and that change would help live RLN just as much (Open Question 2). And precompute carries a cost: a token is pinned to a tree root, so as members join or leave, the pool ages out and must be rebuilt — and under sustained load it empties, falling back to live proving, floor and all (Open Question 5).
So precompute’s win would be latency — dropping the live-proving delay floor — not just cryptography. What D adds on top is what C gives up: slashing, with the proof precomputed.
In short
| A — RLN | B — Cached | C — Pre-computed | D — Pre-computed + slashing | |
|---|---|---|---|---|
| Proof | live | live, cached (free) | token | token |
| Binds packet with | share, in proof | share, in proof | signature | homomorphic share |
| On reuse | slash | slash | detect only | slash |
| Staleness under churn | none (forwarded) | cheap refresh | tokens go stale | tokens go stale |
| Wire | 288 B | 288 B | ~320 B | ~352 B |
All four are the same identity + tree + per-(epoch, k) derivation; they differ only on live vs pre-computed (A,B vs C,D) and how the packet is bound / what reuse does (in-proof share → slash for A,B; signature → detect for C; homomorphic share → slash for D).
Recommendation
Short term, Cached RLN — fast, slashing, free, already shipped. Longer term, D — precompute’s delay-floor win makes it worth the move once proving is off the forwarding loop, and D is the variant that still slashes. Dropping the tree entirely (proof of work, VDF) stays out of scope — see #598.
Open Questions
- The exact circuit cost of D’s smaller-field line — one compile settles it.
- Is a worker thread for proving worth doing on its own, given it helps live RLN and precompute alike?
- Can Sybil and DoS be separated after all, given #598 set proof-of-work and VDF aside?
- Can the delay floor actually go once proving leaves the forwarding path, or does something else still need it?
- Does the token pool survive real traffic, or does sustained load drain it straight back to live proving?