Muchas billeteras bitcoin al elegir monedas para enviar prefieren usar una moneda grande, cuyo saldo es mayor que la cantidad enviada. Después de cada transacción, se forma una moneda de cambio. Después de un tiempo, toda la billetera está cubierta de monedas del orden de 0.001 (~ $ 10 en este momento), que ya no hay nada en qué gastar. Cuando, una vez más, necesitaba hacer una transacción, se me ocurrió si era posible ensamblar la transacción para que no hubiera cambios. La billetera se ofreció obstinadamente a "cortar" otra moneda más grande, así que decidí recoger monedas con mis manos para recolectar la cantidad necesaria. Sin embargo, esto resultó no ser tan simple: la suma resultó ser menor que el valor deseado o excedió demasiado. Como resultado, decidí que debería haber un algoritmo con el que puedas recolectar la cantidad deseada de monedas o un poco más. Resultó que esto no solo es posible, sino que funciona tan bien que me hizo escribir este artículo. Pero lo primero es lo primero.
Problema de mochila
El problema de la mochila es ampliamente conocido: empacar tantas cosas valiosas como sea posible en una mochila, siempre que la capacidad de la mochila sea limitada. En este caso, tenemos el caso del problema de mochila 0-1 , ya que cada artículo (moneda) está disponible para empacar en la mochila solo una vez. Además, el peso de cada "elemento" coincide con su valor, por lo que estamos tratando con un caso aún más especial, el problema de la suma de los subconjuntos . Wikipedia sugiere usar un algoritmo genético, pero decidí buscar una solución exacta usando programación dinámica, ya que esto es bastante factible en términos de recursos y parece simple.
Para reducir el problema de elegir monedas para la tarea de una mochila, debe realizar una pequeña conversión de los datos de entrada. El hecho es que resolver el problema de la mochila (más precisamente, la suma de los subconjuntos) nos dará un subconjunto del conjunto original que tiene una cantidad máxima que no excede el parámetro (capacidad de carga de la mochila). Pero no estamos satisfechos con la combinación de monedas, dando una cantidad menor que la cantidad que queremos enviar. Sin embargo, nos sentimos cómodos con combinaciones que son ligeramente superiores. Por ejemplo, si necesitamos enviar 0.005 bitcoins, y encontramos una combinación que da 0.00499, entonces es inútil para nosotros, ya que es menor que la cantidad que el vendedor quiere. Pero si encontramos 0.005001, eso es correcto. Se puede usar satoshiki adicional como comisión (hablaremos de ello en detalle a continuación) o se lo daremos al vendedor si él permite enviar una cantidad mayor. Por lo tanto, con la ayuda del problema de la mochila, debemos elegir no las monedas que deben enviarse , sino las que deben dejarse . Entonces la "escasez" al máximo se convertirá en "quiebra" en términos del problema original.
Un ejemplo Supongamos que tenemos tales monedas: 0.1 BTC, 0.002 BTC, 0.00832423 BTC. Y necesitamos enviar 0.01 BTC. Encontramos tales monedas, cuya cantidad será máxima, pero menor o igual que la cantidad total de nuestras monedas menos la cantidad enviada, es decir, dicho número: 0.1 + 0.002 + 0.00832423 - 0.01 = 0.10032423. En este caso, una búsqueda simple descubre que es una moneda de 0.1. Lo dejamos, lo que significa que enviamos el resto: 0.002 BTC y 0.00832423 BTC, que en total dan 0.01032423 BTC, que es más de 0.01 BTC y nos conviene. (Es cierto, la comisión salió alrededor de $ 3, pero, digamos que la red está ocupada y queremos que el envío sea lo más rápido posible).
Comisiones
Para tener en cuenta las tarifas de transacción, modifiqué cada moneda de entrada, reduciendo su saldo en la cantidad que habría que pagar por su inclusión en la transacción como entrada. Esto se puede hacer conociendo el tamaño de la entrada y la comisión (por ejemplo, 2 satoshi por byte). Además, modifiqué el monto a enviar, agregando el precio de la parte de la transacción que no depende de las monedas seleccionadas: encabezado y salida (s). El usuario puede especificar todos estos parámetros usando banderas. También puede deshabilitar el ajuste de las comisiones en general especificando una comisión de 0 Satoshi por byte.
Tomé información sobre los tamaños de las entradas y salidas en diferentes versiones de direcciones (segwit clásico, envuelto y segwit nativo desde aquí: https://bitcoin.stackexchange.com/a/84006
Algoritmos e implementación
Inmediatamente dejé caer el algoritmo genético, quizás en vano. Centrado en algoritmos precisos. Mi primer intento fue realizar a través de una búsqueda exhaustiva de todas las combinaciones, pero incluso con 40 monedas funcionó durante horas y tuvo que abandonarlo. Luego probé la programación dinámica sugerida en Wikipedia . En él, no puede guardar en la memoria toda la matriz, sino solo las filas actuales y anteriores. Además, no necesitamos almacenar el valor, ya que coincide con el peso y es el número de columna. Pero debemos recordar la combinación: decidí almacenarla en forma de bitset. Además, puede almacenar solo una fila, creando la siguiente fila in situ a partir de ella. Cada registro de fila distinto de cero permanece en su lugar y se copia (con la adición del bit correspondiente) a otra celda, un cierto número de celdas a la derecha (si antes estaba vacío). Si va en el orden inverso, clasificando a través de la celda en la que va el "salto", entonces puede llenar todo correctamente:
Cada celda diferente de cero en la fila actual genera en la siguiente fila y otra celda para un cierto número de celdas (igual al valor de la moneda agregada) a la derecha. Si ya hay un valor en esa celda, entonces la opción con el mayor número de monedas seleccionadas (es decir, no incluidas en la transacción) "gana", ya que queremos enviar la menor cantidad de monedas posible, otras cosas son iguales.
En una celda gasto 8 bytes para un conjunto de bits, y el número de celdas es igual al número posible de saldos de 0 a la cantidad de monedas menos la cantidad enviada. Por ejemplo, si solo hay 1 bitcoin en la billetera y se envía 0.1, entonces habrá 100'000'000-10'000'000 = 90'000'000 celdas, cada una de 8 bytes, eso es 720 megabytes, un poco para una computadora moderna. Si el número de monedas es inferior a 32, podrían usarse 4 bytes por moneda, pero no lo optimicé. Además, si hay más de 64 monedas, entonces el programa no funciona; esto también debería corregirse haciendo un conjunto de bits de longitud arbitraria. Finalmente, puede descartar el último signo en las balanzas, perdiendo un poco de precisión, pero ganando 10 veces en la memoria. Pero hasta ahora lo hará.
Llamé al programa sin cambios y lo coloqué en el gitlab: gitlab.com/starius/changeless . Está escrito en Go, ensamblado usando go get , como de costumbre. Los binarios para Linux, Windows, Mac , recopilados en CI están disponibles.
Cuando lancé el programa con monedas reales, me sorprendió la precisión con que ella recogió la combinación necesaria. Cuando el número de monedas es grande, casi cualquier cantidad acorde con los saldos de las monedas se puede seleccionar con precisión hasta satoshi. Cambia la cantidad requerida para 1 satoshi y el programa ofrece una combinación completamente diferente de monedas exactamente para esta cantidad. A continuación se muestra un ejemplo de trabajo en 50 monedas aleatorias con saldos de 0 a 1 bitcoin.
$ cat coins50.txt 0.01331611 0.03906237 0.04847086 0.08453118 0.09748168 0.10395389 0.10619825 0.12156721 0.12923149 0.13587973 0.14798976 0.16053788 0.19011834 0.21570038 0.21946913 0.31861430 0.33435508 0.33718842 0.33789473 0.35976748 0.37360122 0.44944553 0.47572926 0.49927495 0.50992142 0.53062326 0.53079433 0.53542072 0.54715225 0.55019714 0.55313907 0.56656642 0.56673333 0.65879650 0.66228482 0.68424322 0.70436496 0.75638055 0.79095597 0.82438005 0.83684407 0.85151564 0.86862948 0.90054250 0.90239402 0.91636213 0.93087757 0.93579251 0.97207439 0.98248384 $ changeless -amount 10.00000000 -coins coins50.txt Processing item 50/50. 0.09748168 + 0.33435508 + 0.47572926 + 0.53542072 + 0.66228482 + 0.70436496 + 0.75638055 + 0.82438005 + 0.9005425 + 0.90239402 + 0.91636213 + 0.93579251 + 0.97207439 + 0.98248384 = 10.00004651 Tx size: 2118 vBytes. Total fees: 0.00004651 BTC (2.2 sats/vByte). $ changeless -amount 10.00000001 -coins coins50.txt Processing item 50/50. 0.01331611 + 0.09748168 + 0.53079433 + 0.56656642 + 0.70436496 + 0.75638055 + 0.82438005 + 0.86862948 + 0.9005425 + 0.91636213 + 0.93087757 + 0.93579251 + 0.97207439 + 0.98248384 = 10.00004652 Tx size: 2118 vBytes. Total fees: 0.00004651 BTC (2.2 sats/vByte).
El programa logró recoger combinaciones de monedas para enviar exactamente 10 bitcoins y exactamente 10.00000001 bitcoins (10 bitcoins y 1 satoshi). Para ver esto, debe restar la comisión de la cantidad de monedas: 10.00004651 - 0.00004651 = 10, 10.00004652 - 0.00004651 = 10.00000001.
Cómo obtener una lista de saldos de monedas
Para el programa Electrum, encontré esta manera (comando de consola):
' '.join((x["value"]) for x in listunspent())
Si desea excluir ciertas monedas, por ejemplo, en una dirección determinada, esto puede hacerse así:
' '.join((x["value"]) for x in listunspent() if x["address"] != "bad address")
Para otras billeteras, no encontré una manera tan fácil y tuve que volver a escribirla con mis manos.