Reconocimiento de nudos como prueba de trabajo

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?

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 ) $G_0$$G_1$$V$$i\in\{0,1\}$$\pi\in\ S_V$$\pi(G_i)$$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 ) ) = $G_0$$G_1$$H:\{0,1\}^*\rightarrow\{0,1\}^k$$y$$H$$y$$(i,\pi)$$H(\pi(G_i))=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 0 ∪ G 1 G 0 ≅ G $H$$k$$G_0$$G_1$$G_0 \cup G_1$$G_0\cong G_1$

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 $H$$\mathsf{SHA256}$$y$$0$$0$

• 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 $G_0$$G_1$

• 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 $B$$c$$Z=H(c\Vert B)$

• ¡El minero calculaelegir( i , π $W= Z\:mod\: 2V!$$(i,\pi)$

• El minero confirma que , es decir, para confirmar que el elegido al azar no es una prueba de que los gráficos son isomorfos$\pi(G_i)\neq G_{1-i}$$\pi$

• Si no, el minero calcula un hash$W=H(\pi(G_i))$

• Si comienza con el número apropiado de , el minero "gana" publicando$W$$0$$(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 ) ) $Z=H(c\Vert B)$$(i,\pi)$$W=H(\pi(G_i))$$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 $G_0$$G_1$

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 $G_1$$G_2$

[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 ) = $\mathsf{NP}$$\mathsf{AM}$$\mathsf{AM}$$p$$0$$p$$H(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.$\mathsf{AM} \cap \mathsf{coAM}$

[Kup11] Greg Kuperberg. La anudación está en , módulo GRH, 2011.$\mathsf{NP}$

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.

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.

Ahora definamos formalmente qué es un mosaico de nudos:

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 cruce$C$
2. Debe tener al menos un elemento con una dimensión de por$N$$M$
3. Debe ser isotópico ambiental al nudo que enviamos$K$
4. Debe tener un conjunto de operaciones de cardinalidad que muestren que es isotópico ambiental al nudoO n$O$$O_n$$K$
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 raqueta$3_1$

(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.$3_1$

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