Der beste Weg, um die Schwierigkeit beim Generieren einer bestimmten Vanity-Adresse zu berechnen?

So kam es dann doch etwas anders. Aber jetzt habe ich eine Lösung, die praktikabel und angemessen erscheint. Die ursprüngliche Aufgabe bestand darin, die Schwierigkeit zu berechnen, eine bestimmte Vanity-Adresse zu finden (wie es vanitygen tut).

Schwierig ist im Grunde die Anzahl_aller_möglichen_Adressen / Anzahl_der_Adressen_mit_Vanity -Präfix- Rate.

Wenn wir beispielsweise nur Dec-Adressen zwischen 0 und 9999 haben, ist es schwierig, Vanity-Adressen zu finden, die mit "1" beginnen, 10, da 10000 die Anzahl aller möglichen Adressen ist und nur Adressen von 1000 bis 1999 übereinstimmen , also gibt es 1000 von ihnen.

Bei Bitcoin-Adressen sind die Dinge etwas komplizierter, aber das Prinzip ist das gleiche.

Lassen Sie uns zuerst herausfinden, wie die Bitcoin-Adresse gebildet wird: Kurz gesagt gibt es ein paar Schritte, die für unsere Aufgabe wichtig sind:

1. Nehmen Sie ein 0x00-Byte (das ist das erste Byte der Adresse, um die Version darzustellen)
2. Nehmen Sie das Ergebnis von ricemd160 (20 Bytes, 160 Bits).
3. Nehmen Sie die ersten vier Bytes von sha256(sha256(ripemd160)) als Prüfsumme
4. Verketten Sie 0x00 + 20 Bytes von reifmd + 4 Bytes von sha256 von sha256 von reifmd
5. Jetzt erhalten Sie ein 25 Byte langes Etwas, das Sie als Long Integer behandeln müssen. Wir nennen diese Nummer eine "Proto-Adresse".
6. Base58Überprüfen Sie es (aber das ist jetzt nicht sehr wichtig) und das Ergebnis wird die Bitcoin-Adresse sein.

Was jedoch wichtig ist, ist das Verständnis dafür, dass wir nur einen reifen Teil ändern können. Das führt uns zu zwei Schlussfolgerungen: Erstens gibt es nur 2^160 Bitcoin-Adressen und zweitens ist es etwas komplizierter.

Lassen Sie uns eine Antwort auf eine wichtige Frage finden: Wenn A und B Zahlen sind, die mit derselben Ziffer beginnen, und es ein X wie A < X < B gibt, bedeutet das, dass X mit derselben Ziffer beginnt? Wenn A 1000 und B 1999 ist – ja. X kann eine beliebige Zahl von 1001 bis 1998 sein. Aber was ist, wenn A 100 und B 10000 ist? X kann eine beliebige Zahl dazwischen sein und darf nicht mit derselben Ziffer beginnen. A, X und B müssen also nur dann am Anfang die gleiche Ziffer haben, wenn sie die gleiche Anzahl von Ziffern haben. Denken Sie daran, es ist wichtig.

Lassen Sie uns herausfinden, was eine Vanity-Adresse und was eine Base58-Codierung ist.

Base58 ist wie base16 und base2 und base10 und wie jede andere Base. Das Symbol "A" ist beispielsweise "A" in base58 und 0x09 in base16 oder 9 in base10. Das ist ein guter Anfang.

Lassen Sie uns entscheiden, dass unsere Adresse mit "1A" beginnt. Wir wissen, dass die Adresse im Grunde eine ganze Zahl von 25 Bytes ist. Was ist "1A"? Es ist ein "1A" in base58 und 0009 in base10. Oder nur 9.

Das bedeutet, dass jede Zahl, die durch 58 geteilt werden kann und einen Quotienten gleich „9“ hat, uns ein „A“-Symbol während base58 gibt. Zum Beispiel 522/58 == 9. 30276/58/58 == 9. Aber nicht nur diese Zahlen werden auf 9 enden, sondern auch diese:

• 9*58 + 58 -1
• 9*58^2 + 58^2 - 1
• 9*58^3 + 58^3 -1
• oder einfach irgendeine (9 + 1)*58^N -1 Zahl

Die Formel gilt also für den Beginn des Bereichs:

Präfix*58^n

für das Ende des Sortiments:

(Präfix + 1)*58^n -1

Hier kommt eine Idee: Wir müssen alle Zahlenbereiche finden, die diese Anforderungen erfüllen:

1. Nummer am Anfang des Bereichs und Nummer am Ende des Bereichs haben die gleiche Anzahl von Ziffern
2. Die Längen dieser Nummern müssen gleich der Länge der Proto-Adresse sein. Das ist wichtig, weil wir eine 25 Bytes lange Ganzzahl haben müssen, die mit einem Null-Byte beginnt, das ist das Gesetz!
3. Ihre Werte müssen kleiner als 2^192 sein, da das führende Byte immer 00 ist und wir nur 25 Bytes haben, was uns nur 24 Bytes oder 192 Bits übrig lässt, deren Wert wir ändern können.

