Dandelion transaction relay (BIP 156) #13947

maflcko · 2018-08-12T14:43:07Z

The implementation of BIP 156 (Dandelion transaction relay) is done in three steps:

Add the protocol messages

dandeliontx, which contains a transaction serialized with all witness data
dandelionacc, which is always empty and only used to signal dandelion support to other peers

Shuffle dandelion stems

We shuffle a list of all peers that sent us the message that they accept dandelion txs (dandelionacc). This list can be used on demand by nodes that want to forward a dandelion transaction. (Actual receiving of dandelion txs is done in the next step).

Also, we add a command line option -dandelion, which can be used to opt out of all dandelion features.

Keep a cache of recent dandelion transactions

Dandelion transactions are never added to the global tx pool and only forwarded to one peer (the next hop in the stem). To guard against the next peer going offline, we keep a cache of recent dandelion transactions that are not yet fluffed (added to the mempool) or mined. Entries in this cache expire after some random timeout and transition to fluff phase.

maflcko · 2018-08-12T14:49:30Z

This is completely untested, so TODO:

add tests
use dandelion relay for our wallet txs

practicalswift · 2018-08-12T14:50:34Z

src/net.h

Any drawbacks from uncommenting the GUARDED_BY(…) annotation?

The drawback was that it didn't compile for me

practicalswift · 2018-08-12T15:08:07Z

src/init.cpp

Should -dandelion=100 generate an error message? From the error message it looks like it should, but not from the logic :-)

100% is allowed to always extend the stem by one hop. So the interval is [0, 100].

Then the error message should be -dandelion must be 0 or a percentage up to 100 or something equivalent?

DrahtBot · 2018-08-12T17:02:42Z

Note to reviewers: This pull request conflicts with the following ones:

Add p2p layer encryption with ECDH/ChaCha20Poly1305 #14032 (Add p2p layer encryption with ECDH/ChaCha20Poly1305 by jonasschnelli)
p2p: Clarify control flow in ProcessMessage #13946 (p2p: Clarify control flow in ProcessMessage by MarcoFalke)
refactor: Replace boost::bind with std::bind #13743 (refactor: Replace std/boost::bind with lambda by ken2812221)
net: Add Clang thread safety annotations for guarded variables in the networking code #13123 (net: Add Clang thread safety annotations for guarded variables in the networking code by practicalswift)
Multiprocess bitcoin #10102 ([experimental] Multiprocess bitcoin by ryanofsky)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

clodhopp · 2018-08-12T18:44:34Z

doc/bips.md

Link https://github.com/bitcoin/bips/blob/master/bip-0156.mediawiki gives error 404 page not found.

@clodhopp that's because the BIP PR hasn't been merged, you can see it here: bitcoin/bips#703
Once merged, the link should work

sipa · 2018-08-12T18:57:41Z

This code doesn't seem to include a "stempool"; how does it deal with dandelion transactions that depend on other dandelion transactions? ATMP will fail for those.

maflcko · 2018-08-12T20:02:45Z

This code doesn't seem to include a "stempool"; how does it deal with dandelion transactions that depend on other dandelion transactions? ATMP will fail for those.

Continued here https://botbot.me/freenode/bitcoin-core-dev/2018-08-12/?msg=103212266&page=2
EDIT by ajtowns: http://www.erisian.com.au/bitcoin-core-dev/log-2018-08-12.html#l-190

sdaftuar

I just left some initial comments from a quick-read of the code. As discussed on IRC we still need to figure out what the right behavior is for transaction chains and replacement transactions (and combinations of the two), and generally how to prevent DoS attacks during stem routing.

If we use a stempool to address those issues, then I'm not sure I understand how we could share a stempool across multiple inbound peers without leaking dandelion routing information to an adversary (and if we have separate stempools for each inbound peer, then that sounds like a lot of overhead).

sdaftuar · 2018-08-13T15:35:47Z

src/init.cpp

