La reconnaissance des nœuds comme preuve de travail

Actuellement, Bitcoin dispose d'un système de preuve de travail (PoW) utilisant SHA256. D'autres fonctions de hachage utilisent des graphiques d'utilisation du système de preuve de travail, l'inversion partielle de la fonction de hachage.

Est-il possible d'utiliser un problème de décision dans la théorie des nœuds comme la reconnaissance de nœuds et d'en faire une fonction de preuve de travail? Quelqu'un a-t-il déjà fait cela auparavant? De plus, lorsque nous aurons cette fonction de preuve de travail, sera-t-elle plus utile que ce qui est actuellement calculé?

S'il existe un protocole Arthur-Merlin pour le nouage similaire aux protocoles [GMW85] et [GS86] Arthur-Merlin pour Graph Non Isomorphism, alors je crois qu'une telle preuve de travail de crypto-monnaie pourrait être conçue, dans laquelle chaque preuve de- les travaux montrent que deux nœuds ne sont pas susceptibles d'être équivalents / isotopiques.

Plus en détail, comme cela est bien connu dans le protocole Graph Non Isomorphism de [GMW85], Peggy le prouveur souhaite prouver à Vicky le vérificateur que deux graphes (rigides) et G 1 sur les sommets V ne sont pas isomorphes. Vicky peut lancer secrètement une pièce aléatoire i ∈ { 0 , 1 } , avec d'autres pièces pour générer une permutation π ∈ S V , et peut présenter à Peggy un nouveau graphique π ( G i ) . Peggy doit en déduire i . Clairement, Peggy ne peut le faire que si les deux graphiques ne sont pas isomorphes.$G_0$$G_1$$V$$i\in\{0,1\}$$\pi\in\ S_V$$\pi(G_i)$$i$

De même, et plus pertinent aux fins d'une preuve de travail , comme enseigné par [GS86], une version Arthur-Merlin du même protocole inclut Arthur d'accord avec Merlin sur , G 1 , donné par exemple comme matrices d'adjacence. Arthur choisit au hasard une fonction de hachage H : { 0 , 1 } ∗ → { 0 , 1 } k , avec une image y . Arthur fournit H et y à Merlin. Merlin doit trouver un ( i , π $G_0$$G_1$$H:\{0,1\}^*\rightarrow\{0,1\}^k$$y$$H$$y$$(i,\pi)$tel que .$H(\pi(G_i))=y$

C'est-à-dire que Merlin recherche une pré-image du hachage , la pré-image étant une permutation de l'une des deux matrices d'adjacence données. Tant que k est choisi correctement, si les deux graphes G 0 et G 1 ne sont pas isomorphes, il y aura plus de chances qu'une pré-image soit trouvée, car le nombre de matrices d'adjacence dans G 0 ∪ G 1 peut être deux fois plus élevé plus grand que si G 0 ≅ G 1 .$H$$k$$G_0$$G_1$$G_0 \cup G_1$$G_0\cong G_1$

Afin de convertir le protocole [GS86] ci-dessus en une preuve de travail, identifiez les mineurs comme Merlin et identifiez les autres nœuds comme Arthur. Mettez-vous d'accord sur un hachage , qui, à toutes fins, peut être le hachage S H A 256 utilisé dans Bitcoin. De même, convenez que y sera toujours 0 , similaire à l'exigence Bitcoin selon laquelle le hachage commence par un certain nombre de 0 en tête .$H$$\mathsf{SHA256}$$y$$0$$0$

• Le réseau s'engage à prouver que deux graphes rigides et G 1 ne sont pas isomorphes. Les graphiques peuvent être donnés par leurs matrices d'adjacence$G_0$$G_1$

