diff options
author | fanquake <fanquake@gmail.com> | 2022-01-23 10:29:13 +0800 |
---|---|---|
committer | fanquake <fanquake@gmail.com> | 2022-01-23 11:44:02 +0800 |
commit | 6d859cbd794a36ed1c0c72324a4ec54d029b3d3b (patch) | |
tree | 281e70ce8f1532d82c6ebec2eff9c0687393b15e | |
parent | e3ce019667fba2ec50a59814a26566fb67fa9125 (diff) | |
parent | 9b8dcb25b57ad31b77c9f37d9a1f5b07dc6378b4 (diff) | |
download | bitcoin-6d859cbd794a36ed1c0c72324a4ec54d029b3d3b.tar.xz |
Merge bitcoin/bitcoin#24021: Rename and move PoissonNextSend functions
9b8dcb25b57ad31b77c9f37d9a1f5b07dc6378b4 [net processing] Rename PoissonNextSendInbound to NextInvToInbounds (John Newbery)
ea99f5d01e56ab0192d211da1034ffb299876937 [net processing] Move PoissonNextSendInbound to PeerManager (John Newbery)
bb060746df22c956b8f44e5b8cd1ae4ed73faddc scripted-diff: replace PoissonNextSend with GetExponentialRand (John Newbery)
03cfa1b6035dbcf6a414f9bc432bd9e612801ebb [refactor] Use uint64_t and std namespace in PoissonNextSend (John Newbery)
9e64d69bf74c8a381fb59841519cc3736bce14d4 [move] Move PoissonNextSend to src/random and update comment (John Newbery)
Pull request description:
`PoissonNextSend` and `PoissonNextSendInbound` are used in the p2p code to obfuscate various regularly occurring processes, in order to make it harder for others to get timing-based information deterministically.
The naming of these functions has been confusing to several people (including myself, see also #23347) because the resulting random timestamps don't follow a Poisson distribution but an exponential distribution (related to events in a Poisson process, hence the name). This PR
- moves `PoissonNextSend()` out of `net` to `random` and renames it to `GetExponentialRand()`
- moves `PoissonNextSendInbound()` out of `CConnman` to `PeerManager` and renames it to `NextInvToInbounds()`
- adds documentation for these functions
This is work by jnewbery - due to him being less active currently, I opened the PR and will address feedback.
ACKs for top commit:
jnewbery:
ACK 9b8dcb25b5
hebasto:
ACK 9b8dcb25b57ad31b77c9f37d9a1f5b07dc6378b4, I have reviewed the code and it looks OK, I agree it can be merged.
theStack:
ACK 9b8dcb25b57ad31b77c9f37d9a1f5b07dc6378b4 📊
Tree-SHA512: 85c366c994e7147f9981fe863fb9838502643fa61ffd32d55a43feef96a38b79a5daa2c4d38ce01074897cc95fa40c76779816edad53f5265b81b05c3a1f4f50
-rw-r--r-- | src/net.cpp | 27 | ||||
-rw-r--r-- | src/net.h | 11 | ||||
-rw-r--r-- | src/net_processing.cpp | 33 | ||||
-rw-r--r-- | src/random.cpp | 7 | ||||
-rw-r--r-- | src/random.h | 14 | ||||
-rw-r--r-- | src/test/fuzz/connman.cpp | 6 |
6 files changed, 53 insertions, 45 deletions
diff --git a/src/net.cpp b/src/net.cpp index 9f0e28df42..ac877df96d 100644 --- a/src/net.cpp +++ b/src/net.cpp @@ -1878,8 +1878,8 @@ void CConnman::ThreadOpenConnections(const std::vector<std::string> connect) auto start = GetTime<std::chrono::microseconds>(); // Minimum time before next feeler connection (in microseconds). - auto next_feeler = PoissonNextSend(start, FEELER_INTERVAL); - auto next_extra_block_relay = PoissonNextSend(start, EXTRA_BLOCK_RELAY_ONLY_PEER_INTERVAL); + auto next_feeler = GetExponentialRand(start, FEELER_INTERVAL); + auto next_extra_block_relay = GetExponentialRand(start, EXTRA_BLOCK_RELAY_ONLY_PEER_INTERVAL); const bool dnsseed = gArgs.GetBoolArg("-dnsseed", DEFAULT_DNSSEED); bool add_fixed_seeds = gArgs.GetBoolArg("-fixedseeds", DEFAULT_FIXEDSEEDS); @@ -1999,7 +1999,7 @@ void CConnman::ThreadOpenConnections(const std::vector<std::string> connect) // // This is similar to the logic for trying extra outbound (full-relay) // peers, except: - // - we do this all the time on a poisson timer, rather than just when + // - we do this all the time on an exponential timer, rather than just when // our tip is stale // - we potentially disconnect our next-youngest block-relay-only peer, if our // newest block-relay-only peer delivers a block more recently. @@ -2008,10 +2008,10 @@ void CConnman::ThreadOpenConnections(const std::vector<std::string> connect) // Because we can promote these connections to block-relay-only // connections, they do not get their own ConnectionType enum // (similar to how we deal with extra outbound peers). - next_extra_block_relay = PoissonNextSend(now, EXTRA_BLOCK_RELAY_ONLY_PEER_INTERVAL); + next_extra_block_relay = GetExponentialRand(now, EXTRA_BLOCK_RELAY_ONLY_PEER_INTERVAL); conn_type = ConnectionType::BLOCK_RELAY; } else if (now > next_feeler) { - next_feeler = PoissonNextSend(now, FEELER_INTERVAL); + next_feeler = GetExponentialRand(now, FEELER_INTERVAL); conn_type = ConnectionType::FEELER; fFeeler = true; } else { @@ -3058,23 +3058,6 @@ bool CConnman::ForNode(NodeId id, std::function<bool(CNode* pnode)> func) return found != nullptr && NodeFullyConnected(found) && func(found); } -std::chrono::microseconds CConnman::PoissonNextSendInbound(std::chrono::microseconds now, std::chrono::seconds average_interval) -{ - if (m_next_send_inv_to_incoming.load() < now) { - // 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. - m_next_send_inv_to_incoming = PoissonNextSend(now, average_interval); - } - return m_next_send_inv_to_incoming; -} - -std::chrono::microseconds PoissonNextSend(std::chrono::microseconds now, std::chrono::seconds average_interval) -{ - double unscaled = -log1p(GetRand(1ULL << 48) * -0.0000000000000035527136788 /* -1/2^48 */); - return now + std::chrono::duration_cast<std::chrono::microseconds>(unscaled * average_interval + 0.5us); -} - CSipHasher CConnman::GetDeterministicRandomizer(uint64_t id) const { return CSipHasher(nSeed0, nSeed1).Write(id); @@ -936,12 +936,6 @@ public: void WakeMessageHandler(); - /** Attempts to obfuscate tx time through exponentially distributed emitting. - Works assuming that a single interval is used. - Variable intervals will result in privacy decrease. - */ - std::chrono::microseconds PoissonNextSendInbound(std::chrono::microseconds now, std::chrono::seconds average_interval); - /** Return true if we should disconnect the peer for failing an inactivity check. */ bool ShouldRunInactivityChecks(const CNode& node, std::chrono::seconds now) const; @@ -1221,8 +1215,6 @@ private: */ std::atomic_bool m_start_extra_block_relay_peers{false}; - std::atomic<std::chrono::microseconds> m_next_send_inv_to_incoming{0us}; - /** * A vector of -bind=<address>:<port>=onion arguments each of which is * an address and port that are designated for incoming Tor connections. @@ -1270,9 +1262,6 @@ private: friend struct ConnmanTestMsg; }; -/** Return a timestamp in the future (in microseconds) for exponentially distributed events. */ -std::chrono::microseconds PoissonNextSend(std::chrono::microseconds now, std::chrono::seconds average_interval); - /** Dump binary message to file, with timestamp */ void CaptureMessage(const CAddress& addr, const std::string& msg_type, const Span<const unsigned char>& data, bool is_incoming); diff --git a/src/net_processing.cpp b/src/net_processing.cpp index 273cb4fccb..02542a6c87 100644 --- a/src/net_processing.cpp +++ b/src/net_processing.cpp @@ -450,6 +450,8 @@ private: */ std::map<NodeId, PeerRef> m_peer_map GUARDED_BY(m_peer_mutex); + std::atomic<std::chrono::microseconds> m_next_inv_to_inbounds{0us}; + /** Number of nodes with fSyncStarted. */ int nSyncStarted GUARDED_BY(cs_main) = 0; @@ -524,6 +526,15 @@ private: Mutex m_recent_confirmed_transactions_mutex; CRollingBloomFilter m_recent_confirmed_transactions GUARDED_BY(m_recent_confirmed_transactions_mutex){48'000, 0.000'001}; + /** + * For sending `inv`s to inbound peers, we use a single (exponentially + * distributed) timer for all peers. If we used a separate timer for each + * peer, a spy node could make multiple inbound connections to us to + * accurately determine when we received the transaction (and potentially + * determine the transaction's origin). */ + std::chrono::microseconds NextInvToInbounds(std::chrono::microseconds now, + std::chrono::seconds average_interval); + /** Have we requested this block from a peer */ bool IsBlockRequested(const uint256& hash) EXCLUSIVE_LOCKS_REQUIRED(cs_main); @@ -825,6 +836,18 @@ static void UpdatePreferredDownload(const CNode& node, CNodeState* state) EXCLUS nPreferredDownload += state->fPreferredDownload; } +std::chrono::microseconds PeerManagerImpl::NextInvToInbounds(std::chrono::microseconds now, + std::chrono::seconds average_interval) +{ + if (m_next_inv_to_inbounds.load() < now) { + // 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. + m_next_inv_to_inbounds = GetExponentialRand(now, average_interval); + } + return m_next_inv_to_inbounds; +} + bool PeerManagerImpl::IsBlockRequested(const uint256& hash) { return mapBlocksInFlight.find(hash) != mapBlocksInFlight.end(); @@ -4434,13 +4457,13 @@ void PeerManagerImpl::MaybeSendAddr(CNode& node, Peer& peer, std::chrono::micros FastRandomContext insecure_rand; PushAddress(peer, *local_addr, insecure_rand); } - peer.m_next_local_addr_send = PoissonNextSend(current_time, AVG_LOCAL_ADDRESS_BROADCAST_INTERVAL); + peer.m_next_local_addr_send = GetExponentialRand(current_time, AVG_LOCAL_ADDRESS_BROADCAST_INTERVAL); } // We sent an `addr` message to this peer recently. Nothing more to do. if (current_time <= peer.m_next_addr_send) return; - peer.m_next_addr_send = PoissonNextSend(current_time, AVG_ADDRESS_BROADCAST_INTERVAL); + peer.m_next_addr_send = GetExponentialRand(current_time, AVG_ADDRESS_BROADCAST_INTERVAL); if (!Assume(peer.m_addrs_to_send.size() <= MAX_ADDR_TO_SEND)) { // Should be impossible since we always check size before adding to @@ -4512,7 +4535,7 @@ void PeerManagerImpl::MaybeSendFeefilter(CNode& pto, std::chrono::microseconds c m_connman.PushMessage(&pto, CNetMsgMaker(pto.GetCommonVersion()).Make(NetMsgType::FEEFILTER, filterToSend)); pto.m_tx_relay->lastSentFeeFilter = filterToSend; } - pto.m_tx_relay->m_next_send_feefilter = PoissonNextSend(current_time, AVG_FEEFILTER_BROADCAST_INTERVAL); + pto.m_tx_relay->m_next_send_feefilter = GetExponentialRand(current_time, AVG_FEEFILTER_BROADCAST_INTERVAL); } // If the fee filter has changed substantially and it's still more than MAX_FEEFILTER_CHANGE_DELAY // until scheduled broadcast, then move the broadcast to within MAX_FEEFILTER_CHANGE_DELAY. @@ -4792,9 +4815,9 @@ bool PeerManagerImpl::SendMessages(CNode* pto) if (pto->m_tx_relay->nNextInvSend < current_time) { fSendTrickle = true; if (pto->IsInboundConn()) { - pto->m_tx_relay->nNextInvSend = m_connman.PoissonNextSendInbound(current_time, INBOUND_INVENTORY_BROADCAST_INTERVAL); + pto->m_tx_relay->nNextInvSend = NextInvToInbounds(current_time, INBOUND_INVENTORY_BROADCAST_INTERVAL); } else { - pto->m_tx_relay->nNextInvSend = PoissonNextSend(current_time, OUTBOUND_INVENTORY_BROADCAST_INTERVAL); + pto->m_tx_relay->nNextInvSend = GetExponentialRand(current_time, OUTBOUND_INVENTORY_BROADCAST_INTERVAL); } } diff --git a/src/random.cpp b/src/random.cpp index 6eb06c5d47..5dae80fe31 100644 --- a/src/random.cpp +++ b/src/random.cpp @@ -19,6 +19,7 @@ #include <sync.h> // for Mutex #include <util/time.h> // for GetTimeMicros() +#include <cmath> #include <stdlib.h> #include <thread> @@ -714,3 +715,9 @@ void RandomInit() ReportHardwareRand(); } + +std::chrono::microseconds GetExponentialRand(std::chrono::microseconds now, std::chrono::seconds average_interval) +{ + double unscaled = -std::log1p(GetRand(uint64_t{1} << 48) * -0.0000000000000035527136788 /* -1/2^48 */); + return now + std::chrono::duration_cast<std::chrono::microseconds>(unscaled * average_interval + 0.5us); +} diff --git a/src/random.h b/src/random.h index 0c6dc24983..5174c553fb 100644 --- a/src/random.h +++ b/src/random.h @@ -10,7 +10,7 @@ #include <crypto/common.h> #include <uint256.h> -#include <chrono> // For std::chrono::microseconds +#include <chrono> #include <cstdint> #include <limits> @@ -82,6 +82,18 @@ D GetRandomDuration(typename std::common_type<D>::type max) noexcept }; constexpr auto GetRandMicros = GetRandomDuration<std::chrono::microseconds>; constexpr auto GetRandMillis = GetRandomDuration<std::chrono::milliseconds>; + +/** + * Return a timestamp in the future sampled from an exponential distribution + * (https://en.wikipedia.org/wiki/Exponential_distribution). This distribution + * is memoryless and should be used for repeated network events (e.g. sending a + * certain type of message) to minimize leaking information to observers. + * + * The probability of an event occuring before time x is 1 - e^-(x/a) where a + * is the average interval between events. + * */ +std::chrono::microseconds GetExponentialRand(std::chrono::microseconds now, std::chrono::seconds average_interval); + int GetRandInt(int nMax) noexcept; uint256 GetRandHash() noexcept; diff --git a/src/test/fuzz/connman.cpp b/src/test/fuzz/connman.cpp index 240274664a..a14d28f4ef 100644 --- a/src/test/fuzz/connman.cpp +++ b/src/test/fuzz/connman.cpp @@ -98,12 +98,6 @@ FUZZ_TARGET_INIT(connman, initialize_connman) (void)connman.OutboundTargetReached(fuzzed_data_provider.ConsumeBool()); }, [&] { - // Limit now to int32_t to avoid signed integer overflow - (void)connman.PoissonNextSendInbound( - std::chrono::microseconds{fuzzed_data_provider.ConsumeIntegral<int32_t>()}, - std::chrono::seconds{fuzzed_data_provider.ConsumeIntegral<int>()}); - }, - [&] { CSerializedNetMsg serialized_net_msg; serialized_net_msg.m_type = fuzzed_data_provider.ConsumeRandomLengthString(CMessageHeader::COMMAND_SIZE); serialized_net_msg.data = ConsumeRandomLengthByteVector(fuzzed_data_provider); |