В этой статье описан алгоритм консенсуса 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:

* Важно отметить, что 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 должен создать блок и "раскидать" его по сети, причем крайне важно, чтобы другие валидаторы успели получить этот блок.

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

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

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

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

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

Optimal scenario

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

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

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

В любом случае видим, что это не создало проблем другим участникам и у них есть 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