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

Византийские отказоустойчивые протоколы — это алгоритмы, устойчивые к произвольным типам сбоев в распределенных алгоритмах . Протокол Византийского соглашения является важной частью этой задачи. с постоянным временем Квантовая версия византийского протокола , ^[1] описано ниже.

Введение

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

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

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

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

Византийская неудача и устойчивость

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

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

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

Эскиз алгоритма

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

Фаза 1 (фаза коммуникации):

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

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

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

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

Подтверждаемый обмен секретами

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

Протокол отказоустойчивости

Протокол квантовой монеты для игрока

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

Византийский протокол

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

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

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

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

Протокол оценки

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

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

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

Если Д честен, то $\mathrm {value} _{i}$ = v и $\mathrm {confidence} _{i}$ = 2 за каждого честного игрока $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}$ .

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

Примечания

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

Ссылки

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

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

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

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

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

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]