¿Cómo puedo probar `sha256^1000000000(X) = Y` para un verificador que no puede realizar tantos cálculos?

Supongamos, por ejemplo, que quiero escribir un contrato de Ethereum que paga 1 ETH para quien me dé la respuesta correcta a sha256^1000000000("good boy"). Esa cantidad de cómputo sería mucho más alta que el límite de gas de Ethereum, por lo que necesito una forma de probar sha256^1000000000("good boy") = Ysin necesitar tanta potencia de cómputo por parte del verificador.

¿Cómo se puede hacer eso?

(Esa es una versión más débil de mi pregunta anterior, que no obtuvo buenas respuestas. ¿Ojalá este problema sea más simple?)

No puede verificar un hash iterado más rápido. Puede calcular previamente el resultado fuera de línea y almacenar el hash del resultado esperado ( sha256(“str”)^.1000001). Tal vez podríamos recomendar un método mejor si nos dice el problema real que desea resolver. Si este es un escenario de prueba de trabajo, use un método asimétrico como, por ejemplo, el PoW que usa bitcoin (deme un nonce que junto con mi desafío genera un hash que es más pequeño que una dificultad definida)
@eckes No es muy diferente de lo que respondí , ¿verdad?
@e-sushi sí, sin embargo, para almacenar públicamente un verificador (los contratos son ejecutables), debe usar un resultado después de las iteraciones esperadas (exponente más grande) No antes. De lo contrario, podrían comenzar desde allí.
@eckes Erm, ¿qué? Ese resultado de verificación pública que asumes podría ser una cosa de Ethereum, lo que estaría fuera de tema aquí y más algo para Ethereum.SE. Como estamos en Crypto.SE, asumí que el verificador no almacena el resultado SHA-256 (verificación) "al aire libre". Esto no se describió en la pregunta ni se preguntó. Entonces, lógicamente asumí que el verificador mantiene el resultado de la verificación en secreto hasta que un remitente calculador envíe el resultado hash correcto y coincidente. Lo que describe presenta un problema de seguridad diferente, completamente ajeno al hash de una cadena millones o miles de millones de veces.
El operador solicita un contrato de Ethereum para hacerlo. Y esos son públicos.
@eckes En ese caso, lo migraré al sitio adecuado: Ethereum.SE

Respuestas (2)

Eso será casi imposible de atajar debido a la simple razón de que SHA-256 es un hash criptográficamente seguro y no ofrece una forma de hacerlo sin hacer los cálculos reales.

Además, no hay debilidades conocidas en SHA-256 que nos permitan manejar esto. Si lo hubiera, SHA-256 estaría roto y definitivamente ya no sería criptográficamente seguro.

La única solución sería tener un conocimiento previo de una parte verificada del cálculo; por ejemplo, $\text{SHA256}^{987654321} = X$, por lo que tiene $X$ como punto de partida que no espera una gran cantidad de cálculos para obtener su $Y$ que llevará más tiempo del que ambos vivimos.

Sin embargo, incluso si alguien ya calculó millones de rondas SHA-256 en la cadena "buen chico", aún tendría que verificar de alguna manera que ese cálculo previo sea correcto y no defectuoso... lo que termina siendo el mismo problema que usted. Probablemente tenga que recalcular las cosas por completo.

Pensándolo por un segundo, su escenario se acerca a una complejidad computacional que podría compararse con la complejidad que asegura algunas cadenas de bloques de criptomonedas como Bitcoin, que utilizan cálculos diferentes, pero que consumen tiempo y recursos en su "Prueba de trabajo".

Por lo tanto, mi sugerencia sería simplemente reducir la complejidad de su $$\text{SHA256("buen chico")}^{1000000000}$$ a algo más usable y alcanzable $$\text{SHA256("buen chico") }^{1000000}$$

Un verificador que no puede realizar tantos cálculos seguirá masticando uno o dos días, pero puede bajar o subir el listón según sus necesidades específicas.

