Eliminate TX trickle bypass, sort TX invs for privacy and priority.

gmaxwell commented at 10:01 am on April 4, 2016: contributor

Previously Bitcoin would send 1/4 of transactions out to all peers instantly. This causes high overhead because it makes >80% of INVs size 1. Doing so harms privacy, because it limits the amount of source obscurity a transaction can receive.

These randomized broadcasts also disobeyed transaction dependencies and required use of the orphan pool. Because the orphan pool is so small this leads to poor propagation for dependent transactions.

When the bypass wasn’t in effect, transactions were sent in the order they were received. This avoided creating orphans but undermines privacy fairly significantly.

This commit: Eliminates the bypass. The bypass is replaced by halving the average delay for outbound peers.

Sorts candidate transactions for INV by their topological depth then by their feerate (then hash); removing the information leakage and providing priority service to higher fee transactions.

Limits the amount of transactions sent in a single INV to 7tx/sec (and twice that for outbound); this limits the harm of low fee transaction floods, gives faster relay service to higher fee transactions. The 7 sounds lower than it really is because received advertisements need not be sent, and because the aggregate rate is multipled by the number of peers.

laanwj commented at 1:05 pm on April 4, 2016: member

Concept ACK

in src/main.cpp: in 6db0da3b6f outdated

5539+        mp = mempool;
5540+    }
5541+
5542+    bool operator()(const CInv &a, const CInv &b)
5543+    {
5544+        if (a.type != MSG_TX) {

sipa commented at 1:37 pm on April 4, 2016:

Have you verified that using this comparator does not change the order of blocks?

Alternatively, if both entries are blocks, perhaps they should be sorted by height?

gmaxwell commented at 7:32 pm on April 4, 2016:

It probably does change it (the sort isn’t stable). I’ll make it sort them by height… or I could split transactions off entirely.

in src/main.cpp: in 6db0da3b6f outdated

5813-                        vInvWait.push_back(inv);
5814-                        continue;
5815-                    }
5816+                // No reason to drain out at many times the network's capacity,
5817+                // especially since we have many peers and some will draw much shorter delays.
5818+                if (vInv.size() >= 7 * AVG_INVENTORY_BROADCAST_INTERVAL || (inv.type == MSG_TX && !fSendTrickle)) {

sipa commented at 1:38 pm on April 4, 2016:

This rate should be a named constant.

sipa commented at 10:19 pm on April 4, 2016: member

@gmaxwell As long as we intend to support serving blocks to pre-0.10 (and especially 0.9 with the limited block orphan pools), we should not reorder block invs.

theuni commented at 11:32 pm on April 4, 2016: member

Concept ACK. Nit: looks like most of these functions should be const.

laanwj added the label P2P on Apr 5, 2016

gmaxwell commented at 5:20 pm on April 5, 2016: contributor

Updated to make the sort stable and use static variables.

in src/main.h: in baf1f9c4a5 outdated

103- *  Blocks, whitelisted receivers, and a random 25% of transactions bypass this. */
104-static const unsigned int AVG_INVENTORY_BROADCAST_INTERVAL = 5;
105+/** Average delay between trickled inventory transmissions in seconds.
106+ *  Blocks and whitelisted receivers bypass this, outbound peers get half this delay. */
107+static const unsigned int INVENTORY_BROADCAST_INTERVAL = 5;
108+/** Maximum number of inventor items to send per transmission.

paveljanik commented at 8:44 am on April 6, 2016:

inventor -> inventory

sipa commented at 2:02 pm on April 6, 2016: member

Concept ACK, going to test.

Eliminate TX trickle bypass, sort TX invs for privacy and priority.

Previously Bitcoin would send 1/4 of transactions out to all peers
 instantly.  This causes high overhead because it makes >80% of
 INVs size 1.  Doing so harms privacy, because it limits the
 amount of source obscurity a transaction can receive.

These randomized broadcasts also disobeyed transaction dependencies
 and required use of the orphan pool.  Because the orphan pool is
 so small this leads to poor propagation for dependent transactions.

When the bypass wasn't in effect, transactions were sent in the
 order they were received.  This avoided creating orphans but
 undermines privacy fairly significantly.

This commit:
 Eliminates the bypass. The bypass is replaced by halving the
  average delay for outbound peers.

 Sorts candidate transactions for INV by their topological
  depth then by their feerate (then hash); removing the
  information leakage and providing priority service to
  higher fee transactions.

 Limits the amount of transactions sent in a single INV to
  7tx/sec (and twice that for outbound); this limits the
  harm of low fee transaction floods, gives faster relay
  service to higher fee transactions. The 7 sounds lower
  than it really is because received advertisements need
  not be sent, and because the aggregate rate is multipled
  by the number of peers.

19b9e051e7

gmaxwell commented at 2:12 pm on April 6, 2016: contributor

I think it’s updated for all comments now.

sipa commented at 10:36 am on April 7, 2016: member

Midly-tested ACK using https://github.com/sipa/bitcoin/commit/115157b45caa374719fa6ad2a3d46281c9109349 to monitor the sizes of invs-to-send. 80% of the observed queues have less than 10 elements, 99.3% have less than 100, 99.9% have less than 1000. The highest observed was 2698. The average is 10.05 elements, with standard deviation 16.65.

gmaxwell commented at 10:58 pm on April 8, 2016: contributor

Closing in favor of #7840.

gmaxwell closed this on Apr 8, 2016

MarcoFalke locked this on Sep 8, 2021

Eliminate TX trickle bypass, sort TX invs for privacy and priority. #7805