Kvantbysantinsk överenskommelse

Bysantinska feltoleranta protokoll är algoritmer som är robusta mot godtyckliga typer av fel i distribuerade algoritmer . Det bysantinska avtalsprotokollet är en väsentlig del av denna uppgift. Konstant-tid kvantversionen av det bysantinska protokollet beskrivs nedan.

Introduktion

Det bysantinska avtalet är ett protokoll för distribuerad datoranvändning . Den har fått sitt namn från ett problem formulerat av Lamport, Shostak och Pease 1982, som i sig är en referens till ett historiskt problem. Den bysantinska armén var uppdelad i divisioner där varje division leddes av en general med följande egenskaper:

• Varje general är antingen lojal eller en förrädare mot den bysantinska staten .
• Alla generaler kommunicerar genom att skicka och ta emot meddelanden.
• Det finns bara två kommandon: attack och reträtt.
• Alla lojala generaler bör komma överens om samma handlingsplan: attack eller reträtt.
• En liten linjär bråkdel av dåliga generaler bör inte orsaka att protokollet misslyckas (mindre än en ${\tfrac {1}{3}}$ bråkdel).

(Se för beviset på omöjlighetsresultatet). Problemet återges vanligtvis på samma sätt i form av en befallande general och lojala löjtnanter, där generalen antingen är lojal eller en förrädare och samma sak för löjtnanterna med följande egenskaper.

• Alla lojala löjtnanter utför samma order.
• Om den befälhavande generalen är lojal, lyder alla lojala löjtnanter ordern som han skickar.
• En strikt mindre än ${\tfrac {1}{3}}$ bråkdel inklusive den befallande generalen är förrädare.

Bysantinskt misslyckande och motståndskraft

Fel i en algoritm eller protokoll kan kategoriseras i tre huvudtyper:

1. Ett misslyckande att ta ytterligare ett exekveringssteg i algoritmen: Detta brukar kallas ett "fail stop"-fel.
2. Ett slumpmässigt misslyckande att utföra korrekt: Detta kallas ett "slumpmässigt fel" eller "slumpmässigt bysantinskt" fel.
3. Ett godtyckligt misslyckande där algoritmen misslyckas med att utföra stegen korrekt (vanligtvis på ett smart sätt av någon motståndare för att få hela algoritmen att misslyckas) som också omfattar de två föregående typerna av fel; detta kallas ett "bysantinskt fel".

Ett bysantinskt motståndskraftigt eller bysantinskt feltolerant protokoll eller algoritm är en algoritm som är robust för alla typer av fel som nämns ovan. Till exempel, givet en rymdfärja med flera redundanta processorer, om processorerna ger motstridiga data, vilka processorer eller uppsättningar av processorer ska man tro? Lösningen kan formuleras som ett bysantinskt feltolerant protokoll.

Skiss av algoritmen

Vi kommer här att skissa den asynkrona algoritmen Algoritmen fungerar i två faser:

• Fas 1 (Kommunikationsfas):

Alla meddelanden skickas och tas emot i denna omgång.

Ett myntvändningsprotokoll är en procedur som tillåter två parter A och B som inte litar på varandra att kasta ett mynt för att vinna ett visst föremål.

Det finns två typer av myntvändningsprotokoll

• svaga myntvändningsprotokoll: De två spelarna A och B börjar initialt utan inmatning och de ska beräkna något värde $c_{A},c_{B}\i [0, 1]$ och kunna anklaga vem som helst för fusk. Protokollet är framgångsrikt om A och B är överens om resultatet. Resultatet 0 definieras som A-vinnande och 1 som B-vinnande. Protokollet har följande egenskaper:
  • Om båda spelarna är ärliga (de följer protokollet) kommer de överens om resultatet av protokollet $c_{A}=c_{B}$ med $Pr(c_{A}=c_{B}=b)={\tfrac {1}{2}}$ för $a,b\in \{0,1\}$ .
  • Om en av spelarna är ärlig (dvs den andra spelaren kan avvika godtyckligt från protokollet i sin lokala beräkning), så vinner den andra parten med sannolikhet högst 1 2 + ϵ {\ ${1}{ 2}}+\epsilon }$ . Med andra ord, om B är oärlig, då $Pr(c_{A}=c_{B}=1)\leq {\tfrac {1 }{2}}+\epsilon$ , och om A är oärlig, då $Pr(c_{A}=c_{B}=0)\ leq {\tfrac {1}{2}}+\epsilon$ .
• Ett starkt myntvändningsprotokoll: I ett starkt myntvändningsprotokoll är målet istället att producera en slumpmässig bit som är förspänd från ett visst värde 0 eller 1. Det är klart att vilket starkt myntvändningsprotokoll med bias ϵ {\displaystyle \ $}$ leder till svag myntslagning med samma bias.

Verifierbar hemlighetsdelning

• Ett verifierbart hemligt delningsprotokoll : Ett (n,k) hemligt delningsprotokoll tillåter en uppsättning av n spelare att dela en hemlighet, s så att endast ett kvorum på k eller fler spelare kan upptäcka hemligheten. Spelaren som delar (fördelar de hemliga bitarna) hemligheten brukar kallas dealern. Ett verifierbart hemligt delningsprotokoll skiljer sig från ett grundläggande hemligt delningsprotokoll genom att spelare kan verifiera att deras andelar är konsekventa även i närvaro av en illvillig återförsäljare.

Fail-stop-protokollet

Protokoll kvantmyntvändning för spelare $P_{i}$

