Czy każde wyzwanie obliczeniowe można przekształcić w proof-of-work?

20

Pozornie bezcelowość wydobywania kryptowalut wywołała pytanie o przydatne alternatywy, zobacz te pytania na Bitcoin , CST , MO . Zastanawiam się, czy istnieje algorytm, który może przekonwertować praktycznie każde wyzwanie obliczeniowe C (którego rozwiązanie można skutecznie zweryfikować) na inne takie wyzwanie Ψ(C) (które jest używane do weryfikacji pracy), tak że

  1. Funkcja Ψ jest losowa, z wykorzystaniem pewnej (publicznej) losowej sekwencji r .
  2. Rozwiązywanie Ψ(C) jest zwykle twarda jak rozwiązywanie C .
  3. Jeśli rozwiązanie x znajduje się na Ψ(C) , a następnie roztwór Ψ1(x) może być obliczony dla efektywnego pierwotnego prowokacji C .
  4. Znanie rozwiązania dla nie pomaga w znalezieniu rozwiązania dla . Ψ ( C )CΨ(C)

4 '(aktualizacja). Jak zauważył Noah w komentarzu, poprzedni warunek powinien zostać wzmocniony do wymagania, aby wstępne przetwarzanie również nie dawało żadnej korzyści w rozwiązywaniu . Ψ ( C )CΨ(C)

Ten ostatni warunek jest wymagane, tak że nikt nie może być wprowadzone do korzystnej sytuacji, ponieważ tylko oni wiedzą roztwór . Korzystając z tej metody, ludzie mogą zgłaszać problemy obliczeniowe, które chcą rozwiązać, a organ centralny może wybrać niektóre godne rozwiązania (np. Znalezienie obcych kontra złamanie hasła). Zauważ, że nie wydaje się to problemem, jeśli rozwiązanie zajmie nawet tydzień (chyba ci kosmici nie potrafią się tak dobrze ukrywać;), ponieważ może to skutkować większą nagrodą za rozwiązanie. W każdym razie tematy te nie są związane z rozwiązaniem mojego teoretycznego problemu, ale oczywiście chętnie omawiam je w komentarzach / na forum.C

Możliwym rozwiązaniem byłoby: odwzorowuje na , to znaczy, aby rozwiązać i inne trudne obliczeniowo wyzwanie. Jednym z problemów jest to, że znajomość rozwiązania sprawia, że ​​rozwiązanie nieco łatwiejsze (o ile łatwiejsze zależy od trudności ). Inną kwestią jest to, że stała się trudniejsza niż .C ( C , H A S H r ) C C Ψ ( C ) H A S H r Ψ ( C ) CΨC(C,HASHr)CCΨ(C)HASHrΨ(C)C

domotorp
źródło
3
Może to może być istotne: eprint.iacr.org/2017/203.pdf
Andreas Björklund
3
Jaka jest różnica między „wyzwaniem obliczeniowym” a „wyzwaniem sprawdzającym pracę”?
Lub Meir
2
Jasne, ale sama definicja dowodów pracy zwykle wymaga rozważenia kilku wyzwań, ponieważ podstawową właściwością, która je definiuje, jest brak amortyzacji. To jest powód, dla którego wykonano takie prace jak eprint.iacr.org/2017/203.pdf - potrzebujesz gwarancji nieumiejętności dla prawie wszystkich aplikacji PoW, zwłaszcza kryptowalut. W każdym razie, szukasz rozwiązania, które można zweryfikować publicznie, czy może wystarczyłoby rozwiązanie weryfikowane prywatnie? Czy chcesz praktycznie efektywnego schematu, czy jesteś w porządku z rozwiązaniem teoretycznym?
Geoffroy Couteau
5
@domotorp, dlaczego uważasz, że eprint.iacr.org/2017/203.pdf nie ma związku z twoim pytaniem?
Alon Rosen
5
Mimo że nie zapewnia on redukcji w stosunku do problemu najgorszego przypadku w P, dokument daje użyteczny PoW w oparciu o szeroki zestaw problemów. W szczególności każdy problem, który można zredukować do wektorów ortogonalnych (OV), w tym wszystkie problemy z grafem, które można ustalić w logice pierwszego rzędu. Dotyczy to również problemu k-OV (przypuszczalnie wymagającego mniej więcej czasu n ^ k), a także innych problemów ze świata drobnoziarnistej złożoności. Więc chociaż może nie tak ogólne, jak można się spodziewać, wyniki są nadal dość ogólne. A w przypadku problemów, o których wspomniałem powyżej, właściwości 1-4 są rzeczywiście spełnione.
Alon Rosen

