cryptonote: sort tx_extra fields

This removes some small amount of fingerprinting entropy.
There is no consensus rule to require this since this field
is technically free form, and a transaction is free to have
custom data in it.

5 files changed, 177 insertions, 1 deletions

diff --git a/src/cryptonote_basic/cryptonote_basic.h b/src/cryptonote_basic/cryptonote_basic.h
index d4558ef7b..b0eabb0aa 100644
--- a/src/cryptonote_basic/cryptonote_basic.h
+++ b/src/cryptonote_basic/cryptonote_basic.h
@@ -47,7 +47,6 @@
 #include "crypto/crypto.h"
 #include "crypto/hash.h"
 #include "misc_language.h"
-#include "tx_extra.h"
 #include "ringct/rctTypes.h"
 #include "device/device.hpp"
 
diff --git a/src/cryptonote_basic/cryptonote_format_utils.cpp b/src/cryptonote_basic/cryptonote_format_utils.cpp
index 428be1c9c..0231a032e 100644
--- a/src/cryptonote_basic/cryptonote_format_utils.cpp
+++ b/src/cryptonote_basic/cryptonote_format_utils.cpp
@@ -376,6 +376,91 @@ namespace cryptonote
     return true;
   }
   //---------------------------------------------------------------
+  template<typename T>
+  static bool pick(binary_archive<true> &ar, std::vector<tx_extra_field> &fields, uint8_t tag)
+  {
+    std::vector<tx_extra_field>::iterator it;
+    while ((it = std::find_if(fields.begin(), fields.end(), [](const tx_extra_field &f) { return f.type() == typeid(T); })) != fields.end())
+    {
+      bool r = ::do_serialize(ar, tag);
+      CHECK_AND_NO_ASSERT_MES_L1(r, false, "failed to serialize tx extra field");
+      r = ::do_serialize(ar, boost::get<T>(*it));
+      CHECK_AND_NO_ASSERT_MES_L1(r, false, "failed to serialize tx extra field");
+      fields.erase(it);
+    }
+    return true;
+  }
+  //---------------------------------------------------------------
+  bool sort_tx_extra(const std::vector<uint8_t>& tx_extra, std::vector<uint8_t> &sorted_tx_extra, bool allow_partial)
+  {
+    std::vector<tx_extra_field> tx_extra_fields;
+
+    if(tx_extra.empty())
+    {
+      sorted_tx_extra.clear();
+      return true;
+    }
+
+    std::string extra_str(reinterpret_cast<const char*>(tx_extra.data()), tx_extra.size());
+    std::istringstream iss(extra_str);
+    binary_archive<false> ar(iss);
+
+    bool eof = false;
+    size_t processed = 0;
+    while (!eof)
+    {
+      tx_extra_field field;
+      bool r = ::do_serialize(ar, field);
+      if (!r)
+      {
+        MWARNING("failed to deserialize extra field. extra = " << string_tools::buff_to_hex_nodelimer(std::string(reinterpret_cast<const char*>(tx_extra.data()), tx_extra.size())));
+        if (!allow_partial)
+          return false;
+        break;
+      }
+      tx_extra_fields.push_back(field);
+      processed = iss.tellg();
+
+      std::ios_base::iostate state = iss.rdstate();
+      eof = (EOF == iss.peek());
+      iss.clear(state);
+    }
+    if (!::serialization::check_stream_state(ar))
+    {
+      MWARNING("failed to deserialize extra field. extra = " << string_tools::buff_to_hex_nodelimer(std::string(reinterpret_cast<const char*>(tx_extra.data()), tx_extra.size())));
+      if (!allow_partial)
+        return false;
+    }
+    MTRACE("Sorted " << processed << "/" << tx_extra.size());
+
+    std::ostringstream oss;
+    binary_archive<true> nar(oss);
+
+    // sort by:
+    if (!pick<tx_extra_pub_key>(nar, tx_extra_fields, TX_EXTRA_TAG_PUBKEY)) return false;
+    if (!pick<tx_extra_additional_pub_keys>(nar, tx_extra_fields, TX_EXTRA_TAG_ADDITIONAL_PUBKEYS)) return false;
+    if (!pick<tx_extra_nonce>(nar, tx_extra_fields, TX_EXTRA_NONCE)) return false;
+    if (!pick<tx_extra_merge_mining_tag>(nar, tx_extra_fields, TX_EXTRA_MERGE_MINING_TAG)) return false;
+    if (!pick<tx_extra_mysterious_minergate>(nar, tx_extra_fields, TX_EXTRA_MYSTERIOUS_MINERGATE_TAG)) return false;
+    if (!pick<tx_extra_padding>(nar, tx_extra_fields, TX_EXTRA_TAG_PADDING)) return false;
+
+    // if not empty, someone added a new type and did not add a case above
+    if (!tx_extra_fields.empty())
+    {
+      MERROR("tx_extra_fields not empty after sorting, someone forgot to add a case above");
+      return false;
+    }
+
+    std::string oss_str = oss.str();
+    if (allow_partial && processed < tx_extra.size())
+    {
+      MDEBUG("Appending unparsed data");
+      oss_str += std::string((const char*)tx_extra.data() + processed, tx_extra.size() - processed);
+    }
+    sorted_tx_extra = std::vector<uint8_t>(oss_str.begin(), oss_str.end());
+    return true;
+  }
+  //---------------------------------------------------------------
   crypto::public_key get_tx_pub_key_from_extra(const std::vector<uint8_t>& tx_extra, size_t pk_index)
   {
     std::vector<tx_extra_field> tx_extra_fields;
diff --git a/src/cryptonote_basic/cryptonote_format_utils.h b/src/cryptonote_basic/cryptonote_format_utils.h
index 8a5296d5b..b40db4668 100644
--- a/src/cryptonote_basic/cryptonote_format_utils.h
+++ b/src/cryptonote_basic/cryptonote_format_utils.h
@@ -31,6 +31,7 @@
 #pragma once
 #include "blobdatatype.h"
 #include "cryptonote_basic_impl.h"
+#include "tx_extra.h"
 #include "account.h"
 #include "subaddress_index.h"
 #include "include_base_utils.h"
@@ -64,6 +65,7 @@ namespace cryptonote
   }
 
   bool parse_tx_extra(const std::vector<uint8_t>& tx_extra, std::vector<tx_extra_field>& tx_extra_fields);
