tendermint_logo


В этой статье описан алгоритм консенсуса BCA (Byzantine Consensus Algorithm), используемый в Tendermint. Разработанный на основе протокола DLS, он не требует никакого "активного" майнинга, как в Proof-of-Work, и может обеспечить безопасную работу сети при наличии как минимум 2/3+ (строго больше чем две трети) "честных" участников сети. Ниже рассказно о том, как этот алгоритм реализован в Tendermint, приведена статистика его работы и смоделировано поведение алгоритма на небольшой сети из пяти участников.


Table of contents


  • Introduction
  • Validators
  • Simple scheme
  • Algorithm steps
    • Malicious proposer
    • Optimal scenario
  • Conclusion
  • Links

Introduction


С момента появление Bitcoin с его Proof-of-Work была проделана колоссальная работа по поиску новых алгоритмов консенсуса. Пересмотру подверглось все:


  • пропускная способность сети (сложно говорить о конкуренции Visa и Bitcoin, имея 7 TPS против 4000 TPS)
  • масштабирование сети (например проблема шардинга данных)
  • устойчивость к целому классу новых атак, характерных для блокчейн-сетей

На данный момент, как нам кажется, существует не так много проектов с потенциально интересными решениями для этих проблем. В первую очередь это конечно семейство Delegated-Proof-of-Stake (BitShares, EOS, Lisk). Помимо этого есть NEM с Proof-of-Importance и заявленными 4000 TPS (о том, как такое вообще возможно мы обязательно расскажем в одной из следующих статей). Определенного внимания заслуживает tangle, создаваемый в IOTA. Но в этой статье мы хотели бы остановиться на алгоритме BCA и его реализации в проекте Tendermint.


Validators


В первую очередь нужно рассказать о тех, кто поддерживает сеть в рабочем состоянии (то есть участвует в построении консенсуса). В отличие от тех же Proof-of-Work или Proof-of-Stake, где майнером может стать любой желающий в любой момент, в BCA только так называемые валидаторы могут принимать участие в формировании блокчейна.


Каким образом обычный участник сети становится валидатором — зависит от конкретной реализации. В простейшем случае валидаторы объявляются в genesis блоке и в дальнейшем их список не меняется (главное, чтобы в начальном списке визайнтийских валидаторов было строго меньше 1/3!). В том же Tendermint можно легко реализовать ротацию валидаторов. Для этого достаточно обозначить в протоколе специальную транзакцию, которая будет отправляться участником, если он хочет "баллотироваться". Дополнительно можно, как внутри того же Lisk, ввести голосование за кандидатов или же выбирать их в соответствии с какими-то уже имеющимися параметрами.


В реализации Tendermint, для любого блока всегда можно получить точный список валидаторов*. Идентифицируются они своими публичными ключами, и в процессе голосования подписывают соответствующими приватными ключами сообщения, отправляемые другим валидоторам и обычным участникам сети. Таким образом можно всегда определить автора того или иного голоса и быть уверенным, что никто "со стороны" не сможет принять участие в построении консенсуса.




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


Simple scheme


Начнем с абстрактного описания того, что происходит в алгоритме, в момент поиска блока N.


NewHeight -> (Propose -> Prevote -> Precommit)+ -> Commit -> NewHeight ->...

Propose — какой-то proposer* предлагает свою версию блока на высоту N.


Prevote — на этом шаге каждый из валидаторов дает свое "оценочное мнение" блоку. В простейшем случае валидатор отправит в сеть сообщение вида "Получил блок <хэш блока>, со всем согласен".


Precommit — спустя некоторое время, выделенное на шаг Prevote, каждый валидатор проверяет, сколько у него "накопилось" Prevote сообщений от других участников. Если их 2/3+ от общего числа валидаторов, то валидатор отправляет Precommit транзакцию.


Три шага в скобках (Propose -> Prevote -> Precommit) — это так называемый раунд. Его суть в том, что существует множество случаев, когда по какой-то причине не получилось найти новый блок. Например выбранный proposer мог быть оффлайн или мог предложить заведомо некорректный блок (этот случай подробно описан ниже).


В этом случае в процесс построения консенсуса вносится два изменения:


  • Выбирается новый proposer
  • У каждого шага есть некоторая общая для всех продолжительность по времени (условно, шаг Prevote длится 5 секунд, после этого все участники переключаются на Precommit). Так как велика вероятность, что что-то пошло не так из-за слабого соединения (например у proposer интернет плохой, он вообще не успел блок загрузить и раскидать по сети), то длительность каждого шага увеличивается на какую-то константу.

Ниже приведена иллюстрация всего процесса из официальной документации Tendermint:


alogorithm




* Важно отметить, что proposer-ы выбираются round-robin алгоритмом из списка валидаторов в пропорции с их весом**. Это дает два интересных свойства: в первую очередь необходимую нам детерменированность (каждый участник сети должен иметь возможность однозначно знать, кто из валидаторов станет proposer-ом в данном раунде). Но в то же время мы имеем псевдослучайный выбор, который позволит свести на нет атаки, связанные с заранее известной последовательностью proposer-ов в процессе выбора.


** Что такое вес — решать разработчику протокола. В простейшем случае можно присвоить всем валидаторам одинаковый вес, то есть выбор proposer-а будет равномерным.


Algorithm steps


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


Malicious proposer


Для полного понимания алгоритма предлагаю разобрать его работу на "реальной" сети. Для начала, зададим саму сеть:


  • Есть 5 валидаторов: A, B, C, D, E (как вы уже поняли, общее число участников сети роли не играет, для BCA важны только валидаторы).
  • В качестве proposer-а выбран валидатор A. Более того, я предлагаю сделать A — византийским валидатором, чтобы посмотреть на работу сети в момент, когда ее пытаются скомпроментировать.
  • Каждый шаг длится t секунд; работа алгоритма начинается в момент времени T.

