Проблема візантійських генералів (The Byzantine Generals Problem)

Проблема візантійських генералів - це аналогія в комп'ютерній науці, яка використовується для опису проблеми встановлення і підтримки безпеки в розподіленій мережі. Для вирішення цієї проблеми чесні вузли (наприклад, комп'ютери або інші фізичні пристрої) повинні мати можливість досягти консенсусу, незважаючи на наявність нечесних вузлів. Це означає, що більшість вузлів повинні встановити набір правил і домовитися про те, як забезпечити дотримання цих правил в мережі.

У цій статті ми більш детально пояснимо, що таке проблема візантійських полководців і чому її так важливо вирішити. Ми розглянемо деякі з найкращих рішень, які були запропоновані та реалізовані протягом багатьох років. Нарешті, ми обговоримо, як різні блокчейн-мережі використовували протоколи консенсусу для подолання проблеми візантійських полководців і сприяння безпечним транзакціям.

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

Проблема візантійських генералів - це загальний виклик, який повинні подолати децентралізовані комп'ютерні системи. Давайте розглянемо цю аналогію і те, як вона пов'язана з сучасною безпекою даних.

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

У 1982 році Леслі Лампорт, Роберт Шостак і Маршалл Піз опублікували дослідницьку роботу під назвою "Проблема візантійських генералів" (The Byzantine Generals Problem). Важливість цієї концепції зрозуміла вже з першої сторінки, де зазначено, що їх дослідження фінансувалося Національним управлінням з аеронавтики і дослідження космічного простору (NASA), Командуванням систем протиракетної оборони та Армійським науково-дослідним управлінням. Хоча проблема візантійських полководців існувала в інформатиці задовго до 1982 року, це була одна з перших спроб поставити цю проблему в релевантну аналогію і запропонувати шляхи її розв'язання.

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

