Inside Bitcoin

501public:
502    inline void InitializeBegin() noexcept {}
503    inline void InitializeEnd(int num_txns, int num_deps) noexcept
504    {
505         // Cost of initialization.
506         m_cost += 39 * num_txns;
507         // Cost of producing linearization at the end.
508         m_cost += 48 * num_txns + 4 * num_deps;
509    }
510    inline void GetLinearizationBegin() noexcept {}
511    inline void GetLinearizationEnd(int num_txns, int num_deps) noexcept
512    {
513        // Note that we account for the cost of the final linearization at the beginning (see
514        // InitializeEnd), because the cost budget decision needs to be made before calling
515        // GetLinearization.
516        // This function exists here to allow overriding it easily for benchmark purposes.
517    }
518    inline void MakeTopologicalBegin() noexcept {}
519    inline void MakeTopologicalEnd(int num_chunks, int num_steps) noexcept
520    {
521        m_cost += 20 * num_chunks + 28 * num_steps;
522    }
523    inline void StartOptimizingBegin() noexcept {}
524    inline void StartOptimizingEnd(int num_chunks) noexcept { m_cost += 13 * num_chunks; }
525    inline void ActivateBegin() noexcept {}
526    inline void ActivateEnd(int num_deps) noexcept { m_cost += 10 * num_deps + 1; }
527    inline void DeactivateBegin() noexcept {}
528    inline void DeactivateEnd(int num_deps) noexcept { m_cost += 11 * num_deps + 8; }
529    inline void MergeChunksBegin() noexcept {}
530    inline void MergeChunksMid(int num_txns) noexcept { m_cost += 2 * num_txns; }
531    inline void MergeChunksEnd(int num_steps) noexcept { m_cost += 3 * num_steps + 5; }
532    inline void PickMergeCandidateBegin() noexcept {}
533    inline void PickMergeCandidateEnd(int num_steps) noexcept { m_cost += 8 * num_steps; }
534    inline void PickChunkToOptimizeBegin() noexcept {}
535    inline void PickChunkToOptimizeEnd(int num_steps) noexcept { m_cost += num_steps + 4; }
536    inline void PickDependencyToSplitBegin() noexcept {}
537    inline void PickDependencyToSplitEnd(int num_txns) noexcept { m_cost += 8 * num_txns + 9; }
538    inline void StartMinimizingBegin() noexcept {}
539    inline void StartMinimizingEnd(int num_chunks) noexcept { m_cost += 18 * num_chunks; }
540    inline void MinimizeStepBegin() noexcept {}
541    inline void MinimizeStepMid(int num_txns) noexcept { m_cost += 11 * num_txns + 11; }
542    inline void MinimizeStepEnd(bool split) noexcept { m_cost += 17 * split + 7; }
543
544    inline uint64_t GetCost() const noexcept { return m_cost; }
545};
546
547/** Class to represent the internal state of the spanning-forest linearization (SFL) algorithm.
548 *
549 * At all times, each dependency is marked as either "active" or "inactive". The subset of active
550 * dependencies is the state of the SFL algorithm. The implementation maintains several other
551 * values to speed up operations, but everything is ultimately a function of what that subset of
552 * active dependencies is.
553 *
554 * Given such a subset, define a chunk as the set of transactions that are connected through active
555 * dependencies (ignoring their parent/child direction). Thus, every state implies a particular
556 * partitioning of the graph into chunks (including potential singletons). In the extreme, each
557 * transaction may be in its own chunk, or in the other extreme all transactions may form a single
558 * chunk. A chunk's feerate is its total fee divided by its total size.
559 *
560 * The algorithm consists of switching dependencies between active and inactive. The final
561 * linearization that is produced at the end consists of these chunks, sorted from high to low
562 * feerate, each individually sorted in an arbitrary but topological (= no child before parent)
563 * way.
564 *
565 * We define four quality properties the state can have:
566 *
567 * - acyclic: The state is acyclic whenever no cycle of active dependencies exists within the
568 *            graph, ignoring the parent/child direction. This is equivalent to saying that within
569 *            each chunk the set of active dependencies form a tree, and thus the overall set of
570 *            active dependencies in the graph form a spanning forest, giving the algorithm its
571 *            name. Being acyclic is also equivalent to every chunk of N transactions having
572 *            exactly N-1 active dependencies.
573 *
574 *            For example in a diamond graph, D->{B,C}->A, the 4 dependencies cannot be
575 *            simultaneously active. If at least one is inactive, the state is acyclic.
576 *
577 *            The algorithm maintains an acyclic state at *all* times as an invariant. This implies
578 *            that activating a dependency always corresponds to merging two chunks, and that
579 *            deactivating one always corresponds to splitting two chunks.
580 *
581 * - topological: We say the state is topological whenever it is acyclic and no inactive dependency
582 *                exists between two distinct chunks such that the child chunk has higher or equal
583 *                feerate than the parent chunk.
584 *
585 *                The relevance is that whenever the state is topological, the produced output
586 *                linearization will be topological too (i.e., not have children before parents).
587 *                Note that the "or equal" part of the definition matters: if not, one can end up
588 *                in a situation with mutually-dependent equal-feerate chunks that cannot be
589 *                linearized. For example C->{A,B} and D->{A,B}, with C->A and D->B active. The AC
590 *                chunk depends on DB through C->B, and the BD chunk depends on AC through D->A.
591 *                Merging them into a single ABCD chunk fixes this.
592 *
593 *                The algorithm attempts to keep the state topological as much as possible, so it
594 *                can be interrupted to produce an output whenever, but will sometimes need to
595 *                temporarily deviate from it when improving the state.
596 *
597 * - optimal: For every active dependency, define its top and bottom set as the set of transactions
598 *            in the chunks that would result if the dependency were deactivated; the top being the
599 *            one with the dependency's parent, and the bottom being the one with the child. Note
600 *            that due to acyclicity, every deactivation splits a chunk exactly in two.
601 *
602 *            We say the state is optimal whenever it is topological and it has no active
603 *            dependency whose top feerate is strictly higher than its bottom feerate. The
604 *            relevance is that it can be proven that whenever the state is optimal, the produced
605 *            linearization will also be optimal (in the convexified feerate diagram sense). It can
606 *            also be proven that for every graph at least one optimal state exists.
607 *
608 *            Note that it is possible for the SFL state to not be optimal, but the produced
609 *            linearization to still be optimal. This happens when the chunks of a state are
610 *            identical to those of an optimal state, but the exact set of active dependencies
611 *            within a chunk differ in such a way that the state optimality condition is not
612 *            satisfied. Thus, the state being optimal is more a "the eventual output is *known*
613 *            to be optimal".
614 *
615 * - minimal: We say the state is minimal when it is:
616 *            - acyclic
617 *            - topological, except that inactive dependencies between equal-feerate chunks are
618 *              allowed as long as they do not form a loop.
619 *            - like optimal, no active dependencies whose top feerate is strictly higher than
620 *              the bottom feerate are allowed.
621 *            - no chunk contains a proper non-empty subset which includes all its own in-chunk
622 *              dependencies of the same feerate as the chunk itself.
623 *
624 *            A minimal state effectively corresponds to an optimal state, where every chunk has
625 *            been split into its minimal equal-feerate components.
626 *
627 *            The algorithm terminates whenever a minimal state is reached.
628 *
629 *
630 * This leads to the following high-level algorithm:
631 * - Start with all dependencies inactive, and thus all transactions in their own chunk. This is
632 *   definitely acyclic.
633 * - Activate dependencies (merging chunks) until the state is topological.
634 * - Loop until optimal (no dependencies with higher-feerate top than bottom), or time runs out:
635 *   - Deactivate a violating dependency, potentially making the state non-topological.
636 *   - Activate other dependencies to make the state topological again.
637 * - If there is time left and the state is optimal:
638 *   - Attempt to split chunks into equal-feerate parts without mutual dependencies between them.
639 *     When this succeeds, recurse into them.
640 *   - If no such chunks can be found, the state is minimal.
641 * - Output the chunks from high to low feerate, each internally sorted topologically.
642 *
643 * When merging, we always either:
644 * - Merge upwards: merge a chunk with the lowest-feerate other chunk it depends on, among those
645 *                  with lower or equal feerate than itself.
646 * - Merge downwards: merge a chunk with the highest-feerate other chunk that depends on it, among
647 *                    those with higher or equal feerate than itself.
648 *
649 * Using these strategies in the improvement loop above guarantees that the output linearization
650 * after a deactivate + merge step is never worse or incomparable (in the convexified feerate
651 * diagram sense) than the output linearization that would be produced before the step. With that,
652 * we can refine the high-level algorithm to:
653 * - Start with all dependencies inactive.
654 * - Perform merges as described until none are possible anymore, making the state topological.
655 * - Loop until optimal or time runs out:
656 *   - Pick a dependency D to deactivate among those with higher feerate top than bottom.
657 *   - Deactivate D, causing the chunk it is in to split into top T and bottom B.
658 *   - Do an upwards merge of T, if possible. If so, repeat the same with the merged result.
659 *   - Do a downwards merge of B, if possible. If so, repeat the same with the merged result.
660 * - Split chunks further to obtain a minimal state, see below.
661 * - Output the chunks from high to low feerate, each internally sorted topologically.
662 *
663 * Instead of performing merges arbitrarily to make the initial state topological, it is possible
664 * to do so guided by an existing linearization. This has the advantage that the state's would-be
665 * output linearization is immediately as good as the existing linearization it was based on:
666 * - Start with all dependencies inactive.
667 * - For each transaction t in the existing linearization:
668 *   - Find the chunk C that transaction is in (which will be singleton).
669 *   - Do an upwards merge of C, if possible. If so, repeat the same with the merged result.
670 * No downwards merges are needed in this case.
671 *
672 * After reaching an optimal state, it can be transformed into a minimal state by attempting to
673 * split chunks further into equal-feerate parts. To do so, pick a specific transaction in each
674 * chunk (the pivot), and rerun the above split-then-merge procedure again:
675 * - first, while pretending the pivot transaction has an infinitesimally higher (or lower) fee
676 *   than it really has. If a split exists with the pivot in the top part (or bottom part), this
677 *   will find it.
678 * - if that fails to split, repeat while pretending the pivot transaction has an infinitesimally
679 *   lower (or higher) fee. If a split exists with the pivot in the bottom part (or top part), this
680 *   will find it.
681 * - if either succeeds, repeat the procedure for the newly found chunks to split them further.
682 *   If not, the chunk is already minimal.
683 * If the chunk can be split into equal-feerate parts, then the pivot must exist in either the top
684 * or bottom part of that potential split. By trying both with the same pivot, if a split exists,
685 * it will be found.
686 *
687 * What remains to be specified are a number of heuristics:
688 *
689 * - How to decide which chunks to merge:
690 *   - The merge upwards and downward rules specify that the lowest-feerate respectively
691 *     highest-feerate candidate chunk is merged with, but if there are multiple equal-feerate
692 *     candidates, a uniformly random one among them is picked.
693 *
694 * - How to decide what dependency to activate (when merging chunks):
695 *   - After picking two chunks to be merged (see above), a uniformly random dependency between the
696 *     two chunks is activated.
697 *
698 * - How to decide which chunk to find a dependency to split in:
699 *   - A round-robin queue of chunks to improve is maintained. The initial ordering of this queue
700 *     is uniformly randomly permuted.
701 *
702 * - How to decide what dependency to deactivate (when splitting chunks):
703 *   - Inside the selected chunk (see above), among the dependencies whose top feerate is strictly
704 *     higher than its bottom feerate in the selected chunk, if any, a uniformly random dependency
705 *     is deactivated.
706 *   - After every split, it is possible that the top and the bottom chunk merge with each other
707 *     again in the merge sequence (through a top->bottom dependency, not through the deactivated
708 *     one, which was bottom->top). Call this a self-merge. If a self-merge does not occur after
709 *     a split, the resulting linearization is strictly improved (the area under the convexified
710 *     feerate diagram increases by at least gain/2), while self-merges do not change it.
711 *
712 * - How to decide the exact output linearization:
713 *   - When there are multiple equal-feerate chunks with no dependencies between them, pick the
714 *     smallest one first. If there are multiple smallest ones, pick the one that contains the
715 *     last transaction (according to the provided fallback order) last (note that this is not the
716 *     same as picking the chunk with the first transaction first).
717 *   - Within chunks, pick among all transactions without missing dependencies the one with the
718 *     highest individual feerate. If there are multiple ones with the same individual feerate,
719 *     pick the smallest first. If there are multiple with the same fee and size, pick the one
720 *     that sorts first according to the fallback order first.
721 */
722template<typename SetType, typename CostModel = SFLDefaultCostModel>
723class SpanningForestState
724{
725private:
726    /** Internal RNG. */
727    InsecureRandomContext m_rng;
728
729    /** Data type to represent indexing into m_tx_data. */
730    using TxIdx = DepGraphIndex;
731    /** Data type to represent indexing into m_set_info. Use the smallest type possible to improve
732     *  cache locality. */
733    using SetIdx = std::conditional_t<(SetType::Size() <= 0xff),
734                                      uint8_t,
735                                      std::conditional_t<(SetType::Size() <= 0xffff),
736                                                         uint16_t,
737                                                         uint32_t>>;
738    /** An invalid SetIdx. */
739    static constexpr SetIdx INVALID_SET_IDX = SetIdx(-1);
740
741    /** Structure with information about a single transaction. */
742    struct TxData {
743        /** The top set for every active child dependency this transaction has, indexed by child
744         *  TxIdx. Only defined for indexes in active_children. */
745        std::array<SetIdx, SetType::Size()> dep_top_idx;
746        /** The set of parent transactions of this transaction. Immutable after construction. */
747        SetType parents;
748        /** The set of child transactions of this transaction. Immutable after construction. */
749        SetType children;
750        /** The set of child transactions reachable through an active dependency. */