Post
Topic
Board Español (Spanish)
Re: Sobre las COLISIONES. Empiezo a preocuparme de que me preocupe en unos años?
by
Nubarius
on 05/08/2015, 17:04:37 UTC
SUPERANTONIO, creo que tiene razón lukyforvar. Estás mezclando el ataque de colisiones con lo que sería simplemente la búsqueda de direcciones concretas. Los tiempos que mencionas al principio se refieren al ataque de colisiones y no los puedes dividir por el número de direcciones conocidas.

Voy a intentar explicar la situación tal como yo la entiendo.

El número de direcciones posibles Bitcoin es 2160, que corresponden a los números enteros entre 0 y 2160 - 1, que son las posibles imágenes de la función hash RIPEMD-160.

Haré dos suposiciones importantes (válidas a día de hoy):

1) RIPEMD-160 es una buena función hash, en el sentido de que arroja resultados que se distribuyen como si se tratara de una lotería perfecta entre los 2160 valores posibles.

2) Disponemos solamente de algoritmos de búsqueda clásicos (es decir, no disponemos de un ordenador cuántico capaz de ejecutar el algoritmo de Grover).

Bajo estas hipótesis, podemos tratar el problema como si se tratara de un problema de extracción de bolas numeradas de una urna. Supongamos entonces que tenemos 2160 bolas en una urna y vamos extrayendo una bola (con reposición) hasta encontrar la que tiene el número que buscamos. Entonces tendremos que hacer un número de extracciones del orden de magnitud de 2160 para que la probabilidad de encontrar la bola buscada sea muy alta. Recordemos que 2160 es un número enorme (más de un "octillón", en la escala larga española), del orden de magnitud de la cantidad de átomos de la Luna.

Supongamos ahora que en lugar de buscar una única bola concreta hay más de un millón de bolas que nos sirven. Para hacer fáciles los cálculos, supongamos que son 220 (1.048.576) el número de bolas que nos sirven. Entonces, el número de extracciones necesario será mucho más bajo: 2160/220. Pero, ojo, esto todavía son 2140 operaciones, un número que sigue siendo enorme (más de un septillón español).

Pero un problema diferente es el de ir extrayendo bolas hasta que salgan dos iguales, sin importarnos cuál sea su número. Esto es lo que se conoce como "ataque del cumpleaños" (por la llamada paradoja del cumpleaños, el hecho antiintuitivo de que en todo grupo humano a partir de 23 personas lo más probable es que haya al menos dos personas con el mismo cumpleaños). En ese tipo de ataque, el exponente se reduce a la mitad. Para 2160 bolas posibles bastaría, para encontrar dos bolas de igual número, con llevar a cabo alrededor de 280 operaciones.

Es este último número, 280 (más de un cuatrillón español), el que se ha utilizado para las estimaciones temporales de "11.700 millones de años" del artículo de elbitcoin.org. El error en tu argumento, SUPERANTONIO, creo que está aquí. Es como si hubieras dividido 280 por 220, lo que te daría un valor ciertamente preocupante. Pero lo correcto, salvo que haya algo que se me escape, sería utilizar 220 como divisor de las 2160 operaciones de la búsqueda por fuerza bruta. Por eso, el intento de encontrar una de entre 1.200.000 direcciones con saldo requeriría muchísimo más tiempo que esos 11.700 millones de años o 100.000 años. Si no me he equivocado, tendrías que multiplicar esos tiempos por 260 (2140/280) en lugar de dividir por 220.