ExonumTM — это наш открытый фреймворк для создания приватных блокчейнов. Сегодня мы расскажем, как работает его алгоритм консенсуса.
Изображение: Bitfury
Прежде чем перейти к рассказу о том, как устроен алгоритм консенсуса ExonumTM, поговорим о том, зачем вообще нужны эти алгоритмы в блокчейнах.
Блокчейн представляет собой распределенную систему без центрального администратора. Для согласования нового блока в сети (и, соответственно, транзакций) участники сети используют специальные алгоритмы консенсуса. Задача консенсуса — помочь узлам одноранговой сети прийти к единому мнению по поводу того, каким должно быть ее новое состояние — то есть выбрать следующий блок в цепочке блокчейна.
Это нужно для того, чтобы защитить блокчейн и информацию, хранящуюся в нем, от подмены. К примеру, в блокчейн на базе ExonumTM, реализованном для РЖД, записывается информация об операциях с деталями для вагонов и поездов. Блокчейн обеспечивает достоверность данных в блоке, что дает компании следить за маршрутом запчастей от поставщика и своевременно обнаруживать подделки. Подробнее об этом и других кейсах мы расскажем дальше.
Разрабатывая алгоритм консенсуса ExonumTM, нам важно было решить проблему византийского поведения узлов. Под византийским поведением мы понимаем зловредную деятельность отдельных узлов сети. К такой деятельности также можно отнести ситуации, когда узлы теряют связь с сетью или уходят в офлайн.
Еще в середине 80-х годов было доказано, что для обеспечения устойчивости распределенной системы она должна работать в условиях частичной синхронности. При этом алгоритм консенсуса обязан обладать следующими критериями:
Для сети с известным количеством участников модель алгоритма консенсуса, устойчивого к византийскому поведению узлов (byzantine fault tolerance, BFT), в условиях частичной синхронности допускает менее 1/3 злонамеренных (византийских) участников в сети.
В ExonumTM-блокчейне присутствуют три типа узлов: валидаторы, аудиторы и легкие клиенты. Первые являются непосредственными участниками алгоритма консенсуса, а вторые — распределяют нагрузку в сети и контролируют работу валидаторов. Что касается легких клиентов, то они лишь предоставляют участникам сети возможность отправлять транзакции в блокчейн. Легкие клиенты и аудиторы не участвуют напрямую в алгоритме консенсуса, поэтому в рамках этого материала мы о них говорить не будем.
Задачей валидаторов является проведение голосования за включение новых блоков в блокчейн. Как мы уже говорили выше, сеть ExonumTM может стабильно функционировать даже при условии, что треть всех узлов являются византийскими. Соответственно, для достижения консенсуса блок должны одобрить более 2/3 узлов блокчейн-сети. И это утверждение можно подтвердить математически.
Предположим, что в сети работает h честных узлов-валидаторов (honest) и f византийских (faulty). Тогда общее число валидаторов можно представить как N = h + f. Все валидаторы принимают решение о «победителе» на основе порогового правила.
По окончании голосования каждый валидатор самостоятельно принимает решение о том, какой из двух кандидатов выиграл. Однако валидаторы могут и не решить, за кого отдать голос, если слишком мало валидаторов отправят свои голоса остальным. Это может произойти в том случае, если византийские узлы начнут рассылать голоса за разных кандидатов честным участникам сети, пытаясь их запутать.
Чтобы исключить подобную ситуацию, необходимо соблюсти два условия:
В итоге получаем следующую цепочку неравенств: h > 2f, α > 2/3 и N ≥ 3f + 1. Отсюда следует, что для подтверждения блока транзакций, он должен получить строго больше 2/3 голосов валидаторов.
Далее поговорим о том, как именно происходит голосование валидаторов в ExonumTM-блокчейне. В общем виде схема выглядит следующим образом:
Процесс достижения консенсуса начинается с того, что главный узел — он выбирается отдельным алгоритмом и регулярно меняется — формирует список транзакций, которые должны быть добавлены в блокчейн (составляет proposal). Затем этот список транслируется по всей сети узлам-валидаторам.
Валидаторы проверяют полученное сообщение на соответствие формату сериализации. Если фиксируются какие-либо ошибки, то узел полностью игнорирует полученное сообщение. Например, будет проигнорировано предложение добавить блок в середину блокчейна или повторно записать уже существующую транзакцию. Если все в порядке, то начинается этап голосования — узлы валидаторы голосуют за добавление блока в блокчейн, транслируя сообщение prevote.
Тот узел, предложение которого получило больше 2/3 одобрений от валидаторов, теряет возможность голосовать за предложения других валидаторов и не может поменять свой proposal. Это состояние называется proof-of-lock.
После того как необходимое количество голосов от валидаторов набрано, главный узел прописывает одобренные транзакции в блок и транслирует специальное сообщение — precommit. Оно содержит хеш обновленного состояния блокчейна и обозначает, что узел готов добавить предложенный блок в цепочку. В тот момент, когда большая часть валидаторов отвечает аналогичным сообщением precommit (с таким же хешем), то блок добавляется в блокчейн. Консенсус оказывается достигнут, и процедура повторяется для каждого последующего блока.
Для повышения стабильности работы системы валидаторы периодически обмениваются еще двумя сообщениями — Request и Block. Первое генерируется, если узлам не хватает каких-либо данных о транзакциях. Второе нужно для передачи информации о блоке транзакций узлу, который отстал по времени (например, отключался), для синхронизации работы всей сети.
Чтобы оценить возможности консенсуса ExonumTM, мы проверяли работу блокчейна на базе двух конфигураций: в одном дата-центре и нескольких, географически распределенных, дата-центрах. Во время тестов оценивался параметр TPS — количество транзакций в секунду — для разного числа валидаторов. Далее, мы приведем графики изменения производительности сети в блокчейнах для работы с криптовалютами (черный график) и временными метками — timestamping (синий график).
TPS как функция от числа валидаторов в случае с одним дата-центром
TPS как функция от числа валидаторов в случае с несколькими дата-центрами
В среднем, ExonumTM-блокчейн оказался способен обрабатывать от 2 до 13 тыс. транзакций за секунду, в зависимости от конфигурации сети.
Фреймворк ExonumTM сегодня применяется в самых разных проектах. Летом прошлого года мы вместе с «Технопром» создали для РЖД специальный маркетплейс. В ExonumTM-блокчейне фиксируются операции с деталями для поездов и данные техпаспорта каждого вагона. Это дает возможность отслеживать перемещение всех запчастей от официальных поставщиков и обнаруживать подделки.
Также мы запустили образовательный блокчейн-проект на базе университета «Синергия». Реестр регистрирует и хранит все сведения об успеваемости студентов: оценки, результаты экзаменов и дипломы. По словам наших коллег, такой подход исключает возможность вносить изменения в документы об образовании и помогает экономить на их архивировании и сертификации.
Еще на базе ExonumTM мы реализовали серию пилотных проектов, ускоряющих разработку и выпуск программного обеспечения. Наши партнеры из инжиниринговой организации Aricent шесть месяцев тестировали фреймворк в работе. Блокчейн-подход к разработке ПО повысил производительность программистов и скорость исправления ошибок.
Другой проект мы начали совместно с группой медицинских компаний. В том числе со стартапом Insillico, где применяют глубокое обучение для поиска новых лекарств. ExonumTM станет ядром экосистемы для обмена данными пациентов. Система упростит проведение клинических испытаний, а также поможет с анализом медицинских карт и ДНК пациентов. В итоге врачи смогут оперативнее диагностировать заболевания и назначать более эффективное лечение.
Мы надеемся, что наш блокчейн найдет применение в других задачах и в других отраслях. Сейчас мы работаем над тем, чтобы внедрить ExonumTM в системы для голосований, аукционов и управления цифровыми правами. Демоверсии некоторых из этих решений вы можете найти на официальном сайте ExonumTM.
Изображение: Bitfury
Зачем нужны алгоритмы консенсуса
Прежде чем перейти к рассказу о том, как устроен алгоритм консенсуса ExonumTM, поговорим о том, зачем вообще нужны эти алгоритмы в блокчейнах.
Блокчейн представляет собой распределенную систему без центрального администратора. Для согласования нового блока в сети (и, соответственно, транзакций) участники сети используют специальные алгоритмы консенсуса. Задача консенсуса — помочь узлам одноранговой сети прийти к единому мнению по поводу того, каким должно быть ее новое состояние — то есть выбрать следующий блок в цепочке блокчейна.
Это нужно для того, чтобы защитить блокчейн и информацию, хранящуюся в нем, от подмены. К примеру, в блокчейн на базе ExonumTM, реализованном для РЖД, записывается информация об операциях с деталями для вагонов и поездов. Блокчейн обеспечивает достоверность данных в блоке, что дает компании следить за маршрутом запчастей от поставщика и своевременно обнаруживать подделки. Подробнее об этом и других кейсах мы расскажем дальше.
Какие задачи мы решали, создавая алгоритм консенсуса Exonum
Разрабатывая алгоритм консенсуса ExonumTM, нам важно было решить проблему византийского поведения узлов. Под византийским поведением мы понимаем зловредную деятельность отдельных узлов сети. К такой деятельности также можно отнести ситуации, когда узлы теряют связь с сетью или уходят в офлайн.
Еще в середине 80-х годов было доказано, что для обеспечения устойчивости распределенной системы она должна работать в условиях частичной синхронности. При этом алгоритм консенсуса обязан обладать следующими критериями:
- Liveness — должна быть возможность принять новый блок в любой момент времени.
- Consistency — база данных транзакций на всех узлах сети должна быть идентичной.
- Censorship resistance — узлы не должны отдавать предпочтение каким-либо транзакциям или игнорировать их.
Для сети с известным количеством участников модель алгоритма консенсуса, устойчивого к византийскому поведению узлов (byzantine fault tolerance, BFT), в условиях частичной синхронности допускает менее 1/3 злонамеренных (византийских) участников в сети.
Как работает алгоритм консенсуса Exonum
В ExonumTM-блокчейне присутствуют три типа узлов: валидаторы, аудиторы и легкие клиенты. Первые являются непосредственными участниками алгоритма консенсуса, а вторые — распределяют нагрузку в сети и контролируют работу валидаторов. Что касается легких клиентов, то они лишь предоставляют участникам сети возможность отправлять транзакции в блокчейн. Легкие клиенты и аудиторы не участвуют напрямую в алгоритме консенсуса, поэтому в рамках этого материала мы о них говорить не будем.
Задачей валидаторов является проведение голосования за включение новых блоков в блокчейн. Как мы уже говорили выше, сеть ExonumTM может стабильно функционировать даже при условии, что треть всех узлов являются византийскими. Соответственно, для достижения консенсуса блок должны одобрить более 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. Отсюда следует, что для подтверждения блока транзакций, он должен получить строго больше 2/3 голосов валидаторов.
Далее поговорим о том, как именно происходит голосование валидаторов в ExonumTM-блокчейне. В общем виде схема выглядит следующим образом:
Процесс достижения консенсуса начинается с того, что главный узел — он выбирается отдельным алгоритмом и регулярно меняется — формирует список транзакций, которые должны быть добавлены в блокчейн (составляет proposal). Затем этот список транслируется по всей сети узлам-валидаторам.
Валидаторы проверяют полученное сообщение на соответствие формату сериализации. Если фиксируются какие-либо ошибки, то узел полностью игнорирует полученное сообщение. Например, будет проигнорировано предложение добавить блок в середину блокчейна или повторно записать уже существующую транзакцию. Если все в порядке, то начинается этап голосования — узлы валидаторы голосуют за добавление блока в блокчейн, транслируя сообщение prevote.
Тот узел, предложение которого получило больше 2/3 одобрений от валидаторов, теряет возможность голосовать за предложения других валидаторов и не может поменять свой proposal. Это состояние называется proof-of-lock.
После того как необходимое количество голосов от валидаторов набрано, главный узел прописывает одобренные транзакции в блок и транслирует специальное сообщение — precommit. Оно содержит хеш обновленного состояния блокчейна и обозначает, что узел готов добавить предложенный блок в цепочку. В тот момент, когда большая часть валидаторов отвечает аналогичным сообщением precommit (с таким же хешем), то блок добавляется в блокчейн. Консенсус оказывается достигнут, и процедура повторяется для каждого последующего блока.
Для повышения стабильности работы системы валидаторы периодически обмениваются еще двумя сообщениями — Request и Block. Первое генерируется, если узлам не хватает каких-либо данных о транзакциях. Второе нужно для передачи информации о блоке транзакций узлу, который отстал по времени (например, отключался), для синхронизации работы всей сети.
Чтобы оценить возможности консенсуса ExonumTM, мы проверяли работу блокчейна на базе двух конфигураций: в одном дата-центре и нескольких, географически распределенных, дата-центрах. Во время тестов оценивался параметр TPS — количество транзакций в секунду — для разного числа валидаторов. Далее, мы приведем графики изменения производительности сети в блокчейнах для работы с криптовалютами (черный график) и временными метками — timestamping (синий график).
TPS как функция от числа валидаторов в случае с одним дата-центром
TPS как функция от числа валидаторов в случае с несколькими дата-центрами
В среднем, ExonumTM-блокчейн оказался способен обрабатывать от 2 до 13 тыс. транзакций за секунду, в зависимости от конфигурации сети.
Где уже используется Exonum
Фреймворк ExonumTM сегодня применяется в самых разных проектах. Летом прошлого года мы вместе с «Технопром» создали для РЖД специальный маркетплейс. В ExonumTM-блокчейне фиксируются операции с деталями для поездов и данные техпаспорта каждого вагона. Это дает возможность отслеживать перемещение всех запчастей от официальных поставщиков и обнаруживать подделки.
Также мы запустили образовательный блокчейн-проект на базе университета «Синергия». Реестр регистрирует и хранит все сведения об успеваемости студентов: оценки, результаты экзаменов и дипломы. По словам наших коллег, такой подход исключает возможность вносить изменения в документы об образовании и помогает экономить на их архивировании и сертификации.
Еще на базе ExonumTM мы реализовали серию пилотных проектов, ускоряющих разработку и выпуск программного обеспечения. Наши партнеры из инжиниринговой организации Aricent шесть месяцев тестировали фреймворк в работе. Блокчейн-подход к разработке ПО повысил производительность программистов и скорость исправления ошибок.
Другой проект мы начали совместно с группой медицинских компаний. В том числе со стартапом Insillico, где применяют глубокое обучение для поиска новых лекарств. ExonumTM станет ядром экосистемы для обмена данными пациентов. Система упростит проведение клинических испытаний, а также поможет с анализом медицинских карт и ДНК пациентов. В итоге врачи смогут оперативнее диагностировать заболевания и назначать более эффективное лечение.
Мы надеемся, что наш блокчейн найдет применение в других задачах и в других отраслях. Сейчас мы работаем над тем, чтобы внедрить ExonumTM в системы для голосований, аукционов и управления цифровыми правами. Демоверсии некоторых из этих решений вы можете найти на официальном сайте ExonumTM.
