Merge pull request #8781

c59e009 verRctNonSemanticsSimpleCached: fix fragility (Jeffrey Ryan)

5 files changed, 279 insertions, 73 deletions

diff --git a/src/cryptonote_core/CMakeLists.txt b/src/cryptonote_core/CMakeLists.txt
index 69411e379..beead6217 100644
--- a/src/cryptonote_core/CMakeLists.txt
+++ b/src/cryptonote_core/CMakeLists.txt
@@ -31,7 +31,9 @@ set(cryptonote_core_sources
   cryptonote_core.cpp
   tx_pool.cpp
   tx_sanity_check.cpp
-  cryptonote_tx_utils.cpp)
+  cryptonote_tx_utils.cpp
+  tx_verification_utils.cpp
+)
 
 set(cryptonote_core_headers)
 
diff --git a/src/cryptonote_core/blockchain.cpp b/src/cryptonote_core/blockchain.cpp
index 8edb33b5a..28d52a2d1 100644
--- a/src/cryptonote_core/blockchain.cpp
+++ b/src/cryptonote_core/blockchain.cpp
@@ -57,6 +57,7 @@
 #include "common/notify.h"
 #include "common/varint.h"
 #include "common/pruning.h"
+#include "common/data_cache.h"
 #include "time_helper.h"
 
 #undef MONERO_DEFAULT_LOG_CATEGORY
@@ -98,7 +99,8 @@ Blockchain::Blockchain(tx_memory_pool& tx_pool) :
   m_difficulty_for_next_block(1),
   m_btc_valid(false),
   m_batch_success(true),
-  m_prepare_height(0)
+  m_prepare_height(0),
+  m_rct_ver_cache()
 {
   LOG_PRINT_L3("Blockchain::" << __func__);
 }
@@ -3211,7 +3213,7 @@ bool Blockchain::have_tx_keyimges_as_spent(const transaction &tx) const
   }
   return false;
 }
-bool Blockchain::expand_transaction_2(transaction &tx, const crypto::hash &tx_prefix_hash, const std::vector<std::vector<rct::ctkey>> &pubkeys) const
+bool Blockchain::expand_transaction_2(transaction &tx, const crypto::hash &tx_prefix_hash, const std::vector<std::vector<rct::ctkey>> &pubkeys)
 {
   PERF_TIMER(expand_transaction_2);
   CHECK_AND_ASSERT_MES(tx.version == 2, false, "Transaction version is not 2");
@@ -3534,6 +3536,13 @@ bool Blockchain::check_tx_inputs(transaction& tx, tx_verification_context &tvc,
         false, "Transaction spends at least one output which is too young");
   }
 
