RLN with pre-computed proofs

[prem]

Token-Based RLN: Summary

What is it?

Token-Based RLN is a modification of the standard RLN-v2 protocol that enables offline precomputation of rate-limiting proofs for mixnet nodes. Instead of deriving the polynomial share parameter x from message content (requiring online computation), it’s derived from precomputed cryptographic tokens.

This works for per-hop proof generation in mixnets described in section 9.2.2 where each hop in mix path must generate RLN proofs when forwarding messages to the next hop.

Regular RLN requires proof generation per message at each hop, creating significant latency as a message is traversing through the mixnet.
With this approach, Mix nodes precompute proofs removing this latency.

Trade-off

Within-epoch linkability: Messages from the same mixnode can be correlated (observers can see “MixNode A sent N messages to MixNode B”). However, this is not a privacy concern in mixnets because:

• Linkability exists only at each hop level, not end-user traffic

• Different threat models: RLN protects mixnet DoS; mixnet protects user anonymity

How It Works

Phase 1: Token Generation

• Generate random epoch salt

• Compute deterministic tokens: token[i] = Hash(secretKey, epoch, i, epochSalt)

Phase 2: Proof Precomputation (Offline)

• For each token, generate complete ZK proof with polynomial share

• Store proofs for later use

Phase 3: Message Forwarding (Online)

• Select unused proof

• Attach to message (< 1ms operation)

Phase 4: Verification

• Verify ZK proof

• Check for duplicate nullifiers (spam detection)

• If duplicate found: recover secret key via Lagrange interpolation and slash

Circuit Modification

The only circuit change from standard RLN-v2:

// Standard RLN-v2: x derived from message

x = Hash(messageHash, epoch)

// Token-Based RLN: x derived from precomputed token

token = Hash(secretKey, epoch, messageId, epochSalt)

x = Hash(token, epoch)

All other components (membership verification, rate limit enforcement, nullifier computation, slashing) remain identical to RLN-v2.

Security

• Rate limiting enforced via nullifier tracking

• Spam detection through duplicate nullifier identification

• Secret key recovery and slashing via Shamir Secret Sharing

• Users cryptographically bound to their registered rate limits

Note that spent nullifiers still would require to be shared/gossipped so that any node can catch and slash/penalize offending user/node.

References

• Mixnet proposal: vacp2p/rfc-index#228

• Standard RLN: 17/WAKU2-RLN-RELAY

*Note that this proposal has been written with the help of AI. *
It still need to be thought through as message is not linked to the generated proof.
Needs review and evaluation for any obvious flaws

[haelius]

I might be missing the crux of the scheme here, but what prevents a malicious user from attaching the (exact) same proof to multiple different messages? I understand that from an RLN PoV this would be a duplicate - however, duplicates are not violations (they are often just deduplicated) and cannot be punished. You cannot slash duplicates (as the key share will be the same) and duplicate proofs would also not invalidate the message (as they do in the current implementation, if not computed over the message as signal). The only slashable violation would be double signalling, where the same rate limit counter and epoch is used to generate proofs for two different signals.

[ugur]

I agree with @haelius regarding the reuse of the same proof for different messages. One possible mitigation is to introduce a lightweight AEAD or MAC.

Consider a valid token–proof tuple (t, p), where the proof p is derived from the token t. Since p is not bound to the message, any message m can be arbitrarily attached to (t, p), and every such combination remains valid.

This can be mitigated by using a relatively lightweight AEAD or MAC with a key k, such as the "aes_key" or "mac_key" defined in RFC Section 8.2, which is already known to the sender and the receiver. Concretely, a message would be sent as:

(t, p, m, MAC_k(t || p || m))

This construction prevents (t, p) from being trivially reused with arbitrary messages, as generating a valid tag requires knowledge of k. However, this approach only mitigates issue rather than fully solving the problem.

[prem]

@haelius

what prevents a malicious user from attaching the (exact) same proof to multiple different messages? I understand that from an RLN PoV this would be a duplicate - however, duplicates are not violations (they are often just deduplicated) and cannot be punished.

Had a discussion with @ugur and we both think by augmenting the above approach with below suggestions we can make it work.

1. token is sent along with the message and each node would have to store and gossip token’s also(along with nullifier) for that and previous epoch to ensure token reuse across messages is prevented.
2. As @ugur suggested if we use the AES_key or mac_key that is already known to sender and receiver to sign the message, it prevents from token and proof being reused by other nodes.

The sender can still reuse proof and token for a different message, but then it would get detected as duplicate and dropped. So essentially spam gets prevented from propagation but no slashing in this case.

Also tried to compare Standard RLN(RLNv2) with this Token-based approach in terms of slashing and identified scenarios as below. Noticed that even standard RLN doesn’t provide protection from flooding, as a node can just generate 1 proof and attach the same to 10K messages and still send it. Which means there is some other outside protection i.e gossipSub scoring in case of Waku-Relay to protect from such cases. Even that is not a very strong protection as a node can keep changing its peerId to get around this.

Spam is detected and discarded in Standard RLN in below ways:

• replay (duplicate msg and proof) - discard
• invalid proof - discard (cannot reuse proof as it is tied to message hash)
• duplicate signal for same messageID - discard and slash

In Token-based approach mentioned above along with Ugur’s suggestion:

