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

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 $\mathcal C$ (którego rozwiązanie można skutecznie zweryfikować) na inne takie wyzwanie $\Psi(\mathcal C)$ (które jest używane do weryfikacji pracy), tak że

1. Funkcja $\Psi$ jest losowa, z wykorzystaniem pewnej (publicznej) losowej sekwencji $r$ .
2. Rozwiązywanie $\Psi(\mathcal C)$ jest zwykle twarda jak rozwiązywanie $\mathcal C$ .
3. Jeśli rozwiązanie $x$ znajduje się na $\Psi(\mathcal C)$ , a następnie roztwór $\Psi^{-1}(x)$ może być obliczony dla efektywnego pierwotnego prowokacji $\mathcal C$ .
4. Znanie rozwiązania dla nie pomaga w znalezieniu rozwiązania dla . Ψ ( C$\mathcal C$$\Psi(\mathcal 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$\mathcal C$$\Psi(\mathcal 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.$\mathcal 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 ) $\Psi$$\mathcal C$$(\mathcal C,HASH_r)$$\mathcal C$$\mathcal C$$\Psi(\mathcal C)$$HASH_r$$\Psi(\mathcal C)$$\mathcal C$

( 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.$\Psi(\mathcal{C})$$\mathcal{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 tego$\mathcal{C}$

1. (w przeciwnym razie wydaje mi się, że nie jest to naprawdę ważne wyzwanie);$\mathcal{C} \in \mathsf{TFNP} \setminus \mathsf{FP}$
2. najszybszy randomizowany algorytm dla działa w oczekiwanym czasie T w typowym przypadku; i$\mathcal{C}$$T$
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\}^k$$\mathcal{C}$$k \approx \log_2 T$$s \in \{0,1\}^k$$f(s)$$\mathcal{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).$k \approx \log_2 T$$\{0,1\}^k$$\mathcal{C}$$\mathcal{C}$

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, aby$H : \{0,1\}^* \to \{0,1\}^k$$\Psi_H(\mathcal{C}; r)$$r \in \{0,1\}^\ell$$\ell \gg k$$\Psi_H$$x \in \{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))$$\mathcal{C}$$(r,x)$

Zobaczmy, że spełnia wszystkie Twoje warunki.

1. „Funkcja jest losowa, przy użyciu pewnej (publicznej) losowej sekwencji r .” Czek!$\Psi$$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 k ≈ T jest zasadniczo czas działania algorytmu optymalne dla C .$\Psi(\mathcal{C})$$\mathcal{C}$$\Psi_H(\mathcal{C},r)$$2^k$$2^k \approx T$$\mathcal{C}$
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 $x$$\Psi(\mathcal{C})$$\Psi^{-1}(x)$$\mathcal{C}$$f(H(r,x))$$\mathcal{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 $\mathcal{C}$$\Psi(\mathcal{C})$$\Psi_H(\mathcal{C}; r)$$x$$f(H(r,x))$$\mathcal{C}$$H$$H$jest 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 , $H$$x \in \{0,1\}^k$$\mathcal{C}$$T \approx 2^{k}$$2^{-k}$$\ell \gg k$ 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 \in \{0,1\}^\ell$$H$$\mathcal{C}$$r$$\mathcal{C}$

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 ”.$\mathcal{C}$$k$$x$$(k,x)\in 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.$\Psi(\mathcal{C})$$D$$H$$C$$\textrm{Data}(k,x)$$(k,x)\in 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 .$\Psi(\mathcal{C})$$(k,x)$$k$$(k,x)\in D$$H(k||x||\textrm{Data}(k,x))<C$

Zbadajmy teraz, w jaki sposób problem spełnia wymagania 1-4.$\Psi(\mathcal{C})$

1. Musimy założyć, że jest już zrandomizowany, aby SLT spełniał tę właściwość.$\mathcal{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 $\Psi(\mathcal{C})$$\mathcal{C}$$\mathcal{C}$$\Psi(\mathcal{C})$$(k,x)\in D$ . Dlatego, ponieważ stałaCjest dokładnie dostrajana, trudnośćΨ(C)jest również dostrajana precyzyjnie.$\frac{2^{n}}{C}$$C$$\Psi(\mathcal{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 ) ) < $\Psi(\mathcal{C})$$\mathcal{C}$$\Psi(\mathcal{C})$$(k,x)$$(k,x)\in D$$H(k||x||\textrm{Data}(k,x))<C$lub nie dopóki nie obliczysz i nie możesz obliczyć danych ( k , x ), chyba że zweryfikujesz, że dane ( k , x ) ∈ D ).$\textrm{Data}(k,x)$$\textrm{Data}(k,x)$$\textrm{Data}(k,x)\in 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 | $\Psi(\mathcal{C})$$\mathcal{C}$$(k,x)$$(k,x)\in D$$(k,x)$$(k,x)\in 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||\textrm{Data}(k,x))<C$$(k,x)\in D$$H(k||x||\textrm{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)\in D$$(k,x)\in D$$(k,x)\in D$$\Psi(\mathcal{C})$$\mathcal{C}$

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

4. może, ale nie musi, spełniać warunek 4 w zależności od konkretnego problemu.$\Psi(\mathcal{C})$$4$

$\textbf{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 .$\mathcal{C}$$\Psi(\mathcal{C})$$\mathcal{C}$$\Psi(\mathcal{C})$$\mathcal{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 .$\mathcal{C}$$\mathcal{C}$$\mathcal{C}$$\mathcal{C}$$A$

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 .$A$$PC$$PC$

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.$PC$$PC$

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

3. 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 $\mathcal{C}$$\mathcal{C}$$\mathcal{C}$$\mathcal{C}$(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$\Psi(\mathcal{C})$$(k,x)$ ale gdzie H ( k | | x | | Dane ( k , x ) ) ≥ C oraz algorytm znajdowania bliskich braków dla Ψ ( C$(k,x)\in D$$H(k||x||\textrm{Data}(k,x))\geq C$$\Psi(\mathcal{C})$będzie taki sam jak algorytm znajdowania rozwiązań dla .$\Psi(\mathcal{C})$

4. 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.$P$$e^{-\lambda x}$$\lambda$$P$