Kvant Vizantiya shartnomasi - Quantum Byzantine agreement

Vizantiya xatolariga bardoshli protokollar o'zboshimchalik bilan bajarilgan xatolar turiga asoslangan algoritmlar taqsimlangan algoritmlar. Ning paydo bo'lishi va mashhurligi bilan Internet, har doim ham to'g'ri ishlashning ba'zi bir kafolatlariga ega bo'lgan har qanday markazlashtirilgan boshqaruvni talab qilmaydigan algoritmlarni ishlab chiqishga ehtiyoj bor.^{[asl tadqiqotmi? ]} Vizantiya kelishuvi protokoli ushbu vazifaning muhim qismidir. Ushbu maqolada Vizantiya protokolining kvant versiyasi,^[1] doimiy vaqt ichida ishlaydigan tasvirlangan.

Kirish

The Vizantiya shartnomasi protokol bu protokol tarqatilgan hisoblash.Uning nomini 1982 yilda Lamport, Shostak va Peaz tomonidan tuzilgan muammodan olgan,^[2] bu o'zi tarixiy muammoga havola. Vizantiya armiyasi bo'linmalarga bo'linib, har bir bo'linmani quyidagi xususiyatlarga ega general boshqaradi.

Har bir general sodiq yoki xoin Vizantiya davlati.
Barcha generallar xabarlarni yuborish va qabul qilish orqali aloqa qilishadi.
Faqat ikkita buyruq bor: hujum va chekinish.
Barcha sodiq generallar bir xil harakatlar rejasida kelishishlari kerak: hujum yoki chekinish.
Yomon Generallarning kichik chiziqli qismi protokolning ishdan chiqishiga olib kelmasligi kerak (a dan kam) ${displaystyle {frac {1} {3}}}$ kasr).

(Qarang ^[3] mumkin bo'lmagan natijaning isboti uchun). Muammo odatda buyruq beradigan general va sodiq leytenantlar shaklida teng ravishda qayta tiklanadi, general bilan sadoqatli yoki xoin, leytenantlar uchun esa quyidagi xususiyatlarga ega.

Barcha sodiq leytenantlar bir xil buyruqni bajaradilar.
Agar qo'mondon general sodiq bo'lsa, barcha sodiq leytenantlar u yuborgan buyruqqa bo'ysunadi.
A dan kamroq ${displaystyle {frac {1} {3}}}$ fraktsiya, shu qatorda General buyrug'i sotqinlar.

Vizantiya muvaffaqiyatsizligi va chidamliligi

Anda xatolar algoritm yoki protokol uchta asosiy turga bo'linishi mumkin:

Algoritmda yana bir bajarilish bosqichini bajarmaslik: Bu odatda "ishlamay to'xtash" xatosi deb ataladi.
To'g'ri bajarilmagan tasodifiy muvaffaqiyatsizlik: Bunga "tasodifiy nosozlik" yoki "tasodifiy Vizantiya" nosozligi deyiladi.
Algoritm qadamlarni to'g'ri bajara olmagan o'zboshimchalik qobiliyatsizligi (odatda ba'zi bir dushmanlar aqlli ravishda, butun algoritmni bajarmaslik uchun), bu avvalgi ikki turdagi xatolarni ham o'z ichiga oladi; bu "Vizantiya xatosi" deb nomlanadi.

Vizantiya bardoshli yoki Vizantiya xatolariga bardoshli protokol yoki algoritm - bu yuqorida aytib o'tilgan barcha turdagi nosozliklar uchun mustahkam algoritm. Masalan, bir nechta ortiqcha protsessorlarga ega kosmik shutl berilgan, agar protsessorlar qarama-qarshi ma'lumotlar keltirsa, qaysi protsessorlarga yoki protsessorlarning to'plamlariga ishonish kerak? Qaror a shaklida tuzilishi mumkin Vizantiya xatolariga bardoshli protokol.

Algoritmning eskizlari

Biz bu erda asenkron algoritmni chizamiz ^[1]Algoritm ikki bosqichda ishlaydi:

1-bosqich (Aloqa bosqichi):

Barcha xabarlar ushbu turda yuboriladi va qabul qilinadi.

