ОБЗОР АЛГОРИТМОВ КОНСЕНСУСА BLOCKCHAIN

ОБЗОР АЛГОРИТМОВ КОНСЕНСУСА BLOCKCHAIN

Бузид Филипп Хамданович

магистрант, Международный Университет Информационных Технологий,

Казахстан, г. Алматы

АННОТАЦИЯ

В данной статье рассматриваются алгоритмы консенсуса в blockchain системах, а именно рассматриваются основные преимущества таких алгоритмов как Proof-of-Work, PBFT, Proof-of-Stake, Proof-of-Authority. Главной задачей является определение области применения данных алгоритмов и их особенностей.

Введение

Blockchain является децентрализованной структурой данных, с возможностью хранения в согласованном виде между всеми участниками сети. В децентрализованных системах фундаментальной проблемой является достижение согласованности данных. Так как каждый участник сети может принять данные или отказать, так же участник может быть не доступен в момент отправки данных. Данная проблема охарактеризована как проблема Византийских генералов впервые описана в 1978 году. Суть задачи описывается сложность доверия сообщением с участием большого количества участников. Исходя из задачи появился вид отказоустойчивости, который называется византийской отказоустойчивости. Сложность данного вида отказоустойчивости является абсолютная непредсказуемость поведения участника и достоверности отправленных сообщений, а также их правильности оформления.

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

• Участник (Узел) – клиентское приложение обеспечивающий доступ к сети, и участвующее в консенсусе данных, узлу участвующие в консенсусе называются майнерами их задача в выполнении алгоритма консенсуса.
• Транзакции – данная сущность представляет сообщение с помощью, которого изменяют состояние конечного автомата.
• Блок – хранение транзакции и создание цепи связанных блоков.
• Протокол консенсуса – протокол подтверждение валидности транзакции и блока, а также принятие решения о включении в сеть.

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

Византийская отказоустойчивость свойство достижения консенсуса между всеми участниками децентрализованных и асинхронных систем, в особенности систем, основанных на пиринговых сетях, даже если некоторые участники не отвечают либо отвечают не корректными данными, сокращенно называется BFT (Byzantine Fault Tolerance). В точности данное свойство описывает состояние компьютерной системы, работающей в распределенной сети, поддерживающее работающее состояние при условии, что компоненты могут выходить из строя, и не имеется информации об этом инциденте. Так же помимо выхода из строя система должна работать в случае предоставления компонентами ложной информации. Данное свойство происходит от задачи Византийских генералов которая была впервые представлена и описана в статье Лесли Лэмпорта, и других в 1982 году [1]. Описание задачи приведено ниже:

“Представьте, что несколько дивизий византийской армии стоят лагерем за пределами вражеского города, каждой дивизией командует свой собственный генерал. Генералы могут общаться друг с другом только через посыльных. Понаблюдав за врагом, они должны принять решение об общем плане действий. Однако некоторые из генералов могут быть предателями, пытающимися помешать лояльным генералам достичь соглашения. Генералы должны решить, когда атаковать город, но им нужно значительное большинство их армии, чтобы атаковать одновременно. Генералы должны иметь алгоритм, гарантирующий, что (а) все лояльные генералы примут один и тот же план действий и (б) небольшое количество предателей не может заставить лояльных генералов принять плохой план. Все лояльные генералы будут делать то, что им предписывает алгоритм, но предатели могут делать все, что пожелают. Алгоритм должен гарантировать условие (а) независимо от того, что делают предатели. Лояльные генералы должны не только прийти к соглашению, но и согласовать разумный план.”

Следовательно, в случае согласование переданных сообщений в сеть среди всех узлов, то принято считать, что Византийская отказоустойчивость достигнута. При этом при Византийской отказоустойчивости в случае неопределённых ситуаций, сообщением присваивается статус по умолчание, к примеру:

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

Лесли Лэмпорт в своей работе [1] доказал, что если имеется 3m + 1 правильно функционирующих узлов, соглашение о идентичности состояния может быть достигнуто.

Алгоритм консенсуса «Proof of Work»

В первые концепт алгоритма был предложен Синтией Дворк в соавторстве с Мони Наор в научной работе «Pricing via Processing or combatting junk email» [11] в 1993 году как организация доступа к общем ресурсам. В данной работе предложен концепт, в котором пользователь при запросе доступа вынужден решить некоторую криптографическую функции либо любую другую математическую функцию, но достаточно сложную и требующую ресурсов при этом за допустимое время и легко решаемая на стороне сервера. Данная концепция была так же предложена Адамом Беком как средство борьбы со спамом [2]. Вскоре Сатоши Накомото представил Bitcoin [10] в котором применил данный концепт для создания алгоритма консенсуса в децентрализованной системе, данная концепция является ключевой в добавлении блока в общую сеть. Сами по себе алгоритмы консенсуса не решают византийскую задачу, они являются частью протокола консенсуса, которую в свою очередь решает проблему синхронизации данных в асинхронных децентрализованных системах.

