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

23

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?

Joshua Herman
źródło
8
Być może zainteresuje Cię to podobne pytanie dotyczące bitcoinów SE: Czy istnieje sposób na skonfigurowanie systemów proof of work bez wykonywania bezużytecznej pracy?
Artem Kaznatcheev
@ArtemKaznatcheev Dzięki źle patrzę na to.
Joshua Herman

Odpowiedzi:

7

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.G0G1Vi{0,1}π SVπ(Gi)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 , π )sol0G1H:{0,1}{0,1}kyH.y(ja,π)tak, że .H.(π(solja))=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 0G 1 może być dwa razy większa duży niż, jeśli G 0G 1 .H.ksol0sol1sol0sol1sol0sol1

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.S.H.ZA256y00

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

  • 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 )bdoZ=H.(dob)

  • Górnik oblicza wybrać ( i , π )W.=Zmore2)V.!(i,π)

  • Górnik potwierdza, że - to znaczy, aby potwierdzić, że losowo wybrany π nie jest dowodem na to, że wykresy są izomorficzneπ(Gi)G1iπ

  • Jeśli nie, górnik oblicza skrót W=H(π(Gi))

  • Jeśli zaczyna się od odpowiedniej liczby 0 , górnik „wygrywa”, publikując ( c , B )W0(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 „sZ=H(cB)(i,π)W=H(π(Gi))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.G0G1

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

[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.NPAMAMp0pH(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.AMcoAM

[Kup11] Greg Kuperberg. Wiązanie jest w , moduł GRH, 2011.NP

Znaki
źródło
1
Co z losowymi ruchami Markowa? mathworld.wolfram.com/MarkovMoves.html
Joshua Herman
Można również uważać węzły za wykresy, które są podpisanymi wykresami, które mają cztery wartościowości. Musisz więc egzekwować to ograniczenie na G1 i G2
Joshua Herman
Oto redukcja koloru quandle do instancji SAT. arxiv.org/pdf/1505.06595.pdf
Joshua Herman
tak, określa, czy masz przekroczenie, czy przekroczenie granicy. Zobacz en.wikipedia.org/wiki/Medial_graph
Joshua Herman
Czy pomogłoby to w testowaniu pod kątem braku oryginalności? Wygląda na to, że musisz tylko stworzyć wykres lamana, który jest łatwy w 2D (a sęki są wykresami płaskimi). www3.cs.stonybrook.edu/~jgao/CSE590-fall05/notes/lecture3.pdf
Joshua Herman
1

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.

Stół Rolfsen Knot

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. Stół do mozaiki węzłów

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

Kafelki mozaikowe

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 MNM
  3. Musi być izotopowy w otoczeniu względem węzła , który wysyłamyK
  4. Musi mieć zestaw operacji liczności O n, które pokazują, że jest on izotopem otoczenia względem węzła KOOnK
  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ą rakiety31

(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ł 31

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

Joshua Herman
źródło
3
Biorąc pod uwagę dwa duże, losowe łącza, jest mało prawdopodobne, aby były one równoważne. I prawdopodobnie nie będą miały tego samego wielomianu Aleksandra, co pozwoli ci udowodnić, że nie są one równoważne w czasie wielomianowym. Zadanie jest więc przez większość czasu łatwe. Podejrzewam, że bardzo mało prawdopodobne jest wygenerowanie naprawdę trudnego przykładu poprzez losowe linki.
Peter Shor
@PeterShor tak, rozpoznaję to. Nie sądzę, że dobrze to sformułowałem, ale wykonuję dowolną liczbę tych zadań, gdy je generuję, aby zwiększyć twardość. Nawet jeśli tak się stanie, czy nie utrudni to?
Joshua Herman
@PeterShor Ponadto certyfikat nie tylko potwierdza, że ​​oba węzły nie są równoważne, ale chcę, aby zestaw węzłów przesuwał się do węzła lub do węzła, który można obliczyć, że nie jest on izotopowy w otoczeniu (taki jak koniczyna).
Joshua Herman
1
W przypadku „znanego węzła w tabeli”, czy planujesz mieć stół wielkości wykładniczej? Ponieważ istnieje wykładniczo wiele węzłów o danym rozmiarze.
Peter Shor
Tak i nie. Rozmiar każdego wystąpienia użycia knothash jest uzależniony od liczebności numeru operacji, a także od prawidłowego wystąpienia węzła lub łącza zakodowanego jako mozaika węzła. Planuję używać tych parametrów, aby ograniczyć liczbę prawidłowych rozwiązań, aby twardość problemu była również parametrem.
Joshua Herman