Задача візантійських генералів досліджує, чи можуть справні процеси узгодити одне рішення, коли несправні поводяться довільно та надсилають суперечливі повідомлення різним адресатам. Формулювання Лампорта, Шостака й Піза 1982 року доводить нижню межу 3m+1 учасників для допуску m зрадників у моделі усних повідомлень без підписів і описує рекурсивні алгоритми для усних та підписаних повідомлень. Це результати за точних припущень, а не синонім будь-якого блокчейн-консенсусу.
Лампорт, Шостак і Піз опублікували алегорію в ACM TOPLAS у липні 1982 року для пояснення інтерактивної узгодженості реплікованих систем. Розділені генерали мають обрати один план, хоча зрадник може надсилати різним адресатам різні твердження. Візантійська відмова сильніша за зупинку: компонент може брехати, суперечити собі, мовчати або виглядати справним лише для частини системи. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
Стаття розрізняє IC1: усі вірні лейтенанти виконують однаковий наказ, та IC2: якщо командир вірний, вони виконують його наказ. Сучасні відповідники — узгодженість або safety, валідність і завершення або liveness. Гарантії мають зміст лише разом із моделлю мережі, автентифікацією та межею кількості відмов. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
У моделі усних повідомлень відомий безпосередній відправник, відсутність виявляється і кожна пара може спілкуватися, але зрадник надсилає різні значення. OM(m) рекурсивно пересилає значення і застосовує детерміновану більшість. Для m візантійських процесів потрібно щонайменше 3m+1 учасників — понад дві третини вірних. Троє не витримують одного зрадника через нерозрізнюваність його ролі. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)]
Непідробний підпис викриває суперечливі повідомлення й не дає змінити підписаний наказ справного учасника. Алгоритм пересилає нові підписані значення та однаково вирішує за зібраною множиною. За ідеальних припущень допускається будь-яка кількість зрадників. Проте підпис доводить походження, а не правдивість, своєчасну доставку чи чесність скомпрометованого ключа; Долев і Стронг уточнили межі раундів. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Dolev & Strong — Authenticated Algorithms for Byzantine Agreement (1983)]
Можливість гарантувати поступ залежить від часових умов. Результат Fischer–Lynch–Paterson 1985 року показує, що в повністю асинхронній детермінованій системі повідомлень навіть один процес, якому дозволено аварійно зупинитися, залишає допустиме виконання без завершення консенсусу. FLP не стверджує, що реальні системи ніколи не погоджуються. Гарантія поступу потребує додаткових припущень, наприклад часових меж, що зрештою починають діяти, або детектора відмов із визначеними властивостями, чи переходу до рандомізованого протоколу. Самого призначення лідера недостатньо. За тривалого розділення мережі безпечний протокол може припинити завершувати операції. [Fischer, Lynch & Paterson — Impossibility of Distributed Consensus with One Faulty Process (1985)] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
PBFT Мігеля Кастро й Барбари Лісков 1999 року перетворює візантійську згоду на реплікований автомат станів. Базова конфігурація n = 3f+1 витримує f візантійських реплік. Підготовленість включає pre-prepare від первинної репліки та 2f відповідних повідомлень prepare; локальне підтвердження вимагає підготовленості й 2f+1 відповідних повідомлень commit. Перетини кворумів і правила зміни виду запобігають суперечливим підтвердженням. Автентифікація, порядкові номери, контрольні точки й зміни виду протидіють підробленню, повторенню, зростанню журналу та несправному лідеру. Відомий склад реплік і детермінована остаточність відрізняються від відкритої мережі Proof of Work. [Castro & Liskov — Practical Byzantine Fault Tolerance (1999)]
Bitcoin не використовує OM чи PBFT і не рахує вузли з відомими іменами. Стійкий до атак Sybil механізм Proof of Work зважує конкурентні історії за накопиченою роботою; кожен Full Node самостійно відкидає блоки, що порушують правила консенсусу, та слідує дійсному ланцюгу з найбільшою сукупною роботою. Тимчасові розгалуження очікувані. За припущень про чесну більшість роботи й комунікацію ймовірність переписування зменшується з глибиною підтверджень, але це не математична незворотність. Модель Bitcoin Backbone формалізує спільний префікс, зростання та якість ланцюга за явно заданої частки роботи нападника й мережевих умов. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol]
Твердження, що Bitcoin розв’язав задачу візантійських генералів, приховує зміну моделі. Класична згода починається з фіксованої групи відомих учасників і межі f; Bitcoin допускає мінливих псевдонімних учасників та зовнішній дефіцитний ресурс. Його гарантії все одно потребують конкретних припущень про доставлення повідомлень. Proof of Work обмежує вплив ідентичностей Sybil, але не запобігає атакам eclipse, цензурі, егоїстичному майнінгу, помилкам програм чи реорганізації за більшості хешрейту. Модель загроз має визначати нападника, часові умови, членство й остаточність; самого позначення BFT недостатньо. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
Для повної картини прочитайте також Nakamoto consensus, Proof of Work, Правила консенсусу, Подвійна витрата, Bitcoin, Finality.