¿Qué problemas computacionales serían buenos problemas de prueba de trabajo para la minería de criptomonedas?

Question

¿Qué matemáticas computacionales problemas que podrían ser utilizados como prueba-de-trabajo problemas para cryptocurrencies? Para hacer esta pregunta más fácil de responder, quiero de prueba de los sistemas de trabajo que funcionan en cryptocurrencies que contienen muchos tipos diferentes de pruebas de los problemas en el trabajo (el uso de diferentes tipos de pruebas-de-los problemas en el trabajo es más seguro que el uso de un solo tipo de prueba-de-trabajo problema) en lugar de la prueba-de-los sistemas de trabajo que funcionan en cryptocurrencies con sólo un tipo de prueba-de-trabajo problema.

De fondo

Para hacer las cosas simples, cryptocurrency la minería requiere uno para resolver problemas computacionales como una prueba-de-trabajo. Por ejemplo, en Bitcoin, los mineros deben encontrar los datos, cuyo algoritmo hash SHA-256 comienza con muchos ceros. Desafortunadamente, las soluciones para la prueba-de-trabajo problema para la mayoría de las cryptocurrencies no tienen ningún valor intrínseco en sí mismos, y estos problemas, el uso de grandes cantidades de recursos y personas incluso han hecho de malware para resolver estos de prueba de los problemas del trabajo.

Los matemáticos tienen una cantidad limitada de recursos computacionales y cryptocurrency que la minería podría potencialmente suministro matemáticos con una casi ilimitada cantidad de potencia de cálculo. Por ejemplo, cryptocurrency mineros recibir el equivalente de millones de dólares en ingresos por día y que pasan mucho potencia computacional de la solución de los problemas requiere de la mina de estas cryptocurrencies.

Requisitos

La mayoría de matemáticas computacionales problemas no son adecuados como prueba-de-trabajo problemas para cryptocurrencies. Aquí están algunos de los requisitos y cosas que nos gustaría en un problema.

1. $\textbf{Verifiable but intractible:}$ El problema debe ser difícil de resolver, pero es fácil de comprobar. Muchos NP-completo los problemas satisfacer este requisito.

2. $\textbf{Tunability:}$ La dificultad de los problemas deben ser finos ajustables. Debe haber un sistema en el lugar que, dado un número real positivo $t$, de manera automática y eficiente selecciona un problema que puede ser resuelto, en promedio, en $t$ segundos sin llegar a resolver el problema. Problemas de optimización pueden ser fácilmente realizados para satisfacer este requisito, ya que con un problema de optimización se puede simplemente elegir la mejor solución cada 5 minutos o así (problemas de optimización puede no ser la mejor para cryptocurrencies, aunque).

3. $\textbf{Intrinsic value:}$ La solución a los problemas que debe tener un valor intrínseco. Estas soluciones y no sólo el proceso de obtención de las soluciones debe ser de un científico, matemático o un interés práctico.

4. $\textbf{Efficient automatic generation:}$ Los problemas deben ser generados automáticamente desde cryptocurrencies en general no tienen las autoridades centrales.

5. $\textbf{Solution tied to block and solver:}$ Por ejemplo, en Bitcoin, la información que se hash, que incluye a la persona a resolver el problema junto con otra información. De esta manera alguien puede robar a alguien de la solución.

Las siguientes características son necesarias sólo si hay uno o un par de tipos de la prueba-de-trabajo problema por cryptocurrency o no hay ningún proceso para quitar automáticamente roto prueba de los problemas del trabajo.

yo. $\textbf{Endless problems:}$ No debe ser una ilimitada cantidad de problemas a resolver, de modo que un nuevo problema que se genera cada pocos minutos.

ii. $\textbf{Unbreakability:}$ A la clase de problemas debe ser "unbreakable". La seguridad de cryptocurrencies depende del hecho de que ninguna de las partes debe tener un secreto algoritmo que resuelve rápidamente los problemas y que ningún cuerpo es propenso a desarrollar un secreto algoritmo en el futuro.

