Reconocimiento de nudos como prueba de trabajo

23

Actualmente, bitcoin tiene un sistema de prueba de trabajo (PoW) que usa SHA256. Otras funciones hash utilizan una prueba de gráficos de uso del sistema de trabajo, inversión parcial de la función hash.

¿Es posible usar un problema de Decisión en la teoría de nudos como el reconocimiento de nudos y convertirlo en una función de prueba de trabajo? ¿Alguien ha hecho esto antes? Además, cuando tengamos esta función de Prueba de trabajo, ¿será más útil de lo que se está calculando actualmente?

Joshua Herman
fuente
8
Es posible que le interese esta pregunta relacionada sobre el SE de bitcoin: ¿hay alguna manera de configurar sistemas de prueba de trabajo sin hacer un trabajo inútil?
Artem Kaznatcheev
@ArtemKaznatcheev Gracias, lo investigaré.
Joshua Herman

Respuestas:

7

Si hay un protocolo Arthur-Merlin para la anudación similar a los protocolos [GMW85] y [GS86] Arthur-Merlin para Graph Non Isomorphism, entonces creo que podría diseñarse una prueba de trabajo de criptomonedas , en la que cada prueba de El trabajo muestra que es probable que dos nudos no sean equivalentes / isotópicos.

En más detalle, como es bien conocido en el protocolo Graph no isomorfismo de [GMW85], Peggy la cámara de fermentación desea demostrar a Vicky el verificador que dos (rígido) representa gráficamente y en vértices no son isomorfos. Vicky puede arrojar secretamente una moneda aleatoria , junto con otras monedas para generar una permutación , y puede presentarle a Peggy un nuevo gráfico . Peggy debe deducir . Claramente, Peggy solo puede hacer esto si las dos gráficas no son isomorfas.G 1 V i { 0 , 1 } π S V π ( G i ) iG0G1Vi{0,1}π SVπ(Gi)i

Del mismo modo, y más relevante para los fines de una prueba de trabajo , tal como se enseña por [GS86] un Arthur-Merlin versión del mismo protocolo incluye Arthur de acuerdo con Merlin en , , dada como para matrices ejemplo de adyacencia. Arthur elige aleatoriamente una función hash , junto con una imagen . Arthur proporciona e a Merlín. Merlín debe encontrar un tal que .G 1 H : { 0 , 1 } { 0 , 1 } k y H y ( i , π ) H ( π ( G i ) ) = yG0G1H:{0,1}{0,1}kyHy(i,π)H(π(Gi))=y

Es decir, Merlín busca una preimagen del hash , siendo la preimagen una permutación de una de las dos matrices de adyacencia dadas. Mientras se elige correctamente, si los dos gráficos y no son isomorfos entonces habrá una mayor probabilidad de que una imagen inversa se encontrará, porque el número de matrices de adyacencia en puede ser el doble de grande que si .k G 0 G 1 G 0G 1 G 0G 1HkG0G1G0G1G0G1

Para convertir el protocolo [GS86] anterior en una prueba de trabajo, identifique a los mineros como Merlín e identifique otros nodos como Arthur. Acuerde un hash , que, a todos los efectos, puede ser el hash utilizado en Bitcoin. Del mismo modo, acuerde que siempre será , similar al requisito de Bitcoin de que el hash comienza con un cierto número de iniciales.S H A 256 y 0 0HSHA256y00

  • La red se compromete a demostrar que dos gráficos rígidos y no son isomorfos. Los gráficos pueden estar dados por sus matrices de adyacenciaG 1G0G1

  • Un minero usa el enlace de regreso al bloque anterior, junto con su propia raíz Merkle de transacciones financieras, llámelo , junto con su propio nonce , para generar un número aleatorioc Z = H ( c B )BcZ=H(cB)

  • ¡El minero calculaelegir( i , π )W=Zmod2V!(i,π)

  • El minero confirma que , es decir, para confirmar que el elegido al azar no es una prueba de que los gráficos son isomorfos ππ(Gi)G1iπ

  • Si no, el minero calcula un hashW=H(π(Gi))

  • Si comienza con el número apropiado de , el minero "gana" publicando0W0(c,B)

  • Otros nodos pueden verificar que para deducir , y pueden verificar que comienza con la dificultad apropiada de ‘s( i , π ) W = H ( π ( G i ) ) 0Z=H(cB)(i,π)W=H(π(Gi))0