Wenn wir alle diese Bereiche finden, können wir herausfinden, wie viele Zahlen es in dem Bereich gibt, indem wir einfach den Beginn des Bereichs vom Ende des Bereichs subtrahieren. Die Summe aller Längen unserer Bereiche ergibt, wie viele mögliche Proto-Adressen wir erhalten können.

Aber das ist nicht das Ende. Wie wir uns erinnern, sind Proto-Adressen nur alle möglichen großen Zahlen, sodass nicht alle in gültige Bitcoin-Adressen umgewandelt werden können. Aber es ist sehr einfach zu berechnen, wie viele von ihnen können. Antwort ist 1/256^4. Warum?

Denn wenn wir eine Bitcoin-Adresse generieren, können wir nur das Ergebnis von reifmd ändern, das uns 20 Bytes gibt. Die anderen 4 Bytes sind nur Prüfsummen. Man kann sich das einfach so vorstellen, dass wir 2^192 Proto-Adressen haben können und nur 2^160 davon gültig sind, weil wir nur 2^160 gültige Bitcoin-Adressen haben können. Dies gibt uns eine Rate von 1/256^4.

Letzter Teil: Nehmen Sie die Summe aller unserer Bereichslängen, teilen Sie sie durch 256 ^ 4 und dies wird die Anzahl aller möglichen Bitcoin-Adressen mit gegebener Eitelkeit sein. Teile einfach 2^160 durch diese Zahl und das wird das Ergebnis sein.

Lassen Sie es uns veranschaulichen, indem wir das A-Präfix schwierig finden.

A ist nur 9. Ok, lass uns alle Bereiche herausfinden, die uns 9 als Quotient geben. 522 - 579 30276 - 33639 1756008 - 1951119 ....... we must go and go until length of our numbers will not reach 24 bytes (mind the leading 00 byte) ........ 41735950621193504130037849728691446275009901558579068928 - 46373278467992782366708721920768273638899890620643409919

Diese beiden Nummern haben eine Länge von 24 Byte. Dies ist unser erstes Sortiment. Der nächste ist

2420685136029223239542195284264103883950574290397585997824 - 2689650151143581377269105871404559871056193655997317775359

Diese Nummern sind ebenfalls 24 Byte lang.

Das nächste Paar ist 140399737889694947893447326487318025269133308843059987873792 und 155999708766327719881608140541464472521259232047844430970879

Beide sind größer als 2^192, also müssen wir jetzt aufhören. Fassen wir unsere Ergebnisse zusammen:

46373278467992782366708721920768273638899890620643409919 - 41735950621193504130037849728691446275009901558579068928 + 2689650151143581377269105871404559871056193655997317775359 - 2420685136029223239542195284264103883950574290397585997824 = 273602342961157415963581459332532814469509354661796118526

So viele mögliche Proto-Adressen können wir haben. Aber vergessen Sie nicht, es durch 156^4 zu teilen und erhalten Sie: 63703009616853067642911677093369144589991624155

Und so viele mögliche Bitcoin-Adressen können wir haben. Teilen Sie jetzt einfach 2^160 durch diese Zahl und das Ergebnis ist 22

Dies ist schwierig für das Präfix "A" oder "1A". Lassen Sie uns nun über einige Sonderfälle sprechen. Was Sie überprüfen müssen, wenn Sie mit Bereichen arbeiten, ist:

• Länge . Die Länge des Bereichs muss gleich der Länge der Protoadresse sein, und Sie müssen alle geeigneten Bereiche zählen.
• 2^192. Wenn das Ende des Bereichs größer als 2^192 ist, müssen Sie diesen Bereich von oben um den Wert 2^192 abschneiden - die Proto-Adresse darf nicht größer als 2^192 sein. Denken Sie auch daran, dass der Beginn des Bereichs immer kleiner als 2^192 sein muss (andernfalls macht das keinen Sinn).

Was ist mit Sonderfällen? Mögen Sie Muster, die mit mehr als einer "1" beginnen? es ist ein bisschen knifflig, aber nicht sehr kompliziert. "1" ist ein Sonderfall in base58, da es gleich 0 ist. Das heißt, wenn am Anfang einige "1" stehen, müssen alle diese Bytes auf Null gesetzt werden und können nicht verwendet werden. Also muss unsere Proto-Adresse, wenn wir sie mit zwei "1" beginnen wollen, am Anfang zwei Null-Bytes haben. Wie 0000XXXX .... wenn wir 111 haben wollen, müssen wir am Anfang 3 Bytes als Nullbytes lassen und so weiter.

Was bedeutet es? Jede 1 kürzt ein Byte von unserer Proto-Adresse, also schneidet sie die Länge unserer möglichen größten Proto-Adressnummer um 8 Bit oder um ein Byte. Das macht es 256-mal schwerer zu finden und ein Byte kürzer.

