¿La mejor manera de calcular la dificultad de generar una dirección de vanidad específica?

Así que las cosas resultaron ser un poco diferentes. Pero ahora tengo una solución, que parece viable y adecuada. La tarea original era calcular la dificultad de encontrar una dirección de tocador específica (como lo hace vanitygen).

Difícil es básicamente la tasa number_of_all_possible_addresses / number_of_addresses_with_vanity_prefix .

Entonces, por ejemplo, si solo tenemos direcciones de dec entre 0 y 9999, es difícil encontrar una dirección de vanidad, que comienza con "1" será 10, porque 10000 es el número de todas las direcciones posibles y solo las direcciones de 1000 a 1999 coincidirán. , entonces hay 1000 de ellos.

Con las direcciones de bitcoin, las cosas son un poco más complicadas, pero el principio es el mismo.

Primero, averigüemos cómo se forma la dirección de bitcoin: en pocas palabras, hay un par de pasos que son importantes para nuestra tarea:

1. Tome un byte 0x00 (que será el primer byte de la dirección para representar su versión)
2. Tome el resultado de ripemd160 (20 bytes, 160 bits).
3. Tome los primeros cuatro bytes de sha256 (sha256 (ripemd160)) como suma de verificación
4. Concatenar 0x00+ 20 bytes de ripemd + 4 bytes de sha256 de sha256 de ripemd
5. Ahora obtienes algo de 25 bytes de largo que debes tratar como un entero largo. Llamaremos a este número una "proto-dirección".
6. Base58Verifíquelo (pero esto no es muy importante ahora) y el resultado será la dirección de bitcoin.

Sin embargo, lo importante es comprender el hecho de que solo podemos cambiar una parte madura. Eso nos lleva a dos conclusiones: la primera es que solo hay 2^160 direcciones de bitcoin y la segunda es un poco más complicada.

Encontremos la respuesta a una pregunta importante: si A y B son números que comienzan con el mismo dígito y hay una X como A < X < B, ¿significa que X comienza con el mismo dígito? Si A es 1000 y B es 1999, sí lo es. X puede ser cualquier número entre 1001 y 1998. Pero, ¿y si A es 100 y B es 10000? X puede ser cualquier número entre ellos y no debe comenzar con el mismo dígito. Entonces, A, X y B deben tener el mismo dígito al principio solo si tienen el mismo número de dígitos. Téngalo en cuenta, es importante.

Averigüemos qué es la dirección personalizada y qué es la codificación base58.

Base58 es como base16 y base2 y base10 y como cualquier otra base. El símbolo "A", por ejemplo, es "A" en base 58 y 0x09 en base 16 o 9 en base 10. Ese es un buen punto para comenzar.

Decidamos que nuestra dirección comienza con "1A". Sabemos que la dirección es básicamente un número entero de 25 bytes. ¿Qué es "1A"? Es un "1A" en base 58 y 0009 en base 10. O solo 9.

Eso quiere decir que todo número, que se pueda dividir por 58 y tenga un cociente igual a "9" nos dará un símbolo "A" en base 58. Por ejemplo 522/58 == 9. 30276/58/58 == 9. Pero no solo esos números terminarán en 9, sino estos también:

• 9*58 + 58 -1
• 9*58^2 + 58^2 - 1
• 9*58^3 + 58^3 -1
• o simplemente cualquier (9 + 1)*58^N -1 número

Así que la fórmula es para el comienzo del rango:

prefijo*58^n

para el final del rango:

(prefijo + 1)*58^n -1

Aquí viene una idea: debemos encontrar todos los rangos de números que cumplan con esos requisitos:

1. El número al comienzo del rango y el número al final del rango tienen el mismo número de dígitos
2. La longitud de estos números debe ser igual a la longitud de la protodirección. Esto es importante porque debemos tener un número entero de 25 bytes que comience con un byte cero, ¡es la ley!
3. Sus valores deben ser menores a 2^192, porque el byte inicial siempre es 00 y solo tenemos 25 bytes, lo que nos deja solo 24 bytes o 192 bits cuyo valor podemos cambiar.

Cuando encontramos todos estos rangos, podemos encontrar cuántos números hay en el rango simplemente restando el comienzo del rango desde el final del rango. La suma de todas las longitudes de nuestros rangos será la cantidad de protodirecciones posibles que podemos obtener.

Pero, este no es el final. Como recordamos, las protodirecciones son solo todos los números grandes posibles, por lo que no todos se pueden convertir en direcciones de bitcoin válidas. Pero es muy simple calcular cuántos de ellos pueden. La respuesta es 1/256^4. ¿Por qué?

