Rozpoznawanie węzłów jako dowód pracy

Obecnie bitcoin ma system proof of work (PoW) wykorzystujący SHA256. Inne funkcje skrótu wykorzystują wykresy wykorzystania systemu dowodu pracy, częściowe odwrócenie funkcji skrótu.

Czy można zastosować problem decyzyjny w teorii węzłów, taki jak rozpoznawanie węzłów, i uczynić z niego funkcję dowodu pracy? Czy ktoś już to zrobił? Ponadto, kiedy będziemy mieli tę funkcję Dowodu pracy, czy będzie ona bardziej przydatna niż to, co jest obecnie obliczane?

Jeśli istnieje protokół Arthur-Merlina dla wiązań podobny do [GMW85] i [GS86] protokołów Arthur-Merlina dla Graph Non Isomorphism, to uważam, że można zaprojektować taki dowód pracy w kryptowalutach , w którym każdy dowód - prace pokazują, że dwa węzły prawdopodobnie nie będą równoważne / izotopowe.

Bardziej szczegółowo, jak dobrze wiadomo w protokole Graph Non Isomorphism [GMW85], Peggy, prover chce udowodnić Vicky weryfikatorowi, że dwa (sztywne) wykresy i G 1 na wierzchołkach V nie są izomorficzne. Vicky może tajemnicy rzuca losową monety ı ∈ { 0 , 1 } , a także z innych monet generowania permutacji gatunku ∈ S V , i może stanowić Peggy nowy wykres gatunku ( g- i ) . Peggy musi wydedukować I . Najwyraźniej Peggy jest w stanie to zrobić tylko wtedy, gdy dwa wykresy nie są izomorficzne.$G_0$$G_1$$V$$i\in\{0,1\}$$\pi\in\ S_V$$\pi(G_i)$$i$

