¿En qué clase de complejidad se encuentra la prueba de trabajo (hashcash) de Bitcoin?

Para formular esta pregunta con precisión, definiré una hipotética función hash "perfecta" idealizada H (n) que tiene buenas propiedades de escalabilidad, y formularé un problema PERFECT HASHCASH en términos de eso, entendiendo que las consideraciones prácticas pueden terminar dando solo una aproximación de este ideal.

Para simplificar, diremos que nuestra función hash H(n) toma como entrada un solo número natural n. Entonces decimos que H(n) es una función hash perfecta si y sólo si:

  1. H(n) asigna cada número natural a una secuencia binaria infinita, cuya complejidad temporal para calcular cualquier segmento inicial s es polinomial en el tamaño de n y s (lo que la convierte en una función de esponja ).
  2. Para cualquier segmento inicial de longitud d, el conjunto de todos los números naturales n tales que H(n) comparte ese segmento inicial tiene densidad natural = 1/(2^d).

Lo primero formaliza la escalabilidad de nuestra función, y lo segundo formaliza la idea de que queremos que todos los hashes aparezcan aproximadamente "con la misma frecuencia" como salida. Aparte de eso, nuestra función hash perfecta es una caja negra, y no nos importa mucho cómo funciona exactamente, siempre que cumpla con las propiedades anteriores, así como con los deseos habituales que se aplican a las funciones hash (fáciles de calcular, difíciles de invertir, colisiones difíciles de encontrar, etc.).

Partiendo del supuesto de que existe una función hash perfecta, ahora podemos definir el problema HASHCASH PERFECTO de la siguiente manera: HASHCASH PERFECTO toma como entrada una función hash perfecta H, un número natural n y un vector de ceros 0^d de longitud d , que puede considerarse como una representación unaria de d. Una solución para el HASHCASH PERFECTO consiste en una n y una d tal que H(n) comienza con 0^d.

Dadas esas entradas, está claro que PERFECT HASHCASH está en la clase de complejidad TFNP , ya que este es un problema de función y se garantiza que existe una solución.

¿Podemos también identificar PERFECT HASHCASH como miembro de cualquier clase de complejidad más fina que TFNP?

¿Podría ser tal vez en PPP ? ¿ PPA ? PPAD ? ¿Algo más?

Para obtener información detallada, consulte Clase de complejidad en Wikipedia.

EDITAR : la pregunta anterior se ha revisado, ya que en la forma en que la formulé originalmente supuse que SHA256 es lo que ahora llamo una función hash perfecta. Muchas personas han notado en los comentarios que esto puede no ser cierto, por lo que en lugar de poner el énfasis en esta pregunta sobre si SHA256 tiene específicamente las buenas propiedades de escala que queremos, definí una función hash idealizada que esperamos que SHA256 al menos se aproxime lo suficientemente bien. para propósitos del mundo real, y reformuló la pregunta en términos de eso.

Como nota final para aclarar cualquier posible confusión, para hacer que el HASHCASH PERFECTO se asemeje al Hashcash real, tendríamos que hacer una suposición más: que existe alguna forma de comenzar con un bloque de datos (un correo electrónico, un bloque de Bitcoin, etc. ) y de alguna manera derivar una función hash perfecta característica de eso, tal vez "salando" una función hash perfecta diferente de manera que el resultado sea también otra función hash perfecta. Entonces, en el caso de un "Bitcoin perfecto", todos los mineros en la red de bitcoin estarían trabajando con sus propias funciones únicas de hash perfectas H'(n) que de alguna manera están vinculadas al bloque en el que están trabajando, y cada minero simplemente probarían H'(0), H'(1), H'(2), ... en orden hasta que encuentren algo que comience con suficientes 0. Cada H' sería una entrada diferente a PERFECT HASHCASH.