+  // Warn that new RCT types are present, and thus the cache is not being used effectively
+  static constexpr const std::uint8_t RCT_CACHE_TYPE = rct::RCTTypeBulletproofPlus;
+  if (tx.rct_signatures.type > RCT_CACHE_TYPE)
+  {
+    MWARNING("RCT cache is not caching new verification results. Please update RCT_CACHE_TYPE!");
+  }
+
   if (tx.version == 1)
   {
     if (threads > 1)
@@ -3555,12 +3564,6 @@ bool Blockchain::check_tx_inputs(transaction& tx, tx_verification_context &tvc,
   }
   else
   {
-    if (!expand_transaction_2(tx, tx_prefix_hash, pubkeys))
-    {
-      MERROR_VER("Failed to expand rct signatures!");
-      return false;
-    }
-
     // from version 2, check ringct signatures
     // obviously, the original and simple rct APIs use a mixRing that's indexes
     // in opposite orders, because it'd be too simple otherwise...
@@ -3578,61 +3581,7 @@ bool Blockchain::check_tx_inputs(transaction& tx, tx_verification_context &tvc,
     case rct::RCTTypeCLSAG:
     case rct::RCTTypeBulletproofPlus:
     {
-      // check all this, either reconstructed (so should really pass), or not
-      {
-        if (pubkeys.size() != rv.mixRing.size())
-        {
-          MERROR_VER("Failed to check ringct signatures: mismatched pubkeys/mixRing size");
-          return false;
-        }
-        for (size_t i = 0; i < pubkeys.size(); ++i)
-        {
-          if (pubkeys[i].size() != rv.mixRing[i].size())
-          {
-            MERROR_VER("Failed to check ringct signatures: mismatched pubkeys/mixRing size");
-            return false;
-          }
-        }
-
-        for (size_t n = 0; n < pubkeys.size(); ++n)
-        {
-          for (size_t m = 0; m < pubkeys[n].size(); ++m)
-          {
-            if (pubkeys[n][m].dest != rct::rct2pk(rv.mixRing[n][m].dest))
-            {
-              MERROR_VER("Failed to check ringct signatures: mismatched pubkey at vin " << n << ", index " << m);
-              return false;
-            }
-            if (pubkeys[n][m].mask != rct::rct2pk(rv.mixRing[n][m].mask))
-            {
-              MERROR_VER("Failed to check ringct signatures: mismatched commitment at vin " << n << ", index " << m);
-              return false;
-            }
-          }
-        }
-      }
-
-      const size_t n_sigs = rct::is_rct_clsag(rv.type) ? rv.p.CLSAGs.size() : rv.p.MGs.size();
-      if (n_sigs != tx.vin.size())
-      {
-        MERROR_VER("Failed to check ringct signatures: mismatched MGs/vin sizes");
-        return false;
-      }
-      for (size_t n = 0; n < tx.vin.size(); ++n)
-      {
-        bool error;
-        if (rct::is_rct_clsag(rv.type))
-          error = memcmp(&boost::get<txin_to_key>(tx.vin[n]).k_image, &rv.p.CLSAGs[n].I, 32);
-        else
-          error = rv.p.MGs[n].II.empty() || memcmp(&boost::get<txin_to_key>(tx.vin[n]).k_image, &rv.p.MGs[n].II[0], 32);
-        if (error)
-        {
-          MERROR_VER("Failed to check ringct signatures: mismatched key image");
-          return false;
-        }
-      }
-
-      if (!rct::verRctNonSemanticsSimpleCached(rv))
+      if (!ver_rct_non_semantics_simple_cached(tx, pubkeys, m_rct_ver_cache, RCT_CACHE_TYPE))
       {
         MERROR_VER("Failed to check ringct signatures!");
         return false;
@@ -3641,6 +3590,12 @@ bool Blockchain::check_tx_inputs(transaction& tx, tx_verification_context &tvc,
     }
     case rct::RCTTypeFull:
     {
+      if (!expand_transaction_2(tx, tx_prefix_hash, pubkeys))
+      {
+        MERROR_VER("Failed to expand rct signatures!");
+        return false;
+      }
+
       // check all this, either reconstructed (so should really pass), or not
       {
         bool size_matches = true;
diff --git a/src/cryptonote_core/blockchain.h b/src/cryptonote_core/blockchain.h
index c61ce4466..42246fca2 100644
--- a/src/cryptonote_core/blockchain.h
+++ b/src/cryptonote_core/blockchain.h
@@ -57,6 +57,7 @@
 #include "rpc/core_rpc_server_commands_defs.h"
 #include "cryptonote_basic/difficulty.h"
 #include "cryptonote_tx_utils.h"
+#include "tx_verification_utils.h"
 #include "cryptonote_basic/verification_context.h"
 #include "crypto/hash.h"
 #include "checkpoints/checkpoints.h"
@@ -597,6 +598,15 @@ namespace cryptonote
     bool store_blockchain();
 
     /**
+     * @brief expands v2 transaction data from blockchain
+     *
+     * RingCT transactions do not transmit some of their data if it
+     * can be reconstituted by the receiver. This function expands
+     * that implicit data.
+     */
+    static bool expand_transaction_2(transaction &tx, const crypto::hash &tx_prefix_hash, const std::vector<std::vector<rct::ctkey>> &pubkeys);
+
+    /**
      * @brief validates a transaction's inputs
      *
      * validates a transaction's inputs as correctly used and not previously
@@ -1222,6 +1232,9 @@ namespace cryptonote
     uint64_t m_prepare_nblocks;
     std::vector<block> *m_prepare_blocks;
 
+    // cache for verifying transaction RCT non semantics
+    mutable rct_ver_cache_t m_rct_ver_cache;
+
     /**
      * @brief collects the keys for all outputs being "spent" as an input
      *
@@ -1575,15 +1588,6 @@ namespace cryptonote
     void load_compiled_in_block_hashes(const GetCheckpointsCallback& get_checkpoints);
 
     /**
-     * @brief expands v2 transaction data from blockchain
-     *
-     * RingCT transactions do not transmit some of their data if it
-     * can be reconstituted by the receiver. This function expands
-     * that implicit data.
-     */
-    bool expand_transaction_2(transaction &tx, const crypto::hash &tx_prefix_hash, const std::vector<std::vector<rct::ctkey>> &pubkeys) const;
-
-    /**
      * @brief invalidates any cached block template
      */
     void invalidate_block_template_cache();
diff --git a/src/cryptonote_core/tx_verification_utils.cpp b/src/cryptonote_core/tx_verification_utils.cpp
new file mode 100644
index 000000000..a93ef2f25
--- /dev/null
+++ b/src/cryptonote_core/tx_verification_utils.cpp
@@ -0,0 +1,167 @@
+// Copyright (c) 2023, The Monero Project
+//
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without modification, are
+// permitted provided that the following conditions are met:
+//
+// 1. Redistributions of source code must retain the above copyright notice, this list of
+//    conditions and the following disclaimer.
+//
+// 2. Redistributions in binary form must reproduce the above copyright notice, this list
+//    of conditions and the following disclaimer in the documentation and/or other
+//    materials provided with the distribution.
+//
+// 3. Neither the name of the copyright holder nor the names of its contributors may be
+//    used to endorse or promote products derived from this software without specific
+//    prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
+// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+// THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+// THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#include "cryptonote_core/blockchain.h"
+#include "cryptonote_core/tx_verification_utils.h"
+#include "ringct/rctSigs.h"
+
+#undef MONERO_DEFAULT_LOG_CATEGORY
+#define MONERO_DEFAULT_LOG_CATEGORY "blockchain"
+
+#define VER_ASSERT(cond, msgexpr) CHECK_AND_ASSERT_MES(cond, false, msgexpr)
+
+using namespace cryptonote;
+
+// Do RCT expansion, then do post-expansion sanity checks, then do full non-semantics verification.
+static bool expand_tx_and_ver_rct_non_sem(transaction& tx, const rct::ctkeyM& mix_ring)
+{
+    // Pruned transactions can not be expanded and verified because they are missing RCT data
+    VER_ASSERT(!tx.pruned, "Pruned transaction will not pass verRctNonSemanticsSimple");
+
+    // Calculate prefix hash
+    const crypto::hash tx_prefix_hash = get_transaction_prefix_hash(tx);
+
+    // Expand mixring, tx inputs, tx key images, prefix hash message, etc into the RCT sig
+    const bool exp_res = Blockchain::expand_transaction_2(tx, tx_prefix_hash, mix_ring);
+    VER_ASSERT(exp_res, "Failed to expand rct signatures!");
+
+    const rct::rctSig& rv = tx.rct_signatures;
+
+    // Check that expanded RCT mixring == input mixring
+    VER_ASSERT(rv.mixRing == mix_ring, "Failed to check ringct signatures: mismatched pubkeys/mixRing");
+
+    // Check CLSAG/MLSAG size against transaction input
+    const size_t n_sigs = rct::is_rct_clsag(rv.type) ? rv.p.CLSAGs.size() : rv.p.MGs.size();
+    VER_ASSERT(n_sigs == tx.vin.size(), "Failed to check ringct signatures: mismatched input sigs/vin sizes");
+
+    // For each input, check that the key images were copied into the expanded RCT sig correctly
+    for (size_t n = 0; n < n_sigs; ++n)
+    {
+        const crypto::key_image& nth_vin_image = boost::get<txin_to_key>(tx.vin[n]).k_image;
+
+        if (rct::is_rct_clsag(rv.type))
+        {
+            const bool ki_match = 0 == memcmp(&nth_vin_image, &rv.p.CLSAGs[n].I, 32);
+            VER_ASSERT(ki_match, "Failed to check ringct signatures: mismatched CLSAG key image");
+        }
+        else
+        {
+            const bool mg_nonempty = !rv.p.MGs[n].II.empty();
+            VER_ASSERT(mg_nonempty, "Failed to check ringct signatures: missing MLSAG key image");
+            const bool ki_match = 0 == memcmp(&nth_vin_image, &rv.p.MGs[n].II[0], 32);
+            VER_ASSERT(ki_match, "Failed to check ringct signatures: mismatched MLSAG key image");
+        }
+    }
+
+    // Mix ring data is now known to be correctly incorporated into the RCT sig inside tx.
+    return rct::verRctNonSemanticsSimple(rv);
+}
+
+// Create a unique identifier for pair of tx blob + mix ring
+static crypto::hash calc_tx_mixring_hash(const transaction& tx, const rct::ctkeyM& mix_ring)
+{
+    std::stringstream ss;
+
+    // Start with domain seperation
+    ss << config::HASH_KEY_TXHASH_AND_MIXRING;
+
+    // Then add TX hash
+    const crypto::hash tx_hash = get_transaction_hash(tx);
+    ss.write(tx_hash.data, sizeof(crypto::hash));
+
+    // Then serialize mix ring
+    binary_archive<true> ar(ss);
+    ::do_serialize(ar, const_cast<rct::ctkeyM&>(mix_ring));
+
+    // Calculate hash of TX hash and mix ring blob
+    crypto::hash tx_and_mixring_hash;
+    get_blob_hash(ss.str(), tx_and_mixring_hash);
+
+    return tx_and_mixring_hash;
+}
+
+////////////////////////////////////////////////////////////////////////////////////////////////////
+
+namespace cryptonote
+{
+
+bool ver_rct_non_semantics_simple_cached
+(
+    transaction& tx,
+    const rct::ctkeyM& mix_ring,
+    rct_ver_cache_t& cache,
+    const std::uint8_t rct_type_to_cache
+)
+{
+    // Hello future Monero dev! If you got this assert, read the following carefully:
+    //
+    // For this version of RCT, the way we guaranteed that verification caches do not generate false
+    // positives (and thus possibly enabling double spends) is we take a hash of two things. One,
+    // we use get_transaction_hash() which gives us a (cryptographically secure) unique
+    // representation of all "knobs" controlled by the possibly malicious constructor of the
+    // transaction. Two, we take a hash of all *previously validated* blockchain data referenced by
+    // this transaction which is required to validate the ring signature. In our case, this is the
+    // mixring. Future versions of the protocol may differ in this regard, but if this assumptions
+    // holds true in the future, enable the verification hash by modifying the `untested_tx`
+    // condition below.
+    const bool untested_tx = tx.version > 2 || tx.rct_signatures.type > rct::RCTTypeBulletproofPlus;
+    VER_ASSERT(!untested_tx, "Unknown TX type. Make sure RCT cache works correctly with this type and then enable it in the code here.");
+
+    // Don't cache older (or newer) rctSig types
+    // This cache only makes sense when it caches data from mempool first,
+    // so only "current fork version-enabled" RCT types need to be cached
+    if (tx.rct_signatures.type != rct_type_to_cache)
+    {
+        MDEBUG("RCT cache: tx " << get_transaction_hash(tx) << " skipped");
+        return expand_tx_and_ver_rct_non_sem(tx, mix_ring);
+    }
+
+    // Generate unique hash for tx+mix_ring pair
+    const crypto::hash tx_mixring_hash = calc_tx_mixring_hash(tx, mix_ring);
+
+    // Search cache for successful verification of same TX + mix ring combination
+    if (cache.has(tx_mixring_hash))
+    {
+        MDEBUG("RCT cache: tx " << get_transaction_hash(tx) << " hit");
+        return true;
+    }
+
+    // We had a cache miss, so now we must expand the mix ring and do full verification
+    MDEBUG("RCT cache: tx " << get_transaction_hash(tx) << " missed");
+    if (!expand_tx_and_ver_rct_non_sem(tx, mix_ring))
+    {
+        return false;
+    }
+
+    // At this point, the TX RCT verified successfully, so add it to the cache and return true
+    cache.add(tx_mixring_hash);
+
+    return true;
+}
+
+} // namespace cryptonote
diff --git a/src/cryptonote_core/tx_verification_utils.h b/src/cryptonote_core/tx_verification_utils.h
new file mode 100644
index 000000000..ccd401d2a
--- /dev/null
+++ b/src/cryptonote_core/tx_verification_utils.h
@@ -0,0 +1,78 @@
+// Copyright (c) 2023, The Monero Project
+//
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without modification, are
+// permitted provided that the following conditions are met:
+//
+// 1. Redistributions of source code must retain the above copyright notice, this list of
+//    conditions and the following disclaimer.
+//
+// 2. Redistributions in binary form must reproduce the above copyright notice, this list
+//    of conditions and the following disclaimer in the documentation and/or other
+//    materials provided with the distribution.
+//
+// 3. Neither the name of the copyright holder nor the names of its contributors may be
+//    used to endorse or promote products derived from this software without specific
+//    prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
+// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+// THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+// THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#pragma once
+
+#include "common/data_cache.h"
+#include "cryptonote_basic/cryptonote_basic.h"
+
+namespace cryptonote
+{
+
+// Modifying this value should not affect consensus. You can adjust it for performance needs
+static constexpr const size_t RCT_VER_CACHE_SIZE = 8192;
+
+using rct_ver_cache_t = ::tools::data_cache<::crypto::hash, RCT_VER_CACHE_SIZE>;
+
+/**
+ * @brief Cached version of rct::verRctNonSemanticsSimple
+ *
+ * This function will not affect how the transaction is serialized and it will never modify the
+ * transaction prefix.
+ *
+ * The reference to tx is mutable since the transaction's ring signatures may be expanded by
+ * Blockchain::expand_transaction_2. However, on cache hits, the transaction will not be
+ * expanded. This means that the caller does not need to call expand_transaction_2 on this
+ * transaction before passing it; the transaction will not successfully verify with "old" RCT data
+ * if the transaction has been otherwise modified since the last verification.
+ *
+ * But, if cryptonote::get_transaction_hash(tx) returns a "stale" hash, this function is not
+ * guaranteed to work. So make sure that the cryptonote::transaction passed has not had
+ * modifications to it since the last time its hash was fetched without properly invalidating the
+ * hashes.
+ *
+ * rct_type_to_cache can be any RCT version value as long as rct::verRctNonSemanticsSimple works for
+ * this RCT version, but for most applications, it doesn't make sense to not make this version
+ * the "current" RCT version (i.e. the version that transactions in the mempool are).
+ *
+ * @param tx transaction which contains RCT signature to verify
+ * @param mix_ring mixring referenced by this tx. THIS DATA MUST BE PREVIOUSLY VALIDATED
+ * @param cache saves tx+mixring hashes used to cache calls
+ * @param rct_type_to_cache Only RCT sigs with version (e.g. RCTTypeBulletproofPlus) will be cached
+ * @return true when verRctNonSemanticsSimple() w/ expanded tx.rct_signatures would return true
+ * @return false when verRctNonSemanticsSimple() w/ expanded tx.rct_signatures would return false
+ */
+bool ver_rct_non_semantics_simple_cached
+(
+    transaction& tx,
+    const rct::ctkeyM& mix_ring,
+    rct_ver_cache_t& cache,
+    std::uint8_t rct_type_to_cache
+);
+
+} // namespace cryptonote