[Перевод] Разбор алгоритма консенсуса в Tendermint
В этой статье описан алгоритм консенсуса 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:
* Важно отметить, что 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
