Feature: Dandelion-lite

[gfanti]

Just had a discussion with @AM5800 and @amiller about a possible alternative Dandelion implementation, which we call Dandelion-lite. Summary of 3 candidate approaches below:

(1) Dandelion
Described in detail in BIP 156.
Pros:

• Strong privacy guarantees (for a routing algorithm)
• Relatively lightweight (adds a few seconds of latency for a stem length of ~10)

Cons:

• Somewhat high complexity, especially for orphan transactions, RBF, etc
• Analysis does not cover what happens when a Dandelion route is changed
• Latency may be too high for Unit-e given focus on speed

(2) Dandelion-lite
The stem phase lasts only 1 hop before fluffing. Each node keeps track of only its own transactions that were sent to a dandelion relay, and starts an embargo timer for each such transaction. A note describing the protocol and analysis can be found here.
Pros:

• Simpler than Dandelion (no need for orphan handling)
• Privacy guarantees are similar to Dandelion when the adversary knows the graph (see linked document for analysis)
• Lower latency than Dandelion since stem phase is only 1 hop

Cons:

• More complex than doing nothing
• Worse privacy than Dandelion when the adversary does not know the graph

Diffusion
This is what is done now: send to each peer with independent exponential delays.
Pros:

• Already implemented
• Lowest latency of the 3 options

Cons:

• Poor privacy guarantees

We are currently leaning towards Dandelion-lite due to the simplicity of implementation, relatively low latency, and the fairly good privacy guarantees (compared to full Dandelion). I will also run some simulations on diffusion and upload them here so we can get a numeric comparison. Thoughts/comments welcome.