Do we use SoftSetBoolArg() like this elsewhere, on arguments that take numeric values? It was not clear to me that this worked until I saw that SoftSetBoolArg converts the false to std::string("0"). (Neat, though.)

Just to not mix up values, this should set 0 instead of false, even if false would be converted automatically to 0.

sdaftuar · 2018-08-13T19:03:21Z

src/net.h

nit: IsEphemeral

sdaftuar · 2018-08-13T19:07:43Z

src/net_processing.cpp

Some IRC discussion around not extending whitelist-relay behavior further with dandelion processing:
https://botbot.me/freenode/bitcoin-core-dev/2018-08-13/?msg=103271568&page=3

sdaftuar · 2018-08-13T19:11:01Z

src/net_processing.cpp

See above comment about dropping this behavior for whitelisted peers.

sdaftuar · 2018-08-13T19:23:54Z

src/protocol.h

+ * The dandelion tx message transmits a single transaction.
+ * @see https://github.com/bitcoin/bips/blob/master/bip-0156.mediawiki
+ */
+extern const char* TX_DANDELION;


I think in the past, we've usually bumped the protocol version when introducing new p2p messages so that we only send the new messages (like ACCEPT_DANDELION) to peers that are signaling that they've upgraded. Not sure how important that is...

Note that we'd never send a TX_DANDELION to a peer that never sent us ACCEPT_DANDELION in the first place. So I don't think this is an issue at all.

Perhaps my comment was not placed on the right line of this file; I was thinking of the dandelionacc message. With sendheaders and I think compact blocks, I believe we bumped the protocol version and only tried to send the new p2p messages (even for handshaking/negotiating the protocol to use) to peers with that higher version?

Good point. I think it is a lot easier to do this without enforcing a global network version bump.

Note that the dandelionacc message is properly read by all nodes that implement dandelion (regardless of their network protocol version) or choose to ignore that message. And for all other nodes (that are completely unaware of dandelion) they simply treat this as unknown message (once per connection) in their logs. I think this one debug log is not enough reason to go through the hassle of bumping the protocol version.

bitcoin/src/net_processing.cpp

Line 2942 in 63f8b01

LogPrint(BCLog::NET, "Unknown command \"%s\" from peer=%d\n", SanitizeString(strCommand), pfrom->GetId());

Why not a service bit?

sdaftuar · 2018-08-14T19:25:14Z

src/net_processing.cpp

I think we should queue transactions for relay to a peer, rather than doing a direct send as is done here. Otherwise transaction relay can fill up our send buffers and delay block relay.

Further our current transaction relay system batches transactions for relay and, at each broadcast time, we sort the to-be-relayed transactions for the purposes of prioritising transactions that have fewer ancestors and higher feerate. I think being able to prioritise transactions with higher feerate for relay is probably useful (to prevent low-feerate transactions from harming propagation times of higher feerate transactions).

it's also better for privacy against traffic analysis to batch things.

maflcko · 2018-08-14T21:10:39Z

src/net_processing.cpp

Should write something to debug log here.

stevenroose · 2018-08-20T13:09:20Z

src/init.cpp

A simple "probability" should a number between 0 and 1. The variable used as default and the code below suggest a percentage is used instead. I think it would make sense to document it as such as well.

I was thinking about this as well: normally I’d expect a probability parameter to be in the interval [0.0, 1.0]. Are we trying to be consistent with other parameters taking probabilities as [0, 100] here, or what is the rationale? :-)

If that is the case, it should at least be mentioned in the help line.

Probability in % to extend ..

stevenroose · 2018-08-20T13:10:30Z

src/init.cpp

Just to not mix up values, this should set 0 instead of false, even if false would be converted automatically to 0.

stevenroose · 2018-08-20T13:37:04Z

src/net.cpp

This check should not be necessary, failing it means there's a bug. I'd suggest either using an assertion or something more severe than this or just removing the check.

stevenroose · 2018-08-20T14:15:55Z

