Dandelion (BIP 156)

[thothd]

We should implement Dandelion transaction relay according to the BIP and Bitcoin's wip implementation.
@gfanti can provide guidance on implementation details as being behind the research paper and created the BIP. @amiller was also directly involved and can surely help around the security / performance aspects.

As part of the implementation it's important to benchmark the p2p network and overall transaction processing performance w/o Dandelion.

It's also essential to provide an init flag (e.g -dandelion as in Bitcoin) to control the probability and whether the feature should be enabled .

[gfanti]

Definitely--one key point is that we should change some of the parameters for Unit-e. The parameters in our reference implementation were chosen to maximize privacy with regard to Bitcoin's latency requirements, which are looser than ours. So instead of having a stem of mean length 10 hops, we may want to do something like 3-4 hops to speed things up.

[scravy]

The PR on bitcoin is commented on by @MarcoFalke as

This is completely untested, so TODO:

• add tests
• use dandelion relay for our wallet txs

we could lend them a hand there.

[gfanti]

@scravy In case it's useful as a starting point, we already implemented a number of tests for our reference implementation

[scravy]

@gfanti I can see one added functional tests: dandelion-org/bitcoin@d043e36#diff-21ab9447686d819eeeb7668ce8011e0d

Since the reference implementation and the open PR on bitcoin implement the same BIP, shouldn't the test run as-is on that bitcoin branch (bitcoin/bitcoin#13947)?

[gfanti]

Yes, it should. Does it not?

[scravy]

I did not check myself, but I did raise it in bitcoin/bitcoin#13947 (comment)

[AM5800]

Update from MarkoFalke on bitcoin implementation:

I disagree that there should be a stempool per inbound node. We need
to obey global size limits (and potentially other constraints) anyway,
so a single stempool would simplify this logic. Also, there shouldn't
be any privacy concerns under the assumption that the attacker already
has knowledge of the full network topology.

Having a single stempool for all transactions also makes transaction
prioritization easier. Let's suppose one inbound node spams us with
low feerate dandelion transactions, then I presume it would be more
straightforward to discard them in a setting with one stempool as
opposed to multiple pools.

My current plan is to make ATMP (AcceptToMemoryPool) work with either
a stempool or mempool. That might require to unfiddle all of the
internal mempool logic, most likely along the lines of
bitcoin/bitcoin#13804 (Transaction Pool
Layer). That is currently a very rough draft and doesn't even compile
due to locking annotation issues. The next step would be to extend
that with size limiting, i.e. take some of the default 300MB mempool
limit and assign it to the stempool in some way. Then as the last
step, rework my Dandelion implementation to use that stempool layer on
top of the mempool.

Unfortunately this is a lot more complexity and code than we wished
for, so the bottleneck will probably be review. To keep review easy, I
will split out related or required sanity fixes or refactoring that
makes sense on its own into their own pull requests. For example,
bitcoin/bitcoin#14193 will hopefully fix the
compile issue with static locking annotations in the Transaction Pool
Layer pull request. Though, it also makes sense on its own for rpc
consistency guarantees...

This sounds like it is going to take A LOT of time to implement.
I also have doubts about this line:

Also, there shouldn't
be any privacy concerns under the assumption that the attacker already
has knowledge of the full network topology.

@amiller @gfanti do you agree with that?

[AM5800]

There are also two questions I would like to discuss(yes, again):

1. Separate or global stempool?
   When a stem transaction arrives, we check it against our usual mempool and:
   a) All dandelion transactions from all inbound nodes
   b) Only dandelion transactions we received from this particular inbound node
   c) Only mempool

2. What to do with orphan dandelion transactions?
   a) Reject them completely
   b) Store them in orphan buffer
   c) Store them in orphan buffer and relay
   (we never tell our decision to anyone, but anyone can observe outcomes of our decisions)

I think those two questions are very important, because their wrong combination might lead to different kinds of attacks. For example with 1a + 2a you can send a tx1 to some node1 and then tx2 that spends tx1 to node2. If tx2 is fluffed => there is a dandelion route node1->...->node2.
There might be other kinds of attacks, I just might not be able to see them all

[AM5800]

I will try to document in this issue all important conversations I had about dandelion:

Q: Is there some specific reason why we need a stempool? And not just to modify mempool in some way, that provides isolation from dandelion and non-dandelion transactions?

amiller [2:30 PM]
We tried to do it with mempool and kept finding additional possible isolation problems, so we switched to that approach
Both options may be ok
Also our initial feedback from Greg Maxwell in Bitcoin led us towards having a second separate data structure basically

[AM5800]

It is very important in dandelion to hide node's state. Because by observing it attacker can try to learn dandelion routing information. Here is my analysis on how we might leak state (I am not evaluating which are probable/feasible, just list).

1. P2P messages. An example might be: attacker sends us inv message with a tx. If we do not reply with getdata - this most likely means that we already have this transaction.
2. Banning. An attacker can observe if he was banned. So if there are some actions that lead to ban in certain node state and don't lead to ban in another state => we can learn this state by trying to get banned
3. Observe what happens with transactions that were sent by an attacker
   a) Child transaction never fluffed => Node didn't have parent tx and rejected child transaction
   b) Child transaction fluffed much later than parent tx => Node didn't have parent tx and left child in orphan pool => Later it received fluffed parent tx => Child tx was routed further

[AM5800]

Closing in favor of #210