wallet: select part of the fake outs from recent outputs

25% of the outputs are selected from the last 5 days (if possible),
in order to avoid the common case of sending recently received
outputs again. 25% and 5 days are subject to review later, since
it's just a wallet level change.

9 files changed, 92 insertions, 32 deletions

diff --git a/src/blockchain_db/blockchain_db.h b/src/blockchain_db/blockchain_db.h
index 5b6a793d8..91c388de6 100644
--- a/src/blockchain_db/blockchain_db.h
+++ b/src/blockchain_db/blockchain_db.h
@@ -1309,10 +1309,11 @@ public:
    *
    * @param amounts optional set of amounts to lookup
    * @param unlocked whether to restrict count to unlocked outputs
+   * @param recent_cutoff timestamp to determine whether an output is recent
    *
    * @return a set of amount/instances
    */
-  virtual std::map<uint64_t, uint64_t> get_output_histogram(const std::vector<uint64_t> &amounts, bool unlocked) const = 0;
+  virtual std::map<uint64_t, std::tuple<uint64_t, uint64_t, uint64_t>> get_output_histogram(const std::vector<uint64_t> &amounts, bool unlocked, uint64_t recent_cutoff) const = 0;
 
   /**
    * @brief is BlockchainDB in read-only mode?
diff --git a/src/blockchain_db/lmdb/db_lmdb.cpp b/src/blockchain_db/lmdb/db_lmdb.cpp
index acb7d2cf6..b5459b56b 100644
--- a/src/blockchain_db/lmdb/db_lmdb.cpp
+++ b/src/blockchain_db/lmdb/db_lmdb.cpp
@@ -2657,7 +2657,7 @@ void BlockchainLMDB::get_output_tx_and_index(const uint64_t& amount, const std::
   LOG_PRINT_L3("db3: " << db3);
 }
 
-std::map<uint64_t, uint64_t> BlockchainLMDB::get_output_histogram(const std::vector<uint64_t> &amounts, bool unlocked) const
+std::map<uint64_t, std::tuple<uint64_t, uint64_t, uint64_t>> BlockchainLMDB::get_output_histogram(const std::vector<uint64_t> &amounts, bool unlocked, uint64_t recent_cutoff) const
 {
   LOG_PRINT_L3("BlockchainLMDB::" << __func__);
   check_open();
@@ -2665,7 +2665,7 @@ std::map<uint64_t, uint64_t> BlockchainLMDB::get_output_histogram(const std::vec
   TXN_PREFIX_RDONLY();
   RCURSOR(output_amounts);
 
-  std::map<uint64_t, uint64_t> histogram;
+  std::map<uint64_t, std::tuple<uint64_t, uint64_t, uint64_t>> histogram;
   MDB_val k;
   MDB_val v;
 
@@ -2683,7 +2683,7 @@ std::map<uint64_t, uint64_t> BlockchainLMDB::get_output_histogram(const std::vec
       mdb_size_t num_elems = 0;
       mdb_cursor_count(m_cur_output_amounts, &num_elems);
       uint64_t amount = *(const uint64_t*)k.mv_data;
-      histogram[amount] = num_elems;
+      histogram[amount] = std::make_tuple(num_elems, 0, 0);
     }
   }
   else
@@ -2694,13 +2694,13 @@ std::map<uint64_t, uint64_t> BlockchainLMDB::get_output_histogram(const std::vec
       int ret = mdb_cursor_get(m_cur_output_amounts, &k, &v, MDB_SET);
       if (ret == MDB_NOTFOUND)
       {
-        histogram[amount] = 0;
+        histogram[amount] = std::make_tuple(0, 0, 0);
       }
       else if (ret == MDB_SUCCESS)
       {
         mdb_size_t num_elems = 0;
         mdb_cursor_count(m_cur_output_amounts, &num_elems);
-        histogram[amount] = num_elems;
+        histogram[amount] = std::make_tuple(num_elems, 0, 0);
       }
       else
       {
@@ -2709,11 +2709,11 @@ std::map<uint64_t, uint64_t> BlockchainLMDB::get_output_histogram(const std::vec
     }
   }
 
-  if (unlocked) {
+  if (unlocked || recent_cutoff > 0) {
     const uint64_t blockchain_height = height();
-    for (auto i: histogram) {
-      uint64_t amount = i.first;
-      uint64_t num_elems = i.second;
+    for (std::map<uint64_t, std::tuple<uint64_t, uint64_t, uint64_t>>::iterator i = histogram.begin(); i != histogram.end(); ++i) {
+      uint64_t amount = i->first;
+      uint64_t num_elems = std::get<0>(i->second);
       while (num_elems > 0) {
         const tx_out_index toi = get_output_tx_and_index(amount, num_elems - 1);
         const uint64_t height = get_tx_block_height(toi.first);
@@ -2722,7 +2722,23 @@ std::map<uint64_t, uint64_t> BlockchainLMDB::get_output_histogram(const std::vec
         --num_elems;
       }
       // modifying second does not invalidate the iterator
-      i.second = num_elems;
+      std::get<1>(i->second) = num_elems;
+
+      if (recent_cutoff > 0)
+      {
+        uint64_t recent = 0;
+        while (num_elems > 0) {
+          const tx_out_index toi = get_output_tx_and_index(amount, num_elems - 1);
+          const uint64_t height = get_tx_block_height(toi.first);
+          const uint64_t ts = get_block_timestamp(height);
+          if (ts < recent_cutoff)
+            break;
+          --num_elems;
+          ++recent;
+        }
+        // modifying second does not invalidate the iterator
+        std::get<2>(i->second) = recent;
+      }
     }
   }
 
diff --git a/src/blockchain_db/lmdb/db_lmdb.h b/src/blockchain_db/lmdb/db_lmdb.h
index 9df4b86d1..6db5abca1 100644
--- a/src/blockchain_db/lmdb/db_lmdb.h
+++ b/src/blockchain_db/lmdb/db_lmdb.h
@@ -265,10 +265,11 @@ public:
    *
    * @param amounts optional set of amounts to lookup
    * @param unlocked whether to restrict count to unlocked outputs
+   * @param recent_cutoff timestamp to determine which outputs are recent
    *
    * @return a set of amount/instances
    */
