Sybil and DOS/Spam protection for libp2p mix

Logos
1

Introduction

This post discusses possible DOS/spam attacks faced by a free-route mixnet such as the one we are trying to design for Logos services and also suggests some possible solutions to address them.
We envision a pluggable DoS and Sybil protection: we will come up with a good default, but deployments that have some internal validation for trusted nodes should be able to just plug that in with a bit of tinkering.

Thinking about DOS/Spam protection of a mixnet

When we think of DOS/Spam protecting a mixnet, following are possible attack surfaces to analyze. There may be more, but as of now we are focusing on the most important ones listed below.

  1. whether an attacker can spam a mix node and bring it down or make it unusable. If this is possible, then the attacker can just bring the whole mixnet down or make it unusable.
  2. whether an attacker can spin up many mix nodes in the mixnet in order to deanonymize or compromise security of the users. This is similar to Sybil attack described for any computer system.

DOS/Spamming a mix node

Since mixnets use onion routing and fixed packet sizes, where each mix node transforms incoming messages before forwarding them, spam protection must be addressed at the individual node level rather than at the network level as a whole (unlike Waku-RLN-Relay).
Additionally, every node in the path must prove the message is not spam, not just the originator. This is because mixnet design ensures that newly injected messages are indistinguishable from forwarded messages, making each hop equally responsible for validation.

Sybil attack on the mixnet

Mixnets rely on the principle that a user cannot be deanonymized as long as there is at least one honest node in their chosen path. This makes two properties critical: a large node pool and random path selection. However, this security model breaks down if an attacker can spin-up numerous malicious nodes, polluting the node pool and increasing the probability of controlling all nodes in a user’s path. Therefore, protecting against Sybil attacks is essential for maintaining mixnet security.

Potential Solutions for Spam protection

The solution should consist of a membership mechanism probably guarded with some stake in order to address sybil issue and should also provide some sort of rate-limiting mechanism in order to prevent spam/DOS.

Any potential solution should retain mixnet anonymity properties such as sender/receiver unlinkability and also ensure any new identities introduced should remain unlinkable to the user. Note that it is ok if membership in the mixnet (i.e., being a participant) may be discerned.

Proof Of Work

Each mix node can do a proof-of-work and attach it before sending a message out i.e a node publishing a message or a node just relaying message it has received.

An advantage of this approach is since each mix node anyways adds a delay, instead of that they can just do this proof-of-work which would take time before sending the message out.

A major disadvantage of this technique is the fact that Logos nodes are heterogeneous in nature ranging from mobile devices to laptops to servers which means that a user with better hardware capacity can still spam the network.

We can think of using an algorithm like RandomX that Monero uses, but that would still require a large amount of RAM which would become infeasible for mobile devices.

This approach provides only spam/DOS protection. However there is no PoW algorithm that has properties of working with mobile devices and at the same time not provide huge advantage for other types of devices especially ones with higher resources. Hence this approach cannot be considered unless above condition is satisfied.

It would have to be combined with another membership based approach in order to provide sybil resistance.

Non-interactive VDF client puzzles

We can use non-interactive Verifiable Delay Function (VDF) client puzzles similar to the ones explained in this paper with some modifications to DOS/Spam protect the mixnet.

Following are some properties of such an approach which makes it suitable for our use-case

  • uses sequential computation and non-parallelizable hence fairness can be achieved in a heterogeneous network of devices
  • can be made non-interactive as explained in the paper which suits the case of mixnet as it reduces overhead of multiple interactions between the mix nodes
  • can be augmented with verifiable random inputs such as Logos Blockchain hash to handle pre-computation attacks
  • verification time far lower than proof-generation time
  • replay attack as mentioned in the paper can be addressed by adding additional puzzle inputs(such as peerId of next node) along with maintaining a local cache of recently seen messages
  • computation time varies little bit across device types (even best possible hardware will only gain ~10x - as per AI), this may benefit mixnet use case because entry nodes (all mobile devices would fall under) would only publish new messages into mixnet whereas intermediate/exit nodes (laptops and other devices) would relay other messages through the mixnet as well and hence have higher traffic than edge devices.

Considering the above advantages, we can come up with a solution by applying some modifications in comparison to the paper

  • use global pre-defined public parameters: hash function, Time Parameter, RSA modulus N
  • use Logos Blockchain hash for randomness
  • add peerID (next hop) in puzzle input to prevent replay attacks
  • maintain a local cache of recently seen messages to prevent replay attacks

Performance Considerations

