Задача візантійських генералів

Задача візантійських генералів — одна із задач криптографії, а саме: взаємодія декількох віддалених абонентів, які отримали накази з єдиного центру. Частина абонентів, разом із центром, можуть бути ворогами. Необхідно виробити єдину стратегію дій, переможну для лояльних абонентів. Протокол розв'язання цієї задачі називають протоколом візантійської угоди або протоколом візантійських генералів.

Задача

Візантія. Ніч напередодні великої битви. Візантійська армія складається з n легіонів, і кожен з них підпорядковується своєму генералу. Окрім цього, армія має головнокомандувача, котрий керує генералами. Однак імперія перебуває в занепаді і до третини генералів (разом із головнокомандувачем), можуть бути зрадниками. Протягом ночі кожен з генералів отримує від головнокомандувача наказ про дії вранці. Можливі два варіанти наказу: «атакувати» або «відступати». Якщо всі чесні генерали атакують, то вони перемагають. Якщо вони відступають, то їм вдається зберегти армію. Але якщо частина з них атакує, а частина відступає, то вони зазнають поразки. Якщо головнокомандувач буде зрадником, то він може дати генералам різні накази, тому накази головнокомандувача не варто виконувати беззаперечно. Якщо кожен генерал буде діяти незалежно від інших, то результат може бути поганим. Вочевидь, вони потребують обміну інформацією один з одним (стосовно отриманих наказів) для узгодженості дій.

Формалізація

Кожен із генералів має отримати один і той же вектор довжини n, у котрому i-й елемент або містить чисельність ${\displaystyle i}$-ї армії (якщо її командувач лояльний), або невизначений (якщо командувач — зрадник).

Алгоритми розв'язання

В результаті розв'язання цієї проблеми виникло дві математичні моделі — інтерактивна система доведень і доведення з нульовим розголошенням.

Інтерактивну систему доведень (Р, V, S) слід розуміти як протокол взаємодії двох абонентів: Р (той що доводить) та V (той що перевіряє). Абонент Р хоче довести V, що твердження S істинне. Абонент V самостійно, без допомоги Р, не може довести твердження S (тому V й називають перевіряльником). Абонент Р може бути й ворогом, котрий хоче довести V, що твердження S істинне, хоча воно хибне. Протокол може складатися з багатьох раундів обміну повідомленнями між Р та V і має відповідати двом умовам:

• 1) повнота — якщо S справді істинне, то абонент Р майже переконає абонента V визнати його істинним;
• 2) коректність — якщо S хибне, то абонент Р навряд чи переконає абонента V, що S — істинне.

Наголосимо на тому, що у визначенні системи (Р, V, S) не припускалося, що V може бути ворогом. А що, коли V є ворогом, котрий хоче дізнатися від Р якусь нову (цікаву для себе) інформацію про твердження S? У такому разі Р, звісно, не бажає, щоб це трапилось як наслідок роботи протоколу (Р, V, S). Протокол (Р, V, S), що розв'язує таку задачу, називається доведенням із нульовим розголошенням і має відповідати, окрім умов 1 і 2, ще такій умові:

• 3) нульове розголошення (або стійкість) — у результаті роботи протоколу (Р, V, S) абонент V не збільшує свої знання про твердження S або, іншими словами, не зможе здобути ніякої інформації про те, чи S істинне.

Розв'язок

Відповідний рекурсивний алгоритм запропонував 1982 року Леслі Лампорт.

Наведемо приклад для випадку коли n=4 і m=1, де: n — загальна кількість генералів, m — кількість зрадників. У такому разі алгоритм має довжину 4 кроки.

1-й крок. Кожен генерал надсилає всім іншим повідомлення, в якому повідомляє чисельність своєї армії. Лояльні генерали зазначають справжню кількість, а зрадники можуть надати різні числа в різних повідомленнях. Генерал-1 вказав число 1 (одна тисяча воїнів), генерал-2 вказав число 2, генерал-3 (зрадник) вказав трьом іншим генералам відповідно x, y, z, а генерал-4 вказав 4.

2-й крок. Кожен формує свій вектор з інформації, яку отримав.

Отримуємо:

vect1 (1,2,x,4)

vect2 (1,2,y,4)

vect3 (1,2,3,4)

vect4 (1,2,z,4)

3-й крок. Кожен надсилає свій вектор усім іншим (генерал-3 знову може надіслати неправильні значення).

Генерали отримують наступні вектори:

g1	g2	g3	g4
(1,2,y,4)	(1,2,x,4)	(1,2,x,4)	(1,2,x,4)
(a,b,c,d)	(e,f,g,h)	(1,2,y,4)	(1,2,y,4)
(1,2,z,4)	(1,2,z,4)	(1,2,z,4)	(i,j,k,l)

4-й крок. Кожен генерал перевіряє кожен елемент у всіх отриманих векторах. Якщо якесь значення збігається не менше, аніж у двох векторах, то воно потрапляє до остаточного вектора, інакше відповідний елемент остаточного вектора позначається невідомим.

Усі лояльні генерали отримують один вектор (1,2,невідомий,4) — згоди досягнуто.

Результати дослідження задачі

Лампорт довів, що в системі, де m елементів працює неправильно, згоди можна досягти лише коли 2m+1 інших елементів працює правильно (лояльних генералів більше, ніж дві третини).

Див. також

• Network Time Protocol (NTP)
• Задача двох генералів

Посилання

• Крюков В. А. Курс лекций «Распределенные ОС» [ 13 жовтня 2011 у Wayback Machine.]
• The Byzantine Generals Problem (with Marshall Pease and Robert Shostak) ACM Transactions on Programming Languages and Systems 4, 3 (July 1982), 382–401." [ 16 серпня 2007 у Wayback Machine.](англ.)
• Криптографія: нові напрямки [ 28 вересня 2010 у Wayback Machine.]