Tangalarni aylantirish protokoli - bu bir-biriga ishonmaydigan ikkita A va B tomonlarga tanga tashlashga, ma'lum bir ob'ektni yutib olishga imkon beradigan protsedura.

Tangalarni aylantirish protokollarining ikki turi mavjud

zaif tanga aylantirish protokollar:^[4] Ikki o'yinchi A va B dastlab hech qanday kirishdan boshlanadi va ular biron bir qiymatni hisoblashlari kerak ${displaystyle c_ {A}, c_ {B} [0,1]} da$ $c _ {{A}}, c _ {{B}} [0,1] da$ va birovni aldashda ayblash imkoniyatiga ega bo'ling. Agar A va B natijalar bo'yicha kelishib olsalar, protokol muvaffaqiyatli bo'ladi. 0 natijasi A g'olibi va 1 g'olibi B sifatida belgilanadi. Protokol quyidagi xususiyatlarga ega:
- Agar ikkala o'yinchi halol bo'lsa (ular protokolga rioya qilsalar), u holda ular protokol natijalari bo'yicha kelishishadi ${displaystyle c_ {A} = c_ {B}}$ bilan ${displaystyle Pr (c_ {A} = c_ {B} = b) = {frac {1} {2}}}$ uchun ${displaystyle a, axlat qutisi {0,1}}$ .
- Agar o'yinchilarning biri halol bo'lsa (ya'ni, boshqa o'yinchi o'zining mahalliy hisoblashidagi o'zboshimchalik bilan protokoldan chetga chiqishi mumkin) bo'lsa, unda boshqa tomon ko'pi bilan ehtimollik bilan g'alaba qozonadi ${displaystyle {frac {1} {2}} + epsilon}$ . Boshqacha qilib aytganda, agar B vijdonsiz bo'lsa, unda ${displaystyle Pr (c_ {A} = c_ {B} = 1) leq {frac {1} {2}} + epsilon}$ va agar A vijdonsiz bo'lsa, unda ${displaystyle Pr (c_ {A} = c_ {B} = 0) leq {frac {1} {2}} + epsilon}$ .
A kuchli tanga aylantirish protokoli: Kuchli tanga aylantirish protokolida maqsad har qanday ma'lum bir qiymatdan 0 yoki 1 dan chetga chiqadigan tasodifiy bitni hosil qilishdan iborat. ${displaystyle epsilon}$ bir xil noto'g'ri tanga aylantirib, zaif tanga olib keladi.

Tasdiqlanadigan maxfiy almashish

A tekshiriladigan maxfiy almashish protokol: A (n, k) maxfiy almashish protokol n-pleyerlar sirini baham ko'rishga imkon beradi, s sirni k yoki undan ko'p o'yinchining kvorumi bilib olishi mumkin. O'yinchi bilan baham ko'rish (maxfiy qismlarni tarqatish) sirni odatda diler deb atashadi. Tekshiriladigan maxfiy almashish protokoli asosiy maxfiy almashish protokolidan farq qiladi, chunki o'yinchilar zararli sotuvchi ishtirokida ham ularning ulushlari izchilligini tekshirishlari mumkin.

To'xtovsiz to'xtatish protokoli

Aktyor uchun kvant tanga protokoli ${displaystyle P_ {i}}$

1-tur GHZ holati ${displaystyle | mathrm {Coin} _ {i} angle = {frac {1} {sqrt {2}}} | 0,0, ldots, 0angle + {frac {1} {sqrt {2}}} | 1,1 , ldots, 1burchak}$ kuni ${displaystyle n}$ kubitlar va yuboring ${displaystyle k}$ th qubit uchun ${displaystyle k}$ futbolchi bir qismini saqlab
Shtatni yaratish ${displaystyle | mathrm {Leader} _ {i} angle = {frac {1} {n ^ {3/2}}} sum olimits _ {a = 1} ^ {n ^ {3}} | a, a, ldots , burchakli burchak}$ kuni ${displaystyle n}$ kubitlar, 1 va orasidagi sonlarning teng superpozitsiyasi ${displaystyle n ^ {3}}$ . Tarqatish ${displaystyle n}$ kubitlar barcha o'yinchilar o'rtasida
Barcha o'yinchilarning kvant xabarlarini qabul qiling va keyingi muloqot turini kuting, shunda raqib qaysi xabarlarning uzatilishini tanlashga majbur qilinadi.
2-tur: barchasini o'lchash (standart bazada) ${displaystyle mathrm {Leader} _ {j}}$ kubitlar I raundda qabul qilingan. Turning "etakchisi" sifatida eng yuqori etakchi qiymatiga ega (o'zboshimchalik bilan bog'langan bog'ich) o'yinchini tanlang. Standart bazada etakchining tanganini o'lchab ko'ring.
QuantumCoinFlip protokoli natijasini o'rnating: ${displaystyle v_ {i}}$ = etakchining tanganing o'lchov natijasi.

