diff --git a/src/miner.h b/src/miner.h
--- a/src/miner.h
+++ b/src/miner.h
@@ -36,12 +36,14 @@
     CTxMemPoolModifiedEntry(CTxMemPool::txiter entry) {
         iter = entry;
         nSizeWithAncestors = entry->GetSizeWithAncestors();
+        nBillableSizeWithAncestors = entry->GetBillableSizeWithAncestors();
         nModFeesWithAncestors = entry->GetModFeesWithAncestors();
         nSigOpCountWithAncestors = entry->GetSigOpCountWithAncestors();
     }
 
     CTxMemPool::txiter iter;
     uint64_t nSizeWithAncestors;
+    uint64_t nBillableSizeWithAncestors;
     Amount nModFeesWithAncestors;
     int64_t nSigOpCountWithAncestors;
 };
@@ -118,6 +120,7 @@
     void operator()(CTxMemPoolModifiedEntry &e) {
         e.nModFeesWithAncestors -= iter->GetFee();
         e.nSizeWithAncestors -= iter->GetTxSize();
+        e.nBillableSizeWithAncestors -= iter->GetTxBillableSize();
         e.nSigOpCountWithAncestors -= iter->GetSigOpCount();
     }
 
diff --git a/src/miner.cpp b/src/miner.cpp
--- a/src/miner.cpp
+++ b/src/miner.cpp
@@ -390,6 +390,7 @@
             if (mit == mapModifiedTx.end()) {
                 CTxMemPoolModifiedEntry modEntry(desc);
                 modEntry.nSizeWithAncestors -= it->GetTxSize();
+                modEntry.nBillableSizeWithAncestors -= it->GetTxBillableSize();
                 modEntry.nModFeesWithAncestors -= it->GetModifiedFee();
                 modEntry.nSigOpCountWithAncestors -= it->GetSigOpCount();
                 mapModifiedTx.insert(modEntry);
diff --git a/src/primitives/transaction.h b/src/primitives/transaction.h
--- a/src/primitives/transaction.h
+++ b/src/primitives/transaction.h
@@ -300,6 +300,10 @@
     // size)
     unsigned int CalculateModifiedSize(unsigned int nTxSize = 0) const;
 
+    // Computes an adjusted tx size so that the UTXIs are billed partially
+    // upfront.
+    size_t GetBillableSize() const;
+
     /**
      * Get the total transaction size in bytes.
      * @return Total transaction size in bytes
diff --git a/src/primitives/transaction.cpp b/src/primitives/transaction.cpp
--- a/src/primitives/transaction.cpp
+++ b/src/primitives/transaction.cpp
@@ -114,6 +114,10 @@
     return nTxSize;
 }
 
+size_t CTransaction::GetBillableSize() const {
+    return ::GetSerializeSize(*this, SER_NETWORK, PROTOCOL_VERSION);
+}
+
 unsigned int CTransaction::GetTotalSize() const {
     return ::GetSerializeSize(*this, SER_NETWORK, PROTOCOL_VERSION);
 }
diff --git a/src/test/transaction_tests.cpp b/src/test/transaction_tests.cpp
--- a/src/test/transaction_tests.cpp
+++ b/src/test/transaction_tests.cpp
@@ -780,4 +780,24 @@
     BOOST_CHECK_EQUAL(state.GetRejectReason(), "bad-txns-undersize");
 }
 
+BOOST_AUTO_TEST_CASE(tx_transaction_fee) {
+    std::vector<size_t> sizes = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
+    for (size_t inputs : sizes) {
+        for (size_t outputs : sizes) {
+            CMutableTransaction mtx;
+            mtx.vin.resize(inputs);
+            mtx.vout.resize(outputs);
+            CTransaction tx(mtx);
+            auto txBillableSize = tx.GetBillableSize();
+            auto txSize = tx.GetTotalSize();
+            BOOST_CHECK(txBillableSize > 0);
+            if (inputs > outputs) {
+                BOOST_CHECK(txBillableSize <= txSize);
+            } else {
+                BOOST_CHECK(txBillableSize >= txSize);
+            }
+        }
+    }
+}
+
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/txmempool.h b/src/txmempool.h
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -86,6 +86,8 @@
     Amount nFee;
     //!< ... and avoid recomputing tx size
     size_t nTxSize;
+    //!< ... and billable size for billing
+    size_t nTxBillableSize;
     //!< ... and modified size for priority
     size_t nModSize;
     //!< ... and total memory usage
@@ -117,12 +119,15 @@
     uint64_t nCountWithDescendants;
     //!< ... and size
     uint64_t nSizeWithDescendants;
+    uint64_t nBillableSizeWithDescendants;
+
     //!< ... and total fees (all including us)
     Amount nModFeesWithDescendants;
 
     // Analogous statistics for ancestor transactions
     uint64_t nCountWithAncestors;
     uint64_t nSizeWithAncestors;
+    uint64_t nBillableSizeWithAncestors;
     Amount nModFeesWithAncestors;
     int64_t nSigOpCountWithAncestors;
 
@@ -143,6 +148,8 @@
     double GetPriority(unsigned int currentHeight) const;
     const Amount GetFee() const { return nFee; }
     size_t GetTxSize() const { return nTxSize; }
+    size_t GetTxBillableSize() const { return nTxBillableSize; }
+
     int64_t GetTime() const { return nTime; }
     unsigned int GetHeight() const { return entryHeight; }
     int64_t GetSigOpCount() const { return sigOpCount; }
@@ -151,11 +158,12 @@
     const LockPoints &GetLockPoints() const { return lockPoints; }
 
     // Adjusts the descendant state, if this entry is not dirty.
-    void UpdateDescendantState(int64_t modifySize, Amount modifyFee,
-                               int64_t modifyCount);
+    void UpdateDescendantState(int64_t modifySize, int64_t modifyBillableSize,
+                               Amount modifyFee, int64_t modifyCount);
     // Adjusts the ancestor state
-    void UpdateAncestorState(int64_t modifySize, Amount modifyFee,
-                             int64_t modifyCount, int modifySigOps);
+    void UpdateAncestorState(int64_t modifySize, int64_t modifyBillableSize,
+                             Amount modifyFee, int64_t modifyCount,
+                             int modifySigOps);
     // Updates the fee delta used for mining priority score, and the
     // modified fees with descendants.
     void UpdateFeeDelta(Amount feeDelta);
@@ -164,12 +172,18 @@
 
     uint64_t GetCountWithDescendants() const { return nCountWithDescendants; }
     uint64_t GetSizeWithDescendants() const { return nSizeWithDescendants; }
+    uint64_t GetBillableSizeWithDescendants() const {
+        return nBillableSizeWithDescendants;
+    }
     Amount GetModFeesWithDescendants() const { return nModFeesWithDescendants; }
 
     bool GetSpendsCoinbase() const { return spendsCoinbase; }
 
     uint64_t GetCountWithAncestors() const { return nCountWithAncestors; }
     uint64_t GetSizeWithAncestors() const { return nSizeWithAncestors; }
+    uint64_t GetBillableSizeWithAncestors() const {
+        return nBillableSizeWithAncestors;
+    }
     Amount GetModFeesWithAncestors() const { return nModFeesWithAncestors; }
     int64_t GetSigOpCountWithAncestors() const {
         return nSigOpCountWithAncestors;
@@ -181,34 +195,39 @@
 
 // Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index.
 struct update_descendant_state {
-    update_descendant_state(int64_t _modifySize, Amount _modifyFee,
-                            int64_t _modifyCount)
-        : modifySize(_modifySize), modifyFee(_modifyFee),
-          modifyCount(_modifyCount) {}
+    update_descendant_state(int64_t _modifySize, int64_t _modifyBillableSize,
+                            Amount _modifyFee, int64_t _modifyCount)
+        : modifySize(_modifySize), modifyBillableSize(_modifyBillableSize),
+          modifyFee(_modifyFee), modifyCount(_modifyCount) {}
 
     void operator()(CTxMemPoolEntry &e) {
-        e.UpdateDescendantState(modifySize, modifyFee, modifyCount);
+        e.UpdateDescendantState(modifySize, modifyBillableSize, modifyFee,
+                                modifyCount);
     }
 
 private:
     int64_t modifySize;
+    int64_t modifyBillableSize;
     Amount modifyFee;
     int64_t modifyCount;
 };
 
 struct update_ancestor_state {
-    update_ancestor_state(int64_t _modifySize, Amount _modifyFee,
-                          int64_t _modifyCount, int64_t _modifySigOpsCost)
-        : modifySize(_modifySize), modifyFee(_modifyFee),
-          modifyCount(_modifyCount), modifySigOpsCost(_modifySigOpsCost) {}
+    update_ancestor_state(int64_t _modifySize, int64_t _modifyBillableSize,
+                          Amount _modifyFee, int64_t _modifyCount,
+                          int64_t _modifySigOpsCost)
+        : modifySize(_modifySize), modifyBillableSize(_modifyBillableSize),
+          modifyFee(_modifyFee), modifyCount(_modifyCount),
+          modifySigOpsCost(_modifySigOpsCost) {}
 
     void operator()(CTxMemPoolEntry &e) {
-        e.UpdateAncestorState(modifySize, modifyFee, modifyCount,
-                              modifySigOpsCost);
+        e.UpdateAncestorState(modifySize, modifyBillableSize, modifyFee,
+                              modifyCount, modifySigOpsCost);
     }
 
 private:
     int64_t modifySize;
+    int64_t modifyBillableSize;
     Amount modifyFee;
     int64_t modifyCount;
     int64_t modifySigOpsCost;
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -33,11 +33,13 @@
       spendsCoinbase(_spendsCoinbase), sigOpCount(_sigOpsCount),
       lockPoints(lp) {
     nTxSize = tx->GetTotalSize();
+    nTxBillableSize = tx->GetBillableSize();
     nModSize = tx->CalculateModifiedSize(GetTxSize());
     nUsageSize = RecursiveDynamicUsage(tx);
 
     nCountWithDescendants = 1;
     nSizeWithDescendants = GetTxSize();
+    nBillableSizeWithDescendants = GetTxBillableSize();
     nModFeesWithDescendants = nFee;
     Amount nValueIn = tx->GetValueOut() + nFee;
     assert(inChainInputValue <= nValueIn);
@@ -46,6 +48,7 @@
 
     nCountWithAncestors = 1;
     nSizeWithAncestors = GetTxSize();
+    nBillableSizeWithAncestors = GetTxBillableSize();
     nModFeesWithAncestors = nFee;
     nSigOpCountWithAncestors = sigOpCount;
 }
@@ -107,23 +110,27 @@
     // setAllDescendants now contains all in-mempool descendants of updateIt.
     // Update and add to cached descendant map
     int64_t modifySize = 0;
-    Amount modifyFee = Amount::zero();
+    int64_t modifyBillableSize = 0;
     int64_t modifyCount = 0;
+    Amount modifyFee = Amount::zero();
     for (txiter cit : setAllDescendants) {
         if (!setExclude.count(cit->GetTx().GetId())) {
             modifySize += cit->GetTxSize();
+            modifyBillableSize += cit->GetTxBillableSize();
             modifyFee += cit->GetModifiedFee();
             modifyCount++;
             cachedDescendants[updateIt].insert(cit);
             // Update ancestor state for each descendant
             mapTx.modify(cit,
                          update_ancestor_state(updateIt->GetTxSize(),
+                                               updateIt->GetTxBillableSize(),
                                                updateIt->GetModifiedFee(), 1,
                                                updateIt->GetSigOpCount()));
         }
     }
     mapTx.modify(updateIt,
-                 update_descendant_state(modifySize, modifyFee, modifyCount));
+                 update_descendant_state(modifySize, modifyBillableSize,
+                                         modifyFee, modifyCount));
 }
 
 // txidsToUpdate is the set of transaction hashes from a disconnected block
@@ -271,10 +278,12 @@
     }
     const int64_t updateCount = (add ? 1 : -1);
     const int64_t updateSize = updateCount * it->GetTxSize();
+    const int64_t updateBillableSize = updateCount * it->GetTxBillableSize();
     const Amount updateFee = updateCount * it->GetModifiedFee();
     for (txiter ancestorIt : setAncestors) {
-        mapTx.modify(ancestorIt, update_descendant_state(updateSize, updateFee,
-                                                         updateCount));
+        mapTx.modify(ancestorIt,
+                     update_descendant_state(updateSize, updateBillableSize,
+                                             updateFee, updateCount));
     }
 }
 
@@ -282,14 +291,18 @@
                                          const setEntries &setAncestors) {
     int64_t updateCount = setAncestors.size();
     int64_t updateSize = 0;
-    Amount updateFee = Amount::zero();
+    int64_t updateBillableSize = 0;
     int64_t updateSigOpsCount = 0;
+    Amount updateFee = Amount::zero();
+
     for (txiter ancestorIt : setAncestors) {
         updateSize += ancestorIt->GetTxSize();
+        updateBillableSize += ancestorIt->GetTxBillableSize();
         updateFee += ancestorIt->GetModifiedFee();
         updateSigOpsCount += ancestorIt->GetSigOpCount();
     }
-    mapTx.modify(it, update_ancestor_state(updateSize, updateFee, updateCount,
+    mapTx.modify(it, update_ancestor_state(updateSize, updateBillableSize,
+                                           updateFee, updateCount,
                                            updateSigOpsCount));
 }
 
@@ -315,12 +328,15 @@
             setEntries setDescendants;
             CalculateDescendants(removeIt, setDescendants);
             setDescendants.erase(removeIt); // don't update state for self
-            int64_t modifySize = -((int64_t)removeIt->GetTxSize());
+            int64_t modifySize = -int64_t(removeIt->GetTxSize());
+            int64_t modifyBillableSize =
+                -int64_t(removeIt->GetTxBillableSize());
             Amount modifyFee = -1 * removeIt->GetModifiedFee();
             int modifySigOps = -removeIt->GetSigOpCount();
             for (txiter dit : setDescendants) {
-                mapTx.modify(dit, update_ancestor_state(modifySize, modifyFee,
-                                                        -1, modifySigOps));
+                mapTx.modify(
+                    dit, update_ancestor_state(modifySize, modifyBillableSize,
+                                               modifyFee, -1, modifySigOps));
             }
         }
     }
@@ -361,20 +377,26 @@
 }
 
 void CTxMemPoolEntry::UpdateDescendantState(int64_t modifySize,
+                                            int64_t modifyBillableSize,
                                             Amount modifyFee,
                                             int64_t modifyCount) {
     nSizeWithDescendants += modifySize;
     assert(int64_t(nSizeWithDescendants) > 0);
+    nBillableSizeWithDescendants += modifyBillableSize;
+    assert(int64_t(nBillableSizeWithDescendants) >= 0);
     nModFeesWithDescendants += modifyFee;
     nCountWithDescendants += modifyCount;
     assert(int64_t(nCountWithDescendants) > 0);
 }
 
-void CTxMemPoolEntry::UpdateAncestorState(int64_t modifySize, Amount modifyFee,
-                                          int64_t modifyCount,
+void CTxMemPoolEntry::UpdateAncestorState(int64_t modifySize,
+                                          int64_t modifyBillableSize,
+                                          Amount modifyFee, int64_t modifyCount,
                                           int modifySigOps) {
     nSizeWithAncestors += modifySize;
     assert(int64_t(nSizeWithAncestors) > 0);
+    nBillableSizeWithAncestors += modifyBillableSize;
+    assert(int64_t(nBillableSizeWithAncestors) >= 0);
     nModFeesWithAncestors += modifyFee;
     nCountWithAncestors += modifyCount;
     assert(int64_t(nCountWithAncestors) > 0);
@@ -903,7 +925,7 @@
 static TxMempoolInfo
 GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it) {
     return TxMempoolInfo{it->GetSharedTx(), it->GetTime(),
-                         CFeeRate(it->GetFee(), it->GetTxSize()),
+                         CFeeRate(it->GetFee(), it->GetTxBillableSize()),
                          it->GetModifiedFee() - it->GetFee()};
 }
 
@@ -1007,7 +1029,7 @@
                                       nNoLimit, nNoLimit, dummy, false);
             for (txiter ancestorIt : setAncestors) {
                 mapTx.modify(ancestorIt,
-                             update_descendant_state(0, nFeeDelta, 0));
+                             update_descendant_state(0, 0, nFeeDelta, 0));
             }
 
             // Now update all descendants' modified fees with ancestors
@@ -1016,7 +1038,7 @@
             setDescendants.erase(it);
             for (txiter descendantIt : setDescendants) {
                 mapTx.modify(descendantIt,
-                             update_ancestor_state(0, nFeeDelta, 0, 0));
+                             update_ancestor_state(0, 0, nFeeDelta, 0, 0));
             }
         }
     }
diff --git a/src/validation.cpp b/src/validation.cpp
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -573,6 +573,9 @@
             nLastTime = nNow;
             // -limitfreerelay unit is thousand-bytes-per-minute
             // At default rate it would take over a month to fill 1GB
+
+            // NOTE: Use the actual size here, and not the fee size since this
+            // is counting real size for the rate limiter.
             if (dFreeCount + nSize >=
                 gArgs.GetArg("-limitfreerelay", DEFAULT_LIMITFREERELAY) * 10 *
                     1000) {