From 422d1225374e2d879dbd116151e0113aa7162500 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Mon, 13 Aug 2012 05:26:29 +0200 Subject: Add a filter field in CNode, add filterload+filteradd+filterclear --- src/main.cpp | 45 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index cb7975af0..9a498ff27 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -3332,6 +3332,51 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) } + else if (strCommand == "filterload") + { + CBloomFilter filter; + vRecv >> filter; + + if (!filter.IsWithinSizeConstraints()) + // There is no excuse for sending a too-large filter + pfrom->Misbehaving(100); + else + { + LOCK(pfrom->cs_filter); + delete pfrom->pfilter; + pfrom->pfilter = new CBloomFilter(filter); + } + } + + + else if (strCommand == "filteradd") + { + vector vData; + vRecv >> vData; + + // Nodes must NEVER send a data item > 520 bytes (the max size for a script data object, + // and thus, the maximum size any matched object can have) in a filteradd message + if (vData.size() > 520) + { + pfrom->Misbehaving(100); + } else { + LOCK(pfrom->cs_filter); + if (pfrom->pfilter) + pfrom->pfilter->insert(vData); + else + pfrom->Misbehaving(100); + } + } + + + else if (strCommand == "filterclear") + { + LOCK(pfrom->cs_filter); + delete pfrom->pfilter; + pfrom->pfilter = NULL; + } + + else { // Ignore unknown commands for extensibility -- cgit v1.2.3 From 269d9c6492dc275650d2137d53f4afdca88e3216 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Mon, 13 Aug 2012 05:26:30 +0200 Subject: Replace RelayMessage with RelayTransaction. --- src/main.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 9a498ff27..93079693c 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -3184,7 +3184,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) if (tx.AcceptToMemoryPool(true, &fMissingInputs)) { SyncWithWallets(inv.hash, tx, NULL, true); - RelayMessage(inv, vMsg); + RelayTransaction(tx, inv.hash, vMsg); mapAlreadyAskedFor.erase(inv); vWorkQueue.push_back(inv.hash); vEraseQueue.push_back(inv.hash); @@ -3207,7 +3207,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) { printf(" accepted orphan tx %s\n", inv.hash.ToString().substr(0,10).c_str()); SyncWithWallets(inv.hash, tx, NULL, true); - RelayMessage(inv, vMsg); + RelayTransaction(tx, inv.hash, vMsg); mapAlreadyAskedFor.erase(inv); vWorkQueue.push_back(inv.hash); vEraseQueue.push_back(inv.hash); -- cgit v1.2.3 From 9fb106e7579831b4ab682d2e6f588662d0f445d0 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Sat, 18 Aug 2012 23:40:00 -0400 Subject: Add a CMerkleBlock to store merkle branches of filtered txes. --- src/main.cpp | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 93079693c..bd5b2408a 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -2239,6 +2239,29 @@ bool ProcessBlock(CNode* pfrom, CBlock* pblock, CDiskBlockPos *dbp) +CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter& filter) +{ + header = block.GetBlockHeader(); + vtx.reserve(block.vtx.size()); + + for(unsigned int i = 0; i < block.vtx.size(); i++) + { + vector branch = block.GetMerkleBranch(i); + uint256 hash = block.vtx[i].GetHash(); + if (filter.IsRelevantAndUpdate(block.vtx[i], hash)) + { + vtx.push_back(make_tuple(i, hash, branch)); + } + } +} + + + + + + + + bool CheckDiskSpace(uint64 nAdditionalBytes) { uint64 nFreeBytesAvailable = filesystem::space(GetDataDir()).available; -- cgit v1.2.3 From b02ddbedcba4f9d86b1aabeb71fe18ec03f9a41a Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Sat, 18 Aug 2012 23:45:19 -0400 Subject: Relay CMerkleBlocks when asked for MSG_FILTERED_BLOCK --- src/main.cpp | 26 ++++++++++++++++++++++++-- 1 file changed, 24 insertions(+), 2 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index bd5b2408a..abb0174ed 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -3068,7 +3068,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) if (fDebugNet || (vInv.size() == 1)) printf("received getdata for: %s\n", inv.ToString().c_str()); - if (inv.type == MSG_BLOCK) + if (inv.type == MSG_BLOCK || inv.type == MSG_FILTERED_BLOCK) { // Send block from disk map::iterator mi = mapBlockIndex.find(inv.hash); @@ -3076,7 +3076,29 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) { CBlock block; block.ReadFromDisk((*mi).second); - pfrom->PushMessage("block", block); + if (inv.type == MSG_BLOCK) + pfrom->PushMessage("block", block); + else // MSG_FILTERED_BLOCK) + { + LOCK(pfrom->cs_filter); + if (pfrom->pfilter) + { + CMerkleBlock merkleBlock(block, *pfrom->pfilter); + typedef boost::tuple > TupleType; + // CMerkleBlock just contains hashes, so also push any transactions in the block the client did not see + // This avoids hurting performance by pointlessly requiring a round-trip + // Note that there is currently no way for a node to request any single transactions we didnt send here - + // they must either disconnect and retry or request the full block. + // Thus, the protocol spec specified allows for us to provide duplicate txn here, + // however we MUST always provide at least what the remote peer needs + BOOST_FOREACH(TupleType& tuple, merkleBlock.vtx) + if (!pfrom->setInventoryKnown.count(CInv(MSG_TX, get<1>(tuple)))) + pfrom->PushMessage("tx", block.vtx[get<0>(tuple)]); + pfrom->PushMessage("merkleblock", merkleBlock); + } + // else + // no response + } // Trigger them to send a getblocks request for the next batch of inventory if (inv.hash == pfrom->hashContinue) -- cgit v1.2.3 From 4c8fc1a5885634c3b463d5d44337d81cc5b1456b Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Mon, 20 Aug 2012 21:10:25 -0400 Subject: Let a node opt out of tx invs before we get a their bloom filter Note that the default value for fRelayTxes is false, meaning we now no longer relay tx inv messages before receiving the remote peer's version message. --- src/main.cpp | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index abb0174ed..1c1de636a 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -2838,6 +2838,10 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) vRecv >> pfrom->strSubVer; 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; if (pfrom->fInbound && addrMe.IsRoutable()) { @@ -3391,6 +3395,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) delete pfrom->pfilter; pfrom->pfilter = new CBloomFilter(filter); } + pfrom->fRelayTxes = true; } @@ -3419,6 +3424,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) LOCK(pfrom->cs_filter); delete pfrom->pfilter; pfrom->pfilter = NULL; + pfrom->fRelayTxes = true; } -- cgit v1.2.3 From 4bedfa9223d38bbc322d19e28ca03417c216700b Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Sat, 27 Oct 2012 21:08:45 +0200 Subject: Add CPartialMerkleTree This adds a compact representation for a subset of a merkle tree's nodes. --- src/main.cpp | 121 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 121 insertions(+) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 1c1de636a..91fe6ba8f 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -2262,6 +2262,127 @@ CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter& filter) +uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, const std::vector &vTxid) { + if (height == 0) { + // hash at height 0 is the txids themself + return vTxid[pos]; + } else { + // calculate left hash + uint256 left = CalcHash(height-1, pos*2, vTxid), right; + // calculate right hash if not beyong the end of the array - copy left hash otherwise1 + if (pos*2+1 < CalcTreeWidth(height-1)) + right = CalcHash(height-1, pos*2+1, vTxid); + else + right = left; + // combine subhashes + return Hash(BEGIN(left), END(left), BEGIN(right), END(right)); + } +} + +void CPartialMerkleTree::TraverseAndBuild(int height, unsigned int pos, const std::vector &vTxid, const std::vector &vMatch) { + // determine whether this node is the parent of at least one matched txid + bool fParentOfMatch = false; + for (unsigned int p = pos << height; p < (pos+1) << height && p < nTransactions; p++) + fParentOfMatch |= vMatch[p]; + // store as flag bit + vBits.push_back(fParentOfMatch); + if (height==0 || !fParentOfMatch) { + // if at height 0, or nothing interesting below, store hash and stop + vHash.push_back(CalcHash(height, pos, vTxid)); + } else { + // otherwise, don't store any hash, but descend into the subtrees + TraverseAndBuild(height-1, pos*2, vTxid, vMatch); + if (pos*2+1 < CalcTreeWidth(height-1)) + TraverseAndBuild(height-1, pos*2+1, vTxid, vMatch); + } +} + +uint256 CPartialMerkleTree::TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector &vMatch) { + if (nBitsUsed >= vBits.size()) { + // overflowed the bits array - failure + fBad = true; + return 0; + } + bool fParentOfMatch = vBits[nBitsUsed++]; + if (height==0 || !fParentOfMatch) { + // if at height 0, or nothing interesting below, use stored hash and do not descend + if (nHashUsed >= vHash.size()) { + // overflowed the hash array - failure + fBad = true; + return 0; + } + const uint256 &hash = vHash[nHashUsed++]; + if (height==0 && fParentOfMatch) // in case of height 0, we have a matched txid + vMatch.push_back(hash); + return hash; + } else { + // otherwise, descend into the subtrees to extract matched txids and hashes + uint256 left = TraverseAndExtract(height-1, pos*2, nBitsUsed, nHashUsed, vMatch), right; + if (pos*2+1 < CalcTreeWidth(height-1)) + right = TraverseAndExtract(height-1, pos*2+1, nBitsUsed, nHashUsed, vMatch); + else + right = left; + // and combine them before returning + return Hash(BEGIN(left), END(left), BEGIN(right), END(right)); + } +} + +CPartialMerkleTree::CPartialMerkleTree(const std::vector &vTxid, const std::vector &vMatch) : nTransactions(vTxid.size()), fBad(false) { + // reset state + vBits.clear(); + vHash.clear(); + + // calculate height of tree + int nHeight = 0; + while (CalcTreeWidth(nHeight) > 1) + nHeight++; + + // traverse the partial tree + TraverseAndBuild(nHeight, 0, vTxid, vMatch); +} + +CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {} + +uint256 CPartialMerkleTree::ExtractMatches(std::vector &vMatch) { + vMatch.clear(); + // An empty set will not work + if (nTransactions == 0) + return 0; + // check for excessively high numbers of transactions + if (nTransactions > MAX_BLOCK_SIZE / 60) // 60 is the lower bound for the size of a serialized CTransaction + return 0; + // there can never be more hashes provided than one for every txid + if (vHash.size() > nTransactions) + return 0; + // there must be at least one bit per node in the partial tree, and at least one node per hash + if (vBits.size() < vHash.size()) + return 0; + // calculate height of tree + int nHeight = 0; + while (CalcTreeWidth(nHeight) > 1) + nHeight++; + // traverse the partial tree + unsigned int nBitsUsed = 0, nHashUsed = 0; + uint256 hashMerkleRoot = TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch); + // verify that no problems occured during the tree traversal + if (fBad) + return 0; + // verify that all bits were consumed (except for the padding caused by serializing it as a byte sequence) + if ((nBitsUsed+7)/8 != (vBits.size()+7)/8) + return 0; + // verify that all hashes were consumed + if (nHashUsed != vHash.size()) + return 0; + return hashMerkleRoot; +} + + + + + + + + bool CheckDiskSpace(uint64 nAdditionalBytes) { uint64 nFreeBytesAvailable = filesystem::space(GetDataDir()).available; -- cgit v1.2.3 From 21aaf255ff4553ae538fb90011b0185bc8039896 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Thu, 8 Nov 2012 16:26:25 -0500 Subject: Use CPartialMerkleTree for CMerkleBlock transactions. --- src/main.cpp | 26 ++++++++++++++++++-------- 1 file changed, 18 insertions(+), 8 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 91fe6ba8f..644c5d0e6 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -2242,17 +2242,27 @@ bool ProcessBlock(CNode* pfrom, CBlock* pblock, CDiskBlockPos *dbp) CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter& filter) { header = block.GetBlockHeader(); - vtx.reserve(block.vtx.size()); - for(unsigned int i = 0; i < block.vtx.size(); i++) + vector vMatch; + vector vHashes; + + vMatch.reserve(block.vtx.size()); + vHashes.reserve(block.vtx.size()); + + for (unsigned int i = 0; i < block.vtx.size(); i++) { - vector branch = block.GetMerkleBranch(i); uint256 hash = block.vtx[i].GetHash(); if (filter.IsRelevantAndUpdate(block.vtx[i], hash)) { - vtx.push_back(make_tuple(i, hash, branch)); + vMatch.push_back(true); + vMatchedTxn.push_back(make_pair(i, hash)); } + else + vMatch.push_back(false); + vHashes.push_back(hash); } + + txn = CPartialMerkleTree(vHashes, vMatch); } @@ -3209,16 +3219,16 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) if (pfrom->pfilter) { CMerkleBlock merkleBlock(block, *pfrom->pfilter); - typedef boost::tuple > TupleType; // CMerkleBlock just contains hashes, so also push any transactions in the block the client did not see // This avoids hurting performance by pointlessly requiring a round-trip // Note that there is currently no way for a node to request any single transactions we didnt send here - // they must either disconnect and retry or request the full block. // Thus, the protocol spec specified allows for us to provide duplicate txn here, // however we MUST always provide at least what the remote peer needs - BOOST_FOREACH(TupleType& tuple, merkleBlock.vtx) - if (!pfrom->setInventoryKnown.count(CInv(MSG_TX, get<1>(tuple)))) - pfrom->PushMessage("tx", block.vtx[get<0>(tuple)]); + typedef std::pair PairType; + BOOST_FOREACH(PairType& pair, merkleBlock.vMatchedTxn) + if (!pfrom->setInventoryKnown.count(CInv(MSG_TX, pair.second))) + pfrom->PushMessage("tx", block.vtx[pair.first]); pfrom->PushMessage("merkleblock", merkleBlock); } // else -- cgit v1.2.3 From c51694eb9b9db915beb1da8d76667d94f4f74c75 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Thu, 10 Jan 2013 14:06:30 -0500 Subject: Filter mempool command --- src/main.cpp | 13 ++++++++----- 1 file changed, 8 insertions(+), 5 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 644c5d0e6..1eb4124c1 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -3446,13 +3446,16 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) else if (strCommand == "mempool") { std::vector vtxid; + LOCK2(mempool.cs, pfrom->cs_filter); mempool.queryHashes(vtxid); vector vInv; - for (unsigned int i = 0; i < vtxid.size(); i++) { - CInv inv(MSG_TX, vtxid[i]); - vInv.push_back(inv); - if (i == (MAX_INV_SZ - 1)) - break; + BOOST_FOREACH(uint256& hash, vtxid) { + CInv inv(MSG_TX, hash); + if ((pfrom->pfilter && pfrom->pfilter->IsRelevantAndUpdate(mempool.lookup(hash), hash)) || + (!pfrom->pfilter)) + vInv.push_back(inv); + if (vInv.size() == MAX_INV_SZ) + break; } if (vInv.size() > 0) pfrom->PushMessage("inv", vInv); -- cgit v1.2.3