13 files changed, 304 insertions, 62 deletions
diff --git a/src/cryptonote_core/blockchain.cpp b/src/cryptonote_core/blockchain.cpp
index 36a233ee7..cc6b48b6b 100644
--- a/src/cryptonote_core/blockchain.cpp
+++ b/src/cryptonote_core/blockchain.cpp
@@ -1597,6 +1597,25 @@ bool Blockchain::get_random_outs_for_amounts(const COMMAND_RPC_GET_RANDOM_OUTPUT
   return true;
 }
 //------------------------------------------------------------------
+bool Blockchain::get_outs(const COMMAND_RPC_GET_OUTPUTS::request& req, COMMAND_RPC_GET_OUTPUTS::response& res) const
+{
+  LOG_PRINT_L3("Blockchain::" << __func__);
+  CRITICAL_REGION_LOCAL(m_blockchain_lock);
+
+  res.outs.clear();
+  res.outs.reserve(req.outputs.size());
+  for (const auto &i: req.outputs)
+  {
+    // get tx_hash, tx_out_index from DB
+    crypto::public_key key = m_db->get_output_key(i.amount, i.index).pubkey;
+    tx_out_index toi = m_db->get_output_tx_and_index(i.amount, i.index);
+    bool unlocked = is_tx_spendtime_unlocked(m_db->get_tx_unlock_time(toi.first));
+
+    res.outs.push_back({key, unlocked});
+  }
+  return true;
+}
+//------------------------------------------------------------------
 // This function takes a list of block hashes from another node
 // on the network to find where the split point is between us and them.
 // This is used to see what to send another node that needs to sync.
diff --git a/src/cryptonote_core/blockchain.h b/src/cryptonote_core/blockchain.h
index 903e0096b..f5950291c 100644
--- a/src/cryptonote_core/blockchain.h
+++ b/src/cryptonote_core/blockchain.h
@@ -440,6 +440,21 @@ namespace cryptonote
     bool get_random_outs_for_amounts(const COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::request& req, COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::response& res) const;
 
     /**
+     * @brief gets specific outputs to mix with
+     *
+     * This function takes an RPC request for outputs to mix with
+     * and creates an RPC response with the resultant output indices.
+     *
+     * Outputs to mix with are specified in the request.
+     *
+     * @param req the outputs to return
+     * @param res return-by-reference the resultant output indices and keys
+     *
+     * @return true
+     */
+    bool get_outs(const COMMAND_RPC_GET_OUTPUTS::request& req, COMMAND_RPC_GET_OUTPUTS::response& res) const;
+
+    /**
      * @brief gets the global indices for outputs from a given transaction
      *
      * This function gets the global indices for all outputs belonging
diff --git a/src/cryptonote_core/cryptonote_core.cpp b/src/cryptonote_core/cryptonote_core.cpp
index 20b9f0b0b..25b750b1d 100644
--- a/src/cryptonote_core/cryptonote_core.cpp
+++ b/src/cryptonote_core/cryptonote_core.cpp
@@ -709,6 +709,11 @@ namespace cryptonote
     return m_blockchain_storage.get_random_outs_for_amounts(req, res);
   }
   //-----------------------------------------------------------------------------------------------
+  bool core::get_outs(const COMMAND_RPC_GET_OUTPUTS::request& req, COMMAND_RPC_GET_OUTPUTS::response& res) const
+  {
+    return m_blockchain_storage.get_outs(req, res);
+  }
+  //-----------------------------------------------------------------------------------------------
   bool core::get_tx_outputs_gindexs(const crypto::hash& tx_id, std::vector<uint64_t>& indexs) const
   {
     return m_blockchain_storage.get_tx_outputs_gindexs(tx_id, indexs);
diff --git a/src/cryptonote_core/cryptonote_core.h b/src/cryptonote_core/cryptonote_core.h
index 30384209f..63969bc23 100644
--- a/src/cryptonote_core/cryptonote_core.h
+++ b/src/cryptonote_core/cryptonote_core.h
@@ -476,6 +476,13 @@ namespace cryptonote
       */
      bool get_random_outs_for_amounts(const COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::request& req, COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::response& res) const;
 
