Візантія, столиця давнього Східного Римського імперії, колись була одним з найпотужніших і багатих міст світу. Однак через свою велику територію Візантія часто зіштовхувалася з зовнішніми вторгненнями та внутрішніми повстаннями. Щоб захистити свої кордони, Візантія висилала кілька армій, кожну з яких командували різні генерали. Досягнення консенсусу серед цих генералів стало значним викликом.
Проблема візантійських генералів має тісний зв'язок з блокчейном. Блокчейн-мережа є розподіленою мережею, де вузли, як візантійські генерали, повинні досягти консенсусу щодо транзакцій та даних в ненадійному мережевому середовищі.

Проблема двох генералів

Проблема двох генералів є окремим випадком проблеми візантійських генералів. Проблема та її доведення нерозв'язності були вперше запропоновані Е. А. Аккоюнлу, К. Еканадхамом і Р. В. Хубером у статті 1975 року «Деякі обмеження та компроміси в проектуванні мережевих комунікацій». У 1978 році Джим Грей офіційно назвав цю проблему «Проблема двох генералів» у своїй книзі «Нотатки про операційні системи баз даних». Спочатку він використовувався для аналізу питань досягнення консенсусу за допомогою комунікації через ненадійний канал зв'язку. Зараз він широко використовується для ілюстрації проблем узгодженості та консенсусу в розподілених системах.

Визначення проблеми:
Дві армії країни A, кожну з яких очолює генерал, готуються напасти на армію країни B. Армія країни B оточена в долині, з арміями A, які розташовані на пагорбах по обидва боки від долини. Однак єдиний шлях між двома арміями A проходить через долину. Армія B сильніша, ніж будь-яка з армій A окремо, але якщо обидві армії A нападуть разом, вони можуть перемогти армію B.
Проблема: Чи можна створити алгоритм, що дозволить двом генералам армій А узгодити одночасний напад? Алгоритм може включати відправку та отримання повідомлень.
Рішення: Класичну проблему двох генералів неможливо вирішити. Не існує протоколу, який може гарантувати, що дві армії A успішно скерують свій напад. Однак у практичних системах питання можуть бути вирішені досить надійно, наприклад, за допомогою механізму «трьохстороннього рукостискання» в протоколі TCP.

Проблема візантійських генералів

Проблема візантійських генералів була вперше запропонована Леслі Лампортом, лауреатом Премії Тьюрінга 2013 року, у його статті 1982 року «Проблема візантійських генералів». Проблема описує, як досягти послідовності в розподілених системах в умовах зловмисної поведінки, такої як підробка повідомлень.
Декілька армій Візантійської імперії оточують вороже місто, кожна з яких очолюється генералом. Візантійські армії могли спілкуватися лише через вісників. Після спостереження за силами ворога візантійські генерали повинні прийти до одного висновку: лише якщо більше половини армій Візантійської імперії атакують разом, вони можуть захопити місто та досягти перемоги.

Рішення: Якщо кількість генералів (вузлів) у візантійській системі дорівнює Z, а кількість ненадійних (зрадливих) генералів X, то лише тоді, коли Z ≥ 3X + 1, протокол літості візантійської неспроможності (BFT) може гарантувати стійкість системи.
У практичних системах відмови, які призводять до нереагування вузлів, класифікуються як “Помилки збою”, тоді як вузли, які підробляють або підміняють повідомлення, класифікуються як “Візантійські помилки.”

Класифікація алгоритму консенсусу

Блокчейн-системи є типом розподіленої системи, особливо громадські ланцюжки, такі як Bitcoin та Ethereum, які складаються з численних високодецентралізованих і недовірливих мережевих вузлів. Механізм консенсусу блокчейну забезпечує постійне досягнення системи блокчейну узгодженості даних без вілок.
На основі типу стійкості до відмов алгоритми консенсусу можна класифікувати на алгоритми без візантійської стійкості (CFT) та алгоритми з візантійською стійкістю (BFT).

Алгоритми невізантійської стійкості до відмов

У розподілених системах алгоритми не-візантійської стійкості помічають надійність всієї розподіленої системи, коли вузли зазнають відмов системи або непередбачених відключень (не-візантійські помилки). Однак, коли злоумисні вузли підробляють або втручаються у дані, алгоритми не-візантійської стійкості не можуть гарантувати надійність системи. Ці алгоритми використовуються переважно в закритих, контрольованих підприємствах розподілених системах. Найбільш представницькими алгоритмами не-візантійської стійкості є алгоритм Paxos та алгоритм Raft.

Алгоритми витривалості до візантійських помилок

Алгоритми виправлення візантійських вад дозволяють розподіленій системі забезпечити надійність навіть у випадку виникнення будь-якого типу несправності вузлів, за умови, що кількість несправних вузлів не перевищує певної частки. Просто кажучи, поки кількість несправних вузлів (внаслідок не візантійських або візантійських помилок) менше певної частки від загальної кількості вузлів, алгоритми виправлення візантійських вад можуть гарантувати надійність системи. Через наявність багатьох недовірливих мережевих вузлів у блокчейн-системах, таких як Bitcoin і Ethereum, алгоритми виправлення візантійських вад використовуються в основному в механізмах консенсусу блокчейну. Найбільш представницькі алгоритми виправлення візантійських вад включають PBFT (Practical Byzantine Fault Tolerance), PoW (Proof of Work) та PoS (Proof of Stake).