The VDF approach requires careful parameter tuning:

  • Time parameter T determines the minimum delay per hop
  • Verification overhead is minimal (milliseconds)
  • Proof size adds approximately ~400 bytes to each message header

Here is a quick performance analysis done using AI

image
image1372×1192 219 KB

This approach only addresses DOS/spam protection and does not address sybil attacks. Hence this would have to be combined with an approach such as Semaphore that addresses sybil attacks.

Semaphore

Semaphore from PSE is an approach to maintain anonymous group membership which when stored on-chain and coupled with a stake would act as a very good mechanism to provide sybil resistance for the mixnet. Each mix node would have to attach some sort of signal/proof in each message that it sends out to indicate membership.

The Semaphore proof adds approximately 200-300 bytes to each message header. This approach only addresses sybil attack but can be coupled with other DOS/Spam protection approaches in order to provide complete protection to the mixnet.

Using a combination of 2 approaches would require including more data in the messageHeader which in turn would increase packetSize for each packet vs a single approach.

RLN

Rate Limiting Nullifiers is a well known privacy preserving Spam/DOS protection mechanism that is being used in Waku-Relay. This would make an easy and perfect candidate to be reused for protecting the mixnet as well since it is well tested and integrated in Waku-Relay. But since mixnet is unique in its own way as in each message in the path is unique and doesn’t traverse through all the nodes in the network. This would make it challenging to use RLN as is and needs to be adapted in order to be used.

A potential approach would be for each mix node (including entry and intermediary nodes) to attach RLN proofs to messages they send out or relay in the mixnet. As a message(not the underlying payload) transforms while traversing the mixnet (due to onion routing), the same RLN proof cannot be reused across nodes for verification. If the same proof is used at each hop, an observer would be able to link all transformed messages and deanonymize users, breaking the core anonymity property of the mixnet.

Another challenge with RLN is that mix nodes are unaware of already-spent nullifiers since the mixnet is not a broadcast network like Waku-Relay. This enables replay attacks where a user can generate one RLN proof and send the same message to every node in the mixnet, exceeding their rate limit. To address this, an additional gossip layer would be needed for mix nodes to broadcast used nullifiers, enabling detection and stake slashing of cheaters. This augmented RLN approach assumes the gossip layer itself is spam-protected, likely using another RLN instance.

This approach addresses both spam protection and sybil attacks as memberships are baked into its design.

Ticket based - economically protected

Use some sort of a ticket-based system where each message published or relayed through the mixnet requires a cryptographic ticket issued based on prior purchase or stake. This approach provides both economic incentives for mix nodes to perform regular operations and natural spam deterrence through cost-per-message economics. The design could be similar to HOPR’s Proof-of-Relay mechanism or can be completely different and should be thought through considering Logos mixnet design.

Key Properties

  • Spam Protection: Economic cost per message naturally rate-limits abuse
  • Sybil Resistance: Nodes must stake capital to obtain ticket-issuing credentials
  • Economic Incentivization: Mix nodes earn revenue for relaying messages, moving beyond tit-for-tat assumptions
  • Privacy Considerations: Ticket validation must not compromise sender anonymity or enable message linking

Integration with Logos Incentivization

This approach directly ties into tokenomics and the broader incentivization framework being researched separately for Logos services. Key integration points include:

  • Off-chain payment protocols for ticket purchase
  • Stake slashing mechanisms for misbehavior
  • Revenue distribution to relay nodes
  • Ticket pricing that balances accessibility with spam prevention

Research Requirements

Significant research is needed to:

  1. Determine if HOPR’s specific ticket mechanism suits Logos mixnet’s free-route architecture
  2. Design privacy-preserving ticket issuance and validation protocols
  3. Model economic parameters (ticket pricing, stake requirements, revenue distribution)
  4. Integrate with the ongoing incentivization work for Logos services

Recommendation: Consider this a long-term approach to be pursued once the incentivization framework becomes more concrete and a short-term spam protection solution is operational.

Comparison of Approaches

Note that this table was generated using AI, so information such as overhead would be an approximation.

Approach Spam Protection Sybil Resistance Mobile-Friendly Message Overhead
PoW ✓ ✗ ✗ ~32 bytes
VDF Puzzles ✓ ✗ ✓ ~400 bytes
Semaphore ✗ ✓ ✓ ~200-300 bytes
RLN ✓ ✓ ✓ ~300 bytes
Tickets ✓ ✓ ✓ ~100-200 bytes
VDF + Semaphore ✓ ✓ ✓ ~700 bytes

