Kwantowe porozumienie bizantyjskie

Bizantyjskie protokoły odporne na błędy to algorytmy odporne na dowolne typy błędów w algorytmach rozproszonych . Bizantyjski protokół porozumienia stanowi zasadniczą część tego zadania. Poniżej opisano kwantową wersję protokołu bizantyjskiego o stałym czasie .

Wstęp

Protokół Porozumienia Bizantyjskiego jest protokołem w przetwarzaniu rozproszonym . Swoją nazwę wzięła od problemu sformułowanego przez Lamporta, Szostaka i Pease’a w 1982 roku, który sam w sobie jest nawiązaniem do problemu historycznego. Armia bizantyjska została podzielona na dywizje, a każdą dywizją dowodził generał posiadający następujące właściwości:

Każdy generał jest albo lojalny, albo zdrajcą państwa bizantyjskiego .
Wszyscy generałowie komunikują się poprzez wysyłanie i odbieranie wiadomości.
Są tylko dwie komendy: atak i odwrót.
Wszyscy lojalni Generałowie powinni zgodzić się na ten sam plan działania: atak lub odwrót.
Mały liniowy ułamek złych generałów nie powinien powodować niepowodzenia protokołu (mniej niż $)$

(Zobacz dowód wyniku niemożliwości). Problem jest zwykle równoważnie przedstawiany w postaci dowódcy generała i lojalnych poruczników, przy czym generał jest albo lojalny, albo zdrajcą, i to samo w przypadku poruczników o następujących właściwościach.

Wszyscy lojalni porucznicy wykonują ten sam rozkaz.
Jeśli dowodzący generał jest lojalny, wszyscy lojalni porucznicy wykonują rozkazy, które wysyła.
Dokładnie mniej niż $w$ tym dowodzący generałem, to zdrajcy.

Bizantyjska porażka i odporność

Błędy w algorytmie lub protokole można podzielić na trzy główne typy:

Niepowodzenie wykonania kolejnego kroku wykonania w algorytmie: Jest to zwykle określane jako błąd „zatrzymania awaryjnego”.
Przypadkowa awaria prawidłowego wykonania: Nazywa się to „błędem losowym” lub „przypadkowym błędem bizantyjskim”.
Arbitralna awaria, w przypadku której algorytm nie wykonuje poprawnie kroków (zwykle w sprytny sposób przez jakiegoś przeciwnika, aby cały algorytm zawiódł), która obejmuje również dwa poprzednie typy błędów; nazywa się to „błędem bizantyjskim”.

Bizantyjski odporny lub bizantyjski protokół lub algorytm odporny na błędy to algorytm odporny na wszelkiego rodzaju awarie wymienione powyżej. Na przykład, biorąc pod uwagę prom kosmiczny z wieloma nadmiarowymi procesorami, jeśli procesory podają sprzeczne dane, któremu procesorowi lub zestawowi procesorów należy wierzyć? Rozwiązanie można sformułować jako bizantyjski protokół odporny na błędy .

Szkic algorytmu

Naszkicujemy tutaj algorytm asynchroniczny. Algorytm działa w dwóch fazach:

Faza 1 (faza komunikacji):

W tej rundzie wszystkie wiadomości są wysyłane i odbierane.

Protokół rzucania monetą to procedura, która pozwala dwóm stronom A i B, które sobie nie ufają, rzucić monetą, aby wygrać określony przedmiot.

Istnieją dwa rodzaje protokołów rzucania monetą

