Merge pull request #2440

6137a0b9 blockchain: reject unsorted ins and outs from v7 (moneromooo-monero)
16afab90 core: sort ins and outs key key image and public key, respectively (moneromooo-monero)
0c36b9f9 common: add apply_permutation file and function (moneromooo-monero)

3 files changed, 71 insertions, 6 deletions

diff --git a/src/cryptonote_core/blockchain.cpp b/src/cryptonote_core/blockchain.cpp
index 274c8cd07..7ee88e430 100644
--- a/src/cryptonote_core/blockchain.cpp
+++ b/src/cryptonote_core/blockchain.cpp
@@ -2384,6 +2384,26 @@ bool Blockchain::check_tx_outputs(const transaction& tx, tx_verification_context
     }
   }
 
+  // from v7, sorted outs
+  if (m_hardfork->get_current_version() >= 7) {
+    const crypto::public_key *last_key = NULL;
+    for (size_t n = 0; n < tx.vout.size(); ++n)
+    {
+      const tx_out &o = tx.vout[n];
+      if (o.target.type() == typeid(txout_to_key))
+      {
+        const txout_to_key& out_to_key = boost::get<txout_to_key>(o.target);
+        if (last_key && memcmp(&out_to_key.key, last_key, sizeof(*last_key)) >= 0)
+        {
+          MERROR_VER("transaction has unsorted outputs");
+          tvc.m_invalid_output = true;
+          return false;
+        }
+        last_key = &out_to_key.key;
+      }
+    }
+  }
+
   return true;
 }
 //------------------------------------------------------------------
@@ -2552,6 +2572,25 @@ bool Blockchain::check_tx_inputs(transaction& tx, tx_verification_context &tvc,
     }
   }
 
+  // from v7, sorted ins
+  if (hf_version >= 7) {
+    const crypto::key_image *last_key_image = NULL;
+    for (size_t n = 0; n < tx.vin.size(); ++n)
+    {
+      const txin_v &txin = tx.vin[n];
+      if (txin.type() == typeid(txin_to_key))
+      {
+        const txin_to_key& in_to_key = boost::get<txin_to_key>(txin);
+        if (last_key_image && memcmp(&in_to_key.k_image, last_key_image, sizeof(*last_key_image)) >= 0)
+        {
+          MERROR_VER("transaction has unsorted inputs");
+          tvc.m_verifivation_failed = true;
+          return false;
+        }
+        last_key_image = &in_to_key.k_image;
+      }
+    }
+  }
   auto it = m_check_txin_table.find(tx_prefix_hash);
   if(it == m_check_txin_table.end())
   {
diff --git a/src/cryptonote_core/cryptonote_tx_utils.cpp b/src/cryptonote_core/cryptonote_tx_utils.cpp
index 94f069827..9b442029a 100644
--- a/src/cryptonote_core/cryptonote_tx_utils.cpp
+++ b/src/cryptonote_core/cryptonote_tx_utils.cpp
@@ -31,6 +31,7 @@
 #include "include_base_utils.h"
 using namespace epee;
 
+#include "common/apply_permutation.h"
 #include "cryptonote_tx_utils.h"
 #include "cryptonote_config.h"
 #include "cryptonote_basic/miner.h"
@@ -156,7 +157,7 @@ namespace cryptonote
     return destinations[0].addr.m_view_public_key;
   }
   //---------------------------------------------------------------
-  bool construct_tx_and_get_tx_key(const account_keys& sender_account_keys, const std::vector<tx_source_entry>& sources, const std::vector<tx_destination_entry>& destinations, std::vector<uint8_t> extra, transaction& tx, uint64_t unlock_time, crypto::secret_key &tx_key, bool rct)
+  bool construct_tx_and_get_tx_key(const account_keys& sender_account_keys, std::vector<tx_source_entry> sources, const std::vector<tx_destination_entry>& destinations, std::vector<uint8_t> extra, transaction& tx, uint64_t unlock_time, crypto::secret_key &tx_key, bool rct)
   {
     std::vector<rct::key> amount_keys;
     tx.set_null();
@@ -263,14 +264,25 @@ namespace cryptonote
       tx.vin.push_back(input_to_key);
     }
 
