📝 Проблема с Византийскими Генералами (перевод статьи @dantheman)

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

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

Доказательство проделанной работой (PoW) не решает задачу Византийских Генералов

Биткойн и другие PoW алгоритмы считают, что лучшая цепь та, в которой доказательство работой наиболее сложное. Имея в виду византийскую задачу можно сказать, что проблема с доказательством работой состоит в том, что всегда остается возможность обратимости блокчейна, просто это становится все менее вероятно и неэкономично. Чтобы считать Биткойн и похожие блокчейны отказоустойчивыми, Вы должны принять, что 99,999% уверенности - это то же самое, что и 100%. Кто-либо, обладающий 10% хэш-мощности, может провести двойную транзакцию против того, кто ожидает шести подтверждений раз в месяц, или 0.02% времени.

White Paper проекта Cosmos

White paper проекта Cosmos содержит заявление о работающем алгоритме византийской отказоустойчивости, посредством которого группа производителей блоков способна единогласно договориться о следующем блоке. Они заявляют, что их процесс гарантирует сети продвижение до тех пор, пока ⅔ остаются честны. Весь остальной мир не должен иметь в виду форки блокчейна, так как они “невозможны” в их алгоритме.
Я был крайне впечатлен основательностью их подхода и надежностью их алгоритма. Я также был признателен за то, что некоторые люди из их команды уделили время оценке моего собственного алгоритма - Делегированного Доказательства Владением Долей (Delegated Proof of Stake - DPOS).

Делегированное Доказательство Владением Долей (DPOS)

DPOS - это алгоритм, где держатели долей избирают нечетное число производителей блоков. В каждом раунде производители блоков перетасовываются и назначается временной интервал, в который они должны произвести блок. При таком процессе наилучшей цепью считается самая длинная цепь. Меньшинство производителей блоков не способно создать цепь длиннее, так как они будут производить меньше блоков в минуту, чем большинство блокчейна.

Как и с Биткойном, используя только такую модель невозможно достичь 100% уверенности, так как большинство может неожиданно переключиться на форк меньшинства и перестать производить блоки сами. В итоге форк меньшинства станет длиннее и глобальный консенсус обязательно будет изменен.

На этот случай мы представили новый концепт, известный как Последний Необратимый Блок (Last Irreversible Block - LIB). Это блок, который был подтвержден ⅔ или более избранных производителей блоков. Ни одна нода автоматически не переключится на форк, который не был построен на основании последнего необратимого блока.

Члены сообщества Cosmos недавно обнаружили определенную последовательность событий, которая способна сломать алгоритм LIB, вызвав разделение сети на два различных LIB. Эта уязвимость алгоритма LIB не вызывает остановку алгоритма DPOS, так как алгоритм LIB является опциональным дополнением, разработанным для определения числа необходимых подтверждений, которые нужны бирже для получения гарантии того, что блок не будет брошен. Алгоритм LIB схож с алгоритмом 6 подтверждений, используемым в Биткойне. Он срабатывает 99.9999% времени. За два с лишним года работы и десятки миллионов блоков спустя он все еще не столкнулся с тупиковым состоянием, которое теоретически возможно.

Реальная проблема в том, кто же генералы

Проблема с Cosmos кроется в подразумеваемом предположении, что набор генералов фиксирован. По крайней мере, для отдельного блока. Если в какой-то момент более ⅓ генералов станут предателями, то сеть остановится и нет такого процесса, который бы мог ее перезапустить. В DPOS, если крупное меньшинство генералов решит предать, сеть все равно будет работать в состоянии “ожидания”. Блоки будут производиться, голоса подаваться, и могут быть выбраны новые генералы. В итоге держатели долей могут дойти до точки, где 100% генералов честны и сеть возобновит нормальную работу. В теории, если 95% генералов предадут, оставшиеся 5% все равно могут провести выборы, чтобы их заменить.

Из этого можно сделать вывод, что Cosmos обладает иным условием попадания в тупик. DPOS устойчив благодаря своей способности продолжать работать на пониженном уровне мощности / доверия, даже когда большинство генералов выведены из строя.

Компромиссы

Каждый алгоритм идет на некоторые компромиссы. Cosmos дает 100% гарантию отсутствия форков и способен производить блоки в распределенной сети каждые 5-10 секунд. Чтобы достичь этого с тем же количеством генералов, какое имеет Steem (21), они потребляют пропускную способность сети, сравнимую со стабильными 5 транзакциями в секунду.

С другой стороны, в Steem крайне редко случаются пропущенные блоки и еще реже - брошенные блоки. Если взглянуть на статистику, блок, произведенный при участии 100% генералов (производителей) имеет шанс в 99.9999% стать конечным блоком. После двух блоков (6 секунд) возможность быть брошенным снижается еще больше. Всякий, кто полагается на алгоритм последнего необратимого блока (40 секунд), защищен от практически любого мыслимого сценария, и в худшем случае (чисто теоретически) застрянет в состоянии ожидания на форке меньшинства вплоть до ручного вмешательства. Это значит, что он ошибается “безопасно”, попадая в состояние, где Вы не будете принимать поддельные транзакции.

Существует еще один дополнительный уровень подтверждения, который может быть применен в DPOS: запрашивание 100% участия и 21 блока. С 63 секундами подтверждения и 100% участия Вы можете быть уверены, что никогда не “застрянете” и что каждая транзакция, которую Вы получите, будет истинно необратима и всеобще принята.

С этими цифрами Вы должны обратить внимание на то, что дополнительное время обеспечивает страхование от оставшихся 0.00001% византийских случаев. Это такой уровень уверенности, для достижения которого требуется много больше 6 уровней Биткойна, особенно, если атакующий обладает 33% хэш-мощности.

Заключение

Исходя из закона убывающей доходности (экономической предельной полезности), ценность увеличения уверенности с 99.9999% до 100% неизмерима для подавляющего большинства реальных мировых транзакций. Люди теряют на комиссиях за транзакции гораздо больше, чем они потеряли бы в случае, если одна из миллиона транзакции случайным образом была бы отменена.
В то же время, стоимость достижения этого последнего 0.0001% уверенности значительна из-за накладных расходов сети и замедления времени блоков, что в целом может стать полным провалом, если более ⅓ нод выйдут из строя.

Оба алгоритма имеют право на существование, но я очень доволен компромиссами, разработанными для DPOS, в сравнении с другими имеющимися алгоритмами