La reconnaissance des nœuds comme preuve de travail

23

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é?

Joshua Herman
la source
8
Vous pourriez être intéressé par cette question connexe sur le bitcoin SE: existe-t-il un moyen de configurer des systèmes de preuve de travail sans faire de travail inutile?
Artem Kaznatcheev
@ArtemKaznatcheev Merci de ne pas regarder cela.
Joshua Herman

Réponses:

7

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.G0G1Vi{0,1}π SVπ(Gi)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 , π )G0G1H:{0,1}{0,1}kyHy(i,π)tel que .H(π(Gi))=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 0G 1 peut être deux fois plus élevé plus grand que si G 0G 1 .HkG0G1G0G1G0G1

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 .HSHA256y00

  • 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'adjacenceG0G1

  • 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 )BcZ=H(cB)

  • Le mineur calcule choisir ( i , π )W=Zmod2V!(i,π)

  • Le mineur confirme que - c'est-à-dire pour confirmer que le π choisi au hasard n'est pas une preuve que les graphiques sont isomorphesπ(Gi)G1iπ

  • Sinon, le mineur calcule un hachage W=H(π(Gi))

  • Si commence par le nombre approprié de 0 , le mineur «gagne» en publiant ( c , B )W0(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 sZ=H(cB)(i,π)W=H(π(gje))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.g0g1

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.g1g2

[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; leNPUNEM 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.UNEMp0pH(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.UNEMcoUNEM

[Kup11] Greg Kuperberg. La nouage est en , modulo GRH, 2011.NP

Des notes
la source
1
Qu'en est-il des mouvements aléatoires de Markov? mathworld.wolfram.com/MarkovMoves.html
Joshua Herman
Vous pouvez également considérer les nœuds comme des graphiques qui sont des graphiques signés à quatre valences. Il vous suffit donc d'appliquer cette restriction sur G1 et G2
Joshua Herman
Voici une réduction d'une coloration quandle à une instance SAT. arxiv.org/pdf/1505.06595.pdf
Joshua Herman
oui, cela détermine si vous avez un passage supérieur ou inférieur. Voir en.wikipedia.org/wiki/Medial_graph
Joshua Herman
Est-ce que cela aiderait à tester la ridicule? On dirait que vous n'avez qu'à construire un graphe laman qui est facile en 2D (et les nœuds sont des graphes plans). www3.cs.stonybrook.edu/~jgao/CSE590-fall05/notes/lecture3.pdf
Joshua Herman
1

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é.

Table Rolfsen Knot

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. Table de mosaïque de noeud

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

Carreaux de mosaïque

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 NM
  3. K
  4. Il doit avoir un ensemble d'opérations de cardinalité OOOnK
  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 à 31 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 31

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

Joshua Herman
la source
3
Étant donné deux gros liens aléatoires, il est peu probable qu'ils soient équivalents. Et ils n'auront probablement pas le même polynôme d'Alexander, ce qui vous permettra de prouver qu'ils ne sont pas équivalents en temps polynomial. La tâche est donc facile la plupart du temps. Je soupçonne qu'il est extrêmement improbable que vous génériez un exemple véritablement dur en prenant des liens aléatoires.
Peter Shor
@ PeterShor oui je le reconnais. Je ne pense pas avoir bien articulé cela, mais je fais également une quantité arbitraire de ces tâches lorsque je la génère pour augmenter la dureté. Même avec cela, cela ne rendrait-il pas cela plus difficile?
Joshua Herman
@PeterShor De plus, le certificat n'est pas seulement que les deux nœuds ne sont pas équivalents, mais je veux un ensemble de mouvements de nœuds vers le nœud ou vers un nœud que vous pourriez calculer qu'il n'est pas isotopique ambiant (comme le trèfle).
Joshua Herman
1
Pour «un nœud connu dans une table», prévoyez-vous d'avoir une table de taille exponentielle? Parce qu'il y a exponentiellement beaucoup de nœuds d'une taille donnée.
Peter Shor
Oui et non. La taille de chaque instance d'utilisation de knothash est liée à la cardinalité du numéro d'opération et également à une instance valide d'un nœud ou d'un lien codé comme une mosaïque de nœuds. Je prévois d'utiliser ces paramètres pour limiter la quantité de solutions valides afin que la dureté du problème soit également un paramètre.
Joshua Herman