Следующая диаграмма представляют алгоритм доказательства работы Рисунок 1.

Рисунок 1. Блок схема алгоритма Proof of Work

Каждый алгоритм консенсуса преследует цель привести все узлы к согласию, то есть доверять друг другу, в среде, где все узлы не имеют информации о других узлах.

Перед добавление нового блока каждая транзакция проходит проверку, после данный блок добавляется в цепочку Blockchain. Стоит обратить внимания, блок будет добавлен к цепи блоков с наибольшим количеством блоков. Узлы, которые принимают на себя обязанность в согласовании блоков и проверки транзакции называются Майнеры. Майнеры при согласовании блоков выполняют сложную математическую вычислительную задачу для добавления блока в сеть данный процесс называется Майнингом. Согласно вышеизложенному данный алгоритм консенсуса Proof-of-Work предполагает решение сложной вычислительной задачи для создания новых блоков в Blockchain, при этом в сети Биткоин данная задача меняется в зависимости от времени ее выполнения и количества участников. Стимул для майнинга заключается в экономических выгодах, когда конкурирующие майнеры получают вознаграждение в криптовалюте и небольшую комиссию за транзакцию.

Обработка транзакции из пула и создания блока, а также сортировка транзакции в хронологическом порядки, не энергозатратная операция. Так же, как и добавления блока в цепь блоков не является энергозатраным. Энергозатратная часть является решение "сложной математической задачи", в особенности в конкурентом режиме, так как имеется срок решения и майнеры используют высоко энергозатратное оборудование, для того чтоб добавить блок первым. Вознаграждение майнеров, происходит только в том случае если блок добавлен, при этом сумма вознаграждения меняется при достижении 2100 добавленных блоков. Следовательно сумма вознаграждаемой криптовалюты уменьшается при достижении указанного выше количества блоков или времени в зависимости от реализации. Так же в зависимости от реализации сложность задачи и время на ее выполнение может варьироваться от таких переменных как количество майнеров и скорость нахождения решения задачи. Данная сложность контролируется с помощью числа nonce и искомого значения (Target Value), увеличивая данные переменные увеличивается сложность вычисления. Для того, чтобы последовательно находить 1 блок и успеть синхронизировать между большинством Майнеров, введен определенный лимит на нахождение одного блока, а именно 10 минут.

Изменение блока невозможно так-как данная задача, в связи с тем, что будет необходимо сгенерировать и вычислить сложные математические задачи всех блоков и транзакции которые они содержат. Это защищает Blockchain от несанкционированного изменения.

Алгоритм консенсуса «PBFT»

Practical Byzantine Fault Tolerance (PBFT) согласно названия алгоритм практическое решение византийской отказоустойчивости, в первые представлен в 99 году Барбарой Лисков и Мигелем Кастро [5]. Данный алгоритм спроектирован для эффективной работы в асинхронных системах, и оптимизирован для снижения накладных расходов. Согласно изложенному выше основная цель данного алгоритма консенсуса является решение задачи Византийской отказоустойчивости. Данный алгоритм имеет ряд следующих преимуществ:

• Энергоэффективность – PBFT не предусматривает сложной математической задачи для вычисления, к примеру как в PoW. Часто PBFT часто используется в паре с другими алгоритмами, к примеру Ziliqa [6] использует в паре с PoW подобным математическим сложным вычислением, выполняется для каждого 100-го блока как создание якорного блока.
• Завершенность транзакции (Окончательность) – Транзакции в PBFT не требуют многократных подтверждений после их завершения и согласования в отличие от других алгоритмов.
• Низкое вознаграждение узлов – так как каждый узел принимает участие в согласовании транзакций возможно стимулирование с помощью небольшого вознаграждения узлов.

Алгоритм PBFT обеспечивает консенсус с помощью репликации состояний и данных в стиле Византийском отказоустойчивости, то есть с помощью рассылки этих данных всем узлам. Таким образом алгоритм работает в сетях, в которых возможно и ожидаемы отказы в работе. Узлы пиринговой сети, работающие с алгоритмом PBFT, имеют упорядоченный порядок в связи с тем, что у каждого узла имеется роль в сети, к примеру ведущий узел (или Мастер узел). При этом в случае отказа ведущего узла следующий резервный узел (или Дочерний узел) может стать ведущим узлом.

