Квантовое византийское соглашение - Quantum Byzantine agreement

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

Вступление

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

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

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

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

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

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

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

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

Набросок алгоритма

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

• Фаза 1 (Фаза связи):

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

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

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

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

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

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

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

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

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

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

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

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

${displaystyle s_{i}=sum ,{s_{k}^{i}}{ ext{for all secrets properly shared}}mod n}$

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

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

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

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

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

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

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

Замечания

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

Рекомендации

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