Merge #18806: net: remove is{Empty,Full} flags from CBloomFilter, clarify CVE fix

1ad8ea2b73134bdd8d6b50704a019d47ad2191d8 net: remove is{Empty,Full} flags from CBloomFilter, clarify CVE fix (Sebastian Falbesoner)

Pull request description:

  The BIP37 bloom filter class `CBloomFilter` contains two flags `isEmpty`/`isFull` together with an update method with the purpose to, according to the comments, "avoid wasting cpu", i.e. the mechanism should serve as an optimization for the trivial cases of empty (all bits zero) or full (all bits one) filters.
  However, the real reason of adding those flags (introduced with commit https://github.com/bitcoin/bitcoin/commit/37c6389c5a0ca63ae3573440ecdfe95d28ad8f07 by gmaxwell) was a _covert fix_ of [CVE-2013-5700](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2013-5700), a vulnerability that allowed a divide-by-zero remote node crash.
  According to gmaxwell himself (https://github.com/bitcoin/bitcoin/pull/9060#issuecomment-257749165):
  > the IsEmpty/IsFull optimizations were largely a pretextual optimization intended to make unexploitable a remote crash vulnerability (integer division by zero) that existed in the original bloom filtering code without disclosing it. I'm doubtful that they are all that useful. :)

  For more information on how to trigger this crash, see PR https://github.com/bitcoin/bitcoin/pull/18515 which contains a detailled description and a regression test. It has also been discussed on a [recent PR club meeting on fuzzing](https://bitcoincore.reviews/18521.html).

  The covert fix code already led to issues and PR based on the wrong assumption that the flags are there for optimization reasons (see #16886 and #16922). This PR gets rid of the flags and the update method and just focuses on the CVE fix itself, i.e. it can be seen as a revert of the covert fix commit modulo the actual fix.

ACKs for top commit:
  meshcollider:
    utACK 1ad8ea2b73134bdd8d6b50704a019d47ad2191d8
  laanwj:
    Concept and code review ACK 1ad8ea2b73134bdd8d6b50704a019d47ad2191d8
  jkczyz:
    ACK 1ad8ea2b73134bdd8d6b50704a019d47ad2191d8
  MarcoFalke:
    ACK 1ad8ea2b73134bdd8d6b50704a019d47ad2191d8
  fjahr:
    Code review ACK 1ad8ea2b73134bdd8d6b50704a019d47ad2191d8

Tree-SHA512: 29f7ff9faece0285e11e16c024851f5bcb772dec64118ccc3f9067ec256267ec8e1b1e3105c7de2a72fd122c3b085e8fc840ab8f4e49813f1cc7a444df1867f7

4 files changed, 5 insertions, 34 deletions

diff --git a/src/bloom.cpp b/src/bloom.cpp
index 30af507243..54fcf487e4 100644
--- a/src/bloom.cpp
+++ b/src/bloom.cpp
@@ -31,8 +31,6 @@ CBloomFilter::CBloomFilter(const unsigned int nElements, const double nFPRate, c
      * Again, we ignore filter parameters which will create a bloom filter with more hash functions than the protocol limits
      * See https://en.wikipedia.org/wiki/Bloom_filter for an explanation of these formulas
      */
-    isFull(false),
-    isEmpty(true),
     nHashFuncs(std::min((unsigned int)(vData.size() * 8 / nElements * LN2), MAX_HASH_FUNCS)),
     nTweak(nTweakIn),
     nFlags(nFlagsIn)
@@ -47,7 +45,7 @@ inline unsigned int CBloomFilter::Hash(unsigned int nHashNum, const std::vector<
 
 void CBloomFilter::insert(const std::vector<unsigned char>& vKey)
 {
-    if (isFull)
+    if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700)
         return;
     for (unsigned int i = 0; i < nHashFuncs; i++)
     {
@@ -55,7 +53,6 @@ void CBloomFilter::insert(const std::vector<unsigned char>& vKey)
         // Sets bit nIndex of vData
         vData[nIndex >> 3] |= (1 << (7 & nIndex));
     }
-    isEmpty = false;
 }
 
 void CBloomFilter::insert(const COutPoint& outpoint)
@@ -74,10 +71,8 @@ void CBloomFilter::insert(const uint256& hash)
 
 bool CBloomFilter::contains(const std::vector<unsigned char>& vKey) const
 {
-    if (isFull)
+    if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700)
         return true;
-    if (isEmpty)
-        return false;
     for (unsigned int i = 0; i < nHashFuncs; i++)
     {
         unsigned int nIndex = Hash(i, vKey);
@@ -112,10 +107,8 @@ bool CBloomFilter::IsRelevantAndUpdate(const CTransaction& tx)
     bool fFound = false;
     // Match if the filter contains the hash of tx
     //  for finding tx when they appear in a block
-    if (isFull)
+    if (vData.empty()) // zero-size = "match-all" filter
         return true;
-    if (isEmpty)
-        return false;
     const uint256& hash = tx.GetHash();
     if (contains(hash))
         fFound = true;
@@ -177,19 +170,6 @@ bool CBloomFilter::IsRelevantAndUpdate(const CTransaction& tx)
     return false;
 }
 
-void CBloomFilter::UpdateEmptyFull()
-{
-    bool full = true;
-    bool empty = true;
-    for (unsigned int i = 0; i < vData.size(); i++)
-    {
-        full &= vData[i] == 0xff;
-        empty &= vData[i] == 0;
-    }
-    isFull = full;
-    isEmpty = empty;
-}
-
 CRollingBloomFilter::CRollingBloomFilter(const unsigned int nElements, const double fpRate)
 {
     double logFpRate = log(fpRate);
diff --git a/src/bloom.h b/src/bloom.h
index 8e3b7be54d..9173b80d66 100644
--- a/src/bloom.h
+++ b/src/bloom.h
@@ -45,8 +45,6 @@ class CBloomFilter
 {
 private:
     std::vector<unsigned char> vData;
-    bool isFull;
-    bool isEmpty;
     unsigned int nHashFuncs;
     unsigned int nTweak;
     unsigned char nFlags;
@@ -64,7 +62,7 @@ public:
      * nFlags should be one of the BLOOM_UPDATE_* enums (not _MASK)
      */
     CBloomFilter(const unsigned int nElements, const double nFPRate, const unsigned int nTweak, unsigned char nFlagsIn);
-    CBloomFilter() : isFull(true), isEmpty(false), nHashFuncs(0), nTweak(0), nFlags(0) {}
+    CBloomFilter() : nHashFuncs(0), nTweak(0), nFlags(0) {}
 
     ADD_SERIALIZE_METHODS;
 
@@ -90,9 +88,6 @@ public:
 
     //! Also adds any outputs which match the filter to the filter (to match their spending txes)
     bool IsRelevantAndUpdate(const CTransaction& tx);
-
-    //! Checks for empty and full filters to avoid wasting cpu
-    void UpdateEmptyFull();
 };
 
 /**
diff --git a/src/net_processing.cpp b/src/net_processing.cpp
index 50a8a8a882..a4d4953281 100644
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -3216,7 +3216,6 @@ bool ProcessMessage(CNode* pfrom, const std::string& msg_type, CDataStream& vRec
         {
             LOCK(pfrom->m_tx_relay->cs_filter);
             pfrom->m_tx_relay->pfilter.reset(new CBloomFilter(filter));
-            pfrom->m_tx_relay->pfilter->UpdateEmptyFull();
             pfrom->m_tx_relay->fRelayTxes = true;
         }
         return true;
diff --git a/src/test/fuzz/bloom_filter.cpp b/src/test/fuzz/bloom_filter.cpp
index 50036ce5bd..7039bf16c1 100644
--- a/src/test/fuzz/bloom_filter.cpp
+++ b/src/test/fuzz/bloom_filter.cpp
@@ -25,7 +25,7 @@ void test_one_input(const std::vector<uint8_t>& buffer)
         fuzzed_data_provider.ConsumeIntegral<unsigned int>(),
         static_cast<unsigned char>(fuzzed_data_provider.PickValueInArray({BLOOM_UPDATE_NONE, BLOOM_UPDATE_ALL, BLOOM_UPDATE_P2PUBKEY_ONLY, BLOOM_UPDATE_MASK}))};
     while (fuzzed_data_provider.remaining_bytes() > 0) {
-        switch (fuzzed_data_provider.ConsumeIntegralInRange(0, 4)) {
+        switch (fuzzed_data_provider.ConsumeIntegralInRange(0, 3)) {
         case 0: {
             const std::vector<unsigned char> b = ConsumeRandomLengthByteVector(fuzzed_data_provider);
             (void)bloom_filter.contains(b);
@@ -65,9 +65,6 @@ void test_one_input(const std::vector<uint8_t>& buffer)
             (void)bloom_filter.IsRelevantAndUpdate(tx);
             break;
         }
-        case 4:
-            bloom_filter.UpdateEmptyFull();
-            break;
         }
         (void)bloom_filter.IsWithinSizeConstraints();
     }