Согласно вышеизложенному данный алгоритм реализован согласно правилам Византийской отказоустойчивости и доказательств Лесли Лэмпорта, а именно алгоритм работает на основе правил что две трети сети работают правильно (Правило большинства). Что позволяет создать византийскую отказоустойчивою систему, которая может функционировать в условиях отказов некоторых узлов не более одной трети, и при условии, что работающее узлы количество которых равняется двум трети всех узлов в системе. Достижение максимальной безопасности и отказоустойчивости возможно при увеличении количества узлов, но увеличение узлов увеличивает объем данных по сети, так как увеличивается обмен сообщениями между узлами. PBFT реализует по этапный процесс согласование, а именно:

• Ведущий узел принимает запрос на обработку.
• Ведущий узел передает запрос на согласование всем резервным узлам.
• Все узлы принимают запрос на выполнение, по завершению отправляется результат клиенту.
• Успешным ответом принято считать если ответили m+1 (где m – максимальное допустимое количество неисправных узлов) узлов с одинаковым ответом.

Смена ролей узлов происходит во время каждого раунда согласования, так же смена роли узла с Ведущего на Резервный в случае, если Ведущий узел не ответил на установленное время. Допускается так же согласование среди Резервных узлов за предоставление роли Ведущий узел другому узлу. Весь процесс описанный выше представлен в виде диаграммы Рисунок 2.

Рисунок 2. Схема взаимодействия между пирами

Как и было раннее указанно что увеличение узлов приводит к росту безопасности и отказоустойчивости Алгоритма PBFT, но следует понимать, что данный алгоритм для построение приватных сетей, что означает увеличение в пределах оговоренных групп лиц. Обратным эффектом увеличения количества узлов приводит к неэффективности данного алгоритма. В особенности если применять данный алгоритм в публичных сетях. Понижение эффективности обусловлено высокими накладными расходами на связь, и необходимости ожидания большого количества ответов от Резервных узлов. Рост расходов на связь растет экспоненциально с каждым дополнительным узлом в сети.

Алгоритм консенсуса «Proof-of-Stake»

Алгоритм был разработан и предложен Виталием Бутерином в 2017 году [7] как альтернатива достижения консенсуса в децентрализованных системах алгоритму Proof of work. Proof-of-Stake алгоритм консенсуса, который основан на принципе создания блоков так называемыми валидаторами, а именно участники сети предоставившие более 32 ETH как долю для сертификации блоков, вместо решения криптографической задачи. Каждый валидатор выбирается алгоритмом в случайном порядке, для мотивации участников в сети в реализации алгоритма в Ethereum 2.0 предусмотрены штрафы за отсутствие в сети и не выполнение обязательств по созданию блоков, и за каждый созданный блок происходит вознаграждение, а также за дополнительную валидацию уже созданных блоков. Основное отличие от Proof of Work, нет необходимости наращивать вычислительную мощность, меньший интервал создания блоков 15 секунд в среднем, в отличии от 10 минут в PoW. После создания блока производится согласование блока не менее 128 валидаторами и после этого блок попадает в основную цепочку блоков со статус «Committee» Рисунок 3.

Рисунок 3. Блок схема Proof-of-Stake

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

1. Все отправленные транзакции помещаются в пул транзакции.
2. Участники, которые претендуют на роль валидатора для следующего блока, повышают ставку в депозите. Данная ставка комбинируется со следующими значениями, а именно возраст ставки, чтобы выбрать валидатора, при этом в некоторых реализациях используется рандомизированная функция выбора блока.
3. Выбранный валидатор проверяет транзакции из пула, создает блок и публикует его. Ставка при этом остается заблокированной, вознаграждение на данном этапе не выдано, в связи с синхронизацией со всем участниками и соответственно согласуют только что добавленный блок.
4. В случае одобрения блока в цепи, блокировка ставки снимается валидатор получает обратно ставку и вознаграждение. Имплементации алгоритма, использующая механизм, основанный на возрасте ставки, для выбора валидаторов, сбрасывается на 0 для текущего блока и валидатора. Валидатор получает низкоприоритетное положение на следующих выборах валидатора.
5. В случае неодобрении нового блока другими участниками, назначается штраф валидатору создавшему данный блок. Блок помечается статусом «Плохой». Возврат к шагу 1, для создания и валидации нового блока.

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

