Withdraw Processing Rate

[jcnelson]

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.

[AshtonStephens]

Closing as duplicate of stacks-network/sbtc#321