Merge pull request #1276

18f66f4 wallet: use the dynamic per kB fee (moneromooo-monero)
e6deb8a rpc: add a dynamic fee estimation RPC call (moneromooo-monero)
82dbba1 core: dynamic fee algorithm from ArticMine (moneromooo-monero)

9 files changed, 202 insertions, 9 deletions

diff --git a/src/cryptonote_config.h b/src/cryptonote_config.h
index 66084da3c..175a5d26e 100644
--- a/src/cryptonote_config.h
+++ b/src/cryptonote_config.h
@@ -64,6 +64,8 @@
 
 #define FEE_PER_KB_OLD                                  ((uint64_t)10000000000) // pow(10, 10)
 #define FEE_PER_KB                                      ((uint64_t)2000000000) // 2 * pow(10, 9)
+#define DYNAMIC_FEE_PER_KB_BASE_FEE                     ((uint64_t)2000000000) // 2 * pow(10,9)
+#define DYNAMIC_FEE_PER_KB_BASE_BLOCK_REWARD            ((uint64_t)10000000000000) // 10 * pow(10,12)
 
 #define ORPHANED_BLOCKS_MAX_COUNT                       100
 
@@ -122,6 +124,8 @@
 
 #define THREAD_STACK_SIZE                       5 * 1024 * 1024
 