El protocolo anterior no es perfecto, creo que algunos problemas deberían resolverse. Por ejemplo, no está claro cómo generar dos grafos aleatorios y que satisfagan las buenas propiedades de rigidez, por ejemplo, ni tampoco está claro cómo ajustar la dificultad que no sea mediante pruebas de gráficos con más o menos vértices. Sin embargo, creo que estos son probablemente superables.G 1G0G1

Pero para un protocolo similar sobre anudamiento , reemplace las permutaciones aleatorias en la matriz de adyacencia de uno de los dos gráficos y con algunas otras operaciones aleatorias en diagramas de nudos o diagramas de cuadrícula ... o algo así. No creo que los movimientos aleatorios de Reidemeister funcionen, porque el espacio se vuelve demasiado difícil de manejar demasiado rápido.G 2G1G2

[HTY05] propuso un protocolo Arthur-Merlin para la anudación, pero desafortunadamente hubo un error y retiraron su reclamo.

[Kup11] mostró que, suponiendo que la Hipótesis de Riemann generalizada, la anudación está en , y menciona que esto también pone la anudación en , pero seré sincero, no sé cómo traducir esto en el marco anterior; El protocolo de [Kup11] creo que consiste en encontrar un módulo primo raro en el que un sistema de ecuaciones polinómicas es . El primer es raro en que , y el sistema de ecuaciones polinómicas corresponde a una representación del grupo de complemento de nudo.A M A M p 0 p H ( p ) = 0NPAMAMp0pH(p)=0

Es de destacar que vea esta respuesta a una pregunta similar en un sitio hermano, que también aborda la utilidad de tales pruebas de trabajo "útiles".


Referencias

[GMW85] Oded Goldreich, Silvio Micali y Avi Wigderson. Pruebas que no dan más que su validez, 1985.

[GS86] Shafi Goldwasser, Michael Sipser. Monedas privadas versus monedas públicas en sistemas de prueba interactivos, 1986.

[HTY05] Masao Hara, Seiichi Tani y Makoto Yamamoto. UNKNOTTING está en , 2005.AMcoAM

[Kup11] Greg Kuperberg. La anudación está en , módulo GRH, 2011.NP

Marcas
fuente
1
¿Qué pasa con los movimientos aleatorios de Markov? mathworld.wolfram.com/MarkovMoves.html
Joshua Herman
También puede considerar los nudos como gráficos que son gráficos con signo que tienen cuatro valencia. Entonces solo tienes que imponer esa restricción en G1 y G2
Joshua Herman
Aquí hay una reducción de una coloración de quandle a una instancia SAT. arxiv.org/pdf/1505.06595.pdf
Joshua Herman
sí, determina si tiene un cruce por encima o por debajo. Ver en.wikipedia.org/wiki/Medial_graph
Joshua Herman el
¿Esto ayudaría a probar la ridiculez? Parece que solo tiene que construir un gráfico laman que es fácil en 2D (y los nudos son gráficos planos). www3.cs.stonybrook.edu/~jgao/CSE590-fall05/notes/lecture3.pdf
Joshua Herman el
1

Creo que la forma de hacerlo es crear una tabla de nudos de mosaico con un conjunto de restricciones para no permitir accesos directos. Entonces, una tabla de nudos es un conjunto de nudos que tienen una propiedad dada. La propiedad a continuación está siendo un nudo principal.

Mesa Rolfsen Knot

Ahora veamos una tabla de nudos compuesta por nudos de mosaico: un mosaico de nudos es un tipo de representación de nudos que usan mosaicos en lugar de ser cadenas en un espacio tridimensional. Mesa de mosaico de nudos

Ahora definamos formalmente qué es un mosaico de nudos:

Azulejos de mosaico

De https://arxiv.org/pdf/1602.03733.pdf Un mosaico de nudos es la representación de un nudo en una cuadrícula n × n compuesta por 11 fichas.