Recommendations

Based on the analysis above:

Short-term

Option-1: Implement VDF-based puzzles combined with Semaphore for membership, as this provides both spam protection and sybil resistance while remaining mobile-friendly. This combination offers:

  • Fair resource usage across heterogeneous devices
  • Strong sybil resistance through staked membership
  • Reasonable message overhead (~400-800 bytes)
  • No additional gossiping required

This does require some research into the VDF puzzle suggested by the referenced paper.

Option-2: Investigate adapted RLN approach. Use Logos-Messaging/Waku-Relay for nullifier gossip as it already has spam protection via another RLN.

Long-term

Integrate with economic incentivization models using ticket-based systems as the tokenomics mature. This aligns with broader Logos service incentivization work.

Open Questions

These are some of the open questions that require further thought and inputs.

  1. how memberships(whichever approach chosen) would be distributed for Logos installations in order to have sybil resistance? We want each Logos installation node to participate in the mixnet but at the same time want to prevent attackers from creating numerous installations to conduct Sybil attacks. What’s the tradeoff between accessibility (easy onboarding for legitimate users) vs. security (preventing fake installations)?
  2. how do we ensure that there are significant intermediate/exit nodes(core nodes) in the mixnet and not end up with having too many entry nodes(mobile devices/edge nodes)? The side effect of this would be that number of nodes to relay messages would be far lesser than nodes only sending messages and would lead to network bottlenecks and poor message throughput. What incentives can encourage core node operation, and how do we prevent a “tragedy of the commons” where everyone wants to use the mixnet but few want to run relay nodes?
  3. how much should be the rate-limit for a node in mixnet to send messages? We should ideally have differentiated rate limits based on role of the mix node i.e entry only node might get lower rate limit and intermediate nodes should get higher rate limits as they also relay/forward other’s messages.
  4. what specific behaviors should trigger stake slashing? How to detect and prove misbehavior in a privacy-preserving way without compromising the unlinkability properties of the mixnet?

Potential Next Steps??

  1. Short Term implementation: Further analyze the chosen approach and build proof-of-concept or do a POC with RLN
  2. Design membership stake requirements: Economic analysis to determine optimal stake amounts for sybil resistance

Would appreciate feedback/comments wrt above approaches so that further steps can be taken.
Also would be happy to analyze any alternative approaches that get proposed. :slight_smile:

5 Likes
2

Thank you for the detailed post!

Perhaps a naive question: do we necessarily need a separate Sybil protection mechanism assuming we have DoS protection? For example, if every node must do some PoW-like work (or VDF), do we care how many nodes join?

You write that for VDF + Semaphore option

No additional gossiping required

but how would I check if your Semaphore membership is valid if I don’t have the current membership set? And in order to sync with the membership set, we need to gossip about who recently joined and left - is that true?

More generally, I’m thinking along the following lines. Sure, we want to protect against Sybil attacks, and fundamentally we have two avenues, just as you outline: puzzle-like (PoW, VFD) and membership-like (Semaphore, RLN). The benefit of puzzles, the way I see them, is that a puzzle solution doesn’t require global synchronization to be checked. In contrast, to check if a membership is valid, the verifier needs to know the up-to-date membership set. So my thinking is: are membership-based approaches even worth it? We would burden all nodes with membership set sync, whereas a resourceful attacker would still be able to register multiple memberships similar to producing multiple puzzle solutions. We could limit access to membership creation, but that would introduce a central point of failure. In other words: an attacker can direct resources either to puzzle solving or to creating Sybil identities with equivalent results; however from a user’s perspective protecting against Sybils introduces sync complexities, while puzzles are self-contained and require no extra communication.

Does this reasoning make sense?

3

well, proof of work only ensure there is no spam inside the mixnet. But Sybil protection is required to ensure an attacker doesn’t spawn too many nodes that would end up breaking up mixnet’s anonymity itself. It is not about how many nodes join, but rather an adversary/attacker spinning up many nodes so that the mix node pool is polluted.

well, if the membership is stored on-chain then it would automatically get synced. Ofcourse one of the assumptions we have been making here is that either RLN/semaphore or any sort of membership set is on-chain. Maybe it was not explicitly mentioned, but thanks for pointing it out.

not if membership set is stored on chain. kind of like how RLN memberships get synced currently in case of Waku. Gossip is not used, rather chain events are monitored. I mean the underlying blockchain would anyways gossip these details.