+1 aunque no todos en este sitio son criptógrafos; puede ser beneficioso describir los acrónimos (FNP, TFNP, etc.) o preguntar en crypto.stackoverflow.com
Creo que es responsabilidad del autor de la pregunta hacer que su pregunta sea comprensible para los expertos potenciales que respondan la pregunta, no debería ser necesario proporcionar toda la información de fondo en cada pregunta, inflaría demasiado las preguntas.
polinomio en que valor? ¿Qué está jugando el papel del tamaño de entrada aquí?
Nat: Dificultad.
El principio del casillero garantiza que hay un número infinito de soluciones para alguna x. No garantiza un número infinito de soluciones para cada x; no estoy seguro de que podamos refutar que haya alguna x para la que no haya solución.
No estoy seguro de que tenga sentido considerar la dificultad (o su registro) como tamaño de entrada. En particular, porque si la función hash se fija como SHA-256, los valores de dificultad superiores a 2^256 no tienen sentido, por lo que no se puede hablar de asintótica.
@MeniRosenfeld El pp garantiza que hay soluciones (más de cero, pero no infinitamente muchas, lo que es imposible para un tamaño de entrada discreto finito). El tamaño de entrada correcto desde el punto de vista de la complejidad debería ser el número de bits en x e y. Pero, para ser descuidado, en la práctica será esencialmente el número de bits en la salida de la función hash --- menos traería problemas para la existencia de una solución en dificultad extrema, más presumiblemente (!) se convertiría rápidamente en innecesariamente muchos .
@pyramids: El pp garantiza que hay una solución para algunos x. No para cada x.
Muchas de las preguntas aquí son específicas de las limitaciones del mundo real del uso de SHA-256, por lo que revisé la pregunta para considerar una función hash perfecta idealizada que escala perfectamente y que esperamos que SHA-256 al menos se aproxime decentemente en situaciones del mundo real. .
@MeniRosenfeld Estoy corregido, pero de nuevo ya dijiste la parte "para alguna x"; mi punto era solo que "número infinito" era incorrecto, no quise disputar la parte "para alguna x". Supongo que nos tomó a ambos encontrar (con suerte) todos los errores en su declaración.
@MikeBattaglia Vi tus cambios. Veré si puedo encontrar tiempo para ello más tarde, pero supongo que todo lo que podré hacer es (probablemente) estar de acuerdo en que cambió la pregunta de modo que gran parte de mi respuesta ya no se aplica. Lo cual me temo que no te ayudará con el problema central.
@pyramids: Mis comentarios fueron una respuesta al OP. El OP dijo que hay infinitas imágenes previas, lo que resulta del hecho de que la cadena de entrada a SHA-256 puede ser arbitrariamente larga (no se limita a ningún tamaño de entrada en particular). Esto es cierto y solo impugné la parte "para todo x". El OP luego dijo que el tamaño de entrada es difícil, lo que dije no tiene sentido. No veo errores en mi declaración, así que espero una disculpa por su comentario irrespetuoso y por no seguir la conversación.
@MeniRosenfeld: Lamento leer que no está satisfecho con mis comentarios. Solo intento ayudar en el problema, no seguir órdenes o ilusiones del tipo "No veo errores, así que no debe haber ninguno". Si, en cambio, analizáramos el problema, probablemente aprenderíamos cosas nuevas, como que el principio del casillero realmente solo funciona si el rango de entrada y salida tiene el mismo tamaño. Hay algo mal con la combinación de infinitamente muchos y pp aquí, ya sea en su respuesta, en la pregunta previa a la revisión o en algún lugar en la forma en que los combinamos.
@pyramids: le sugiero que lea en.wikipedia.org/wiki/Pigeonhole_principle . El PP definitivamente aplica para conjuntos de diferente tamaño y conjuntos infinitos. En una biyección de un conjunto infinito a un conjunto finito, debe haber un elemento en el rango de salida con un número infinito de preimágenes. Este argumento no tiene sentido: no estás participando en la discusión técnica, ignoras tus propias fallas y me culpas por cosas que no hice. "No veo errores" no significa "no debe haber ninguno", significa que la responsabilidad de encontrar errores es suya si desea hablar de manera irrespetuosa como lo hizo.
@MeniRosenfeld: Wow, tienes razón, esa declaración del principio del casillero tiene una extensión (¡incluso explícitamente!) a la entrada infinita. Pero se vuelve aún más extraño que eso: el que vinculó explícitamente requiere que la entrada sea mayor que la salida, todo lo contrario a la forma en que básicamente se aplica el mismo principio del casillero en el principio del casillero polinomial (PPP), consulte http ://en.wikipedia.org/wiki/PPP_%28complexity%29 , ¡donde la entrada y la salida deben tener exactamente el mismo tamaño!
@pyramids: Está bien. PPP es una lectura interesante con la que no estaba familiarizado anteriormente, pero es un concepto esotérico. A lo que me vinculé es a lo que comúnmente se conoce como el principio del casillero. PPP se llama así por su uso del PP. Tenga en cuenta que una solución para PC es "una preimagen de 0 o dos preimágenes de una salida". El PP garantiza una solución a esto porque si no hay una preimagen de 0, el rango de salida efectivo se reduce en 1 elemento; por lo tanto, hay más valores de entrada que valores de salida, se aplica el PP y hay dos preimágenes para alguna salida.
(PD: donde dije arriba "biyección" debería haber sido solo "función")
@MeniRosenfeld: Sí, exactamente. Estoy de acuerdo con esa explicación. Además, supongo que con esa información probablemente podamos estar de acuerdo en que no hubo malicia o falta de respeto involucrada. Odiaría dejarte sintiéndote agraviado; Simplemente estaba abordando de manera limitada todo en el contexto del PPP (y subclases más finas) específicamente preguntado por el OP, en lugar de una forma más general del PP.
@pyramids: Podemos estar de acuerdo en que hubo malentendidos.

