¿Se puede transformar cualquier desafío computacional en prueba de trabajo?

La aparente inutilidad de la minería de criptomonedas planteó la cuestión de alternativas útiles, vea estas preguntas en Bitcoin , CST , MO . Me pregunto si existe un algoritmo que pueda convertir prácticamente cualquier desafío computacional (cuya solución se puede verificar eficientemente) en otro desafío \ Psi (\ mathcal C) (que se utiliza para la prueba de trabajo) de tal manera que$\mathcal C$$\Psi(\mathcal C)$

1. La función $\Psi$ es aleatorizada, usando alguna secuencia aleatoria (pública) $r$ .
2. La solución de $\Psi(\mathcal C)$ es típicamente tan duro como la solución de $\mathcal C$ .
3. Si una solución $x$ se encuentra para $\Psi(\mathcal C)$ , y luego una solución de $\Psi^{-1}(x)$ se puede calcular de manera eficiente para el desafío original de $\mathcal C$ .
4. Conocer una solución para $\mathcal C$ no ayuda a encontrar una solución para $\Psi(\mathcal C)$ .

$\;\:\:$4 '(Actualización). Como señaló Noah en un comentario, la condición previa debe fortalecerse para requerir que el preprocesamiento $\mathcal C$ tampoco dé ninguna ventaja en la resolución de $\Psi(\mathcal C)$ .

Esta última condición es necesaria para que nadie se puede poner en una posición ventajosa simplemente porque saben que una solución de $\mathcal C$ . Usando este método, las personas pueden presentar problemas computacionales que desean que se resuelvan y una autoridad central puede elegir algunos que sean dignos de resolver (como encontrar extraterrestres versus romper contraseñas). Tenga en cuenta que no parece ser un problema si el problema tarda incluso una semana en resolverse (supongo que esos alienígenas no pueden ser tan buenos para esconderse;), ya que esto podría resultar en una recompensa más grande por una solución. De todos modos, estos temas no están relacionados con la solución de mi problema teórico, pero por supuesto estoy feliz de discutirlos en los comentarios / en el foro.

Una posible solución sería la siguiente: $\Psi$ asigna $\mathcal C$ en $(\mathcal C,HASH_r)$ , es decir, para resolver $\mathcal C$ y algún otro desafío computacionalmente difícil. Un problema con esto es que conocer una solución a $\mathcal C$ hace que resolver $\Psi(\mathcal C)$ sea ​​algo más fácil (cuánto más fácil depende de la dificultad de $HASH_r$ ). Otra cuestión es que $\Psi(\mathcal C)$ se hizo más difícil de lo que $\mathcal C$ .

