Создатель Node.js Ryan Dahl впервые в Украине на конференции JS Fest. Программа уже на сайте
×Закрыть

Еще 13 консенсус-протоколов для распределенных систем. Часть 2

Продолжаю описание консенсус-протоколов от Intellectsoft Blockchain Lab. Ранее я рассматривал 12 популярных протоколов консенсуса. Во второй части расскажу о самых экзотических алгоритмах, используемых в технологиях распределенного реестра (DLT) — от BFT-характеристики до Leased Proof-of-Stake, Proof-of-Stake-Time и Proof-of-Asset.

1. Byzantine Fault Tolerance (BFT) протоколы. Продолжение
1.1. Протокол SIEVE
1.2. Протокол Round Robin
1.3. Протоколы Paxos и Raft
1.4. HoneyBadger Byzantine Fault Tolerance (hbBFT)
1.5. Loopchain Fault Tolerance (LFT) (Устойчивость к проблеме платформы Loopchain)
1.6. Cross-Fault Tolerance (XFT) (Устойчивость к проблеме системных сбоев)

2. Консенсус-протоколы для других задач
2.1. Proof-of-Asset (PoA) (Доказательство актива)
2.2. Proof-of-Authority (PoA) (Доказательство полномочий)
2.3. Proof-of-Brain (PoB) (Доказательство «мозговой деятельности»)
2.4. Proof-of-Capacity (PoC) (Доказательство ресурсов)
2.5. Proof-of-Contribution (PoCo) (Доказательство вклада)
2.6. Proof-of-Stake-Time (PoST) (Доказательство доли времени)
2.7. Leased-Proof-of-Stake (LPoS) (Арендованное доказательство доли)

1. Byzantine Fault Tolerance (BFT) протоколы. Продолжение

В этом разделе рассмотрим несколько технических характеристик протоколов, «устойчивых к византийской проблеме» (BFT). Их особенность в том, что даже когда нода (один из валидаторов) не может выполнить действие, остальные ноды продолжают работать, поддерживая систему. Незначительные различия в технических характеристиках протокола помогают распределенным системам адаптироваться к конкретным условиям и быть более надежными.

Протоколы BFT обеспечивают безопасность, подразумевая, что ничего плохого никогда не произойдет, а также жизнеспособность — ведь в конечном итоге произойдет что-то хорошее. Ранее только частные сети могли иметь свойства BFT. Когда были представлены Bitcoin и Proof-of-Work, это стало возможным и в публичной среде.

1.1. Протокол SIEVE

Принцип: выполнение операций, сравнение исходящих данных в копиях и поиск любых расхождений.

Производительность: высокая.

Среда DLT: приватный блокчейн c разрешениями.

Завершенность: немедленная.

Пример использования: Hyperledger.
Поскольку Hyperledger является модульной структурой, у вас есть возможность добавить варианты консенсуса, и SIEVE один из них. Стандартным вариантом является протокол PBFT или Practical Byzantine Fault Tolerance, который мы рассмотрели в предыдущей статье. SIEVE и XFT все еще находятся в бета-версии, но ниже описан функционал, детали которого уже известны.

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

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

  • Если протокол обнаруживает незначительные несоответствия среди небольшого числа этих копий, значения с несоответствиями просеиваются (буквальное значение английского «sieve»).
  • Если несоответствие происходит между несколькими процессами, то просеивается сама операция-нарушитель.

1.2. Протокол Round Robin

Принцип: несколько нод играют ключевую роль в подтверждении и голосовании за транзакции. Процесс валидации блока не зависит от одного участника.

Производительность: высокая.

Среда DLT: приватный блокчейн c разрешениями.

Завершенность: немедленная.

Пример использования: Multichain, Tendermint.

Механизм протокола Round Robin лучше всего подходит для бизнеса в сфере финансовой торговли и цепочки поставок. Этот алгоритм предполагает, что валидаторы достигают консенсуса, голосуя за блоки. Голосование проходит в три этапа:

  • предварительный (pre-vote);
  • предварительно фиксированный (pre-commit);
  • фиксированный (commit).

Получение более 2/3 фиксированных голосов означает получение фиксированных голосов от большинства валидаторов. Блок считается фиксированным, когда 2/3 валидаторов отдали за него фиксированные голоса.

1.3. Протоколы Paxos и Raft