Also note that we are assuming that Logos Blockchain would also be running on all the nodes in some form i.e either as node syncing required state or edge nodes might be using some form of blockchain light mode(not clear on this yet). I think this should be mentioned as an assumption to get clarity.

well, all the membership approaches are carrying an underlying assumption that some sort of an econonic stake/ some other form of check prevents users from just creating memberships very easily. I agree this is not clear at this point, but we need to have some sort of strong mechanism from preventing too many memberships easily by someone. Not sure what it is at this point though, which is why i added an open question on how memberships would be distributed for Logos installations in general.

The idea is to identify some sort of decentralized membership mechanism like Semaphore/RLN which probably would most probably be on-chain to avoid centralization. Do note that puzzle solving is just to protect spam/DOS in the mixnet and Sybil protection is required to preserve anonymity of users and both of these have very different aims. So we are looking at 2 different types of attackers/adversaries. An attacker who wants to just spam and maybe make mixnet unusable, and a second type whose objective is not to spam the network but create many nodes in order to observe and analyze traffic who inturn would deanonymize/link users to the data.

4

Sybil

I don’t think sybil protection for a completely open and fully anonymous (fully unidentified) mixnet is possible. You’d need some further constraint.

For example, nodes serving in a mixnet would credential themselves instead of being completely anonymous: e.g. “operated by IFT”; they would present a signed certificate bound to their address (say their address resolves some DNSSEC domain or whatever). Then, nodes that will use the mixnet will demand somehow that the route include only nodes that can certify that they belong to the identity sets that they trust.

I’d do that and just declare automatic victory over “mixnet sybil” and never look at this problem ever again. If users think the mixnet is in a healthy state overall and for their particular use cases they don’t need to be maximally paranoid, they’d just send and empty ID set in their request (meaning do whatever route). And that is what would happen if the economics and the concrete deployment situation at year YYYY is good.

And these IDs can be completely pseudonymous. All you need is the ability to determine that N nodes (where N can even be 1) serving the mixnet share the same cryptographic identity, which doesn’t need to map to some real-world identity. But over time say N=100 nodes in the mixnet look like they are doing a good job, then users will choose to trust them (it’s on them, ultimately). The shared cryptographic identity is just so that users don’t have to create massive sets that are per-host, because what matters in a mixnet is who is ultimately operating them, and a private key is known by one operator, so all these nodes are operated by the same guy so they’re all honest or all malicious simultaneously.

DoS

I didn’t even know VDFs could be mobile friendly. Math is hard. That’s just awesome.

Since that exists, I’d say just use that plus ID the mixnet nodes and that’s a prod V1 wrapped much faster (potentially). You can then release a V2 mixnet later with a more sophisticated model. The great thing about mixnets is that you can have more than one mixnet, so implementing another one later can be completely disjoint from what you did before. Just give it a different name so people can choose which one to run. Then later you can do V3 etc.

Remainder

The last thing is "does the default logos suite install come with “trust any mixnet node” or “trust the IFT and the Ethereum foundation and … rest of curated list”. I’d just set it at default (trust everyone) and establish in the docs that privacy is a responsibility: you have to take charge of it, and not rely on whatever the default is if that’s actually important to you (both defaults are equally good IMO).

EDIT: Actually, the ID thing is a little bit more complicated. Let’s say you trust some entity that provides commentary (analysis) on the network itself. They would sign and publish some graylist or blacklist, and when you send a message to the mixnet, you could say, “exclude the nodes in this list published by this entity/domain”, instead of naming 1,000 hostnames to exclude that have been already unmasked by the community as operated by some adversary.

5

Thanks for the clarification! Now this makes more sense for me: we have two implementation options for syncing the membership set: a separate gossip layer vs piggy-backing on the underlying blockchain which we keep track of anyway.

I’d note also that for a chain-based membership we should address edge cases originating from the fact that our time granularity is one block time. Strictly speaking, on verifying every message, I need to wait for the next block to check whether the membership set has changed. (Moreover, that assumes that all transactions that update the all membership get included in the next block.)

6

Thanks for this write-up!

Two minor meta-comments that might make this post more easy to refer to in future:

  • technically we’re dealing with two related, but separate problems: DoS protection and Sybil protection. This is clear in the body of the post, but perhaps we can change the title to reflect this (“Sybil and DoS protection for libp2p mix”)?
  • I’d make it clear that we envision pluggable DoS and Sybil protection: we will come up with a good default, but deployments that have some internal validation for trusted nodes should be able to just plug that in with a bit of tinkering.

