Проверяемые случайные функции в консенсусе

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

Проверяемая случайная функция (VRF), предложенная Микали, Рабином и Вэданом в 1999 году, — это псевдослучайная функция, предоставляющая доказательство корректности. У VRF есть три алгоритма: KeyGen создаёт пару ключей (SK, PK); по SK и alpha вычисляется пара (beta, pi), где beta — результат, а pi — доказательство; проверка по (PK, alpha, beta, pi) возвращает результат действителен или недействителен. Для любого, кто не знает SK, результат beta неотличим от случайного, что обеспечивает псевдослучайность VRF, а доказательство pi невозможно подделать, что обеспечивает уникальность VRF. Размер доказательства равен O(1), то есть постоянен независимо от входных данных.

Наиболее широко применяемая конструкция VRF — ECVRF, описанная в RFC 9381 IETF и основанная на вычислительной сложности задачи дискретного логарифмирования на эллиптических кривых. Имея закрытый ключ x и вход alpha, доказывающая сторона вычисляет хеширование в точку кривой по (PK, alpha), получая H, а затем gamma = x * H — умножение точки на скаляр. Результат VRF вычисляется как beta = keccak(gamma). Доказательство pi использует аргумент с нулевым разглашением типа Шнорра: доказывающая сторона фиксирует случайное k, вычисляет вызов c как хеш от (H, gamma, k*G, k*H), получает ответ s = k - c*x и выдаёт pi = (gamma, c, s). При проверке сверяются уравнения Шнорра и повторно вычисляется beta.

Algorand (Сильвио Микали и др., 2017) первым применил VRF в блокчейн-консенсусе. В каждом раунде каждый валидатор конфиденциально вычисляет VRF(SK, round || seed), получая случайный результат. Результат сравнивается с порогом: если VRF_output < stake_fraction * threshold, валидатор выбирается членом комитета или предложителем блока. Только сам валидатор знает о своём избрании до тех пор, пока не передаст свой блок или голос вместе с доказательством VRF. Такой криптографический самостоятельный отбор устраняет необходимость в публичном избрании лидера и делает Algorand устойчивым к целенаправленным атакам типа «отказ в обслуживании» против заранее известных будущих лидеров.

Cardano Ouroboros Praos (текущая развернутая версия) использует VRF для избрания лидеров слотов. В каждой эпохе из блокчейна выводится новое случайное начальное значение. Оператор каждого пула стейкинга (SPO) вычисляет VRF(SK, slot || epoch_seed) для каждого слота эпохи. Если результат оказывается ниже порога, пропорционального его доле стейка, он становится лидером слота и может создать блок. Доказательство VRF включается в заголовок блока, благодаря чему любой участник может проверить, что SPO был избран законно. Это обеспечивает Cardano доказуемую защиту от адаптивных противников, которые узнают расписание лидеров в середине эпохи.

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

Chainlink VRF предоставляет смарт-контрактам проверяемую случайность как услугу. Контракт-потребитель запрашивает случайность, оплачивая её токенами LINK. Узел-оракул Chainlink хранит пару ключей VRF. Узел вычисляет ECVRF(SK, seed), где seed выводится из хеша блока и предоставленного пользователем счётчика, а затем передаёт (beta, pi) в блокчейн. Контракт-координатор VRF проверяет доказательство и только после этого передаёт случайный результат потребителю. Благодаря этому смарт-контракты получают устойчивую к манипуляциям случайность без необходимости реализовывать в блокчейне собственный маяк VRF — это полезно для выпуска NFT, лотерей и игр.

Протокол Signal использует VXEdDSA (проверяемая X25519 EdDSA) — конструкцию VRF над Curve25519. Когда отправитель создаёт подпись для одноразового предварительного ключа, VRF используется для получения детерминированного, но непредсказуемого одноразового числа из сообщения и ключа отправителя. Это предотвращает повторное использование одноразового числа, которое нарушило бы безопасность EdDSA, и при этом сохраняет возможность проверки подписей. Доказательство VRF позволяет получателю проверить, что одноразовое число было выведено корректно, не давая отправителю выбрать вредоносное значение, способное привести к атакам на восстановление ключа. VXEdDSA демонстрирует, что VRF является универсальным криптографическим инструментом, а не только средством для консенсуса.

Проверяемые функции задержки (VDF) иногда путают с VRF. VDF требует последовательного вычисления как минимум T шагов (свойство временной блокировки) и выдаёт результат с коротким доказательством корректности. VDF используются для уменьшения смещения последнего раскрывающего в RANDAO: запланированный для Ethereum уровень VDF должен сделать любую попытку манипуляции зависимой от предварительного вычисления VDF, которое занимает больше времени, чем окно атаки. VRF обеспечивают мгновенное закрытое вычисление, а VDF — медленное публичное вычисление. Они дополняют друг друга: VDF предотвращают смещение последнего раскрывающего, а VRF — предсказание лидера.

Выбор с помощью VRF обеспечивает важное усиление безопасности против адаптивных противников. В PBFT и Tendermint личность лидера известна заранее (расписание по очереди), что позволяет противнику провести распределённую атаку типа «отказ в обслуживании» против следующего лидера до того, как тот предложит блок. Выбор на основе VRF (Algorand, Cardano) сохраняет личность лидера в тайне до передачи блока — к этому моменту блок уже предложен, поэтому атака типа «отказ в обслуживании» приходит слишком поздно. Это называется адаптивной безопасностью или непредсказуемым избранием лидера. Криптографическое свойство, делающее это возможным, заключается в том, что результат VRF выглядит псевдослучайным для любого, у кого нет закрытого ключа.

Правильная реализация VRF требует учесть несколько важных аспектов. Хеширование в точку кривой должно выполняться с использованием алгоритма с постоянным временем и равномерным распределением (IETF RFC 9380 определяет стандартизированные методы предотвращения утечек по времени). Одноразовое число VRF k в доказательстве должно детерминированно выводиться из (SK, alpha) с использованием RFC 6979 — повторное использование k или применение слабого случайного k раскрывает секретный ключ (та же уязвимость, что и при повторном использовании одноразового числа ECDSA). Размер доказательства для ECVRF-P256-SHA256-TAI составляет 80 байт; для ECVRF-ED25519-SHA512-ELL2 — также 80 байт, поэтому оба варианта подходят для включения в блокчейн. Свойство уникальности VRF гарантирует, что для одной и той же пары (SK, alpha) не существует двух корректных доказательств.

Почему выбор лидера на основе VRF обеспечивает более высокий уровень безопасности, чем циклическое расписание лидеров?

VRF создают псевдослучайные результаты с криптографическими доказательствами корректности, обеспечивая непредсказуемость, неподверженность смещению и публичную проверяемость. ECVRF (RFC 9381) — стандартная конструкция на эллиптических кривых. Algorand использует криптографический самостоятельный отбор с помощью VRF для защиты от адаптивных противников. Cardano Ouroboros Praos использует VRF для избрания лидера каждого слота. Chainlink VRF предоставляет смарт-контрактам проверяемую случайность. VRF дополняют VDF, которые устраняют смещение последнего раскрывающего, и отличаются от RANDAO, использующего накопленные подписи BLS с известной уязвимостью последнего раскрывающего.