-  std::map<uint64_t, uint64_t> get_output_histogram(const std::vector<uint64_t> &amounts, bool unlocked) const;
+  std::map<uint64_t, std::tuple<uint64_t, uint64_t, uint64_t>> get_output_histogram(const std::vector<uint64_t> &amounts, bool unlocked, uint64_t recent_cutoff) const;
 
 private:
   void do_resize(uint64_t size_increase=0);
diff --git a/src/cryptonote_core/blockchain.cpp b/src/cryptonote_core/blockchain.cpp
index 9d2bf9332..9ea023a4c 100644
--- a/src/cryptonote_core/blockchain.cpp
+++ b/src/cryptonote_core/blockchain.cpp
@@ -3757,9 +3757,9 @@ bool Blockchain::get_hard_fork_voting_info(uint8_t version, uint32_t &window, ui
   return m_hardfork->get_voting_info(version, window, votes, threshold, earliest_height, voting);
 }
 
-std::map<uint64_t, uint64_t> Blockchain:: get_output_histogram(const std::vector<uint64_t> &amounts, bool unlocked) const
+std::map<uint64_t, std::tuple<uint64_t, uint64_t, uint64_t>> Blockchain:: get_output_histogram(const std::vector<uint64_t> &amounts, bool unlocked, uint64_t recent_cutoff) const
 {
-  return m_db->get_output_histogram(amounts, unlocked);
+  return m_db->get_output_histogram(amounts, unlocked, recent_cutoff);
 }
 
 #if defined(PER_BLOCK_CHECKPOINT)