The fact that we already have implemented RLN primitives is quite a big advantage. The other advantage is that we probably expect that nodes will already have an RLN membership for communication (and other) purposes. This may/may not be directly reusable, but could at least provide a solid starting point. Another thing is that RLN provides us with a way to punish (slash) at least one type of bad actor (spammers, that is, not Sybils) which gives it a bit more teeth.

1 Like
7

Thanks! updated the post.

I agree that we have the primitives implemented, but while analyzing VDF client puzzles i did realize that our mixnet would require different rate limits for types of nodes: edge nodes that only act as entry nodes vs core/relay nodes that also relay other mix traffic in the network that would require higher rate limits than edge nodes. I am not sure at this point what the differentiation would look like.
Can we achieve the same with current RLN? cc @ugur
We could start with a first iteration that all nodes would have same rate limits, but this would have to addressed before going for production level deployments.
Also agree that we can assume that underlying Logos-Messaging would already have RLN available and hence we can use it for gossipping nullifiers.

When i think about spam protecting a mixnet, wondering if rate limiting is a way to go or using some sort of POW/VDF to slow down senders makes more sense. I feel inclined to choose the later approach of using VDF. WDYT?

8

Yep, but i guess since it is for spam protection or sybil protection having a short syncing delay such as block-time might be fine as the extent of damange that can be done would be negligible in a short window(which would generally be few seconds/minutes).

9

Agreed, which is why there needs to be some form of membership required for nodes to be part of mixnet in order to give sybil protection.

which is why the proposal is to use anonymous credentials such as RLN/semaphore so that nodes can participate in the mixnet without loosing their anonymity. That being said a node’s participation in the mixnet would become known unless we use some sort of means to obscure mixnet traffic as regular internet traffic.
The idea is for none of the nodes to be operated by IFT and rather be completely decentralized except for bootstrapping into the network.

Any specific reason to use same cryptographic identity when we have anonymous credentials like RLN available?

This would just be a bootstrap list into the network and mix-nodes will be discovered by existing discovery mechanisms. Not sure if we plan to have a curated list as at this point we are thinking of a free-route mixnet which doesn’t have a predefined set of nodes defined somewhere.

wdym by trusted entity? are you talking about some sort of reputation system? that in itself would be a complex thing to design in order to make it decentralized and anonymous. Maybe this is somthing that would be required eventually to somehow identify nodes that don’t provide proper service etc…but i would not consider having this kind of a system at this early stage.

10

Agreed, which is why there needs to be some form of membership required for nodes to be part of mixnet in order to give sybil protection.

I have Many Thoughts ™ on this, but the TLDR is yes, you’re right. Requiring a paid membership for a node to serve as one real mixnet node available for selection is a good thing overall and helps with the actual Sybil attack problem (i.e. I have to select 3 nodes, and I don’t want this 100,000-node botnet to be in the bag for selection).

What I would advise is to steer all the way clear from any staking/slashing model. Like, don’t do this at all, ever. For reasons. I know some blockchain projects are doing this (Lokinet?) but I think this is a Very Bad Idea.

Any specific reason to use same cryptographic identity when we have anonymous credentials like RLN available?

I was trying to see if we could have a simpler system with no RLN and no blockchain registration – they are available, but they are just more work. I think RLN is winning, so that whole node-IDs-filtered-by-client-requests idea can be discarded.

wdym by trusted entity? are you talking about some sort of reputation system? that in itself would be a complex thing to design in order to make it decentralized and anonymous. Maybe this is somthing that would be required eventually to somehow identify nodes that don’t provide proper service etc…but i would not consider having this kind of a system at this early stage.

Not designing a reputation system, but pushing the entire problem to the client. A reputation system tries to measure the worth of identities and determine which identities to use. The reputation system in the idea I presented would be “whatever users think is safe.” But that idea has its own complexities. It’s trying to do something more like what Tor does, which is not what is wanted here, I think.

11

If this is a question about general RLN capabilities - yes, we can have differentiated rate-limits in the current version of RLN (introduced in “v2”). We already have that deployed on testnet for TWN where you could theoretically get a bigger rate limit for a higher deposit.

My understanding of Tor’s “directory authorities” is that they help clients build circuits that are probably not entirely controlled by Sybils through a range of techniques that limits nodes’ possible influence based on some metrics that could indicate trustworthiness. I do think there’re some things to be inspired by in their approach, e.g. being flexible enough to allow clients to introduce their own trusted lists (self-hosted/via directories) on top of the RLN/Semaphore membership mechanism. Tor also has the concept of “guards” as entry nodes that have proven themselves across a range of metrics (esp. over time, which is a great mitigator of short-term massive Sybil attacks). We can perhaps adapt this concept to include our version of “guards” from some higher-confidence list in every mix route.

