Branch and Bound (BnB, ramificación y poda)

Branch and Bound es el algoritmo de selección de monedas que intenta no crear cambio en absoluto. Dado el monto de un pago y el conjunto de monedas de la billetera, busca un subconjunto cuyo total caiga en una ventana estrecha: como mínimo, el pago más su comisión; como máximo, esa cifra más lo que habría costado crear una salida de cambio. Cualquier combinación dentro de la ventana puede gastarse como una transacción sin cambio (en inglés), y el pequeño excedente se va al minero en lugar de volver como una moneda nueva.

El nombre describe la búsqueda. El algoritmo ordena las monedas por valor y las recorre en un árbol en profundidad; en cada paso se ramifica según incluya o no la siguiente moneda. La poda es lo que mantiene eso manejable: cada vez que el total acumulado se pasa de la ventana, o las monedas que quedan no pueden alcanzarla de ninguna manera, la rama se abandona de inmediato. También se detiene tras un presupuesto fijo de intentos, 100,000 en la implementación de Core, y devuelve el mejor conjunto sin cambio que haya encontrado, o nada. Los demás algoritmos de la billetera corren junto a él de todos modos, así que el usuario nunca se queda esperándolo.

La idea viene de la tesis de maestría de 2016 de Mark "Murch" Erhardt sobre selección de monedas, que mostró que el método Knapsack que Bitcoin Core usaba desde los primeros tiempos casi nunca encontraba las coincidencias exactas para las que había sido diseñado (menos del 1.5% de los pagos en su simulación), mientras que Branch and Bound las encontraba hasta en el 30% y reducía en más de un tercio el número de UTXOs que acumulaba la billetera. Andrew Chow implementó Branch and Bound para Core, el pull request se integró en 2018 y el algoritmo salió en la versión 0.17.0 en octubre de ese año. De la 0.17 a la 22.0 corría primero, y la billetera recurría a Knapsack si fallaba. Desde la versión 23.0 la billetera corre todos los algoritmos en cada gasto y se queda con el resultado que menos desperdicia, y una solución sin cambio de Branch and Bound suele ganar esa comparación.

¿Por qué tomarse la molestia de evitar el cambio? Porque una salida de cambio es un costo que se paga dos veces. Agrega bytes a la transacción actual y crea una moneda nueva que agregará más bytes a alguna transacción futura cuando por fin se gaste. Es también la salida que los analistas de cadena siguen para vincular una de tus transacciones con la siguiente. Una transacción sin cambio es más barata de construir, más barata de gastar después y no le da nada con qué trabajar a la heurística de detección del cambio. Branch and Bound encuentra esas transacciones cuando existen, y resulta que existen más a menudo de lo que la gente espera en cuanto una billetera tiene una variedad razonable de tamaños de moneda.