Banyak dompet bitcoin ketika memilih koin untuk dikirim lebih suka menggunakan koin besar, saldo yang lebih besar dari jumlah yang dikirim. Setelah setiap transaksi tersebut, koin perubahan terbentuk. Setelah beberapa waktu, seluruh dompet ditumbuhi dengan koin seperti itu dari urutan 0,001 (~ $ 10 saat ini), yang sudah tidak ada lagi untuk dibelanjakan. Ketika, sekali lagi, saya perlu melakukan transaksi, terpikir oleh saya apakah mungkin untuk mengumpulkan transaksi sehingga tidak ada perubahan. Dompet itu dengan keras kepala menawarkan untuk "memotong" koin lain yang lebih besar, jadi saya memutuskan untuk mengambil koin dengan tangan saya untuk mengumpulkan jumlah yang diperlukan. Namun, ini ternyata tidak sesederhana itu: jumlahnya ternyata kurang dari nilai yang diinginkan atau terlampau banyak. Akibatnya, saya memutuskan bahwa harus ada algoritma yang dengannya Anda dapat mengumpulkan jumlah yang diinginkan dari koin atau lebih sedikit. Ternyata ini tidak hanya mungkin, tetapi bekerja dengan sangat baik yang membuat saya menulis artikel ini. Tetapi hal pertama yang pertama.
Masalah ransel
Masalah ransel diketahui secara luas: untuk mengemas barang-barang berharga sebanyak mungkin ke dalam ransel, asalkan kapasitas ransel terbatas. Dalam hal ini, kami memiliki kasus masalah ransel 0-1 , karena setiap item (koin) tersedia untuk dikemas dalam ransel hanya sekali. Selain itu, bobot masing-masing "item" bertepatan dengan nilainya, jadi kita berhadapan dengan kasus yang lebih khusus, masalah jumlah himpunan bagian dari himpunan bagian . Wikipedia menyarankan menggunakan algoritma genetika, tetapi saya memutuskan untuk mencari solusi yang tepat menggunakan pemrograman dinamis, karena ini cukup dapat dicapai dalam hal sumber daya dan terlihat sederhana.
Untuk mengurangi masalah memilih koin untuk tugas ransel, Anda perlu melakukan sedikit konversi data input. Faktanya adalah bahwa menyelesaikan masalah ransel (lebih tepatnya, jumlah himpunan bagian) akan memberi kita bagian dari himpunan asli yang memiliki jumlah maksimum tidak melebihi parameter (kapasitas pembawa ransel). Tetapi kami tidak puas dengan kombinasi koin, memberikan jumlah yang kurang dari jumlah yang ingin kami kirim. Namun, kami merasa nyaman dengan kombinasi yang sedikit lebih unggul. Misalnya, jika kami perlu mengirim 0,005 bitcoin, dan kami menemukan kombinasi yang memberi 0,00499, maka itu tidak berguna bagi kami, karena kurang dari jumlah yang diinginkan penjual. Tetapi jika kita menemukan 0,005001, itu benar. Satoshiki tambahan dapat digunakan sebagai komisi (kami akan membicarakannya secara rinci di bawah) atau memberikannya kepada penjual jika ia mengizinkan pengiriman jumlah yang lebih besar. Oleh karena itu, dengan bantuan masalah ransel, kita perlu memilih bukan koin yang perlu dikirim , tetapi yang perlu dibiarkan . Maka "kekurangan" secara maksimal akan berubah menjadi "gagal" dalam hal masalah aslinya.
Sebuah contoh Misalkan kita memiliki koin seperti itu: 0,1 BTC, 0,002 BTC, 0,00832423 BTC. Dan kami perlu mengirim 0,01 BTC. Kami akan menemukan koin semacam itu, yang jumlahnya akan maksimum, tetapi kurang dari atau sama dengan jumlah total koin kami dikurangi jumlah yang dikirim, yaitu, jumlah tersebut: 0,1 + 0,002 + 0,00832423 - 0,01 = 0,10032423. Dalam hal ini, pencarian sederhana menemukan bahwa itu adalah koin 0,1. Kami meninggalkannya, yang berarti kami mengirimkan sisanya: 0,002 BTC dan 0,00832423 BTC, yang totalnya memberikan 0,01032423 BTC, yang lebih dari 0,01 BTC dan cocok untuk kami. (Benar, komisi keluar sekitar $ 3, tetapi katakanlah bahwa jaringan sedang sibuk dan kami ingin melakukan pengiriman secepat mungkin.)
Komisi
Untuk memperhitungkan biaya transaksi, saya memodifikasi setiap koin input, mengurangi saldonya dengan jumlah yang harus dibayar untuk dimasukkan dalam transaksi sebagai input. Ini dapat dilakukan dengan mengetahui ukuran input dan komisi (misalnya, 2 satoshi per byte). Selain itu, saya memodifikasi jumlah yang akan dikirim, menambahkan kepadanya harga bagian dari transaksi yang tidak bergantung pada koin yang dipilih: heading dan exit. Pengguna dapat menentukan semua parameter ini menggunakan flag. Anda juga dapat menonaktifkan penyesuaian untuk komisi secara umum dengan menetapkan komisi 0 Satoshi per byte.
Saya mengambil informasi tentang ukuran input dan output dalam berbagai versi alamat (klasik, terbungkus segwit, dan segwit asli dari sini: https://bitcoin.stackexchange.com/a/84006
Algoritma dan implementasi
Saya langsung menjatuhkan algoritma genetika, mungkin sia-sia. Berfokus pada algoritma yang akurat. Upaya pertama saya adalah mewujudkan melalui pencarian lengkap semua kombinasi, tetapi bahkan pada 40 koin itu bekerja berjam-jam dan harus meninggalkannya. Kemudian saya mencoba pemrograman dinamis yang disarankan di Wikipedia . Di dalamnya, Anda tidak dapat menyimpan dalam memori seluruh matriks, tetapi hanya baris saat ini dan sebelumnya. Selain itu, kita tidak perlu menyimpan nilainya, karena bertepatan dengan berat dan merupakan nomor kolom. Tetapi kita perlu mengingat kombinasinya - saya memutuskan untuk menyimpannya dalam bentuk bitset. Selain itu, Anda dapat menyimpan hanya satu baris, membangun baris berikutnya di tempat darinya. Setiap catatan baris nol tetap di tempatnya dan disalin (dengan penambahan bit yang sesuai) ke sel lain sejumlah sel di sebelah kanan (jika kosong di sana sebelumnya). Jika Anda menggunakan urutan terbalik, menyortir sel tempat "lompatan" masuk, maka Anda dapat mengisi semuanya dengan benar:
Setiap sel bukan nol di baris saat ini menghasilkan di baris berikutnya sendiri dan sel lain untuk sejumlah sel tertentu (sama dengan nilai koin yang ditambahkan) di sebelah kanan. Jika sel itu sudah memiliki nilai, maka opsi dengan jumlah terbesar yang dipilih (yaitu, tidak termasuk dalam transaksi) koin "menang", karena kami ingin mengirim koin sesedikit mungkin, hal lain dianggap sama.
Pada satu sel saya menghabiskan 8 byte untuk bitset, dan jumlah sel sama dengan jumlah saldo dari 0 hingga jumlah koin dikurangi jumlah yang dikirim. Misalnya, jika hanya ada 1 bitcoin di dompet, dan 0,1 dikirim, maka akan ada 100'000'000-10'000'000 = 90'000'000 sel, masing-masing 8 byte, yaitu 720 megabyte - sedikit untuk komputer modern. Jika jumlah koin kurang dari 32, maka dimungkinkan untuk menggunakan 4 byte per koin, tetapi saya tidak mengoptimalkannya. Selain itu, jika ada lebih dari 64 koin, maka program tidak berfungsi - ini juga harus diperbaiki dengan membuat bitet dengan panjang sewenang-wenang. Akhirnya, Anda bisa membuang tanda terakhir di saldo, kehilangan sedikit akurasi, tetapi menang 10 kali dalam memori. Tapi sejauh ini akan berhasil.
Saya menyebut program tidak berubah dan meletakkannya di gitlab: gitlab.com/starius/changeless . Itu ditulis dalam Go, dirakit menggunakan go get , seperti biasa. Binari untuk Linux, Windows, Mac , dikumpulkan dalam CI tersedia.
Ketika saya meluncurkan program dengan koin asli, saya kagum pada seberapa akurat dia mengambil kombinasi yang diperlukan. Ketika jumlah koin besar, hampir semua jumlah yang sepadan dengan saldo koin dapat dipilih dengan akurasi hingga satoshi! Anda mengubah jumlah yang diperlukan untuk 1 satoshi dan program ini memberikan kombinasi koin yang sama sekali berbeda dengan jumlah ini. Di bawah ini adalah contoh bekerja pada 50 koin acak dengan saldo dari 0 hingga 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).
Program ini berhasil mengambil kombinasi koin untuk mengirim tepat 10 bitcoin dan tepat 10,00000001 bitcoin (10 bitcoin dan 1 satoshi). Untuk melihat ini, Anda harus mengurangi komisi dari jumlah koin: 10.00004651 - 0,00004651 = 10, 10.00004652 - 0,00004651 = 10.00000001.
Cara mendapatkan daftar saldo koin
Untuk program Electrum, saya menemukan cara ini (perintah konsol):
' '.join((x["value"]) for x in listunspent())
Jika Anda ingin mengecualikan koin tertentu, misalnya di alamat tertentu, maka ini dapat dilakukan seperti ini:
' '.join((x["value"]) for x in listunspent() if x["address"] != "bad address")
Untuk dompet lain, saya tidak menemukan cara yang mudah dan harus mengetik ulang dengan tangan saya.