dandelion stem pool

stempool.md

Protocols like Dandelion, Dandelion++, Dandelion-Lite, and Clover have been designed to improve privacy when broadcasting a transaction to the bitcoin p2p network: the idea being that rather than simply flooding each transaction to every peer, you have an initial limited relay of the transaction prior to flood broadcast with the result being that it's unlikely for an attacker to be in the initial set of nodes that see the transaction during the limited relay, and that an external attacker can't distinguish the originator of the transaction from other nodes within the initial set.

Refs:

• Dandelion: https://dl.acm.org/doi/pdf/10.1145/3084459
• Dandelion++: https://dl.acm.org/doi/pdf/10.1145/3224424
• Clover: https://link.springer.com/content/pdf/10.1007/s12083-021-01241-z.pdf
• Anonymity Properties: https://arxiv.org/pdf/1703.08761.pdf
• Bitcoin PR: bitcoin/bitcoin#13947
• Bitcoin issue: bitcoin/bitcoin#20203
• Suhas on dandelion DDoS vectors https://bitcoin.stackexchange.com/questions/81503/what-is-the-tradeoff-between-privacy-and-implementation-complexity-of-dandelion

My notes:

• here!
• https://github.com/ajtowns/dandelion-simulations/blob/202102-hacks2/altdlion.py
• https://github.com/ajtowns/bitcoin/commits/202211-stempool

How should transactions be tracked during this initial phase?

One approach would be to simply include them in the mempool as normal. For an attacker that is expecting a transaction to be published, and either knows the txid or can create a conflicting transaction (by creating an alternative spend of one of the inputs), this would allow them to probe nodes and identify whether than node is participating in the initial limited relay, and could then potentially use that information to identify the tx originator.

See this comment on needing a stempool, and the reference in the following comment to irc discussion: bitcoin/bitcoin#13947 (comment)

Question: how should the stempool interact with dynamic minimum relay fees? what if a selected stem peer has too low a feefilter? pretend you sent it, but don't, and just wait for timeout?

Note that this necessitates redownloading a tx each time it's announced during the stem phase, as otherwise not responding to an INV with a GETDATA and not having previously sent an INV would indicate that you're in the stem phase.

So to handle txs in the stem phase, have a "stempool" to track them. The idea being that when you receive a stemming tx, you validate it (as a package, including any dependencies from the stempool), then if it validates, you add it to the stempool, along with tracking information as to when to fluff it.

"stempool" here means a new multi-index in CTxMemPool

This means the stempool should be queryable by:

1. (fluff_timeout) for transition to fluffing
2. (txid, source_peer) in order to find stemmed ancestors for package validation
3. (wtxid, source_peer) for deduplication on incoming stemmed INVs
4. (wtxid, dest_peer) for deduplication on forwarding txs
5. (bucket, spamscore) to be able to evict entries from the stempool if a particular source is peer is sending too much (bucket should be a function of source_peer, but potentially many source_peers may share the same bucket. spamscore should be calculated per-source_peer, so that even though the bucket is shared, a spammy peer only ends up causing its own transactions to be fluffed early)

The logic then is:

• while the lowest fluff_timeout is now or earlier [index 1]:

  • remove that tx from the stempool and fluff it

• receive an inv for a stemmed transaction:

  • if it hasn't been seen from this peer, request it [index 3]

• receive a stemmed transaction

  • if it has parents that aren't in the mempool, or in the stempool for this source tx [index 2],
    • request those parents via stem/package relay
    • add the tx to the orphan pool
    • restart once parents have arrived
  • see if it passes test mempool accept (including any parents in the stempool)
    • (possibly) if it doesn't due to low fees, look for orphans that this may be a parent of
  • recalculate the incoming node's spamminess score
  • decide on a fluff timeout
  • calculate the spamminess bucket and dest_peer(s)
  • add the tx to the stempool
  • while the spamminess bucket is full
    • remove the most spammy tx from the bucket [index 5] and fluff it (including if it had been stemmed to other dest_peers)
  • if the tx hasn't been removed from the stempool, queue it for stem relay to the selected dest_peer(s) [index 4]