From f2d3ba73860e875972738d1da1507124d0971ae5 Mon Sep 17 00:00:00 2001 From: Gregory Maxwell Date: Mon, 4 Apr 2016 02:36:47 +0000 Subject: 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. --- src/main.cpp | 60 ++++++++++++++++++++++++++++++++++++------------------------ 1 file changed, 36 insertions(+), 24 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index a94d52f89..4a28bbb00 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -5560,6 +5560,29 @@ bool ProcessMessages(CNode* pfrom) return fOk; } +class CompareInvMempoolOrder +{ + CTxMemPool *mp; +public: + CompareInvMempoolOrder(CTxMemPool *mempool) + { + mp = mempool; + } + + bool operator()(const CInv &a, const CInv &b) + { + if (a.type != MSG_TX && b.type != MSG_TX) { + return false; + } else { + if (a.type != MSG_TX) { + return true; + } else if (b.type != MSG_TX) { + return false; + } + return mp->CompareDepthAndScore(a.hash, b.hash); + } + } +}; bool SendMessages(CNode* pto) { @@ -5790,42 +5813,31 @@ bool SendMessages(CNode* pto) bool fSendTrickle = pto->fWhitelisted; if (pto->nNextInvSend < nNow) { fSendTrickle = true; - pto->nNextInvSend = PoissonNextSend(nNow, AVG_INVENTORY_BROADCAST_INTERVAL); + // Use half the delay for outbound peers, as their is less privacy concern for them. + pto->nNextInvSend = PoissonNextSend(nNow, INVENTORY_BROADCAST_INTERVAL >> !pto->fInbound); } LOCK(pto->cs_inventory); - vInv.reserve(std::min(1000, pto->vInventoryToSend.size())); + if (fSendTrickle && pto->vInventoryToSend.size() > 1) { + // Topologically and fee-rate sort the inventory we send for privacy and priority reasons. + CompareInvMempoolOrder compareInvMempoolOrder(&mempool); + std::stable_sort(pto->vInventoryToSend.begin(), pto->vInventoryToSend.end(), compareInvMempoolOrder); + } + vInv.reserve(std::min(INVENTORY_BROADCAST_MAX, pto->vInventoryToSend.size())); vInvWait.reserve(pto->vInventoryToSend.size()); BOOST_FOREACH(const CInv& inv, pto->vInventoryToSend) { if (inv.type == MSG_TX && pto->filterInventoryKnown.contains(inv.hash)) continue; - - // trickle out tx inv to protect privacy - if (inv.type == MSG_TX && !fSendTrickle) - { - // 1/4 of tx invs blast to all immediately - static uint256 hashSalt; - if (hashSalt.IsNull()) - hashSalt = GetRandHash(); - uint256 hashRand = ArithToUint256(UintToArith256(inv.hash) ^ UintToArith256(hashSalt)); - hashRand = Hash(BEGIN(hashRand), END(hashRand)); - bool fTrickleWait = ((UintToArith256(hashRand) & 3) != 0); - - if (fTrickleWait) - { - vInvWait.push_back(inv); - continue; - } + // No reason to drain out at many times the network's capacity, + // especially since we have many peers and some will draw much shorter delays. + if (vInv.size() >= INVENTORY_BROADCAST_MAX || (inv.type == MSG_TX && !fSendTrickle)) { + vInvWait.push_back(inv); + continue; } pto->filterInventoryKnown.insert(inv.hash); vInv.push_back(inv); - if (vInv.size() >= 1000) - { - pto->PushMessage(NetMsgType::INV, vInv); - vInv.clear(); - } } pto->vInventoryToSend = vInvWait; } -- cgit v1.2.3 From dc13dcd2bec2613a1cd5e0395b09b449d176146f Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Thu, 7 Apr 2016 13:57:36 +0200 Subject: Split up and optimize transaction and block inv queues --- src/main.cpp | 76 +++++++++++++++++++++++++++++++++++------------------------- 1 file changed, 45 insertions(+), 31 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 4a28bbb00..61d9301f8 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -5569,18 +5569,11 @@ public: mp = mempool; } - bool operator()(const CInv &a, const CInv &b) + bool operator()(std::set::iterator a, std::set::iterator b) { - if (a.type != MSG_TX && b.type != MSG_TX) { - return false; - } else { - if (a.type != MSG_TX) { - return true; - } else if (b.type != MSG_TX) { - return false; - } - return mp->CompareDepthAndScore(a.hash, b.hash); - } + /* As std::make_heap produces a max-heap, we want the entries with the + * fewest ancestors/highest fee to sort later. */ + return mp->CompareDepthAndScore(*b, *a); } }; @@ -5808,38 +5801,59 @@ bool SendMessages(CNode* pto) // Message: inventory // vector vInv; - vector vInvWait; { + LOCK(pto->cs_inventory); + vInv.reserve(std::max(pto->vInventoryBlockToSend.size(), INVENTORY_BROADCAST_MAX)); + + // Add blocks + BOOST_FOREACH(const uint256& hash, pto->vInventoryBlockToSend) { + vInv.push_back(CInv(MSG_BLOCK, hash)); + if (vInv.size() == MAX_INV_SZ) { + pto->PushMessage(NetMsgType::INV, vInv); + vInv.clear(); + } + } + pto->vInventoryBlockToSend.clear(); + + // Determine transactions to relay bool fSendTrickle = pto->fWhitelisted; if (pto->nNextInvSend < nNow) { fSendTrickle = true; - // Use half the delay for outbound peers, as their is less privacy concern for them. + // Use half the delay for outbound peers, as there is less privacy concern for them. pto->nNextInvSend = PoissonNextSend(nNow, INVENTORY_BROADCAST_INTERVAL >> !pto->fInbound); } - LOCK(pto->cs_inventory); - if (fSendTrickle && pto->vInventoryToSend.size() > 1) { + if (fSendTrickle) { + // Produce a vector with all candidates for sending + vector::iterator> vInvTx; + vInvTx.reserve(pto->setInventoryTxToSend.size()); + for (std::set::iterator it = pto->setInventoryTxToSend.begin(); it != pto->setInventoryTxToSend.end(); it++) { + vInvTx.push_back(it); + } // Topologically and fee-rate sort the inventory we send for privacy and priority reasons. + // A heap is used so that not all items need sorting if only a few are being sent. CompareInvMempoolOrder compareInvMempoolOrder(&mempool); - std::stable_sort(pto->vInventoryToSend.begin(), pto->vInventoryToSend.end(), compareInvMempoolOrder); - } - vInv.reserve(std::min(INVENTORY_BROADCAST_MAX, pto->vInventoryToSend.size())); - vInvWait.reserve(pto->vInventoryToSend.size()); - BOOST_FOREACH(const CInv& inv, pto->vInventoryToSend) - { - if (inv.type == MSG_TX && pto->filterInventoryKnown.contains(inv.hash)) - continue; + std::make_heap(vInvTx.begin(), vInvTx.end(), compareInvMempoolOrder); // No reason to drain out at many times the network's capacity, // especially since we have many peers and some will draw much shorter delays. - if (vInv.size() >= INVENTORY_BROADCAST_MAX || (inv.type == MSG_TX && !fSendTrickle)) { - vInvWait.push_back(inv); - continue; + unsigned int nRelayedTransactions = 0; + while (!vInvTx.empty() && nRelayedTransactions < INVENTORY_BROADCAST_MAX) { + // Fetch the top element from the heap + std::pop_heap(vInvTx.begin(), vInvTx.end(), compareInvMempoolOrder); + std::set::iterator it = vInvTx.back(); + vInvTx.pop_back(); + uint256 hash = *it; + // Remove it from the to-be-sent set + pto->setInventoryTxToSend.erase(it); + // Check if not in the filter already + if (pto->filterInventoryKnown.contains(hash)) { + continue; + } + // Send + vInv.push_back(CInv(MSG_TX, hash)); + nRelayedTransactions++; + pto->filterInventoryKnown.insert(hash); } - - pto->filterInventoryKnown.insert(inv.hash); - - vInv.push_back(inv); } - pto->vInventoryToSend = vInvWait; } if (!vInv.empty()) pto->PushMessage(NetMsgType::INV, vInv); -- cgit v1.2.3 From ed7068302c7490e8061cb3a558a0f83a465beeea Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Fri, 8 Apr 2016 16:26:41 +0200 Subject: Handle mempool requests in send loop, subject to trickle By eliminating queued entries from the mempool response and responding only at trickle time, this makes the mempool no longer leak transaction arrival order information (as the mempool itself is also sorted)-- at least no more than relay itself leaks it. --- src/main.cpp | 74 +++++++++++++++++++++++++++++++++++++----------------------- 1 file changed, 46 insertions(+), 28 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 61d9301f8..282c8cdb6 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -5235,34 +5235,9 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, pfrom->fDisconnect = true; return true; } - LOCK2(cs_main, pfrom->cs_filter); - std::vector vtxid; - mempool.queryHashes(vtxid); - vector vInv; - BOOST_FOREACH(uint256& hash, vtxid) { - CInv inv(MSG_TX, hash); - if (pfrom->pfilter) { - CTransaction tx; - bool fInMemPool = mempool.lookup(hash, tx); - if (!fInMemPool) continue; // another thread removed since queryHashes, maybe... - if (!pfrom->pfilter->IsRelevantAndUpdate(tx)) continue; - } - if (pfrom->minFeeFilter) { - CFeeRate feeRate; - mempool.lookupFeeRate(hash, feeRate); - LOCK(pfrom->cs_feeFilter); - if (feeRate.GetFeePerK() < pfrom->minFeeFilter) - continue; - } - vInv.push_back(inv); - if (vInv.size() == MAX_INV_SZ) { - pfrom->PushMessage(NetMsgType::INV, vInv); - vInv.clear(); - } - } - if (vInv.size() > 0) - pfrom->PushMessage(NetMsgType::INV, vInv); + LOCK(pfrom->cs_inventory); + pfrom->fSendMempool = true; } @@ -5815,13 +5790,52 @@ bool SendMessages(CNode* pto) } pto->vInventoryBlockToSend.clear(); - // Determine transactions to relay + // Check whether periodic sends should happen bool fSendTrickle = pto->fWhitelisted; if (pto->nNextInvSend < nNow) { fSendTrickle = true; // Use half the delay for outbound peers, as there is less privacy concern for them. pto->nNextInvSend = PoissonNextSend(nNow, INVENTORY_BROADCAST_INTERVAL >> !pto->fInbound); } + + // Respond to BIP35 mempool requests + if (fSendTrickle && pto->fSendMempool) { + std::vector vtxid; + mempool.queryHashes(vtxid); + pto->fSendMempool = false; + CAmount filterrate = 0; + { + LOCK(pto->cs_feeFilter); + filterrate = pto->minFeeFilter; + } + + LOCK(pto->cs_filter); + + BOOST_FOREACH(const uint256& hash, vtxid) { + CInv inv(MSG_TX, hash); + pto->setInventoryTxToSend.erase(hash); + if (filterrate) { + CFeeRate feeRate; + mempool.lookupFeeRate(hash, feeRate); + if (feeRate.GetFeePerK() < filterrate) + continue; + } + if (pto->pfilter) { + CTransaction tx; + bool fInMemPool = mempool.lookup(hash, tx); + if (!fInMemPool) continue; // another thread removed since queryHashes, maybe... + if (!pto->pfilter->IsRelevantAndUpdate(tx)) continue; + } + pto->filterInventoryKnown.insert(hash); + vInv.push_back(inv); + if (vInv.size() == MAX_INV_SZ) { + pto->PushMessage(NetMsgType::INV, vInv); + vInv.clear(); + } + } + } + + // Determine transactions to relay if (fSendTrickle) { // Produce a vector with all candidates for sending vector::iterator> vInvTx; @@ -5851,6 +5865,10 @@ bool SendMessages(CNode* pto) // Send vInv.push_back(CInv(MSG_TX, hash)); nRelayedTransactions++; + if (vInv.size() == MAX_INV_SZ) { + pto->PushMessage(NetMsgType::INV, vInv); + vInv.clear(); + } pto->filterInventoryKnown.insert(hash); } } -- cgit v1.2.3 From b5599147533103efea896a1fc4ff51f2d3ad5808 Mon Sep 17 00:00:00 2001 From: Gregory Maxwell Date: Wed, 20 Apr 2016 07:05:23 +0000 Subject: Move bloom and feerate filtering to just prior to tx sending. This will avoid sending more pointless INVs around updates, and prevents using filter updates to timetag transactions. Also adds locking for fRelayTxes. --- src/main.cpp | 42 ++++++++++++++++++++++++++++++++++++------ 1 file changed, 36 insertions(+), 6 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 282c8cdb6..b707de2e5 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -4557,12 +4557,16 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, vRecv >> LIMITED_STRING(pfrom->strSubVer, MAX_SUBVERSION_LENGTH); pfrom->cleanSubVer = SanitizeString(pfrom->strSubVer); } - if (!vRecv.empty()) + if (!vRecv.empty()) { vRecv >> pfrom->nStartingHeight; - if (!vRecv.empty()) - vRecv >> pfrom->fRelayTxes; // set to true after we get the first filter* message - else - pfrom->fRelayTxes = true; + } + { + LOCK(pfrom->cs_filter); + if (!vRecv.empty()) + vRecv >> pfrom->fRelayTxes; // set to true after we get the first filter* message + else + pfrom->fRelayTxes = true; + } // Disconnect if we connected to ourself if (nNonce == nLocalHostNonce && nNonce > 1) @@ -5325,12 +5329,13 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, CBloomFilter filter; vRecv >> filter; + LOCK(pfrom->cs_filter); + if (!filter.IsWithinSizeConstraints()) // There is no excuse for sending a too-large filter Misbehaving(pfrom->GetId(), 100); else { - LOCK(pfrom->cs_filter); delete pfrom->pfilter; pfrom->pfilter = new CBloomFilter(filter); pfrom->pfilter->UpdateEmptyFull(); @@ -5798,6 +5803,12 @@ bool SendMessages(CNode* pto) pto->nNextInvSend = PoissonNextSend(nNow, INVENTORY_BROADCAST_INTERVAL >> !pto->fInbound); } + // Time to send but the peer has requested we not relay transactions. + if (fSendTrickle) { + LOCK(pto->cs_filter); + if (!pto->fRelayTxes) pto->setInventoryTxToSend.clear(); + } + // Respond to BIP35 mempool requests if (fSendTrickle && pto->fSendMempool) { std::vector vtxid; @@ -5843,6 +5854,11 @@ bool SendMessages(CNode* pto) for (std::set::iterator it = pto->setInventoryTxToSend.begin(); it != pto->setInventoryTxToSend.end(); it++) { vInvTx.push_back(it); } + CAmount filterrate = 0; + { + LOCK(pto->cs_feeFilter); + filterrate = pto->minFeeFilter; + } // Topologically and fee-rate sort the inventory we send for privacy and priority reasons. // A heap is used so that not all items need sorting if only a few are being sent. CompareInvMempoolOrder compareInvMempoolOrder(&mempool); @@ -5850,6 +5866,7 @@ bool SendMessages(CNode* pto) // No reason to drain out at many times the network's capacity, // especially since we have many peers and some will draw much shorter delays. unsigned int nRelayedTransactions = 0; + LOCK(pto->cs_filter); while (!vInvTx.empty() && nRelayedTransactions < INVENTORY_BROADCAST_MAX) { // Fetch the top element from the heap std::pop_heap(vInvTx.begin(), vInvTx.end(), compareInvMempoolOrder); @@ -5862,6 +5879,19 @@ bool SendMessages(CNode* pto) if (pto->filterInventoryKnown.contains(hash)) { continue; } + // Not in the mempool anymore? don't bother sending it. + CFeeRate feeRate; + if (!mempool.lookupFeeRate(hash, feeRate)) { + continue; + } + if (filterrate && feeRate.GetFeePerK() < filterrate) { + continue; + } + if (pto->pfilter) { + CTransaction tx; + if (!mempool.lookup(hash, tx)) continue; + if (!pto->pfilter->IsRelevantAndUpdate(tx)) continue; + } // Send vInv.push_back(CInv(MSG_TX, hash)); nRelayedTransactions++; -- cgit v1.2.3