Odpowiedzi:

8

( Uwaga : Andreas Björklund zasugerował rozwiązanie w komentarzach, które moim zdaniem jest lepsze niż to opisane poniżej. Patrz http://eprint.iacr.org/2017/203 , autor: Ball, Rosen, Sabin i Vasudevan. Krótko mówiąc, dają dowody pracy oparte na problemach takich jak wektory ortogonalne, których twardość jest dobrze zrozumiana i do których wiele problemów (np. k-SAT) można stosunkowo skutecznie zredukować Ich instancja PoW jest tak trudna jak najgorszy przypadek Wektory, nawet jeśli instancja wejściowa C jest łatwa, dzięki czemu unikają poważnej wady rozwiązania opisanego poniżej.Ψ(C)C

Rozwiązanie opisane poniżej może skorzystać z jego prostoty --- może być opisane nie-ekspertowi --- ale wydaje mi się, że jest o wiele mniej interesujące teoretycznie.)

Rozwiązanie jest możliwe, jeśli przyjmie się silne założenie, że „najszybszy algorytm dla jest zasadniczo losowy” (i jeśli modelujemy funkcję skrótu kryptograficznego jako losową wyrocznię). Jednym ze sposobów sformalizowania tego jest powiedzenie tegoC

  1. (w przeciwnym razie wydaje mi się, że nie jest to naprawdę ważne wyzwanie);CTFNPFP
  2. najszybszy randomizowany algorytm dla działa w oczekiwanym czasie T w typowym przypadku; iCT
  3. istnieje skutecznie obliczalną funkcji z { 0 , 1 } K do dziedziny rozwiązań C dla k log 2 T tak, że zawsze istnieje s { 0 , 1 } k z F ( y ) Rozwiązaniem C .f{0,1}kCklog2Ts{0,1}kf(s)C

Należy zauważyć, że przy założeniu, że sugeruje, że przeszukiwanie brute-force z { 0 , 1 } k jest zasadniczo algorytm optymalne dla C . Jest to więc dość mocne założenie. Z drugiej strony, jeśli C nie spełnia tych właściwości, trudno mi sobie wyobrazić, że spełniam oba warunki (2) i (4).klog2T{0,1}kCC

Następnie, biorąc pod uwagę funkcję skrótu , którą modelujemy jako losową wyrocznię, definiujemy Ψ H ( C ; r ) w następujący sposób, gdzie r { 0 , 1 } dla niektórych £ -l » k jest przypadkowy wejście do * F H . Celem jest wyprowadzenie x { 0 , 1 } tak, abyH:{0,1}{0,1}kΨH(C;r)r{0,1}kΨHx{0,1} jest rozwiązaniem C . Innymi słowy, ( r , x ) powinien mieszać z „dobrymi losowymi monetami” dla powyższego algorytmu.f(H(r,x))C(r,x)