-    // "Shuffle" outs
-    std::vector<tx_destination_entry> shuffled_dsts(destinations);
-    std::random_shuffle(shuffled_dsts.begin(), shuffled_dsts.end(), [](unsigned int i) { return crypto::rand<unsigned int>() % i; });
+    // sort ins by their key image
+    std::vector<size_t> ins_order(sources.size());
+    for (size_t n = 0; n < sources.size(); ++n)
+      ins_order[n] = n;
+    std::sort(ins_order.begin(), ins_order.end(), [&](const size_t i0, const size_t i1) {
+      const txin_to_key &tk0 = boost::get<txin_to_key>(tx.vin[i0]);
+      const txin_to_key &tk1 = boost::get<txin_to_key>(tx.vin[i1]);
+      return memcmp(&tk0.k_image, &tk1.k_image, sizeof(tk0.k_image)) < 0;
+    });
+    tools::apply_permutation(ins_order, [&] (size_t i0, size_t i1) {
+      std::swap(tx.vin[i0], tx.vin[i1]);
+      std::swap(in_contexts[i0], in_contexts[i1]);
+      std::swap(sources[i0], sources[i1]);
+    });
 
     uint64_t summary_outs_money = 0;
     //fill outputs
     size_t output_index = 0;
-    for(const tx_destination_entry& dst_entr:  shuffled_dsts)
+    for(const tx_destination_entry& dst_entr: destinations)
     {
       CHECK_AND_ASSERT_MES(dst_entr.amount > 0 || tx.version > 1, false, "Destination with wrong amount: " << dst_entr.amount);
       crypto::key_derivation derivation;
@@ -297,6 +309,20 @@ namespace cryptonote
       summary_outs_money += dst_entr.amount;
     }
 
+    // sort outs by their public key
+    std::vector<size_t> outs_order(tx.vout.size());
+    for (size_t n = 0; n < tx.vout.size(); ++n)
+      outs_order[n] = n;
+    std::sort(outs_order.begin(), outs_order.end(), [&](size_t i0, size_t i1) {
+      const txout_to_key &tk0 = boost::get<txout_to_key>(tx.vout[i0].target);
+      const txout_to_key &tk1 = boost::get<txout_to_key>(tx.vout[i1].target);
+      return memcmp(&tk0.key, &tk1.key, sizeof(tk0.key)) < 0;
+    });
+    tools::apply_permutation(outs_order, [&] (size_t i0, size_t i1) {
+      std::swap(tx.vout[i0], tx.vout[i1]);
+      std::swap(amount_keys[i0], amount_keys[i1]);
+    });
+
     //check money
     if(summary_outs_money > summary_inputs_money )
     {
diff --git a/src/cryptonote_core/cryptonote_tx_utils.h b/src/cryptonote_core/cryptonote_tx_utils.h
index 7aa7c280d..69254fb5f 100644
--- a/src/cryptonote_core/cryptonote_tx_utils.h
+++ b/src/cryptonote_core/cryptonote_tx_utils.h
@@ -71,7 +71,7 @@ namespace cryptonote
   //---------------------------------------------------------------
   crypto::public_key get_destination_view_key_pub(const std::vector<tx_destination_entry> &destinations, const account_keys &sender_keys);
   bool construct_tx(const account_keys& sender_account_keys, const std::vector<tx_source_entry>& sources, const std::vector<tx_destination_entry>& destinations, std::vector<uint8_t> extra, transaction& tx, uint64_t unlock_time);
-  bool construct_tx_and_get_tx_key(const account_keys& sender_account_keys, const std::vector<tx_source_entry>& sources, const std::vector<tx_destination_entry>& destinations, std::vector<uint8_t> extra, transaction& tx, uint64_t unlock_time, crypto::secret_key &tx_key, bool rct = false);
+  bool construct_tx_and_get_tx_key(const account_keys& sender_account_keys, std::vector<tx_source_entry> sources, const std::vector<tx_destination_entry>& destinations, std::vector<uint8_t> extra, transaction& tx, uint64_t unlock_time, crypto::secret_key &tx_key, bool rct = false);
 
   bool generate_genesis_block(
       block& bl