Análisis matemático de la probabilidad de encontrar direcciones de vanidad Bitcoin (parte 1 de 2)
Las direcciones bitcoin que se usan con mayor frecuencia al momento de recibir dinero son las direcciones para transacciones P2PKH (Pay to Public Key Hash – Pago a Hash de Clave Pública), las cuales suelen comenzar por el número 1 seguido de un conjunto de caracteres alfanuméricos.
Por ejemplo:
14yKahAMTXdnBzyThRf59LnpS53dLFqSWq
Sin embargo se pueden crear direcciones de vanidad en las cuales las primeras letras forman una palabra o las iniciales de algún nombre por ejemplo:
1Davidi92Y3zTJ5Qm4TdPqBWSk8pgdUGHG
En esta dirección observamos que las 5 primeras letras forman la palabra “David”, estas direcciones suelen usarse para identificar a una institución o persona. El proceso de generación de una dirección de vanidad consiste en probar con miles y hasta millones de claves privadas e ir verificando las direcciones correspondientes hasta encontrar el patrón que corresponda por lo cual básicamente se trata de un cálculo de fuerza bruta computacional, la mayoría de las direcciones de vanidad suelen tener hasta 6 caracteres debido a la gran complejidad de encontrar patrones más largos.
En el presente artículo se analiza la probabilidad de encontrar direcciones de vanidad dependiendo del número de letras presentes en las mismas, también se establece una fórmula para calcular el número de intentos aproximados para tener una probabilidad determinada de éxito.
Nota Aclaratoria: Este análisis parte de la premisa de que el algoritmo HASH160 distribuye las apariciones de cada carácter en las direcciones bitcoin de manera que cada carácter aparezca con la misma frecuencia que todos los otros, lo cual no es estrictamente verdadero pero puede ser usado como una aproximación cercana a la realidad.
Paso 1: Se calcula la probabilidad de encontrar la coincidencia que se busca
Ejemplo: “abiad” no sensible a mayúscula, es decir coincidencias del tipo (“Abiad” , “ABIAD”, “abiad”, “AbiAd”,…).
Para la 1° letra ‘a’ la probabilidad de acertar es 2/58 debido a que hay 2 caracteres que cumplen la coincidencia en base58check (‘a’ y ‘A’), 2 casos favorables de 58 casos posibles. Se aplica el mismo razonamiento para las demás letras, la probabilidad de aparición de las 5 letras se muestra en la siguiente tabla:
Por ser eventos independientes la probabilidad de que aparezcan las 5 letras al mismo tiempo es igual al producto de las probabilidades individuales:
Esto quiere decir que la probabilidad de encontrar la coincidencia “abiad” no sensible a mayúscula es de 1 sobre 41.022.298
Luego la probabilidad de no encontrar dicha coincidencia es de 41.022.297 sobre 41.022.298
Paso 2: se analiza la probabilidad de encontrar la coincidencia en n intentos
Para obtener esta probabilidad se calcula la probabilidad de no encontrar la coincidencia en n intentos y luego la probabilidad inversa es lo que se busca. Llamemos K a la probabilidad de no encontrar la coincidencia en 1 intento
En un sólo intento la probabilidad de no encontrar la coincidencia es:
Por ser eventos independientes en 2 intentos la probabilidad de no encontrar la coincidencia es:
Luego en n intentos
Por lo tanto la probabilidad de encontrar a coincidencia es:
Ahora despejamos n
Calculamos el número de intentos que necesitamos para cada probabilidad recordando que
Según podemos observar en la tabla para tener un 90% de probabilidades de encontrar la dirección de vanidad que comience por las 5 letras del apellido “abiad” sin importar si las letras son mayúsculas o minúsculas necesitamos probar más de 94 millones de claves privadas, lo cual es un número relativamente grande.
Ejemplos de otros patrones de vanidad
1-Patrón: ‘Y’ sensible a mayúsculas (se debe recordar que solo existe un caso posible ‘Y’)
Con solo probar 530 claves privadas tendríamos una probabilidad de 99,99% de encontrar una dirección bitcoin que empiece por la letra ‘Y mayúscula, por lo tanto es relativamente fácil encontrar esta dirección.
2-Patrón: ‘juan’ no sensibles a mayúsculas
Para tener un 90% de probabilidades de encontrar la dirección de vanidad que comience por las 4 letras del nombre “juan” sin importar si las letras son mayúsculas o minúsculas necesitamos probar más de 1,6 millones de claves privadas.
Todo este análisis se basa en la premisa de que el algoritmo HASH160 distribuye las apariciones de cada carácter en las direcciones bitcoin de manera uniforme, lo cual no es estrictamente verdadero como puede apreciarse leyendo el siguiente artículo https://steemit.com/bitcoin/@ydavgonzalez/frecuencia-de-aparicion-de-cada-letra-en-las-direcciones-de-vanidad-bitcoin, sin embargo, estos resultados se usan como una aproximación a la realidad.
Para realizar pruebas generando direcciones de vanidad les comparto el siguiente generador de direcciones de vanidad bitcoin y dogecoin de mi autoría programado en java:
http://www.mediafire.com/file/j85g9sr6voow3v5/CriptoVanity_Beta.jar
Si te ha gustado mi post te invito a compartir tu opinión mediante un comentario y seguirme en mi canal @ydavgonzalez donde publico diversos artículos sobre Criptomonedas, Matemática, Programación y mucho más.
Buen análisis, sigue así.
gracias
Felicitaciones al autor de este post y a todos los que tienen el conocimiento matemàtico suficiente (No es mi caso) para leerlo hasta el final. Upvote.
EXCELENTE POST. MUY INTERESANTE, ARTÍCULO COMO ESTE SON FUNDAMENTALES PARA CRECER EN ESTA COMUNIDAD.