Zobaczmy, że spełnia wszystkie Twoje warunki.

  1. „Funkcja jest losowa, przy użyciu pewnej (publicznej) losowej sekwencji r .” Czek!Ψr
  2. „Rozwiązywanie jest zazwyczaj tak samo trudne jak rozwiązywanie C ”. Należy zauważyć, że proste losowo algorytm * F H ( C , r ) przebiega w przewidywany czas co najwyżej 2 k plus wielomianu ogólnych, i założenie 2 kT jest zasadniczo czas działania algorytmu optymalne dla C .Ψ(C)CΨH(C,r)2k2kTC
  3. „Jeżeli roztwór znajduje się na * F ( C ) , a następnie roztwór * F - 1 ( x ) może być obliczony dla efektywnego pierwotnego prowokacji C ”. Można tego dokonać obliczając f ( H ( r , x ) ) , który z założenia jest rozwiązaniem C.xΨ(C)Ψ1(x)Cf(H(r,x))C
  4. „Znanie rozwiązania dla nie pomaga w znalezieniu rozwiązania dla Ψ ( C ) .” Z definicji, rozwiązując Ψ H ( C , R ) wymaga znalezienia X takich, że f ( H ( r , x ) ) jest rozwiązaniem C . Ponieważ modelowaliśmy H jako losową wyrocznię, możemy obniżyć dolną granicę oczekiwanego czasu działania dowolnego algorytmu, który rozwiązuje ten problem, poprzez optymalną oczekiwaną złożoność zapytania problemu, w którym HCΨ(C)ΨH(C;r)xf(H(r,x))CHHjest podane przez czarną skrzynkę i jesteśmy proszeni o znalezienie rozwiązania tego samego problemu. Ponownie, ponieważ jest wyrocznią losową, oczekiwana złożoność zapytania jest odwrotnością ułamka elementów x { 0 , 1 } k, które są rozwiązaniami (aż do stałego współczynnika). Z założenia optymalny oczekiwany czas działania dowolnego algorytmu dla C wynosi T 2 k , co oznacza, że ​​ta frakcja nie może być znacznie większa niż 2 - k . Ponieważ k i r { 0 , 1Hx{0,1}kCT2k2kk jest wybierany równomiernie losowo, jest to nawet prawdą w przypadku przetwarzania wstępnego, które może zależeć od H i C (ale nie r ), a w szczególności jest prawdą, nawet jeśli znamy rozwiązanie dla C z góry.r{0,1}HCrC
Noah Stephens-Davidowitz
źródło
To bardzo miłe rozwiązanie. Jedynym miejscem, w którym widzę możliwość poprawy, jest stan (2). Dla wielu problemów , są algorytmy c n czas na c < 2 . Byłoby miło, gdyby coś takiego można było zachować, ale nie jestem pewien, czy da się to zrobić. Z pewnością twoja metoda jest już lepsza od metod stosowanych obecnie w przypadku kryptowalut! NPcnc<2
domotorp
W rzeczywistości może nawet niewiele trzeba zmienić w blockchain. Tylko społeczność może zgodzić się, że w danym momencie należy dołączyć do łańcucha bloków, którego skrót rozwiązuje jakikolwiek problem praktyczny. W rzeczywistości może standardowy blockchain może być kontynuowany, a może to być niezależne wyzwanie solo. Być może na rynku taka instancja solo będzie warta więcej niż tradycyjne monety, tak jak Rogue One jest lepszy niż sw7 lub sw8. x
domotorp
Cieszę się że to lubisz :). Chcę tylko wyjaśnić, że chociaż moje warunki na sugerują, że „przeszukiwanie z użyciem siły brutalnej w pewnej przestrzeni wyszukiwania jest zasadniczo optymalne”, nie oznaczają one, że przeszukiwanie z użyciem siły brutalnej nad pierwotną przestrzenią wyszukiwania jest zasadniczo optymalne. Na przykład w przypadku SAT nie jest to to samo, co wymaganie najszybszego algorytmu do uruchomienia za 2 n czasu. C2n
Noah Stephens-Davidowitz
W przypadku składu - na przykład problem obliczeniowy dopuszcza definicję problemu, w której problem obliczeniowy może składać się z mniejszych problemów, których rozwiązanie jest łatwiejsze, a istnieje rozwiązanie, które nie jest oparte na składzie, nie uwzględniałoby tego ?
user3483902
Myślę, że innym problemem związanym z tym rozwiązaniem jest to, na co zwróciłeś uwagę w komentarzu do mojego pytania, a mianowicie, że jeśli ktoś może skutecznie przetworzyć w wydajny sposób, może uzyskać poważną przewagę. Myślę, że to dość delikatna kwestia. Wyobraź sobie, że zgłaszam problem, którego rozwiązanie (w standardowym formacie) można sprawdzić n- raz, ale mam tajną metodę, aby to sprawdzić Cn raz. Daje mi to dużą zaletę przy rozwiązywaniuΨ(C). nΨ(C)
domotorp
1

Poniższą prostą technikę, którą nazywam techniką loterii rozwiązań (SLT), można zastosować w połączeniu z innymi technikami (np. Z wieloma problemami POW, techniką wymienioną w odpowiedzi Noah Stephens-Davidowitz itp.), Aby pomóc przekształcić obliczeniowe wyzwania w realny dowód problemów z pracą. SLT pomaga rozwiązać problemy z problemami wydobywania kryptowaluty innymi niż warunki 1-4.

Załóżmy, że jest wyzwaniem obliczeniowym formy „znajdź odpowiednią wartość skrótu k wraz z łańcuchem x takim, że ( k , x ) D ”.Ckx(k,x)D

