Historia de los desafios/rompecabezas de bitcoin.Especificamente los que nacieron con la TX
08389f34c98c606322740c0be6a7125d9860bb8d5cb182c02f98461e5fa6cd15El 15 de Enero del 2015 una transacción fue realizada con un solo input hacia 256 output con UXTOS secuenciales de 0.001 BTC hasta 0.256 BTC.
La dirección que recibió 0.001 BTC es 1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH la cual pertenece al Punto generador de la Curva Elíptica Secp256k1 llave privada numero 1
Alguien pensó que las demás direcciones estaban de cierta forma ordenadas de alguna forma y comenzaron a ir resolviendo los rompecabezas de menor denominación.
El único patrón discernible que se consiguió en su momento fue que cada dirección se encontraba en un rango de bit específico, es decir que la dificultad para resolver cada dirección crecía exponencialmente
Nota que se le llamaron rompecabezas ya que se pensaba que tenían algún orden o manera de resolverse ya sea mediante regresión lineal o alguna otro patrón oculto, sin embargo ahora se sabe que son desafíos.
Durante el transcurso del año 2017 un usuario en bitcointalk, apuntó que el rompecabezas era bastante extraño ya que si se trataba de resolver direcciones solo por fuerza bruta las direcciones arriba de 160 bits no tenían sentido dado que la seguridad de las direcciones esta limitada por el hash rmd160 ya que si en teoria tienes el poder de cómputo para resolver una dirección de 160 bits, realmente serias capaz de encontrar cualquier dirección.
En este momento el autor del desafío/rompecabezas sale a luz y publica su primer y único mensaje en el foro bajo el usuario de
saatoshi_rising indicando que es un desafío realizado llaves privadas aleatorias confirmando que cada llave está en un rango de bit diferente. Asimismo indico que movería los balances de los desafíos del 161 al 256, asi como también incrementar los desafíos no resueltos en un factor de 10
This puzzle is very strange. If it's for measuring the world's brute forcing capacity, 161-256 are just a waste (RIPEMD160 entropy is filled by 160, and by all of P2PKH Bitcoin). The puzzle creator could improve the puzzle's utility without bringing in any extra funds from outside - just spend 161-256 across to the unsolved portion 51-160, and roughly treble the puzzle's content density.
If on the other hand there's a pattern to find... well... that's awfully open-ended... can we have a hint or two?
I am the creator.
You are quite right, 161-256 are silly. I honestly just did not think of this. What is especially embarrassing, is this did not occur to me once, in two years. By way of excuse, I was not really thinking much about the puzzle at all.
I will make up for two years of stupidity. I will spend from 161-256 to the unsolved parts, as you suggest. In addition, I intend to add further funds. My aim is to boost the density by a factor of 10, from 0.001*length(key) to 0.01*length(key). Probably in the next few weeks. At any rate, when I next have an extended period of quiet and calm, to construct the new transaction carefully.
A few words about the puzzle. There is no pattern. It is just consecutive keys from a deterministic wallet (masked with leading 000...0001 to set difficulty). It is simply a crude measuring instrument, of the cracking strength of the community.
Finally, I wish to express appreciation of the efforts of all developers of new cracking tools and technology. The "large bitcoin collider" is especially innovative and interesting!
Se sabe que si es el autor del desafio ya que el incremento que el menciono si sucedio TX:
5d45587cfd1d5b0fb826805541da7d94c61fe432259e68ee26f4a04544384164En el año 2019 otro movimiento que el autor realizó fue liberar las llaves públicas de los desafíos no resueltos que terminaban en 5 y 0 es decir desafios 65, 70, 75, … 160.
TX:
17e4e323cfbc68d7f0071cad09364e8193eedf8fefbcbd8a21b4b65717a4b3d3Tras este ultimo cambio varios de esos desafios fueron resuletos inmediatemente o en los dias posteriores.
Para este momento tenemos 2 tipos de desafíos:
-Los que solo se conoce su dirección, de los cuales solo se ha resuleto hasta el desafio de 64 bits, Sigiente en la lista es el de 66 bits
-Los que tienen también llave pública disponible, de estos solo se ha resuelto hasta el desafio 125, siguiente en la lista es el de 130 bits
Recientemente este año, los desafíos no resueltos hasta el momento fueron incrementados una vez mas en un factor de 10.
https://mempool.space/tx/12f34b58b04dfb0233ce889f674781c0e0c7ba95482cca469125af41a78d13b3Asi ahora el desafío de 66 bits tiene 6.6 BTC y el desafío de 160 bits tiene 16 BTC
No me he interesado en demasía con anterioridad por los rompecabezas del estilo, por lo que me iría bien conocer la respuesta a algunas preguntas básicas que me surgen (exponiendo mi pleno desconocimiento del asunto de paso):
Q1) ¿Quiénes y por qué motivo montan estos puzles a resolver?
Q2) ¿Alguien ha llegado a resolver alguno históricamente?
Q3) ¿Estamos hablando de obtener la clave privada a partir del conocimiento de la clave pública o de la dirección pública?
Q4) Si Q3 es cierto ¿qué diferencia hay entre intentar resolver un puzle e intentar obtener la clave privada de una dirección con TXs realizadas?
Q5) Entiendo que por BSGS
te refieres a ésto. ¿Puedes explicar los principios fundamentales en términos llanos?
Excelenes preguntas.
R1) Posiblemente satoshi o alguien con la misma filosofia que el, el motivo tal como se cito en el unico mensaje del autor es medir la el poder de computo de la comunidad, posiblemente se trate de medir cuando es tiempo de realizar algun HardFork para otro esquema de cifrado posiblmenente algun cifrado post-cuantico.
R2) La mayoria de los que resolvieron los desafios no lo hicieron publico con Excepcion de JeanLucPons y Zielar que resolvieron los desafios de 90, 95, 100, 105, 110 y 115 bits.
https://en.wikipedia.org/wiki/Discrete_logarithm_recordsOn 16 June 2020, Aleksander Zieniewicz (zielar) and Jean Luc Pons (JeanLucPons) announced the solution of a 114-bit interval elliptic curve discrete logarithm problem on the secp256k1 curve by solving a 114-bit private key in Bitcoin Puzzle Transactions Challenge. To set a new record, they used their own software [39] based on the Pollard Kangaroo on 256x NVIDIA Tesla V100 GPU processor and it took them 13 days. Two weeks earlier - They used the same number of graphics cards to solve a 109-bit interval ECDLP in just 3 days.
R3) Como se comento al principio solo se trataba direcciones sin llave publica expuesta, sin embargo esto cambio cuando se liberaron las llaves publicas en el año 2019.
Entonces ahora tenemos 2 variantes para resolver los desafios, fuerza bruta pura para las direcciones y tenemos kangaroo y BSGS para las llaves publicas.
R4) La diferencia es que en este caso se espera que las llaves privadas esten en un rango menor de bits (Menores a 160) y actualmente estamos atorados con 130 bits.
Sin embargo las llaves de las carteras que no entran en este desafio (Carteraas reales) se espera que esten en un rango de 256 bits La diferencia es abismal ya que crece exponencialmente.
R5) Si ese es, te dejo otro link
Elliptic Curve Cryptography: breaking security and a comparison with RSAAqui va mi explicacion, basicamente se trata de generar una table de datos precalculados, estos datos son las llaves publicas que estan ligadas a las llaves privadas desde 1 hasta N, donde N puede ser un numero cercano a los 4 mil millones o mucho mas, aqui el limite es la cantidad de memoria RAM disponible.
Una vez que ya tienes esta tabla en memoria, el siguiente paso es realizar restas a las llaves publicas objetivo, con el fin de Moverlas del rango esperado al rando de nuestra tabla y comparar si el resultado de la resta se encuentra en nuestra, si esto se cumple es facil calcular el valor de la llave privada.
Ejemplo, digamos que nuestra tabla tiene las llaves publicas del 1 al 1000
Nuestra llave obejtivo es 2048, aqui van las restas y comparaciones
2048 - 0 = 2048, Esta el resultado en nuestra tabla? NO
2048 - 1000 = 1048, Esta el resultado en nuestra tabla? NO
2048 - 2000 = 48, Esta el resultado en nuestra tabla? SI, posicion 48, Calculando la llave privada es 48 + 2000
En el link que pase se encuentra mejor explicado:
Elliptic Curve Cryptography: breaking security and a comparison with RSA
)