Квантовое византийское соглашение

Эта статья, возможно, содержит оригинальные исследования . Пожалуйста, улучшите его , проверив сделанные утверждения и добавив встроенные цитаты . Заявления, содержащие только оригинальные исследования, следует удалить. ( Июль 2016 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Византийские отказоустойчивые протоколы - это алгоритмы, устойчивые к любым типам сбоев в распределенных алгоритмах . С появлением и популярностью Интернета возникла необходимость в разработке алгоритмов, не требующих централизованного управления и обеспечивающих некоторую гарантию правильной работы. ^{[ оригинальное исследование? ]} Протокол византийского соглашения является важной частью этой задачи. Постоянное время квантовая версия византийского протокола , ^[1] описана ниже.

Введение [ править ]

Византийское соглашение Протокол представляет собой протокол в распределенных вычислениях . Он получил свое название от проблемы, сформулированной Лэмпортом, Шостаком и Пизом в 1982 г. ^[2], которая сама по себе является отсылкой к исторической проблеме. Византийская армия была разделена на подразделения, каждая из которых возглавлялась генералом со следующими характеристиками:

Каждый генерал либо лоялен, либо предан византийскому государству .
Все генералы общаются, отправляя и получая сообщения.
Есть всего две команды: атаковать и отступать.
Все верные генералы должны согласовать один и тот же план действий: нападение или отступление.
Небольшая линейная доля плохих генералов не должна вызывать сбой протокола (меньше доли). ${\ displaystyle {\ tfrac {1} {3}}}$

(См. ^[3] для доказательства результата о невозможности). Проблема обычно эквивалентно переформулируется в форме командующего генерала и лояльных лейтенантов, причем генерал является либо лояльным, либо предателем, и то же самое для лейтенантов со следующими свойствами.

Все верные лейтенанты выполняют один и тот же приказ.
Если командующий генерал лоялен, все верные лейтенанты подчиняются его приказу.
Строго меньшая часть, включая командующего генерала, являются предателями. ${\ displaystyle {\ tfrac {1} {3}}}$

Византийский провал и стойкость [ править ]

Сбои в алгоритме или протоколе можно разделить на три основных типа:

Неспособность предпринять еще один шаг выполнения в алгоритме: это обычно называется ошибкой «аварийной остановки».
Случайный сбой при правильном выполнении: это называется «случайный сбой» или «случайный византийский сбой».
Произвольный сбой, при котором алгоритм не может правильно выполнить шаги (обычно хитрым способом каким-либо противником, чтобы заставить весь алгоритм выйти из строя), который также включает в себя предыдущие два типа ошибок; это называется «византийской ошибкой».

Византийский отказоустойчивый или византийский отказоустойчивый протокол или алгоритм - это алгоритм, устойчивый ко всем видам сбоев, упомянутых выше. Например, учитывая космический шаттл с несколькими избыточными процессорами, если процессоры выдают противоречивые данные, каким процессорам или группам процессоров следует верить? Решение можно сформулировать как византийский отказоустойчивый протокол.

Набросок алгоритма [ править ]

Мы сделаем набросок асинхронного алгоритма ^[1] . Алгоритм состоит из двух этапов:

Этап 1 (этап коммуникации):

Все сообщения отправляются и принимаются в этом раунде.

Протокол подбрасывания монеты - это процедура, которая позволяет двум сторонам A и B, которые не доверяют друг другу, подбросить монету для выигрыша определенного объекта.

Существует два типа протоколов подбрасывания монет.

слабые протоколы подбрасывания монеты : ^[4] Два игрока A и B изначально начинают без входов, и они должны вычислить некоторую ценность и иметь возможность обвинить кого-либо в мошенничестве. Протокол считается успешным, если A и B согласны с исходом. Результат 0 определяется как выигрыш A, а результат 1 - как выигрыш B. Протокол имеет следующие свойства: ${\ displaystyle c_ {A}, c_ {B} \ in [0,1]}$
- Если оба игрока честны (они следуют протоколу), то они соглашаются с результатом протокола с помощью for . ${\ displaystyle c_ {A} = c_ {B}}$ ${\ Displaystyle Pr (c_ {A} = c_ {B} = b) = {\ tfrac {1} {2}}}$ ${\ displaystyle a, b \ in \ {0,1 \}}$
- Если один из игроков честен (т. Е. Другой игрок может произвольно отклоняться от протокола в своих локальных вычислениях), то другая сторона выигрывает с максимальной вероятностью . Другими словами, если B нечестен, тогда , а если A нечестен, тогда . ${\ displaystyle {\ tfrac {1} {2}} + \ epsilon}$ ${\ Displaystyle Pr (c_ {A} = c_ {B} = 1) \ leq {\ tfrac {1} {2}} + \ epsilon}$ ${\ Displaystyle Pr (c_ {A} = c_ {B} = 0) \ leq {\ tfrac {1} {2}} + \ epsilon}$
Сильный протокол монеты листать : В сильном протоколе монеты листать, цель состоит в том, чтобы вместо того, чтобы произвести случайный бит , который смещен от какого - либо конкретного значения 0 или 1. Очевидно, что любой сильного протокол монеты листать с смещением приводит к слабой монете листать с такая же предвзятость. ${\ displaystyle \ epsilon}$

Поддающийся проверке секретный обмен [ править ]

Проверяемый секрет совместного протокола: А (п, к) разделение секрета протокол позволяет набор русских игроков , чтобы поделиться секретом, S таким образом, что только кворум из к или более игроков может открыть секрет. Игрок, делящий секрет (раздающий секретные части), обычно называется дилером. Поддающийся проверке протокол совместного использования секретов отличается от базового протокола совместного использования секретов тем, что игроки могут проверять согласованность своих долей даже в присутствии злоумышленника.

Протокол отказоустойчивости [ править ]

Протокол квантового подбрасывания монеты для игрока ${\ displaystyle P_ {i}}$ [ править ]

Раунд 1 генерирует состояние GHZ на кубитах и отправляет th кубит тому игроку, сохраняя одну часть ${\ displaystyle | \ mathrm {Coin} _ {i} \ rangle = {\ tfrac {1} {\ sqrt {2}}} | 0,0, \ ldots, 0 \ rangle + {\ tfrac {1} {\ sqrt {2}}} | 1,1, \ ldots, 1 \ rangle}$ ${\ displaystyle n}$ ${\ displaystyle k}$ ${\ displaystyle k}$
Сформировать состояние на кубитов, равное суперпозицию чисел от 1 до . Распределите кубиты между всеми игроками ${\ displaystyle | \ mathrm {Leader} _ {i} \ rangle = {\ tfrac {1} {n ^ {3/2}}} \ sum \ nolimits _ {a = 1} ^ {n ^ {3}} | а, а, \ ldots, а \ rangle}$ ${\ displaystyle n}$ ${\ Displaystyle п ^ {3}}$ ${\ displaystyle n}$
Получите квантовые сообщения от всех игроков и дождитесь следующего раунда связи, тем самым заставляя противника выбирать, какие сообщения были переданы.
Раунд 2: Измерьте (в стандартной базе) все кубиты, полученные в первом раунде. Выберите игрока с наивысшим значением лидера (ничья разорвана произвольно) в качестве «лидера» раунда. Отмерьте монету лидера в стандартной базе. ${\ displaystyle \ mathrm {лидер} _ {j}}$
Установите вывод протокола QuantumCoinFlip: = результат измерения монеты лидера. ${\ displaystyle v_ {i}}$

Византийский протокол [ править ]

Чтобы сгенерировать случайную монету, присвойте каждому игроку целое число в диапазоне [0, n-1], и каждому игроку не разрешается выбирать свой собственный случайный идентификатор, поскольку каждый игрок выбирает случайное число для каждого другого игрока и распределяет его, используя проверяемый схема разделения секрета. ${\ displaystyle P_ {k}}$ $s{_{k}^{i}}$ $P_{i}$

В конце этой фазы игроки соглашаются, какие секреты были должным образом переданы, затем секреты открываются, и каждому игроку присваивается значение. $P_{i}$

s_{i}=\sum \,{s_{k}^{i}}{\text{for all secrets properly shared}}\mod n

Для этого требуются частные информационные каналы, поэтому мы заменяем случайные секреты суперпозицией . В котором состояние кодируется с использованием квантово-проверяемого протокола совместного использования секретов (QVSS). ^[5] Мы не можем распределить состояние, так как плохие игроки могут свернуть состояние. Чтобы этого не произошло, мы кодируем состояние, используя квантово-проверяемое совместное использование секрета (QVSS), и отправляем каждому игроку свою долю секрета. Здесь снова для проверки требуется византийское соглашение, но достаточно заменить соглашение протоколом оценки. ^[6]^[7] $|\phi \rangle ={\tfrac {1}{\sqrt {n}}}\sum \nolimits _{a=0}^{n-1}|a\rangle$ $|\phi ,\phi ,\ldots \phi \rangle$

Протокол оценки [ править ]

Протокол ранжирования имеет следующие свойства с использованием определений в ^[6] Неформально протокол градуированного широковещания - это протокол с назначенным игроком, называемым «дилером» (тот, кто осуществляет широковещательную передачу), такой, что:

Если дилер хорош, все игроки получают одно и то же сообщение.
Даже если дилер плохой, если какой-то хороший игрок принимает сообщение, все хорошие игроки получают такое же сообщение (но они могут принять его, а могут и не принять).

Говорят, что протокол P обеспечивает градуированную трансляцию, если в начале протокола назначенный игрок D (называемый дилером) имеет значение v, а в конце протокола каждый игрок выводит такую пару , что следующие свойства держат: $P_{i}$ $(\mathrm {value} _{i},\mathrm {confidence} _{i})$ $(\forall i,\mathrm {confidence} _{i}\in \{0,1,2\})$

Если D честный, то = v и = 2 для каждого честного игрока . $\mathrm {value} _{i}$ $\mathrm {confidence} _{i}$ $P_{i}$
Для любых двух честных игроков и . $P_{i}$ $P_{j},$ $\vert \mathrm {confidence} _{i}-\mathrm {confidence} _{j}\vert \leq 1$
(Последовательность) Для любых двух честных игроков и , если и , то . $P_{i}$ $P_{j}$ $\mathrm {confidence} _{i}>0$ $\mathrm {confidence} _{j}>0$ $\mathrm {value} _{i}=\mathrm {value} _{j}$

Для этапа проверки протокол QVSS гарантирует, что для хорошего дилера правильное состояние будет закодировано, и что для любого, возможно неисправного дилера, какое-то конкретное состояние будет восстановлено на этапе восстановления. Отметим, что для целей нашего византийского протокола квантового подбрасывания монеты этап восстановления намного проще. Каждый игрок измеряет свою долю QVSS и отправляет классическое значение всем другим игрокам. Этап проверки с высокой вероятностью гарантирует, что при наличии до неисправных игроков все хорошие игроки восстановят одно и то же классическое значение (которое является тем же значением, которое было бы результатом прямого измерения закодированного состояния). $t<{\tfrac {n}{4}}$ $t<{\tfrac {n}{4}}$

Замечания [ править ]

В 2007 г. квантовый протокол Византийского соглашения был продемонстрирован экспериментально ^[8] с использованием состояния четырехфотонной поляризационно-запутанной связи. Это показывает, что квантовая реализация классических протоколов Византийского соглашения действительно возможна.

Ссылки [ править ]

^ а б Майкл Бен-Ор; Авинатан Хасидим (2005). Быстрое квантовое византийское соглашение . STOC '05: Материалы тридцать седьмого ежегодного симпозиума ACM по теории вычислений. Балтимор, Мэриленд, США. С. 481–485. DOI : 10.1145 / 1060590.1060662 .
^ Лэмпорт, Лесли; Шостак, Роберт; Пиз, Маршалл (1982). «Проблема византийских генералов». Транзакции ACM по языкам и системам программирования . 4 (3): 382–401. DOI : 10.1145 / 357172.357176 . ISSN 0164-0925 .
^ Фишер, Майкл Дж .; Lynch, Nancy A .; Патерсон, Майкл С. (1985). «Невозможность распределенного консенсуса с одним ошибочным процессом». Журнал ACM . 32 (2): 374–382. DOI : 10.1145 / 3149.214121 . ISSN 0004-5411 . S2CID 207660233 .
^ Керенидис, I .; Наяк, А. (2004). «Слабый подбрасывание монеты с небольшим уклоном». Письма об обработке информации . 89 (3): 131–135. arXiv : Quant-ph / 0206121v2 . DOI : 10.1016 / j.ipl.2003.07.007 . ISSN 0020-0190 . S2CID 14445949 .
^ Крепо, Клод; Готтесман, Даниэль; Смит, Адам (2002). Безопасные многосторонние квантовые вычисления . 34-й симпозиум ACM по теории вычислений, STOC. С. 643–652. DOI : 10.1145 / 509907.510000 .
^ а б Бен-Ор, Майкл; Павлов, Элан; Вайкунтанатан, Винод (2006). «Византийское соглашение в полной информационной модели за O (log n) раундов». Материалы тридцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '06 . С. 179–186. CiteSeerX 10.1.1.296.4133 . DOI : 10.1145 / 1132516.1132543 . ISBN 1595931341. S2CID 6379620 .
^ Фельдман, Песеч; Микали, Сильвио (1997). «Оптимальный вероятностный протокол для синхронного византийского соглашения». SIAM Journal on Computing . 26 (4): 873–933. DOI : 10.1137 / S0097539790187084 . ISSN 0097-5397 .
^ Гертнер, Саша; Буреннане, Мохамед; Курцифер, Кристиан; Кабельо, Адан; Вайнфуртер, Харальд (2008). «Экспериментальная демонстрация квантового протокола для византийского соглашения и обнаружения лжецов». Письма с физическим обзором . 100 (7): 070504. arXiv : 0710.0290v2 . Bibcode : 2008PhRvL.100g0504G . DOI : 10.1103 / PhysRevLett.100.070504 . ISSN 0031-9007 . PMID 18352533 . S2CID 30443015 .

[Ben-Or-1] а б Майкл Бен-Ор; Авинатан Хасидим (2005). Быстрое квантовое византийское соглашение . STOC '05: Материалы тридцать седьмого ежегодного симпозиума ACM по теории вычислений. Балтимор, Мэриленд, США. С. 481–485. DOI : 10.1145 / 1060590.1060662 .

[LamportShostak1982-2] Лэмпорт, Лесли; Шостак, Роберт; Пиз, Маршалл (1982). «Проблема византийских генералов». Транзакции ACM по языкам и системам программирования . 4 (3): 382–401. DOI : 10.1145 / 357172.357176 . ISSN 0164-0925 .

[FischerLynch1985-3] Фишер, Майкл Дж .; Lynch, Nancy A .; Патерсон, Майкл С. (1985). «Невозможность распределенного консенсуса с одним ошибочным процессом». Журнал ACM . 32 (2): 374–382. DOI : 10.1145 / 3149.214121 . ISSN 0004-5411 . S2CID 207660233 .

[KerenidisNayak2004-4] Керенидис, I .; Наяк, А. (2004). «Слабый подбрасывание монеты с небольшим уклоном». Письма об обработке информации . 89 (3): 131–135. arXiv : Quant-ph / 0206121v2 . DOI : 10.1016 / j.ipl.2003.07.007 . ISSN 0020-0190 . S2CID 14445949 .

[CrépeauGottesman2002-5] Крепо, Клод; Готтесман, Даниэль; Смит, Адам (2002). Безопасные многосторонние квантовые вычисления . 34-й симпозиум ACM по теории вычислений, STOC. С. 643–652. DOI : 10.1145 / 509907.510000 .

[wiki:byzantine-6] а б Бен-Ор, Майкл; Павлов, Элан; Вайкунтанатан, Винод (2006). «Византийское соглашение в полной информационной модели за O (log n) раундов». Материалы тридцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '06 . С. 179–186. CiteSeerX 10.1.1.296.4133 . DOI : 10.1145 / 1132516.1132543 . ISBN 1595931341. S2CID 6379620 .

[FeldmanMicali1997-7] Фельдман, Песеч; Микали, Сильвио (1997). «Оптимальный вероятностный протокол для синхронного византийского соглашения». SIAM Journal on Computing . 26 (4): 873–933. DOI : 10.1137 / S0097539790187084 . ISSN 0097-5397 .

[GaertnerBourennane2008-8] Гертнер, Саша; Буреннане, Мохамед; Курцифер, Кристиан; Кабельо, Адан; Вайнфуртер, Харальд (2008). «Экспериментальная демонстрация квантового протокола для византийского соглашения и обнаружения лжецов». Письма с физическим обзором . 100 (7): 070504. arXiv : 0710.0290v2 . Bibcode : 2008PhRvL.100g0504G . DOI : 10.1103 / PhysRevLett.100.070504 . ISSN 0031-9007 . PMID 18352533 . S2CID 30443015 .

[1]