Una cosa debe quedar clara: al usar un hash criptográficamente seguro, no puede verificar más rápido que calcular esto por completo; al igual que el remitente calculador tendrá que calcular completamente el resultado que luego desea verificar. Más recursos computacionales lógicamente darán como resultado un cálculo más rápido... lo que puede o no ser un problema cuando su verificador no tiene los mismos recursos computacionales que la otra parte. Esto es algo que debe recordar y tener en cuenta, dependiendo de cómo y/o dónde quiera usar/implementar su idea.

¿Cómo es eso cierto? La cuestión no es calcular rápido esta función, sino verificar que el cómputo se haya realizado correctamente, en un tiempo menor al requerido para evaluarla. Y sabemos que es factible, con métodos criptográficos, generar pruebas de que un cálculo muy largo conduce a algún resultado, de modo que verificar la prueba lleva mucho menos tiempo que realizar el cálculo. Eso se llama delegación de computación, y un SNARG haría perfectamente el truco, incluso tenemos implementaciones disponibles.
@GeoffroyCouteau LOL, ¿en serio? Ok, estoy abierto a ser corregido. Simplemente dígame el resultado SHA-256 sha256^1000000000("good boy")para que pueda verificar y probar que no es lo que afirmo: 2e115facdd6e12fdb2938b6a0d6662efa2cd92dac6a3c5c94c8784c52a1dd0b5(que es exactamente el problema que OP está preguntando desde que dejó la pregunta en Crypto.SE). Si puede verificar y probar que mi resultado hash no es correcto, con gusto eliminaré mi respuesta. Para su comodidad, esta oferta es válida mientras yo viva. ¡Buena suerte! ;)
@GeoffroyCouteau Mira, estoy de acuerdo en que hay otras soluciones al problema, pero la pregunta se hizo específicamente sobre la verificación de mil millones de cálculos SHA-256 en una cadena. Entonces, mi respuesta se limita a hablar exactamente de eso. Una de las razones por las que moví las preguntas y respuestas aquí es que quedó claro que el autor de la pregunta necesita algo diferente a su idea SHA-256. Como notará, su comentario y respuesta evitan hablar sobre SHA-256 todos juntos y apuntan sin rodeos a otra solución, sin explicar por qué "verificar mil millones de rondas SHA-256" como se describe no es factible en tales escenarios.
También estoy abierto a la corrección, y podría haber entendido mal la pregunta de OP :) Interpreté la siguiente oración: "Necesito una forma de probar sha256 ^ 1000000000 ("buen chico") = Y sin necesitar tanto poder de cómputo en el verificador side" como la siguiente pregunta: el probador, que calcula el hash iterado, necesita una forma de producir una prueba que lo acompañe de que lo hizo correctamente, de modo que la prueba se pueda verificar más rápido que calcular el hash por completo. En mi comprensión del escenario, se vuelve factible, porque el probador está dispuesto a ayudar al verificador en el proceso.
Pero claro, si el probador simplemente te da el resultado y te dice que lo verifiques, sin nada más, no puedes hacer mucho mejor que hacer todo el cálculo. Verificar un cálculo de mil millones de sha256 en una cadena (o, de hecho, cualquier otro tipo de cálculo pesado bien definido) en una pequeña cantidad de tiempo es perfectamente factible si el probador está dispuesto a ayudar, incluso puede hacerlo de forma no interactiva produciendo un breve prueba adjunta, pero de hecho es inviable sin su ayuda.

Vea mi respuesta a su otra pregunta en Cryptography.SE : la solución más simple sería usar un contrato inteligente que realice el algoritmo de verificación de un sistema SNARG para la declaración que desea. El tiempo de verificación puede hacerse esencialmente independiente del tamaño del cálculo, y hay varias implementaciones de SNARG disponibles. El principal problema aquí es para el probador, que no solo necesitaría resolver el acertijo, sino también generar una prueba de que lo resolvió, lo que puede llevar bastante tiempo, pero estás tratando de dificultarle la solución. de todos modos, por lo que probablemente no sea un problema.

¿Cómo puedo probar `sha256^1000000000(X) = Y` para un verificador que no puede realizar tantos cálculos?
RespuestasAquíPolítica de privacidad1y, 0v