Respuestas (1)

Hay una razón por la cual las funciones hash criptográficas, como el SHA256 doble que se usa para la prueba de trabajo en Bitcoin, generalmente no se describen usando estas clases de complejidad que clasifican el comportamiento asintótico. De hecho, hay varios.

  1. Una razón técnica es que las funciones hash a menudo no escalan. Por ejemplo, no se define cómo se extendería la prueba de trabajo para operar en 512 bits. Entonces, una opción natural sería usar SHA512, pero pasar de SHA256 a SHA512 requiere muchas opciones esencialmente arbitrarias, como cambiar la cantidad de rondas de 64 a 80, que están estandarizadas pero no en una forma de escala natural y no para hash arbitrariamente grande tamaños

  2. No es relevante para el criptógrafo. Incluso una función hash NP completa, que sería la más fuerte entre los casos de complejidad que enumeró para construir un hash fuerte, no garantiza todo lo que queremos de un hash criptográfico o una función de prueba de trabajo. Para calificar para NP-completo es simplemente una fuerte heurística de que el problema no puede resolverse mediante un algoritmo que es, asintóticamente, menos que exponencial. Pero para una buena función hash queremos que sea, en el conteo de bits muy limitado que elegimos para usarla, máximamente exponencial en el sentido de que resolverla es realmente tan difícil como probar todas las posibilidades en una función hash. Para su correspondiente función de prueba de trabajo con tal dificultad que solo una fracción x del rango de salida es aceptable, esto significaría que deberíamos esperar requerir una cantidad de intentos de x/2 veces el tamaño del rango de salida completo para encontrar una prueba de trabajo. Cualquier cosa mejor que eso incitaría a un académico a decir que la función hash asociada está rota, incluso si simplemente reduce el número de intentos a la mitad, lo que aún la colocaría en una clase de complejidad exponencial y sería fácilmente posible incluso con una función NP completa. .

    Un ejemplo impresionante (pero solo superficialmente relacionado) de cómo elegir algo aparentemente NP-completo es insuficiente para obtener algo criptográficamente difícil es la criptografía de mochila. Por supuesto, allí el problema era que al elegir casos especiales se reducía la complejidad del problema. El punto es que incluso un problema NP-completo puede ser menos difícil que tener que probar todas las soluciones, ¡a pesar de que a veces se describe de esa manera! Para una calidad de grado de criptografía, tener que probar cada entrada se entiende literalmente; para el análisis de complejidad, es suficiente si la escala asintótica sigue siendo exponencial en el número de bits. Entonces, si pudiera reducir el problema a otra función NP-completa tomando solo cada 1000 bits como entrada,

  3. ¡Es difícil! Y creo que esta dificultad ya lo ha descarriado: incluso sus argumentos para ubicar este problema en TFNP son, aunque muy cercanos a la verdad, no verdaderos en el sentido matemático. Por ejemplo, si especifico x=0, ninguna y puede producir hash(y) <x, contradiciendo su afirmación. Si todos los demás x están bien o si hay un valor mínimo requerido para x probablemente depende de cómo defina las "cadenas" y en las que desea que opere el hashcash. Para Bitcoin con un número limitado de bits que ingresan al doble-SHA256, no me sorprendería si x=1 tampoco tiene una solución, es decir, si ningún hash de bloque puede volverse exactamente cero. Por supuesto, probablemente nunca lo sabremos. En la práctica, es deseable que una función hash produzca funciones de prueba de trabajo total en la forma que usted describe, pero no creo que sea una calidad comprobada. Descargo de responsabilidad: Sinceramente, no lo sé. Realmente deberías preguntarle a un criptógrafo.

    Lo que queda por hacer para responder a su pregunta, después de encontrar cómo se escala la función hash y verificar que sigue siendo polinomial para tamaños grandes arbitrarios, es solo esta prueba de que la función de prueba de trabajo correspondiente es total. Si esta prueba se puede hacer usando el principio del casillero, has demostrado que está en PPA, etc.

    Entonces, ¿dónde está la dificultad? Por ejemplo, si y tiene al menos tantos bits como x, y si cambiamos su hashcash para que tenga un valor menor o igual en lugar de menor que, y si estamos dispuestos a multiplicarlo aún más hasta el punto de que encontrar una prueba de trabajo o la existencia de una colisión hash es lo suficientemente bueno como para hacer que "hashcash" sea verdadero, entonces obviamente se aplicaría el principio del casillero como se explica en el artículo de wikipedia al que se vinculó.

    Pero cualquier cosa menos que eso, hasta donde puedo ver, no sería suficiente para aplicar el principio del casillero y, por lo tanto, no respondería a la pregunta de si el hashcash está en PPP o no. Para volver a consultar su artículo de wikipedia vinculado: solo para muy pocos problemas, la respuesta es conocida, incluso para PPP. Para los casos especiales de PPP, PPA y PPAD, obviamente se vuelve aún más difícil. Si encuentra una solución, publíquela en una revista académica, ¡no solo aquí!