src/net.h

Please elaborate a bit more on the documentation of the integer.

Maybe it is better to create a struct? This integer will look much better with a name. It is very hard to read all those peer.first and peer.second

stevenroose · 2018-08-20T15:18:28Z

src/net.h

The convention seems to be XXX_INTERVAL instead of INTERVAL_XXX.

Also, why 10 minutes?

@stevenroose as per the BIP: https://github.com/bitcoin/bips/blob/master/bip-0156.mediawiki#periodic-dandelion-route-shuffling (the value suggested in the BIP is best discussed on the bitcoin-dev mailinglist)

@Sjors this would do:
/** As per BIP156, pick new dandelion peers once every 10 minutes or 600 seconds. */

stevenroose · 2018-08-20T18:50:42Z

src/net.h

Why 90? This is like the most important parameter of the dandelion algorithm, I think it deserves some motivation..

@stevenroose the BIP specifies that:

When relaying a Dandelion transaction along a Dandelion route, there is a 10% chance that the Dandelion transaction becomes a typical Bitcoin transaction and is therefore relayed via diffusion.

@Sjors So I'd suggest referring to the BIP in the comment of that variable.

What I'm trying to say with this comments is that this is supposed to be an implementation of the BIP, so it should refer to the BIP for logic/params etc. It has happened too often that a BIP is just a description of the implementation.

stevenroose · 2018-08-20T19:06:49Z

src/net_processing.cpp

Perhaps mention txid?

stevenroose · 2018-08-20T19:09:43Z

src/net_processing.cpp

Should this check also be made for the wallet's own transactions? Or should a forced non-fluff be done in that case?

stevenroose · 2018-08-20T19:15:16Z

src/net_processing.cpp

Wrong indentation since after return.

stevenroose · 2018-08-20T19:37:05Z

src/protocol.h

+ * The dandelion tx message transmits a single transaction.
+ * @see https://github.com/bitcoin/bips/blob/master/bip-0156.mediawiki
+ */
+extern const char* TX_DANDELION;


Why not a service bit?

scravy · 2018-09-19T08:22:56Z

Shouldn't the functional test from the reference implementation (dandelion-org@d043e36#diff-21ab9447686d819eeeb7668ce8011e0d) run more-or-less unchanged on top of this branch?

rodasmith · 2018-09-30T23:10:01Z

src/net.cpp

+            m_nodes_dandelion.clear();
+            for (CNode* node : all_nodes) {
+                // Ignore inbound nodes
+                if (node->fInbound) continue;


Why ignore inbound nodes? Does this mean non-listening dandelion nodes send only their own transactions and that the peer who receives such will know with undeniable certainty that the non-listening node initiated the transaction?

Inbound nodes are much more likely to be snooping peers.

While that is true, aren't there solutions that do not make dandelion break firewalled nodes' privacy? For example, send only to outgoing peers if you originated the transaction, but send to incoming as well for forwarded txes? Perhaps weigh the outgoing peers more heavily than incoming peers when selecting a random peer to forward to (either by assigning a weight to individual peers based on incoming/outgoing status, or by first randomly selecting the outgoing or incoming pool with a fixed weighting before selecting a peer from whichever pool).

jb55 · 2018-10-03T00:08:25Z

These commits could be documented more in general, I'm finding it hard to review when there are no descriptions about what is being implemented.

AM5800 · 2018-10-09T12:01:52Z

It has been mentioned several times that common stempool might leak dandelion routing information to an adversary. Can someone help me understand how exactly?

Also, what is the current status of this issue? I would like to offer some help. For example with tests

scravy · 2018-10-09T12:30:34Z

@jb55 BIP156 should explain a lot of things.

jb55 · 2018-10-09T16:24:20Z

@scravy I'm more interested in documentation of the implementation itself, how each commit relates to a part of the bip, etc. It's much harder to verify an implementation without that, especially with important privacy/security features. I don't think we should be making it harder on reviewers than it needs to be.

stevenroose · 2018-10-09T17:30:31Z

@jb55 Totally agree. All the non-trivial pieces of code should explain themselves, refer to the BIP when relevant, etc..

AM5800 · 2018-10-25T07:57:04Z

src/net_processing.cpp

    });
 }

