As transaction volume continues to increase, so does the demand for block space, which is limited by both transaction serialized size and consumed cycles in CKB.
The user pays a fee as the bidding to the block space. Setting the fee too low may cause the transaction delayed or never confirmed.
Which makes the matters worse, it seems unlikely that the user will always set a proper fee. There are mainly two reasons. First, The fee estimate algorithm could not predict the future fee surge caused by sudden congestion. The second, in applications such as lighting network, the transaction was created long before it is revealed.
The user has to fix the fee issue via fee bumping. This article is a proposal for the fee bumping mechanism for CKB.
The miners select transactions to fill the limited block space which gives the highest fee. Because there are two different limits, serialized size and consumed cycles, the selection algorithm is a multi-dimensional knapsack problem.
Introducing the transaction virtual bytes converts the multi-dimensional knapsack to a typical knapsack problem, which has a simple greedy algorithm.
Using the following notations
The virtual bytes is
The greedy algorithm sorts the transactions in decreasing order of fee rate, in which is the fee paid by the transaction . It then proceeds to insert them into the block as long as there is remaining space of both serialized size and consumed cycles.
A transaction A is a parent of another transaction B if at least one of B's input cells is A's output cell. B is called a child transaction of A.
An ancestor of a transaction is either its parent transaction or an ancestor of any its parent.
Miners are not allowed to add a transaction to the next block unless all its ancestors are already in the chain or will be added to the next block together.
Instead of sorting the transactions by fee rate and try them one by one, miners have to process transactions in packages.
The ancestor package of a transaction is a set that includes itself and all its ancestors remaining in the pool. The weight of the ancestor package is the lesser of the transaction fee rate and the package fee rate as defined in the following formula, where
A modified algorithm sorts the transactions by ancestor weight and inserts the package as a whole.
The algorithm has to scan all the transactions unless there is a perfect fit for the max size or cycles. If the block is nearly full, and there are consecutive failed tests, the algorithm can exit early.
⚠️⚠️️️️️⚠️️️ This section is still a proposal, which may be not available in the current version of CKB.
A transaction B is a child of another transaction A if at least one of B's input cells is A's output cell.
A descendant of a transaction is either its child transaction or a descendant of any its child.
The descendant package of a transaction is a set which includes itself and all its descendants also in the pool. The weight of the descendant package is the greater of the transaction fee rate and the package fee rate as defined in the following formula, where
Because of the physical limit, the node cannot save all unconfirmed transactions in the pool. In CKB, the pool has both the size and cycle limit. When the pool reaches the limit, it must trim the transactions using the descendant weight.
Because transaction weight depends on its fee rate and its package fee rate, there are two corresponding methods to bump the fee.
A CPFP transaction is a child transaction of an existing transaction in the pool. To prioritize its parent, it must have a higher ancestor weight than its parent. Assume that the new transaction is , and its only parent transaction in the pool is , the CPFP transaction must have enough fee such that
The CPFP transaction usually has a high fee rate, so it also bumps the descendant weight of its parent transaction thus they are less unlikely to be trimmed when the pool is full.
However, when a package is too large, the chance that it fails to fit into the remaining block space increases. The pool must limit the package transaction count, total serialized size, and the total consumed cycles.
If a transaction has outputs for different parties, one party can add new descendant transactions to pin the transaction with a very low descendant weight. Because of the descendant package limits, other parties cannot bump the fee rate via CPFP.[2] It's a serious problem for protocols like lighting network.[3]
CPFP carve-out[4] is a solution to this problem. It allows exceeding the descendant package limits when the last transaction added to the package meets the following criteria.
⚠️⚠️️️️️⚠️️️ CPFP carve-out is still a proposal, which may be not available in the current version of CKB.
CPFP carve-out allows at most one extra transaction. If the descendant package of a transaction has transactions, the pool should reject new descendants.
If all the parents of a transaction have been confirmed and the transaction has two outputs for each party, neither party can trigger the carve-out because only the direct child satisfies the condition "The transaction has one ancestor in the pool", but a single child is far from reaching the package limits. If a party adds more descendants, another party is always able to add an extra carve-out child to bump the fee.
⚠️⚠️️️️️⚠️️️ RBF is still a proposal, which may be not available in the current version of CKB.
An RBF transaction has conflict inputs with existing transactions in the pool. Miners must remove all the conflict transactions and their descendants before accepting the RBF transaction, so the transaction creators must pay enough fees as incentives.
Using C to denote the set of conflict transactions and their descendants, the RBF transaction must pay the fee that
The RBF transaction should not break the package limits. But some packages may have an extra transaction because of CPFP carve out, RBF carve-out reserves their limits if the new transaction has a single conflict transaction which has no descendants. When RBF carve out takes effect, any ancestor of the new transaction is allowed to have a descendant package that
Recall that , are descendant package transactions count, total virtual bytes limits. is carve out transaction virtual bytes limits.
In CKB, it is the transaction molecule serialized size plus 4 bytes overhead. ↩︎
Bitcoin Optech. Transaction pinning. https://bitcoinops.org/en/topics/transaction-pinning/ ↩︎
Bitcoin Optech, New attack against LN payment atomicity. Bitcoin Optech Newsletter #95. https://bitcoinops.org/en/newsletters/2020/04/29/#new-attack-against-ln-payment-atomicity ↩︎
Bitcoin Optech. CPFP carve out. https://bitcoinops.org/en/topics/cpfp-carve-out/ ↩︎