1. tokenId(supposed to be unique per message) is generated randomly
2. instead of messagehash tokenID is bound to proof(to help with pre-computation)

Spam scenarios and handling in suggested approach:

1. replay (same msg with token and proof) - identified and discarded in similar way
2. reuse of proof across different messages by same/different user - duplicate token/nullifier identified and discarded - This is not a very protection as spam can still spread before token/nullifier is gossipped.
3. duplicate signal for same messageID - discard and slash

This still requires further analysis/refinement for any other attack vectors, but seems like a good candidate for mix use-case atleast because it provides us with pre-computation which avoids latency.

We can consider adding some sort of mixnode local peerScoring logic if flooding is noticed by a node due to replay/proof-reuse as a sort of disincentivzation.

Would appreciate comments

@ugur Please add/correct if i have missed anything from our discussion.

[ugur]

Thank you @prem, this looks nice!

One small clarification for those who may be confused by the term signing:

@prem

to sign the message

Here, “signing” refers to creating an AEAD or MAC tag rather than a digital signature. Hash-based MACs are preferable, as in future versions a PoW instance could be integrated on top of them to introduce additional asymmetry.

[haelius]

Right, thanks for all the clarifications.

I think it depends on how much utility we gain from precomputing proofs vs. introducing these possible vulnerabilities.

Noticed that even standard RLN doesn’t provide protection from flooding, as a node can just generate 1 proof and attach the same to 10K messages and still send it.

The difference though, as far as I can see, is that within RLN-Relay the mechanism broadcasting the proofs is the same mechanism that you’re protecting against spam. In other words, duplicate messages get detected immediately within the RLN-Relay layer - if an attacker tries to get “ahead” of this, by flooding their duplicates to more nodes simultaneously, they’ll only succeed in these nodes adding those duplicates to their own seen caches faster and deduplicate any further copies. This limits the attack efficiency. Furthermore, a proof that wasn’t generated against the message it’s attached to will invalidate the message immediately on the routing layer (and cause the publisher to be descored). You’re right that peer ID cycling is possible here, but, again, invalid messages can never propagate in the network.

IIUC, with the proposed mechanism, deduplication and checking for message validity will be a race condition with the separate gossip layer. I imagine that a motivated attacker can get almost unlimited utility by just sending enough valid-looking messages, beating the gossip layer at just enough mix nodes that a fair percentage of them unwraps and remixes the message to the next hop before detecting the duplicate. Once the message has been forwarded, there’s no way to deduplicate it anymore, making the second hop a very easy DoS target. There’s no inherent way to detect message validity, in other words, so an attacker knows it can’t be punished for just continuing to flood until it has injected enough messages into mix paths to significantly deteriorate the network.

it provides us with pre-computation which avoids latency.

True. We can consider this as a possible tradeoff. Just noting again that introducing latency remains a feature of mixing - this will just set a minimum per-hop latency. This may be a more acceptable tradeoff. I checked the key benchmarks again (RLN Key Benchmarks | Waku Documentation) and note that RLN proof generation is around 150ms. We can use this when evaluating the benefit of either of the two approaches (pre-computed vs per-message proofs).

[prem]

@haelius

I think it depends on how much utility we gain from precomputing proofs vs. introducing these possible vulnerabilities.

Agreed, but i think we would have to pre-compute proofs for some use-cases as explained below.

@haelius

within RLN-Relay the mechanism broadcasting the proofs is the same mechanism that you’re protecting against spam. In other words, duplicate messages get detected immediately within the RLN-Relay layer - if an attacker tries to get “ahead” of this, by flooding their duplicates to more nodes simultaneously, they’ll only succeed in these nodes adding those duplicates to their own seen caches faster and deduplicate any further copies. This limits the attack efficiency.

Yes, Agreed.

@haelius

with the proposed mechanism, deduplication and checking for message validity will be a race condition with the separate gossip layer. I imagine that a motivated attacker can get almost unlimited utility by just sending enough valid-looking messages, beating the gossip layer at just enough mix nodes that a fair percentage of them unwraps and remixes the message to the next hop before detecting the duplicate. Once the message has been forwarded, there’s no way to deduplicate it anymore, making the second hop a very easy DoS target. There’s no inherent way to detect message validity, in other words, so an attacker knows it can’t be punished for just continuing to flood until it has injected enough messages into mix paths to significantly deteriorate the network.

This is a very good point and a loophole in this whole approach. If we can find a way to tie and verify message validity by using some sort of signing by node’s private-key and verifiable. This would address the issue to some level but introduce some additional computation cost.
Will think more on this problem.

@haelius

Just noting again that introducing latency remains a feature of mixing - this will just set a minimum per-hop latency. This may be a more acceptable tradeoff. I checked the key benchmarks again (RLN Key Benchmarks | Waku Documentation) and note that RLN proof generation is around 150ms. We can use this when evaluating the benefit of either of the two approaches (pre-computed vs per-message proofs).

Yep, but for a usecase like Logos-messaging having a 150ms latency per hop might not be acceptable in addition to processing and network latency. Because for publishing a message, it will have to go through 3 mix nodes + injected into gossipsub network which already has a ~4 node propagation(with RLN verification) to disseminate a message into the network.
Which is why it might make sense to pursue this kind of an approach of pre-computation.

For use-cases where this type of latency/delay is acceptable, we can probably consider using standard RLN itself.