Wenn wir am Anfang 11 haben wollen, haben wir nur 23 Bytes, um unsere Bereiche zu generieren, und wenn wir 1111 haben wollen, werden wir nur 21 Bytes haben. Unsere Reichweiten werden also viel kleiner und die Schwierigkeit wird viel höher sein. Und natürlich ist es nicht möglich, eine Adresse zu finden, wenn wir mehr als 19 "1" im Muster haben, denn wir müssen etwas dem reifen Ergebnis überlassen :)

Wenn das Muster nur mit 111 beginnt, zählen Sie einfach die Zahl "1" und nehmen Sie an, dass der Bereichsanfang 0 und das Bereichsende 2^(200-8*Anzahl_von_1) ist, da wir nur 200 Bits für die Proto-Adresse und einige davon haben muss im Fall unseres 111(1)-ähnlichen Musters auf Null gesetzt werden.

Wenn wir ein Muster wie 11(1)X(X) haben, wobei X ein Nicht-Null-Symbol ist, kürzen Sie einfach die maximal mögliche Proto-Adresse durch die Anzahl der Bytes gleich der Anzahl der Einsen und führen Sie normale Berechnungen durch.

Hier ist meine Lösung, die für die meisten Fälle gut funktioniert, außer dass sie nur 1-s und sehr lange Präfixe enthält:

function complexityForBtcAddressPrefixWithLength(bytes prefix, uint length) public pure returns(uint) {
    require(prefix.length >= length);

    uint8[128] memory unbase58 = [
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 
        255, 0, 1, 2, 3, 4, 5, 6, 7, 8, 255, 255, 255, 255, 255, 255, 
        255, 9, 10, 11, 12, 13, 14, 15, 16, 255, 17, 18, 19, 20, 21, 255, 
        22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 255, 255, 255, 255, 255,
        255, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 255, 44, 45, 46,
        47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 255, 255, 255, 255, 255
    ];

    uint leadingOnes = countBtcAddressLeadingOnes(prefix, length);

    uint256 prefixValue = 0;
    uint256 prefix1 = 1;
    for (uint i = 0; i < length; i++) {
        uint index = uint(prefix[i]);
        require(index != 255);
        prefixValue = prefixValue * 58 + unbase58[index];
        prefix1 *= 58;
    }

    uint256 top = (uint256(1) << (200 - 8*leadingOnes));
    uint256 total = 0;
    uint256 prefixMin = prefixValue;
    uint256 diff = 0;
    for (uint digits = 1; prefix1/58 < (1 << 192); digits++) {
        prefix1 *= 58;
        prefixMin *= 58;
        prefixValue = prefixValue * 58 + 57;

        diff = 0;
        if (prefixValue >= top) {
            diff += prefixValue - top;
        }
        if (prefixMin < (top >> 8)) {
            diff += (top >> 8) - prefixMin;
        }

        if ((58 ** digits) >= diff) {
            total += (58 ** digits) - diff;
        }
    }

    if (prefixMin == 0) { // if prefix is contains only ones: 111111
        // NEED TO FIX BUG HERE!!!
        total = (58 ** (digits - 1)) - diff;
    }

    return (1 << 192) / total;
}

function countBtcAddressLeadingOnes(bytes prefix, uint length) public pure returns(uint) {
    uint leadingOnes = 1;
    for (uint j = 0; j < length && prefix[j] == 49; j++) {
        leadingOnes = j + 1;
    }
    return leadingOnes;
}

Hier sind meine erfolgreichen Tests:

makeIt('1AAAAA', 259627881);
makeIt('1QLbz6', 259627881);
makeIt('1QLbz7', 837596142);
makeIt('1QLbz8', 15318045009);
makeIt('1aaaaa', 15318045009);
makeIt('1zzzzz', 15318045009);
makeIt('111ABC', 15318045009);
makeIt('1111ZZ', 888446610538);
makeIt('111111X', 50656515217834);

makeIt('1B', 22);
makeIt('1Bi', 1330);
makeIt('1Bit', 77178);
makeIt('1Bitc', 4476342);
makeIt('1Bitco', 259627881);
makeIt('1Bitcoi', 15058417127);
makeIt('1Bitcoin', 873388193410);
makeIt('1BitcoinEater', "573254251836560363813");

Und falsche Tests:

makeIt('111111', 1099511627776);
makeIt('1111111', 281474976710656);
makeIt('1BitcoinEaterAddress', "1265736312036992302053249573170410");

Mit Fehlern:

Contract: VanityBTC should test difficulty for 111111:

  AssertionError: expected '1103823438081' to equal '1099511627776'
  + expected - actual

  -1103823438081
  +1099511627776

Contract: VanityBTC should test difficulty for 1111111:

  AssertionError: expected '282578800148737' to equal '281474976710656'
  + expected - actual

  -282578800148737
  +281474976710656

Contract: VanityBTC should test difficulty for 1BitcoinEaterAddress:

  AssertionError: expected '1.265736312036992302053249062715592e+33' to equal '1.26573631203699230205324957317041e+33'
  + expected - actual

  -1.265736312036992302053249062715592e+33
  +1.26573631203699230205324957317041e+33