Существуют протоколы особо устойчивые к сбоям системы (crash-fault tolerant или CFT), известные как Paxos и Raft. Оба являются более быстрыми версиями BFT и действуют по принципу репликации операции (state machine replication), которым пользуется Microsoft.

1.4. HoneyBadger Byzantine Fault Tolerance (hbBFT)

Принцип: деление на эпохи, подразумевающее добавление каждой новой партии транзакций к зафиксированному (и распределенному) логу в конце каждой эпохи.

Производительность: высокая.

Среда DLT: блокчейн с разрешениями и не требующий разрешений.

Завершенность: немедленная.

Пример использования: n/a.

HoneyBadger Byzantine Fault Tolerance (hbBFT) — это первый BFT протокол атомарного вещания, обеспечивающий оптимальную асимптотическую эффективность в асинхронных условиях. Говоря простым языком, HoneyBadgerBFT устойчив к сбоям в глобальных сетях, чем превосходит другие алгоритмы BFT. Ноды HoneyBadger могут оставаться скрытыми за анонимными реле, на подобии браузера Tor. Транзакции происходят в разное время и протокол работает с любой скоростью, которую поддерживает сеть.

1.5. Loopchain Fault Tolerance (LFT) (Устойчивость к проблеме платформы Loopchain)

Принцип: сокращает модель работы Round Robin до двух шагов и разрешает ограниченное количество нод.

Производительность: высокая.

Среда DLT: приватный блокчейн с разрешениями.

Завершенность: немедленная.

Пример использования: ICON.

Протокол Loopchain Fault Tolerance (LFT) является продолжением Tendermint (который объединяет DPoS и PBFT, мы описали их в первой статье) и усовершенствованной версией BFT, что позволило ему стать безопасным, высокопроизводительным и масштабируемым консенсус-алгоритмом.

LFT напоминает алгоритм Round Robin своей трехэтапной системой голосования (предварительный, предварительно фиксированный, фиксированный), но сокращенный до 2 шагов. В голосовании участвует ограниченное количество нод. LFT использует технику «Spinning» (Вращение), чтобы упростить запутанный алгоритм выбора первичной ноды.

1.6. Cross-Fault Tolerance (XFT) (Устойчивость к проблеме системных сбоев)

Принцип: усовершенствованный BFT протокол. Объединяет синхронные и асинхронные протоколы для связи.

Производительность: очень высокая.

Среда DLT: приватный блокчейн с разрешениями.

Завершенность: немедленная.

Пример использования: Hyperledger.

Наконец мы подошли вплотную к протоколу, который использует комбинацию асинхронных и синхронных методов для сетевых коммуникаций. Cross-Fault Tolerance (XFT) сочетает в себе скорость протокола Crash-Fault Tolerance (CFT) и надежность BFT характеристики. Согласно авторам технологии, «XFT разумно срезает углы и игнорирует возможные атаки, которые сегодня считаются либо дорогостоящими, либо крайне маловероятными».

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

Исследования алгоритмов консенсуса от KPMG

2. Консенсус-протоколы для других задач

Не все предприятия должны быть частными. Некоторые компании предполагают использование децентрализованных публичных алгоритмов. Самые популярные из них мы рассмотрели в Части 1, но упомянули не все.

2.1. Proof-of-Asset (PoA) (Доказательство актива)

Принцип: токенизация активов, часто физических товаров.

Производительность: высокая.

Среда DLT: публичный / приватный блокчейн.

Завершенность: немедленная.

Пример использования: Digix, BANKEX.

Вы уже знаете, что, по своей сути, блокчейн является неизменным регистром. Поскольку его природа не допускает ошибок учета, он может объединять физический актив или сертификат с технологией блокчейна при соотношении 1:1. Этот подход известен как протокол Proof-of-Asset (PoA).

Что еще можно токенизировать с помощью алгоритма PoA, помимо золота? Например:

  • право собственности на землю;
  • права владения;
  • акции, облигации, долговые кредиты и другие производные финансовые инструменты.

В этом отношении протокол Proof-of-Asset прост, гибок и надежен. Требуется лишь небольшая адаптация и / или добавление действующих лиц в протокол, и система будет готова для работы с другими типами активов.

2.2. Proof-of-Authority (PoA) (Доказательство полномочий)

Принцип: право валидации транзакций имеют только известные участники (BFT).

Производительность: высокая.

Среда DLT: публичный / приватный блокчейн.

Завершенность: вероятностная.

Пример использования: POA network, Parity.

