Inside Bitcoin

251    assert(confAvg.size() == failAvg.size());
252    for (unsigned int j = 0; j < buckets.size(); j++) {
253        for (unsigned int i = 0; i < confAvg.size(); i++) {
254            confAvg[i][j] *= decay;
255            failAvg[i][j] *= decay;
256        }
257        m_feerate_avg[j] *= decay;
258        txCtAvg[j] *= decay;
259    }
260}
261
262// returns -1 on error conditions
263double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
264                                         double successBreakPoint, unsigned int nBlockHeight,
265                                         EstimationResult *result) const
266{
267    // Counters for a bucket (or range of buckets)
268    double nConf = 0; // Number of tx's confirmed within the confTarget
269    double totalNum = 0; // Total number of tx's that were ever confirmed
270    int extraNum = 0;  // Number of tx's still in mempool for confTarget or longer
271    double failNum = 0; // Number of tx's that were never confirmed but removed from the mempool after confTarget
272    const int periodTarget = (confTarget + scale - 1) / scale;
273    const int maxbucketindex = buckets.size() - 1;
274
275    // We'll combine buckets until we have enough samples.
276    // The near and far variables will define the range we've combined
277    // The best variables are the last range we saw which still had a high
278    // enough confirmation rate to count as success.
279    // The cur variables are the current range we're counting.
280    unsigned int curNearBucket = maxbucketindex;
281    unsigned int bestNearBucket = maxbucketindex;
282    unsigned int curFarBucket = maxbucketindex;
283    unsigned int bestFarBucket = maxbucketindex;
284
285    // We'll always group buckets into sets that meet sufficientTxVal --
286    // this ensures that we're using consistent groups between different
287    // confirmation targets.
288    double partialNum = 0;
289
290    bool foundAnswer = false;
291    unsigned int bins = unconfTxs.size();
292    bool newBucketRange = true;
293    bool passing = true;
294    EstimatorBucket passBucket;
295    EstimatorBucket failBucket;
296
297    // Start counting from highest feerate transactions
298    for (int bucket = maxbucketindex; bucket >= 0; --bucket) {
299        if (newBucketRange) {
300            curNearBucket = bucket;
301            newBucketRange = false;
302        }
303        curFarBucket = bucket;
304        nConf += confAvg[periodTarget - 1][bucket];
305        partialNum += txCtAvg[bucket];
306        totalNum += txCtAvg[bucket];
307        failNum += failAvg[periodTarget - 1][bucket];
308        for (unsigned int confct = confTarget; confct < GetMaxConfirms(); confct++)
309            extraNum += unconfTxs[(nBlockHeight - confct) % bins][bucket];
310        extraNum += oldUnconfTxs[bucket];
311        // If we have enough transaction data points in this range of buckets,
312        // we can test for success
313        // (Only count the confirmed data points, so that each confirmation count
314        // will be looking at the same amount of data and same bucket breaks)
315
316        if (partialNum < sufficientTxVal / (1 - decay)) {
317            // the buckets we've added in this round aren't sufficient
318            // so keep adding
319            continue;
320        } else {
321            partialNum = 0; // reset for the next range we'll add
322
323            double curPct = nConf / (totalNum + failNum + extraNum);
324
325            // Check to see if we are no longer getting confirmed at the success rate
326            if (curPct < successBreakPoint) {
327                if (passing == true) {
328                    // First time we hit a failure record the failed bucket
329                    unsigned int failMinBucket = std::min(curNearBucket, curFarBucket);
330                    unsigned int failMaxBucket = std::max(curNearBucket, curFarBucket);
331                    failBucket.start = failMinBucket ? buckets[failMinBucket - 1] : 0;
332                    failBucket.end = buckets[failMaxBucket];
333                    failBucket.withinTarget = nConf;
334                    failBucket.totalConfirmed = totalNum;
335                    failBucket.inMempool = extraNum;
336                    failBucket.leftMempool = failNum;
337                    passing = false;
338                }
339                continue;
340            }
341            // Otherwise update the cumulative stats, and the bucket variables
342            // and reset the counters
343            else {
344                failBucket = EstimatorBucket(); // Reset any failed bucket, currently passing
345                foundAnswer = true;
346                passing = true;
347                passBucket.withinTarget = nConf;
348                nConf = 0;
349                passBucket.totalConfirmed = totalNum;
350                totalNum = 0;
351                passBucket.inMempool = extraNum;
352                passBucket.leftMempool = failNum;
353                failNum = 0;
354                extraNum = 0;
355                bestNearBucket = curNearBucket;
356                bestFarBucket = curFarBucket;
357                newBucketRange = true;
358            }
359        }
360    }
361
362    double median = -1;
363    double txSum = 0;
364
365    // Calculate the "average" feerate of the best bucket range that met success conditions
366    // Find the bucket with the median transaction and then report the average feerate from that bucket
367    // This is a compromise between finding the median which we can't since we don't save all tx's
368    // and reporting the average which is less accurate
369    unsigned int minBucket = std::min(bestNearBucket, bestFarBucket);
370    unsigned int maxBucket = std::max(bestNearBucket, bestFarBucket);
371    for (unsigned int j = minBucket; j <= maxBucket; j++) {
372        txSum += txCtAvg[j];
373    }
374    if (foundAnswer && txSum != 0) {
375        txSum = txSum / 2;
376        for (unsigned int j = minBucket; j <= maxBucket; j++) {
377            if (txCtAvg[j] < txSum)
378                txSum -= txCtAvg[j];
379            else { // we're in the right bucket
380                median = m_feerate_avg[j] / txCtAvg[j];
381                break;
382            }
383        }
384
385        passBucket.start = minBucket ? buckets[minBucket-1] : 0;
386        passBucket.end = buckets[maxBucket];
387    }
388
389    // If we were passing until we reached last few buckets with insufficient data, then report those as failed
390    if (passing && !newBucketRange) {
391        unsigned int failMinBucket = std::min(curNearBucket, curFarBucket);
392        unsigned int failMaxBucket = std::max(curNearBucket, curFarBucket);
393        failBucket.start = failMinBucket ? buckets[failMinBucket - 1] : 0;
394        failBucket.end = buckets[failMaxBucket];
395        failBucket.withinTarget = nConf;
396        failBucket.totalConfirmed = totalNum;
397        failBucket.inMempool = extraNum;
398        failBucket.leftMempool = failNum;
399    }
400
401    float passed_within_target_perc = 0.0;
402    float failed_within_target_perc = 0.0;
403    if ((passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool)) {
404        passed_within_target_perc = 100 * passBucket.withinTarget / (passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool);
405    }
406    if ((failBucket.totalConfirmed + failBucket.inMempool + failBucket.leftMempool)) {
407        failed_within_target_perc = 100 * failBucket.withinTarget / (failBucket.totalConfirmed + failBucket.inMempool + failBucket.leftMempool);
408    }
409
410    LogDebug(BCLog::ESTIMATEFEE, "FeeEst: %d > %.0f%% decay %.5f: feerate: %g from (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out)\n",
411             confTarget, 100.0 * successBreakPoint, decay,
412             median, passBucket.start, passBucket.end,
413             passed_within_target_perc,
414             passBucket.withinTarget, passBucket.totalConfirmed, passBucket.inMempool, passBucket.leftMempool,
415             failBucket.start, failBucket.end,
416             failed_within_target_perc,
417             failBucket.withinTarget, failBucket.totalConfirmed, failBucket.inMempool, failBucket.leftMempool);
418
419
420    if (result) {
421        result->pass = passBucket;
422        result->fail = failBucket;
423        result->decay = decay;
424        result->scale = scale;
425    }
426    return median;
427}
428
429void TxConfirmStats::Write(AutoFile& fileout) const
430{
431    fileout << Using<EncodedDoubleFormatter>(decay);
432    fileout << scale;
433    fileout << Using<VectorFormatter<EncodedDoubleFormatter>>(m_feerate_avg);
434    fileout << Using<VectorFormatter<EncodedDoubleFormatter>>(txCtAvg);
435    fileout << Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(confAvg);
436    fileout << Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(failAvg);
437}
438
439void TxConfirmStats::Read(AutoFile& filein, size_t numBuckets)
440{
441    // Read data file and do some very basic sanity checking
442    // buckets and bucketMap are not updated yet, so don't access them
443    // If there is a read failure, we'll just discard this entire object anyway
444    uint64_t maxConfirms, maxPeriods;
445
446    // The current version will store the decay with each individual TxConfirmStats and also keep a scale factor
447    filein >> Using<EncodedDoubleFormatter>(decay);
448    if (decay <= 0 || decay >= 1) {
449        throw std::runtime_error("Corrupt estimates file. Decay must be between 0 and 1 (non-inclusive)");
450    }
451    filein >> scale;
452    if (scale == 0) {
453        throw std::runtime_error("Corrupt estimates file. Scale must be non-zero");
454    }
455
456    filein >> Using<VectorFormatter<EncodedDoubleFormatter>>(m_feerate_avg);
457    if (m_feerate_avg.size() != numBuckets) {
458        throw std::runtime_error("Corrupt estimates file. Mismatch in feerate average bucket count");
459    }
460    filein >> Using<VectorFormatter<EncodedDoubleFormatter>>(txCtAvg);
461    if (txCtAvg.size() != numBuckets) {
462        throw std::runtime_error("Corrupt estimates file. Mismatch in tx count bucket count");
463    }
464    filein >> Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(confAvg);
465    maxPeriods = confAvg.size();
466    maxConfirms = scale * maxPeriods;
467
468    if (maxConfirms <= 0 || maxConfirms > 6 * 24 * 7) { // one week
469        throw std::runtime_error("Corrupt estimates file.  Must maintain estimates for between 1 and 1008 (one week) confirms");
470    }
471    for (unsigned int i = 0; i < maxPeriods; i++) {
472        if (confAvg[i].size() != numBuckets) {
473            throw std::runtime_error("Corrupt estimates file. Mismatch in feerate conf average bucket count");
474        }
475    }
476
477    filein >> Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(failAvg);
478    if (maxPeriods != failAvg.size()) {
479        throw std::runtime_error("Corrupt estimates file. Mismatch in confirms tracked for failures");
480    }
481    for (unsigned int i = 0; i < maxPeriods; i++) {
482        if (failAvg[i].size() != numBuckets) {
483            throw std::runtime_error("Corrupt estimates file. Mismatch in one of failure average bucket counts");
484        }
485    }
486
487    // Resize the current block variables which aren't stored in the data file
488    // to match the number of confirms and buckets
489    resizeInMemoryCounters(numBuckets);
490
491    LogDebug(BCLog::ESTIMATEFEE, "Reading estimates: %u buckets counting confirms up to %u blocks\n",
492             numBuckets, maxConfirms);
493}
494
495unsigned int TxConfirmStats::NewTx(unsigned int nBlockHeight, double val)
496{
497    unsigned int bucketindex = bucketMap.lower_bound(val)->second;
498    unsigned int blockIndex = nBlockHeight % unconfTxs.size();
499    unconfTxs[blockIndex][bucketindex]++;
500    return bucketindex;