Итак, начнем создавать блок #X. Первым идет шаг Propose, длительностью t секунд, в течении которого proposer должен создать блок и "раскидать" его по сети, причем крайне важно, чтобы другие валидаторы успели получить этот блок.


propose


Теперь перейдем к шагу Prevote. Сейчас, главная задача валидаторов — проверить блок и решить, "согласны" они с ним или нет. В этом случае B, C, D, E отправят по сети сообщение Prevote nil — оно означает, что никто из них не согласен с предложенным блоком. Для большей реалистичности предположим, что у E — плохой интернет и он вообще ничего не получил за t секунд. A (proposer также участвует в голосовании!) отправит Prevote, в попытке поддержать свой некорректный блок. Для большей реалитичности, пусть у E как обычно плохой интернет и он вообще не получил никаких новых сообщений от A, B, C, D.


prevote_start


Тогда сообщения, полученные на шаге Prevote, для каждого валидатора выглядят следующим образом:


prevote_end


Поясню, что у E плохой интернет и другие участники вообще не успевают получить от него сообщения.


Остался заключительный шаг раунда — Precommit. B, C, D, E отправят в сеть Precommit nil сообщение (потому что число Prevote сообщений у каждого из них меньше чем 2/3+ числа валидаторов). Посмотрим на собранные Precommit сообщения для каждого валидатора:


precommit_end


Очевидно, что нет валидаторов, которые собрали бы 2/3+ Precommit сообщений, а значит, по схеме выше, этот раунд будет завершен без создания нового блока высоты #X. Важное замечание — в каждом блоке должны находиться эти самые Precommit сообщения и, очевидно, их должно быть как минимум 2/3+. Поэтому даже если A захочет раскидать по сети "ложный" блок, то у него не будет нужного числа подписанных Precommit сообщений, а значит любой участник мгновенно заметит подвох.


Optimal scenario


Как вы уже поняли, в раунде, описанном выше, создать новый блок не получилось. А значит, что перед началом следующего раунда proposer-ом будет выбран другой валидатор (пускай это будет B) и длительность шагов немного увеличена, чтобы нивелировать влияние медленного соединения. Так что в этом раунде валидатор E больше не будет стоять в стороне из-за плохого интернета, а примет полноценное участие.


Опять же, начинаем с шага Propose, причем на этот раз блок полностью валиден и успел дойти до всех валидаторов. Поэтому предлагаю сразу переключиться на шаг Prevote и посмотреть, как выглядит список Prevote сообщений у каждого валидатора. Для большего интереса предположим, что A все еще malicious, так что на этот раз он будет пытаться помешать созданию блока.


prevote_end_optimal


Видно, что у всех валидаторов достаточно Prevote сообщений, чтобы отправлять Precommit сообщения. Опять же ради интереса, предположим, что A отправит Precommit nil сообщение, хотя это формально неправильно с его стороны.


precommit_end_o


В любом случае видим, что это не создало проблем другим участникам и у них есть 2/3+ Precommit сообщений для того, чтобы создать новый блок.


Conclusion


Надеюсь, что статья оказалась вам полезна, раз уж вы дочитали ее до этого места :) Еще пару слов по поводу Tendermint — в ближайшее время мы опубликуем как минимум три статьи про эту замечательную технологию. Первая будет представлять из себя некоторый overview всего проекта и его возможностей. А во второй будет максимально подробно продемонстрирован процесс создания своего блокчейна (никакого ICO, обещаем!) на связке Tendermint + Python 3.


Links


Комментарии (6)


  1. TrllServ
    27.02.2018 22:20

    Интересная концепция.
    Допустим треть + 1 будут в китае, и они отвалятся(как это бывает в реальности) сеть будет парализована, т.к. недостаточно валидаторов для голосования?


    1. Pavlov_dog Автор
      28.02.2018 18:09

      Да, все верно. На самом деле, описанная вами проблема действительно актуальна, особенно в случае с Китаем. Например, у Bitcoin перерасчет сложности делается раз в 2016 блоков (~2 недели).

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


  1. Deosis
    28.02.2018 07:40

    Это дает два интересных свойства: в первую очередь необходимую нам детерменированность (каждый участник сети должен иметь возможность однозначно знать, кто из валидаторов станет proposer-ом в данном раунде). Но в то же время мы имеем псевдослучайный выбор, который позволит свести на нет атаки, связанные с заранее известной последовательностью proposer-ов в процессе выбора.

    Противоречивые требования. Каждый может определить текущего proposer, но не может определить следующего, но должен определить, если понадобится.


  1. claygod
    28.02.2018 13:26

    Название алгоритма не указано, но похоже это DPoS


  1. NeoCode
    28.02.2018 20:19

    Шикарная статья, то что нужно!
    Вопрос по алгоритмам консенсуса (не по этому конкретно, а вообще): получается что для достижения консенсуса нужен обмен «каждый с каждым»? А если в сети миллионы пиров?


    1. TrllServ
      01.03.2018 00:51

      Если скачать криптовалютный кошель, он считает хорошим соединение с сетью, когда нашел и получает данные от 4-5 нод.
      Обычно держит соединение на 8, и еще несколько держит в запасе. Из чего делаем вывод, что предполагается, что 8 разных точек в сети не могут врать.
      К тому же достижение консенсуса достигается не кол-вом пользователей, а большей вычислительной мощностью(PoW) или большим балансом(PoS). Если упростить.