Алгоритм Proof-of-Authority (PoA) используется как в приватных, так и в публичных блокчейн-проектах. Он обеспечивает сравнительно быстрые транзакции через механизм консенсуса, основанный на идентичности (полномочия участников).

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

2.3. Proof-of-Brain (PoB) (Доказательство «мозговой деятельности»)

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

Производительность: средняя.

Среда DLT: публичный/ приватный блокчейн.

Завершенность: вероятностная.

Пример использования: Basic Attention Token, Steem.

Что, если ваш бизнес — это СМИ или социальная сеть? Что, если вы связываете создателей контента с рекламодателями, но никто из них не доверяет текущей системе? На сегодняшний день экономика совместного потребления и экономика добавленной стоимости требуют новых моделей для решения этих проблем.

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

2.4. Proof-of-Capacity (PoC) (Доказательство ресурсов)

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

Производительность: высокая.

Среда DLT: публичный блокчейн.

Завершенность: вероятностная.

Примеры использования: Burst.

Proof-of-Space (Доказательство свободного места), Proof-of-Storage (Доказательство места для хранения) или Proof-of-Capacity (Доказательство ресурсов). Называйте как угодно. Предложенный еще в 2014 году, этот алгоритм является одновременно энергоэффективным и позиционируется как равномерно распределенный.

Концепция «мегабайты как ресурсы» предполагает использование значительного объема памяти, чтобы заполнить его данными. Чем больше памяти выделит участник, тем выше его шансы сгенерировать блок. Storj работает по аналогичному протоколу с названием Proof-of-Retrievability (Доказательство извлекаемости), но с небольшими изменениями.

2.5. Proof-of-Contribution (PoCo) (Доказательство вклада)

Принцип: механизм консенсуса вне блокчейна, основанный на вычислительной мощности.

Производительность: низкая.

Среда DLT: публичный блокчейн.

Завершенность: немедленная.

Пример использования: iExec, CyberVein.

Proof-of-Contribution основан на мощности компьютера в сети и подобен протоколу Proof-of-Research (Доказательство проведенного исследования), который вознаграждает добровольцев за то, что они тратят свою компьютерную мощность на большие научные вычисления. Например, на исследование данных астрономических наблюдений SETI@Home на платформе BOINC.

Примером протокола PoCo является iExec — это децентрализованный проект облачных вычислений на основе блокчейна. Он использует идею грид-вычислений (Desktop Grid), также называемую «вычислениями на волонтерской основе» (Volunteer Computing). Эта форма распределенных вычислений означает сбор компьютерных ресурсов через интернет, которые мало используются, для их объединения в «виртуальный суперкомпьютер». Таким образом можно параллельно запускать очень большие приложения за долю от стоимости традиционного суперкомпьютера.

2.6. Proof-of-Stake-Time (PoST) (Доказательство доли времени)

Принцип: Улучшение протокола PoS, при котором предпочтение отдается более старым нодам.

Производительность: высокая.

Среда DLT: публичный блокчейн.

Завершенность: вероятностная.

Пример использования: Peercoin, VeriCoin.

В протоколе Proof-of-Stake-Time (PoST) размер хэша меньше, чем кратное количество монет, доля времени и цель. Таким образом, участники с меньшим количеством токенов по-прежнему имеют возможность участвовать в майнинге (майнинг в проектах на основе протокола Proof-of-Stake). Это несколько похоже на протокол Proof-of-Importance (PoI) (Доказательство важности), используемый проектом NEM, который мы рассмотрели в первой статье, но с небольшими отличиями. Например, когда мощность сети ниже, время простоя увеличивается.

2.7. Leased-Proof-of-Stake (LPoS) (Арендованное доказательство доли)

Принцип: дать возможность всем участвовать в майнинге через протокол PoS.

Производительность: высокая.

Среда DLT: публичный/приватный блокчейн.

Завершенность: вероятностная.

Пример использования: WAVES.

Leased Proof-of-Stake — это гибридная форма алгоритма PoS. По сути, мелкие участники, которые не имеют достаточной доли и, следовательно, не могут майнить новые монеты, получают возможность сдавать свои крипто-активы полным нодам. Так первые получают возможность участвовать в майнинге и извлекают прибыль, а вторые — более высокую вероятность создания следующего блока, и вся сеть становится более децентрализованной.
Это напоминает майнинг пулы, которые чаще всего обслуживают сеть Биткоин. Более того, система LPoS позволяет участникам в любое время делать с монетами все, что угодно: потратить их или обменять на альткоины. В этом случае «арендный» договор автоматически аннулируется, и владелец арендованных монет больше не может рассчитывать на долю.