Vizantiya protokoli

Tasodifiy tanga yaratish uchun har bir o'yinchiga [0, n-1] oralig'ida butun sonni belgilang va har bir o'yinchiga har bir o'yinchi sifatida o'z tasodifiy identifikatorini tanlashga ruxsat berilmaydi. ${displaystyle P_ {k}}$ tasodifiy sonni tanlaydi ${displaystyle s {_ {k} ^ {i}}}$ har bir boshqa o'yinchi uchun ${displaystyle P_ {i}}$ va buni tasdiqlangan maxfiy almashish sxemasi yordamida tarqatadi.

Ushbu bosqich yakunida o'yinchilar qaysi sirlarni to'g'ri bo'lishgani to'g'risida kelishib oladilar, keyin sirlar ochiladi va har bir o'yinchi ${displaystyle P_ {i}}$ qiymat beriladi

{displaystyle s_ {i} = sum, {s_ {k} ^ {i}} {ext {barcha sirlar uchun to'g'ri taqsimlangan}} mod n}

Buning uchun shaxsiy axborot kanallari kerak, shuning uchun biz tasodifiy sirlarni superpozitsiya bilan almashtiramiz ${displaystyle | phi angle = {frac {1} {sqrt {n}}} sum olimits _ {a = 0} ^ {n-1} | aangle}$ . Bunda shtat kvant tomonidan tasdiqlanadigan maxfiy almashish protokoli (QVSS) yordamida kodlangan.^[5] Biz davlatni taqsimlay olmaymiz ${displaystyle | phi, phi, ldots phi burchak}$ chunki yomon o'yinchilar davlatni qulashi mumkin. Yomon o'yinchilarni bunday qilishiga yo'l qo'ymaslik uchun biz davlatni kvant bilan tasdiqlanadigan maxfiy almashinuv (QVSS) yordamida kodlaymiz va har bir o'yinchiga o'zlariga tegishli bo'lgan sirni yuboramiz. Bu erda yana tekshirish Vizantiya shartnomasini talab qiladi, ammo kelishuvni asosiy protokol bilan almashtirish kifoya.^[6]^[7]

Baholash protokoli

Belgilangan protokol quyidagi ta'riflardan foydalangan holda quyidagi xususiyatlarga ega ^[6]Norasmiy ravishda, baholangan translyatsiya protokol - "diler" deb nomlangan (efirga uzatuvchi) deb nomlangan belgilangan pleyerga ega protokol:

Agar diler yaxshi bo'lsa, barcha o'yinchilar bir xil xabar olishadi.
Agar diler yomon bo'lsa ham, agar ba'zi bir yaxshi o'yinchi xabarni qabul qilsa, barcha yaxshi o'yinchilar bir xil xabarni olishadi (lekin ular buni qabul qilishi yoki qabul qilmasligi mumkin).

P protokoli darajalangan deb aytiladi translyatsiya agar protokolning boshida D (diler deb nomlangan) belgilangan o'yinchi v qiymatiga ega bo'lsa va protokol oxirida har bir o'yinchi ${displaystyle P_ {i}}$ juftlikni chiqaradi ${displaystyle (mathrm {value} _ {i}, mathrm {ishonch} _ {i})}$ shunday qilib quyidagi xususiyatlar mavjud: ${displaystyle (forall i, mathrm {trust} _ {i} in {0,1,2})}$

