Was ist der Münzauswahlalgorithmus?

Ich konnte die Ergebnisse der Münzauswahl nirgendwo aufgeschrieben finden und habe sie gerade aus dem Code zusammengesetzt. Es funktioniert wie von David erwähnt , aber hier sind mehr Details.

Die Logik des Münzauswahlalgorithmus zur Übertragung des Zielbetrags

1. Wenn einer Ihrer UTXO ² mit dem Ziel übereinstimmt¹, wird er verwendet.
2. Wenn die „Summe aller Ihrer UTXO kleiner als das Ziel“ mit dem Ziel übereinstimmt, werden sie verwendet. (Dies ist der Fall, wenn Sie eine komplette Brieftasche fegen.)
3. Wenn die „Summe aller Ihrer UTXO kleiner als das Ziel“ das Ziel nicht übersteigt, wird das kleinste UTXO größer als Ihr Ziel verwendet.

4. Andernfalls führt Bitcoin Core 1000 Runden durch, in denen nicht ausgegebene Transaktionsausgaben zufällig kombiniert werden, bis ihre Summe größer oder gleich dem Ziel ist. Wenn es zufällig eine genaue Übereinstimmung findet, stoppt es früh und verwendet diese.
   Ansonsten begnügt man sich schließlich mit dem Minimum von

   • das kleinste UTXO größer als das Ziel
   • die kleinste Kombination von UTXO, die es in Schritt 4 entdeckt hat.

Wie David erwähnt, beschränkt sich das Teilmengenproblem zunächst auf UTXO, die mindestens eine Bestätigung haben, wenn sie von Ihnen selbst gesendet werden, oder sechs Bestätigungen, wenn sie von einer anderen Brieftasche empfangen werden, und lockert diese Anforderungen später in zwei weiteren Durchgängen, wenn kein geeigneter Satz von UTXO entdeckt werden konnte .

Einige Beispiele

Alice hat vier UTXO:
• UTXO_A 0,1
BTC
• UTXO_B 0,3 BTC • UTXO_C 0,5 BTC
• UTXO_D 1 BTC

Ich werde Transaktionsgebühren der Einfachheit halber ignorieren.

Beispiel 1:

Alice möchte 0,3 BTC senden .
Bitcoin Core entdeckt, dass UTXO_B mit dem Ziel übereinstimmt, und verwendet nur UTXO_B als Eingabe.

Beispiel 2:

Alice möchte 0,4 BTC senden .
Bitcoin Core stellt fest, dass UTXO_C das kleinste UTXO ist, das größer als das Ziel ist, und dass die Summe aller UTXO, die kleiner als das Ziel sind (dh UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4), hier mit dem Ziel übereinstimmt. Als Eingänge werden sowohl UTXO_A als auch UTXO_B verwendet.

Beispiel 3:

Alice möchte 0,45 BTC senden .
Bitcoin Core stellt fest, dass UTXO_C das kleinste UTXO ist, das größer als das Ziel ist, und dass die Summe aller UTXO, die kleiner als das Ziel sind (dh UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4), das Ziel nicht übersteigt. UTXO_C wird als einzige Eingabe verwendet, wobei es sich um die nächstkleinere Eingabe handelt, die größer als das Ziel ist.

Beispiel 4:

Alice möchte 0,35 BTC senden .
Bitcoin Core stellt fest, dass UTXO_C das kleinste UTXO ist, das größer als das Ziel ist, und dass die Summe aller UTXO, die kleiner als das Ziel sind (dh UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4), nicht mit dem Ziel übereinstimmt. Es addiert zufällig ausgewählte UTXO 1000 Mal, bis sie das Ziel übertreffen, wobei es sich an die kleinste ausreichende Kombination erinnert. Die kleinste ausreichende Kombination wird dann mit der kleinsten einzelnen Eingabe verglichen, die größer als das Ziel ist. Unter der Annahme, dass es hier die beste Kombination findet, die wäre UTXO_A + UTXO_B, findet es das Target < UTXO_A + UTXO_B < UTXO_Cund verwendet UTXO_A und UTXO_B als Eingaben.

Beispiel 5:

Alice möchte 0,6 BTC senden .
Bitcoin Core stellt fest, dass UTXO_D das kleinste UTXO ist, das größer als das Ziel ist, und dass die Summe aller UTXO, die kleiner als das Ziel sind (dh UTXO_A + UTXO_B + UTXO_C = 0.1 + 0.3 + 0.5 = 0.9), nicht mit dem Ziel übereinstimmt. Es beginnt wie zuvor, zufällige Kombinationen auszuprobieren, und in dieser Situation würde es wahrscheinlich feststellen, dass UTXO_A + UTXO_C = Target. Wenn es eine Kombination findet, die dem Ziel entspricht, bricht es und geht sofort mit dieser Kombination weiter. Als Eingänge werden UTXO_A und UTXO_C verwendet.

¹ _{„Ziel“ wird hier für den auszugebenden Betrag verwendet.}
² _{UTXO = Nicht ausgegebene Transaktionsausgabe}

Ja, genau das macht der Kunde. Dazu verwendet es Heuristiken, um ein Teilmengen-/Summen- oder Rucksackproblem zu lösen.

Es verwendet einen Multi-Pass-Ansatz und versucht zunächst, nur Coins mit mindestens sechs Bestätigungen zu verwenden. In den nächsten beiden Durchgängen lockert es diese Anforderungen. In jedem Durchlauf versucht es, die Anzahl der beanspruchten Transaktionsausgaben und dann die zurückgegebene Wechselgeldmenge zu minimieren.

Beachten Sie, dass alle Münzen in Ihrer Brieftasche berücksichtigt werden. In dem vom Bitcoin-Client verwendeten Abrechnungsmodell gehören bestimmte Coins nicht zu bestimmten Konten.

Wenn Sie den Code selbst überprüfen möchten, suchen Sie nach SelectCoinsin wallet.cpp.