Support Replace-by-fee in memory pool

[doitian]

Feature Request

Is your feature request related to a problem? Please describe.

CKB only supports Child-pay-for-parent fee-bumping mechanism, but CPFP is not available in some scenarios. For example, when all the cell outputs have a since precondition.

Describe the solution you'd like

Add opt-in mechanism to replace a transaction in the memory pool.

• The user must set a flag to show that a transaction can be replaced.
• The new transaction must have a higher fee weight and a total fee amount.

References

• https://bitcoincore.org/en/faq/optin_rbf/

[doitian]

@code-monad has proposed a solution. We'll hold for now and will push forward when this issue gets enough discussions.

@code-monad could you post your proposal public?

[code-monad]

RBF in CKB(draft 2023.01.05)

old one:

RBF in CKB(deprated)

Refers:

Opt-in RBF FAQ

https://github.com/bitcoin/bitcoin/pull/6871/files#diff-34d21af3c614ea3cee120df276c9c4ae95053830d7f1d3deaf009a4625409ad2

Side Notes:

txid in CKB will change hence the fee and weight was changed. a simple inject-replace is impossible.

Analysis

The key point is, submmit the new tx before old one. Since ChunkQueue is FIFO, so the simplest way is insert new tx into its head.

other details

A tx replacement must follow

1. The transaction is submitted through new extended version of SubmitLocalTx and SubmitRemoteTx called SubmitLocalTxReplaceable and SubmitRemoteTxReplaceable. In the client side which is send through RPC send_transaction_replaceable
2. Assume that a Tx called “Tx_A” was submmited with these functions/calls will be marked as replaceable in TxPool
3. Client can construct a new replace tx called “TX_B” with any same input before the original tx’s status becomes Committed or Rejected
4. The Tx_B must have a higher fee, and spends the same input cell with Tx_A
5. The Tx_B will be inserted into a high priority queue, chunk’s process will pop and use value inside it, until it’s empty, then self.front
6. When submitting tx from high priority queue, it will first check if the hash of it’s input is still in the map; If not, it means that this tx is no longer replaceable(whether Committed or Rejected), this tx will be rejected(not accepted as a replacement)
7. When process a tx in tx_pool, it will first check if any input of this tx is found in the record map, if so, this is a replacement tx, which will perfoms a rbf; if not, it will continue the original resolve process

Solution Design

So the modification would be:

1. Adding parameters to SubmitLocalTx and SubmitRemoteTx

adds a bool in ckb_tx_pool::service::Message

pub(crate) enum Message {
//.....
		SubmitLocalTx(Request<TransactionView, bool, SubmitTxResult>),
    SubmitRemoteTx(Request<(TransactionView, bool, Cycle, PeerIndex), ()>),
//....
}

2. Adding new rpc

Adds send_transaction_replaceable , make send_transaction as a wrapper for it, defaults replaceable is false

#[rpc(name = "send_transaction_replaceable")]
    fn send_transaction_replaceable(
        &self,
        tx: Transaction,
	replaceable: bool,
        outputs_validator: Option<OutputsValidator>,
    ) -> Result<H256>;

3. Adding fields into TxEntry

/// An entry in the transaction pool.
#[derive(Debug, Clone, Eq)]
pub struct TxEntry {
    /// Transaction
    pub rtx: ResolvedTransaction,
    /// Cycles
    pub cycles: Cycle,
    /// tx size
    pub size: usize,
    /// fee
    pub fee: Capacity,
    //......
    pub timestamp: u64,
    **/// The flag to show whether this transaction can be replaced**
    **pub replaceable: bool,**
}

4. Adding new field to TxPool

Adds a map that records all inputs in a replaceable tx

/// Tx-pool implementation
pub struct TxPool {
    pub(crate) config: TxPoolConfig,
    /// The short id that has not been proposed
    pub(crate) pending: PendingQueue,
    /// The proposal gap
    pub(crate) gap: PendingQueue,
    /// Tx pool that finely for commit
    pub(crate) proposed: ProposedPool,
    /// cache for committed transactions hash
    pub(crate) committed_txs_hash_cache: LruCache<ProposalShortId, Byte32>,
    // sum of all tx_pool tx's virtual sizes.
    pub(crate) total_tx_size: usize,
    // sum of all tx_pool tx's cycles.
    pub(crate) total_tx_cycles: Cycle,
    /// storage snapshot reference
    pub(crate) snapshot: Arc<Snapshot>,
    /// record recent reject
    pub recent_reject: Option<RecentReject>,
    // expiration milliseconds,
    pub(crate) expiry: u64,

    // records the replaceable tx's inputs
    pub replaceable_inputs: HashMap<Outpoint, ProposalShortId>,
}

5. Check if a tx is replaceable brefore resolve

In Precheck,there’s a method call named resolve_tx_from_pending_and_proposed, which is used to check if a tx used a seen input in pool

pub(crate) fn resolve_tx_from_pending_and_proposed(
        &self,
        tx: TransactionView,
    ) -> Result<ResolvedTransaction, Reject> {
				//......
				//......
				// Check if tx's inputs is marked replaceable
				if **check_replaceable(tx) {
					// deal with replaceable inputs
					// maybe just act as a normal tx
				} else {
	        resolve_transaction(
            tx,
            &mut seen_inputs,
            &pending_and_proposed_provider,
            snapshot,
	        )
	        .map_err(Reject::Resolve)
				}

    }

All inputs which contain in the tx that the conflict replaceable input from should be removed from TxPool.replaceable_inputs

6. Remove old tx if a tx is replaced by another tx

Since the replacement will never happen when after a tx being Commited/ Rjected,the original tx shall be able to remove from the pool.

7. What will happen if a replace tx submitted too late after the original tx Committed?

It will not become a new tx, because the replace tx spends the same input cell with the original one.

8. Adding replaceable mark into RelayTransaction

check: https://github.com/nervosnetwork/ckb/blob/develop/util/types/schemas/extensions.mol#L155

table RelayTransaction {
    cycles:                     Uint64,
    transaction:                Transaction,
    replaceable:                BoolOpt,
}

9. Adding replaceable mark to PoolTransactionEntry in util/types/src/core/service.rs

// util/types/src/core/service.rs
/// Notify pool transaction entry
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct PoolTransactionEntry {
    /// Transaction view
    pub transaction: TransactionView,
    /// Transaction consumed cycles
    pub cycles: Cycle,
    /// Transaction serialized cycles
    pub size: usize,
    /// Transaction fee
    pub fee: Capacity,
    /// The unix timestamp when entering the Txpool, unit: Millisecond
    pub timestamp: u64,
    pub replaceable: bool,
}

This is used in NotifyController::notify_new_transaction

Avoiding Spam and DDos

As a refer to https://github.com/bitcoin/bitcoin/blob/master/doc/policy/packages.md#package-mempool-acceptance-rules

We need to introduce some additional policy restriction to RBF feature:

1. The replacement tx can not contains any unconfirmed inputs in txpool. This can solve the “tx pin problem”
2. The replacement transaction should pay a higher effective fee rate than the total fee of the root of the set of transactions it replaces
3. The replacement transaction must also pay for replacing the original transactions at or above the rate set by the node's minimum fee. https://github.com/nervosnetwork/ckb/wiki/Transaction-»-Transaction-Fee#min-transaction-fee-rate
4. Replace rate limitation: Assume that we set a time duration as a rate limit(for example 5s), if a tx was replaced within 5s before, then the incomming replace tx will be rejected directly