słabe protokoły rzucania monetą: dwaj gracze A i B początkowo zaczynają bez danych wejściowych i mają obliczyć pewną wartość $\ displaystyle c_ {A}, c_ {B} \ w [0, 1]}$ $c_{{A}},c_{{B}}\in [0,1]$ i móc oskarżyć kogokolwiek o oszustwo. Protokół kończy się sukcesem, jeśli A i B zgadzają się co do wyniku. Wynik 0 jest zdefiniowany jako wygrana A, a 1 jako wygrana B. Protokół ma następujące właściwości:
- ${\ Displaystyle Pr (c_ {A} = c_ {B} = b) = {\ tfrac {1} {2}}}$ $=$ zgadzają się co do wyniku protokołu z dla za $\ displaystyle a, b \ in \{0,1\}}$ .
- Jeśli jeden z graczy jest uczciwy (tj. drugi gracz może dowolnie odstąpić od protokołu w swoich lokalnych obliczeniach), wówczas druga strona wygrywa z największym prawdopodobieństwem. 1 2 + ${\ tfrac {1} 2}}+\epsilon }$ . Innymi słowy, jeśli B jest nieuczciwy, to $\ Displaystyle Pr (c_ {A} = c_ {B} = 1) \ równoważnik {\ tfrac {1 }{2}}+\epsilon }$ , a jeśli A jest nieuczciwy, to ${\ Displaystyle Pr (c_ {A} = c_ {B} = 0) \ równoważnik {\ tfrac {1} {2}} + \ epsilon}$ .
Silny protokół rzucania monetą: w silnym protokole rzucania monetą celem jest zamiast tego wygenerowanie losowego bitu, który jest odchylony od dowolnej konkretnej wartości 0 lub 1. Jest oczywiste, że każdy mocny protokół rzucania monetą ma stronniczość ϵ {\ displaystyle \ $}$ prowadzi do słabego rzutu monetą z tym samym nastawieniem.

Sprawdzalne udostępnianie sekretów

Weryfikowalny protokół udostępniania sekretów : Protokół udostępniania sekretów (n,k) umożliwia zbiorowi n graczy dzielenie się sekretem w taki sposób, że tylko kworum składające się z k lub więcej graczy może odkryć sekret. Gracz dzielący się sekretem (rozdający części sekretu) jest zwykle nazywany krupierem. Sprawdzalny protokół udostępniania sekretów różni się od podstawowego protokołu udostępniania sekretów tym, że gracze mogą sprawdzić, czy ich udziały są spójne nawet w obecności złośliwego dealera.

Protokół zatrzymania awaryjnego

Protokół kwantowy rzut monetą dla gracza. ${\ displaystyle P_ {i}}$

Runda 1 generuje stan GHZ ${\ Displaystyle | \ operatorname {Moneta} _ {i} \ rangle = {\ tfrac {1} {\ sqrt {2}}} | 0,0, \ ldots, 0 \ rangle + {\ tfrac {1} {\ sqrt {2}}} | 1,1, \ ldots, 1 \ rangle}$ na kubitach ${\ displaystyle n}$ i wyślij $część$ $displaystyle k}$ th kubit do gracza zachowującego jedną
Wygeneruj stan ${\ Displaystyle |\ operatorname {Lider} _ {i} \ rangle = {\ tfrac {1} {n ^ {3/2}}} \ suma \ nolimits _ {a = 1} ^ {n ^ {3}} | a, a, \ ldots, a \ rangle}$ na ${\ displaystyle n}$ $obliczeń$ kwantowych spójne z wieloma kubitami), równa superpozycja liczb od . Rozdziel $pomiędzy$ wszystkich graczy
Otrzymuj wiadomości kwantowe od wszystkich graczy i czekaj na następną rundę komunikacji, zmuszając w ten sposób przeciwnika do wyboru, które wiadomości zostaną przekazane.
Runda 2: Zmierz (w standardowej bazie) wszystkie kubity $\ displaystyle \ operatorname {lider} _ {j}}$ Wybierz gracza z najwyższą wartością lidera (remisy rozwiązane arbitralnie) jako „lider” rundy. Zmierz monetę lidera w standardowej podstawie.
Ustaw wyjście protokołu QuantumCoinFlip: $.$ pomiaru monety lidera

Protokół bizantyjski

$.$ z zakresu [0, n-1], a każdy gracz nie może wybrać własnego losowego identyfikatora, ponieważ każdy gracz wybiera losową liczbę $}}$ $}$ dla każdego innego gracza to przy użyciu weryfikowalnego schematu tajnego udostępniania.

$,$ które sekrety zostały prawidłowo udostępnione, sekrety są następnie otwierane i każdemu graczowi się wartość

{\ displaystyle s_ {i} = \ suma \, {s_ {k} ^ {i}} {\ tekst {dla wszystkich tajemnic prawidłowo udostępnionych}} \ mod n }

