Автор оригинальной статьи Джозеф Петровски

Переведено Natali

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

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

1. Кто может предложить следующее изменение?
2. Какой набор изменений является финальным?
3. Что случится, если кто-то нарушит правила?

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

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

Протокол GRANDPA

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

Эта последняя часть важна, потому что она устраняет узкое место, которое мешает другим блокчейн finality gadget. 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. Каждый валидатор ожидает получения достаточного количества предварительных коммитов для формирования подтверждающего сообщения на новой финализированной цепочке.

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

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

Accountable Safety: когда что-то идёт не по плану

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

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

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

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

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

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

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

Как дедушка помогает доступности и валидности GRANDPA Helps Availability and Validity

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

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

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

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

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

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

Чтобы получить доступ к исходной статье, посетите официальный английский блог Polkadot.

Telegram(Ru): t.me/PolkadotRu