Kонсенсус в Exonum: как он работает

Exonum ^[1]TM — это наш открытый фреймворк для создания приватных блокчейнов. Сегодня мы расскажем, как работает его алгоритм консенсуса.

^[2]
Изображение: Bitfury ^[3]

Зачем нужны алгоритмы консенсуса

Прежде чем перейти к рассказу о том, как устроен алгоритм консенсуса Exonum^TM, поговорим о том, зачем вообще нужны эти алгоритмы в блокчейнах.

Блокчейн представляет собой распределенную систему без центрального администратора. Для согласования порядка блоков (и, соответственно, транзакций) участники сети используют ^[4] специальные алгоритмы консенсуса. Задача консенсуса — помочь узлам одноранговой сети прийти к единому мнению по поводу того, каким должно быть ее новое состояние — то есть выбрать следующий блок в цепочке блокчейна.

Это нужно для того, чтобы защитить блокчейн и информацию, хранящуюся в нем, от подмены. К примеру, в блокчейн на базе Exonum^TM, реализованном для РЖД, записывается информация об операциях с деталями для вагонов и поездов. Зная, что консенсус обеспечивает достоверность данных в блоке, компания может следить за маршрутом запчастей от поставщика и своевременно обнаруживать подделки. Подробнее об этом и других кейсах мы расскажем дальше.

Какие задачи мы решали, создавая алгоритм консенсуса Exonum

Говоря о консенсусе, одним из первых на ум приходит биткоин-блокчейн с его алгоритмом proof-of-work ^[5] (PoW). Он требует от участников (майнеров) проведения сложных математических операций для подбора хеша блока и расходования ресурсов вычислительных систем. Таким образом, участники биткоин-сети поддерживают её работу путем вложения собственных материальных ресурсов. В подобных условиях недобросовестная активность в сети становится невыгодной и дорогостоящей.

Но несмотря на то что биткоин считается самой надежной из существующих распределенных систем, его консенсус не может решить проблему византийского поведения узлов ^[6]. Под византийским поведением мы понимаем зловредную деятельность, способную нарушить работу алгоритма консенсуса. К такой деятельности также можно отнести ситуации, когда узлы теряют связь с сетью или уходят в офлайн.

Еще в середине 80-х годов было доказано ^[7], что для обеспечения устойчивости распределенной системы она должна работать в условиях частичной синхронности. При этом алгоритм консенсуса обязан обладать следующими критериями:

• Liveness — должна быть возможность принять новый блок в любой момент времени.
• Consistency — база данных транзакций на всех узлах сети должна быть идентичной.
• Censorship resistance — узлы не должны отдавать предпочтение каким-либо транзакциям или игнорировать их.

Для распределенной сети с известным количеством участников наиболее оптимальной моделью консенсуса является BFT (byzantine fault tolerance ^[8]). Она удовлетворяет требованиям частичной синхронности узлов и способна поддерживать стабильную работу сети даже в том случае, если треть её участников будет скомпрометирована. По этим причина именно модель BFT легла в основу алгоритма консенсуса ^[9] Exonum^TM.

Как работает алгоритм консенсуса Exonum

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

Задачей валидаторов является проведение голосования за включение новых блоков в блокчейн. Как мы уже говорили выше, сеть Exonum^TM может стабильно функционировать даже при условии, что треть всех узлов являются византийскими. Соответственно, для достижения консенсуса блок должны одобрить 2/3 узлов блокчейн-сети. И это утверждение можно подтвердить математически.

Предположим, что в сети работает h честных узлов-валидаторов (honest) и f византийских (faulty). Тогда общее число валидаторов можно представить как N = h + f. Все валидаторы голосуют за один из двух представленных блоков, при этом они собирают у себя голоса других участников и принимают решение о победителе на основе порогового правила.

Оно гласит: число голосов за победителя должно быть больше или равно α * N, где α — число в промежутке от 0 до 1. Таким образом, абсолютное большинство голосов достигается при α > 1/2.

По окончании голосования каждый валидатор самостоятельно принимает решение о том, какой из двух кандидатов выиграл. Однако валидаторы могут и не решить, за кого отдать голос, если слишком мало валидаторов отправят свои голоса остальным. Это может произойти в том случае, если византийские узлы начнут рассылать голоса за разных кандидатов честным участникам сети, пытаясь их запутать.

Чтобы исключить подобную ситуацию, необходимо соблюсти два условия:

• Честные валидаторы должны иметь возможность сделать выбор без участия византийских узлов. Это условие определяется свойством liveness, о котором мы говорили выше. Математически оно выражается следующим неравенством: h ≥ α * N.
• Кандидат, за которого проголосовало меньшинство честных валидаторов, не может преодолеть порог в α * N. Это продиктовано критерием консистентности (consistency). Условие выражается так: [h/2] + f < α * N, где [h/2] — целая часть числа h/2.

В итоге получаем следующую цепочку неравенств: h > 2f, α > 2/3 и N ≥ 3f + 1. Отсюда следует, что для подтверждения блока транзакций, он должен получить две трети голосов валидаторов.

Далее поговорим о том, как именно происходит голосование валидаторов в Exonum-блокчейне. В общем виде схема выглядит следующим образом:

Процесс достижения консенсуса начинается с того, что главный узел — он выбирается отдельным алгоритмом и регулярно меняется — формирует список транзакций, которые должны быть добавлены в блокчейн (составляет proposal). Затем этот список транслируется по всей сети узлам-валидаторам.

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

Тот узел, предложение которого получило две трети одобрений от валидаторов, автоматически блокируется. Это состояние называется proof-of-lock. Узел теряет возможность голосовать за предложения других валидаторов и не может поменять свой proposal.

После того как необходимое количество голосов от валидаторов набрано, главный узел прописывает одобренные транзакции в блок и транслирует специальное сообщение — precommit. Оно содержит хеш обновленного состояния блокчейна ^[10] и обозначает, что узел готов добавить предложенный блок в цепочку. В тот момент, когда большая часть валидаторов отвечает аналогичным сообщением precommit (с таким же хешем), то блок добавляется в блокчейн. Консенсус оказывается достигнут, и процедура повторяется для каждого последующего блока.

Для повышения стабильности работы системы валидаторы периодически обмениваются еще двумя сообщениями — Request и Block. Первое генерируется, если узлам не хватает каких-либо данных о транзакциях. Второе нужно для передачи информации о блоке транзакций узлу, который отстал по времени (например, отключался), для синхронизации работы всей сети.

Чтобы оценить возможности консенсуса, мы проверяли работу блокчейна на базе двух конфигураций: в одном дата-центре и нескольких, географически распределенных, дата-центрах. Во время тестов оценивался параметр TPS — количество транзакций в секунду — для разного числа валидаторов. Далее, мы приведем графики изменения производительности сети в блокчейнах для работы с криптовалютами (черный график) и временными метками — timestamping (синий график).

TPS как функция от числа валидаторов в случае с одним дата-центром

TPS как функция от числа валидаторов в случае с несколькими дата-центрами

В среднем, Exonum-блокчейн оказался способен обрабатывать от 2 до 13 тыс. транзакций за секунду, в зависимости от конфигурации сети.

Где уже используется Exonum

Фреймворк Exonum^TM сегодня применяется в самых разных проектах. Летом прошлого года мы вместе с «Технопром» создали ^[11] для РЖД специальный маркетплейс. В Exonum-блокчейне фиксируются операции с деталями для поездов и данные техпаспорта каждого вагона. Это дает возможность отслеживать перемещение всех запчастей от официальных поставщиков и обнаруживать подделки.

Также мы запустили ^[12] образовательный блокчейн-проект на базе университета «Синергия». Реестр регистрирует и хранит все сведения об успеваемости студентов: оценки, результаты экзаменов и дипломы. По словам наших коллег, такой подход исключает возможность вносить изменения в документы об образовании и помогает экономить на их архивировании и сертификации.

Еще на базе Exonum^TM мы реализовали ^[13] серию пилотных проектов, ускоряющих разработку и выпуск программного обеспечения. Наши партнеры из инжиниринговой организации Aricent шесть месяцев тестировали фреймворк в работе. Блокчейн-подход к разработке ПО повысил производительность программистов и скорость исправления ошибок.

Другой проект мы начали ^[14] совместно с группой медицинских компаний. В том числе со стартапом Insillico, где применяют глубокое обучение для поиска новых лекарств. Exonum станет ядром экосистемы для обмена данными пациентов. Система упростит проведение клинических испытаний, а также поможет с анализом медицинских карт и ДНК пациентов. В итоге врачи смогут оперативнее диагностировать заболевания и назначать более эффективное лечение.

Мы надеемся, что наш блокчейн найдет применение в других задачах и в других отраслях. Сейчас мы работаем над тем, чтобы внедрить Exonum^TM в системы для голосований, аукционов и управления цифровыми правами. Демо некоторых решений есть на официальном сайте ^[15].

Автор: BitfuryRussia

Источник ^[16]