Задача Візантійських генералів

Задача

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

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

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

Ситуація проста - всі елементи один одному довіряють за замовчуванням, але що робити, якщо деякі з них помиляються, а інші - свідомо надають неправдиву інформацію? Як в такій ситуації прийняти загальне «колегіальне» рішення? Дане завдання носить назву «Проблеми Візантійських Генералів», а її рішення лежить в основі стійкості P2P мереж.

Суть задічі

Дане завдання було придумана в 1982 році, як типова ілюстрація того, наскільки сильні можуть бути проблеми знаходження колегіального рішення в великих групах, що складаються з рівноправних елементів.

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

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

Чи можна в такій ситуації домогтися ефективного колегіального рішення, з яким за визначенням доведеться погодитися всім учасникам процесу? Як виявилося - можна.

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

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

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

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

Алгоритми консенсусу

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

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

Висновок

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

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