iii. $\textbf{Progress freeness:}$ Cada problema debe ser "el progreso-gratis" en el siguiente sentido. Si Alice trabaja en el problema desde el mediodía y Alice no ha encontrado una solución a las 12:30, luego a las 12:30 Alice va a tener ninguna ventaja sobre otro participante que comienza a trabajar en el problema a las 12:30. En otras palabras, la cantidad de tiempo que se necesita para resolver el problema dado que sigue una distribución exponencial.

iv. $\textbf{Pre-computation resistance:}$(observado por Loreno Heer en los comentarios) La prueba-de-trabajo es un problema que debe ser "pre-cálculo resistente". Una manera de obtener esta propiedad para hacer la prueba-de-trabajo dependiente del problema en datos aleatorios, tales como las transacciones actuales. También se podría hacer problemas en el futuro dependen de soluciones anteriores.

Otros comentarios

Yo soy un poco más interesado en los problemas matemáticos que tenga o pueda tener en el futuro las aplicaciones prácticas en lugar de problemas que sólo son puramente matemáticos de interés. En el mejor de los casos, me gustaría ver los problemas que pueden tener aplicaciones criptográficas.

Esta pregunta difiere de la anterior pregunta ya que la pregunta anterior no pedimos para los problemas que son específicamente la prueba-de-trabajo problemas para cryptocurrency de minería de datos (y las respuestas que se dan no son adecuados como prueba-de-trabajo problemas para cryptocurrency de minería de cualquiera).

Answer 1

Han considerado que la unknotting nudos?

El problema sería encontrar una secuencia de movimientos de Reidemeister para un enlace aleatorio gráfico que lo reduce a la unknot. En algunos casos, ninguna secuencia de existir, pero la mayoría de los grafos aleatorios son conocidos por ser unknotted bajo ciertos nudos de algoritmos: http://iopscience.iop.org/article/10.1088/1751-8113/49/40/405001/meta

Unknotting sí está en NP, como se describe aquí: hay un polinomio de tiempo de algoritmo para desenredar el unknot?

Unknotting tiene muchas aplicaciones en la vida real. Además, dado el potencial de la secuencia de movimientos de Reidemeister que podría unknot el nudo, es muy fácil comprobar que se produce la unknot.

Puede haber algunos problemas con esto (tal vez un secreto algoritmo rápido en las obras?), pero si es así, estoy seguro de que alguien más va a comentar.

Answer 2

El cálculo de la permanente de una pequeña matriz es computacionalmente difícil problema, como se ha discutido aquí, aquí, y aquí. Véase también la Wikipedia el artículo.

Dado un $n \times n$ matriz $A$, un ingenuo cálculo de $\text{perm}(A)$ usando la definición puede exigir $|S_n|=n!$ multiplicaciones. Uno de los mejores algoritmos conocidos es Ryser la fórmula [Rys63], basado en la inclusión-exclusión principio, que requieren $O(2^n n^2)$ de las operaciones aritméticas.

De hecho, incluso de forma determinista la verificación de la declaración de $$k=\text{perm}(A)$$ no puede ser en $\text P$, es decir, no puede ser el polinomio en $n$. Si un idioma se en $\text P$, algunos muy raro declaraciones de complejidad computacional seguiría.

Sin embargo, como se muestra en [LFKN90] y refinado por Babai, existe una prueba interactiva que permite a un armario de $P$ a convencer a un polinomio de tiempo delimitado verificador $V$ de los de arriba, con $O(n)$ pasos de la interacción, si el comprobador fueron capaces de lanzar públicamente un número al azar de las monedas. El [LFKN90] protocolo consiste en el armario de anunciar los coeficientes de los polinomios $f(x)$ correspondiente a permanentes de "menores de edad" de la gráfica dada. El aleatorio de lanzar una moneda se utilizan para generar un elemento $x_i$ de % de $\mathbb{F_p}$ para algunos prime $p>n^4$; el verificador podrá verificar las declaraciones como $f(x_i)=k_i$.

Para aplicar [LKFN90] a un cryptocurrency, el "minero" podría equipararse con el armario de $P$, y el resto de los nodos sería equiparada con los verificadores $V$.