+static void FluffTransaction(CTxMemPool& tx_pool, const CNode* from, const CTransactionRef& ptx, CConnman* connman)


I was wandering... FluffTransaction is logically equivalent to receiving a transaction, right?
Then shouldn't we also execute all this code on fluff?

AM5800 · 2018-10-25T08:05:34Z

src/net.cpp

+
+    if (CNode::IsDandelionEnabled()) {
+        // Shuffle dandelion destinations
+        m_thread_shuffle_dandelion = std::thread(&TraceThread<std::function<void()>>, "dandelionshuff", [&] { ThreadShuffleDandelionDestinations(); });


When I tried this PR in action - dandelion was turned off for the first epoch. I believe this happens because we do the very first shuffle when there are no connections. Maybe the first shuffle should be delayed until someone connects?

AM5800 · 2018-10-25T08:17:17Z

src/net_processing.cpp

+        from->m_cache_expiry.pop();
+    } while (from->m_cache_expiry.top() < now_millis);
+
+    for (auto it = from->m_cache_dandelion.cbegin(); it != from->m_cache_dandelion.cend(); ++it) {


An idea: if you define m_cache_expiry as std::map<int64_t, CTransactionRef> - you will get the same 'Constant time lookup' but you won't need to walk the whole cache - expired transactions are already available

AM5800 · 2018-10-25T08:22:39Z

src/net_processing.cpp

+    // Dandelion relay (at least one hop)
+    const int64_t now_micros = GetTimeMicros();
+    const int64_t expiry = now_micros + EXPIRE_DANDELION_CACHE * 1000 * 1000 + PoissonNextSend(now_micros, EXPIRE_DANDELION_CACHE_AVG_ADD);
+    node_from->m_cache_dandelion.emplace(std::make_pair(ptx->GetWitnessHash(), std::make_pair(ptx, expiry)));


Nit:
node_from->m_cache_dandelion.emplace(ptx->GetWitnessHash(), std::make_pair(ptx, expiry))
does absolutely the same, but shorter.

riclas · 2019-02-04T13:03:10Z

I believe this explanation of the DDoS possibilities on Dandelion by @sdaftuar belongs here:
https://bitcoin.stackexchange.com/questions/81503/what-is-the-tradeoff-between-privacy-and-implementation-complexity-of-dandelion

regarding option b), maybe dynamically adjusting stem % according to fullness of the stempool/cache could be a solution? at worst, we would fluff all the time just like a regular tx spam attack.

maflcko · 2019-07-22T16:33:59Z

I closed this for now because it is non-trivial to allow for all wallet behavior (e.g. cpfp and rbf) while not opening DOS vectors. I think a simpler first step would be to go for "Dandelion Light" or "Dandelion one-hop".

That approach would not need any DOS protection, since the only sender is our own wallet and the next hop would already fluff the tx (and send it back to us, so that our wallet can know it made it into the mempool eventually)

Dandelion transaction relay (BIP156) original source available at bitcoin/bitcoin#13947. Ported forward from Bitcoin 0.17 - looks to be written in a much neater manner. Signed-off-by: barrystyle <baz@tiltpool.com>

fanquake · 2022-08-04T14:14:59Z

Removed up for grabs.

ajtowns · 2022-11-04T09:43:44Z

src/net_processing.cpp

+    static constexpr int DANDELION_SEND_FLAGS{0}; // Always send as witness tx
+
+    // Check if the next peer would fluff (assume same probability)
+    bool force_fluff = GetRand(100 * 100) / 100. >= CNode::m_dandelion_stem_pct_threshold;


