Що таке завдання візантійських генералів і як воно пов’язане з BFT?

Що таке завдання візантійських генералів?

Завдання візантійських генералів — це теоретична дилема, вперше представлена 1982 року в роботі Леслі Лемпорта, Роберта Шостака і Маршала Піза під назвою The Byzantine Generals Problem. Її суть полягає в наступному.

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

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

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

Це створює ризик отримання неправдивої інформації. Наприклад, один із воєначальників виявиться зрадником і навмисно передасть неправдиве повідомлення. Або під час відправлення відбудеться підміна листа недоброзичливцями.

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

Тому під час розв’язання задачі необхідно придумати механізм взаємодії генералів у такий спосіб, щоб вони дійшли консенсусу, навіть якщо частина з них передасть хибні дані.

Що таке BFT?

На перший погляд, це завдання ніяк не пов’язане з роботою блокчейну. Однак насправді вирішення цієї дилеми безпосередньо впливає на таку його властивість, як BFT, у зв’язку з чим і була написана вищезгадана стаття The Byzantine Generals Problem.

Byzantine Fault Tolerance (BFT) або візантійська відмовостійкість — це здатність системи продовжувати роботу в разі, якщо один із вузлів мережі недобросовісно виконує свої функції, незалежно від причини.

У результаті теоретичне розв’язання задачі візантійських генералів дає змогу на практиці наділити блокчейн властивістю BFT, яка може бути застосована не тільки до блокчейну, а й до інших технічних напрямів. При цьому наявність цієї характеристики особливо актуальна для децентралізованих мереж, оскільки її відсутність ставить їхню безпеку під загрозу. Наприклад, у результаті атаки 51%.

Варіації BFT

На момент написання існують дві основні концепції реалізації цієї властивості.

Practical Byzantine Fault Tolerance (PBFT)

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

Вони обмінюються між собою інформацією про статус перевірки. Якщо з блоком усе гаразд, то основна нода включає його в блокчейн. При цьому для досягнення консенсусу необхідно 2/3 голосів усіх службових вузлів.

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

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

Також у деяких випадках можливе захоплення контролю над блокчейном за допомогою тієї самої атаки 51%, якщо зловмисник підключить до мережі достатню кількість вузлів.

Federated Byzantine Agreement (FBA)

FBA є більш гнучким і масштабованим механізмом. Шляхом загального голосування ноди обирають представників, яким вони довіряють. Довіра ґрунтується переважно на минулій активності учасника мережі, що дає розуміння про його сумлінність.

Потім кожен обраний вузол формує так звану підмережу, що складається зі звичайних нод, яким він «вірить». У кожному подібному кластері відбувається своє досягнення консенсусу.

Довірений вузол формує блок транзакцій і пропонує його включити в блокчейн. Підмережа зобов’язана перевірити і вирішити питання щодо його додавання.

Так відбувається перший етап валідування мережі в кластерах. Обрана нода «вірить» виключно власній групі учасників. Після цього діяльність переходить на другий рівень. Лідери підмереж домовляються між собою. Якщо вони приходять до спільного консенсусу, блок додається в блокчейн.

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

Однак у цій конфігурації великий ризик централізації, коли ноди функціонують лише у «власних» групах, куди може стати проблематично потрапити новим користувачам.

Практичне використання BFT

Хоча BFT є важливою властивістю, без якої блокчейн не зможе нормально функціонувати, його концепції реалізації є лише орієнтиром. Жоден із блокчейнів не використовує їх у чистому вигляді. Ні PBFT, ні FBA. Натомість більшість проєктів експлуатують певні елементи, які потім використовуються для створення алгоритмів досягнення консенсусу.

Більшою мірою це стосується системи Practical Byzantine Fault Tolerance, яка стала основою для Proof-of-Stake, Proof-of-Work та інших алгоритмів досягнення консенсусу. Вони імплементували аспекти безпеки, закладені у розв’язанні задачі візантійських генералів, завдяки чому децентралізовані мережі можуть справлятися в більшості випадків зі збоями або потенційними атаками на них.

Висновки

Завдання візантійських генералів було запропоновано ще 1982 року, коли блокчейн не існував навіть на рівні концепції. Проте дилема заклала принципи, які в підсумку дали змогу створити алгоритми досягнення консенсусу, що мають властивість BFT.

Без цієї здатності розподілені мережі не змогли б якісно і безпечно обробляти транзакції, що, своєю чергою, могло підірвати довіру користувачів і завадити розвитку криптовалютної індустрії загалом.