12

I’m going to shamelessly sidestep the technical suggestion here and pull another perspective out of my ass:

I’m thinking that the overall solution, whatever it is, is centered on what, or who, the nodes serving the network are.

  1. Projects like Tor: volunteer sysops for the love of it (high expertise, exclusive participation in server-side, open client-side)
  2. Typical blockchain system (chain node, mixnet, or otherwise): businesses (stake say $100 ~ $10K, get an income, misbehave and get “slashed”)
  3. Typical P2P system: people at home spin up a node and that’s it

So we have Things Like Tor (type 1), Thinks Like Lokinet (type 2), and let’s say I2P (type 3). Type 1 participates for the glory/flex/skills/activism; type 2 participates to obtain income primarily (and the other type 1 motives secondarily), type 3 also participates for the love of it (with minimal expertise and resourcing required) and/or for the resourcing tit-for-tat.

I’m more worried that Logos may get stuck between type 2 and type 3 for sourcing its nodes, and that’s not exclusive to mixnet, but more like a general (potential) problem.

That pretty much sums up the extent of my (very limited) usefulness to this discussion. I’m just worried that if you try to source type 3 volunteers, or a mix of 2 and 3, you may end up with problems amassing volunteer nodes. I guess going all-in type 2 and putting stake and slashing, etc. would be a self-consistent decision and could work (in that case slashing becomes potentially a Very Good Idea).

Both type 1 and type 2 are tolerant of more complex setups with registrations and stakes, etc. I think type 3 is more sensitive to those.

1 Like
13

Alright, was not aware of that. I was thinking RLNv3 is required for differentiated rate limits (i.e each member can purchase different rates by varying stake). I thought v2 only introduced x rate per epoch rather than 1 per epoch. Thanks for clarifying!

Thanks! Will go through this to get an idea and see if something fits our use-cases.

Is this some sort of not-so-strict reputation system based on client’s input?

sounds like reputation model, Thanks will go through the details to understand more.

14

Thanks a lot for this! This made me think of how logos would be deployed ultimately and also look at I2P. I will dig deeper into I2P as well to understand how they solve various attack vectors.

AFAIU, Logos would be deployed as type1 and type-3 as you mentioned above i.e users running on home laptops and setups to access dapps on Logos. Apart from this i would assume there would be users running various other types of Logos nodes maybe on servers either at-home or on the cloud etc. These would be users who would be running e.g some sort of pinning service for storage, or specialized nodes. Note that all users atleast in the begining participanting in the mixnet are doing it based on tit-for-tat model only. Maybe at a later stage we can think of incentivization as explained in the original post.

Briefly looking at I2P which uses a Proof-Of-Work mechanism for new nodes to prevent sybil attacks, maybe something like this can be thought of:
what if we think of an approach where any new node joining the mixnet can be considered only to either act as entry/exit node and not act as relay node in the mixnet i.e either it can use mixnet to send traffic or provide services over the mixnet where it acts as exit/service node. In the meantime in the background it can keep solving VDF puzzles and prove that it is not some attacker trying to take over the mixnet and once maybe it solves enough puzzles with some time limit of e.g few days then it can publicize itself as intermediate node.
As most new nodes are going to be either service-consumers/providers they would be fine just acting as entry/exit nodes. Another advantage is we don’t have to worry how to allocate membership for such nodes as they would gain membership maybe after successfully solving these long puzzles.
An approach like this would require to tie some sort of anonymous identity to the node which can be probable backed by some capital/stake(or some other mechanism).
WDYT @haelius

15

Regarding VDFs, I want to bring up a term that I find important, “asymmetry”.

VDFs are good in terms of asymmetry, because the attacker pays 50x workload and you verify this just x. You benefit basically 49x against the attacker. In literature, VDFs are considered for use in consensus mechanisms with big inputs such as 1 second, which is meaningful for the benefits of this asymmetry. But in low delay operations, such as 50-100 ms around (if this is more for each hop, total libp2p-mix delay gets increased too much), this 49x benefits VDF’s symmetry is getting less beneficial since verifying VDF takes more time in terms of proportion than calculating. The spam attacker can abuse this advantage to send invalid VDF calculations to execute DOS attacks on the mixnet instances. This can be feasible since VDF calculations work in a single core, so with the rest of the free cores, the attacker can create more invalid VDFs.