This doubles the odds of the next node fluffing -- 10% chance that we thought they should fluff, but if we don't think they should fluff, they'll still make their own decision, giving another 9% (=90%*10%) chance that they'll think they should fluff for a total of 19%.

(necroreviewing!)

protocol: Add BIP 156 message types

8c27c3b

practicalswift reviewed Aug 12, 2018

View reviewed changes

maflcko added the P2P label Aug 12, 2018

maflcko added this to the 0.18.0 milestone Aug 12, 2018

maflcko added the Feature label Aug 12, 2018

practicalswift reviewed Aug 12, 2018

View reviewed changes

This was referenced Aug 12, 2018

p2p: Clarify control flow in ProcessMessage #13946

Merged

refactor: Replace boost::bind with std::bind #13743

Merged

clodhopp reviewed Aug 12, 2018

View reviewed changes

sdaftuar reviewed Aug 13, 2018

View reviewed changes

sdaftuar reviewed Aug 14, 2018

View reviewed changes

maflcko commented Aug 14, 2018

View reviewed changes

src/net_processing.cpp Outdated

Copy link

Member Author

maflcko Aug 14, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Should write something to debug log here.

logging: Add BCLog::DANDELION

3c29217

maflcko force-pushed the Mf1804-dandelion branch 3 times, most recently from 2728324 to be9db89 Compare August 14, 2018 23:41

doc: Dandelion transaction relay (BIP 156)

c5aba5c

maflcko force-pushed the Mf1804-dandelion branch 4 times, most recently from 0526b2d to b508ed1 Compare August 17, 2018 12:46

stevenroose suggested changes Aug 20, 2018

View reviewed changes

maflcko force-pushed the Mf1804-dandelion branch 3 times, most recently from 8252b0e to ce8c6d6 Compare August 21, 2018 14:31

net: Add thread to shuffle potential dandelion stems

bbe290e

thothd mentioned this pull request Sep 14, 2018

Dandelion (BIP 156) dtr-org/unit-e#100

Closed

rodasmith reviewed Sep 30, 2018

View reviewed changes

AM5800 reviewed Oct 25, 2018

View reviewed changes

maflcko removed this from the 0.18.0 milestone Dec 3, 2018

maflcko added the Up for grabs label Jul 11, 2019

maflcko closed this Jul 11, 2019

maflcko deleted the Mf1804-dandelion branch July 11, 2019 21:12

laanwj removed the Needs rebase label Oct 24, 2019

ysangkok mentioned this pull request Jun 26, 2020

Reject 156 (expired) bitcoin/bips#939

Merged

ghost mentioned this pull request Oct 20, 2020

Dandelion++ #20203

Closed

ghost mentioned this pull request Apr 20, 2021

removed DANDELION reference gapcoin-project/gapcoin-project.github.io#55

Merged

bitcoin locked as resolved and limited conversation to collaborators Feb 15, 2022

fanquake removed the Up for grabs label Aug 4, 2022

ajtowns reviewed Nov 4, 2022

View reviewed changes

bitcoin unlocked this conversation Nov 4, 2022

bitcoin locked and limited conversation to collaborators Nov 4, 2022

Dandelion transaction relay (BIP 156) #13947

Dandelion transaction relay (BIP 156) #13947

Uh oh!

Conversation

maflcko commented Aug 12, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Add the protocol messages

Shuffle dandelion stems

Keep a cache of recent dandelion transactions

Uh oh!

maflcko commented Aug 12, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

DrahtBot commented Aug 12, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sipa commented Aug 12, 2018

Uh oh!

maflcko commented Aug 12, 2018 • edited by ajtowns Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sdaftuar left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

practicalswift Aug 20, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

maflcko commented Aug 12, 2018 •

edited

Loading

DrahtBot commented Aug 12, 2018 •

edited

Loading

maflcko commented Aug 12, 2018 •

edited by ajtowns

Loading

practicalswift Aug 20, 2018 •

edited

Loading