Net: Bucketing INV delays (1 bucket) for incoming connections to hide tx time

naumenkogs commented at 7:04 pm on May 21, 2018: member

It has been brought up to my attention that current random delays mechanism (originally intended to obfuscate transaction metadata) allows to easily estimate the time a transaction was received by a node.

It may be done by connecting multiple observer nodes to the same node. Each of those nodes will generate its own schedule of delays. Combined metadata regarding those events from different sources allows an observer to estimate transaction time.

After this patch a spy won’t gain additional information by just creating multiple connections to a target.

gmaxwell commented at 7:19 pm on May 21, 2018: contributor

I’m glad to see someone working on this!

One prior proposal was to put all inbound into one timing bucket, and keep per-peer timing for each outbound with the rationale that the attacker doesn’t control our outbounds but could potentially control any inbounds.

If we found that to be too slow we could quantize inbound network groups into a small number of buckets (e.g. 4, by computing hasher(seed, netgroup)&3 or similar) and have timers per that so even when an attacker goes and gets a lot of groups his speedup has a small bound

I think probably we shouldn’t be too afraid of slowing down propagation– the changes to add delays at all were a massive slowdown and generated basically no notice.

Also related to this we might want to track the rate of novel transactions being accepted for a particular peer and up-delay really slow peers (like send every Nth time it would otherwise send). The rational being that relay of novel transactions blinds tracking (since we won’t relay something a peer gave to us back to them) and also lazy tracking stuff tends not to relay anything. Delaying tx relay to a peer that never sends anything would hardly hurt propagation in the network, but at least might force attackers to be a bit more useful.

in src/net.cpp:2873 in 2b74996e37 outdated