Problem Konfiguracja: Załóżmy, że D stanowi zestaw, H jest kryptograficznej funkcji kodującej i C pewne stałe. Załóżmy ponadto, że Dane ( k , x ) są informacją, którą łatwo uzyskać po stwierdzeniu, że ( k , x ) D, ale której nie można uzyskać inaczej.Ψ(C)DHCData(k,x)(k,x)D

Problem Cel: znaleźć parę ( k , x ), tak, że K jest odpowiednia mieszania i w której ( k , x ) D i gdzie H ( k | | x | | danych ( k , x ) ) < C .Ψ(C)(k,x)k(k,x)DH(k||x||Data(k,x))<C

Zbadajmy teraz, w jaki sposób problem spełnia wymagania 1-4.Ψ(C)

  1. Musimy założyć, że jest już zrandomizowany, aby SLT spełniał tę właściwość.C

2-3. zwykle staje się trudniejsze niż C i jest to dobra rzecz. Trudność problemu z korektą pracy musi być dokładnie dostrojona, ale pierwotny problem C może, ale nie musi, mieć trudny do dostrojenia poziom trudności (pamiętaj, że trudność w wydobyciu Bitcoina jest korygowana co dwa tygodnie). Trudność problemu Ψ ( C ) jest równa trudności ze znalezieniem odpowiedniego ( k , x ) D pomnożonego przez 2 nΨ(C)CCΨ(C)(k,x)D . Dlatego, ponieważ stałaCjest dokładnie dostrajana, trudnośćΨ(C)jest również dostrajana precyzyjnie.2nCCΨ(C)

Mimo że problem jest trudniejszy niż pierwotny problem C , prawie cała praca nad rozwiązaniem problemu Ψ ( C ) zostanie poświęcona na po prostu znalezienie pary ( k , x ) z ( k , x ) D zamiast obliczania skrótów (nie można obliczyć, czy H ( k | | x | | Data ( k , x ) ) < CΨ(C)CΨ(C)(k,x)(k,x)DH(k||x||Data(k,x))<Club nie dopóki nie obliczysz i nie możesz obliczyć danych ( k , x ), chyba że zweryfikujesz, że dane ( k , x ) D ).Data(k,x)Data(k,x)Data(k,x)D