diff --git a/src/cryptonote_core/blockchain.h b/src/cryptonote_core/blockchain.h
index 94701608e..262c2952b 100644
--- a/src/cryptonote_core/blockchain.h
+++ b/src/cryptonote_core/blockchain.h
@@ -729,10 +729,11 @@ namespace cryptonote
      *
      * @param amounts optional set of amounts to lookup
      * @param unlocked whether to restrict instances to unlocked ones
+     * @param recent_cutoff timestamp to consider outputs as recent
      *
      * @return a set of amount/instances
      */
-    std::map<uint64_t, uint64_t> get_output_histogram(const std::vector<uint64_t> &amounts, bool unlocked) const;
+    std::map<uint64_t, std::tuple<uint64_t, uint64_t, uint64_t>> get_output_histogram(const std::vector<uint64_t> &amounts, bool unlocked, uint64_t recent_cutoff) const;
 
     /**
      * @brief perform a check on all key images in the blockchain
diff --git a/src/daemon/rpc_command_executor.cpp b/src/daemon/rpc_command_executor.cpp
index db0d0a6e4..bed10715b 100644
--- a/src/daemon/rpc_command_executor.cpp
+++ b/src/daemon/rpc_command_executor.cpp
@@ -1243,6 +1243,8 @@ bool t_rpc_command_executor::output_histogram(uint64_t min_count, uint64_t max_c
 
     req.min_count = min_count;
     req.max_count = max_count;
+    req.unlocked = false;
+    req.recent_cutoff = 0;
 
     if (m_is_rpc)
     {
@@ -1261,10 +1263,10 @@ bool t_rpc_command_executor::output_histogram(uint64_t min_count, uint64_t max_c
     }
 
     std::sort(res.histogram.begin(), res.histogram.end(),
-        [](const cryptonote::COMMAND_RPC_GET_OUTPUT_HISTOGRAM::entry &e1, const cryptonote::COMMAND_RPC_GET_OUTPUT_HISTOGRAM::entry &e2)->bool { return e1.instances < e2.instances; });
+        [](const cryptonote::COMMAND_RPC_GET_OUTPUT_HISTOGRAM::entry &e1, const cryptonote::COMMAND_RPC_GET_OUTPUT_HISTOGRAM::entry &e2)->bool { return e1.total_instances < e2.total_instances; });
     for (const auto &e: res.histogram)
     {
-        tools::msg_writer() << e.instances << "  " << cryptonote::print_money(e.amount);
+        tools::msg_writer() << e.total_instances << "  " << cryptonote::print_money(e.amount);
     }
 
     return true;
diff --git a/src/rpc/core_rpc_server.cpp b/src/rpc/core_rpc_server.cpp
index e8b2d5cb1..f5258268c 100644
--- a/src/rpc/core_rpc_server.cpp
+++ b/src/rpc/core_rpc_server.cpp
@@ -1236,10 +1236,10 @@ namespace cryptonote
       return false;
     }
 
-    std::map<uint64_t, uint64_t> histogram;
+    std::map<uint64_t, std::tuple<uint64_t, uint64_t, uint64_t>> histogram;
     try
     {
-      histogram = m_core.get_blockchain_storage().get_output_histogram(req.amounts, req.unlocked);
+      histogram = m_core.get_blockchain_storage().get_output_histogram(req.amounts, req.unlocked, req.recent_cutoff);
     }
     catch (const std::exception &e)
     {
@@ -1251,8 +1251,8 @@ namespace cryptonote
     res.histogram.reserve(histogram.size());
     for (const auto &i: histogram)
     {
-      if (i.second >= req.min_count && (i.second <= req.max_count || req.max_count == 0))
-        res.histogram.push_back(COMMAND_RPC_GET_OUTPUT_HISTOGRAM::entry(i.first, i.second));
+      if (std::get<0>(i.second) >= req.min_count && (std::get<0>(i.second) <= req.max_count || req.max_count == 0))
+        res.histogram.push_back(COMMAND_RPC_GET_OUTPUT_HISTOGRAM::entry(i.first, std::get<0>(i.second), std::get<1>(i.second), std::get<2>(i.second)));
     }
 
     res.status = CORE_RPC_STATUS_OK;
diff --git a/src/rpc/core_rpc_server_commands_defs.h b/src/rpc/core_rpc_server_commands_defs.h
index 61c302e45..135cf1fe7 100644
--- a/src/rpc/core_rpc_server_commands_defs.h
+++ b/src/rpc/core_rpc_server_commands_defs.h
@@ -1172,26 +1172,33 @@ namespace cryptonote
       uint64_t min_count;
       uint64_t max_count;
       bool unlocked;
+      uint64_t recent_cutoff;
 
       BEGIN_KV_SERIALIZE_MAP()
         KV_SERIALIZE(amounts);
         KV_SERIALIZE(min_count);
         KV_SERIALIZE(max_count);
         KV_SERIALIZE(unlocked);
+        KV_SERIALIZE(recent_cutoff);
       END_KV_SERIALIZE_MAP()
     };
 
     struct entry
     {
       uint64_t amount;
-      uint64_t instances;
+      uint64_t total_instances;
+      uint64_t unlocked_instances;
+      uint64_t recent_instances;
 
       BEGIN_KV_SERIALIZE_MAP()
         KV_SERIALIZE(amount);
-        KV_SERIALIZE(instances);
+        KV_SERIALIZE(total_instances);
+        KV_SERIALIZE(unlocked_instances);
+        KV_SERIALIZE(recent_instances);
       END_KV_SERIALIZE_MAP()
 
-      entry(uint64_t amount, uint64_t instances): amount(amount), instances(instances) {}
+      entry(uint64_t amount, uint64_t total_instances, uint64_t unlocked_instances, uint64_t recent_instances):
+          amount(amount), total_instances(total_instances), unlocked_instances(unlocked_instances), recent_instances(recent_instances) {}
       entry() {}
     };
 
diff --git a/src/wallet/wallet2.cpp b/src/wallet/wallet2.cpp
index 98dbc4fd6..6a60ebe28 100644
--- a/src/wallet/wallet2.cpp
+++ b/src/wallet/wallet2.cpp
@@ -77,6 +77,9 @@ using namespace cryptonote;
 #define UNSIGNED_TX_PREFIX "Monero unsigned tx set\001"
 #define SIGNED_TX_PREFIX "Monero signed tx set\001"
 
+#define RECENT_OUTPUT_RATIO (0.25) // 25% of outputs are from the recent zone
+#define RECENT_OUTPUT_ZONE (5 * 86400) // last 5 days are the recent zone
+
 #define KILL_IOSERVICE()  \
     do { \
       work.reset(); \
@@ -2855,6 +2858,7 @@ void wallet2::get_outs(std::vector<std::vector<entry>> &outs, const std::list<si
     auto end = std::unique(req_t.params.amounts.begin(), req_t.params.amounts.end());
     req_t.params.amounts.resize(std::distance(req_t.params.amounts.begin(), end));
     req_t.params.unlocked = true;
+    req_t.params.recent_cutoff = time(NULL) - RECENT_OUTPUT_ZONE;
     bool r = net_utils::invoke_http_json_remote_command2(m_daemon_address + "/json_rpc", req_t, resp_t, m_http_client);
     m_daemon_rpc_mutex.unlock();
     THROW_WALLET_EXCEPTION_IF(!r, error::no_connection_to_daemon, "transfer_selected");
@@ -2880,18 +2884,33 @@ void wallet2::get_outs(std::vector<std::vector<entry>> &outs, const std::list<si
 
       // if there are just enough outputs to mix with, use all of them.
       // Eventually this should become impossible.
-      uint64_t num_outs = 0;
+      uint64_t num_outs = 0, num_recent_outs = 0;
       for (auto he: resp_t.result.histogram)
       {
         if (he.amount == amount)
         {
-          num_outs = he.instances;
+          LOG_PRINT_L2("Found " << print_money(amount) << ": " << he.total_instances << " total, "
+              << he.unlocked_instances << " unlocked, " << he.recent_instances << " recent");
+          num_outs = he.unlocked_instances;
+          num_recent_outs = he.recent_instances;
           break;
         }
       }
       LOG_PRINT_L1("" << num_outs << " outputs of size " << print_money(amount));
       THROW_WALLET_EXCEPTION_IF(num_outs == 0, error::wallet_internal_error,
           "histogram reports no outputs for " + boost::lexical_cast<std::string>(amount) + ", not even ours");
+      THROW_WALLET_EXCEPTION_IF(num_recent_outs > num_outs, error::wallet_internal_error,
+          "histogram reports more recent outs than outs for " + boost::lexical_cast<std::string>(amount));
+
+      // X% of those outs are to be taken from recent outputs
+      size_t recent_outputs_count = requested_outputs_count * RECENT_OUTPUT_RATIO;
+      if (recent_outputs_count == 0)
+        recent_outputs_count = 1; // ensure we have at least one, if possible
+      if (recent_outputs_count > num_recent_outs)
+        recent_outputs_count = num_recent_outs;
+      if (td.m_global_output_index >= num_outs - num_recent_outs)
+        --recent_outputs_count; // if the real out is recent, pick one less recent fake out
+      LOG_PRINT_L1("Using " << recent_outputs_count << " recent outputs");
 
       if (num_outs <= requested_outputs_count)
       {
@@ -2921,11 +2940,24 @@ void wallet2::get_outs(std::vector<std::vector<entry>> &outs, const std::list<si
           // return to the top of the loop and try again, otherwise add it to the
           // list of output indices we've seen.
 
-          // triangular distribution over [a,b) with a=0, mode c=b=up_index_limit
-          uint64_t r = crypto::rand<uint64_t>() % ((uint64_t)1 << 53);
-          double frac = std::sqrt((double)r / ((uint64_t)1 << 53));
-          uint64_t i = (uint64_t)(frac*num_outs);
-          // just in case rounding up to 1 occurs after sqrt
+          uint64_t i;
+          if (num_found - 1 < recent_outputs_count) // -1 to account for the real one we seeded with
+          {
+            // equiprobable distribution over the recent outs
+            uint64_t r = crypto::rand<uint64_t>() % ((uint64_t)1 << 53);
+            double frac = std::sqrt((double)r / ((uint64_t)1 << 53));
+            i = (uint64_t)(frac*num_recent_outs) + num_outs - num_recent_outs;
+            LOG_PRINT_L2("picking " << i << " as recent");
+          }
+          else
+          {
+            // triangular distribution over [a,b) with a=0, mode c=b=up_index_limit
+            uint64_t r = crypto::rand<uint64_t>() % ((uint64_t)1 << 53);
+            double frac = std::sqrt((double)r / ((uint64_t)1 << 53));
+            i = (uint64_t)(frac*num_outs);
+            LOG_PRINT_L2("picking " << i << " as triangular");
+          }
+          // just in case rounding up to 1 occurs after calc
           if (i == num_outs)
             --i;
 
@@ -3975,7 +4007,7 @@ uint64_t wallet2::get_num_rct_outputs()
   THROW_WALLET_EXCEPTION_IF(resp_t.result.histogram.size() != 1, error::get_histogram_error, "Expected exactly one response");
   THROW_WALLET_EXCEPTION_IF(resp_t.result.histogram[0].amount != 0, error::get_histogram_error, "Expected 0 amount");
 
-  return resp_t.result.histogram[0].instances;
+  return resp_t.result.histogram[0].total_instances;
 }
 //----------------------------------------------------------------------------------------------------
 std::vector<size_t> wallet2::select_available_unmixable_outputs(bool trusted_daemon)