As Prem stated here, RandomX cannot be suitable for mobile devices; Equihash can provide a fairer and easier solution among mobile and powerful devices because its similar high-end RAM of laptops and mobiles, also asymmetry here is far more than VDFs, so the attack above is not valid here. It’s ref implementation here.

1 Like
16

This is a very good point. Thanks for analyzing VDFs!
So we can’t use VDF’s for spam protection, but as i proposed above maybe we can use VDF as a way for new nodes to be delayed adding to mixnet intermediate nodes?
You also make a valid point that a user with multiple CPU’s can still create/generate multiple VDF’s in comparison to a user with lesser
CPU’s.

These points make VDF an infeasible option for spam protection.

Interesting, taking a quick look this indeed seems like an interesting algo to use for client puzzles which is mobile friendly. But i am wondering what would be the best option for a mixnet i.e between POW-like vs rate limits because the behaviour of both is different eventhough both are solutions for spam prevention. I will think little more on these two types of methodologies and pros/cons of using each type so that we can decide which one to use.

17

While thinking of potential default Spam protection approach for Logos mixnet, realized it is good to analyze the approaches discussed above.

Rate-Limit vs PoW-like Approaches for Spam Protection

When evaluating DOS/Spam protection for mixnets, particularly for Logos installations using free-route mixnets, approaches fall under two main categories:

  1. Rate limit approaches(e.g. RLN)
  2. Proof-of-Work (PoW) like approaches like equihash

Rate-Limit Based Approaches

Benefits

  • Predictable bandwidth: Rate limits can be defined globally based on bandwidth analysis (similar to Waku-Relay’s approach for TWN default network rate-limits) with some changes such as intermediate/relay nodes would need to have higher rate limits than entry only nodes.

  • Resource planning: Each node can anticipate and plan for bandwidth requirements

Challenges

  • Bandwidth availability uncertainty: During path construction, it’s difficult to know if a node has available bandwidth in the current epoch. Success depends on network traffic patterns

  • Risks/Challenges: Messages may be dropped if bandwidth is exhausted. Messages can be delayed to the next rate-limit epoch, but this is problematic because:

Bandwidth Problem

Should Logos nodes declare the bandwidth they will provide to the mixnet? If yes, Rate-limits can be set more accurately per node.
Challenge is how to determine real-time bandwidth availability for nodes in a path?

  • Circuits (like Tor): Circuits reserve resources during setup which ensures this problem doesn’t happen
  • Per-message paths: Overcoming Rate-limits can cause drops even for legitimate traffi

PoW-like Systems

Benefits

  • Guaranteed delivery: Messages sent into the mixnet won’t be dropped due to rate-limit thresholds (assuming nodes remain online). They may get delayed though.

  • No epoch-based dropping: Unlike rate limit-based systems, messages aren’t rejected for exceeding bandwidth allocations

Challenges

  • Hardware-dependent rates
    Different hardware configurations result in varying rate-limits, even with algorithms like Equihash. Nodes have different publishing rates based on their puzzle-solving capabilities. Even with relatively modest variance (10-20x between mobile and workstation), this creates inconsistent network behavior

  • Message queueing: When a mix-node receives many messages to process and forward, delays become unpredictable. Solving puzzles for each message leads to Message queue buildup and Increased processing delays

  • Implicit rate-limits: Nodes effectively have a de facto rate-limit based on hardware capabilities, type of PoW algorithm used, message processing capacity

Applicability Across Use Cases

Currently Logos mixnet usecases can be categorized as below

  • Per Message Path selection: e.g In case of Logos Messaging, the bandwidth estimation and delay challenges discussed are most relevant here, as each message selects a new mix path.

  • Circuits: e.g In case of Logos Storage, these issues are less problematic since circuits are built through the mix (albeit short-lived), allowing nodes in the path to allocate resources like bandwidth during circuit setup.

Both approaches fail to fully address bandwidth and bandwidth limit issues. Both can lead to delays or packet dropping when device resource limits are reached.

Based on the above it looks like RLN would be a good choice to consider as a first Spam prevention for mixnet especially since we are considering integrating Logos Messaging which already has rate-limits implemented on its own gossipsub layer. This helps with propagating the used nullifiers to all nodes as explained in approach of using RLN.

Any comments/suggestions are welcome!

18

Approaches to integration spam protection into the Mix protocol

On further analyzing how to plug spam protection into mix protocol especially considering sphinx packet format, there seem to be two distinct approaches for spam protection integration into mix protocol. This update highlights the approaches and also indicate the viability of different spam protection methods.

