Create new BlockPolicyEstimator for fee estimates

This class groups transactions that have been confirmed in blocks into buckets, based on either their fee or their priority.  Then for each bucket, the class calculates what percentage of the transactions were confirmed within various numbers of blocks.  It does this by keeping an exponentially decaying moving history for each bucket and confirm block count of the percentage of transactions in that bucket that were confirmed within that number of blocks.

-Eliminate txs which didn't have all inputs available at entry from fee/pri calcs

-Add dynamic breakpoints and tracking of confirmation delays in mempool transactions

-Remove old CMinerPolicyEstimator and CBlockAverage code

-New smartfees.py

-Pass a flag to the estimation code, using IsInitialBlockDownload as a proxy for when we are still catching up and we shouldn't be counting how many blocks it takes for transactions to be included.

-Add a policyestimator unit test

2 files changed, 228 insertions, 61 deletions

diff --git a/qa/rpc-tests/smartfees.py b/qa/rpc-tests/smartfees.py
index 4eb8bb4842..69f3c22c17 100755
--- a/qa/rpc-tests/smartfees.py
+++ b/qa/rpc-tests/smartfees.py
@@ -1,5 +1,5 @@
 #!/usr/bin/env python2
-# Copyright (c) 2014 The Bitcoin Core developers
+# Copyright (c) 2014-2015 The Bitcoin Core developers
 # Distributed under the MIT software license, see the accompanying
 # file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
@@ -11,82 +11,249 @@ from test_framework import BitcoinTestFramework
 from bitcoinrpc.authproxy import AuthServiceProxy, JSONRPCException
 from util import *
 
