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

Вступ

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

Походження

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

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

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

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

Візантійська помилковість

Припустимо, є n генералів і t зрадників. Скажімо, n=3, t=1, отже, один з A, B і C є зрадником. Якщо A віддає команду [атака], але зрадник B каже C [відступити], тоді C не може прийняти рішення; Якщо зрадник B посилає команду [атака] до A і команду [відступ] до C, тоді A і C не можуть дійти згоди. Тому, коли кількість зрадників більше або дорівнює 1/3, проблема візантійських генералів не може бути вирішена.

Аналогічно, припускаючи, що загальна кількість вузлів мережі дорівнює N, а кількість шкідливих вузлів дорівнює T, проблему можна вирішити лише тоді, коли N>=3T+1, тобто кількість нормальних вузлів у мережі становить принаймні ( 2/3) N, щоб забезпечити послідовність інформації. У надійному мережевому зв’язку Byzantine Fault Tolerance може певною мірою вирішити проблему збою вузла, щоб система могла досягти консенсусу.

Механізм підтвердження роботи (PoW).

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

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

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

Алгоритми з асиметричним ключем

Для шифрування та дешифрування алгоритмів з асиметричним ключем потрібні два окремі секретні ключі – відкритий ключ і закритий ключ, які зазвичай з’являються парами. Якщо A хоче надіслати повідомлення B, A потрібен відкритий ключ B для шифрування інформації, а B потрібен власний закритий ключ для розшифровки інформації. Якщо B хоче показати свою особу, він/вона може підписати закритий ключ, написати «текст підпису» та передати його. Інші можуть підтвердити його/її особу за відкритим ключем B.

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