Porque cuando generamos una dirección de bitcoin, todo lo que podemos cambiar es el resultado de ripemd, que nos da 20 bytes. Otros 4 bytes son solo suma de comprobación. Una forma sencilla de pensarlo es que podemos tener 2^192 protodirecciones y solo 2^160 de ellas serán válidas, porque solo podemos tener 2^160 direcciones de bitcoin válidas. Esto nos da una tasa de 1/256^4.

Parte final: tome la suma de todas las longitudes de nuestros rangos, divídala por 256 ^ 4 y este será el número de todas las direcciones de bitcoin posibles con la vanidad dada. Simplemente divide 2^160 por este número y este será el resultado.

Ilustrémoslo encontrando difícil el prefijo A.

A es solo 9. Bien, averigüemos todos los rangos, eso nos dará 9 como cociente. 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

Ambos números tienen una longitud de 24 bytes. Esta es nuestra primera gama. El siguiente es

2420685136029223239542195284264103883950574290397585997824 - 2689650151143581377269105871404559871056193655997317775359

Estos números también tienen una longitud de 24 bytes.

El próximo par será 140399737889694947893447326487318025269133308843059987873792 y 155999708766327719881608140541464472521259232047844430970879

Ambos son más grandes que 2^192, así que ahora debemos detenernos. vamos a resumir nuestros resultados:

46373278467992782366708721920768273638899890620643409919 - 41735950621193504130037849728691446275009901558579068928 + 2689650151143581377269105871404559871056193655997317775359 - 2420685136029223239542195284264103883950574290397585997824 = 273602342961157415963581459332532814469509354661796118526

Esta es la cantidad de protodirecciones posibles que podemos tener. Pero no olvides dividirlo por 156^4 y obtener: 63703009616853067642911677093369144589991624155

Y esta es la cantidad de posibles direcciones de bitcoin que podemos tener. Ahora solo divide 2^160 por este número y el resultado será 22

Esta es la dificultad para el prefijo "A" o "1A". Ahora hablemos de algunos casos especiales. Lo que debes revisar, al trabajar con rangos es:

• longitud _ La longitud del rango debe ser igual a la longitud de la protodirección y debe contar todos los rangos adecuados.
• 2^192. si el final del rango es mayor que 2^192, debe cortar este rango desde la parte superior por un valor de 2^192; la protodirección no puede ser mayor que 2^192. También recuerde que el comienzo del rango debe ser siempre menor que 2^192 (si no, eso no tiene ningún sentido).

¿Qué pasa con los casos especiales? ¿Te gustan los patrones que comienzan con más de un "1"? es un poco complicado, pero no muy complicado. "1" es un caso especial en base58 porque es igual a 0. Eso significa que, cuando hay algunos "1" al principio, todos estos bytes deben ponerse a cero y no pueden usarse. Entonces, nuestra proto-dirección, si queremos comenzar con dos "1", debe tener dos bytes cero al principio. Como 0000XXXX.... si queremos tener 111 debemos dejar 3 bytes como cero bytes al principio y así sucesivamente.

¿Qué significa? Cada 1 cortará un byte de nuestra protodirección, por lo que reducirá la longitud de nuestro número de protodirección más grande posible en 8 bits o en un byte. Eso hará que sea 256 veces más difícil de encontrar y un byte más corto.

Por ejemplo, si queremos tener 11 al principio, solo tendremos 23 bytes para generar nuestros rangos y si queremos tener 1111, solo nos dará 21 bytes. Así que nuestros rangos serán mucho más pequeños y la dificultad será mucho mayor. Y obviamente no es posible encontrar ninguna dirección si tenemos más de 19 "1" en el patrón, porque debemos dejar algo al resultado de ripemd :)

Si el patrón comienza solo con 111, solo cuente el número de "1" y suponga que el comienzo del rango es 0 y el final del rango es 2 ^ (200-8 * número_de_1) porque solo tenemos 200 bits para proto-dirección y algunos de ellos debe ponerse a cero en el caso de nuestro patrón similar al 111(1).

si tenemos un patrón como 11 (1) X (X) donde X es un símbolo distinto de cero, simplemente acorte la proto-dirección máxima posible por un número de bytes igual al número de 1 y realice los cálculos ordinarios.

Aquí está mi solución que funciona bien para la mayoría de los casos, excepto que contiene solo 1-s y prefijos muy largos:

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;
}

Aquí están mis pruebas exitosas:

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");

Y pruebas incorrectas:

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

Con errores:

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