Knotenerkennung als Beweis der Arbeit

23

Derzeit verfügt Bitcoin über ein Proof-of-Work-System (PoW) mit SHA256. Andere Hash-Funktionen verwenden einen Proof-of-Work-System.

Ist es möglich, ein Entscheidungsproblem in der Knotentheorie wie die Knotenerkennung zu verwenden und es zu einem Beweis der Arbeitsfunktion zu machen? Hat das auch schon jemand gemacht? Auch wenn wir diese Proof of Work-Funktion haben, ist sie nützlicher als das, was gerade berechnet wird?

Joshua Herman
quelle
8
Diese verwandte Frage zur Bitcoin SE könnte Sie interessieren: Gibt es eine Möglichkeit, Proof-of-Work-Systeme einzurichten, ohne unnötige Arbeit zu verrichten?
Artem Kaznatcheev
@ArtemKaznatcheev Vielen Dank, dass ich mich darum kümmere.
Joshua Herman

Antworten:

7

Wenn es ein Arthur-Merlin- Protokoll für die Verknotung gibt, das dem [GMW85] und dem [GS86] Arthur-Merlin-Protokoll für den Graph Non Isomorphism ähnlich ist , dann glaube ich, dass ein solcher Kryptowährungsnachweis entworfen werden könnte, bei dem jeder Beweis Die Arbeit zeigt, dass zwei Knoten wahrscheinlich nicht äquivalent / isotopisch sind.

Wie aus dem Graph Non Isomorphism Protocol von [GMW85] bekannt ist, möchte der Prüfer Peggy Vicky beweisen, dass zwei (starre) Graphen und G 1 auf V Vertices nicht isomorph sind. Vicky darf heimlich eine zufällige Münze i { 0 , 1 } zusammen mit anderen Münzen werfen , um eine Permutation π S V zu erzeugen , und darf Peggy einen neuen Graphen π ( G i ) präsentieren . Peggy muss ich ableiten . Es ist klar, dass Peggy dies nur kann, wenn die beiden Graphen nicht isomorph sind.G0G1Vi{0,1}π SVπ(Gi)i

Ähnlich und relevanter für die Zwecke eines Arbeitsnachweises , wie er von [GS86] gelehrt wird, schließt eine Arthur-Merlin- Version desselben Protokolls ein, dass Arthur mit Merlin in Bezug auf , G 1 übereinstimmt , beispielsweise als Adjazenzmatrizen. Arthur wählt zufällig eine Hash-Funktion H : { 0 , 1 } { 0 , 1 } k zusammen mit einem Bild y aus . Arthur liefert H und Y an Merlin. Merlin muss ein ( i , π ) findenG0G1H:{0,1}{0,1}kyHy(i,π)so dass .H(π(Gi))=y

Das heißt, Merlin sucht nach einem Vorbild des Hash- , wobei das Vorbild eine Permutation einer der beiden gegebenen Adjazenzmatrizen ist. Solange k richtig gewählt ist und die beiden Graphen G 0 und G 1 nicht isomorph sind, besteht eine höhere Wahrscheinlichkeit, dass ein Vorbild gefunden wird, da die Anzahl der Adjazenzmatrizen in G 0G 1 doppelt so groß sein kann groß als wenn G 0G 1 .HkG0G1G0G1G0G1

Um das obige [GS86] -Protokoll in einen Proof-of-Work umzuwandeln, identifizieren Sie Bergleute als Merlin und andere Knoten als Arthur. Vereinbaren Sie einen Hash , der für alle Zwecke der in Bitcoin verwendete Hash S H A 256 sein kann. In ähnlicher Weise darüber einig , dass y immer sein wird , 0 , ähnlich die Bitcoin Anforderung , dass der Hash mit einer bestimmten Anzahl beginnt der führenden 0 s‘.HSHA256y00

  • Das Netzwerk willigt ein, zu beweisen, dass zwei starre Graphen und G 1 nicht isomorph sind. Die Graphen können durch ihre Adjazenzmatrizen gegeben seinG0G1

  • Eine Bergarbeiterin verwendet den Link zurück zum vorherigen Block zusammen mit ihrer eigenen Merkle-Wurzel von Finanztransaktionen und nennt ihn zusammen mit ihrem eigenen Nonce c , um eine Zufallszahl Z = H ( c B ) zu generieren.BcZ=H(cB)

  • Der Bergmann berechnet zu wählen ( i , π )W=Zmod2V!(i,π)

  • Der Bergmann bestätigt, dass - das heißt, um zu bestätigen, dass das zufällig ausgewählte π kein Beweis dafür ist, dass die Graphen isomorph sindπ(Gi)G1iπ

  • Wenn nicht, berechnet der Bergmann einen Hash W=H(π(Gi))

  • Beginnt mit der entsprechenden Anzahl von Nullen , gewinnt der Bergarbeiter durch Veröffentlichung ( c , B )W0(c,B)

  • Andere Knoten können überprüfen , dass herzuleiten ( i , π ) , und können überprüfen , dass W = H ( π ( G i ) ) beginnt mit der entsprechenden Schwierigkeit, 0 ‚sZ=H(cB)(i,π)W=H(π(Gi))0

