Консенсус в Polkadot, Часть 2: GRANDPA

Это вторая часть нашей серии статей о консенсусе в Polkadot. Читайте Часть 1 для введения.

Во введении было сказано, что алгоритм консенсуса помогает сети компьютеров ответить на три вопроса. GRANDPA относится ко второму.

1. Кто может предложить следующее изменение?

2. Какой набор изменений является финальным?

3. Что случится, если кто-то нарушит правила?

GRANDPA это гаджет финализации в Polkadot. Его цель — детерминистически выбрать каноническую цепочку. Другими словами, GRANDPA решает, какой набор изменений является финальным. Он не создает блоки самостоятельно; вместо этого валидаторы GRANDPA импортируют блоки из другого модуля производителя блоков (который мы обсудим в Части 3).

Одно из преимуществ разделения создания блоков и безопасности [1],  помимо того, что это в целом правильная архитектура, заключается в том, что GRANDPA не накладывает много ограничений на блоки, которые он импортирует. GRANDPA требует, чтобы система производства блоков имела конечную безопасность, следовала правилу выбора форков GRANDPA, и чтобы заголовок блока имел указатель на его родительский блок. Это третье свойство гарантирует, что лёгкие клиенты могут подключаться к цепочке.

Протокол GRANDPA

GRANDPA стоит особняком от других Byzantine fault-tolerant (BFT) алгоритмов, потому что валидаторы голосуют за цепочки, а не блоки. Протокол применяет голоса транзитивно, и алгоритм GRANDPA находит самый большой номер блока с достаточным количеством голосов, чтобы его считать окончательным. Этот процесс позволяет завершить несколько блоков в один раунд.

Эта последняя часть важна, потому что она устраняет узкое место, которое мешает гаджетам финализации в других блокчейнах. GRANDPA, как и другие производные PBFT, имеет сложность O(n²). То есть, если вы удвоите количество узлов, вам придется отправить в четыре раза больше сообщений. Консенсусные системы, которые делают производство блоков частью процесса финализации, вынуждают отправлять эти сообщения для каждого отдельного блока. Выделив создание блоков в отдельный модуль, мы можем производить блоки гораздо более эффективным способом (O(n) для BABE), и авершать сразу несколько в одном раунде.

Чтобы увидеть пример этого, посмотрите на эти сообщения логов от ноды Kusama:

Idle (24 peers), best: #664257 (0x706c…76b7), finalized #664253 (0xe4ab…4d2a) Imported #664258 (0xee71…6321) Idle (24 peers), best: #664258 (0xee71…6321), **finalized #664256 **(0x809a…a5d8)

Обратите внимание, что в одном раунде GRANDPA финализировал три блока (664,254 - 664,256).

Это пример того, как GRANDPA может завершить несколько блоков в одном раунде, как показано в сообщениях лога ранее. Темно-серые блоки слева уже были финализированы, и валидаторы (серые точки справа) прислали голоса для нового раунда. Еще три блока получили большинство и были финализированы.

Раунд GRANDPA

Участники голосования выполняют следующие действия для финализации новых блоков:

1. Узел, назначенный в качестве "основного", транслирует новый блок, который, по его мнению, может быть финализирован из предыдущего раунда.

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

3. Каждый валидатор проверяет новый блок, который может быть финализирован на основе набора предварительных голосов. Если набор предварительных голосов расширяет последнюю финализированную цепочку, то каждый валидатор делает “предварительный коммит” к этой цепочке.

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

Тонкое, но важное отличие от других византийских отказоустойчивых алгоритмов (таких как PBFT и Hotstuff) заключается в том, что на критическом пути нет изменения представления. Хотя основной (primary) изменяется каждый раунд, это изменение представления предназначено только для начала нового раунда в условиях асинхронной сети, так что в частично синхронных сетях протокол всегда будет продвигаться вперед, даже без первичного назначения .

Шаги в протоколе являются завершенными, когда они имеют более двух третей предварительных голосов или пре-коммитов от валидаторов. Чтобы иметь детерминированную финальность, число голосов в наборе валидаторов должно быть ограничено. Это отличается от цепочек с вероятностной финальностью, которые могут иметь неограниченное количество валидаторов. Метод выбора набора голосующих — это логика, которая определяется вне протокола GRANDPA (читайте в Части 4).

