Сравнение консенсусов PoS: Casper против Tendermint

Сравнение консенсусов PoS: Casper против Tendermint было подробно описано в блоге Cosmos.Network. Задача византийских генералов (BFT) была впервые поставлена в 1982 году (Lamport, Shostak, Pease) для распределенных коммуникационных сетей и упрощенно ее можно сформулировать как «создание надежной системы из ненадежных частей». Вплоть до 1999 года система, успешно решающая BFT, так и не была создана, да она и не была особенно актуальна, поскольку интернет только эволюционировал от централизованных вычислений к распределенным. Все, что требовалось, это устойчивость к сбоям.

Поэтому, первыми получили широкое распространение простые отказоустойчивые алгоритмы Paxos (1998) и Raft (2013). Созданный в 1999 году алгоритм PBFT (P — значит практичный), не выходил за пределы академических структур. Прорывом стала работа Сатоши Накамото, впервые применившего BFT консенсус в схеме блокчейна, и после практической демонстрации этого решения многочисленные исследователи начали искать варианты использования технологии в задачах реального мира.

В 2011 году, на ветке BitcoinTalk сформировались первые обсуждения идеи, впоследствии получившей название Proof-of-Stake, однако первые реализации PoS, такие как Peercoin, изрядно подорвали репутацию идеи. Одним из первых исследователей, предложивших реализацию BFT в PoS открытого блокчейна, стал Чэ Квон (Jae Kwon), основавший Tendermint в 2014 году.

В то время разработчики PoS исходили из допущения, что набор узлов в сети является статическим и остается стабильным на протяжении долгих периодов, что оказалось полностью несостоятельным в условиях реального блокчейна. Чэ Квон впервые адаптировал BFT к блокчейну, используя динамический набор валидаторов и ротацию лидеров, в протоколе Tendermint. За ним последовали другие проекты PoS, такие как Tezos, Casper и другие. Все они использовали разные подходы, однако все искали ответ на один и тот же основной вопрос: возможно ли достичь такого же уровня безопасности как у алгоритма PoW Биткойна, не расходуя при этом материальные ресурсы?

В PoS мощность голосования, деноминированная в нативной криптовалюте, приходит на замену мощности хэширования. Широко известные проблемы блокчейна: ограничение пропускной способности, высокие издержки на обслуживание майнеров PoW и экологические соображения, стали весомым стимулом для привлечения существенных ресурсов в исследования PoS.

Алгоритмы Proof-of-Stake

Casper против Tendermint. Рассмотрим различные варианты PoS, лежащие в основе трех основных криптовалютных протоколов: Casper the Friendly Ghost (или CBC — Correct by Construction), разрабатываемый Владом Замфиром, Casper FFG (Friendly Finality Gadget) Виталика Бутерина и Tendermint Чэ Квона.

Существует два базовых варианта алгоритма PoS — это PoS на основе цепи и BFT-PoS. Tendermint представляет собой BFT вариант, Casper CBC — цепь, а Casper FFG — гибрид двух предыдущих.

Теорема CAP говорит о невозможности одновременного обеспечения больше двух из трех свойств:

Доступность.
Согласованность.
Устойчивость к разделению.

Алгоритмы PoS на основе цепи предпочитают доступность согласованности: доступность означает, что все транзакции будут обработаны, но за счет согласованного состояния, воспроизводящегося по всей цепи. Напротив, алгоритмы BFT-PoS строго выбирают согласованность, предпочитая ее доступности.

Уязвимости Proof-of-Stake

Нечего терять. Виталик Бутерин назвал эту атаку «Нечего терять» (Nothing-at-Stake). Сценарий: валидаторы эффективно атакуют сеть, голосуя за множественные конфликтующие блоки на одинаковой высоте блокчейна — ведь делая это, они ничем не рискуют и максимизируют доходы. Все наивные алгоритмы PoS уязвимы к этой атаке. Оптимальной стратегией для валидаторов будет голосование за максимально возможное количество форков:

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

Защита от этой атаки — введенное Виталиком Бутериным понятие «бритвы» (Slasher), когда недобросовестные действия влекут за собой потерю депозита. Такая бритва, вместе с набором условий, которые влекут за собой ее применение, включена во все три рассматриваемые BFT PoS протокола.