Este es mi punto de partida para pedirle una mesa de nudos de mosaico con un conjunto de restricciones. Lo que quiero preguntarte es que me des una tabla con las siguientes propiedades

  1. Debe tener al menos un elemento con un número de cruceC
  2. Debe tener al menos un elemento con una dimensión de porMNM
  3. Debe ser isotópico ambiental al nudo que enviamosK
  4. Debe tener un conjunto de operaciones de cardinalidad que muestren que es isotópico ambiental al nudoO n KOOnK
  5. Todas las operaciones deben ser únicas.
  6. Debes darme las coordenadas de la operación en el propio nudo.CR
  7. Debe estar codificado como un mosaico de nudos.

Entonces, codifiquemos el trébol en un formato legible por máquina. Tomamos cada mosaico y les asignamos un número (01-11). Usando la raqueta del lenguaje de programación se verá así

(define trefoil (array #[#[00 02 01 00]
                         #[02 10 09 01]
                         #[03 09 04 06]
                         #[00 03 05 04]] : Integer))

Que corresponde a en la tabla anterior por Rolfesen. Ahora, veamos una tarea trivial. Una vez más usando raqueta31

(struct braidcoin ([source_knot : (Matrix Integer)]
                   [target_knot : (Matrix Integer)]
                   [crossing_number : (Refine [n : Integer] (> n 0))]
                   [dimention : (Refine [n : Integer] (> n 0))]
                   [timestamp : date])

Esto nos daría la tarea trivial que sería la tabla trivial que tendría solo el nudo principal . Los nudos de origen y destino en la estructura anterior serían los mismos. El número de cruce sería tres. La dimensión sería de cuatro por cuatro.31

Entonces, ahora que hemos establecido cuál debería ser la salida. Ahora, ¿cómo abordamos la generación del problema?

Entonces, sabemos que bajo la isotopía ambiental puede llegar a otro diagrama de nudos dado otro diagrama de nudos en un conjunto finito de movimientos reidmeister. Entonces, generemos dos enlaces aleatorios. La tarea que definimos tiene dos enlaces aleatorios. Quiero que demuestre que son equivalentes al enumerar todos los nudos posibles que se pueden expresar o que no son equivalentes al darme un conjunto de estados o rutas a un nudo conocido en una mesa.

Una forma en que podemos mejorar la velocidad de saber que un nudo está en la tabla o no es mediante la construcción de una tabla hash con índices como el polinominal de Alexander. Cada instancia tendría el polinominal de Alexander calculado para él y si comparten el mismo polinomio de Alexander se agregará como un elemento a esa tabla.

Tengo parte de un programa de trabajo en la siguiente esencia: https://gist.github.com/zitterbewegung/4152b322eef5ecccdcf3502e8220844b

Joshua Herman
fuente
3
Dados dos enlaces grandes y aleatorios, es poco probable que sean equivalentes. Y probablemente no tendrán el mismo polinomio de Alexander, lo que le permitirá demostrar que no son equivalentes en el tiempo polinomial. Entonces la tarea es fácil la mayor parte del tiempo. Sospecho que es extremadamente improbable que generes un ejemplo realmente difícil al tomar enlaces aleatorios.
Peter Shor
@ PeterShor sí, lo reconozco. No creo que haya articulado esto bien, pero también estoy haciendo una cantidad arbitraria de estas tareas cuando la estoy generando para aumentar la dureza. Incluso con eso ocurriendo, ¿eso no lo haría más difícil?
Joshua Herman
@PeterShor Además, el certificado no es solo que ambos nudos no son equivalentes, sino que quiero un conjunto de movimientos de nudos hacia el nudo o hacia un nudo que podría calcular que no es isotópico ambiental (como el trébol).
Joshua Herman
1
Para "un nudo conocido en una tabla", ¿planea tener una tabla de tamaño exponencial? Porque hay exponencialmente muchos nudos de un tamaño dado.
Peter Shor
Si y no. El tamaño de cada instancia de uso de knothash está limitado por la cardinalidad del número de Operación y también una instancia válida de un nudo o enlace codificado como un mosaico de nudos. Planeo usar estos parámetros para limitar la cantidad de soluciones válidas para que la dureza del problema también sea un parámetro.
Joshua Herman