+  bool sort_tx_extra(const std::vector<uint8_t>& tx_extra, std::vector<uint8_t> &sorted_tx_extra, bool allow_partial = false);
   crypto::public_key get_tx_pub_key_from_extra(const std::vector<uint8_t>& tx_extra, size_t pk_index = 0);
   crypto::public_key get_tx_pub_key_from_extra(const transaction_prefix& tx, size_t pk_index = 0);
   crypto::public_key get_tx_pub_key_from_extra(const transaction& tx, size_t pk_index = 0);
diff --git a/src/cryptonote_core/cryptonote_tx_utils.cpp b/src/cryptonote_core/cryptonote_tx_utils.cpp
index 071ce591e..1e5a7fb23 100644
--- a/src/cryptonote_core/cryptonote_tx_utils.cpp
+++ b/src/cryptonote_core/cryptonote_tx_utils.cpp
@@ -38,6 +38,7 @@ using namespace epee;
 #include "cryptonote_tx_utils.h"
 #include "cryptonote_config.h"
 #include "cryptonote_basic/miner.h"
+#include "cryptonote_basic/tx_extra.h"
 #include "crypto/crypto.h"
 #include "crypto/hash.h"
 #include "ringct/rctSigs.h"
@@ -84,6 +85,8 @@ namespace cryptonote
     if(!extra_nonce.empty())
       if(!add_extra_nonce_to_tx_extra(tx.extra, extra_nonce))
         return false;
+    if (!sort_tx_extra(tx.extra, tx.extra))
+      return false;
 
     txin_gen in;
     in.height = height;
@@ -434,6 +437,9 @@ namespace cryptonote
       add_additional_tx_pub_keys_to_extra(tx.extra, additional_tx_public_keys);
     }
 
+    if (!sort_tx_extra(tx.extra, tx.extra))
+      return false;
+
     //check money
     if(summary_outs_money > summary_inputs_money )
     {
diff --git a/tests/unit_tests/test_tx_utils.cpp b/tests/unit_tests/test_tx_utils.cpp
index 8a9f983e6..55c76c3b6 100644
--- a/tests/unit_tests/test_tx_utils.cpp
+++ b/tests/unit_tests/test_tx_utils.cpp
@@ -33,6 +33,8 @@
 #include <vector>
 
 #include "common/util.h"
+#include "cryptonote_basic/cryptonote_basic.h"
+#include "cryptonote_basic/tx_extra.h"
 #include "cryptonote_core/cryptonote_tx_utils.h"
 
 namespace
@@ -203,3 +205,85 @@ TEST(validate_parse_amount_case, validate_parse_amount)
   r = cryptonote::parse_amount(res, "1 00.00 00");
   ASSERT_FALSE(r);
 }
