Верификация мастер-блока

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

Верификатор и сессии

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

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

Порог подтверждения

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

Повторный публичный ключ в наборе валидаторов схлопывается в одну запись ещё до подсчёта суммы, так что дублирование веса не даёт. Арифметика подсчёта защищена от переполнения: если суммарный вес набора превышает половину диапазона используемого целочисленного типа, умножение насыщается. Порог тогда фиксируется на уровне, который остаётся достижимым, но настоящих двух третей уже не составляет — в пределе, при весе набора около верхней границы типа, вдвое ниже них. На весах реального набора валидаторов такая ситуация не возникает.

Самопроверка и собственная подпись

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

Своя подпись при этом не обменивается по сети, а подставляется сразу: в начале работы по блоку в накопленный результат сразу кладётся пара «свой открытый ключ — своя подпись», а накопленный вес стартует со своего собственного веса.

Подписывает и проверяет узел не сами байты блока, а фиксированный буфер данных для подписи: четырёхбайтовый тег-разделитель, за ним корневой хеш и файловый хеш идентификатора блока — 68 байт, из которых получается 64-байтовая подпись ed25519. Тег отделяет эти данные от подписей других механизмов протокола, использующих тот же ключ. Ни номер блока, ни его шард, ни содержимое тела блока в эти данные не входят, но раз в них входят оба хеша идентификатора, подпись удостоверяет именно конкретную битовую сборку блока: два разных кандидата на один и тот же номер дают разные хеши и, значит, несовместимые подписи. Поэтому если локально собранный кандидат разошёлся с версией остальных валидаторов, узлу попросту не набрать для него порог: подписи, годные для чужой сборки блока, к этой не подойдут.

Приватный оверлей сессии

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

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

Обмен подписями

Внутри приватного оверлея сессии валидаторы обмениваются подписями одним симметричным запросом: отправитель передаёт номер блока в шарде сессии и свою подпись, а в ответ получает либо подпись отвечающего, либо отметку, что подпись принята и будет проверена позже. Отдельного запроса «пришли мне подпись» в протоколе нет — не имея своей подписи, спросить чужую нельзя.

Получив такой запрос, сессия смотрит, что ей известно о номере блока:

• сессия отменена — запрос остаётся без ответа;
• блок с этим номером уже верифицируется: если ему ещё нужны подписи, присланная подпись проверяется (раздел «Приём и проверка подписи»), и при успешном приёме отправителю возвращается собственная подпись узла по этому блоку. Если подписей уже достаточно, присланная подпись просто игнорируется, но ответ всё равно отправляется;
• блок ещё не дошёл до верификации, но на его номер заранее выделено место в кэше (раздел «Слоты кэша на будущие блоки») — подпись сохраняется в кэше без криптографической проверки, с перезаписью прежнего значения, если оно там уже было;
• ни того, ни другого — запрос отклоняется.

Отменённая сессия, неизвестный отправитель, невалидная подпись, отсутствие места в кэше — любой такой отказ выглядит для отправителя не как ошибка протокола, а как молчание: сессия просто не отвечает.

Приём и проверка подписи

Новая чужая подпись — та, что пришла во входящем запросе обмена по уже известному блоку, либо та, что раздобыла собственная задача опроса узла (раздел «Получение недостающих подписей» ниже). Любая из них попадает в запись блока через одну и ту же проверку, и это единственная точка приёма новой подписи в уже открытую запись.

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

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

Занявшая место подпись сразу добавляет вес валидатора к накопленной сумме. Если сумма достигла порога, запись блока помечается подтверждённой: по этому признаку обработчик входящих запросов дальше отличает блок, которому подписи ещё нужны, от того, которому уже достаточно (раздел «Обмен подписями»).

Слоты кэша на будущие блоки

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

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

Переиспользование накопленных подписей

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

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

Если слота кэша нет, готовится пустой набор — по слоту на каждого чужого валидатора набора, без единой уже вставленной подписи.

Начальный набор в обоих случаях уже содержит собственную подпись узла и её вес (раздел «Самопроверка и собственная подпись»), а если набранного веса, включая переиспользованные из кэша подписи, уже достаточно, верификация блока обходится вовсе без сетевого обмена: порог считается достигнутым ещё на этом шаге.

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

Получение недостающих подписей

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