Атака из глубины (Long distance attack). По окончании цикла работы, валидатор забирает свой депозит. Атакующий может построить форк из некоторой глубины цепи, без опасения потерять депозит. Как только депозиты разморожены, исчезает стимул не голосовать за форк, начиная с некоторой высоты цепи. Другими словами, когда депозиты более 2/3 валидаторов разморожены, они могут создать дублирующую цепь, включающую в себя прошлый набор валидаторов, и производить произвольные альтернативные транзакции.

Это может стать критичным для протоколов PoS, так как их модель безопасности обязательно «субъективна». Модель безопасности называется субъективной, если участие в сети требует большого количества социальной информации. Новые узлы, появляющиеся в сети, делают различающиеся выводы о текущем состоянии сети, поскольку их решение базируется на субъективной информации, т. е., на социальной репутации. И напротив, модель безопасности PoW обязательно «объективна», так как текущее состояние сети всегда будет состояние с максимальным количеством доказательства работы, и все новые узлы появляются с одинаковым выводом, поскольку их выводы основаны на объективной информации.

Противодействие атакам из глубины осуществляется с помощью модели слабой субъективности, которая требует от новых узлов соблюдения следующих правил:

Доверенными могут быть только узлы, уже обладающие депозитами.
Размороженные депозиты могут быть перемещены только после некоторого «периода оттаивания». После разморозки, токены должны оставаться на месте от недель до месяцев, так, чтобы удовлетворялись условия синхронизации (т. е., отсроченные сообщения).
Запрет отката дальше чем N блоков, где N — длина депозита.
Опционально: записывать набор валидаторов в блокчейне PoW.

И в обоих вариантах Casper, и в Tendermint, используется простой механизм залогового депозита с последующим «оттаиванием» на срок от недель до нескольких месяцев. К тому же, Casper FFG содержит правило выбора форка, согласно которому откатить назад завершенный (finalized) блок невозможно. Все попытки переписать блок старше последнего завершенного игнорируются протоколом.

Картельный сговор. Наконец, третье препятствие, стоящее перед любой экономической парадигмой, обладающей ценностью, это проблема олигополии, и децентрализованные криптовалютные протоколы здесь не исключение.

Влад Замфир пишет в 4-й главе Истории Casper:

Криптовалюта стремится к концентрации в руках немногих. То же касается и майнинговых мощностей. На многих рынках «реального мира» конкуренция между олигополиями считается нормой. Наладить координацию между несколькими богатыми валидаторами несравнимо проще, чем скоординировать большое количество относительно бедных валидаторов. Так что в этом контексте картельные сговоры полностью ожидаемы.

В борьбе с олигополией валидаторов, Tendermint полагается на вне-протокольные способы сопротивления цензуре. Его авторы утверждают, что пользователи неизбежно заметят формирование картеля, и социальными методами распространят информацию об этом, после чего либо покинут атакуемый блокчейн, либо реорганизуют его.

Таким образом, единственной моделью, явно содержащей способы борьбы с образованием картелей, остается Casper CBC Замфира.

Алгоритм Tendermint

BFT PoS — Tendermint. PoS протоколы на основе BFT псевдослучайно присваивают валидатору право предлагать новые блоки в течение процесса голосования, состоящего из множества раундов. Однако, производство и финализация блоков зависит от супер-большинства (кворум в 2/3) всех валидаторов, подписавших предлагаемый блок. На это может потребоваться несколько раундов, или polkas, пока блоки не станут финализированными. BFT системы терпимы всего к 1/3 сбоев, где сбои включают в себя произвольное и/или недобросовестное поведение.

Tendermint Core. Tendermint состоит из двух основных компонентов: аппарата консенсуса и интерфейса приложений. Аппарат консенсуса называется Tendermint Core. Он отвечает за то, чтобы одинаковые транзакции были записаны на каждой машине в одинаковом порядке. Интерфейс приложений, или ABCI, дает возможность обрабатывать транзакции на любом языке программирования.