+# Construct 2 trivial P2SH's and the ScriptSigs that spend them
+# So we can create many many transactions without needing to spend
+# time signing.
+P2SH_1 = "2MySexEGVzZpRgNQ1JdjdP5bRETznm3roQ2" # P2SH of "OP_1 OP_DROP"
+P2SH_2 = "2NBdpwq8Aoo1EEKEXPNrKvr5xQr3M9UfcZA" # P2SH of "OP_2 OP_DROP"
+# Associated ScriptSig's to spend satisfy P2SH_1 and P2SH_2
+# 4 bytes of OP_TRUE and push 2-byte redeem script of "OP_1 OP_DROP" or "OP_2 OP_DROP"
+SCRIPT_SIG = ["0451025175", "0451025275"]
+
+def satoshi_round(amount):
+    return  Decimal(amount).quantize(Decimal('0.00000001'), rounding=ROUND_DOWN)
+
+def small_txpuzzle_randfee(from_node, conflist, unconflist, amount, min_fee, fee_increment):
+    '''
+    Create and send a transaction with a random fee.
+    The transaction pays to a trival P2SH script, and assumes that its inputs
+    are of the same form.
+    The function takes a list of confirmed outputs and unconfirmed outputs
+    and attempts to use the confirmed list first for its inputs.
+    It adds the newly created outputs to the unconfirmed list.
+    Returns (raw transaction, fee)
+    '''
+    # It's best to exponentially distribute our random fees
+    # because the buckets are exponentially spaced.
+    # Exponentially distributed from 1-128 * fee_increment
+    rand_fee = float(fee_increment)*(1.1892**random.randint(0,28))
+    # Total fee ranges from min_fee to min_fee + 127*fee_increment
+    fee = min_fee - fee_increment + satoshi_round(rand_fee)
+    inputs = []
+    total_in = Decimal("0.00000000")
+    while total_in <= (amount + fee) and len(conflist) > 0:
+        t = conflist.pop(0)
+        total_in += t["amount"]
+        inputs.append({ "txid" : t["txid"], "vout" : t["vout"]} )
+    if total_in <= amount + fee:
+        while total_in <= (amount + fee) and len(unconflist) > 0:
+            t = unconflist.pop(0)
+            total_in += t["amount"]
+            inputs.append({ "txid" : t["txid"], "vout" : t["vout"]} )
+        if total_in <= amount + fee:
+            raise RuntimeError("Insufficient funds: need %d, have %d"%(amount+fee, total_in))
+    outputs = {}
+    outputs[P2SH_1] = total_in - amount - fee
+    outputs[P2SH_2] = amount
+    rawtx = from_node.createrawtransaction(inputs, outputs)
+    # Createrawtransaction constructions a transaction that is ready to be signed
+    # These transactions don't need to be signed, but we still have to insert the ScriptSig
+    # that will satisfy the ScriptPubKey.
+    completetx = rawtx[0:10]
+    inputnum = 0
+    for inp in inputs:
+        completetx += rawtx[10+82*inputnum:82+82*inputnum]
+        completetx += SCRIPT_SIG[inp["vout"]]
+        completetx += rawtx[84+82*inputnum:92+82*inputnum]
+        inputnum += 1
+    completetx += rawtx[10+82*inputnum:]
+    txid = from_node.sendrawtransaction(completetx, True)
+    unconflist.append({ "txid" : txid, "vout" : 0 , "amount" : total_in - amount - fee})
+    unconflist.append({ "txid" : txid, "vout" : 1 , "amount" : amount})
+
+    return (completetx, fee)
+
+def split_inputs(from_node, txins, txouts, initial_split = False):
+    '''
+    We need to generate a lot of very small inputs so we can generate a ton of transactions
+    and they will have low priority.
+    This function takes an input from txins, and creates and sends a transaction
+    which splits the value into 2 outputs which are appended to txouts.
+    '''
+    prevtxout = txins.pop()
+    inputs = []
+    outputs = {}
+    inputs.append({ "txid" : prevtxout["txid"], "vout" : prevtxout["vout"] })
+    half_change = satoshi_round(prevtxout["amount"]/2)
+    rem_change = prevtxout["amount"] - half_change  - Decimal("0.00001000")
+    outputs[P2SH_1] = half_change
+    outputs[P2SH_2] = rem_change
+    rawtx = from_node.createrawtransaction(inputs, outputs)
+    # If this is the initial split we actually need to sign the transaction
+    # Otherwise we just need to insert the property ScriptSig
+    if (initial_split) :
+        completetx = from_node.signrawtransaction(rawtx)["hex"]
+    else :
+        completetx = rawtx[0:82] + SCRIPT_SIG[prevtxout["vout"]] + rawtx[84:]
+    txid = from_node.sendrawtransaction(completetx, True)
+    txouts.append({ "txid" : txid, "vout" : 0 , "amount" : half_change})
+    txouts.append({ "txid" : txid, "vout" : 1 , "amount" : rem_change})
+
+def check_estimates(node, fees_seen, max_invalid, print_estimates = True):
+    '''
+    This function calls estimatefee and verifies that the estimates
+    meet certain invariants.
+    '''
+    all_estimates = [ node.estimatefee(i) for i in range(1,26) ]
+    if print_estimates:
+        print([str(all_estimates[e-1]) for e in [1,2,3,6,15,25]])
+    delta = 1.0e-6 # account for rounding error
+    last_e = max(fees_seen)
+    for e in filter(lambda x: x >= 0, all_estimates):
+        # Estimates should be within the bounds of what transactions fees actually were:
+        if float(e)+delta < min(fees_seen) or float(e)-delta > max(fees_seen):
+            raise AssertionError("Estimated fee (%f) out of range (%f,%f)"
+                                 %(float(e), min(fees_seen), max(fees_seen)))
+        # Estimates should be monotonically decreasing
+        if float(e)-delta > last_e:
+            raise AssertionError("Estimated fee (%f) larger than last fee (%f) for lower number of confirms"
+                                 %(float(e),float(last_e)))
+        last_e = e
+    valid_estimate = False
+    invalid_estimates = 0
+    for e in all_estimates:
+        if e >= 0:
+            valid_estimate = True
+        else:
+            invalid_estimates += 1
+        # Once we're at a high enough confirmation count that we can give an estimate
+        # We should have estimates for all higher confirmation counts
+        if valid_estimate and e < 0:
+            raise AssertionError("Invalid estimate appears at higher confirm count than valid estimate")
+    # Check on the expected number of different confirmation counts
+    # that we might not have valid estimates for
+    if invalid_estimates > max_invalid:
+        raise AssertionError("More than (%d) invalid estimates"%(max_invalid))
+    return all_estimates
+
+
 class EstimateFeeTest(BitcoinTestFramework):
 
     def setup_network(self):
+        '''
+        We'll setup the network to have 3 nodes that all mine with different parameters.
+        But first we need to use one node to create a lot of small low priority outputs
+        which we will use to generate our transactions.
+        '''
         self.nodes = []