+
+TEST(sort_tx_extra, empty)
+{
+  std::vector<uint8_t> extra, sorted;
+  ASSERT_TRUE(cryptonote::sort_tx_extra(extra, sorted));
+  ASSERT_EQ(extra, sorted);
+}
+
+TEST(sort_tx_extra, pubkey)
+{
+  std::vector<uint8_t> sorted;
+  const uint8_t extra_arr[] = {1, 30, 208, 98, 162, 133, 64, 85, 83, 112, 91, 188, 89, 211, 24, 131, 39, 154, 22, 228,
+    80, 63, 198, 141, 173, 111, 244, 183, 4, 149, 186, 140, 230};
+  std::vector<uint8_t> extra(&extra_arr[0], &extra_arr[0] + sizeof(extra_arr));
+  ASSERT_TRUE(cryptonote::sort_tx_extra(extra, sorted));
+  ASSERT_EQ(extra, sorted);
+}
+
+TEST(sort_tx_extra, two_pubkeys)
+{
+  std::vector<uint8_t> sorted;
+  const uint8_t extra_arr[] = {1, 30, 208, 98, 162, 133, 64, 85, 83, 112, 91, 188, 89, 211, 24, 131, 39, 154, 22, 228,
+    80, 63, 198, 141, 173, 111, 244, 183, 4, 149, 186, 140, 230,
+    1, 30, 208, 98, 162, 133, 64, 85, 83, 112, 91, 188, 89, 211, 24, 131, 39, 154, 22, 228,
+    80, 63, 198, 141, 173, 111, 244, 183, 4, 149, 186, 140, 230};
+  std::vector<uint8_t> extra(&extra_arr[0], &extra_arr[0] + sizeof(extra_arr));
+  ASSERT_TRUE(cryptonote::sort_tx_extra(extra, sorted));
+  ASSERT_EQ(extra, sorted);
+}
+
+TEST(sort_tx_extra, keep_order)
+{
+  std::vector<uint8_t> sorted;
+  const uint8_t extra_arr[] = {1, 30, 208, 98, 162, 133, 64, 85, 83, 112, 91, 188, 89, 211, 24, 131, 39, 154, 22, 228,
+    80, 63, 198, 141, 173, 111, 244, 183, 4, 149, 186, 140, 230,
+    2, 9, 1, 0, 0, 0, 0, 0, 0, 0, 0};
+  std::vector<uint8_t> extra(&extra_arr[0], &extra_arr[0] + sizeof(extra_arr));
+  ASSERT_TRUE(cryptonote::sort_tx_extra(extra, sorted));
+  ASSERT_EQ(extra, sorted);
+}
+
+TEST(sort_tx_extra, switch_order)
+{
+  std::vector<uint8_t> sorted;
+  const uint8_t extra_arr[] = {2, 9, 1, 0, 0, 0, 0, 0, 0, 0, 0,
+    1, 30, 208, 98, 162, 133, 64, 85, 83, 112, 91, 188, 89, 211, 24, 131, 39, 154, 22, 228,
+    80, 63, 198, 141, 173, 111, 244, 183, 4, 149, 186, 140, 230};
+  const uint8_t expected_arr[] = {1, 30, 208, 98, 162, 133, 64, 85, 83, 112, 91, 188, 89, 211, 24, 131, 39, 154, 22, 228,
+    80, 63, 198, 141, 173, 111, 244, 183, 4, 149, 186, 140, 230,
+    2, 9, 1, 0, 0, 0, 0, 0, 0, 0, 0};
+  std::vector<uint8_t> extra(&extra_arr[0], &extra_arr[0] + sizeof(extra_arr));
+  ASSERT_TRUE(cryptonote::sort_tx_extra(extra, sorted));
+  std::vector<uint8_t> expected(&expected_arr[0], &expected_arr[0] + sizeof(expected_arr));
+  ASSERT_EQ(expected, sorted);
+}
+
+TEST(sort_tx_extra, invalid)
+{
+  std::vector<uint8_t> sorted;
+  const uint8_t extra_arr[] = {1};
+  std::vector<uint8_t> extra(&extra_arr[0], &extra_arr[0] + sizeof(extra_arr));
+  ASSERT_FALSE(cryptonote::sort_tx_extra(extra, sorted));
+}
+
+TEST(sort_tx_extra, invalid_suffix_strict)
+{
+  std::vector<uint8_t> sorted;
+  const uint8_t extra_arr[] = {2, 9, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1};
+  std::vector<uint8_t> extra(&extra_arr[0], &extra_arr[0] + sizeof(extra_arr));
+  ASSERT_FALSE(cryptonote::sort_tx_extra(extra, sorted));
+}
+
+TEST(sort_tx_extra, invalid_suffix_partial)
+{
+  std::vector<uint8_t> sorted;
+  const uint8_t extra_arr[] = {2, 9, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1};
+  const uint8_t expected_arr[] = {2, 9, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1};
+  std::vector<uint8_t> extra(&extra_arr[0], &extra_arr[0] + sizeof(extra_arr));
+  ASSERT_TRUE(cryptonote::sort_tx_extra(extra, sorted, true));
+  std::vector<uint8_t> expected(&expected_arr[0], &expected_arr[0] + sizeof(expected_arr));
+  ASSERT_EQ(sorted, expected);
+}