Haces muchos buenos puntos. Algunos de ellos profundizan en la formulación de mi pregunta más que en el espíritu de la misma, por lo que reformulé la pregunta en términos de una "función hash perfecta" idealizada para la cual todos los hash ocurren con la misma frecuencia y que escala perfectamente. Estaba asumiendo que SHA256 es una función hash perfecta, pero si no lo es, entonces estoy interesado en la situación en la que se usa una función hash perfecta. Creo que eso aborda su punto técnico 1. (continuación)
Creo que mi reformulación también aborda su punto 2, ya que para que exista alguna debilidad como la que menciona, tendría que afectar cada función hash perfecta para hacer una declaración general sobre todo el problema PERFECT HASHCASH en general. Finalmente, creo que mi formación más rigurosa también aborda su punto #3. Notará que lo formulé en términos de que una cantidad de bits iniciales son 0 en lugar de que la cosa sea menos que un objetivo solo para mantenerlo simple, pero generalizarlo al enfoque basado en el objetivo también es sencillo si lo desea.
@MikeBattaglia Estoy de acuerdo en que ha resuelto muchos de los tecnicismos. Sin embargo, queda algo problemático que puede ser más que un simple tecnicismo: el principio del casillero en la raíz de las clases de complejidad más finas a las que espera llegar es esencialmente un argumento de conteo. Por lo tanto, funciona para problemas en los que puede decir "o golpeo (en un lado) el objetivo o encuentro una colisión". Dado que encontrar una colisión no resolverá su (perfecto) problema de hashcash, es posible que no sea posible aplicar el principio del casillero. Al menos yo no pude.
pirámides: eso es lo que estoy pensando, aunque no estaba seguro de si podría existir alguna forma más loca y complicada de reducirlo a algo en PPP. Pero supongo que si PPP está fuera, entonces eso también descarta PPAD y PPA, ya que están en PPP.
¿En qué clase de complejidad se encuentra la prueba de trabajo (hashcash) de Bitcoin?
RespuestasAquíPolítica de privacidad1y, 0v