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

Original author: Sergey Potekhin, Softblocks Co
  • Translation

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


AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 27

    0
    Интересная концепция.
    Допустим треть + 1 будут в китае, и они отвалятся(как это бывает в реальности) сеть будет парализована, т.к. недостаточно валидаторов для голосования?
      0
      Да, все верно. На самом деле, описанная вами проблема действительно актуальна, особенно в случае с Китаем. Например, у Bitcoin перерасчет сложности делается раз в 2016 блоков (~2 недели).

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

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

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

          Нет, изначально вариация на тему PBFT (в практически девственном виде). Если веса голосов участников будут зависеть от количества монет, то будет DPoS.

            +1
            Да, все верно. В DPoS вашу значимость определит размер депонированной суммы, а, например, в PoI (Proof-of-Importance, используется в NEM) ваш вес зависит от «важности» в сети. Сам их алгоритм довольно нетривиален, поэтому я в течении следующего месяца обязательно про него напишу :)
              0
              Не будете ли писать и о Proof-of-Authority?
              P.S. У Вас куча наинтереснейших статей по блокчейну, искреннее спасибо за них.
                0
                Не очень понимаю, что можно рассказать про PoA, если подскажете интересную тему — обязательно напишу.
                Спасиб :)
                  0
                  Скажем так, как вы бы прокомментировали вот такую популярную картинку:

                  image
                    0
                    1. Обладание вычислительной мощностью (чипы на картинке). Анонимно
                    2. Обладание монетами. Анонимно
                    3. Обладание определенным приватным ключом (паспорт на картинке). Неанонимно
          0
          Шикарная статья, то что нужно!
          Вопрос по алгоритмам консенсуса (не по этому конкретно, а вообще): получается что для достижения консенсуса нужен обмен «каждый с каждым»? А если в сети миллионы пиров?
            0
            Если скачать криптовалютный кошель, он считает хорошим соединение с сетью, когда нашел и получает данные от 4-5 нод.
            Обычно держит соединение на 8, и еще несколько держит в запасе. Из чего делаем вывод, что предполагается, что 8 разных точек в сети не могут врать.
            К тому же достижение консенсуса достигается не кол-вом пользователей, а большей вычислительной мощностью(PoW) или большим балансом(PoS). Если упростить.
              0

              В случае с описанным в статье базовым консенсусом – как раз-таки за счёт количества участников. Описанная база интересна, но содержит нюанс, которые с моей точки зрения ограничивают её применение. Поправьте меня, если я неправ, но каждый блок должен хранить 2/3+ неких подписей из pre-vote и/или pre-commit сообщений.

                0
                Да, в общем то верно. Вот структура блока из их документации — ссылка. Только хранить pre-vote вроде бы ни к чему, достаточно только pre-commit. Ну потому что если у вас есть pre-commit — то из этого однозначно следует, что у вас есть и pre-vote, а если их нет — то и блока нет :)
            0
            В разделе Malicious proposer на первой иллюстрации А отправляет блоки в B,D,E, но не отправляет в С, а в С блок приходит от В, почему так?
              0
              Это была попытка продемонстрировать несвязность сети нод :)
                0
                Несвязанность… Не очень понятно, но я тогда сформулирую вопрос по другому: каждый раз нода отправляет сообщения ВСЕМ, или вы как-то реализовали возможность делегировать отправление сообщений. При такой ситуации ведь самый первый вопрос в доверии, отправит ли прокси-нода сообщение дальше.
                  +1
                  Нет, нода не отправляет сообщение всем. Представьте, что у вас 10.000 участников сети — вы же не будете держать соединение со всеми (9.999) и отправлять каждому один и тот же пакет. На то сеть и децентрализована, что вы можете держать в «контактах» штук 10 других нод и отправлять только им. А они уже, проверив сообщение на корректность, отправят своим десяти «контактам», а те своим и так далее.

                  Доверие действительно есть, но понятно, что его нужно тем меньше, чем больше у вас «контактов».
                    0
                    Вот почему спрашиваю: если 1 отправляет сообщение в 9999 узлов, то он условно говоря и зависит именно от этого множества и процентного содержания неких византийцев, а если только от десяти, то его зависимость весьма… зависима (пардон за тавтологию). Т.е. с точки зрения BCA алгоритма какая у меня может быть уверенность именно в этих 10, или следующих за ними в волне 100?

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

                    Подозреваю, что это что-то из p2p или торрентов, но если возможно, объясните на пальцах. Возможно, при разработке в данном контексте вы рассматривали какие-то альтернативы, можете выложить тут какую-то такую цепочку рассуждений?

                    И ещё, с одной стороны, при отправке тупо всем 9999 сообщений это кажется много, но ведь в конечном итоге эти 9999 запросов пройдутся по сети всё равно, и если каждый из узлов при инициализации новой транзакции будет вместо отправки «волны» массово броадкастить (так и хотелось написать «спамить»), то при какой-то более-менее равномерной нагрузке в сети всё окажется достаточно равноценно… Можете дать свои соображения по этому вопросу? Понятно, что при 1000000 узлов это видится по другому, но тем не менее, для не такого колоссального числа узлов, измеряемого тысячами, а не десятками тысяч и более?
                      +1
                      Отвечая на ваш claygod вопрос ниже, то бишь тут.
                      У вас возникла путаница из-за заметной разницы между красивой обёрткойконцепцией и реально работающей моделью. Ключевое в идеальной ситуации(тот самый конь), когда все вокруг византийцы и надо проверятьопросить всех 9999. Далее удобство пользования. И реально структура сети.
                      По пунктам:
                      1. В реальности византийцев уже давно нет и можно с уверенностью считать, что 99% такие же как и вы. То есть обычный пользователь сети, которых если интересует сеть, то больше теоретически. Описанное правильнее называть не византийскими генералами, а византийской пехотой которая по этой схеме проверяет всю армию. Они б просто завалили друг друга посланиями и проверяли их пару недель.
                      2. Если вам надо обменяться с 5001 (на самом деле 50%+1, а не всем) ради проверки одного сообщения. Это значит в понятных цифрах, что если б биткоин работал как вы описываете, понадобилось бы подключение 70-100Mbit/s
                      упрощенно в цифрах
                      Биткоин по скорости уступает многих альтернативам, но даже его заявленные 7 транзакций в секунду, который на самом деле обычно около 4-5.
                      Итого упростим многое из протокола и получим 1kb опросить 5000 раз = 5 мегабайт в секунду т.е. ~50Mbit только, чтоб проверять проходящие в сети транзакции. Как думаете много ли будет желающих? Бонус: сеть лайткоин может в 10 раз быстрее.

                      3. Реальная структура инета не позволяет выдать всем статический «белый» IP. А потому, все у кого нет «белого» IP или он динамический приходится подключаться к тем у кого они есть. И именно они становятся в этом случае генералами. Но мы как солдат 21го века держим связь сразу с 8 генералами, сверяя все сообщения, хотя возмутители спокойствия из сети быстро выбрасываются, и вы о них не узнаете(не получите IP для подключения). На самом деле просто для скорости — многопоточного скачиванияполучения информации.

                      Попытка изложить достаточно понимания без специальных знаний.
                        0
                        TrllServ, спасибо за разъяснение, как говорится, век живи, век учись. С точки зрения показанных вами цифр я бы сказал, что броадкаст возможен лишь в какой-то небольшой сети, сотни штук (100*1kb=0.1mb). Но и при таком варианте 1000 транзакций в секунду создаст трафик ~100Mbit, что конечно, весьма много.
                        (Поправьте мои рассуждения, если они неверны).

                        И тогда если можно, разьясните, как же всё-таки гарантируется доставка сообщения всем? Да и с немногими, но возможными византийцами как быть в этом случае? К примеру в википедии на странице Одноранговая сеть упомянуто, что к примеру RIAA дискредитирует пиринговые сети, что в контексте блокчейна даже ещё больше вызывает вопросов.
                          +1
                          claygod, ну зачем же так сурово? (шутко)
                          я пол часа ищу на профильных сайтах, атаку RIAA которая дискредитирует p2p. А оказалось, что яндекс прав подсовывая любезно информацию про музыку и ссылку на википению. Не ищем легких путей.
                          По существу вопроса.
                          Во первых это не дискредитирует технически систему, она не становится уязвимой. Тут просто ищется повод, что б применить судебное решение по отработанной схеме(прецедентам). Более того, аналогичная атака начата на Биткоин, кто-то намеренно положил в блокчейн, очень хитрым способом, что-то «похожее на детское порно». Слово «похожее», добавляется, что б исключить судебное преследование распространяющего СМИ. geektimes.ru/post/299275
                          Особо интересны каменты. Пример «фотография порвана на тысячи кусочков и раскидана по блокам» очень точное описание способа, что-то положить в сеть биткоин. Можно ли считать это можно ли это считать злым умыслом всех кто хранит полную историю — мне кажется сомнительно. Но какое примут решение, если дойдет до суда, я не сомневаюсь. Копирасты умеют превратить в бред всё за что берутся.

                          Во вторых, там же написано, что было найдено решение.
                    +1
                    Как и написал Pavlov_dog, реальные клиенты не держат связь сразу со всеми — слишком затратно, а при увеличении сети станет просто не реальной нагрузкой. Большинство ныне существующих проектов держат всего 8 соединений и считают это надёжной связью с сетью. Ещё несколько контактов проверяют и держат «про запас».

                    Работа чем-то похожа на работу GPS приемника в работе и выборе спутников.
                      0
                      Спасибо за ответ, чуть выше я ещё задал вопросы, поглядите пожалуйста, чтобы не дублировать в соседних ветках.
                0
                BCA только так называемые валидаторы могут принимать участие в формировании блокчейна
                Я правильно понимаю, что это означает, что сеть не децентрализована — ведь у неё есть выделенные узлы?

                Ещё один вопрос — как решается проблема того, что узел может «майнить» без особых затрат разные форки?
                  0
                  > Я правильно понимаю, что это означает, что сеть не децентрализована — ведь у неё есть выделенные узлы?

                  Это вопрос формулировок, но в целом сети ничто не мешает иметь выделенные узлы и быть децентрализованной. Например в Bitcoin тоже есть специальные узлы, которые майнят — их безусловно меньшая часть.

                  > Ещё один вопрос — как решается проблема того, что узел может «майнить» без особых затрат разные форки?

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

                  Таки нет? Pavlov_dog

                  Only users with full accounts can post comments. Log in, please.