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

Введение

Византийская проблема генералов, также известная как проблема двух генералов, была предложена в статье Лесли Ламберта об отказоустойчивости распределенной одноранговой сетевой коммуникации в 1982 году. В коммуникации распределенной системы некоторые локальные проблемы могут привести к тому, что компьютер будет посылать сообщения об ошибках и нарушит согласованность системы. Таким образом, Византийская проблема генералов - это, по сути, проблема консенсуса в коммуникации "точка-точка".

Происхождение

Проблема византийских генералов возникла в средние века. Из-за огромной территории Византии, связь между армиями может полагаться только на гонцов. Если найдется предатель, намеренно искажающий информацию руководителей армии, это приведет к несогласованности оперативных планов, что приведет к "византийским провалам".

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

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

Проблема византийских генералов в Интернете означает, что в процессе передачи канала некоторым узлам может быть трудно достичь синхронизации информации из-за чрезмерной рабочей нагрузки или некоторых злонамеренных атак. В 1999 году Мигель Кастро и Барбара Лисков предложили византийскую отказоустойчивость (BFT). Они считали, что если две трети узлов в системе работают нормально, то согласованность и корректность системы можно гарантировать. Позже Сатоши Накамото предложил механизм доказательства работы (PoW) и асимметричный криптографический алгоритм Биткойна, который обеспечил новое решение Византийской проблемы генералов.

Византийская отказоустойчивость

Предположим, что есть n генералов и t предателей. Допустим, n=3, t=1, поэтому один из A, B и C - предатель. Если А отдает команду [атака], но предатель В говорит С [отступить], то С не может вынести решение; Если предатель В посылает команду [атака] А и команду [отступление] С, то А и С не могут прийти к соглашению. Поэтому, когда число предателей больше или равно 1/3, Византийская проблема генералов не может быть решена.

Аналогично, если предположить, что общее количество узлов сети равно N, а количество вредоносных узлов равно T, то проблема может быть решена только тогда, когда N>=3T+1, то есть количество нормальных узлов в сети составляет не менее (2/3) N, чтобы обеспечить согласованность информации. В надежной сетевой коммуникации византийская отказоустойчивость может в определенной степени решить проблему отказа узла, так что система может достичь консенсуса.

Механизм доказательства работы (PoW)

Предположим, что генерал А сначала отдает команду [атака] и ставит свою подпись. После его получения, если другие генералы также планируют атаковать, они выполнят команду [атака] и его подпись после команды генерала А. Если А не выполнит команду [атака] после того, как А отправит ее, другие генералы могут оценить А как предателя и использовать это для выделения нужной информации.

Аналогично, несколько участвующих узлов получат результат через серию работ, и первый узел, получивший результат, будет транслировать его всей сети. Если результат верен, другие узлы добавят результат в свои собственные бухгалтерские книги, чтобы подготовиться к вычислениям, чтобы выиграть право на запись транзакций в блокчейн.

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

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

Для шифрования и дешифрования алгоритмов с асимметричным ключом необходимы два отдельных секретных ключа - открытый ключ и закрытый ключ, которые обычно располагаются попарно. Если A хочет отправить сообщение в B, A нужен открытый ключ B для шифрования информации, а B нужен его/ее собственный закрытый ключ для расшифровки информации. Если Б хочет показать свою личность, он/она может подписать закрытый ключ, написать "текст подписи" и передать его в эфир. Другие могут проверить его/ее личность по открытому ключу B.

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