Oczywiście fakt, że jest trudniejszy niż C, przedstawia pewne nowe obawy. Przydatnym problemem jest najprawdopodobniej przypadek, w którym chciałoby się przechowywać pary ( k , x ) gdzie ( k , x ) D w jakiejś bazie danych. Aby jednak otrzymać nagrodę za blok, górnik musi ujawnić tylko parę ( k , x ), gdzie ( k , x ) D i H ( k | |Ψ(C)C(k,x)(k,x)D(k,x)(k,x)D zamiast wszystkich par ( k , x ) D niezależnie od tego, czy H ( k | | x | | Data ( k , x ) ) < C czy nie. Jednym z możliwych rozwiązań tego problemu jest po prostu ujawnienie przez górników wszystkich par ( k , x ) gdzie ( k , x )H(k||x||Data(k,x))<C(k,x)DH(k||x||Data(k,x))<C(k,x) z grzeczności. Górnicy będą mieli również możliwość odrzucenia łańcuchy jeśli górnicy nie napisali ich sprawiedliwego podziału par ( k , x ) D . Być może należy policzyć liczbę par ( k , x ) D do obliczeń, kto ma również najdłuższy prawidłowy łańcuch. Jeśli większość górników pisać swoje rozwiązania, a następnie proces rozwiązywania * F ( C ) będzie produkować tak wiele rozwiązań, jak proces rozwiązywania C .(k,x)D(k,x)D(k,x)DΨ(C)C

W scenariuszu, w którym górnicy umieszczają wszystkie pary , Ψ ( C ) spełniłyby ducha warunków 2-3.(k,x)DΨ(C)

  1. może, ale nie musi, spełniać warunek 4 w zależności od konkretnego problemu.Ψ(C)4

Other Advantages of this technique:

SLT oferuje inne zalety niż warunki 1-4, które są pożądane lub konieczne w przypadku problemu z próbą pracy.

  1. Poprawa równowagi bezpieczeństwa / wydajności: SLT pomoże w przypadku, gdy może być zbyt łatwy do rozwiązania lub zbyt trudny do zweryfikowania. W ogóle, Ψ ( C ) jest znacznie trudniejsze do rozwiązania niż C , ale Ψ ( C ) jest tak łatwe do sprawdzenia jak C .CΨ(C)CΨ(C)C

  2. Usunięcie zepsutego / niepewnego problemu: SLT można wykorzystać do algorytmicznego usuwania złych problemów z POW w krypto-walucie z zapasowym problemem z POW i wieloma problemami z POW. Załóżmy, że jednostka odnajduje bardzo szybki algorytm rozwiązywania problemu . Wówczas taki problem nie jest już odpowiednim sprawdzianem pracy i powinien zostać usunięty z kryptowaluty. Kryptowaluta musi zatem mieć algorytm, który usuwa C z kryptowaluty, ilekroć ktoś opublikował algorytm, który zbyt szybko rozwiązuje problem C, ale w przeciwnym razie nigdy nie usuwa problemu C. Oto zarys takiego algorytmu usunięciu problemu wykorzystywane w celu usunięcia problemu, który będziemy nazywać Problem A .CCCCA

za. Alice płaci dużą opłatę (opłata pokryje koszty, które górnicy ponoszą za weryfikację algorytmu), a następnie umieszcza algorytm, który nazwiemy Algorytmem K, który łamie Problem do łańcucha bloków. Jeżeli algorytm K opiera się na dużej ilości wstępnie obliczonych danych P C , a następnie stanowisk Alice korzeń Merkle tego wstępnie obliczonych danych P C .APCPC

b. Przypadkowe przypadki problemu A są wytwarzane przez Blockchain. Alicja następnie posty części wstępnej obliczana danych, które są potrzebne dla algorytmu K do pracy poprawnie wraz z ich Merkle oddziału w celu udowodnienia, że dane faktycznie pochodzi od . Jeśli algorytm Alice szybko zasilony wstępnie obliczonymi danymi P C , problem zostanie usunięty, a Alice otrzyma nagrodę za opublikowanie algorytmu, który usuwa problem z łańcucha bloków.PCPC

Ta procedura usuwania problemów jest kosztowna obliczeniowo dla górników i walidatorów. Jednak SLT usuwa większość trudności obliczeniowych tej techniki, dzięki czemu można ją zastosować w razie potrzeby w krypto-walucie (przypadki, w których ta technika jest używana, będą prawdopodobnie dość rzadkie).

  1. Pule wydobywcze są bardziej realne: w kryptowalutach często bardzo trudno jest zdobyć nagrodę blokową. Ponieważ nagrody blokowe są bardzo trudne do zdobycia, górnicy często wydobywają rzeczy zwane pulami wydobywczymi, w których górnicy łączą swoje zasoby w rozwiązywaniu problemu i w których dzielą nagrodę blokową proporcjonalnie do liczby „bliskich braków”, którą znaleźli . Ewentualny problem dla jest to, że może to być trudne do uzyskania jakościową pojęcie tego, co stanowi jako „koło miss” za problem C i algorytm znalezieniem w pobliżu Miss może być różny od algorytmu rozwiązywania C . Ponieważ górnicy z puli będą poszukiwać bliskich nieudanych prób, mogą nie być bardzo skuteczni w rozwiązywaniu problemu C.CCCC(a zatem niewiele osób dołączy do kopalni). Jednak dla istnieje wyraźne pojęcie bliskiego miss, a mianowicie bliskie miss to para ( k , x ), w którejΨ(C)(k,x) ale gdzie H ( k | | x | | Dane ( k , x ) ) C oraz algorytm znajdowania bliskich braków dla Ψ ( C )(k,x)DH(k||x||Data(k,x))CΨ(C)będzie taki sam jak algorytm znajdowania rozwiązań dla .Ψ(C)

  2. Bezproblemowość postępu: Mówi się, że problem próby pracy jest wolny od postępu, jeśli ilość czasu potrzebna jednostce lub grupie jednostek na znalezienie następnego bloku w łańcuchu bloków jest zgodna z rozkładem wykładniczym e - λ x, gdzie stała λ jest wprost proporcjonalna do ilości mocy obliczeniowej, że jednostka z wykorzystaniem rozwiązania problemu P . W przypadku problemów związanych z wydobywaniem kryptowalut wymagana jest płynność postępu, aby górnicy mogli otrzymać nagrodę blokową proporcjonalną do ich mocy wydobywczej w celu uzyskania decentralizacji. SLT z pewnością pomaga problemom z kopaniem osiągnąć postęp w chudości.PeλxλP

Joseph Van Name
źródło