+     /**
+      * @copydoc Blockchain::get_outs
+      *
+      * @note see Blockchain::get_outs
+      */
+     bool get_outs(const COMMAND_RPC_GET_OUTPUTS::request& req, COMMAND_RPC_GET_OUTPUTS::response& res) const;
+
 
      /**
       * @copydoc miner::pause
diff --git a/src/rpc/core_rpc_server.cpp b/src/rpc/core_rpc_server.cpp
index 90f7a8434..9cd1893cf 100644
--- a/src/rpc/core_rpc_server.cpp
+++ b/src/rpc/core_rpc_server.cpp
@@ -42,6 +42,7 @@ using namespace epee;
 #include "core_rpc_server_error_codes.h"
 
 #define MAX_RESTRICTED_FAKE_OUTS_COUNT 40
+#define MAX_RESTRICTED_GLOBAL_FAKE_OUTS_COUNT 500
 
 namespace cryptonote
 {
@@ -226,6 +227,29 @@ namespace cryptonote
     return true;
   }
   //------------------------------------------------------------------------------------------------------------------------------
+  bool core_rpc_server::on_get_outs(const COMMAND_RPC_GET_OUTPUTS::request& req, COMMAND_RPC_GET_OUTPUTS::response& res)
+  {
+    CHECK_CORE_BUSY();
+    res.status = "Failed";
+
+    if (m_restricted)
+    {
+      if (req.outputs.size() > MAX_RESTRICTED_GLOBAL_FAKE_OUTS_COUNT)
+      {
+        res.status = "Too many outs requested";
+        return true;
+      }
+    }
+
+    if(!m_core.get_outs(req, res))
+    {
+      return true;
+    }
+
+    res.status = CORE_RPC_STATUS_OK;
+    return true;
+  }
+  //------------------------------------------------------------------------------------------------------------------------------
   bool core_rpc_server::on_get_indexes(const COMMAND_RPC_GET_TX_GLOBAL_OUTPUTS_INDEXES::request& req, COMMAND_RPC_GET_TX_GLOBAL_OUTPUTS_INDEXES::response& res)
   {
     CHECK_CORE_BUSY();
diff --git a/src/rpc/core_rpc_server.h b/src/rpc/core_rpc_server.h
index 3d50c77be..6ebf41abc 100644
--- a/src/rpc/core_rpc_server.h
+++ b/src/rpc/core_rpc_server.h
@@ -78,6 +78,7 @@ namespace cryptonote
       MAP_URI_AUTO_BIN2("/gethashes.bin", on_get_hashes, COMMAND_RPC_GET_HASHES_FAST)
       MAP_URI_AUTO_BIN2("/get_o_indexes.bin", on_get_indexes, COMMAND_RPC_GET_TX_GLOBAL_OUTPUTS_INDEXES)      
       MAP_URI_AUTO_BIN2("/getrandom_outs.bin", on_get_random_outs, COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS)      
+      MAP_URI_AUTO_BIN2("/get_outs.bin", on_get_outs, COMMAND_RPC_GET_OUTPUTS)      
       MAP_URI_AUTO_JON2("/gettransactions", on_get_transactions, COMMAND_RPC_GET_TRANSACTIONS)
       MAP_URI_AUTO_JON2("/is_key_image_spent", on_is_key_image_spent, COMMAND_RPC_IS_KEY_IMAGE_SPENT)
       MAP_URI_AUTO_JON2("/sendrawtransaction", on_send_raw_tx, COMMAND_RPC_SEND_RAW_TX)
@@ -126,6 +127,7 @@ namespace cryptonote
     bool on_stop_mining(const COMMAND_RPC_STOP_MINING::request& req, COMMAND_RPC_STOP_MINING::response& res);
     bool on_mining_status(const COMMAND_RPC_MINING_STATUS::request& req, COMMAND_RPC_MINING_STATUS::response& res);
     bool on_get_random_outs(const COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::request& req, COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::response& res);        
+    bool on_get_outs(const COMMAND_RPC_GET_OUTPUTS::request& req, COMMAND_RPC_GET_OUTPUTS::response& res);        
     bool on_get_info(const COMMAND_RPC_GET_INFO::request& req, COMMAND_RPC_GET_INFO::response& res);        
     bool on_save_bc(const COMMAND_RPC_SAVE_BC::request& req, COMMAND_RPC_SAVE_BC::response& res);
     bool on_get_peer_list(const COMMAND_RPC_GET_PEER_LIST::request& req, COMMAND_RPC_GET_PEER_LIST::response& res);
diff --git a/src/rpc/core_rpc_server_commands_defs.h b/src/rpc/core_rpc_server_commands_defs.h
index 89370a035..22c3590e1 100644
--- a/src/rpc/core_rpc_server_commands_defs.h
+++ b/src/rpc/core_rpc_server_commands_defs.h
@@ -41,7 +41,7 @@ namespace cryptonote
 #define CORE_RPC_STATUS_BUSY   "BUSY"
 #define CORE_RPC_STATUS_NOT_MINING "NOT MINING"
 
-#define CORE_RPC_VERSION 1
+#define CORE_RPC_VERSION 2
 
   struct COMMAND_RPC_GET_HEIGHT
   {
@@ -271,6 +271,51 @@ namespace cryptonote
     };
   };
   //-----------------------------------------------
+  struct COMMAND_RPC_GET_OUTPUTS
+  {
+    struct out
+    {
+      uint64_t amount;
+      uint64_t index;
+
+      BEGIN_KV_SERIALIZE_MAP()
+        KV_SERIALIZE(amount)
+        KV_SERIALIZE(index)
+      END_KV_SERIALIZE_MAP()
+    };
+
+    struct request
+    {
+      std::vector<out> outputs;
+
+      BEGIN_KV_SERIALIZE_MAP()
+        KV_SERIALIZE(outputs)
+      END_KV_SERIALIZE_MAP()
+    };
+
+    struct outkey
+    {
+      crypto::public_key key;
+      bool unlocked;
+
+      BEGIN_KV_SERIALIZE_MAP()
+        KV_SERIALIZE_VAL_POD_AS_BLOB(key)
+        KV_SERIALIZE(unlocked)
+      END_KV_SERIALIZE_MAP()
+    };
+
+    struct response
+    {
+      std::vector<outkey> outs;
+      std::string status;
+
+      BEGIN_KV_SERIALIZE_MAP()
+        KV_SERIALIZE(outs)
+        KV_SERIALIZE(status)
+      END_KV_SERIALIZE_MAP()
+    };
+  };
+  //-----------------------------------------------
   struct COMMAND_RPC_SEND_RAW_TX
   {
     struct request
diff --git a/src/simplewallet/simplewallet.cpp b/src/simplewallet/simplewallet.cpp
index a3a4685b5..1622f755c 100644
--- a/src/simplewallet/simplewallet.cpp
+++ b/src/simplewallet/simplewallet.cpp
@@ -2466,9 +2466,9 @@ bool simple_wallet::transfer_main(bool new_algorithm, const std::vector<std::str
   {
     auto writer = fail_msg_writer();
     writer << tr("not enough outputs for specified mixin_count") << " = " << e.mixin_count() << ":";
-    for (const cryptonote::COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::outs_for_amount& outs_for_amount : e.scanty_outs())
+    for (std::pair<uint64_t, uint64_t> outs_for_amount : e.scanty_outs())
     {
-      writer << "\n" << tr("output amount") << " = " << print_money(outs_for_amount.amount) << ", " << tr("found outputs to mix") << " = " << outs_for_amount.outs.size();
+      writer << "\n" << tr("output amount") << " = " << print_money(outs_for_amount.first) << ", " << tr("found outputs to mix") << " = " << outs_for_amount.second;
     }
   }
   catch (const tools::error::tx_not_constructed&)
@@ -2629,9 +2629,9 @@ bool simple_wallet::sweep_unmixable(const std::vector<std::string> &args_)
   {
     auto writer = fail_msg_writer();
     writer << tr("not enough outputs for specified mixin_count") << " = " << e.mixin_count() << ":";
-    for (const cryptonote::COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::outs_for_amount& outs_for_amount : e.scanty_outs())
+    for (std::pair<uint64_t, uint64_t> outs_for_amount : e.scanty_outs())
     {
-      writer << "\n" << tr("output amount") << " = " << print_money(outs_for_amount.amount) << ", " << tr("found outputs to mix") << " = " << outs_for_amount.outs.size();
+      writer << "\n" << tr("output amount") << " = " << print_money(outs_for_amount.first) << ", " << tr("found outputs to mix") << " = " << outs_for_amount.second;
     }
   }
   catch (const tools::error::tx_not_constructed&)
@@ -2861,9 +2861,9 @@ bool simple_wallet::sweep_all(const std::vector<std::string> &args_)
   {
     auto writer = fail_msg_writer();
     writer << tr("not enough outputs for specified mixin_count") << " = " << e.mixin_count() << ":";
-    for (const cryptonote::COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::outs_for_amount& outs_for_amount : e.scanty_outs())
+    for (std::pair<uint64_t, uint64_t> outs_for_amount : e.scanty_outs())
     {
-      writer << "\n" << tr("output amount") << " = " << print_money(outs_for_amount.amount) << ", " << tr("found outputs to mix") << " = " << outs_for_amount.outs.size();
+      writer << "\n" << tr("output amount") << " = " << print_money(outs_for_amount.first) << ", " << tr("found outputs to mix") << " = " << outs_for_amount.second;
     }
   }
   catch (const tools::error::tx_not_constructed&)
diff --git a/src/wallet/api/wallet.cpp b/src/wallet/api/wallet.cpp
index 67d2ebecb..4b97e2f1d 100644
--- a/src/wallet/api/wallet.cpp
+++ b/src/wallet/api/wallet.cpp
@@ -527,8 +527,8 @@ PendingTransaction *WalletImpl::createTransaction(const string &dst_addr, const
         } catch (const tools::error::not_enough_outs_to_mix& e) {
             std::ostringstream writer;
             writer << tr("not enough outputs for specified mixin_count") << " = " << e.mixin_count() << ":";
-            for (const cryptonote::COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::outs_for_amount& outs_for_amount : e.scanty_outs()) {
-                writer << "\n" << tr("output amount") << " = " << print_money(outs_for_amount.amount) << ", " << tr("found outputs to mix") << " = " << outs_for_amount.outs.size();
+            for (const std::pair<uint64_t, uint64_t> outs_for_amount : e.scanty_outs()) {
+                writer << "\n" << tr("output amount") << " = " << print_money(outs_for_amount.first) << ", " << tr("found outputs to mix") << " = " << outs_for_amount.second;
             }
             m_errorString = writer.str();
             m_status = Status_Error;
diff --git a/src/wallet/wallet2.cpp b/src/wallet/wallet2.cpp
index 502d64c9c..b1544321c 100644
--- a/src/wallet/wallet2.cpp
+++ b/src/wallet/wallet2.cpp
@@ -2364,45 +2364,174 @@ void wallet2::transfer_selected(const std::vector<cryptonote::tx_destination_ent
   LOG_PRINT_L2("wanted " << print_money(needed_money) << ", found " << print_money(found_money) << ", fee " << print_money(fee));
   THROW_WALLET_EXCEPTION_IF(found_money < needed_money, error::not_enough_money, found_money, needed_money - fee, fee);
 
-  typedef COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::out_entry out_entry;
-  typedef cryptonote::tx_source_entry::output_entry tx_output_entry;
-
-  COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::response daemon_resp = AUTO_VAL_INIT(daemon_resp);
-  if(fake_outputs_count)
+  typedef std::pair<uint64_t, crypto::public_key> entry;
+  std::vector<std::vector<entry>> outs;
+  if (fake_outputs_count)
   {
-    COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::request req = AUTO_VAL_INIT(req);
-    req.outs_count = fake_outputs_count + 1;// add one to make possible (if need) to skip real output key
-    BOOST_FOREACH(transfer_container::iterator it, selected_transfers)
+    // get histogram for the amounts we need
+    epee::json_rpc::request<cryptonote::COMMAND_RPC_GET_OUTPUT_HISTOGRAM::request> req_t = AUTO_VAL_INIT(req_t);
+    epee::json_rpc::response<cryptonote::COMMAND_RPC_GET_OUTPUT_HISTOGRAM::response, std::string> resp_t = AUTO_VAL_INIT(resp_t);
+    m_daemon_rpc_mutex.lock();
+    req_t.jsonrpc = "2.0";
+    req_t.id = epee::serialization::storage_entry(0);
+    req_t.method = "get_output_histogram";
+    for(auto it: selected_transfers)
+      req_t.params.amounts.push_back(it->amount());
+    req_t.params.unlocked = true;
+    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");
+    THROW_WALLET_EXCEPTION_IF(resp_t.result.status == CORE_RPC_STATUS_BUSY, error::daemon_busy, "get_output_histogram");
+    THROW_WALLET_EXCEPTION_IF(resp_t.result.status != CORE_RPC_STATUS_OK, error::get_histogram_error, resp_t.result.status);
+
+    // we ask for more, to have spares if some outputs are still locked
+    size_t requested_outputs_count = (size_t)((fake_outputs_count + 1) * 1.5 + 1);
+
+    // generate output indices to request
+    COMMAND_RPC_GET_OUTPUTS::request req = AUTO_VAL_INIT(req);
+    COMMAND_RPC_GET_OUTPUTS::response daemon_resp = AUTO_VAL_INIT(daemon_resp);
+    for(transfer_container::iterator it: selected_transfers)
     {
-      THROW_WALLET_EXCEPTION_IF(it->m_tx.vout.size() <= it->m_internal_output_index, error::wallet_internal_error,
-        "m_internal_output_index = " + std::to_string(it->m_internal_output_index) +
-        " is greater or equal to outputs count = " + std::to_string(it->m_tx.vout.size()));
-      req.amounts.push_back(it->amount());
+      std::unordered_set<uint64_t> seen_indices;
+      size_t start = req.outputs.size();
+
+      // if there are just enough outputs to mix with, use all of them.
+      // Eventually this should become impossible.
+      uint64_t num_outs = 0;
+      for (auto he: resp_t.result.histogram)
+      {
+        if (he.amount == it->amount())
+        {
+          num_outs = he.instances;
+          break;
+        }
+      }
+      if (num_outs <= requested_outputs_count)
+      {
+        for (uint64_t i = 0; i < num_outs; i++)
+          req.outputs.push_back({it->amount(), i});
+        // duplicate to make up shortfall: this will be caught after the RPC call,
+        // so we can also output the amounts for which we can't reach the required
+        // mixin after checking the actual unlockedness
+        for (uint64_t i = num_outs; i < requested_outputs_count; ++i)
+          req.outputs.push_back({it->amount(), num_outs - 1});
+      }
+      else
+      {
+        // start with real one
+        uint64_t num_found = 1;
+        seen_indices.emplace(it->m_global_output_index);
+        req.outputs.push_back({it->amount(), it->m_global_output_index});
+
+        // while we still need more mixins
+        while (num_found < requested_outputs_count)
+        {
+          // if we've gone through every possible output, we've gotten all we can
+          if (seen_indices.size() == num_outs)
+            break;
+
+          // get a random output index from the DB.  If we've already seen it,
+          // 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
+          if (i == num_outs)
+            --i;
+
+          if (seen_indices.count(i))
+            continue;
+          seen_indices.emplace(i);
+
+          req.outputs.push_back({it->amount(), i});
+          ++num_found;
+        }
+      }
+
+      // sort the subsection, to ensure the daemon doesn't know wich output is ours
+      std::sort(req.outputs.begin() + start, req.outputs.end(),
+          [](const COMMAND_RPC_GET_OUTPUTS::out &a, const COMMAND_RPC_GET_OUTPUTS::out &b) { return a.index < b.index; });
     }
 
+    // get the keys for those
     m_daemon_rpc_mutex.lock();
-    bool r = epee::net_utils::invoke_http_bin_remote_command2(m_daemon_address + "/getrandom_outs.bin", req, daemon_resp, m_http_client, 200000);
+    r = epee::net_utils::invoke_http_bin_remote_command2(m_daemon_address + "/get_outs.bin", req, daemon_resp, m_http_client, 200000);
     m_daemon_rpc_mutex.unlock();
-    THROW_WALLET_EXCEPTION_IF(!r, error::no_connection_to_daemon, "getrandom_outs.bin");
-    THROW_WALLET_EXCEPTION_IF(daemon_resp.status == CORE_RPC_STATUS_BUSY, error::daemon_busy, "getrandom_outs.bin");
+    THROW_WALLET_EXCEPTION_IF(!r, error::no_connection_to_daemon, "get_outs.bin");
+    THROW_WALLET_EXCEPTION_IF(daemon_resp.status == CORE_RPC_STATUS_BUSY, error::daemon_busy, "get_outs.bin");
     THROW_WALLET_EXCEPTION_IF(daemon_resp.status != CORE_RPC_STATUS_OK, error::get_random_outs_error, daemon_resp.status);
-    THROW_WALLET_EXCEPTION_IF(daemon_resp.outs.size() != selected_transfers.size(), error::wallet_internal_error,
-      "daemon returned wrong response for getrandom_outs.bin, wrong amounts count = " +
-      std::to_string(daemon_resp.outs.size()) + ", expected " +  std::to_string(selected_transfers.size()));
-
-    std::vector<COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::outs_for_amount> scanty_outs;
-    BOOST_FOREACH(COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::outs_for_amount& amount_outs, daemon_resp.outs)
-    {
-      if (amount_outs.outs.size() < fake_outputs_count)
+    THROW_WALLET_EXCEPTION_IF(daemon_resp.outs.size() != req.outputs.size(), error::wallet_internal_error,
+      "daemon returned wrong response for get_outs.bin, wrong amounts count = " +
+      std::to_string(daemon_resp.outs.size()) + ", expected " +  std::to_string(req.outputs.size()));
+
+    std::unordered_map<uint64_t, uint64_t> scanty_outs;
+    size_t base = 0;
+    outs.reserve(selected_transfers.size());
+    for(transfer_container::iterator it: selected_transfers)
+    {
+      outs.push_back(std::vector<entry>());
+      outs.back().reserve(fake_outputs_count + 1);
+
+      // pick real out first (it will be sorted when done)
+      outs.back().push_back({it->m_global_output_index, boost::get<txout_to_key>(it->m_tx.vout[it->m_internal_output_index].target).key});
+
+      // then pick others in random order till we reach the required number
+      // since we use an equiprobable pick here, we don't upset the triangular distribution
+      std::vector<size_t> order;
+      order.resize(requested_outputs_count);
+      for (size_t n = 0; n < order.size(); ++n)
+        order[n] = n;
+      std::shuffle(order.begin(), order.end(), std::default_random_engine(crypto::rand<unsigned>()));
+
+      for (size_t o = 0; o < requested_outputs_count && outs.back().size() < fake_outputs_count + 1; ++o)
       {
-        scanty_outs.push_back(amount_outs);
+        size_t i = base + order[o];
+        if (req.outputs[i].index == it->m_global_output_index) // don't re-add real one
+          continue;
+        if (!daemon_resp.outs[i].unlocked) // don't add locked outs
+          continue;
+        if (o > 0 && daemon_resp.outs[i].key == daemon_resp.outs[i - 1].key) // don't add duplicates
+          continue;
+        outs.back().push_back({req.outputs[i].index, daemon_resp.outs[i].key});
+      }
+      if (outs.back().size() < fake_outputs_count + 1)
+      {
+        scanty_outs[it->amount()] = outs.back().size();
       }
+      else
+      {
+        // sort the subsection, so any spares are reset in order
+        std::sort(outs.back().begin(), outs.back().end(), [](const entry &a, const entry &b) { return a.first < b.first; });
+
+        // sanity check
+        for (size_t n = 1; n < outs.back().size(); ++n)
+        {
+          THROW_WALLET_EXCEPTION_IF(outs.back()[n].first == outs.back()[n-1].first, error::wallet_internal_error,
+              "Duplicate indices though we did not ask for any");
+          THROW_WALLET_EXCEPTION_IF(outs.back()[n].second == outs.back()[n-1].second, error::wallet_internal_error,
+              "Duplicate keys after we have weeded them out");
+        }
+      }
+      base += requested_outputs_count;
     }
     THROW_WALLET_EXCEPTION_IF(!scanty_outs.empty(), error::not_enough_outs_to_mix, scanty_outs, fake_outputs_count);
   }
+  else
+  {
+    for (transfer_container::iterator it: selected_transfers)
+    {
+      std::vector<entry> v;
+      v.push_back({it->m_global_output_index, boost::get<txout_to_key>(it->m_tx.vout[it->m_internal_output_index].target).key});
+      outs.push_back(v);
+    }
+  }
 
   //prepare inputs
-  size_t i = 0;
+  typedef cryptonote::tx_source_entry::output_entry tx_output_entry;
+  size_t i = 0, out_index = 0;
   std::vector<cryptonote::tx_source_entry> sources;
   BOOST_FOREACH(transfer_container::iterator it, selected_transfers)
   {
@@ -2410,38 +2539,34 @@ void wallet2::transfer_selected(const std::vector<cryptonote::tx_destination_ent
     cryptonote::tx_source_entry& src = sources.back();
     transfer_details& td = *it;
     src.amount = td.amount();
-    //paste mixin transaction
-    if(daemon_resp.outs.size())
+    //paste keys (fake and real)
+
+    for (size_t n = 0; n < fake_outputs_count + 1; ++n)
     {
-      daemon_resp.outs[i].outs.sort([](const out_entry& a, const out_entry& b){return a.global_amount_index < b.global_amount_index;});
-      BOOST_FOREACH(out_entry& daemon_oe, daemon_resp.outs[i].outs)
-      {
-        if(td.m_global_output_index == daemon_oe.global_amount_index)
-          continue;
-        tx_output_entry oe;
-        oe.first = daemon_oe.global_amount_index;
-        oe.second = daemon_oe.out_key;
-        src.outputs.push_back(oe);
-        if(src.outputs.size() >= fake_outputs_count)
-          break;
-      }
+      tx_output_entry oe;
+      oe.first = outs[out_index][n].first;
+      oe.second = outs[out_index][n].second;
+      src.outputs.push_back(oe);
+      ++i;
     }
 
     //paste real transaction to the random index
-    auto it_to_insert = std::find_if(src.outputs.begin(), src.outputs.end(), [&](const tx_output_entry& a)
+    auto it_to_replace = std::find_if(src.outputs.begin(), src.outputs.end(), [&](const tx_output_entry& a)
     {
-      return a.first >= td.m_global_output_index;
+      return a.first == td.m_global_output_index;
     });
-    //size_t real_index = src.outputs.size() ? (rand() % src.outputs.size() ):0;
+    THROW_WALLET_EXCEPTION_IF(it_to_replace == src.outputs.end(), error::wallet_internal_error,
+        "real output not found");
+
     tx_output_entry real_oe;
     real_oe.first = td.m_global_output_index;
     real_oe.second = boost::get<txout_to_key>(td.m_tx.vout[td.m_internal_output_index].target).key;
-    auto interted_it = src.outputs.insert(it_to_insert, real_oe);
+    *it_to_replace = real_oe;
     src.real_out_tx_key = get_tx_pub_key_from_extra(td.m_tx);
-    src.real_output = interted_it - src.outputs.begin();
+    src.real_output = it_to_replace - src.outputs.begin();
     src.real_output_in_tx_index = td.m_internal_output_index;
     detail::print_source_entry(src);
-    ++i;
+    ++out_index;
   }
 
   cryptonote::tx_destination_entry change_dts = AUTO_VAL_INIT(change_dts);
diff --git a/src/wallet/wallet2.h b/src/wallet/wallet2.h
index 9ff6c4e21..d0c514a6d 100644
--- a/src/wallet/wallet2.h
+++ b/src/wallet/wallet2.h
@@ -668,12 +668,12 @@ namespace tools
         "daemon returned wrong response for getrandom_outs.bin, wrong amounts count = " +
         std::to_string(daemon_resp.outs.size()) + ", expected " +  std::to_string(selected_transfers.size()));
 
-      std::vector<COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::outs_for_amount> scanty_outs;
+      std::unordered_map<uint64_t, uint64_t> scanty_outs;
       BOOST_FOREACH(COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::outs_for_amount& amount_outs, daemon_resp.outs)
       {
         if (amount_outs.outs.size() < fake_outputs_count)
         {
-          scanty_outs.push_back(amount_outs);
+          scanty_outs[amount_outs.amount] = amount_outs.outs.size();
         }
       }
       THROW_WALLET_EXCEPTION_IF(!scanty_outs.empty(), error::not_enough_outs_to_mix, scanty_outs, fake_outputs_count);
diff --git a/src/wallet/wallet_errors.h b/src/wallet/wallet_errors.h
index ea0b6a1f5..8ea061152 100644
--- a/src/wallet/wallet_errors.h
+++ b/src/wallet/wallet_errors.h
@@ -377,7 +377,7 @@ namespace tools
     //----------------------------------------------------------------------------------------------------
     struct not_enough_outs_to_mix : public transfer_error
     {
-      typedef std::vector<cryptonote::COMMAND_RPC_GET_RANDOM_OUTPUTS_FOR_AMOUNTS::outs_for_amount> scanty_outs_t;
+      typedef std::unordered_map<uint64_t, uint64_t> scanty_outs_t;
 
       explicit not_enough_outs_to_mix(std::string&& loc, const scanty_outs_t& scanty_outs, size_t mixin_count)
         : transfer_error(std::move(loc), "not enough outputs to mix")
@@ -393,9 +393,9 @@ namespace tools
       {
         std::ostringstream ss;
         ss << transfer_error::to_string() << ", mixin_count = " << m_mixin_count << ", scanty_outs:";
-        for (const auto& outs_for_amount : m_scanty_outs)
+        for (const auto& out: m_scanty_outs)
         {
-          ss << '\n' << cryptonote::print_money(outs_for_amount.amount) << " - " << outs_for_amount.outs.size();
+          ss << '\n' << cryptonote::print_money(out.first) << " - " << out.second;
         }
         return ss.str();
       }
diff --git a/tests/unit_tests/hardfork.cpp b/tests/unit_tests/hardfork.cpp
index 35973011a..eab6b9cf8 100644
--- a/tests/unit_tests/hardfork.cpp
+++ b/tests/unit_tests/hardfork.cpp
@@ -86,8 +86,8 @@ public:
   virtual output_data_t get_output_key(const uint64_t& amount, const uint64_t& index) { return output_data_t(); }
   virtual output_data_t get_output_key(const uint64_t& global_index) const { return output_data_t(); }
   virtual tx_out_index get_output_tx_and_index_from_global(const uint64_t& index) const { return tx_out_index(); }
-  virtual tx_out_index get_output_tx_and_index(const uint64_t& amount, const uint64_t& index) { return tx_out_index(); }
-  virtual void get_output_tx_and_index(const uint64_t& amount, const std::vector<uint64_t> &offsets, std::vector<tx_out_index> &indices) {}
+  virtual tx_out_index get_output_tx_and_index(const uint64_t& amount, const uint64_t& index) const { return tx_out_index(); }
+  virtual void get_output_tx_and_index(const uint64_t& amount, const std::vector<uint64_t> &offsets, std::vector<tx_out_index> &indices) const {}
   virtual void get_output_key(const uint64_t &amount, const std::vector<uint64_t> &offsets, std::vector<output_data_t> &outputs) {}
   virtual bool can_thread_bulk_indices() const { return false; }
   virtual std::vector<uint64_t> get_tx_output_indices(const crypto::hash& h) const { return std::vector<uint64_t>(); }
@@ -106,7 +106,7 @@ public:
   virtual bool for_all_transactions(std::function<bool(const crypto::hash&, const cryptonote::transaction&)>) const { return true; }
   virtual bool for_all_outputs(std::function<bool(uint64_t amount, const crypto::hash &tx_hash, size_t tx_idx)> f) const { return true; }
   virtual bool is_read_only() const { return false; }
-  virtual std::map<uint64_t, uint64_t> get_output_histogram(const std::vector<uint64_t> &amounts) const { return std::map<uint64_t, uint64_t>(); }
+  virtual std::map<uint64_t, uint64_t> get_output_histogram(const std::vector<uint64_t> &amounts, bool unlocked) const { return std::map<uint64_t, uint64_t>(); }
 
   virtual void add_block( const block& blk
                         , const size_t& block_size