Иначе задача одновременно ждёт подписи, которую вот-вот принесёт входящий запрос от этого же валидатора, и результата собственного цикла опроса. Цикл опроса берёт разрешение общего на блок семафора, ограниченного параметром max_parallel_requests, отправляет тот же запрос обмена подписями со своей подписью и ждёт ответа не дольше таймаута, заданного параметром exchange_signatures_timeout. Получив подпись в ответе, цикл опроса обрывается. Отметка «принято в кэш», сетевая ошибка, таймаут — любой другой исход отпускает разрешение семафора, и задача засыпает на паузу, растущую по экспоненте от exchange_signatures_backoff.min_interval до потолка exchange_signatures_backoff.max_interval, прежде чем повторить попытку. Предела числа попыток нет: задача либо получит валидную подпись, либо будет прервана вместе со всей верификацией блока или сессией целиком.

Полученная любым из двух путей подпись проходит уже описанный порядок приёма (раздел «Приём и проверка подписи»). Если в записи уже лежит другое значение от того же валидатора, задача перечитывает сохранённое и завершается им. Если подпись оказывается невалидной, задача засыпает на паузу failed_exchange_interval и повторяет весь цикл заново, с задержкой, вновь сброшенной до начального значения.

Гонка «слот против опроса» экономит сетевые обращения: при N валидаторах в наборе каждый опрашивает каждого, и почти всегда подпись нужного валидатора приходит и сама, во входящем запросе, раньше, чем до неё доходит очередь исходящего опроса.

Поток верификации блока целиком

Верификация одного номера блока — это последовательность шагов, в которую складываются самопроверка, кэш, обмен подписями и подсчёт веса.

Сначала — быстрая проверка: если номер блока уже не новее ранее отменённой границы сессии (раздел «Отмена сессий и слотов»), верификация сразу завершается без результата. Иначе нижняя граница сессии поднимается до этого номера, и вслед за ней сдвигается вперёд всё окно слотов кэша (раздел «Слоты кэша на будущие блоки»).

Дальше из слота кэша на этот номер, если он есть, или с чистого листа строится начальный набор подписей (раздел «Переиспользование накопленных подписей»), и этот набор регистрируется как запись блока в сессии. Начать верификацию одного и того же номера дважды нельзя: повторная попытка регистрации заканчивается ошибкой. Отмена сессии проверяется ещё раз, уже после регистрации: если она успела сработать, запись убирается и верификация завершается без результата. Слот кэша на этот номер удаляется только теперь, строго после регистрации записи, чтобы входящий обмен ни на мгновение не остался без места для входящей подписи.

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

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

Отмена сессий и слотов

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

Найденная сессия получает частичную отмену: граница отменённых номеров и нижняя граница сессии сдвигаются вперёд, до указанного блока включительно. Это та же нижняя граница, что двигает вперёд окно слотов кэша, поэтому новые слоты на уже отменённые номера больше не создаются, а существующие слоты кэша до этой границы удаляются. У всех уже открытых записей блоков с такими номерами останавливается сбор подписей, если он ещё шёл. Но сама запись остаётся в памяти ещё некоторое число блоков, заданное параметром old_blocks_to_keep конфигурации верификатора, и по-прежнему отвечает на входящие запросы собственной подписью узла (раздел «Обмен подписями»). Это даёт время отстающим валидаторам донабрать подписи по уже пройденному блоку. Только когда граница отмены уходит от номера записи дальше этого запаса, запись удаляется по-настоящему.

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

Подписи в доказательстве мастер-блока

Собранные подписи вместе с суммарным весом уезжают в доказательство блока — но только для мастер-блока: у блока рабочей цепочки поле подписей в доказательстве всегда пусто.

В доказательстве подписи хранятся не как сырой набор пар «валидатор, подпись», а как отдельная структура. В неё входят короткий хеш набора валидаторов, идентификатор набора, число собранных подписей, суммарный собранный вес и сами подписи в виде отображения. Хеш и идентификатор набора валидаторов взяты из заголовка уже собранного блока, а не из идентификатора сессии верификации. Подписи в этом отображении пронумерованы заново при сохранении, а не индексами валидаторов в наборе. Раз в собранный набор подписей входит и собственная подпись узла (раздел «Самопроверка и собственная подпись»), она сохраняется в доказательстве наравне с чужими.

Суммарный вес в доказательстве — это вес фактически собравшихся подписей, а не сам порог: он может быть выше порога и в общем случае различается у разных узлов сети, потому что состав собранных подписей у них разный (раздел «Поток верификации блока целиком»).

Конфигурация

Верификатор настраивается разделом validator конфигурации узла.