Консенсус «Proof-of-Authority»

В отличии от предыдущих двух алгоритмов консенсуса доказательство работы (Proof of Work) и доказательство владения (Proof-of-Stake) предназначенных для публичных Blockchain сетей, в которых согласно вышеизложенному нет регистрации и учета пользователей, данный алгоритм предназначен для приватных сетей, в которых имеется регистрация пользователей. Транзакции обрабатываются и создание блоков возлагается на валидаторы сети, при этом выбора валидатора происходит последовательным. Согласно отображенной схеме, (Рисунок 4), участники, прошедшие регистрацию и принявшие на себя роль валидаторов, добавляются в список валидаторов. Каждый раунд из данного списка выбирается последовательно валидатор для создания следующего блока.

Рисунок 4. Блок схема Proof-of-Authority

Согласно вышеизложенному скорость алгоритма зависит от количества валидаторов чем их выше, тем выше скорость создания блоков. Так же в Имплементации Hyperledger Besu, имеется возможность установки максимального размера блоков, а именно максимально возможный 2147 МБ. Блок с максимальным размером скорее для локальных приватных решений, но так как имеется возможность увеличивать размер блок с 21 КБ до 2147 МБ, значительное преимущество. При этом имеются ряд ограничений:

• Минимум валидаторов – для работы сети необходимо как минимум 4 валидатора.
• Лимит транзакций – пул транзакции по умолчанию установлен в 1000 необработанных транзакции.

Подтверждение полномочий (PoA) — это модифицированная форма подтверждения ставки (PoS), где вместо ставки с денежной стоимостью роль ставки выполняет удостоверение личности валидатора. В этом контексте идентификация означает соответствие между личной идентификацией валидатора на платформе и официально выданной документацией на одно и то же лицо, т. е. уверенность в том, что валидатор является именно тем, за кого себя выдает это лицо. Так же, как и в PoS, в консенсусе PoA идентичность как форма участия также редка. Но, в отличие от PoS, у каждого человека есть только одна личность.

Установление личности означает добровольное раскрытие того, кто вы есть, в обмен на право проверки блоков. Это означает, что выгоды, которые вы извлекаете из этого, являются общедоступными, как и не законные действия, которые пользователь может предпринять. Идентичность, поставленная на карту, может послужить отличным уравнителем, который одинаково понимают и ценят все действующие лица.  Лица, чья личность (и, следовательно, репутация) поставлены на карту для обеспечения безопасности сети, получают стимул для сохранения сети. Чтобы концепция работала в реальных условиях, необходимо выполнить несколько условий:

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

Выполнить эти условия на самом деле не так уж и сложно.  К примеру, одна из реализации алгоритма Proof-of-Authority POA Network [9], разработан новый подход для валидаторов базовой сети, требуя от них получения действующей лицензии государственного нотариуса. Чтобы подтвердить подлинность своей личности, нотариусы, у которых уже есть информация о своей личности, находящаяся в свободном доступе в общественном достоянии, проходят официальную проверку личности по цепочке через POA Network DApps. Поскольку общедоступные базы данных лицензированных нотариусов и DApps для проверки сети POA независимы друг от друга, подделка информации с обеих сторон помешает кандидату стать валидатором.

Список литературы:

1. Lamport L., Fischer M. Byzantine generals and transaction commit protocols. – 1982.
2. Back A. et al. Hashcash-a denial of service counter-measure. – 2002.
3. Nakamoto S., Bitcoin A. A peer-to-peer electronic cash system //Bitcoin.–URL: https://bitcoin. org/bitcoin. pdf. – 2008. – Т. 4.
4. Dwork C., Naor M. Pricing via processing or combatting junk mail //Annual international cryptology conference. – Springer, Berlin, Heidelberg, 1992. – С. 139-147.
5. Castro M. et al. Practical byzantine fault tolerance //OsDI. – 1999. – Т. 99. – №. 1999. – С. 173-186.
6. Secure A. The Zilliqa Project: A Secure, Scalable Blockchain Platform. – 2018.
7. Buterin V., Griffith V. Casper the friendly finality gadget //arXiv preprint arXiv:1710.09437. – 2017.
8. Wood G. Polkadot: Vision for a heterogeneous multi-chain framework //White Paper. – 2016. – Т. 21. – С. 2327-4662.
9. Shamili P., Muruganantham B. Design and Implementation Considerations of POA Network Architecture in the Ethereum Blockchain //Webology. – 2022. – Т. 19. – №. 1.