+#define HF_VERSION_DYNAMIC_FEE                  4
+
 // New constants are intended to go here
 namespace config
 {
diff --git a/src/cryptonote_core/blockchain.cpp b/src/cryptonote_core/blockchain.cpp
index 9ea023a4c..ffebcd592 100644
--- a/src/cryptonote_core/blockchain.cpp
+++ b/src/cryptonote_core/blockchain.cpp
@@ -46,6 +46,7 @@
 #include "misc_language.h"
 #include "profile_tools.h"
 #include "file_io_utils.h"
+#include "common/int-util.h"
 #include "common/boost_serialization_helper.h"
 #include "warnings.h"
 #include "crypto/hash.h"
@@ -2709,6 +2710,87 @@ void Blockchain::check_ring_signature(const crypto::hash &tx_prefix_hash, const
 }
 
 //------------------------------------------------------------------
+uint64_t Blockchain::get_dynamic_per_kb_fee(uint64_t block_reward, size_t median_block_size)
+{
+  if (median_block_size < CRYPTONOTE_BLOCK_GRANTED_FULL_REWARD_ZONE_V2)
+    median_block_size = CRYPTONOTE_BLOCK_GRANTED_FULL_REWARD_ZONE_V2;
+
+  uint64_t unscaled_fee_per_kb = (DYNAMIC_FEE_PER_KB_BASE_FEE * CRYPTONOTE_BLOCK_GRANTED_FULL_REWARD_ZONE_V2 / median_block_size);
+  uint64_t hi, lo = mul128(unscaled_fee_per_kb, block_reward, &hi);
+  static_assert(DYNAMIC_FEE_PER_KB_BASE_BLOCK_REWARD % 1000000 == 0, "DYNAMIC_FEE_PER_KB_BASE_BLOCK_REWARD must be divisible by 1000000");
+  static_assert(DYNAMIC_FEE_PER_KB_BASE_BLOCK_REWARD / 1000000 <= std::numeric_limits<uint32_t>::max(), "DYNAMIC_FEE_PER_KB_BASE_BLOCK_REWARD is too large");
+  // divide in two steps, since the divisor must be 32 bits, but DYNAMIC_FEE_PER_KB_BASE_BLOCK_REWARD isn't
+  div128_32(hi, lo, DYNAMIC_FEE_PER_KB_BASE_BLOCK_REWARD / 1000000, &hi, &lo);
+  div128_32(hi, lo, 1000000, &hi, &lo);
+  assert(hi == 0);
+
+  return lo;
+}
+
+//------------------------------------------------------------------
+bool Blockchain::check_fee(size_t blob_size, uint64_t fee) const
+{
+  const uint8_t version = get_current_hard_fork_version();
+
+  uint64_t fee_per_kb;
+  if (version < HF_VERSION_DYNAMIC_FEE)
+  {
+    fee_per_kb = FEE_PER_KB;
+  }
+  else
+  {
+    uint64_t median = m_current_block_cumul_sz_limit / 2;
+    uint64_t already_generated_coins = m_db->height() ? m_db->get_block_already_generated_coins(m_db->height() - 1) : 0;
+    uint64_t base_reward;
+    if (!get_block_reward(median, 1, already_generated_coins, base_reward, version))
+      return false;
+    fee_per_kb = get_dynamic_per_kb_fee(base_reward, median);
+  }
+  LOG_PRINT_L2("Using " << print_money(fee) << "/kB fee");
+
+  uint64_t needed_fee = blob_size / 1024;
+  needed_fee += (blob_size % 1024) ? 1 : 0;
+  needed_fee *= fee_per_kb;
+
+  if (fee < needed_fee)
+  {
+    LOG_PRINT_L1("transaction fee is not enough: " << print_money(fee) << ", minimum fee: " << print_money(needed_fee));
+    return false;
+  }
+  return true;
+}
+
+//------------------------------------------------------------------
+uint64_t Blockchain::get_dynamic_per_kb_fee_estimate(uint64_t grace_blocks) const
+{
+  const uint8_t version = get_current_hard_fork_version();
+
+  if (version < HF_VERSION_DYNAMIC_FEE)
+    return FEE_PER_KB;
+
+  if (grace_blocks >= CRYPTONOTE_REWARD_BLOCKS_WINDOW)
+    grace_blocks = CRYPTONOTE_REWARD_BLOCKS_WINDOW - 1;
+
+  std::vector<size_t> sz;
+  get_last_n_blocks_sizes(sz, CRYPTONOTE_REWARD_BLOCKS_WINDOW - grace_blocks);
+  for (size_t i = 0; i < grace_blocks; ++i)
+    sz.push_back(CRYPTONOTE_BLOCK_GRANTED_FULL_REWARD_ZONE_V2);
+
+  uint64_t median = epee::misc_utils::median(sz);
+  if(median <= CRYPTONOTE_BLOCK_GRANTED_FULL_REWARD_ZONE_V2)
+    median = CRYPTONOTE_BLOCK_GRANTED_FULL_REWARD_ZONE_V2;
+
+  uint64_t already_generated_coins = m_db->height() ? m_db->get_block_already_generated_coins(m_db->height() - 1) : 0;
+  uint64_t base_reward;
+  if (!get_block_reward(median, 1, already_generated_coins, base_reward, version))
+    return false;
+
+  uint64_t fee = get_dynamic_per_kb_fee(base_reward, median);
+  LOG_PRINT_L2("Estimating " << grace_blocks << "-block fee at " << print_money(fee) << "/kB");
+  return fee;
+}
+
+//------------------------------------------------------------------
 // This function checks to see if a tx is unlocked.  unlock_time is either
 // a block index or a unix time.
 bool Blockchain::is_tx_spendtime_unlocked(uint64_t unlock_time) const
diff --git a/src/cryptonote_core/blockchain.h b/src/cryptonote_core/blockchain.h
index 262c2952b..eb7a050b2 100644
--- a/src/cryptonote_core/blockchain.h
+++ b/src/cryptonote_core/blockchain.h
@@ -513,6 +513,47 @@ namespace cryptonote
     bool check_tx_inputs(transaction& tx, uint64_t& pmax_used_block_height, crypto::hash& max_used_block_id, tx_verification_context &tvc, bool kept_by_block = false);
 
     /**
+     * @brief get dynamic per kB fee for a given block size
+     *
+     * The dynamic fee is based on the block size in a past window, and
+     * the current block reward. It is expressed by kB.
+     *
+     * @param block_reward the current block reward
+     * @param median_block_size the median blob's size in the past window
+     *
+     * @return the per kB fee
+     */
+    static uint64_t get_dynamic_per_kb_fee(uint64_t block_reward, size_t median_block_size);
+
+    /**
+     * @brief get dynamic per kB fee estimate for the next few blocks
+     *
+     * The dynamic fee is based on the block size in a past window, and
+     * the current block reward. It is expressed by kB. This function
+     * calculates an estimate for a dynamic fee which will be valid for
+     * the next grace_blocks
+     *
+     * @param grace_blocks number of blocks we want the fee to be valid for
+     *
+     * @return the per kB fee estimate
+     */
+    uint64_t get_dynamic_per_kb_fee_estimate(uint64_t grace_blocks) const;
+
+    /**
+     * @brief validate a transaction's fee
+     *
+     * This function validates the fee is enough for the transaction.
+     * This is based on the size of the transaction blob, and, after a
+     * height threshold, on the average size of transaction in a past window
+     *
+     * @param blob_size the transaction blob's size
+     * @param fee the fee
+     *
+     * @return true if the fee is enough, false otherwise
+     */
+    bool check_fee(size_t blob_size, uint64_t fee) const;
+
+    /**
      * @brief check that a transaction's outputs conform to current standards
      *
      * This function checks, for example at the time of this writing, that
diff --git a/src/cryptonote_core/tx_pool.cpp b/src/cryptonote_core/tx_pool.cpp
index dba05a539..e72a592ca 100644
--- a/src/cryptonote_core/tx_pool.cpp
+++ b/src/cryptonote_core/tx_pool.cpp
@@ -133,12 +133,8 @@ namespace cryptonote
       fee = tx.rct_signatures.txnFee;
     }
 
-    uint64_t needed_fee = blob_size / 1024;
-    needed_fee += (blob_size % 1024) ? 1 : 0;
-    needed_fee *= FEE_PER_KB;
-    if (!kept_by_block && fee < needed_fee)
+    if (!kept_by_block && !m_blockchain.check_fee(blob_size, fee))
     {
-      LOG_PRINT_L1("transaction fee is not enough: " << print_money(fee) << ", minimum fee: " << print_money(needed_fee));
       tvc.m_verifivation_failed = true;
       tvc.m_fee_too_low = true;
       return false;
diff --git a/src/rpc/core_rpc_server.cpp b/src/rpc/core_rpc_server.cpp
index 0fca2eb57..a02a2375b 100644
--- a/src/rpc/core_rpc_server.cpp
+++ b/src/rpc/core_rpc_server.cpp
@@ -1283,6 +1283,13 @@ namespace cryptonote
     return true;
   }
   //------------------------------------------------------------------------------------------------------------------------------
+  bool core_rpc_server::on_get_per_kb_fee_estimate(const COMMAND_RPC_GET_PER_KB_FEE_ESTIMATE::request& req, COMMAND_RPC_GET_PER_KB_FEE_ESTIMATE::response& res, epee::json_rpc::error& error_resp)
+  {
+    res.fee = m_core.get_blockchain_storage().get_dynamic_per_kb_fee_estimate(req.grace_blocks);
+    res.status = CORE_RPC_STATUS_OK;
+    return true;
+  }
+  //------------------------------------------------------------------------------------------------------------------------------
   bool core_rpc_server::on_out_peers(const COMMAND_RPC_OUT_PEERS::request& req, COMMAND_RPC_OUT_PEERS::response& res)
   {
 	  // TODO
diff --git a/src/rpc/core_rpc_server.h b/src/rpc/core_rpc_server.h
index 147f019d6..2fdb790ab 100644
--- a/src/rpc/core_rpc_server.h
+++ b/src/rpc/core_rpc_server.h
@@ -116,6 +116,7 @@ namespace cryptonote
         MAP_JON_RPC_WE("get_output_histogram",   on_get_output_histogram,       COMMAND_RPC_GET_OUTPUT_HISTOGRAM)
         MAP_JON_RPC_WE("get_version",            on_get_version,                COMMAND_RPC_GET_VERSION)
         MAP_JON_RPC_WE("get_coinbase_tx_sum",    on_get_coinbase_tx_sum,        COMMAND_RPC_GET_COINBASE_TX_SUM)
+        MAP_JON_RPC_WE("get_fee_estimate",       on_get_per_kb_fee_estimate,    COMMAND_RPC_GET_PER_KB_FEE_ESTIMATE)
       END_JSON_RPC_MAP()
     END_URI_MAP2()
 
@@ -162,6 +163,7 @@ namespace cryptonote
     bool on_get_output_histogram(const COMMAND_RPC_GET_OUTPUT_HISTOGRAM::request& req, COMMAND_RPC_GET_OUTPUT_HISTOGRAM::response& res, epee::json_rpc::error& error_resp);
     bool on_get_version(const COMMAND_RPC_GET_VERSION::request& req, COMMAND_RPC_GET_VERSION::response& res, epee::json_rpc::error& error_resp);
     bool on_get_coinbase_tx_sum(const COMMAND_RPC_GET_COINBASE_TX_SUM::request& req, COMMAND_RPC_GET_COINBASE_TX_SUM::response& res, epee::json_rpc::error& error_resp);
+    bool on_get_per_kb_fee_estimate(const COMMAND_RPC_GET_PER_KB_FEE_ESTIMATE::request& req, COMMAND_RPC_GET_PER_KB_FEE_ESTIMATE::response& res, epee::json_rpc::error& error_resp);
     //-----------------------
 
 private:
diff --git a/src/rpc/core_rpc_server_commands_defs.h b/src/rpc/core_rpc_server_commands_defs.h
index 85895a71a..718c98b6a 100644
--- a/src/rpc/core_rpc_server_commands_defs.h
+++ b/src/rpc/core_rpc_server_commands_defs.h
@@ -1266,4 +1266,27 @@ namespace cryptonote
       END_KV_SERIALIZE_MAP()
     };
   };
+
+  struct COMMAND_RPC_GET_PER_KB_FEE_ESTIMATE
+  {
+    struct request
+    {
+      uint64_t grace_blocks;
+
+      BEGIN_KV_SERIALIZE_MAP()
+        KV_SERIALIZE(grace_blocks)
+      END_KV_SERIALIZE_MAP()
+    };
+
+    struct response
+    {
+      std::string status;
+      uint64_t fee;
+
+      BEGIN_KV_SERIALIZE_MAP()
+        KV_SERIALIZE(status)
+        KV_SERIALIZE(fee)
+      END_KV_SERIALIZE_MAP()
+    };
+  };
 }
diff --git a/src/wallet/wallet2.cpp b/src/wallet/wallet2.cpp
index f57a8d2ca..6d51e355f 100644
--- a/src/wallet/wallet2.cpp
+++ b/src/wallet/wallet2.cpp
@@ -80,6 +80,8 @@ using namespace cryptonote;
 #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 FEE_ESTIMATE_GRACE_BLOCKS 10 // estimate fee valid for that many blocks
+
 #define KILL_IOSERVICE()  \
     do { \
       work.reset(); \
@@ -2765,6 +2767,40 @@ uint64_t wallet2::get_fee_multiplier(uint32_t priority, bool use_new_fee) const
   return 1;
 }
 //----------------------------------------------------------------------------------------------------
+uint64_t wallet2::get_dynamic_per_kb_fee_estimate()
+{
+  epee::json_rpc::request<cryptonote::COMMAND_RPC_GET_PER_KB_FEE_ESTIMATE::request> req_t = AUTO_VAL_INIT(req_t);
+  epee::json_rpc::response<cryptonote::COMMAND_RPC_GET_PER_KB_FEE_ESTIMATE::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_fee_estimate";
+  req_t.params.grace_blocks = FEE_ESTIMATE_GRACE_BLOCKS;
+  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();
+  CHECK_AND_ASSERT_THROW_MES(r, "Failed to connect to daemon");
+  CHECK_AND_ASSERT_THROW_MES(resp_t.result.status != CORE_RPC_STATUS_BUSY, "Failed to connect to daemon");
+  CHECK_AND_ASSERT_THROW_MES(resp_t.result.status == CORE_RPC_STATUS_OK, "Failed to get fee estimate");
+  return resp_t.result.fee;
+}
+//----------------------------------------------------------------------------------------------------
+uint64_t wallet2::get_per_kb_fee()
+{
+  bool use_dyn_fee = use_fork_rules(HF_VERSION_DYNAMIC_FEE, -720 * 14);
+  if (!use_dyn_fee)
+    return FEE_PER_KB;
+  try
+  {
+    return get_dynamic_per_kb_fee_estimate();
+  }
+  catch (...)
+  {
+    LOG_PRINT_L1("Failed to query per kB fee, using " << print_money(FEE_PER_KB));
+    return FEE_PER_KB;
+  }
+}
+//----------------------------------------------------------------------------------------------------
 // separated the call(s) to wallet2::transfer into their own function
 //
 // this function will make multiple calls to wallet2::transfer if multiple
@@ -2774,7 +2810,7 @@ std::vector<wallet2::pending_tx> wallet2::create_transactions(std::vector<crypto
   const std::vector<size_t> unused_transfers_indices = select_available_outputs_from_histogram(fake_outs_count + 1, true, true, trusted_daemon);
 
   const bool use_new_fee  = use_fork_rules(3, -720 * 14);
-  const uint64_t fee_per_kb  = use_new_fee ? FEE_PER_KB : FEE_PER_KB_OLD;
+  const uint64_t fee_per_kb  = get_per_kb_fee();
   const uint64_t fee_multiplier = get_fee_multiplier(priority, use_new_fee);
 
   // failsafe split attempt counter
@@ -3495,7 +3531,7 @@ std::vector<wallet2::pending_tx> wallet2::create_transactions_2(std::vector<cryp
   const bool use_rct = use_fork_rules(4, 0);
 
   const bool use_new_fee  = use_fork_rules(3, -720 * 14);
-  const uint64_t fee_per_kb  = use_new_fee ? FEE_PER_KB : FEE_PER_KB_OLD;
+  const uint64_t fee_per_kb  = get_per_kb_fee();
   const uint64_t fee_multiplier = get_fee_multiplier(priority, use_new_fee);
 
   // throw if attempting a transaction with no destinations
@@ -3777,7 +3813,7 @@ std::vector<wallet2::pending_tx> wallet2::create_transactions_from(const crypton
 
   const bool use_rct = fake_outs_count > 0 && use_fork_rules(4, 0);
   const bool use_new_fee  = use_fork_rules(3, -720 * 14);
-  const uint64_t fee_per_kb  = use_new_fee ? FEE_PER_KB : FEE_PER_KB_OLD;
+  const uint64_t fee_per_kb  = get_per_kb_fee();
   const uint64_t fee_multiplier = get_fee_multiplier(priority, use_new_fee);
 
   LOG_PRINT_L2("Starting with " << unused_transfers_indices.size() << " non-dust outputs and " << unused_dust_indices.size() << " dust outputs");
@@ -4083,7 +4119,7 @@ std::vector<wallet2::pending_tx> wallet2::create_unmixable_sweep_transactions(bo
   tx_dust_policy dust_policy(hf1_rules ? 0 : ::config::DEFAULT_DUST_THRESHOLD);
 
   const bool use_new_fee  = use_fork_rules(3, -720 * 14);
-  const uint64_t fee_per_kb  = use_new_fee ? FEE_PER_KB : FEE_PER_KB_OLD;
+  const uint64_t fee_per_kb  = get_per_kb_fee();
 
   // may throw
   std::vector<size_t> unmixable_outputs = select_available_unmixable_outputs(trusted_daemon);
diff --git a/src/wallet/wallet2.h b/src/wallet/wallet2.h
index b34db0b6c..fb7de44ad 100644
--- a/src/wallet/wallet2.h
+++ b/src/wallet/wallet2.h
@@ -520,6 +520,8 @@ namespace tools
     uint64_t get_upper_tranaction_size_limit();
     std::vector<uint64_t> get_unspent_amounts_vector();
     uint64_t get_fee_multiplier(uint32_t priority, bool use_new_fee) const;
+    uint64_t get_dynamic_per_kb_fee_estimate();
+    uint64_t get_per_kb_fee();
     float get_output_relatedness(const transfer_details &td0, const transfer_details &td1) const;
     std::vector<size_t> pick_prefered_rct_inputs(uint64_t needed_money) const;
     void set_spent(size_t idx, uint64_t height);