Agar D halol bo'lsa, unda ${displaystyle mathrm {value} _ {i}}$ = v va ${displaystyle mathrm {ishonch} _ {i}}$ = Har bir halol futbolchi uchun 2 tadan ${displaystyle P_ {i}}$ .
Har qanday ikkita halol futbolchi uchun ${displaystyle P_ {i}}$ va ${displaystyle P_ {j},}$ ${displaystyle vert mathrm {ishonch} _ {i} -mathrm {ishonch} _ {j} vert leq 1}$ .
(Mustahkamlik) Har qanday ikkita halol futbolchi uchun ${displaystyle P_ {i}}$ va ${displaystyle P_ {j}}$ , agar ${displaystyle mathrm {ishonch} _ {i}> 0}$ va ${displaystyle mathrm {ishonch} _ {j}> 0}$ , keyin ${displaystyle mathrm {value} _ {i} = mathrm {value} _ {j}}$ .

Uchun ${displaystyle t <{frac {n} {4}}}$ QVSS protokolini tekshirish bosqichi yaxshi diler uchun to'g'ri holat kodlanganligini va nosoz bo'lgan har qanday diler uchun tiklanish bosqichida ma'lum bir holat tiklanishini kafolatlaydi. Shuni ta'kidlaymizki, Vizantiya kvant tangalarini almashtirish protokoli uchun tiklanish bosqichi ancha sodda. Har bir o'yinchi QVSSdagi ulushini o'lchaydi va boshqa barcha o'yinchilarga klassik qiymatni yuboradi. Tekshirish bosqichi yuqori ehtimollik bilan kafolatlaydi, bunga qadar ${displaystyle t <{frac {n} {4}}}$ noto'g'ri o'yinchilar barcha yaxshi o'yinchilar bir xil klassik qiymatni tiklaydilar (bu kodlangan holatni to'g'ridan-to'g'ri o'lchash natijasida kelib chiqadigan bir xil qiymat).

Izohlar

2007 yilda Vizantiya shartnomasi bo'yicha kvant protokoli eksperimental tarzda namoyish etildi ^[8] to'rt fotonli polarizatsiya bilan chalkash holatdan foydalanish. Bu shuni ko'rsatadiki, Vizantiya shartnomasi bo'yicha klassik protokollarning kvant bo'yicha bajarilishi haqiqatan ham mumkin.

Adabiyotlar

^ ^a ^b Maykl Ben-Or; Avinatan Xassidim (2005). Tez kvantli vizantiya shartnomasi. STOC '05: Hisoblash nazariyasi bo'yicha o'ttiz ettinchi yillik ACM simpoziumi materiallari. Baltimor, MD, AQSh. p. 481-485. doi:10.1145/1060590.1060662.
^ Lamport, Lesli; Shostak, Robert; Piz, Marshall (1982). "Vizantiya generallari muammosi". Dasturlash tillari va tizimlari bo'yicha ACM operatsiyalari. 4 (3): 382–401. doi:10.1145/357172.357176. ISSN 0164-0925.
^ Fischer, Maykl J.; Linch, Nensi A.; Paterson, Maykl S. (1985). "Bitta noto'g'ri jarayon bilan tarqatilgan konsensusning mumkin emasligi". ACM jurnali. 32 (2): 374–382. doi:10.1145/3149.214121. ISSN 0004-5411.
^ Kerenidis, I .; Nayak, A. (2004). "Kichkina tanqislik bilan zaif tanga aylanmoqda". Axborotni qayta ishlash xatlari. 89 (3): 131–135. arXiv:kvant-ph / 0206121v2. doi:10.1016 / j.ipl.2003.07.007. ISSN 0020-0190.
^ Krep, Klod; Gottesman, Daniel; Smit, Adam (2002). Xavfsiz ko'p partiyali kvant hisoblash. Hisoblash nazariyasi bo'yicha 34-ACM simpoziumi, STOC. 643–652 betlar. doi:10.1145/509907.510000.
^ ^a ^b Ben-Or, Maykl; Pavlov, Elan; Vaikuntanatan, Vinod (2006). "O (log n) turlarida to'liq ma'lumotli modeldagi Vizantiya shartnomasi". Hisoblash nazariyasi bo'yicha o'ttiz sakkizinchi yillik ACM simpoziumi materiallari - STOC '06. 179–186 betlar. CiteSeerX 10.1.1.296.4133. doi:10.1145/1132516.1132543. ISBN 1595931341.
^ Feldman, Pesek; Micali, Silvio (1997). "Sinxron Vizantiya bitimi uchun maqbul taxminiy protokol". Hisoblash bo'yicha SIAM jurnali. 26 (4): 873–933. doi:10.1137 / S0097539790187084. ISSN 0097-5397.
^ Gaertner, Sascha; Bourennane, Mohamed; Kurtsiefer, nasroniy; Kabello, Adan; Vaynfurter, Xarald (2008). "Vizantiya bitimi va yolg'onchini aniqlash uchun kvant protokolining eksperimental namoyishi". Jismoniy tekshiruv xatlari. 100 (7): 070504. arXiv:0710.0290v2. Bibcode:2008PhRvL.100g0504G. doi:10.1103 / PhysRevLett.100.070504. ISSN 0031-9007. PMID 18352533.

[Ben-Or-1] Maykl Ben-Or; Avinatan Xassidim (2005). Tez kvantli vizantiya shartnomasi. STOC '05: Hisoblash nazariyasi bo'yicha o'ttiz ettinchi yillik ACM simpoziumi materiallari. Baltimor, MD, AQSh. p. 481-485. doi:10.1145/1060590.1060662.

[LamportShostak1982-2] Lamport, Lesli; Shostak, Robert; Piz, Marshall (1982). "Vizantiya generallari muammosi". Dasturlash tillari va tizimlari bo'yicha ACM operatsiyalari. 4 (3): 382–401. doi:10.1145/357172.357176. ISSN 0164-0925.

[FischerLynch1985-3] Fischer, Maykl J.; Linch, Nensi A.; Paterson, Maykl S. (1985). "Bitta noto'g'ri jarayon bilan tarqatilgan konsensusning mumkin emasligi". ACM jurnali. 32 (2): 374–382. doi:10.1145/3149.214121. ISSN 0004-5411.

[KerenidisNayak2004-4] Kerenidis, I .; Nayak, A. (2004). "Kichkina tanqislik bilan zaif tanga aylanmoqda". Axborotni qayta ishlash xatlari. 89 (3): 131–135. arXiv:kvant-ph / 0206121v2. doi:10.1016 / j.ipl.2003.07.007. ISSN 0020-0190.

[CrépeauGottesman2002-5] Krep, Klod; Gottesman, Daniel; Smit, Adam (2002). Xavfsiz ko'p partiyali kvant hisoblash. Hisoblash nazariyasi bo'yicha 34-ACM simpoziumi, STOC. 643–652 betlar. doi:10.1145/509907.510000.

[wiki:byzantine-6] Ben-Or, Maykl; Pavlov, Elan; Vaikuntanatan, Vinod (2006). "O (log n) turlarida to'liq ma'lumotli modeldagi Vizantiya shartnomasi". Hisoblash nazariyasi bo'yicha o'ttiz sakkizinchi yillik ACM simpoziumi materiallari - STOC '06. 179–186 betlar. CiteSeerX 10.1.1.296.4133. doi:10.1145/1132516.1132543. ISBN 1595931341.

[FeldmanMicali1997-7] Feldman, Pesek; Micali, Silvio (1997). "Sinxron Vizantiya bitimi uchun maqbul taxminiy protokol". Hisoblash bo'yicha SIAM jurnali. 26 (4): 873–933. doi:10.1137 / S0097539790187084. ISSN 0097-5397.

[GaertnerBourennane2008-8] Gaertner, Sascha; Bourennane, Mohamed; Kurtsiefer, nasroniy; Kabello, Adan; Vaynfurter, Xarald (2008). "Vizantiya bitimi va yolg'onchini aniqlash uchun kvant protokolining eksperimental namoyishi". Jismoniy tekshiruv xatlari. 100 (7): 070504. arXiv:0710.0290v2. Bibcode:2008PhRvL.100g0504G. doi:10.1103 / PhysRevLett.100.070504. ISSN 0031-9007. PMID 18352533.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]