Podobnie i bardziej odpowiednie dla celów dowodu pracy , jak naucza [GS86], wersja Arthur-Merlin tego samego protokołu obejmuje Arthura zgadzającego się z Merlinem w sprawie , G 1 , podanej jako na przykład macierze przylegania. Artur losowo wybiera funkcję skrótu H : { 0 , 1 } ∗ → { 0 , 1 } k , wraz z obrazem y . Artur zapewnia H i y Merlinowi. Merlin musi znaleźć ( i , π $G_0$$G_1$$H:\{0,1\}^*\rightarrow\{0,1\}^k$$y$$H$$y$$(i,\pi)$tak, że .$H(\pi(G_i))=y$

Oznacza to, że Merlin szuka preimage skrótu , przy czym preimage jest permutacją jednej z dwóch danych macierzy sąsiedztwa. Tak długo, jak prawidłowo wybrano k , jeśli dwa wykresy G 0 i G 1 nie są izomorficzne, wówczas istnieje większa szansa na znalezienie preimage, ponieważ liczba macierzy przylegania w G 0 ∪ G 1 może być dwa razy większa duży niż, jeśli G 0 ≅ G 1 .$H$$k$$G_0$$G_1$$G_0 \cup G_1$$G_0\cong G_1$

Aby przekonwertować powyższy protokół [GS86] na dowód pracy, zidentyfikuj górników jako Merlin i inne węzły jako Arthur. Uzgodnić mieszania , która pod każdym względem, może być S H 256 mieszania używany w Bitcoin. Podobnie, ustalić, że R jest zawsze 0 , podobnie jak wymagania Bitcoin że mieszania rozpoczyna się od pewnej liczby prowadzi 0 „s.$H$$\mathsf{SHA256}$$y$$0$$0$

• Sieć zgadza się udowodnić, że dwa sztywne wykresy i G 1 nie są izomorficzne. Wykresy mogą być podane przez ich macierze przylegania$G_0$$G_1$

• Górnik używa linku z powrotem do poprzedniego bloku, wraz z własnym pierwiastkiem Merkle transakcji finansowych, nazwij go , wraz z własną nonce c , aby wygenerować losową liczbę Z = H ( c ‖ B $B$$c$$Z=H(c\Vert B)$

• Górnik oblicza wybrać ( i , π $W= Z\:mod\: 2V!$$(i,\pi)$

• Górnik potwierdza, że - to znaczy, aby potwierdzić, że losowo wybrany π nie jest dowodem na to, że wykresy są izomorficzne$\pi(G_i)\neq G_{1-i}$$\pi$

• Jeśli nie, górnik oblicza skrót $W=H(\pi(G_i))$

• Jeśli zaczyna się od odpowiedniej liczby 0 , górnik „wygrywa”, publikując ( c , B $W$$0$$(c,B)$

• Inne węzły mogą weryfikować, że wywnioskować ( I , gatunku ) , można sprawdzić, W = H ( π ( G I ) ) rozpoczyna się od odpowiedniego trudności 0 „s$Z=H(c\Vert B)$$(i,\pi)$$W=H(\pi(G_i))$$0$

Powyższy protokół nie jest idealny, myślę, że należałoby opracować pewne zagięcia. Na przykład, nie jest jasne, jak wygenerować dwa losowe wykresy i G 1, które spełniają na przykład dobre właściwości sztywności, ani nie jest jasne, jak dostosować trudność inaczej niż poprzez testowanie wykresów z większą lub mniejszą liczbą wierzchołków. Myślę jednak, że są one prawdopodobnie do przezwyciężenia.$G_0$$G_1$

Ale dla podobnego protokołu wiązania , zamień losowe permutacje na macierzy przyległości jednego z dwóch wykresów i G 2 na inne losowe operacje na diagramach węzłów lub diagramach siatki ... lub coś takiego. Nie sądzę, żeby przypadkowe ruchy Reidemeistera działały, ponieważ przestrzeń zbyt szybko staje się niewygodna.$G_1$$G_2$

[HTY05] zaproponował protokół Arthura-Merlina dla wiązań, ale niestety wystąpił błąd i wycofali swoje roszczenie.

[Kup11] wykazały, że przy założeniu, że uogólnionego Riemanna hipoteza knottedness jest w , i mówi, że to również stawia knottedness w A M , ale będę szczery nie wiem jak przetłumaczyć to pod powyższym ram; M Protokół [Kup11] i że wymaga znalezienia rzadkich doskonałą p modulo którym układ równań wielomianowych jest 0 . Liczba pierwsza p jest rzadka pod tym względem, że H ( p ) = 0 , a układ równań wielomianowych odpowiada reprezentacji grupy komplementacji węzłów.$\mathsf{NP}$$\mathsf{AM}$$\mathsf{AM}$$p$$0$$p$$H(p)=0$

Warto zauważyć, że odpowiedź na podobne pytanie znajduje się na stronie siostrzanej, która dotyczy również użyteczności takich „przydatnych” dowodów pracy.

Referencje:

[GMW85] Oded Goldreich, Silvio Micali i Avi Wigderson. Dowody, że dają tylko swoją ważność, 1985.

[GS86] Shafi Goldwasser, Michael Sipser. Monety prywatne a monety publiczne w interaktywnych systemach dowodowych, 1986.

[HTY05] Masao Hara, Seiichi Tani i Makoto Yamamoto. UNKNOTTING jest w , 2005.$\mathsf{AM} \cap \mathsf{coAM}$

[Kup11] Greg Kuperberg. Wiązanie jest w , moduł GRH, 2011.$\mathsf{NP}$

Myślę, że sposobem na to jest stworzenie tabeli mozaikowych węzłów z zestawem ograniczeń, które nie zezwalają na skróty. Tak więc tabela węzłów to zbiór węzłów, które mają daną właściwość. Właściwość poniżej jest głównym węzłem.

Zobaczmy teraz tabelę węzłów złożoną z węzłów mozaiki: mozaika węzłów jest rodzajem przedstawienia węzłów, które używają kafelków zamiast ciągów w przestrzeni trójwymiarowej.

Teraz pozwala formalnie zdefiniować, czym jest mozaika węzłów:

Od https://arxiv.org/pdf/1602.03733.pdf Mozaika węzłowa to reprezentacja węzła na siatce n × n złożonej z 11 płytek, oto ich poniżej.

To jest mój punkt wyjścia, aby poprosić cię o mozaiczny stół z węzłami z zestawem ograniczeń. Chcę cię prosić o podanie tabeli z następującymi właściwościami

1. Musi mieć co najmniej jeden element o numerze przecięcia $C$
2. Musi mieć co najmniej element o wymiarze przez $N$$M$
3. Musi być izotopowy w otoczeniu względem węzła , który wysyłamy$K$
4. Musi mieć zestaw operacji liczności O n, które pokazują, że jest on izotopem otoczenia względem węzła $O$$O_n$$K$
5. Wszystkie operacje muszą być unikalne
6. Musisz podać mi współrzędne operacji na samym węźle.$CR$
7. Musi być zakodowany jako mozaika węzłowa.

Więc zakodujmy koniczynę w formacie odczytywalnym maszynowo. Bierzemy każdy kafelek i przypisujemy mu numer (01-11). Za pomocą rakiety języka programowania będzie to wyglądać tak

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

Co odpowiada w powyższej tabeli autorstwa Rolfesena. Teraz zobaczmy trywialne zadanie. Jeszcze raz za pomocą rakiety$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])

To dałoby nam trywialne zadanie, którym byłby trywialny stół, który miałby tylko pierwszy węzeł $3_1$

Więc teraz, kiedy ustaliliśmy, jaki powinien być wynik. Jak teraz radzimy sobie z generowaniem problemu?

Wiemy zatem, że w izotopii otoczenia można przejść do innego schematu węzłów, biorąc pod uwagę inny schemat węzłów w skończonym zestawie ruchów Reidmeistera. Więc wygenerujmy dwa losowe linki. Zadanie, które wtedy definiujemy, otrzymuje dwa losowe łącza. Chcę, abyś wykazał, że są one równoważne poprzez wyliczenie każdego możliwego węzła, który można wyrazić, lub pokazanie, że nie są one równoważne, podając mi zestaw stanów lub ścieżek do znanego węzła w stół.

Sposobem, w którym możemy poprawić szybkość rozpoznawania węzła w tabeli lub nie, jest zbudowanie tabeli mieszającej z indeksami jako wielomian Aleksandra. Każde wystąpienie obliczałoby dla niego wielomian Aleksandra, a jeśli miałyby ten sam wielomian Aleksandra, byłyby dołączane jako element do tej tabeli.

Mam część działającego programu o następującej treści: https://gist.github.com/zitterbewegung/4152b322eef5ecccdcf3502e8220844b