Wymaga to prywatnych kanałów informacyjnych, więc losowe tajemnice zastępujemy superpozycją ${\ Displaystyle | \ phi \ rangle = {\ tfrac {1} {\ sqrt {n}}} \ suma \ nolimits _ {a = 0} ^ {n-1} | a \ rangle}$ . W którym stan jest kodowany przy użyciu protokołu udostępniania sekretów weryfikowalnego kwantowo (QVSS). Nie możemy rozpowszechniać stanu ${\ displaystyle |\ phi, \ phi, \ ldots \ phi \ rangle},$ ponieważ źli gracze mogą zawalić stan. Aby uniemożliwić złym graczom robienie tego, kodujemy stan za pomocą kwantowego weryfikowalnego udostępniania sekretów (QVSS) i wysyłamy każdemu graczowi jego część sekretu. Tutaj ponownie weryfikacja wymaga Porozumienia Bizantyjskiego, ale wystarczy zastąpienie porozumienia protokołem oceny.

Protokół oceny stopnia

Protokół gradacyjny ma następujące właściwości, korzystając z definicji zawartych w artykule Nieformalnie, protokół transmisji stopniowanej to protokół z wyznaczonym graczem zwanym „dealerem” (tym, który nadaje), w taki sposób, że:

Jeśli krupier jest dobry, wszyscy gracze otrzymają ten sam komunikat.
Nawet jeśli krupier jest zły, jeśli jakiś dobry gracz zaakceptuje wiadomość, wszyscy dobrzy gracze otrzymają tę samą wiadomość (ale mogą ją zaakceptować lub nie).

Mówi się, że protokół P zapewnia stopniowaną transmisję, jeśli na początku protokołu wyznaczony gracz D (zwany krupierem) posiada wartość v, a na końcu protokołu każdy gracz P ja {\ ${ ja}}$ wyprowadza parę $Displaystyle (\ operatorname {wartość} _ {i}, \ operatorname {pewność} _ {i}) }$ w taki sposób, że zachodzą następujące właściwości: $\ Displaystyle (\ forall ja, \ operatorname {pewność siebie} _ {i} \ w \ {0,1,2 \$

Jeśli D jest uczciwy, to ${wartość} _ {i}}$ ${\ displaystyle \ operatorname {pewność siebie} _ {i }} =$ = v i $2$ dla każdego .
Dla dowolnych dwóch uczciwych graczy ${j},}$ $\$ , ${\ Displaystyle \ Vert \ operatorname {pewność} _ {i} - \ operatorname {pewność} _ {j} \ Vert \ równoważnik 1}$ .
(Spójność) Dla dowolnych dwóch uczciwych graczy i $\ Displaystyle P_ {$ $}}$ , jeśli do $operatorname {pewność siebie } _ {i}> 0}$ i $Displaystyle \ operatorname {pewność siebie} _ {j}> 0}$ następnie $\ displaystyle \ operatorname {wartość} _ {i} = \ operatorname {wartość} _ {j$ }

Dla $weryfikacji$ protokołu QVSS gwarantuje, że dla dobrego dealera zostanie zakodowany prawidłowy stan, a dla każdego, ewentualnie określony stan zostanie przywrócony na etapie odzyskiwania. Zauważamy, że dla celów naszego bizantyjskiego protokołu kwantowego rzucania monetą etap odzyskiwania jest znacznie prostszy. Każdy gracz mierzy swój udział w QVSS i wysyła klasyczną wartość do wszystkich pozostałych graczy. Etap weryfikacji gwarantuje z dużym prawdopodobieństwem, że w obecności aż do $wadliwi$ gracze, wszyscy dobrzy gracze odzyskają tę samą klasyczną wartość (która jest tą samą wartością, która wynikałaby z bezpośredniego pomiaru zakodowanego stanu)

Uwagi

W 2007 roku zademonstrowano eksperymentalnie protokół kwantowy Porozumienia Bizantyjskiego, stosując czterofotonowy stan splątania polaryzacyjnego. To pokazuje, że kwantowa implementacja klasycznych protokołów Porozumienia Bizantyjskiego jest rzeczywiście wykonalna.