Механизм голосования Tendermint Core состоит из нескольких раундов. Каждый раунд представляет собой процесс из трех шагов: валидаторы предлагают блок, сообщают о намерении закончить его создание, а затем подписывают готовые блоки.

Алгоритм консенсуса начинается с набора валидаторов. Валидаторы держат у себя полную копию блокчейна и идентифицируются открытыми ключами. Они по очереди предлагают блоки на каждой новой высоте блокчейна. На один раунд выделяется один предлагающий блок валидатор. Каждое предложение подписывается соответственным приватным ключом валидатора, так что в случае какого-либо сбоя, валидатор, ответственный за него, может быть идентифицирован. Остальные валидаторы голосуют своими приватными ключами по каждому предложению. Однако, из-за асинхронности сети, создание блока может занять несколько раундов.

По ряду причин, блок может не получиться: например, очередной валидатор может оказаться оффлайн, или сеть может испытывать задержки. Перед тем, как перейти к следующему раунду, валидаторы ожидают получения готового предложения в течение определенного временного отрезка. Зависимость от такого таймаута делает Tendermint протоколом со слабой синхронизацией (вместо асинхронного). Однако, остальная часть протокола асинхронна, и валидаторы могут двигаться дальше только получив одобрение супер-большинства в 2/3. Это означает, что 2/3 валидаторов должны быть онлайн, иначе сеть может остановиться.

Если набор насчитывает меньше 1/3 недобросовестных валидаторов, Tendermint гарантирует безопасность (т. е., валидаторы никогда не выдадут конфликтующие блоки на равной высоте). Следовательно, форк в блокчейне, основанном на Tendermint, невозможен.

Основные свойства:

Доказуемая живучесть;
Порог безопасности: 1/3 валидаторов;
Мгновенная завершенность: 1-3 секунды, в зависимости от числа валидаторов;
Приоритет отдается согласованности;
Безопасный консенсус в слабо синхронной сети.
PoS на основе цепи

Конструкция Tendermint предпочитает безопасность и завершенность живучести. Такой подход основан на предположении, что в реальном мире система просто остановится, а участникам придется в восстанавливать систему на программном уровне, вне рамок протокола.

Алгоритмы PoS на основе цепи симулируют консенсус PoW, в котором протокол присваивает право создания целого нового блока псевдослучайно выбранному валидатору, а новый блок привязывается хэшем к родительскому блоку самой длинной предыдущей цепи. PoS на основе цепи, в основном, опирается на синхронные сети, отдавая приоритет доступности за счет согласованности. Оба протокола Casper адаптируют базовые идеи Tendermint к конструкции, предпочитающей живучесть безопасности.

Алгоритм Casper FFG

Casper против Tendermint. Casper FFG представляет собой гибридную реализацию PoW/PoS, созданную под руководством Виталика Бутерина. PoW протокол консенсуса не принимают окончательных решений и, теоретически, блоки могут быть переписаны вплоть до какой-то прошлой высоты цепи. Блок называется «финализированным», когда он ни при каких обстоятельствах не может быть переписан. Поскольку PoW не дает твердых гарантий финализации, он не считается безопасным на уровне консенсуса. Чем глубже в блокчейн погружаются блоки PoW, тем более вероятностно финализированными они становятся. Имплементация логики FFG в блокчейн Эфириума добавит ему свойство необратимости и сопротивляемость атаке 51%.

Casper FFG будет вводиться поэтапно: группа Бутерина предпочла консервативный подход к переходу от модели PoW к PoS. По видимому, окончательный вариант Casper получит лучшие особенности как от FFG, так и от CBC. Логика Casper FFG содержится в смарт-контракте. Чтобы стать валидатором Casper, необходимо отправить некоторое количество ETH (сумма пока не определена) на депозит в этот смарт-контракт.

Чекпойнты (checkpoints) — ключевой компонент PoS консенсуса FFG: протокол оценивает финализацию каждого 50-го блока, который называется чекпойнт, а сам сегмент из 50 блоков называется эпохой. Впервые в Эфириуме появляются валидаторы, которые голосуют за блоки в каждой эпохе.

