¿Qué es el algoritmo de selección de monedas?

No pude encontrar los resultados de la selección de monedas escritos en ninguna parte, y simplemente terminé de reconstruirlos a partir del código. Funciona como mencionó David , pero aquí hay más detalles.

La lógica del algoritmo de selección de monedas para transferir la cantidad objetivo

1. Si alguno de sus UTXO² coincide con el objetivo¹, se utilizará.
2. Si la "suma de todos sus UTXO más pequeños que el objetivo" coincide con el objetivo, se utilizarán. (Este es el caso si barre una billetera completa).
3. Si la "suma de todos sus UTXO menores que el Objetivo" no supera el objetivo, se utilizará el UTXO más pequeño mayor que su Objetivo.

4. De lo contrario, Bitcoin Core realiza 1000 rondas de combinación aleatoria de salidas de transacciones no gastadas hasta que su suma sea mayor o igual que el objetivo. Si encuentra una coincidencia exacta, se detiene temprano y la usa.
   De lo contrario, finalmente se conforma con el mínimo de

   • el UTXO más pequeño mayor que el objetivo
   • la combinación más pequeña de UTXO que descubrió en el Paso 4.

Como mencionó David, el problema del subconjunto se restringirá primero a los UTXO que tengan al menos una confirmación si los envía usted mismo, o seis confirmaciones si los recibe de otra billetera, luego relaja estos requisitos en dos pases más si no se puede descubrir un conjunto adecuado de UTXO. .

Algunos ejemplos

Alice tiene cuatro UTXO:
• UTXO_A 0.1BTC
• UTXO_B 0.3BTC
• UTXO_C 0.5BTC
• UTXO_D 1BTC

Ignoraré las tarifas de transacción por el bien de la simplicidad.

Ejemplo 1:

Alice quiere enviar 0.3BTC .
Bitcoin Core descubre que UTXO_B coincide con el objetivo y solo usa UTXO_B como entrada.

Ejemplo 2:

Alice quiere enviar 0.4BTC .
Bitcoin Core encuentra que UTXO_C es el UTXO más pequeño mayor que el objetivo, y que la suma de todos los UTXO más pequeños que el objetivo (es decir UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4, ) coincide con el objetivo aquí. Tanto UTXO_A como UTXO_B se utilizan como entradas.

Ejemplo 3:

Alice quiere enviar 0.45BTC .
Bitcoin Core encuentra que UTXO_C es el UTXO más pequeño mayor que el objetivo, y que la suma de todos los UTXO más pequeños que el objetivo (es decir UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4, ) no supera el objetivo. UTXO_C se utiliza como única entrada, siendo la siguiente entrada más pequeña mayor que el objetivo.

Ejemplo 4:

Alice quiere enviar 0.35BTC .
Bitcoin Core encuentra que UTXO_C es el UTXO más pequeño mayor que el objetivo, y que la suma de todos los UTXO más pequeños que el objetivo (es decir UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4, ) no coincide con el objetivo. Suma UTXO seleccionados aleatoriamente 1000 veces hasta superar el Target, recordando la menor combinación suficiente. La combinación suficiente más pequeña se compara luego con la entrada individual más pequeña mayor que el objetivo. Suponiendo que encuentre la mejor combinación aquí, que sería UTXO_A + UTXO_B, la encuentra Target < UTXO_A + UTXO_B < UTXO_Cy usa UTXO_A y UTXO_B como entradas.

Ejemplo 5:

Alice quiere enviar 0.6BTC .
Bitcoin Core encuentra que UTXO_D es el UTXO más pequeño mayor que el objetivo, y que la suma de todos los UTXO más pequeños que el objetivo (es decir UTXO_A + UTXO_B + UTXO_C = 0.1 + 0.3 + 0.5 = 0.9, ) no coincide con el objetivo. Comienza probando combinaciones aleatorias como antes, y en esta situación probablemente descubriría eso UTXO_A + UTXO_C = Target. Cuando encuentra una combinación que coincide con el objetivo, se rompe e inmediatamente va con esa combinación. UTXO_A y UTXO_C se utilizan como entradas.

¹ _{"Objetivo" se utiliza aquí para la cantidad a gastar.}
² _{UTXO = Salida de transacciones no gastadas}

Sí, eso es exactamente lo que hace el cliente. Utiliza heurística para hacer esto, resolviendo un problema de subconjunto/suma o mochila.

Utiliza un enfoque de múltiples pases, primero tratando de usar solo monedas con al menos seis confirmaciones. En los próximos dos pases relaja estos requisitos. Dentro de cada pase, intenta minimizar la cantidad de salidas de transacciones reclamadas y luego la cantidad de cambio devuelta.

Tenga en cuenta que se consideran todas las monedas en su billetera. En el modelo de contabilidad que utiliza el cliente de Bitcoin, las monedas específicas no pertenecen a cuentas específicas.

Si desea verificar el código usted mismo, busque SelectCoinsen wallet.cpp.