[Перевод] Разбор алгоритма консенсуса в Tendermint

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 блоке и в дальнейшем их список не меняется (главное, чтобы в начальном списке визайнтийских валидаторов было строго меньше ⅓!). В том же 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

  • Tendermint wiki — Validators
  • Tendermint wiki — Byzantine Consensus Algorithm
  • Consensus in the Presence of Partial Synchrony — C. Dwork, 1988
  • Blockchain Consensus Protocols in the Wild — Christian Cachin, Marko Vukoli

© Habrahabr.ru