Процедура финализации чекпойнта, находящегося в предыдущей эпохе, занимает два раунда голосования (т. е., 2 эпохи). Блок 1 считается финализированным после выполнения двух условий:

Супер-большинство в 2/3 валидаторов голосуют за блок 1 в эпохе 1: это называется легализация (justifying) блока 1.
Супер-большинство в 2/3 валидаторов голосует за блок 2 в эпохе 2, где блок 2 — прямой «наследник» блока 1.

Таким образом, блок 1 финализирован в эпохе 2. Эпоха 2 называется LFE (Последняя эпоха финализации).

Иллюстрация логики FFG. Каждый блок представляет чекпойнт. Линии — эпоха между двумя чекпойнтами. Блок становится LFE, когда его прямой наследник легализован.

Валидаторы получают награду, как только чекпойнт финализирован. Однако, если обнаруживаются два финализированных чекпойнта на одинаковой высоте (два форка), включается условие «бритвы» и по меньшей мере 1/3 депозитов уничтожается. Доказательство нарушения передается PoW майнерам в виде транзакции, которые создают блок с этим доказательством, а валидатор, сообщивший о нарушении, получает награду (Finder’s fee).

Далее, допустим, что майнер пытается провести брутфорс атаку. Финализированный блокчейн не позволит переписать блоки даже, если атакующий обладает более 51% мощности хэширования. Таким образом, Casper FFG обеспечивает безопасность. Однако он не может обеспечить живучесть (liveness), поскольку она зависит от механизма предложения блоков, которым остается PoW.

Основные свойства:

Завершенность: порядка 20 минут до финализации. Финализированные эпохи делают блокчейн устойчивым против брутфорс-атак со стороны майнеров.
Безопасность консенсуса.
Доказуемая живучесть.
Приоритет доступности.

У валидаторов появляется сильная мотивация остаться на канонической цепи, поскольку наказание за подтверждение отдельных форков может стать двойным. С формализацией условия «Бритвы 2.0», валидаторы получают наказание не только за двойное голосование, но и за поддержку неверного форка. Это создает условие «разочарования», когда валидаторы предпочтут вообще воздержаться от голосования, если они не уверены, какой форк выбрать.

Алгоритм Casper CBC

PoS протокол, разработанный Владом Замфиром с нуля и оптимизированный для противостоянию олигополиям реального мира (пулам валидаторов). Он воплощает адаптированную для PoS идею протокола GHOST, разработанного для PoW. Принципы, заложенные в основу Casper CBC, используют крипто-экономические методы для достижения уровней безопасности, определяемых самими валидаторами. В отличие от Casper FFG с его гибридным PoW/PoS, рассмотренного в предыдущей главе, Casper CBC — чистая PoS концепция. Так же как и протоколы PoW, CBC выбирает доступность, жертвуя согласованностью. Окончательная финализация блоков отсутствует, вместо этого, она увеличивается вместе с глубиной цепи. Общее свойство FFG и CBC — голова цепи всегда растет быстрее, чем блоки становятся финализированными.

Уникальная особенность CBC — целевые уровни безопасности каждый валидатор выбирает сам. Это параметр, аналогичный тому, как, например, 6 подтверждений транзакции Биткойна являются общепринятым параметром для определения финализации. В то же время, при всей сложности применяемых методов, сеть поддерживает достаточно низкий оверхэд, по сравнению с PoW.

Основные свойства:

Сопротивляемость образованию картелей: CBC построен на принципах сопротивления олигополии: никакой сговор валидаторов не может получить контроль над протоколом.
Приоритет доступности: узлы Casper допускают форк блоков до наступления консенсуса.
Безопасность консенсуса: асинхронная. Зависит от порогов безопасности, определяемых самими валидаторами.
Живучесть: достигается в частичной синхронизации.

Основное преимущество обеих версий Casper перед Tendermint — это количество валидаторов, которое система может принять одновременно. Правила создания блоков Tendermint требуют финализации, одновременной с созданием блока, поэтому время создания блока должно быть небольшим, что означает ограничение предельного числа валидаторов. Поскольку Casper не требует мгновенной финализации, сеть Эфириума может иметь много большее число валидаторов.