Хоча фактичне вирішення проблеми візантійських генералів є досить складним, ми тепер розуміємо фундаментальний виклик. Вкрай важливо визнати, що концепція може бути застосована виключно до військових комунікацій, як це і відбувається за аналогією. Однак, ця проблема насправді стосується всіх видів комп'ютерних систем, не пов'язаних з військовим застосуванням. Кожного разу, коли розподілена група вузлів (наприклад, комп'ютерів або інших фізичних пристроїв) потребує надійного зв'язку, мережа повинна вирішити проблему візантійських полководців.

Візантійські збої

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

Застосовуючи цю концепцію до реальних комп'ютерних систем, це може бути програмна помилка, апаратна несправність і/або зловмисна атака. Іншими словами, візантійські збої не обов'язково повинні бути організованою атакою зловмисників. Це можуть бути просто проблеми, які заважають вузлам прийти до згоди щодо рішень для розподіленої мережі.

Візантійська відмовостійкість

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

У помірно захищеній мережі така проста подія, як вихід з ладу декількох вузлів, не має помітного впливу на мережу. Здатність захищатися від таких сценаріїв відома як візантійська відмовостійкість. Вважається, що мережі, які здатні впоратися з більшою кількістю візантійських збоїв, мають більш високу толерантність, що означає, що вони більш безпечні, ніж ті, які не можуть впоратися з візантійськими збоями.

Досягнення візантійської відмовостійкості

Досягнення візантійської відмовостійкості історично було складним завданням. Це пов'язано з тим, що перед комп'ютерними науковцями стоїть широкий спектр проблем безпеки, які необхідно враховувати. Крім того, існує потреба у створенні практичних рішень, спрямованих на усунення, здавалося б, абстрактних, теоретичних загроз. Ось кілька рішень, які були розроблені протягом багатьох років для різних додатків розподілених систем.

Ранні рішення

Дослідження візантійської відмовостійкості почалися в 1950-х роках і в основному оберталися навколо авіаційної промисловості. Наприкінці 1970-х і на початку 1980-х років було розроблено декілька рішень Візантійської відмовостійкості для літаків і космічних апаратів.

У 1978 році дослідники з Лабораторії Дрейпера опублікували технічний звіт про відмовостійкий мультипроцесор (Fault-Tolerant Multiprocessor, FTMP) - багатопроцесорний комп'ютер, який усуває вразливість до однієї несправності для авіаційних модулів. Ці дослідження тривали протягом 1980-х років.

Наприкінці 1970-х років компанія Honeywell Labs розробила мікропроцесорну систему управління польотом (MMFCS), яка забезпечила точне виявлення візантійських відмов і можливість диференціювати їх від інших типів відмов. У 1981 році SRI International, та сама організація, яка придумала термін "проблема візантійських генералів", опублікувала технічний документ для комп'ютера управління літаком під назвою Software Implemented Fault Tolerance (SIFT).

Паксосський протокол і парламент з неповним робочим днем

У 1989 році Леслі Лампорт вперше опублікував Паксосський протокол. У 1998 році Лампорт опублікував статтю під назвою "Парламент, що працює неповний робочий день", в якій описав це рішення проблеми візантійських генералів. Знову ж таки, проста аналогія може бути використана для розуміння складної проблеми.

У давнину островом Паксос в Егейському морі керував парламент, що працював неповний робочий день. Оскільки торгівля була пріоритетнішою за управління, ніхто на Паксосі не бажав ставати повноцінним членом парламенту острова. Це означало, що уряд повинен був знайти спосіб безперервного функціонування навіть тоді, коли його чиновники входили і виходили зі своїх ролей. Оскільки багато деталей про те, як працював парламент, було втрачено для історії, Лампорт зробив деякі припущення про те, як працювала система управління. Лампорт виявив, що ця система була схожа на виклики, які повинні вирішувати сучасні розподілені системи.

На основі цієї аналогії Лампорт та інші вчені-комп'ютерники розробили протокол Paxos, який фактично є сімейством консенсусних протоколів, що лягли в основу підходу реплікації державних машин. У той час як попередні системи вимагали, щоб вузли були одночасно онлайн і спілкувалися синхронно для досягнення консенсусу, протокол Paxos був асинхронним. По суті, реплікація машинних станів представила ефективний спосіб для вузлів розподіленої системи виконувати незалежну перевірку і спілкуватися в асинхронному або напівсинхронному режимі.

Це передбачає чотири основні кроки.

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

Протокол Paxos став значною подією в галузі комп'ютерних наук, оскільки він ввів спосіб гарантувати узгодженість даних у розподіленій системі і дозволив мережам стати більш захищеними від можливих візантійських збоїв.

Практична візантійська відмовостійкість (pBFT)

У 1999 році Мігель Кастро і Барбара Лісков опублікували наукову роботу під назвою "Практична візантійська відмовостійкість", в якій представили новий алгоритм досягнення візантійської відмовостійкості. Слово "практичний" використовується тому, що Кастро і Лісков виявили, що раніше розроблені алгоритми або припускали, що мережа є синхронною, або не забезпечували практичних засобів досягнення консенсусу для асинхронних систем.

Цей алгоритм, який зазвичай скорочено називають pBFT, дозволяв асинхронним мережам обробляти тисячі запитів за секунду з лише субмілісекундним збільшенням затримки. Хоча це стало великим проривом для розподілених систем, pBFT зіткнувся з двома основними проблемами, які обмежили його застосування. По-перше, pBFT стає більш дорогим у використанні зі збільшенням кількості вузлів. По-друге, pBFT вразливий до атак Sybil - поширеної загрози безпеці, в якій зловмисник використовує декілька псевдонімів для контролю над більшістю вузлів в одноранговій мережі. Пізніше було впроваджено більше протоколів для вирішення деяких обмежень pBFT. Наприклад, Q/U, HQ, Zyzzyva та ABsTRACT були зосереджені на вирішенні питань продуктивності та вартості. Aardvark і RBFT зосереджувалися на вирішенні питань надійності.

Мережа Біткоїн

У жовтні 2008 року Сатоші Накамото опублікував оригінальний документ "Біла книга Біткоїна". Хоча термін "проблема візантійських полководців" жодного разу не використовується в цьому документі, Накамото фактично запропонував рішення, яке було реалізовано із запуском мережі Біткоїн у січні 2009 року. Біткоїн став першим у світі блокчейном, який є одним з різновидів технології розподіленого реєстру (DLT).

Мережа надала користувачам можливість безпечно надсилати та отримувати цифрову валюту під назвою Bitcoin (BTC). Інші розподілені системи для цифрових платежів були запропоновані до Bitcoin, але вони не мали успіху в основному через їх нездатність запобігти візантійським збоям. Оскільки ці рішення не вирішували проблему візантійських генералів, вони були схильні до загрози безпеки, відомої як проблема подвійних витрат. Іншими словами, користувачі могли витрачати кошти, яких насправді не існувало. З біткоїном проблема подвійних витрат вирішена, оскільки дизайн мережі забезпечує дуже, дуже високий рівень візантійської відмовостійкості.

Так як же мережа Біткоїн досягає цього? Важливо розуміти, що Біткоїн спирається на попередні рішення проблеми візантійських генералів. Наприклад, мережа забезпечує асинхронний зв'язок між вузлами і, по суті, є реплікованим автоматом. Безпека мережі також ґрунтується на поєднанні таких концепцій, як асиметричне шифрування, однорангова мережева технологія та доказ роботи (Proof of Work, PoW). Як і протокол Paxos або pBFT, Proof of Work є консенсусним протоколом. Хоча PoW був вперше запропонований в 1992 році, Біткоїн став першою мережею, яка запровадила конкурентний аспект перевірки даних PoW, відомий як майнінг. Незабаром більше мереж, заснованих на PoW, почали використовувати рішення біткоїна для вирішення проблеми візантійських полководців. Незабаром з'явилися й інші різновиди протоколів консенсусу блокчейну.

Візантійські рішення відмовостійкості для мереж блокчейн

В даний час існує три основних типи протоколів консенсусу, що використовуються в мережах блокчейн. Існує досить багато варіацій в численних реалізаціях цих протоколів; однак, більшість мереж використовують одну і ту ж загальну механіку для досягнення візантійської відмовостійкості.

Proof of Work (PoW)

Як зазначалося вище, Біткоїн став першою мережею, яка реалізувала процес, відомий як видобуток криптовалюти за консенсусом Proof of Work (PoW). У цій системі проблема візантійських полководців вирішується шляхом винагороди чесних користувачів (відомих як майнери), які вирішують складні математичні задачі за допомогою потужних комп'ютерів. Після того, як правильне рішення перевірено, майнер отримує винагороду в рідній монеті мережі блокчейн.

Хоча цей процес насправді вимагає ще кількох кроків, головна ідея, яку слід зрозуміти, полягає в тому, що великі блокчейн-мережі на основі PoW, такі як Біткоїн, є дуже безпечними. Це тому, що знадобилися б мільйони доларів, щоб навіть спробувати атакувати мережу і створити візантійський збій. Щоб успішно здійснити атаку подвійних витрат, нечесним майнерам потрібно було б отримати контроль над 51% обчислювальних потужностей мережі, що відомо як атака 51%. Хоча це практично неможливо в мережі Біткоїн, це насправді є серйозною проблемою для менших мереж з меншою кількістю майнерів, оскільки обчислювальні ресурси і витрати набагато нижчі.

Proof of Stake (PoS)

Вперше впроваджений у 2012 році, Proof of Stake (PoS) - це ще один протокол консенсусу в блокчейні, який спрямований на вирішення проблеми візантійських генералів. На відміну від мереж на основі PoW, мережі на основі PoS не покладаються на майнінг криптовалюти. Замість цього використовується процес, відомий як стейкінг. У цій системі користувачі (відомі як валідатори) вносять кошти. Валідатори, які вкладають більшу частину монет блокчейну, можуть підтвердити більше блоків і отримати більше винагороди. Крім того, користувачі, які намагаються підтвердити недійсні транзакції, можуть втратити свої кошти.

Користувачі можуть розміщувати монети за допомогою звичайних домашніх комп'ютерів, а не спеціалізованих комп'ютерів, необхідних для майнінгу в мережі на основі PoW. Деякі мережі на основі PoS реалізували рішення, які запобігають атакам подвійних витрат та іншим можливим проблемам безпеки, які можуть виникнути в результаті збоїв в роботі "Візантії". Наприклад, в Ethereum 2.0 (Serenity) буде використовуватися алгоритм PoS під назвою Casper, який вимагає більшості в дві третини голосів вузлів для досягнення консенсусу перед створенням блоків.

Делегований доказ частки Delegated Proof of Stake (DPoS)

Делегований доказ частки (DPoS), вперше впроваджений в 2014 році, є протоколом консенсусу в блокчейні, який працює подібно до Proof of Stake. Обидва вимагають від користувачів внесення коштів. Однак, в мережах, заснованих на DPoS, тільки кілька користувачів (відомих як делегати) можуть підтверджувати транзакції і створювати блоки. Як правило, всі користувачі можуть вкладати монети блокчейну, щоб віддати свій голос на користь кандидата в делегати. Вибрані вузли, як правило, розподіляють винагороду за блок між своїми виборцями пропорційно до суми коштів, внесених на виборах делегатів.

За допомогою DPoS вузли здатні досягати консенсусу набагато швидше, ніж PoW або PoS. Це означає, що транзакції можуть оброблятися набагато швидше в масштабі. Компроміс полягає в тому, що підтримка високого рівня візантійської відмовостійкості з DPoS може стати складною в деяких ситуаціях. Менша кількість вузлів відповідає за безпеку мережі, а це означає, що теоретично вузлам легше вступити в змову проти інтересів більшості. Однак, мережі на основі DPoS прагнуть уникнути цього сценарію, часто проводячи вибори делегатів, щоб гарантувати, що делегати залишаються відповідальними за свої рішення.

Джерела:

• https://komodoplatform.com/en/academy/byzantine-generals-problem/