Заключение

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

LinkedIn

14 комментариев

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

У меня вопрос про протокол Round Robin.
В тексте сказано:

Блок считается фиксированным, когда 2/3 валидаторов отдали за него фиксированные голоса.

Как это выглядит на практике? У всех в трее висит клиент. Выскакивает сообщение «А давайте подтвердим Васе и Пете их сделку? ;) », и я такой на кнопку тыц и типа подтвердил? :)

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

Если конкретно про Tendermint, то там да, все ноды поддерживают связь друг с другом и можно, для примера, закодировать свои проверки. Ноды сами голосуют «ЗА» блок, если все ок. В дефолте сами транзакции не проверяются, для системы это просто массив байт. Проверки самые базовые — размер транзакции и их количество. слоем приложения в tendermint есть так называемый ABCI клиент, на котором дергают RPC-методы (на транзакцию каждую вызов, потом начало, конец блока и коммит). Поведение обработчиков должно быть детерминированным. Любые проверки уровня логики — програмируются самостоятельно. И там можно реализовать, например, отбрасывание транзакций как невалидных, если к примеру, траназкция перевода средств и т.п.

Т.е., если я правильно понял, на стороне клиента я должен подготовить скрипт по верификации блока и тогда я смогу стать участником сети?

Архитектурно Tendermint чуток сложнее (и проще одновременно). Вы можете добавить свою логику, если ее нет, движок будет производить блоки «по своему» )

На практике такие системы все имеют свою правду, и основная особенность — что все, на что конкретный участник опирается — это его ledger (все что он знает о истории и участниках) и его алгоритмы проверок. Если вы хотите быть участником сети — значит о вас должны знать те, кто там уже находятся. После того как о вас узнали (добавили в свои леджеры как доверенного участника) — вы можете учавствовать в голосованиях за валидность транзакций.
Сам процесс валидации может быть очень разным, но важно только примет ли сеть транзакции под которыми вы ставите подпись или которые инициируете. Для того чтобы максимизировать успех таких процессов их стандартизируют в вот такие протоколы. И проверки обычно проходят автоматически, у вас в трее висит ваш клиент и слушает сеть.
При удачной валидации — на вашей стороне (ваш клиент верит сообщению опираясь на свой leger) — клиент поставить свою подпись под сообщением и оповестит всех остальных участников которые принимают решения. Если сообщение поддержит большенство участников — значит ему можно доверять на уровне сети. Ваш клиент, доверяя большинству, вносит изменения в состояние своего ledger-а (например изменяет владельца актива на того кто указан в сообщении). После этого ваш ledger и ваша правда состоят в том что активом владеет другой человек, и ваш клиент будет учитывать это в следующих сообщениях/валидайиях связанных с данным активом.

Спасибо, отличный материал!

А напомните, в первой было про семейство Ouroboros? Там также много вариантов, кстати, над ними ведут работу и наши, один из участников из Харькова

Спасибо, вот ссылка на первую статью. dou.ua/...​es/12-konsensus-protocols
Там сделан упор на более известные семейства PoW, PoS, BFT и еще немного DAG.

Я б уточнил — BFT предполагает работу не просто когда часть участников «не может» — но и когда они откровенно творят свою неположенную фигню и врут о своих действиях.

> At the beginning of the project, it was not clear how many computers in total are needed to guarantee that a conspiracy of n faulty computers could not «thwart» the efforts of the correctly-operating ones to reach consensus.

Ну и так далее.
Если это требование смягчать, то соответственно уменьшаются и требования по запасу, но это уже не byzantine :)

Совершенно верно, такие протоколы опираются на мнение абсолютного большенства, и игнорируют ошибочные или ложные сообщения меньшенства.

Шикарная статья и оч.полезная инфа.

Спасибо, это вторая в серии. Вот — dou.ua/...​s/12-konsensus-protocols ссылка на первую

Когда Биткоин будет расти?

О цене судить не стану, но технологически уверен что да. Он пока самый простой и понятный большому бизнесу, ну и самый знаменитый. В 2019 я жду развитее протоколов 2го уровня в принципе и увеличение использования lightning network в частности.

Подписаться на комментарии