Prevent mempool leaks

[gfanti]

A received dinv should be checked against the same filters that a normal inv is (mempool, setknown, rejects) and then requested even if the txn has already been fetched before. When the txn is received it should be tested against the mempool but not inserted into the mempool-- because the presences of a transaction can be interrogated out of a nodes mempool (e.g. via mempool rpc or by observing the effects of conflicts). A separate peer-specific relay pool may be required to prevent third parties from querying for propagation by attempting to fetch a txn which only passed through a node in stem mode.
(thanks gmaxwell for this suggestion)

[amiller]

There are maybe a few ways of doing this. It might be necessary to consider tradeoffs and work out just what privacy guarantee we'd be getting in each case.

One option is to have each node forget entirely about the stem transaction after relaying it. No inserting in mempool, not even inserting in filterInventoryKnown. The reason not to insert in filterInventoryKnown is because otherwise we might not participate in propagation during "fluff" mode when the transaction comes back around. Propagating via the stem but then "forgetting" seems consistent.

However, if we skip placing the transaction in mempool, then we would potentially relay the same transaction over again in stem mode. Or worse, we'd even relay "double spend" transactions. Doesn't this mean we'd be contributing to DoS? Maybe not.... one reason why this is OK is because "stem mode" never amplifies the propagation, i.e. we only propagate to 1 other peer, not all 30+ish of our peers. No exponential propagation begins until "fluff" mode, at which point ordinary mempool rules apply.

[amiller]

Ugh, I can't find an easy way to validate if a transaction could be accepted into mempool without actually placing it in mempool. Perhaps an option is to perform minimal validation of stem-propagated tx's? But then, there would be a problem if an A --stem --> B ---stem --> C, and then C determines the transaction is invalid and disconnects B. The logic for checking a transaction is too complicated for me to really want to copy a subset of that over.

Maybe it would be acceptable to add a bool dryrun=False option to AcceptToMempool?

[amiller]

Thinking through this yet more... there are some tricky interactions with other mechanisms in propagation, mainly a) replacement of txs in mempool by txs with higher fees, and b) handling chains of descendent transactions that might get processed out of order.

We're proposing to have stem transactions bypass mempool. So basically what we'd be doing is letting stem transactions propagate with only a subset of these checks, but get processed by mempool rules when they switch. So we would need to guarantee that as long as the subset of "stem checks" are passed, then the next node that receives it and puts it in mempool cannot assign a misbehavior score to the stem relayer.

[amiller]

Here's a new plan.... (after spending a day trying to implement this by avoiding mempool, it requires too much tricky duplication of behavior). Instead, we will actually insert transactions in mempool, and mask them another way, by setting a time-limited "embargo". Requests for mempool etc. during an embargo will simply skip over the dandelion transaction and hide it. Robustness will be enabled by expiring the embargo with a random delay per #9.

There is still a big challenge remaining in handling orphans and out-of-order transactions. If we treat each transaction independently for the sake of stem propagation, then it's possible for a child transaction to enter "fluff" mode before the parent. This will cause our peers to request the parent from us, even if we did not relay the INV for the parent (since the parent was in stem node).

This cannot be treated as just an edge case, since simple usage patterns (calling "sendtoaddress" multiple times in rapid succession) will typically create a chain of dependent transactions... so it's important these don't get stuck, and ideally still benefit from dandelion privacy.

So, here is a new suggestion:

• If an accepted "stem" transaction depends on parents who are under "embargo," then this transaction is placed under embargo equal to the maximum of the embargo times for all the parents. This means that we skip the dandelion "coin flip" for a child transaction, if we have already made a coinflip for an earlier transaction.

• This provides an extra reason to pick a "fixed" outgoing stem node, that does not change for each transaction, so descendent transactions get routed to the same place. If we have a "handover", where our current outgoing stem node disconnects or we decide to choose another, we should process the list of currently embargoed transactions, and either switch them all to fluff, or send them to the new stem node.

There are still several tricky cases though. Suppose A generates {tx1, tx2} that depend on each other. Then suppose we have:
A --[stem]{tx1,tx2}--> B --[stem]{tx1,tx2}--> C
and then shortly after
Attacker --[fluff]{tx2}--> A
If A has tx1 and tx2 under embargo, then it should try not to reveal to Attacker whether it has these. But, if A really does not have tx1, then the expected behavior should be to send getdata(tx1) to Attacker.

So in short, it's going to be really tricky to simultaneously 1) retain as much of the same policy of existing Bitcoin in terms of validation / DoS-scoring behavior, but also 2) avoid behaving differently whether we have seen a stem transaction or not.

[amiller]

OK, the plan described above is partially implemented in fee2593 (what an unfortunate commit hash!)

Items are requested even if they've been fetched before. This is accomplished by:

1. having Dandelion INV message avoid putting an entry in "mapAlreadyAskedFor", which is the main obstacle that prevents future INV messages are responded to with GETDATA.
   fee2593#diff-9a82240fe7dfe86564178691cc57f2f1R2750

 +    if (inv.type == MSG_DANDELION_TX || inv.type == MSG_WITNESS_DANDELION_TX) {
 +	// Bypass the queue for dandelion transactions
 +	setDandelionAskFor.insert(inv.hash);
 +    } else {
 +	setDandelionAskFor.erase(inv.hash);
 +	if (it != mapAlreadyAskedFor.end())
 +	    mapAlreadyAskedFor.update(it, nRequestTime);
 +	else
 +	    mapAlreadyAskedFor.insert(std::make_pair(inv.hash, nRequestTime));
 +    }

2. Skipping the filterInventoryKnown for dandelion INV items (and for transactions sent in response to a getdata in response to a dandelion INV
   fee2593#diff-eff7adeaec73a769788bb78858815c91R1674

 +                // Skip adding to inventory for dandelion tx
 +                if (inv.type == MSG_TX || inv.type == MSG_WITNESS_TX)
 +                    pfrom->AddInventoryKnown(inv);

3. Ignoring the AlreadyHave flag when deciding whether to invoke AskFor
   fee2593#diff-eff7adeaec73a769788bb78858815c91R1681

 +                    if (!fAlreadyHave || fEmbargoed) {
 +                        pfrom->AskFor(inv);
 +                    }

Furthermore, responses to "getdata" fee2593#diff-eff7adeaec73a769788bb78858815c91R1220 and "mempool"
fee2593#diff-eff7adeaec73a769788bb78858815c91R3220 omit the transaction if it is currently embargoed.

Finally, to avoid out of order problems, only 1 dandelion node is chosen (for minimalism here in this preliminary version, it's just the first outgoing connection), and a child is guaranteed to be routed as a "stem" if any of the inputs it depends on are currently treated as stems.
fee2593#diff-eff7adeaec73a769788bb78858815c91R971

Does this embargo mechanism provide adequate protection against the spy attacker probing the node's mempool? Here are the concerns I think are left:

• In the worst case, the attacker is one of the recipients of the victim's transaction. In this case, the attacker could create a transaction that spends one of the coins, and send it to each node in order to tell whether it is relayed or placed in the orphans cache.
• If the attacker cannot spend any of the transaction's coins, then the attacker could still create a bogus transaction that purports to spend one of them. This may be OK for us... we will need to be double check that the attacker cannot discriminate between a transaction that is rejected for invalid signature vs a transaction that is placed in the orphan cache.