Как разные протоколы решают задачу византийских генералов?

Что такое задача византийских генералов?

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

Суть задачи:

«Армии нескольких генералов (сетевые узлы) осаждают город. Общаться между собой они могут только отправляя гонцов (транзакции). Ключевая задача — договориться об общем плане нападения или отступления (консенсус). Некоторые генералы являются предателями и всячески хотят помешать договору».

Первую научную статью на эту тему в 1982 году опубликовали Лесли Лэмпорт, Роберт Шостак и Маршалл Пиз. Задача справедлива только к распределенным системам, где нет центрального узла, которому доверяют остальные участники сети. В реальном мире таким узлом может быть, например, центральный банк страны, отвечающий за эмиссию фиатной валюты, распределяя ее по счетам коммерческих банков.

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

Как Сатоши Накамото решил задачу византийских генералов?

В 2008 году создатель биткоина Сатоши Накамото предложил практическое решение задачи византийских генералов. Он разработал протокол биткоина и реализовал алгоритм консенсуса Proof-of-Work (PoW). Это позволило исключить элемент доверия, установив четкие правила достижения консенсуса (договора) между узлами распределенной сети биткоин (генералами).

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

Когда один из узлов решит выполнить «неправильную работу», все другие участники это увидят и не позволят произойти нежелательной активности. 

Какие алгоритмы консенсуса используются в криптовалютах?

Помимо Proof-of-Work, наиболее распространенными и надежными решениями задачи византийских генералов служат алгоритмы Proof of Stake (PoS) и Byzantine Fault Tolerance (BFT). 

Proof of Stake (PoS) является наиболее популярной версией на крипторынке. Суть механизма заключается в том, что вместо майнеров, как в PoW, управление сетью отдали владельцам нативной монеты. Главное преимущество такого подхода — незначительное потребление энергии в сравнении с PoW.

Byzantine Fault Tolerance (BFT) — предназначен для масштабирования сетей PoS-блокчейнов. В отличие от предыдущих, BFT использует коллективное принятие решений в достижении консенсуса. Узлы отправляют транзакции друг другу пока ⅔ всех узлов не придут к одинаковому результату.

На рынке существует множество модификаций и гибридных алгоритмов. Один из таких — Tendermint, лежащий в основе блокчейна Cosmos, где одновременно применяются Delegated Proof-of-Stake (DPoS) и BFT. А, например, Solana использует dPoS и имплементацию алгоритма консенсуса BFT — Practical Byzantine Fault Tolerance (pBFT).

Кроме этих алгоритмов в криптовалютах применяют более десятка вариантов консенсуса. Перечислим некоторые из них:

• Leased Proof of Stake (LPoS) — очередная разновидность PoS, где пользователи могут участвовать в генерации блоков, передавая токены в лизинг «главным» узлам. Этот консенсус применяется в блокчейне Waves;
• Proof of Elapsed Time (PoET) — доказательство истекшего времени. Модификация PoW, использующая мощности CPU. Здесь заложены принципы алгоритма справедливой лотереи, где случайным образом выбирается валидатор пропорционально вложенным ресурсам. Используется в решениях от Hyperledger;
• Delegated Byzantine Fault Tolerance (DBFT) — модификация сразу двух алгоритмов: PBFT и DPoS. Этот вариант достижения консенсуса применяют в блокчейне NEO;
• Directed Acyclic Graphs (DAG) — направленный ациклический граф. Это не консенсус, но альтернативная блокчейну технология. DAG состоит из кругов и линий, а не из блоков, и выглядит как граф. Алгоритмы консенсуса в таких сетях могут использоваться привычные, однако способ записи информации кардинально другой. Одним из таких гибридов является Hashgraph;
• Proof of Activity (POA) — доказательство активности. Использует гибридный механизм на основе PoW и PoS. Наиболее известный представитель — Decred;
• Proof of Importance (Pol) — в доказательстве важности лежат принципы рейтинговой системы. Чем выше условный рейтинг валидатора, тем больше у него шансов найти блоки. Известность этому виду консенсуса принесла сеть NEM;
• Proof of Capacity (PoC) — доказательство емкости. Использует вместо вычислительных ресурсов пространство на жестком диске. Консенсус применяется в сетях Chia и BitTorent;
• Proof-of-Personhood (PoP) — доказательство личности. Использует механизмы подтверждения «человечности», гарантируя, что каждый участник проекта получит равный голос и долю вознаграждения. Флагманом выступает криптовалюта Worldcoin.