Das obige Protokoll ist nicht perfekt, einige Knicke müssten wohl noch ausgearbeitet werden. Es ist beispielsweise nicht klar, wie zwei Zufallsgraphen und G 1 erzeugt werden sollen , die beispielsweise gute Steifigkeitseigenschaften erfüllen, und es ist auch nicht klar, wie die Schwierigkeit anders als durch Testen auf Graphen mit mehr oder weniger Scheitelpunkten eingestellt werden soll. Ich denke jedoch, dass diese wahrscheinlich überwindbar sind.G0G1

Ersetzen Sie für ein ähnliches Protokoll zur Verknotung zufällige Permutationen in der Adjazenzmatrix eines der beiden Graphen und G 2 durch andere zufällige Operationen in Knotendiagrammen oder Gitternetzdiagrammen. Ich denke nicht, dass zufällige Reidemeister-Bewegungen funktionieren, weil der Raum zu schnell zu unhandlich wird.G1G2

[HTY05] schlug ein Arthur-Merlin-Protokoll zur Knotenbildung vor, aber leider gab es einen Fehler, und sie zogen ihre Behauptung zurück.

[Kup11] hat gezeigt, dass unter der Annahme der verallgemeinerten Riemann-Hypothese die Verknotung in , und erwähnt, dass dies auch die Verknotung in A M setzt , aber ich bin ehrlich, ich weiß nicht, wie ich das in den obigen Rahmen übersetzen soll. das A M - Protokoll [Kup11] Ich denke , beinhaltet einen seltenen Primzahl zu finden p Modulo , die ein System von Polynomialgleichungen ist 0 . Die Primzahl p ist insofern selten, als H ( p ) = 0 ist und das System der Polynomgleichungen einer Darstellung der Knoten-Komplement-Gruppe entspricht.NPAMAMp0pH(p)=0

Beachten Sie, dass Sie diese Antwort auf eine ähnliche Frage auf einer Schwestersite finden, die sich auch mit dem Nutzen solcher "nützlichen" Arbeitsnachweise befasst.


Verweise:

[GMW85] Oded Goldreich, Silvio Micali und Avi Wigderson. Beweise, die nichts als ihre Gültigkeit beweisen, 1985.

[GS86] Shafi Goldwasser, Michael Sipser. Private Münzen gegen öffentliche Münzen in interaktiven Beweissystemen, 1986.

[HTY05] Masao Hara, Seiichi Tani und Makoto Yamamoto. Unknotting ist in 2005.AMcoAM

[Kup11] Greg Kuperberg. Verknotung ist in , Modulo GRH, 2011.NP

Mark S
quelle
1
Was ist mit zufälligen Markov-Zügen? mathworld.wolfram.com/MarkovMoves.html
Joshua Herman
Sie können Knoten auch als Diagramme betrachten, bei denen es sich um signierte Diagramme mit vier Valenzen handelt. Sie müssen also nur diese Einschränkung für G1 und G2 durchsetzen
Joshua Herman
Hier ist eine Reduktion einer Quandle-Färbung auf eine SAT-Instanz. arxiv.org/pdf/1505.06595.pdf
Joshua Herman
Ja, es bestimmt, ob Sie eine Über- oder Unterquerung haben. Siehe en.wikipedia.org/wiki/Medial_graph
Joshua Herman
Würde dies bei der Prüfung auf Lächerlichkeit helfen? Sieht so aus, als müssten Sie nur ein Lamandiagramm erstellen, das in 2D einfach ist (und Knoten sind ebene Diagramme). www3.cs.stonybrook.edu/~jgao/CSE590-fall05/notes/lecture3.pdf
Joshua Herman
1

Ich denke, der Weg, dies zu tun, besteht darin, eine Tabelle mit Mosaikknoten mit einer Reihe von Einschränkungen zu erstellen, um Verknüpfungen zu verbieten. Eine Knotentabelle ist also eine Menge von Knoten, die eine bestimmte Eigenschaft haben. Die Eigenschaft unten ist ein Hauptknoten.

Rolfsen Knotentisch