( Nota : Andreas Björklund sugirió una solución en los comentarios que creo que es mejor que la que se describe a continuación. Ver http://eprint.iacr.org/2017/203 , por Ball, Rosen, Sabin y Vasudevan. En resumen, dan pruebas de trabajo basadas en problemas como vectores ortogonales cuya dureza se entiende bien y a los que muchos problemas (p. ej., k-SAT) se pueden reducir de manera relativamente eficiente. Su instancia PoW es tan difícil como los vectores ortogonales en el peor de los casos, incluso si la instancia de entrada es fácil, de modo que eviten un inconveniente importante de la solución que se describe a continuación.Ψ ( C ) $\Psi(\mathcal{C})$$\mathcal{C}$

La solución que se describe a continuación podría beneficiarse de su simplicidad, se puede describir a un no experto, pero me parece mucho menos interesante en teoría.

Una solución es posible si uno asume que "el algoritmo más rápido para está fundamentalmente aleatorizado" (y si modelamos una función criptográfica hash como un oráculo aleatorio). Una forma de formalizar esto es decir que$\mathcal{C}$

1. $\mathcal{C} \in \mathsf{TFNP} \setminus \mathsf{FP}$ (de lo contrario, supongo que no es realmente un desafío válido);
2. el algoritmo aleatorio más rápido para ejecuta en el tiempo esperado en una instancia típica; yC$\mathcal{C}$$T$
3. existe una función eficientemente computable desde hasta el dominio de soluciones a para manera que siempre exista una con una solución a .f { 0 , 1 } k C k ≈ log 2 T s ∈ { 0 , 1 } k f ( s ) $f$$\{0,1\}^k$$\mathcal{C}$$k \approx \log_2 T$$s \in \{0,1\}^k$$f(s)$$\mathcal{C}$

Observe que la suposición de que implica que la búsqueda de fuerza bruta de es esencialmente el algoritmo óptimo para . Entonces, esta es una suposición bastante fuerte. Por otro lado, si no satisface estas propiedades, entonces es difícil para mí imaginar que satisface sus condiciones (2) y (4).k ≈ log 2 T { 0 , 1 } k C $k \approx \log_2 T$$\{0,1\}^k$$\mathcal{C}$$\mathcal{C}$

Luego, dada una función hash , que como un oráculo aleatorio, definimos como sigue, donde para algunos es la entrada aleatoria de . El objetivo es generar modo que sea ​​una solución para . En otras palabras, debería ser hash a "buenas monedas aleatorias" para el algoritmo anterior.H : { 0 , 1 } ∗ → { 0 , 1 } k Ψ H ( C ; r ) r ∈ { 0 , 1 } ℓ ℓ ≫ k Ψ H x ∈ { $H : \{0,1\}^* \to \{0,1\}^k$$\Psi_H(\mathcal{C}; r)$$r \in \{0,1\}^\ell$$\ell \gg k$$\Psi_H$ , 1 } ∗ f ( H ( r , x ) ) C ( r , x $x \in \{0,1\}^*$$f(H(r,x))$$\mathcal{C}$$(r,x)$

Veamos que esto satisface todas sus condiciones.

1. "La función es aleatorizada, usando alguna secuencia aleatoria (pública) ". ¡Cheque!Ψ $\Psi$$r$
2. "Resolver suele ser tan difícil como resolver ". Observe que el algoritmo aleatorio simple para ejecuta en el tiempo esperado como máximo más la sobrecarga polinómica, y suponiendo que es esencialmente el tiempo de ejecución del algoritmo óptimo para .$\Psi(\mathcal{C})$ C Ψ H ( C , r ) 2 k 2 k ≈ T $\mathcal{C}$$\Psi_H(\mathcal{C},r)$$2^k$$2^k \approx T$$\mathcal{C}$
3. "Si se encuentra una solución para , entonces se puede calcular eficientemente una solución para el desafío original ". Esto se puede hacer calculando , que es una solución a por suposición.x Ψ ( C$x$$\Psi(\mathcal{C})$ Ψ - 1 ( x ) C f ( H ( r , x ) ) $\Psi^{-1}(x)$$\mathcal{C}$$f(H(r,x))$$\mathcal{C}$
4. "Conocer una solución para no ayuda a encontrar una solución para ". Por definición, resolver requiere encontrar tal que sea ​​una solución para . Dado que modelamos como un oráculo aleatorio, podemos reducir el tiempo de ejecución esperado de cualquier algoritmo que resuelva este problema mediante la complejidad óptima de consulta esperada del problema de consulta en el que está dado por un cuadro negro y se nos pide encontrar un Solución al mismo problema. Y, de nuevo porque es un oráculo aleatorio, la complejidad de la consulta esperada es solo la inversa de la fracción de elementosC Ψ ( C ) Ψ H ( C ; r ) x f ( H ( r , x ) ) C H H H x ∈ { 0 , 1 } k C T ≈ 2 k 2 - k ℓ ≫ k r ∈ { 0 , 1 } ℓ H C r $\mathcal{C}$$\Psi(\mathcal{C})$$\Psi_H(\mathcal{C}; r)$$x$$f(H(r,x))$$\mathcal{C}$$H$$H$$H$$x \in \{0,1\}^k$ que son soluciones (hasta un factor constante). Por supuesto, el tiempo de ejecución óptimo esperado de cualquier algoritmo para es , lo que implica que esta fracción no puede ser mucho mayor que . Dado que y se eligen uniformemente al azar, esto es incluso cierto con el preprocesamiento que puede depender de y (pero no ) , y en particular es cierto incluso si conocemos una solución a de antemano.$\mathcal{C}$$T \approx 2^{k}$$2^{-k}$$\ell \gg k$$r \in \{0,1\}^\ell$$H$$\mathcal{C}$$r$$\mathcal{C}$

La siguiente técnica simple que llamo la técnica de lotería de solución (SLT) se puede usar junto con otras técnicas (como tener múltiples problemas de prisioneros de guerra, la técnica mencionada en la respuesta de Noah Stephens-Davidowitz, etc.) para ayudar a transformar los desafíos computacionales en pruebas viables de problemas laborales. El SLT ayuda a mejorar problemas con problemas de minería de criptomonedas que no sean las condiciones 1-4.

Suponga que es un desafío computacional de la forma "encontrar un hash adecuado junto con una cadena tal que ".C k x ( k , x ) ∈ $\mathcal{C}$$k$$x$$(k,x)\in D$

Configuración del problema : suponga que es un conjunto, es una función de cifrado hash y es algo constante. Supongamos además que es una información que es fácil de obtener después de que se determina que pero que no se puede obtener de otra manera.Ψ ( C ) $\Psi(\mathcal{C})$$D$ H C Datos ( k , x ) ( k , x ) ∈ $H$$C$$\textrm{Data}(k,x)$$(k,x)\in D$

Problema objetivo: encontrar un par tal que sea ​​un hash adecuado y donde , y donde .Ψ ( C ) ( k , x ) k ( k , x ) ∈ D H ( k | | x | | Datos ( k , x ) ) < $\Psi(\mathcal{C})$$(k,x)$$k$$(k,x)\in D$$H(k||x||\textrm{Data}(k,x))<C$

Investiguemos ahora cómo el problema satisface los requisitos 1-4.$\Psi(\mathcal{C})$

1. Tenemos que asumir que ya está aleatorizado para que el SLT satisfaga esta propiedad.$\mathcal{C}$

2-3. generalmente se volverá más difícil que y esto es algo bueno. La dificultad de un problema de prueba de trabajo debe ser finamente ajustable, pero el problema original puede o no tener un nivel de dificultad finamente ajustable (recuerde que la dificultad para extraer Bitcoin se ajusta cada dos semanas) . La dificultad del problema es igual a la dificultad de encontrar algo adecuado multiplicado por . Por lo tanto, dado que la constante es finamente ajustable, la dificultad de también es finamente ajustable.Ψ ( C ) C C Ψ ( C ) ( k , x ) ∈ D 2 $\Psi(\mathcal{C})$$\mathcal{C}$$\mathcal{C}$$\Psi(\mathcal{C})$$(k,x)\in D$C CΨ(C$\frac{2^{n}}{C}$$C$$\Psi(\mathcal{C})$

Aunque el problema es más difícil que el problema original , casi todo el trabajo para resolver el problema dedicará simplemente a encontrar un par con lugar de calcular hashes (no se puede calcular si o no hasta que uno ha calculado y uno no puede calcular menos que uno verifique que ).Ψ ( C ) C Ψ ( C ) ( k , x ) ( k , x ) ∈ D H ( k | | x | | Datos ( k , x ) ) < C Datos ( k $\Psi(\mathcal{C})$$\mathcal{C}$$\Psi(\mathcal{C})$$(k,x)$$(k,x)\in D$$H(k||x||\textrm{Data}(k,x))<C$ x ) Datos ( k , x ) Datos ( k , x ) ∈ $\textrm{Data}(k,x)$$\textrm{Data}(k,x)$$\textrm{Data}(k,x)\in D$

Por supuesto, el hecho de que es más difícil que presenta algunas preocupaciones nuevas. Para un problema útil, lo más probable es que uno quiera almacenar los pares donde en alguna base de datos. Sin embargo, para recibir la recompensa de bloque, el minero solo debe revelar un par donde y lugar de todos los pares independientemente de si o no. Una posible solución a este problema es que los mineros simplemente revelen todos los pares dondeΨ ( C ) C ( k , x ) ( k , x ) ∈ D ( k , x ) ( k , x ) ∈ D H ( k | | x | | Datos ( k , x ) $\Psi(\mathcal{C})$$\mathcal{C}$$(k,x)$$(k,x)\in D$$(k,x)$$(k,x)\in D$ < C ( k , x ) ∈ D H ( k | | x | $H(k||x||\textrm{Data}(k,x))<C$$(k,x)\in D$Datos ( k , x ) ) < C ( k , x ) ( k , x ) ∈ D ( k , x ) ∈ D ( k , x ) ∈ D Ψ ( C ) $H(k||x||\textrm{Data}(k,x))<C$$(k,x)$$(k,x)\in D$por cortesía. Los mineros también tendrán la capacidad de rechazar cadenas si los mineros no han publicado su parte justa de los pares . Quizás, uno debería contar el número de pares para el cálculo de quién tiene la cadena válida más larga también. Si la mayoría de los mineros publican sus soluciones, entonces el proceso de resolver producirá tantas soluciones como el proceso de resolver .$(k,x)\in D$$(k,x)\in D$$\Psi(\mathcal{C})$$\mathcal{C}$

En el escenario donde los mineros publican todos los pares , satisfarían el espíritu de las condiciones 2-3.( k , x ) ∈ D Ψ ( C$(k,x)\in D$$\Psi(\mathcal{C})$

4. Ψ ( C ) $\Psi(\mathcal{C})$ puede o no satisfacer la condición dependiendo del problema específico.$4$

$\textbf{Other Advantages of this technique:}$

El SLT ofrece otras ventajas que las condiciones 1-4 que son deseables o necesarias para un problema de prueba de trabajo.

1. Mejora del equilibrio de seguridad / eficiencia: el SLT ayudará en el caso de que sea ​​demasiado fácil de resolver o demasiado difícil de verificar. En general, es mucho más difícil de resolver que , pero es tan fácil de verificar como .C Ψ ( C ) C Ψ ( C ) $\mathcal{C}$$\Psi(\mathcal{C})$$\mathcal{C}$$\Psi(\mathcal{C})$$\mathcal{C}$

2. Eliminación de un problema roto / inseguro: el SLT podría usarse para eliminar algorítmicamente problemas POW malos en una criptomoneda con un problema POW de respaldo y múltiples problemas POW. Suponga que una entidad encuentra un algoritmo muy rápido para resolver el problema . Entonces, tal problema ya no es un problema de prueba de trabajo adecuado y debe eliminarse de la criptomoneda. Por lo tanto, la criptomoneda debe tener un algoritmo que elimine de la criptomoneda cada vez que alguien haya publicado un algoritmo que resuelva el problema demasiado rápido pero que nunca elimina el problema contrario. Aquí hay un resumen de un algoritmo de eliminación de este tipo de problemas que se utiliza para eliminar un problema que llamaremos ProblemaC C C C$\mathcal{C}$$\mathcal{C}$$\mathcal{C}$$\mathcal{C}$$A$ .

a. Alice paga una tarifa grande (la tarifa cubrirá los costos en que incurren los mineros para verificar el algoritmo) y luego publica el algoritmo que llamaremos Algoritmo K que divide el Problema en la cadena de bloques. Si el algoritmo K se basa en una gran cantidad de datos , entonces Alice publica la raíz de Merkle de esta datos .A P C P $A$$PC$$PC$

si. Las instancias aleatorias del problema A son producidas por Blockchain. Luego, Alice publica las porciones de los datos precalculados que son necesarios para que el Algoritmo K funcione correctamente junto con su rama Merkle para demostrar que los datos realmente provienen de la . Si el algoritmo de Alice se alimentó rápidamente con la datos , entonces el problema se elimina y Alice recibe una recompensa por publicar el algoritmo que elimina el problema de la cadena de bloques.P C P $PC$$PC$

Este procedimiento de eliminación de problemas es computacionalmente costoso para los mineros y validadores. Sin embargo, el SLT elimina la mayor parte de la dificultad computacional de esta técnica para que pueda usarse si es necesario en una criptomoneda (los casos en que se usa esta técnica probablemente serán bastante raros).

3. Los grupos mineros son más factibles: en las criptomonedas, a menudo es muy difícil ganar la recompensa en bloque. Dado que las recompensas en bloque son muy difíciles de ganar, los mineros a menudo explotan en cosas llamadas grupos mineros en los que los mineros combinan sus recursos para resolver un problema y en los que comparten la recompensa en bloque en proporción a la cantidad de "casi accidentes" que han encontrado . Un posible problema para es que puede ser difícil producir una noción cualitativa de lo que constituye una "falta cercana" para el problema y el algoritmo para encontrar una falta cercana puede ser diferente del algoritmo para resolver . Dado que los mineros de la piscina buscarán casi accidentes, pueden no ser muy eficientes para resolverC C C C Ψ ( C ) ( k , x ) ( k , x ) ∈ D H ( k | | x | | Datos ( k , x ) ) ≥ C Ψ ( C ) Ψ ( C$\mathcal{C}$$\mathcal{C}$$\mathcal{C}$$\mathcal{C}$ (y, por lo tanto, pocas personas se unirán a grupos de minería). Sin embargo, para , hay una noción clara de una falta cercana, a saber, una falta cercana es un par donde pero donde , y el algoritmo para encontrar casi errores para será el mismo que el algoritmo para encontrar soluciones a .$\Psi(\mathcal{C})$$(k,x)$$(k,x)\in D$$H(k||x||\textrm{Data}(k,x))\geq C$$\Psi(\mathcal{C})$$\Psi(\mathcal{C})$

4. Libertad de progreso: se dice que un problema de prueba de trabajo está libre de progreso si la cantidad de tiempo que le toma a una entidad o grupo de entidades encontrar el siguiente bloque en la cadena de bloques sigue la distribución exponencial donde la constante es directamente proporcional a la cantidad de potencia computacional que entidad está usando para resolver el Problema . Se requiere libertad de progreso para los problemas de minería de criptomonedas para que los mineros reciban una recompensa en bloque en proporción a su poder minero para lograr la descentralización. El SLT ciertamente ayuda a los problemas mineros a lograr la libertad de progreso.P e - λ x λ $P$$e^{-\lambda x}$$\lambda$$P$