search

ChainSafe / js-libp2p-gossipsub

TypeScript implementation of Gossipsub
Apache License 2.0
151 stars 43 forks source link

Dandelion Implementation / Spec #341

Open kaiserd opened 2 years ago

kaiserd commented 2 years ago

Background

As I am working on a Dandelion Vac RFC specifying Dandelion for Waku Relay (and by extension for libp2p, because Waku Relay builds on libp2p gossipsub), I was looking into current implementations and analyses beyond the Dandelion/Dandelion++ papers. The first goal is identifying anonymity properties, and, if possible, relaxations that yield lower latency but still beneficial anonymity properties.

js-libp2p-gossipsub Dandelion Implementation

The current implementation of js-libp2p-gossipsub does not follow the Dandelion and/or Dandelion++ approaches directly. It currently implements what the Dandelion paper refers to as "diffusion-by-proxy" with a fixed stem length (the implementation features an additional degree parameter for the anonymity phase, though).

In contrast, Dandelion

1) fixes the anonymity graph 2) has a probabilistic stem length 3) introduces random delay in the fluff phase (because it uses diffusion) which gossipsub does not do

Also, it introduces epochs and a fail-safe that diffuses messages if they are not received via fluff spreading after some time.

I wanted to ask if there is any analysis regarding the design choices made in the current implementation? It will improve latency, but (presumably) at the cost of lower entropy (i.e. higher recall / precision for the attacker).

Dandelion Vac Spec

Would any js-libp2p-gossipsub Dandelion contributor be interested in collaborating on a Vac RFC specifying Dandelion for libp2p gossipsub / Waku Relay? I am currently working on a first raw version as a basis for discussion. We are interested in trade-offs leaning towards lower latency at a low anonymity cost.

Further References

dapplion commented 2 years ago

CC: @noot @wemeetagain are you avail to participate in the spec-ing process?

noot commented 2 years ago

@kaiserd copy pasting my reply from discord:

hey, a potential solution being looked into is having the stem length be determined probabilistically, so the probability of a stem length of 3-5 is high and decreases after that. while receiving a higher stem length would make it more likely that the sender is the originator, it wouldn't be 100% guaranteed. the reason the stem length was fixed between 3-6 is to have a bound on latency which is critical for validators, but like you said hurts anonymity. the research on this is still ongoing 🙂

I'd be interested in potentially collaborating on this. would also be good to loop in @AtHeartEngineer since he's actively researching this as well.

AtHeartEngineer commented 2 years ago

I'd be interested in potentially collaborating on this. would also be good to loop in @AtHeartEngineer since he's actively researching this as well.

Yep I have been talking to @kaiserd some too. I'm going to figure out a good place for us all to talk/coordinate.

kaiserd commented 2 years ago

Awesome :). Thanks :).

kaiserd commented 2 years ago

For the time being, we could use the #network-privacy channel on the Vac discord. I'll send you invites :).

wemeetagain commented 1 month ago

@kaiserd are you still working on this?