-        self.nodes.append(start_node(0, self.options.tmpdir,
-                            ["-debug=mempool", "-debug=estimatefee", "-relaypriority=0"]))
-        # Node1 mines small-but-not-tiny blocks, and allows free transactions.
+        # Use node0 to mine blocks for input splitting
+        self.nodes.append(start_node(0, self.options.tmpdir, ["-maxorphantx=1000",
+                                                              "-relaypriority=0", "-whitelist=127.0.0.1"]))
+
+        print("This test is time consuming, please be patient")
+        print("Splitting inputs to small size so we can generate low priority tx's")
+        self.txouts = []
+        self.txouts2 = []
+        # Split a coinbase into two transaction puzzle outputs
+        split_inputs(self.nodes[0], self.nodes[0].listunspent(0), self.txouts, True)
+
+        # Mine
+        while (len(self.nodes[0].getrawmempool()) > 0):
+            self.nodes[0].generate(1)
+
+        # Repeatedly split those 2 outputs, doubling twice for each rep
+        # Use txouts to monitor the available utxo, since these won't be tracked in wallet
+        reps = 0
+        while (reps < 5):
+            #Double txouts to txouts2
+            while (len(self.txouts)>0):
+                split_inputs(self.nodes[0], self.txouts, self.txouts2)
+            while (len(self.nodes[0].getrawmempool()) > 0):
+                self.nodes[0].generate(1)
+            #Double txouts2 to txouts
+            while (len(self.txouts2)>0):
+                split_inputs(self.nodes[0], self.txouts2, self.txouts)
+            while (len(self.nodes[0].getrawmempool()) > 0):
+                self.nodes[0].generate(1)
+            reps += 1
+        print("Finished splitting")
+
+        # Now we can connect the other nodes, didn't want to connect them earlier
+        # so the estimates would not be affected by the splitting transactions
+        # Node1 mines small blocks but that are bigger than the expected transaction rate,
+        # and allows free transactions.
         # NOTE: the CreateNewBlock code starts counting block size at 1,000 bytes,
-        # so blockmaxsize of 2,000 is really just 1,000 bytes (room enough for
-        # 6 or 7 transactions)
+        # (17k is room enough for 110 or so transactions)
         self.nodes.append(start_node(1, self.options.tmpdir,
-                                ["-blockprioritysize=1500", "-blockmaxsize=2000",
-                                 "-debug=mempool", "-debug=estimatefee", "-relaypriority=0"]))
+                                     ["-blockprioritysize=1500", "-blockmaxsize=18000",
+                                      "-maxorphantx=1000", "-relaypriority=0", "-debug=estimatefee"]))
         connect_nodes(self.nodes[1], 0)
 
         # Node2 is a stingy miner, that
-        # produces very small blocks (room for only 3 or so transactions)
-        node2args = [ "-blockprioritysize=0", "-blockmaxsize=1500",
-                      "-debug=mempool", "-debug=estimatefee", "-relaypriority=0"]
+        # produces too small blocks (room for only 70 or so transactions)
+        node2args = ["-blockprioritysize=0", "-blockmaxsize=12000", "-maxorphantx=1000", "-relaypriority=0"]
+
         self.nodes.append(start_node(2, self.options.tmpdir, node2args))
-        connect_nodes(self.nodes[2], 0)
+        connect_nodes(self.nodes[0], 2)
+        connect_nodes(self.nodes[2], 1)
 
         self.is_network_split = False
         self.sync_all()
-        
+
+    def transact_and_mine(self, numblocks, mining_node):
+        min_fee = Decimal("0.00001")
+        # We will now mine numblocks blocks generating on average 100 transactions between each block
+        # We shuffle our confirmed txout set before each set of transactions
+        # small_txpuzzle_randfee will use the transactions that have inputs already in the chain when possible
+        # resorting to tx's that depend on the mempool when those run out
+        for i in range(numblocks):
+            random.shuffle(self.confutxo)
+            for j in range(random.randrange(100-50,100+50)):
+                from_index = random.randint(1,2)
+                (txhex, fee) = small_txpuzzle_randfee(self.nodes[from_index], self.confutxo,
+                                                      self.memutxo, Decimal("0.005"), min_fee, min_fee)
+                tx_kbytes = (len(txhex)/2)/1000.0
+                self.fees_per_kb.append(float(fee)/tx_kbytes)
+            sync_mempools(self.nodes[0:3],.1)
+            mined = mining_node.getblock(mining_node.generate(1)[0],True)["tx"]
+            sync_blocks(self.nodes[0:3],.1)
+            #update which txouts are confirmed
+            newmem = []
+            for utx in self.memutxo:
+                if utx["txid"] in mined:
+                    self.confutxo.append(utx)
+                else:
+                    newmem.append(utx)
+            self.memutxo = newmem
 
     def run_test(self):