GRANDPA поддерживает взвешенное голосование. Например, вы можете реализовать GRANDPA в своей цепочке, где валидаторы с большим количеством стейка получают больше голосов. Однако в Polkadot все валидаторы имеют один голос. Это было экономическим решением, чтобы предотвратить получение малому количеству узлов большой доли сети.

Ответственная Безопасность (accountable safety): когда что-то идёт не по плану

GRANDPA имеет функцию под названием accountable safety, чтобы привлечь валидаторов к ответственности за нарушения безопасности. Нарушение безопасности происходит, когда финализируются два блока, которые находятся в разных цепочках. Ответственная безопасность — это как расследование после несчастного случая.

Но как две конфликтующие цепи достигают финальности? BFT системы всегда строятся на требовании, чтобы максимальное число неисправных валидаторов составляло некоторую долю , в нашем случае треть ,  от общего числа валидаторов. Чтобы финализировать две конфликтующие цепочки, набор валидаторов не соответствуют этому требованию; по крайней мере одна треть валидаторов проголосовала за эти две цепочки.

В этом примере имеется 10 валидаторов, то есть 3-это максимальное количество “неисправных” валидаторов, которое может выдержать система (f = (10-1) / 3). С 4 “неисправными” валидаторами (красный) и разделением сети каждая группа честных валидаторов (синий) может думать, что финализированы различные блоки.

Голосование за две конфликтующие цепочки называется Двусмысленностью (equivocation). Двусмысленность является слабостью BFT систем. В GRANDPA мы можем это обнаружить.

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

Если это так, то мы задаем второй вопрос: какие предварительные голоса в первом раунде вы видели? Мы, по сути, просим их пожаловаться на других валидаторов и раскрыть все голоса, которые они получили от коллег. Таким образом вы обнаружите валидаторов, которые голосовали за две конфликтующие цепочки. Предположительно, они будут жестоко наказаны, но за это ответственна логика цепочки, а не консенсуса.

Если произойдет сбой безопасности, то сеть вынуждена будет инициировать хардфорк, чтобы выбрать, какая из конфликтующих цепей является финальной. Благодаря ответственной безопасности Polkadot может гарантировать, что валидаторы, совершившие атаку, будут наказаны, и не останутся в списке валидаторов.

Как GRANDPA помогает доступности и валидности

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

Idle (24 peers), best: #664258 (0xee71…6321), finalized #664256 (0x809a…a5d8)

Системы интероперабельных блокчейнов, включая Polkadot, имеют проблему доступности данных. Представьте себе, что один сборщик передает блок валидатору, но ни один из других сборщиков парачейна его не видел. Что произойдет, если сборщик, отправивший блок, отключится от сети? Валидаторы несут ответственность за хранение полных блоков в течение определенного периода времени, так что любой сборщик парачейна может запросить блок.

Валидаторы должны проверять блоки перед голосованием за них, но мы хотим убедиться, что они это делают. Узлы Polkadot, которые мы называем рыбаками, необходимы, чтобы проверять блоки и сообщать о любом некорректном поведении валидатора, например, предложении недопустимого блока для включения в релейную цепь (Relay Chain).

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

Мы обсудили, как принять решение о канонической цепочке, но откуда берутся эти варианты цепочек? Вот тут-то и появляется BABE. Читайте в Части 3 этой серии.

Читайте часть 3: BABE.

[1] Я предпочитаю термин «безопасность», а не «окончательность», потому что завершенные блоки не являются окончательными с точки зрения законов физики. Они окончательные, потому что так сказал GRANPA. Я предпочитаю слово «безопасный», от которого можно ожидать более разумных ожиданий, чем «окончательный». Например, мы считаем безопасным авиаперелет. Но все мы знаем, что иногда авиалайнер терпит крушение. Кроме того, когда самолет все-таки терпит крушение, у нас есть процесс расследования и обращения в суд, чтобы привлечь к ответственности определенные стороны.

Данная статья является переводом на русский язык официальной статьи с веб-сайта Polkadot, ранее опубликованный Natali.

Original published in December 18, 2019, "Polkadot Consensus Part 2: GRANDPA"

by Joe Petrowski Research Analyst, Parity Technologies”

Мы также рекомендуем ознакомиться c lightpaper Polkadot на русском языке.