Консенсус в Polkadot, Часть 3: BABE

Это третья часть нашей серии статей о консенсусе в Polkadot. Читайте Часть 1 в качестве введения и Часть 2, рассказывающую о GRANDPA.

Blind Assignment for Blockchain Extension (BABE) — это механизм производства блоков, который был основан на Ouroboros Praos, еще одним proof-of-stake протоколом. Он может быть использован сам по себе, потому что он обеспечивает вероятностную финальность, или он может быть соединен с гаджетом финализации, таким как GRANDPA.

BABE — это алгоритм на основе слотов. Он разделен на эпохи, причем каждая эпоха разбивается на слоты. В Polkadot каждый слот длится шесть секунд, это расчетное время блока. BABE выбирает автора (или нескольких), чтобы создать блок в каждом слоте.

Время в BABE разделено на эпохи. Каждая эпоха — это набор слотов.

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

Каждый слот может иметь первичного и вторичного автора (или “лидера слота”). Первичные лидеры слотов назначаются случайным образом. Поскольку функция является случайной, иногда появляются слоты без лидера. Чтобы обеспечить постоянное время создания блока, BABE использует циклическую систему для назначения вторичных лидеров слотов.

Первичные лидеры слотов

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

VRF генерирует псевдослучайное число вместе с доказательством того, что оно было корректно сгенерировано. Такие функции принимают некоторые параметры, включая закрытый ключ, в качестве входных данных. Наша VRF принимает случайный сид эпохи (заранее согласованный всеми нодами), номер слота и приватный ключ автора. Поскольку никакие два узла не имеют одного и того же приватного ключа, каждый узел может генерировать уникальное псевдослучайное значение для каждого слота.

Каждый автор вычисляет значение VRF для каждого слота в эпоху. Если значение VRF находится ниже некоторого согласованного порога, валидатор имеет право создать блок в этом слоте. В результате могут появиться слоты без первичного лидера, а также слоты с несколькими первичными лидерами. Позже мы обсудим, что делать в данных случаях.

VRF в BABE принимает на вход сид эпохи, номер слота и приватный ключ валидатора и выдает значение для каждого слота в эпохе. Когда значение VRF автора блока находятся ниже порогового значения сети, он создает блок в качестве первичного лидера для этого слота.

Вторичные лидеры слотов

Чтобы избавиться от пустых слотов, BABE использует запасной вариант. В каждом слоте есть второстепенный лидер. Если никто не заявляет, что он является первичным лидером в начале слота, то вторичный становится автором блока. Этот резервный вариант гарантирует, что каждый слот имеет автора блока и помогает гарантировать постоянное время создания блоков.

Соединяем BABE и GRANDPA

Итак, у нас есть GRANDPA, финализирующий цепочки, и BABE, создающий новые блоки. Некоторые из цепочек BABE могут иметь форки, так как один слот может иметь несколько лидеров.

Первое правило выбора основной цепочки простое: BABE должен удлинять цепочку, которая была финализирована GRANDPA. Это одно из требований, чтобы использовать GRANDPA.

Второе, более тонкое требование для использования GRANDPA состоит в том, что алгоритм создания блоков должен иметь способ выбора “лучшей” цепочки. Это свойство приводит к тому, что BABE имеет вероятностную финализацию (в принципе, вы можете использовать его и без GRANDPA).

Самая “лучшая” цепочка в BABE — это та, в которой больше всего блоков создано первичными лидерами.

Пример правила выбора алгоритмом BABE лучшей цепочки.

Форки — обычное дело в BABE. В статье о GRANPA упоминалось, что сложность создания блоков O(n), это означает, что автор просто должен транслировать свой блок всем, но не нуждается в том, чтобы каждый отправлял сообщение каждому (как в GRANPA). Таким образом, не все будут иметь одинаковое представление о нефинализированной цепочке (желтые блоки на изображении).

Такая система позволяет нам эффективно создавать блоки и позволяет GRANDPA финализировать сразу несколько из них.

Постойте, а как же часы?

Мы назначаем слоты на основе периодов времени, но у нас нет единого представления о времени. У каждого компьютера есть свои часы. Мы не можем использовать централизованную службу времени (называемую NTP-серверами), потому что это единая точка для атаки. Злоумышленник может атаковать сервер NTP, либо отключив его, либо взяв под свой контроль, чтобы подстроить различные атаки, например, отправляя разное время на разные узлы.

Если вам интересно, рассмотрите следующий сценарий:

Я получаю от вас сообщение: “сейчас 8:42:00.” Мои часы показывают 8:42:03. Возможно одно из трех:

Наши часы синхронизированы, и это просто доставка сообщения заняла 3 секунды.

На самом деле доставка заняла 1 секунду. А наши часы отстают от синхронизации на 2 секунды.

Мне пришли недостоверные данные, и это неверное время.

Теперь представьте, что я получаю это сообщение, когда мои часы показывают 8:41:59. Если я поверю, что вы честно говорите мне о вашем времени, то я знаю, что мы не синхронизированы и что я должен перевести свои часы вперед. Я до сих пор не знаю, сколько времени потребовалось для доставки сообщения по сети, поэтому я не знаю, насколько сильно мы рассинхронизировались.

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

Авторы блоков в BABE используют время приема блоков для создания некого шаблона об общем сетевом времени. Они аппроксимируют время приема блока на будущее, основываясь на времени слота, чтобы определить, когда они должны создать блок.

До сих пор мы обсуждали, как создаются блоки (BABE) и как они финализируются (GRANDPA). Следующая проблема, которую мы должны решить, заключается в том, как заставить людей правильно следовать этим протоколам? В заключительной части этой серии мы обсудим, как среда выполнения стимулирует участников на корректное поведение для BABE и GRANDPA и наказания за ошибки.

Читайте часть 3: BABE: о безопасности.

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

Original published in December 18, 2019, "Polkadot Consensus Part 3: BABE"

by Joe Petrowski Research Analyst, Parity Technologies”

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

Присоединяйтесь в Telegram чат "Subsocial на русском", общайтесь и получайте самые свежие новости о SubSocial