-        # Prime the memory pool with pairs of transactions
-        # (high-priority, random fee and zero-priority, random fee)
-        min_fee = Decimal("0.001")
-        fees_per_kb = [];
-        for i in range(12):
-            (txid, txhex, fee) = random_zeropri_transaction(self.nodes, Decimal("1.1"),
-                                                            min_fee, min_fee, 20)
-            tx_kbytes = (len(txhex)/2)/1000.0
-            fees_per_kb.append(float(fee)/tx_kbytes)
-
-        # Mine blocks with node2 until the memory pool clears:
-        count_start = self.nodes[2].getblockcount()
-        while len(self.nodes[2].getrawmempool()) > 0:
-            self.nodes[2].generate(1)
-            self.sync_all()
-
-        all_estimates = [ self.nodes[0].estimatefee(i) for i in range(1,20) ]
-        print("Fee estimates, super-stingy miner: "+str([str(e) for e in all_estimates]))
+        self.fees_per_kb = []
+        self.memutxo = []
+        self.confutxo = self.txouts # Start with the set of confirmed txouts after splitting
+        print("Checking estimates for 1/2/3/6/15/25 blocks")
+        print("Creating transactions and mining them with a huge block size")
+        # Create transactions and mine 20 big blocks with node 0 such that the mempool is always emptied
+        self.transact_and_mine(30, self.nodes[0])
+        check_estimates(self.nodes[1], self.fees_per_kb, 1)
 
-        # Estimates should be within the bounds of what transactions fees actually were:
-        delta = 1.0e-6 # account for rounding error
-        for e in filter(lambda x: x >= 0, all_estimates):
-            if float(e)+delta < min(fees_per_kb) or float(e)-delta > max(fees_per_kb):
-                raise AssertionError("Estimated fee (%f) out of range (%f,%f)"%(float(e), min_fee_kb, max_fee_kb))
-
-        # Generate transactions while mining 30 more blocks, this time with node1:
-        for i in range(30):
-            for j in range(random.randrange(6-4,6+4)):
-                (txid, txhex, fee) = random_transaction(self.nodes, Decimal("1.1"),
-                                                        Decimal("0.0"), min_fee, 20)
-                tx_kbytes = (len(txhex)/2)/1000.0
-                fees_per_kb.append(float(fee)/tx_kbytes)
-            self.nodes[1].generate(1)
-            self.sync_all()
+        print("Creating transactions and mining them with a block size that can't keep up")
+        # Create transactions and mine 30 small blocks with node 2, but create txs faster than we can mine
+        self.transact_and_mine(20, self.nodes[2])
+        check_estimates(self.nodes[1], self.fees_per_kb, 3)
 
-        all_estimates = [ self.nodes[0].estimatefee(i) for i in range(1,20) ]
-        print("Fee estimates, more generous miner: "+str([ str(e) for e in all_estimates]))
-        for e in filter(lambda x: x >= 0, all_estimates):
-            if float(e)+delta < min(fees_per_kb) or float(e)-delta > max(fees_per_kb):
-                raise AssertionError("Estimated fee (%f) out of range (%f,%f)"%(float(e), min_fee_kb, max_fee_kb))
+        print("Creating transactions and mining them at a block size that is just big enough")
+        # Generate transactions while mining 40 more blocks, this time with node1
+        # which mines blocks with capacity just above the rate that transactions are being created
+        self.transact_and_mine(40, self.nodes[1])
+        check_estimates(self.nodes[1], self.fees_per_kb, 2)
 
         # Finish by mining a normal-sized block:
-        while len(self.nodes[0].getrawmempool()) > 0:
-            self.nodes[0].generate(1)
-            self.sync_all()
-
-        final_estimates = [ self.nodes[0].estimatefee(i) for i in range(1,20) ]
-        print("Final fee estimates: "+str([ str(e) for e in final_estimates]))
+        while len(self.nodes[1].getrawmempool()) > 0:
+            self.nodes[1].generate(1)
 
+        sync_blocks(self.nodes[0:3],.1)
+        print("Final estimates after emptying mempools")
+        check_estimates(self.nodes[1], self.fees_per_kb, 2)
 
 if __name__ == '__main__':
     EstimateFeeTest().main()
diff --git a/qa/rpc-tests/util.py b/qa/rpc-tests/util.py
index 9ecee31959..ee6d3ca014 100644
--- a/qa/rpc-tests/util.py
+++ b/qa/rpc-tests/util.py
@@ -33,7 +33,7 @@ def check_json_precision():
     if satoshis != 2000000000000003:
         raise RuntimeError("JSON encode/decode loses precision")
 
-def sync_blocks(rpc_connections):
+def sync_blocks(rpc_connections, wait=1):
     """
     Wait until everybody has the same block count
     """
@@ -41,9 +41,9 @@ def sync_blocks(rpc_connections):
         counts = [ x.getblockcount() for x in rpc_connections ]
         if counts == [ counts[0] ]*len(counts):
             break
-        time.sleep(1)
+        time.sleep(wait)
 
-def sync_mempools(rpc_connections):
+def sync_mempools(rpc_connections, wait=1):
     """
     Wait until everybody has the same transactions in their memory
     pools
@@ -56,7 +56,7 @@ def sync_mempools(rpc_connections):
                 num_match = num_match+1
         if num_match == len(rpc_connections):
             break
-        time.sleep(1)
+        time.sleep(wait)
 
 bitcoind_processes = {}