2870+{
2871+    assert(pto);
2872+    uint64_t net_group = pto->nKeyedNetGroup;
2873+    std::pair<int, uint64_t> key{average_interval_seconds, net_group};
2874+    LOCK(cs_group_next_sends);
2875+    std::map<std::pair<int, uint64_t>, int64_t>::iterator group_next_send = group_next_sends.find(key);

gmaxwell commented at 7:21 pm on May 21, 2018:

I think for IPv6 this could be a slightly far-fetched memory exhaustion DOS.

skeees commented at 8:13 pm on May 21, 2018: contributor

Maybe I’m missing something, but what would be the downside of having a single next send across all outbound peers if propagation latency isn’t a huge issue? It seems like delay by net group is moving in that direction

sipa commented at 8:37 pm on May 21, 2018: member

We assume that outgoing connections are less likely to be (significantly) under attacker control, due to them being self-selected, and addrman having built-in precautions against eclipse attacks (cc @EthanHeilman). Giving different peers a synchronized timer results increases bandwidth spikes, which isn’t so much a concern for tx propagation, but may interfere with block propagation if they coincide. For outgoing peers (max 16) this is not that much of a concern, but then again, due to the previous point, synchronizing things is also less useful there.

Regarding @gmaxwell’s point of memory exhaustion, we could introduce a per-group reference counter, and delete the corresponding map entries when no peers in that group remain?

in src/net.h:315 in 2b74996e37 outdated

309@@ -310,6 +310,10 @@ class CConnman
310     unsigned int GetReceiveFloodSize() const;
311 
312     void WakeMessageHandler();
313+
314+    /** Attempts to obfuscate tx time through exponentially distributed emitting. */
315+    int64_t PoissonNextSendTo(int64_t now, int average_interval_seconds, CNode* pto);

Empact commented at 8:47 pm on May 21, 2018:

const CNode*, alternatively pass the net_group

in src/net.h:441 in 2b74996e37 outdated

437@@ -434,6 +438,9 @@ class CConnman
438      *  This takes the place of a feeler connection */
439     std::atomic_bool m_try_another_outbound_peer;
440 
441+    std::map<std::pair<int, uint64_t>, int64_t> group_next_sends GUARDED_BY(cs_group_next_sends);

Empact commented at 8:48 pm on May 21, 2018:

nit: include <map>

naumenkogs commented at 8:57 pm on May 21, 2018: member

@gmaxwell thanks for the feedback.

I like the idea of turning it into a small number of buckets. I think that 8 buckets may be fine considering current load (should not cause significant spikes in bandwidth).

Please let me know if you see a better estimation for a reasonable number of buckets.

gmaxwell commented at 9:38 pm on May 21, 2018: contributor

@skeees Putting all in one will result in more spiky bandwidth usage (e.g. you hit your queue then use a bunch of bandwidth transmitting to everyone at once), and I believe but lack a rigorous analysis that we get more privacy for a given amount of average delay if the transactions diffuse randomly in the network to hide where they originated from, at least if we assume the target doesn’t send many transactions (and that an attacker isn’t abusing multiple groups to get a faster effective send.)

E.g. imagine a user who originates from node X and an attacker that connects to almost all nodes in the network. If all sends happen at once, when the attacker sees a transaction happen from X first then he can have some confidence that transactions happened from there. If the send times are independent and the attacker sees a transaction from X first he doesn’t learn that much from that transaction.

The issue becomes if the attacker connects to you 20 times and the times are independent than he gets effectively a 20th of the delay. Which is why I was suggesting leaving outbounds independent and putting all inbounds into a single group or a small number of groups.

fanquake added the label P2P on May 21, 2018

fanquake added the label Privacy on May 21, 2018

in src/net.cpp:2871 in bd666a9789 outdated

2864@@ -2864,13 +2865,16 @@ bool CConnman::ForNode(NodeId id, std::function<bool(CNode* pnode)> func)
2865     return found != nullptr && NodeFullyConnected(found) && func(found);
2866 }
2867 
2868-int64_t CConnman::PoissonNextSendTo(int64_t now, int average_interval_seconds, uint64_t net_group)
2869+int64_t CConnman::PoissonNextSendTo(int64_t now, bool inbound, uint64_t net_group)
2870 {
2871-    std::pair<int, uint64_t> key{average_interval_seconds, net_group};
2872+    if (!inbound) {
2873+      return PoissonNextSend(now, INVENTORY_BROADCAST_INTERVAL >> 1);

sipa commented at 10:37 pm on May 21, 2018:

I think it’s suboptimal to put knowledge of the actual scheduling policy in net; it belongs more in net_processing (the INVENTORY_BROADCAST_INTERVAL and NETWORK_GROUP_BUCKETS should move there as well, I think).

How about passing a boolean per_group in, or saying that when net_group = 0 there is no grouping to be done? Then you can keep the decision logic in net_processing, and keep this function generally usable.

in src/net_processing.cpp:3514 in f890492b4c outdated

3473@@ -3474,7 +3474,11 @@ bool PeerLogicValidation::SendMessages(CNode* pto, std::atomic<bool>& interruptM
3474             if (pto->nNextInvSend < nNow) {
3475                 fSendTrickle = true;
3476                 // Use half the delay for outbound peers, as there is less privacy concern for them.
3477-                pto->nNextInvSend = PoissonNextSend(nNow, INVENTORY_BROADCAST_INTERVAL >> !pto->fInbound);
3478+                if (pto->fInbound) {

sipa commented at 11:45 pm on May 21, 2018:

I think this needs to be inverted.

jimpo commented at 6:08 pm on June 3, 2018:

For the sake of encapsulation, I think you can put more of this logic into int64_t CConnman::PoissonNextSendTo(int64_t now, CNode* node), including the check on fInbound and the half delay comment.

sipa commented at 7:57 pm on July 5, 2018:

@jimpo Does this comment still apply? CConnman::PoissonNextSendTo doesn’t take a CNode* argument anymore, and I think it’s better separation to keep the logic for determining the interval separate from the logic for computing the next send.

jimpo commented at 9:24 pm on July 5, 2018:

I’d still prefer a separate method for these four lines CConnman::PoissonNextSendTo(int64_t now, CNode* node). Certainly having the separate PoissonNextSend which actually computes the interval is a good idea (which already exists), but CConnman::PoissonNextSendTo as defined currently just does the interval caching by netgroup. I find the interface weird and I don’t understand the split between logic there and here.

That said, it’s a pretty minor point and I don’t feel too strongly.

jamesob commented at 6:51 pm on July 13, 2018:

(comment addressed AFAICT)

in src/net.cpp:2870 in f890492b4c outdated

2863@@ -2864,8 +2864,21 @@ bool CConnman::ForNode(NodeId id, std::function<bool(CNode* pnode)> func)
2864     return found != nullptr && NodeFullyConnected(found) && func(found);
2865 }
2866 
2867-int64_t PoissonNextSend(int64_t nNow, int average_interval_seconds) {
2868-    return nNow + (int64_t)(log1p(GetRand(1ULL << 48) * -0.0000000000000035527136788 /* -1/2^48 */) * average_interval_seconds * -1000000.0 + 0.5);
2869+int64_t CConnman::PoissonNextSendTo(int64_t now, int average_interval_seconds, uint64_t net_group_bucket)
2870+{
2871+    LOCK(cs_net_bucket_next_sends);
2872+    std::map<uint64_t, int64_t>::iterator net_bucket_next_send = net_bucket_next_sends.find(net_group_bucket);

sipa commented at 11:47 pm on May 21, 2018:

Without the interval size in the map, the correctness of this function depends on there only being a single interval (which is the case now, so no problem). It would be good to document that in the net.h definition, or change it.

jimpo commented at 6:03 pm on June 3, 2018:

Since that is the case, maybe average_interval_seconds should be removed as a parameter and just use the INVENTORY_BROADCAST_INTERVAL constant directly.

sdaftuar commented at 5:05 pm on May 25, 2018: member

I’ve been looking at this paper “Deanonymization in the Bitcoin P2P Network” (https://papers.nips.cc/paper/6735-deanonymization-in-the-bitcoin-p2p-network.pdf). It’s got some ideas for how to think about an adversary’s strategies with respect to detecting the first node on a network to relay a new transaction.

It seems to me there are a couple different kinds of adversaries to consider – (a) one that makes only inbound connections to listening nodes on the network, versus (b) one that manages to take over some percentage of listening nodes and thus controls x% of the outbound connections on the network. (And then these could be combined of course.)

For type (a) adversaries, there are multiple types of strategies that could be employed to deanonymize the first listening node to relay a transaction. Perhaps the simplest strategy is the “first spy” estimator described in that paper, where the adversary estimates the first node to relay a transaction to it as the source. Such a strategy seems to be very successful if the adversary connects to each node on the network multiple times, and this PR would mitigate that. However, based on simulations I’ve done, I think 8 buckets is too many. I don’t have a sense for how easy it is for an adversary to actually connect from different network groups to achieve the 8 different timings – so if we decide that is suitably hard, then maybe the point I’m raising is moot – but if we assume that is achievable, then my simulations suggest a 40% success rate for a first-spy adversary.

The paper I mentioned above goes into some length discussing the success bounds of an attacker that is smarter than that and also uses knowledge of the network graph to estimate the source node. I am still working through simulations that demonstrate the ideas they suggest, but I think I have a rough maximum-likelihood estimator that appears to be – very roughly – 15-20% successful at estimating the source node based on the times at which the adversary sees announcements from each node in the network. This is assuming that the adversary has 1 inbound connection to each node on the network.

It seems to me that as a first pass, we might limit the number of buckets so that the effectiveness of a first-spy adversary is on par with that of a smarter adversary[1]. From my analysis so far, I think having 2 buckets for incoming peers would roughly achieve that, with the important caveats that (a) no one has sanity checked my sim results [2], and (b) I don’t know yet how good the maximum-likelihood estimator could be if it were smart enough to use 2 connections to each peer.

If we weren’t concerned about tradeoffs (ie bandwidth spikes or relay propagation delays), I’d say we could just make this all one bucket for inbound peers, to maximize source-privacy in our current transaction relay model.

[1] I think we could also go further and figure out some equilibrium with respect to an adversary controlling X% of the listening nodes/outbound connections on the network, but I’m not sure how to think about the relative costs of these kinds of adversarial approaches.

[2] If anyone is able to do their own simulations or estimations to corroborate my observations that would be fantastic.

sipa commented at 8:52 pm on May 25, 2018: member

@sdaftuar Do you think there would be reasons to increase the number of groups when there are more connections? Clearly for small numbers of connections the concern about bandwidth spikes doesn’t exist, but if a node has 1000 connections, perhaps it does.

gmaxwell commented at 9:32 pm on May 25, 2018: contributor

@sdaftuar The suggestion I was leaning towards making but couldn’t justify strongly was to multiply the interval for inbound peers by 2 and have 4 groups– so that each of the 4 groups gets serviced 4x less often than a outbound peer . This would make an inbound oriented attacker get as much information from their inbound attack as being a attacker on a single outbound connection.

I would expect that 4 is still pretty bandwidth spike mitigating.

We also do want to have multiple groups so that we have a chance of ‘routing around’ a first spy monitor. Though perhaps the outbounds are sufficient for that.

I don’t have a sense for how easy it is for an adversary to actually connect from different network groups to achieve the 8 different timings

Trivial, because our “network groups” are just /16s you can achieve the 8 groups just with a single EC2 account, picking different datacenters. Even if we got a bit smarter and put in some prefixes of major VPS providers to be treated as a single group (or one per provider), it’s still not terrible hard to get on lots of networks… there are even commercial services that give you addresses in as many /8s as possible for the purpose of jamming the bittorrent DHT stuff for ‘anti-piracy’ reasons.

We should generally assume that network group limitations are a pretty modest roadbump. They’re cheap to implement, so “why not”…. but they don’t to much.

also uses knowledge of the network graph to estimate the source node.

Thus future efforts on topology rotation, … though there are tradeoffs there too. :( @sipa

Do you think there would be reasons to increase the number of groups when there are more connections?

Well the attacker decides to connect to you, so naively doing that would be foolish since he could just get more information that way. Another way of looking at it is if you have 1000 connections presumably you have a lot more bandwidth and don’t mind the spikes that much. If you don’t like the spikes run fewer connections.

sipa commented at 1:46 am on May 28, 2018: member

Well the attacker decides to connect to you, so naively doing that would be foolish since he could just get more information that way.

Uh, of course. Ignore my suggestion.

The suggestion I was leaning towards making but couldn’t justify strongly was to multiply the interval for inbound peers by 2 and have 4 groups– so that each of the 4 groups gets serviced 4x less often than a outbound peer .

That seems reasonable, but some simulations - for example on the effect on network wide propagation speed would be useful.

in src/net_processing.h:42 in c49fa62a8a outdated

34@@ -35,6 +35,23 @@ static constexpr int64_t EXTRA_PEER_CHECK_INTERVAL = 45;
35 /** Minimum time an outbound-peer-eviction candidate must be connected for, in order to evict, in seconds */
36 static constexpr int64_t MINIMUM_CONNECT_TIME = 30;
37 
38+/** Average delay between local address broadcasts in seconds. */

jimpo commented at 5:49 pm on June 3, 2018:

I believe these can all go in net_processing.cpp instead of the header file.

jimpo commented at 9:17 pm on July 5, 2018:

@naumenkogs This has not been addressed.

jimpo commented at 6:16 pm on June 3, 2018: contributor

Concept ACK on limiting by inbound net group.

Not sure about the best selection of parameters without simulation, but this can always be tweaked later. I like @gmaxwell’s suggestion of 4 buckets and increasing the broadcast interval on inbounds from 2x to 4x over outbound connections.

As for @sipa’s suggestion of scaling buckets with the number of connections, it might be reasonable to scale with the configured max inbound connections, which not manipulable by an attacker.

sdaftuar commented at 2:20 am on June 6, 2018: member

I’ve been doing some more simulations on this recently. I still don’t have good results for the graph-aware estimators that (in theory) should be pretty powerful. But I did want to share a couple other results on the first spy estimator:

First my previously reported simulations were more optimistic than I realized, because I was just modeling the effect of limiting the number of connections an adversary could make, without taking into account the delay in propagation across the network that occurs when we bin the inbound peers. So for instance I previously modeled how well an attacker would do if we limited them to 8 connections per peer, without also modeling the effect on the network due to ALL inbound peers being in those buckets as well.

Slowing down transaction relay across the network benefits the first-spy estimator (as it increases their window of success). So I fixed that deficiency in my latest simulation, and I observed that bucketing the inbound peers to 8 buckets – and assuming that the adversary is in all 8 buckets for all nodes on the network – appears to give a success rate to the attacker of ~54% (!).

I did my simulations on randomly generated graphs on 5000 nodes, where each node randomly picked 8 outbound peers. I assume the adversary is connected in every available inbound bucket. This uses the existing relay delays we have for inbound peers (2x the mean delay of our outbound peers). For each row in the table, I ran 2000 simulations.

Number of inbound buckets	Success rate
1	19%
2	26%
3	34%
4	41%
5	46%
6	50%
7	53%
8	54%

I also simulated @gmaxwell’s suggested strategy, of using 4 inbound buckets, but applying a bigger (4x instead of 2x) delay to inbound peers. That had a first-spy estimator success rate of 28%.

I’ll update these results with some statistics about total propagation times soon…

MarcoFalke added the label Needs rebase on Jun 6, 2018

naumenkogs commented at 6:13 pm on June 7, 2018: member

I’ve run a simulation to figure out how accurate might be a simple first-time spy under different conditions.

I’ve used a network of 1000 nodes only (random graphs, 8 outgoing connections), so you can consider the results as upper bound comparing to the real Bitcoin network. (cause more nodes will introduce noise) 500 simulations.

I’ve considered an attacker that connects to all of the nodes multiple times so that it takes over all of the inbound buckets.

R = inbound_connection_interval/outbound_connection_inverval

R = 2

Number of inbound buckets	Success rate
1	13%
2	26%
4	50%
8	63%

R = 4

Number of inbound buckets	Success rate
1	13%
2	21%
4	41%
8	56%

From these numbers, 2 buckets and R=4 seems optimal.

Both of mine and @sdaftuar simulations demonstrate that increasing R is useful. However, this makes the assumption about outgoing connections more crucial.

I’m going to run more simulations soon.

naumenkogs commented at 1:21 am on June 14, 2018: member

I’ve measured how R affects propagation delay. From my measurements, it looks like the difference is within 25-40% for R=2 comparing to R=4 (I think that’s a lot, but probably acceptable for now), and the distribution of values (50% 75% 99% 100%) is similar for different number of buckets as well as different R.

Another point I’ve found is number of buckets itself does not affect propagation delay much — at least for a reasonable number (up to 8, see prior data), which is surprising for me. It may be because of the size of my simulation (only 1000 nodes).

Anyway, from my observations it seems like neither setting R=4 nor using a small number of buckets affect propagation time very dramatically. @sdaftuar may have more interesting results here.

naumenkogs commented at 5:36 pm on June 14, 2018: member

I was also wondering what if an attacker has control over 1 of 8 outgoing connections per each peer in the network.

In this case, modifying R does not make any difference: success rate is 37-40% for 1 or 2 bucket scenario (worst case for a spy) for R=2, 4, 8. Success rate for R=8 grows a bit slower with number of buckets comparing to R = 2, but not significantly (~5-10%).

Having less buckets helps in the same fashion as in the previous measurements, but 37% is very high as for the worst case for a spy.

If we consider that an attacker may take control over 1 outgoing per some fraction of nodes, then having less buckets still would be helpful to prevent first-spy.

naumenkogs commented at 7:36 pm on July 3, 2018: member

Here are my results on spikes.

Analysis

Distributions

I guess what is important is the tail of the distribution – the probability of huge number of transactions being relayed within one interval of 5 seconds. I won’t say anything about buckets > 2, because my results show that anonymity properties are weak there. I’d say, once we have more nodes in the network and having connections to 100% of nodes will be harder to achieve, we may consider buckets > 2.

if we choose 1 bucket, r=2 is better because it is less spikey and the success rate is the same. If we are OK with eventual spikes of 18 KB/s, we should do 1 bucket and r=2.

If we compare 2-bucket results, the distribution is slightly better for r=2, while anonymity is better for r=4 (5% better). I think r=4 is better here (keep in mind though that it introduces 25-40% propagation delay according to my measurements). The eventual spikes here are 14 KB/s. Obviously, r=3 would be something in the middle, I may do additional runs for that scenario, I’m not adding it here to avoid confusion.

Please share your thoughts.

Upd: Raw data and more graphs (buckets > 2) are available here.

laanwj added this to the "Blockers" column in a project

naumenkogs force-pushed on Jul 5, 2018

naumenkogs commented at 0:03 am on July 7, 2018: member

Here are my experimental results on propagation delay.

This was discussed on bitcoin irc with @gmaxwell and @sipa.

At first, the fact that number of buckets does not matter much was questioned. You can see precise results now. 1 bucket comparing to 8 is 20-25% worse for 50% coverage, and 5-10% worse for 100% coverage.

At the same time, making R=4 itself has an impact around 80% comparing to R=2. That’s why I’m arguing for R=2 and 1 bucket (if we allow those spikes of 18 KB/s).

What is still surprising for me (and for some other people) is: with R=1 setting buckets to 1 is slightly less significant than doing the same with R=4 — see “max slowdown”. We expected it to be more significant, because we expected that with R=1 nature of relay through incoming should matter more. Also be aware that absolute max slowdown is fairly low — up to 2 seconds.

I’ve briefly seen some graphs of @sdaftuar and it was something similar to what I’ve had — the same surprise.

DrahtBot removed the label Needs rebase on Jul 7, 2018

gmaxwell commented at 3:45 pm on July 10, 2018: contributor

Anyone oppose changing this to 1 bucket? it would let you simplify the code. e.g. I think the map could be eliminated, etc… just the shared inbound peer state. I think the 18kb/s spikes are okay, we’ll do much worse when a compact-block-cold peer requests a block from us…

naumenkogs force-pushed on Jul 12, 2018

gmaxwell commented at 10:12 pm on July 12, 2018: contributor

ACK. Though if you change it again you might want to rename the function to *Inbound instead of *To since it no longer takes a To argument. If you do, you should brace the if per the developer notes– multi-line ifs should always be braced. (My ACK applies with or without these changes).

naumenkogs force-pushed on Jul 12, 2018

gmaxwell commented at 6:07 pm on July 13, 2018: contributor

re-ACK

jamesob commented at 6:56 pm on July 13, 2018: member

utACK https://github.com/bitcoin/bitcoin/pull/13298/commits/efa0092979691492218e90c80e366957cb6b97db

Should the PR description be updated to clarify that we’re going with a 1-bucket approach? I had to wade through the comment thread to verify that was the intent.

in src/net.cpp:2869 in efa0092979 outdated

2863@@ -2864,8 +2864,17 @@ bool CConnman::ForNode(NodeId id, std::function<bool(CNode* pnode)> func)
2864     return found != nullptr && NodeFullyConnected(found) && func(found);
2865 }
2866 
2867-int64_t PoissonNextSend(int64_t nNow, int average_interval_seconds) {
2868-    return nNow + (int64_t)(log1p(GetRand(1ULL << 48) * -0.0000000000000035527136788 /* -1/2^48 */) * average_interval_seconds * -1000000.0 + 0.5);
2869+int64_t CConnman::PoissonNextSendInbound(int64_t now, int average_interval_seconds)
2870+{
2871+    if (next_send_inv_to_incoming < now) {

sipa commented at 6:56 pm on July 13, 2018:

Given that you’re reading from the atomic variable multiple times here, there is a risk that it was updated by two threads in parallel, resulting in two different timestamps being returned from this function - which would break the independence of sends between nodes.

This is a highly unlikely event, and it may even be impossible for now (due to limited threading in the network handing code). However, with the objective of doing it “by the book”, I believe a correct implementation would be this:

 0int64_t previous = next_send_inv_to_incoming.load();
 1if (prevous < now) {
 2    int64_t next = PoissonNextSend(now, average_interval_seconds);
 3    do {
 4        if (next_send_inv_to_incoming.compare_exchange_weak(previous, next)) {
 5            // We succesfully updated the atomic next_send_inv_to_incoming
 6            return next;
 7        }
 8        // Another thread changed next_send_to_inv after we fetched previous,
 9        // but before we tried to update it. The values chosen by the other
10        // thread is loaded into previous, so check if that value is >= now.
11        if (previous >= now) return previous;
12    }
13}
14return previous;

(this is not a blocker for my review)

in src/net.h:444 in 2a361eb7d5 outdated

440@@ -434,6 +441,8 @@ class CConnman
441      *  This takes the place of a feeler connection */
442     std::atomic_bool m_try_another_outbound_peer;
443 
444+    std::atomic<int64_t> next_send_inv_to_incoming;

instagibbs commented at 7:28 pm on July 13, 2018:

mu-nit: use m_ prefix for member variable

instagibbs approved

instagibbs commented at 7:31 pm on July 13, 2018: member

utACK https://github.com/bitcoin/bitcoin/pull/13298/commits/2a361eb7d5832ec7e7dabccfb32dcbf815fad049

but I agree with @jamesob that the description needs updating. Took me a couple minutes to figure out the connection with what is quite simple code now.

naumenkogs renamed this:
~~Net: Random delays *per network group* to obfuscate transaction time~~
Net: Bucketing INV delays (1 bucket) for incoming connections to hide tx time
on Jul 13, 2018

in src/net.cpp:2879 in 2a361eb7d5 outdated

2876+    return next_send_inv_to_incoming;
2877+}
2878+
2879+int64_t PoissonNextSend(int64_t now, int average_interval_seconds)
2880+{
2881+  return now + (int64_t)(log1p(GetRand(1ULL << 48) * -0.0000000000000035527136788 /* -1/2^48 */) * average_interval_seconds * -1000000.0 + 0.5);

Empact commented at 8:33 pm on July 13, 2018:

nit: non-standard indentation here and elsewhere, clang-format will fix

in src/net_processing.h:55 in 2a361eb7d5 outdated

50+ *  Limits the impact of low-fee transaction floods. */
51+static const unsigned int INVENTORY_BROADCAST_MAX = 7 * INVENTORY_BROADCAST_INTERVAL;
52+/** Average delay between feefilter broadcasts in seconds. */
53+static const unsigned int AVG_FEEFILTER_BROADCAST_INTERVAL = 10 * 60;
54+/** Maximum feefilter broadcast delay after significant change. */
55+static const unsigned int MAX_FEEFILTER_CHANGE_DELAY = 5 * 60;

Empact commented at 8:42 pm on July 13, 2018:

Agree with @jimpo, these can move to net_processing.cpp

sipa commented at 9:27 pm on July 13, 2018:

Agree, and additionally they can become constexpr.

in src/net_processing.cpp:3499 in 2a361eb7d5 outdated

3496@@ -3497,7 +3497,11 @@ bool PeerLogicValidation::SendMessages(CNode* pto, std::atomic<bool>& interruptM
3497             if (pto->nNextInvSend < nNow) {
3498                 fSendTrickle = true;
3499                 // Use half the delay for outbound peers, as there is less privacy concern for them.

Empact commented at 8:49 pm on July 13, 2018:

mu-nit: this comment would be slightly more relevant in the else block

sipa commented at 9:28 pm on July 13, 2018: member

utACK 2a361eb7d5832ec7e7dabccfb32dcbf815fad049; just nits.

jamesob commented at 9:58 pm on July 13, 2018: member

utACK https://github.com/bitcoin/bitcoin/commit/2a361eb7d5832ec7e7dabccfb32dcbf815fad049

gmaxwell commented at 9:58 pm on July 13, 2018: contributor

re-ACK

sdaftuar commented at 11:11 pm on July 13, 2018: member

utACK, sorry I let this slip, I have a bunch of simulation results that I had been meaning to revisit and summarize here (and I haven’t had a chance to really go through @naumenkogs’s latest results) but my short thought is that 1 bucket for inbound peers is probably the right answer and at any rate this is a substantial improvement compared with current behavior.

ACK’ing now so that we can get this merged for 0.17 (and I will try to come back and post additional observations / simulation results here later for others to review)

naumenkogs force-pushed on Jul 14, 2018

Bucket for inbound when scheduling invs to hide tx time d45b344ffd

in src/net.cpp:2871 in 496f9dcfa6 outdated

2868-    return nNow + (int64_t)(log1p(GetRand(1ULL << 48) * -0.0000000000000035527136788 /* -1/2^48 */) * average_interval_seconds * -1000000.0 + 0.5);
2869+int64_t CConnman::PoissonNextSendInbound(int64_t now, int average_interval_seconds)
2870+{
2871+    if (m_next_send_inv_to_incoming < now) {
2872+        // There is a theoretical possibility of a race condition here
2873+        // For now it is impossible, because this variable may be updated by 1 thread only

sipa commented at 2:39 am on July 14, 2018:

This sounds a bit contradictory: if there is a theoretical possibility, then it is not impossible.

Perhaps you can say “If this function were called from multiple threads simultaneously it would possible that both update the next send variable, and return a different result to their caller. This is not possible in practice as only the net processing thread invokes this function.”?

naumenkogs force-pushed on Jul 14, 2018

sipa commented at 8:51 pm on July 14, 2018: member

re-utACK d45b344ffd46b0226449cbd46cdaff9577402cf0

gmaxwell commented at 9:42 am on July 15, 2018: contributor

re-ACK

fanquake added this to the milestone 0.17.0 on Jul 15, 2018

jimpo commented at 4:25 pm on July 16, 2018: contributor

utACK d45b344

Empact commented at 8:01 pm on July 16, 2018: member

Looks like github is having some issues, but this has been merged in: f8d470e24606297dab95e30b1d39ff664fbda31d

sipa closed this on Jul 16, 2018

mruddy referenced this in commit f8d470e246 on Jul 16, 2018

sipa referenced this in commit bb676f4fad on Jul 16, 2018

sipa added the label Needs release notes on Jul 16, 2018

MarcoFalke referenced this in commit 0568dcd67d on Jul 16, 2018

sipa removed this from the "Blockers" column in a project

fanquake removed the label Needs release note on Mar 20, 2019

jasonbcox referenced this in commit bf845c5cc8 on Dec 20, 2019

codablock referenced this in commit 950e7ce276 on Apr 9, 2020

codablock referenced this in commit 89f6c6e9f0 on Apr 12, 2020

codablock referenced this in commit 359dd417a7 on Apr 12, 2020

codablock referenced this in commit 75498942ff on Apr 12, 2020

codablock referenced this in commit ea9f97c53b on Apr 14, 2020

PastaPastaPasta referenced this in commit a6f569eb60 on Jul 19, 2020

PastaPastaPasta referenced this in commit b35510650b on Jul 24, 2020

PastaPastaPasta referenced this in commit d8b4809954 on Jul 27, 2020

UdjinM6 referenced this in commit 6abae4c31d on Jul 27, 2020

UdjinM6 referenced this in commit d9cb2605f5 on Jul 27, 2020

jonspock referenced this in commit 93ea116cc9 on Oct 2, 2020

jonspock referenced this in commit 69f8e47d41 on Oct 5, 2020

jonspock referenced this in commit 151b4786fc on Oct 10, 2020

ckti referenced this in commit 98b5e623b3 on Mar 28, 2021

gades referenced this in commit bf765d00b9 on Feb 10, 2022

gades referenced this in commit 51f549b043 on Mar 23, 2022

DrahtBot locked this on Aug 25, 2022

Net: Bucketing INV delays (1 bucket) for incoming connections to hide tx time #13298

Meta

Analysis