For more details on these approaches, see PR #228.

Approach 1: Sender-Generated Per-Hop Proofs

In this approach, the sender pre-generates spam protection proofs for all hops and embeds them in the encrypted routing header (β).

  • Proofs are encrypted within β and bound to the decrypted payload state (δ’)

  • This means proofs can only be verified AFTER expensive Sphinx operations: session key derivation, replay checking, header integrity verification, and decryption of β and δ

Implication for DoS protection:

Nodes must perform costly cryptographic operations before detecting spam. Deployments using this approach should implement additional network-level protections (connection rate limiting, localized peer reputation) to defend against volumetric attacks targeting Sphinx decryption.

Approach 2: Per-Hop Proof Generation

In this approach, each node generates a fresh proof for the next hop, added as a new header field (σ) alongside the standard Sphinx fields.

When each node generates proofs for forwarded packets, a fundamental availability problem emerges from the interaction between random path selection and per-node processing capacity:

  • Intermediate nodes may exhaust their processing capacity (rate limits or computational capacity) due to random path selection by multiple independent senders

  • Legitimate packets get delayed or dropped even when no individual sender is misbehaving

Example scenario with RLN (predictable/fixed bottleneck):

  1. Mix node A has rate limit of 100 messages/epoch

  2. In one epoch, 50 different senders independently select Node A in their random paths

  3. Each sender sends 3 messages → 150 messages route through Node A

  4. Result: Node A must drop 50 legitimate messages

Similar issue with PoW like approaches (capacity-based bottleneck)

Key distinction:

  • RLN: Bottleneck is predictable and fixed by protocol (e.g., 100 msgs/epoch regardless of hardware)

  • PoW like approaches: Bottleneck is capacity-based and varies by node hardware, but still creates availability issues

This happens because path selection is uncoordinated and random across all senders, making popular nodes unavailable regardless of individual sender behavior or bottleneck type.

Advantage - Early verification:

Proofs can be verified BEFORE any Sphinx processing, providing better DoS protection by rejecting spam earlier without wasting computational resources.

Trade-off consideration:

While this approach provides early verification benefits, it inherently suffers from capacity bottlenecks at popular/hotspot nodes regardless of spam protection method. The severity depends on whether bottlenecks are predictable (RLN) or capacity-based (PoW), but availability issues persist in both cases.

Key Takeaway

Per-hop proof generation creates a fundamental capacity bottleneck at popular nodes due to uncoordinated random path selection, regardless of the spam protection method used. The key distinction is:

  • Predictable bottleneck (RLN): Fixed protocol-level rate limits cause deterministic packet drops

  • Capacity-based bottleneck (PoW/VDF): Hardware limitations cause variable delays or drops depending on node capabilities

Practical implications:

  • RLN: The predictable bottleneck makes per-hop generation particularly problematic - sender-generated approach is strongly preferred despite late verification drawbacks

  • PoW/VDF: The capacity-based bottleneck is more flexible (upgradeable hardware, varies by node), but availability issues still persist.

Sender-generated per-hop proofs avoid the bottleneck entirely by shifting all proof generation to the sender, making nodes pure verifiers. This eliminates capacity constraints at intermediate nodes at the cost of higher sender burden and late verification timing.

Header Overhead Comparison

Sender-Generated (L=5 hops): ~1360 bytes overhead (payload: 3984 → 2624 bytes)

Per-Hop Generation: ~272 bytes overhead (payload: 3984 → 3712 bytes)

Per-hop has lower overhead but suffers from rate-limit bottleneck, making it impractical for RLN.

cc @ugur

1 Like
19

Would it be correct to say that an attacker with much resources (RLN or compute) could choose mix paths in such a way to DOS specific nodes?

Since paths can be chosen, attacks are inevitable no?

Is increasing the cost of attacks the only mitigation possible?

1 Like
20

I guess rate limits and memberships for RLN (which seems to be first choice) is something that needs to be thought through. I am not sure if we should provide same rate limits to everyone in the network. Maybe nodes with sender roles will have 1 type of rate limit and intermediate nodes would have n times rate limit of senders. This just reduces chance of intermediate nodes getting overloaded.

One way is for the intermediate nodes would delay and queue the packets beyond their limits.

Well, kind-of yes i would say which is why a rate-limited mechanism would reduce attack surface as mentioned above.

This is definitely one way.
Long term goal to solve this would be via incentivization and paying for mix services to prevent spam.

1 Like