• Un mineur utilise le lien vers le bloc précédent, ainsi que sa propre racine Merkle de transactions financières, appelez-le , ainsi que son propre nonce c , pour générer un nombre aléatoire Z = H ( c ‖ B $B$$c$$Z=H(c\Vert B)$

• Le mineur calcule choisir ( i , π $W= Z\:mod\: 2V!$$(i,\pi)$

• Le mineur confirme que - c'est-à-dire pour confirmer que le π choisi au hasard n'est pas une preuve que les graphiques sont isomorphes$\pi(G_i)\neq G_{1-i}$$\pi$

• Sinon, le mineur calcule un hachage $W=H(\pi(G_i))$

• Si commence par le nombre approprié de 0 , le mineur «gagne» en publiant ( c , B $W$$0$$(c,B)$

• D'autres nœuds peuvent vérifier que à déduire ( i , π ) , et peuvent vérifier que W = H ( π ( G i ) ) commence avec la difficulté appropriée de 0 s$Z=H(c\Vert B)$$(i,\pi)$$W=H(\pi(G_i))$$0$

Le protocole ci-dessus n'est pas parfait, je pense que certains défauts devraient être résolus. Par exemple, il n'est pas clair comment générer deux graphes aléatoires et G 1 qui satisfont à de bonnes propriétés de rigidité, par exemple, ni comment ajuster la difficulté autrement qu'en testant des graphes avec plus ou moins de sommets. Cependant, je pense que ceux-ci sont probablement surmontables.$G_0$$G_1$

Mais pour un protocole similaire sur le nouage , remplacez les permutations aléatoires sur la matrice d'adjacence de l'un des deux graphiques et G 2 par quelques autres opérations aléatoires sur les diagrammes de nœuds ou les diagrammes de grille ... ou quelque chose. Je ne pense pas que les mouvements aléatoires de Reidemeister fonctionnent, car l'espace devient trop encombrant trop rapidement.$G_1$$G_2$

[HTY05] a proposé un protocole Arthur-Merlin pour le nouage, mais malheureusement il y avait une erreur et ils ont retiré leur demande.

[Kup11] a montré que, en supposant l'hypothèse de Riemann généralisée, le nœud est dans , et mentionne que cela met également le nœud dans A M , mais je vais être honnête, je ne sais pas comment traduire cela dans le cadre ci-dessus; le$\mathsf{NP}$$\mathsf{AM}$ protocole de je pense [Kup11] consistetrouver un premier rare p modulo lequel un système d'équations polynomiales est 0 . Le premier p est rare en ce que H ( p ) = 0 , et le système d'équations polynomiales correspond à une représentation du groupe complémentaire de nœuds.$\mathsf{AM}$$p$$0$$p$$H(p)=0$

À noter, voir cette réponse à une question similaire sur un site frère, qui traite également de l'utilité de ces preuves de travail "utiles".

Les références:

[GMW85] Oded Goldreich, Silvio Micali et Avi Wigderson. Des preuves qui ne rapportent que leur validité, 1985.

[GS86] Shafi Goldwasser, Michael Sipser. Pièces privées contre pièces publiques dans les systèmes de preuve interactifs, 1986.

[HTY05] Masao Hara, Seiichi Tani et Makoto Yamamoto. UNKNOTTING est dans , 2005.$\mathsf{AM} \cap \mathsf{coAM}$

[Kup11] Greg Kuperberg. La nouage est en , modulo GRH, 2011.$\mathsf{NP}$

Je pense que la façon de le faire est de créer une table de nœuds de mosaïque avec un ensemble de restrictions pour interdire les raccourcis. Une table de nœuds est donc un ensemble de nœuds qui ont une propriété donnée. La propriété ci-dessous est un nœud privilégié.

Voyons maintenant une table de nœuds composée de nœuds de mosaïque: une mosaïque de nœuds est un type de représentation de nœuds qui utilisent des tuiles au lieu d'être des chaînes dans un espace tridimensionnel.

Permet maintenant de définir formellement ce qu'est une mosaïque de nœuds:

De https://arxiv.org/pdf/1602.03733.pdf Une mosaïque de nœuds est la représentation d'un nœud sur une grille n × n composée de 11 tuiles les voici ci-dessous.

C'est mon point de départ en vous demandant une table de noeuds en mosaïque avec un ensemble de restrictions. Ce que je veux vous demander, c'est de me donner un tableau avec les propriétés suivantes

1. $C$
2. Il doit avoir au moins un élément de dimension $N$$M$
3. $K$
4. Il doit avoir un ensemble d'opérations de cardinalité $O$$O_n$$K$
5. Toutes les opérations doivent être uniques
6. Tu dois me donner les coordonnées $CR$
7. Il doit être codé comme une mosaïque de nœuds.

Permet donc d'encoder le trèfle dans un format lisible par machine. Nous prenons chaque tuile et leur attribuons un numéro (01-11). En utilisant la raquette du langage de programmation, cela ressemblera à ceci

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

Ce qui correspond à $3_1$ dans le tableau ci-dessus de Rolfesen. Maintenant, voyons une tâche triviale. Encore une fois avec une raquette

(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])

Cela nous donnerait la tâche triviale qui serait la table triviale n'aurait que le nœud principal $3_1$

Donc, maintenant que nous avons établi ce que la sortie devrait être. Maintenant, comment abordons-nous la génération du problème?

Nous savons donc que sous isotopie ambiante, vous pouvez accéder à un autre diagramme de nœuds, étant donné un autre diagramme de nœuds dans un ensemble fini de mouvements de reidmeister. Permet donc de générer deux liens aléatoires. La tâche que nous définissons reçoit deux liens aléatoires. Je veux que vous montriez qu'ils sont équivalents en énumérant tous les nœuds possibles qui peuvent être exprimés ou qu'ils ne sont pas équivalents en me donnant un ensemble d'états ou de chemins vers un nœud connu dans une table.

Un moyen où nous pouvons améliorer la vitesse de savoir qu'un nœud est dans la table ou non est de construire une table de hachage avec des indices comme le polynôme d'Alexander. Chaque instance aurait le polynôme Alexander calculé pour elle et s'ils partagent le même polynôme Alexander, il serait ajouté en tant qu'élément à cette table.

J'ai une partie d'un programme de travail à l'essentiel suivant: https://gist.github.com/zitterbewegung/4152b322eef5ecccdcf3502e8220844b