[Mic94] enseñó cómo quitar la interacción en el azar de oracle modelo mediante la aplicación de la Fiat-Shamir heurística para la prueba, la generación aleatoria de la moneda-lanza en una no-forma interactiva. Un cryptocurrency ya tiene un gran número de monedas que están de acuerdo en que al azar, es decir, el merkle raíz de los bloques anteriores.

Como prueba-de-trabajo basado en el cálculo de la permanente, el siguiente protocolo puede ser un punto de partida:

1. Para el bloque $b$, decir $O(1)$ random $0-1$ matrices se agregan a un fondo común. Las matrices pueden ser generados al azar basado en hash de bloques anteriores
2. Los mineros de competir para encontrar una permanente por $d$ matrices en la piscina, donde $d$ es alguna dificultad de destino
3. Una vez encontrado, un minero de la siguiente manera [Mic94] para anunciar su prueba, la salazón de los hash de los bloques anteriores con los coeficientes de la [LFKN90] protocolo para generar el aleatorio de lanzar una moneda utilizada en el protocolo de

El cálculo de los permanentes de matrices aleatorias que pueden tener un valor intrínseco en el bloque de los diseños, los matchings en grafos bipartitos, simétrica tensores, etc. Además, la creación de protocolos para el público de la verificación de la computación es, para mí, una interesante área de investigación – en el ejemplo dado en la literatura es la verificación científica de los cómputos de hecho "en la nube".

Como un aparte, como se enseña en [Kil92] la conversión de un (muy larga) cadena de prueba de $\pi$ en un (breves) compromiso puede ser hecho por la construcción de una merkle-árbol de la cadena de prueba, y el compromiso, es decir, anunciando públicamente, la raíz de la merkle-árbol. La verificación de un determinado bit $\pi_i$ implica "siguiendo el camino" de la hoja a la raíz. Es importante destacar que para un cryptocurrency, no debemos carga el armario demasiado, y siguiente [Kil92] a problemas en $\text{NEXP}$ requiere el minero mantener la muy larga transcripción $\pi$ en la memoria. Trabajo desde finales de los años 90 se ha reducido significativamente la carga en el armario, y tengo la sensación de que hay una sensación de que un verdadero sucinta no interactivo argumento de conocimiento puede estar a la vuelta de la esquina.

---

Referencias

[LFKN90] C. Lund, L. Fortnow, H. Karloff, y N. Nissan. Métodos algebraicos para interactivo de pruebas. 1990.

[Mic94] S. Micali. Computacionalmente sonido de las pruebas. 1994.

[Kil92] J. Killian. Una nota en la eficacia de cero-conocimiento de las pruebas y los argumentos. 1992.

[Rys63] J. H. Ryser. La Combinatoria De Las Matemáticas. 1963.

Answer 3

Encontrar ciclos en gráficos es un problema estándar de teoría de gráficos que se presta bien a la prueba de trabajo. Vea mi página del proyecto Cuckoo Cycle en https://github.com/tromp/cuckoo que tiene toneladas de detalles, así como recompensas para mejorar las mejores implementaciones actuales.

Por supuesto, los gráficos pseudoaleatorios específicos generados en Cuckoo Cycle no tienen ningún uso práctico en absoluto ...

Answer 4

Me parece una excelente sugerencia, aunque no es seguro que todos los requisitos pueden ser satisfechos. Más específicamente, 3 y 5 - si queremos generar de forma aleatoria de los casos, entonces ¿por qué iban a tener ningún valor intrínseco? Sería la factorización de grandes números enteros tienen un valor intrínseco?

Un ejemplo que se me ocurre es el ajedrez como estrategia. Hay una creciente base de datos de la cual las posiciones que implican algunas piezas son victorias/empates. El problema es que la prueba podría ser difícil de comprobar, aunque, probablemente, no es imposible tener una prueba de formato que se puede comprobar muy rápido.

También, si el bitcoin presupuesto está en los millones, creo que sería bueno tener una junta central que seleccionar cada de vez en cuando un importante problema computacional para cuya solución hay una recompensa de muchos bitcoins. Al menos yo no veo nada malo con esta versión de la propuesta.