Sehen wir uns nun eine Knotentabelle an, die aus Mosaikknoten besteht: Ein Knotenmosaik ist eine Art Darstellung von Knoten, bei denen Kacheln anstelle von Zeichenfolgen in einem dreidimensionalen Raum verwendet werden. Knoten-Mosaik-Tabelle

Definieren wir nun formal, was ein Knotenmosaik ist:

Mosaikfliesen

Von https://arxiv.org/pdf/1602.03733.pdf Ein Knotenmosaik ist die Darstellung eines Knotens in einem n × n-Raster, das aus 11 Kacheln besteht.

Dies ist mein Ausgangspunkt, um Sie nach einer Mosaik-Knotentabelle mit einer Reihe von Einschränkungen zu fragen. Ich möchte Sie bitten, mir eine Tabelle mit den folgenden Eigenschaften zu geben

  1. C
  2. NM
  3. K
  4. OOnK
  5. Alle Operationen müssen eindeutig sein
  6. CR
  7. Es muss als Knotenmosaik codiert werden.

So können Sie das Kleeblatt in einem maschinenlesbaren Format codieren. Wir nehmen jedes Plättchen und weisen ihnen eine Nummer (01-11) zu. Mit dem Programmiersprachenschläger wird es so aussehen

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

31

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

31

Nun haben wir festgelegt, wie die Ausgabe aussehen soll. Wie gehen wir nun mit der Entstehung des Problems um?

Wir wissen also, dass Sie unter Umgebungsisotopie zu einem anderen Knotendiagramm gelangen können, wenn Sie ein anderes Knotendiagramm in einer endlichen Menge von Reidmeister-Zügen angeben. Lasst uns also zwei zufällige Links generieren. Die Aufgabe, die wir definieren, wird mit zwei zufälligen Links versehen. Ich möchte, dass Sie zeigen, dass sie entweder äquivalent sind, indem Sie jeden möglichen Knoten aufzählen, der ausgedrückt werden kann, oder dass sie nicht äquivalent sind, indem Sie mir eine Reihe von Zuständen oder Pfaden zu einem bekannten Knoten in geben ein Tisch.

Eine Möglichkeit, die Geschwindigkeit zu verbessern, mit der festgestellt werden kann, ob sich ein Knoten in der Tabelle befindet oder nicht, besteht darin, eine Hash-Tabelle mit Indizes als Alexander-Polynom zu erstellen. Für jede Instanz wird das Alexander-Polynom berechnet, und wenn sie dasselbe Alexander-Polynom verwenden, wird es als Element an diese Tabelle angehängt.

Ich habe Teil eines Arbeitsprogramms unter folgender Adresse: https://gist.github.com/zitterbewegung/4152b322eef5ecccdcf3502e8220844b

Joshua Herman
quelle
3
Bei zwei großen, zufälligen Links ist es unwahrscheinlich, dass sie gleichwertig sind. Und sie werden wahrscheinlich nicht dasselbe Alexander-Polynom haben, was Sie beweisen lässt, dass sie in der Polynomzeit nicht gleichwertig sind. Die Aufgabe ist also die meiste Zeit einfach. Ich vermute, dass es äußerst unwahrscheinlich ist, dass Sie ein wirklich schweres Beispiel erstellen, indem Sie zufällige Links verwenden.
Peter Shor
@PeterShor ja das erkenne ich. Ich glaube nicht, dass ich das gut artikuliert habe, aber ich mache auch eine willkürliche Menge dieser Aufgaben, wenn ich sie erstelle, um die Härte zu erhöhen. Selbst wenn dies eintritt, würde es das nicht schwieriger machen?
Joshua Herman
@PeterShor Auch das Zertifikat besagt nicht nur, dass beide Knoten nicht gleichwertig sind, sondern ich möchte, dass sich ein Knotensatz zum Unknot oder zu einem Knoten bewegt, von dem man errechnen kann, dass er kein Umgebungsisotop ist (wie das Kleeblatt).
Joshua Herman
1
Planen Sie für "einen bekannten Knoten in einer Tabelle" einen exponentiell großen Tisch? Weil es exponentiell viele Knoten einer bestimmten Größe gibt.
Peter Shor
Ja und nein. Die Größe jeder Verwendung von Knoten ist an die Kardinalität der Vorgangsnummer und an eine gültige Instanz eines Knotens oder einer Verknüpfung gebunden, die als Knotenmosaik codiert ist. Ich plane, diese Parameter zu verwenden, um die Anzahl der gültigen Lösungen zu begrenzen, sodass die Härte des Problems auch ein Parameter ist.
Joshua Herman