1. Omgång 1 genererar GHZ-tillståndet $|\mathrm {Coin} _{i}\rangle ={\tfrac {1}{\sqrt {2}}}|0,0,\ldots ,0\rangle + {\tfrac {1}{\sqrt {2}}}|1,1,\ldots ,1\rangle$ på $n$ qubits och skicka ${\displaystyle k}:$ e qubit till ${\ displaystyle k}:$ e spelaren som behåller en del
2. Generera staten $|\mathrm {Leader} _{i}\rangle ={\tfrac {1}{n^{3/2}}}\sum \nolimits _{a=1} ^{n^{3}}|a,a,\ldots ,a\rangle$ på $n$ qudits (kvantberäkningskomponenter konsekventa av flera qubits), en lika stor överlagring av talen mellan 1 och $n^{3}$ . Fördela de $n$ qudits mellan alla spelare
3. Ta emot kvantmeddelanden från alla spelare och vänta på nästa kommunikationsomgång, vilket tvingar motståndaren att välja vilka meddelanden som skickades.
4. Omgång 2: Mät (i standardbasen) alla $\mathrm {Leader} _{j}$ qubits som tagits emot i omgång I. Välj spelaren med det högsta ledarvärdet (banden brutits godtyckligt) som omgångens "ledare". Mät ledarens mynt i standardbasen.
5. Ställ in utdata från QuantumCoinFlip-protokollet: $v_{i}$ = mätresultat av ledarens mynt.

Det bysantinska protokollet

För att generera ett slumpmässigt mynt tilldela varje spelare ett heltal i intervallet [0,n-1] och varje spelare får inte välja sitt eget slumpmässiga ID eftersom varje spelare P k {\displaystyle P_{k}} $slumpmässigt$ tal $s{_{k}^{i}}$ för alla andra spelare $P_{i}$ och distribuerar detta med ett verifierbart hemligt delningsschema.

I slutet av denna fas kommer spelarna överens om vilka hemligheter som delades korrekt, hemligheterna öppnas sedan och varje spelare $P_{i}$ tilldelas värdet

$s_{i}=\summa \,{s_{k}^{i}}{\text{för alla hemligheter korrekt delade}}\mod n$

Detta kräver privata informationskanaler så vi ersätter de slumpmässiga hemligheterna med superpositionen $|\phi \rangle ={\tfrac {1}{\sqrt {n}}}\sum \nolimits _{a=0}^{n-1}|a\rangle$ . I vilket tillståndet kodas med ett kvantverifierbart hemligt delningsprotokoll (QVSS). Vi kan inte fördela staten $|\phi ,\phi ,\ldots \phi \rangle$ eftersom de dåliga spelarna kan kollapsa tillståndet. För att förhindra dåliga spelare från att göra det kodar vi staten med Quantum verifierbar hemlighetsdelning (QVSS) och skickar varje spelare sin del av hemligheten. Även här kräver verifieringen bysantinsk överenskommelse, men det räcker att ersätta överenskommelsen med protokollet med betygsgjutning.

Grade-cast protokoll

Ett graderat sändningsprotokoll har följande egenskaper med hjälp av definitionerna i Informellt, ett graderat sändningsprotokoll är ett protokoll med en utsedd spelare som kallas "dealer" (den som sänder) så att:

1. Om dealern är bra får alla spelare samma besked.
2. Även om dealern är dålig, om någon bra spelare accepterar budskapet, får alla bra spelare samma meddelande (men de kanske accepterar det eller inte).

Ett protokoll P sägs uppnå graderad sändning om, i början av protokollet, en utsedd spelare D (kallad dealer) har ett värde v, och i slutet av protokollet, varje spelare P i {\ ${ i}}$ matar ut ett par $(\mathrm {value} _{i},\mathrm {confidence} _{i})$ så att följande egenskaper gäller: $(\forall i,\mathrm {confidence} _{i}\in \{0,1,2\})$

1. Om D är ärlig, då $\mathrm {värde} _{i}$ = v och $\mathrm {förtroende} _{i }$ = 2 för varje ärlig spelare $P_{i}$ .
2. För två ärliga spelare $P_{i}$ och $P_{j},$$\vert \mathrm {förtroende} _{i}-\mathrm {förtroende} _{j}\vert \leq 1$ .
3. (Konsistens) För två ärliga spelare $P_{i}$ och $P_{j}$ , om $\mathrm {förtroende } _{i}>0$ och $\mathrm {confidence} _{j}>0$ , sedan $\mathrm {värde} _{i}=\mathrm {värde} _{j}$ .

För $t<{\tfrac {n}{4}}$ garanterar verifieringssteget för QVSS-protokollet att för en bra återförsäljare kommer det korrekta tillståndet att kodas, och att för alla eventuellt felaktiga återförsäljare, något särskilt tillstånd kommer att återhämtas under återhämtningsstadiet. Vi noterar att för syftet med vårt bysantinska kvantmyntflip-protokoll är återhämtningsstadiet mycket enklare. Varje spelare mäter sin andel av QVSS och skickar det klassiska värdet till alla andra spelare. Verifieringsstadiet garanterar, med hög sannolikhet, att i närvaro av upp till $t<{\tfrac {n}{4}}$ felaktiga spelare kommer alla bra spelare att återfå samma klassiska värde (vilket är samma värde som skulle resultera från en direkt mätning av det kodade tillståndet).

Anmärkningar

År 2007 demonstrerades ett kvantprotokoll för bysantinsk överenskommelse experimentellt med användning av ett polarisationsintrasslat tillstånd med fyra fotoner. Detta visar att kvantimplementeringen av klassiska bysantinska avtalsprotokoll verkligen är genomförbar.