Answer 5

Aquí está un artículo reciente, que ha sido recibido positivamente en el cryptocurrency de la comunidad. Voy a ampliar sobre este artículo aquí.

Mientras convencionales de las funciones de hash no permiten construir muy útil la prueba de los problemas del trabajo, si se reemplaza la función de hash para la prueba-de-trabajo con una variación aleatoria de la función específicamente diseñado para ser calculados por los circuitos reversibles, entonces la prueba-de-trabajo problema tiene un uso práctico, además de simplemente asegurar la blockchain. Esta prueba-de-trabajo problema que se le pedirá al desarrollo de la súper-eficiente reversible equipos. Además, estas nuevas pruebas-de-los problemas en el trabajo va a satisfacer todos los requisitos que uno quiere en una prueba de trabajo problema para cryptocurrencies que he mencionado en la pregunta.

¿Es reversible la informática?

Un bijective la puerta de entrada (tales como el NO, Toffoli, y Fredkin puertas) es también llamada puerta reversible (y, por definición, cada bijective puerta debe tener el mismo número de bits de entrada como de salida de las palas). Un circuito que se dice ser reversible si todos los de su lógica puertas son reversibles. Como combinatoria de los circuitos de modelo ordinario de la computación, los circuitos reversibles modelo reversible de la computación. Cualquier cálculo que puede ser llevado a cabo eficientemente por una computadora normal también puede ser razonablemente eficiente calcula utilizando reversible equipo. Por ejemplo, PSPACE=REVSPACE donde REVSPACE se refiere a los problemas que se pueden resolver en una reversible equipo con un polinomio cantidad de espacio.

Por qué reversible de la computación?

Landauer del principio de que el borrado un poco los costos siempre $k\cdot T\cdot\ln(2)$ de la energía donde $k$ es la constante de Boltzmann y $T$ es la temperatura. Desde $k=1.38064852\cdot 10^{-23}\cdot m^{2}\cdot kg\cdot s^{-2}\cdot K^{-1}$, llegamos a la conclusión de que en $300 K$, borrando un poco los costos de $2.8 × 10^{−21}$ julios.

Mientras que la informática convencional siempre los costos de energía ya que con la informática convencional, uno siempre tiene que borrar la información, más probable es que hay no hay límite inferior para la eficiencia de la computación reversible desde reversible de computación no borrar cualquier información. Desde reversible computadoras serán más eficientes que los ordenadores normales, reversible equipos no generan tanto calor como los ordenadores normales, de modo reversible equipos será capaz de operar a velocidades mucho más altas que los ordenadores normales.

Mientras reversible equipo en teoría debería ser mucho más eficaz que una irreversible equipo, actualmente no hay reversible equipos en el mercado hoy en día que son más eficientes que sus irreversible contrapartes.

Si la prueba-de-trabajo problemas para cryptocurrencies requieren para solucionar problemas diseñados para super eficiente reversible equipos, entonces las empresas tienen un gran incentivo para producir reversible circuitos integrados que rápidamente se pueden resolver estos problemas sin utilizar tanta energía.

Una descripción preliminar de la prueba-de-trabajo problema

Ahora debemos seleccionar una prueba-de-trabajo problema que debe ser llevado a cabo por un reversibles equipo con la misma facilidad con que se lleva a cabo por un clásico de la computadora. Por lo tanto quiero que la variación aleatoria de la función computable en un circuito reversible sin ningún ancilla.

Para esta prueba-de-trabajo problema, supongamos que $f:\{0,1\}^{324}\rightarrow\{0,1\}^{324}$ es una función calculada por un circuito que consta únicamente de puertas reversibles y donde el circuito no contener cualquier basura o ancilla bits.

Supongamos que $\mathbf{k}$ es el hash del bloque de encabezado y $\alpha$ es ajustable 324 número de bits. Entonces la prueba-de-trabajo problema para el bloque actual será encontrar algunos de 68 cadena de bits $\mathbf{x}$ tal que $f(\mathbf{k}\#\mathbf{x})\leq\alpha$ donde $\#$ denota la operación de concatenación.