Byzantine Generals Problem — задача узгодження рішення між учасниками, які можуть брехати, мовчати або кожному повідомляти різне. Потрібна процедура, що не дозволить тим, хто дотримується правил, ухвалити суперечливі рішення. Гарантії залежать від зв’язку, перевірки походження повідомлень і кількості можливих збоїв.
Уявіть загони навколо міста. Вони мають разом наступати або разом відступати: розрізнені дії можуть їх згубити. Командир надсилає накази, але хтось може зрадити й розповідати іншим різні версії. Як надійним учасникам зрештою діяти однаково? Це не розповідь про справжню битву, а уявний приклад для комп’ютерів, яким потрібні узгоджені записи. Наприклад, кілька серверів — комп’ютерів, що забезпечують спільну службу, — повинні однаково визначити, чи вже оброблено платіж. Самого отримання відповіді недостатньо: відповіді мають вести до спільного рішення. [1] [9]
Leslie Lamport, Robert Shostak і Marshall Pease представили відоме формулювання в липні 1982 року, після своєї роботи 1980 року про узгодження за наявності збоїв. Зрадник позначає компонент, поведінку якого вже не можна передбачити. Комп’ютер не обов’язково просто зупиниться. Він може правильно відповісти одному сусідові й неправильно іншому, пропустити повідомлення або стверджувати, що бачив інше. Причиною буває як атака, так і помилка програми. Візантійський збій описує те, що спостерігають інші, а не наміри пристрою. BFT (Byzantine Fault Tolerance) означає здатність системи витримувати таку поведінку за визначених умов. [1] [2]
Початкова задача має дві умови. IC1 вимагає, щоб усі надійні підлеглі прийняли однаковий наказ. IC2 додає: якщо командир також надійний, вони повинні прийняти саме його наказ. Без другої умови правило «завжди відступайте» здавалося б розв’язком, але ігнорувало б чесного командира. У комп’ютерних системах розрізняють безпеку — відсутність суперечливих результатів — і живучість, тобто здатність узагалі отримати результат. Інші правила визначають допустимі результати. Узгоджений запис сам по собі не доводить, що введене твердження було правдивим у зовнішньому світі. [1] [9]
Позначимо командира A, а підлеглих B і C. C отримує від A наказ наступати, але B каже, що командир наказав відступати. Бреше B чи командир надіслав різні накази? Без підпису, який можна перевірити після пересилання, C може не розрізнити ці ситуації. Та сама невизначеність можлива для B. Якщо обидва завжди слухатимуться командира, нечесний A розділить їх; якщо завжди ігноруватимуть його, порушать умову для чесного командира. Отже, у цій задачі з трьома учасниками й одним можливим зрадником немає процедури без підписів, що завжди досягає успіху. Бракує інформації для розрізнення випадків, а не швидших комп’ютерів. [1] [9]
У класичній моделі без підписів для m можливих зрадників потрібно щонайменше n ≥ 3m+1 учасників: для одного — чотири. Тут n — загальна кількість учасників, а m — найбільша кількість зрадників, яку система має витримати. Недостатньо додати голос і раз підрахувати більшість. OM(m) передбачає повторне пересилання почутого й оцінювання повідомлень за спільними правилами; базовий випадок OM(0) приймає значення командира або узгоджене запасне значення. Модель припускає відомих учасників, прямі з’єднання, правильне доставлення надісланих повідомлень, відомого безпосереднього відправника й можливість виявити відсутнє повідомлення. «Без підписів» не означає «без жодної перевірки походження». Без цих припущень число чотири нічого не гарантує. [1] [9]
За допомогою перевірного цифрового підпису, Digital Signature, B може показати C, що саме підписав командир. Програма створює підпис за допомогою приватного ключа — секретного числового значення. Інші перевіряють його відповідним відкритим ключем, не знаючи приватного. Зрадник не може непомітно змінити наказ надійного учасника або підробити його підпис. Алгоритм підписаних повідомлень поширює підписані значення й застосовує спільне правило вибору. У цій моделі зникає зазначена вимога чесної більшості, але залишаються припущення про непідробність підписів, доставлення й часові умови раундів. Робота Dolev і Strong 1983 року далі досліджує потрібну кількість раундів. Навіть правильний підпис не гарантує правдивості змісту чи своєчасної доставки й не доводить, що приватний ключ не викрали. Він засвідчує походження повідомлення, а не загальну чесність відправника. [1] [3]
Коли сервер не відповідає, інші не знають, чи він зупинився, чи має дуже повільний зв’язок. Результат FLP, опублікований Michael Fischer, Nancy Lynch і Michael Paterson у 1985 році, точно описує цю невизначеність. Процес тут — це програма, що виконується. Детермінована процедура за однакового стану й вхідних даних робить той самий наступний крок, а не обирає його випадково. У повністю асинхронній системі без відомої верхньої межі затримки детермінована процедура не може гарантувати завершення узгодження в кожному допустимому перебігу, якщо навіть один процес може аварійно зупинитися. Це справедливо й за надійного доставлення без обмеження затримок. Це не означає, що спільного рішення ніколи не буде. Практичні системи додають часові припущення, відповідний детектор збоїв або випадковість. Під час поділу мережі чекати може бути безпечніше, ніж підтверджувати несумісні результати. [4] [13] [8]
Miguel Castro і Barbara Liskov у 1999 році описали Practical Byzantine Fault Tolerance, PBFT, для служби з кількома відомими копіями. Це копії служби, які працюють на різних серверах і постійно обробляють ті самі запити. Їх називають репліками; це не збережені резервні файли. Базова конфігурація n = 3f+1 витримує f несправних копій. Із чотирьох серверів один може бути візантійським; дві групи по три мають щонайменше два спільні сервери, серед яких принаймні один надійний. Потрібний набір підтверджень називають кворумом. Самого перетину недостатньо: важливі правила фаз і зміни керівника. Точніше, стан prepared потребує запиту, повідомлення pre-prepare та 2f відповідних prepare від різних реплік, які не є провідною. Локальне підтвердження додатково потребує 2f+1 повідомлень commit, можливо разом із власним. Перевірка походження, порядкові номери й контрольні точки протидіють підробкам, повторенням і необмеженому зростанню журналу. Безпека не залежить від часових меж, але поступ потребує додаткових умов щодо затримок. [5] [10] [11] [12]
Bitcoin не має заздалегідь закритого списку серверів. Якби кожен новий обліковий запис мав голос, нападник міг би створити більшість: це Sybil Attack. Тому Proof of Work пов’язує створення блоків з обчислювальною роботою. Блок — це пакет транзакцій, який додають до спільної історії. Full Node — комп’ютер із програмою, яка самостійно перевіряє правила, — спочатку відкидає недопустимі блоки, а потім обирає допустиму гілку з найбільшою накопиченою роботою. Bitcoin не виконує OM чи PBFT; тимчасові розгалуження є частиною роботи мережі. За достатньої переваги чесної потужності та відповідного зв’язку додаткові підтвердження знижують ризик переписування історії, але не дають абсолютної незворотності. Дослідження Bitcoin Backbone розглядає ці умови: узгодженість історій, зростання ланцюга й частку блоків чесних учасників. [6] [7]
Почувши «мережа досягає консенсусу», запитайте: хто може брати участь, що контролює нападник, як довго можуть іти повідомлення й коли рішення може змінитися? Навіть Proof of Work не усуває всіх труднощів. Eclipse Attack ізолює вузол від чесних сусідів, цензура виключає транзакції, а Selfish Mining передбачає приховування видобутих блоків. Залишаються помилки програм і можливість переписати частину історії за достатньої переваги нападника. Проте навіть більшість обчислювальної потужності не змусить справний Full Node прийняти блок, що порушує його правила. Історія генералів вчить з’ясовувати умови досягнення спільного рішення, а не довіряти самій назві технології. [6] [7] [8]
Для повної картини прочитайте також Nakamoto Consensus, Proof of Work, Правила консенсусу, Подвійна витрата, Bitcoin, Finality. На цю статтю також посилаються Nakamoto Consensus.