sBTC Research - Withdrawal Limits / Handling Multiple Withdrawals

[AshtonStephens]

This is a research discussion post meant to be edited with research notes surrounding withdrawal limits and handling more than one withdrawal at a time.

The current sBTC SIP proposes allowing only one withdrawal to be in the pending state at a time, but we need to be able to handle a greater rate of withdrawal requests in order to meet customer demands.

[AshtonStephens]

Currently under investigation by @jferrant.

[jferrant]

By default, Bitcoin Core imposes constraints on unconfirmed transaction chains (limit of 25 ancestors). If a transaction has more than the limit, it will be rejected from the Bitcoin mempool. Managing extended transaction chains can be challenging due to fluctuating fee rates and the potential for parent transactions to be dropped. When fee rates surge, it's not possible to simply prioritize a single transaction; instead, all ancestors must be addressed. Altering any ancestor transaction disrupts all subsequent transactions because their inputs become invalid, necessitating resubmission. Moreover, if a node's mempool reaches capacity, it will prioritize dropping low fee rate transactions. If one of these discarded transactions is an ancestor in a chain, all its descendant transactions become invalidated.
To circumvent these complexities, signers employ a strategy known as payment batching. This involves delaying withdrawals for a specified time period (X minutes) or until a specific number of withdrawal requests are received (Y). These multiple withdrawals are then consolidated into a single Bitcoin payment transaction. This approach reduces the block weight of each payment, resulting in lower fees and simplifying unspent transaction output (UTXO) management. Fewer inputs are required per payment, reducing the amount of funds in transit. Finally, with payment batching, only a single change output is created per batch instead of per withdrawal.

See this very well written stacks overflow for further detail :)

https://bitcoin.stackexchange.com/questions/105033/is-it-okay-to-chain-multiple-unconfirmed-transactions

[AshtonStephens]

Jude's addition in stacks-sbtc/sbtc#324 provides a solution:

The sBTC SIP calls for there to be at most one in-flight withdrawal transaction at any given time. Each withdrawal fulfillment transaction on Bitcoin can fulfill many withdrawal requests on Stacks via batching (this isn't in the SIP yet, but it's easy to describe and easy to implement).

However, what if there are more withdrawal requests pending than TXOs that can fit in a relay-policy-conforming Bitcoin transaction? The solution would be to send multiple withdrawal transactions which consume unconfirmed UTXOs from already-sent (but not confirmed) withdrawal transactions. Assuming that an optimal scheduling can be found, then given that the maximum unconfirmed UTXO chaining depth is 25 and the maximum number of TXOs is 200 (I'm guessing this number), we could fulfill at most 200**(25 - 1) withdraw requests without waiting for confirmation. The Stackers would create a UTXO fan-out tree of depth 24, where each transaction funded 200 additional UTXOs. The tree nodes at depth 25 would spend these UTXOs to fulfill withdraw requests. This means that, in theory, we'd always have sufficient withdraw-processing capacity.

If we consider the task of processing N pending withdrawals, and if we assume that we are always willing to spend all of the BTC wallet's UTXOs each time we proceed to process them, then I think this sketch of an algorithm would suffice:

Input N = the list of pending withdrawals
Input T = the number of TXOs per Bitcoin transaction
Input W = the list of wallet UTXOs
Input P = the wallet's address
Output X = the schedule of Bitcoin transactions to send

;; This pseudocode makes use of a subroutine BitcoinTx(), which takes the following arguments:
;; -- A list of addresses to fund, and their amounts.
;; -- A list of UTXOs to consume to fund them
;; -- The number of change addresses to create (0 or 1)

If len(N) == 0 || len(W) == 0:
   ;; Nothing to do
   Return []

;; D is the UTXO tree depth
Let D = ceil(log(len(N)) / log(T)).
If D == 1:
   ;; All N withdrawals fit into a single transaction.
   ;; This is the overwhelmingly common case.
   ;; Spend all W UTXOs to fund N addresses, and leave one change address.
   Return [new BitcoinTx(N, W, 1)]
   
;; Sort N in descending order from biggest to smallest withdrawal amount
N.sort_for_fulfillment()

;; Need to fan out to produce enough UTXOs
;; S is the UTXOs we can spend from, which starts at W.
;; S will be the last row of intermediate nodes in the tree we will create
Let S = W

;; Make the intermediate nodes in the UTXO tree
;; R is the tree row index
For R in 0..(D - 2):
   ;; C is the number of nodes in row R
   Let C = T ** R
   ;; U is the list of UTXOs we add to the tree
   Let U = []
   For I in 0..C:
      ;; F is the amount of BTC needed to fund all withdrawals that descend from this node
       Let F = N[(I * len(N)) / C .. ((I + 1) * len(N)) / C].sum_withdrawals()
      ;; M is the smallest subset of UTXOs in S that sum to at least F.
      ;; Finding M is NP-hard, but there are poly-time approximation algorithms.  Also, S might be sufficiently small for an optimal solution to be found.
      ;; This removes the M UTXOs from S, and returns the remainder.
      Let (M, S) = find_subset_sum(S, F)
      ;; Make a Bitcoin transaction that creates T outputs to address P, with no change address.
      ;; It consumes the UTXOs in M, and creates a change output that we can spend.
      Let B = new BitcoinTx([P] * T, M, 1);
      U.append(B)
      X.append(B)
      ;; Update S with B's new UTXOs
      S.update(B.outputs)
   ;; The set of spendable UTXOs is now whatever we just added to this row.
   S = U

;; Last row in the tree -- fund all N withdrawals.
;; I indexes S
For I in 0..(len(S) - 1):
   ;; Fund the next T withdrawals.
   ;; Because we go up to `len(S) - 1`, will always fund exactly T withdrawals here.
   Let B = new BitcoinTx(N[T*I ... min(len(N), T*(i+1))], S[i], 0)
   X.append(B)

;; Fund the last withdrawal to produce a change UTXO. This is the new W.
Let B = new BitcoinTx(N[T*(len(S) - 1)..], S[len(S) - 1], 1)
X.append(B)

;; We have our schedule.  Broadcast them in order.
Return X

I'm eliding some details above, but they're straight-forward. In particular, the fee calculation isn't shown, but this can be deduced by the size of the transaction and the going fee set in .sbtc. I'm sure there are bugs and edge cases in the above, but the gist of the idea is that if we can't fit all pending withdrawals into a single batched tx, we can build up a tree of intermediate Bitcoin transactions that we can then immediately spend fulfill all withdrawal requests. The intermediate Bitcoin transactions' UTXOs are all consumed by their children nodes, terminating with the withdrawal fulfillment transaction. The last withdrawal fulfillment transaction creates a single change address with the remaining wallet balance.