🦥 Лучше подождать: что такое Verifiable Delay Functions (VDF)
Хотя это неочевидно, но случайные числа крайне важны в нашей повседневной жизни. Это такое же общественное благо, как газ или электричество. Ведь случайность используется в любых ситуациях, когда нужно честно распределить ресурсы. Случайность с высокой энтропией играет важную роль в процессах голосования и ситуациях, когда требуется сделать независимый выбор. Сотни таких процессов происходят в работе сетей, наших девайсов, при шифровании информации. Случайность может обеспечить безопасность, предотвращая возможность манипулирования конечным решением. С развитием ИИ, IoT и блокчейна, потребность в безопасности и случайных числах становится как никогда острой.
В блокчейне сложно создать идеальный рандомайзер и обнаружить случайное число. А еще сложнее — полностью защитить этот процесс от манипуляций злоумышленников. Поэтому были предложены функции проверяемой задержки, Verifiable Delay Functions или VDF.
Введение в понятие функций проверяемой задержки (VDF)
Протокол VDF обеспечивает общедоступный, публично проверяемый, беспристрастный и непредсказуемый источник случайности. Даже в случае, когда процессор использует параллельные вычисления, VDF может быть выполнена только на одном ядре процессора. На выходе функция дает уникальный результат, который может быть быстро и легко проверен участниками сети. Проверка результата может быть выполнена параллельно на двух ядрах.
Использование этой функции не требует честности от большинства участников в сети, вместо этого нужен лишь один честный участник. Параллельные вычисления не ускорят VDF, но при этом проверка результата происходит быстро для всех участников. По задумке VDF должен оставаться безопасным даже перед лицом злоумышленника, способного выполнить полиномиально ограниченное предварительное вычисление.
В исследовании говорится, что обычно разработчики допускают ошибки, используя значения будущих хешей блоков, сложность блоков или временные метки для получения случайного значения. Эти методы уязвимы для манипуляций со стороны майнеров.
Они уязвимы еще потому, что каждый алгоритм — функционально детерминирован, это значит, что даже для получения случайного значения он стремится следовать запрограммированным правилам. Именно поэтому результат часто бывает предсказуем. Большинство генераторов случайных чисел полагаются на ввод заранее заготовленного датасета из внешних источников.
Представим, что запускаем цифровую лотерею, в которой пользователи угадывают, будет ли хэш следующего блока четным или нечетным. Майнер может поспорить, что блок четный, и если следующий блок окажется нечетным, он его просто сбросит. Это увеличит вероятность выигрыша майнера. Это один из множества примеров, когда случайные значения могут быть фальсифицированы. Все они страдают от проблемы, в которой наблюдателям легко вычислить, как их выбор повлияет на случайность, генерируемую в цепочке.
Другая проблема появляется, когда нужно выбрать валидаторов в протоколе Proof-of-Stake. Способность майнера влиять или предсказывать случайность позволяет ему влиять на выбор. Есть различные методы решения этой проблемы. Например, решение Ouroboros для обмена секретной информацией. Но в этом случае должно быть честное большинство голосов. В этом случае, злоумышленникам легко увидеть, как различные входные данные влияют на результат генератора псевдослучайных чисел. Это привело авторов исследования к созданию проверяемых функций задержки (VDF).
Эти специальные «медленные» хеш-функции используются в для создания надежного маяка случайности: службы, производящей публично проверяемые случайные числа, которые гарантированно будут беспристрастными и непредсказуемыми. Эти маяки случайности являются ценным инструментом в децентрализованной среде.
Так что такое VDF?
Verifiable Delay Function (VDF) или функция проверяемой задержки — это функция, для вычисления которой требуется длительное время. Но как только решение найдено, любой может довольно быстро проверить правильность вычисления за установленный период времени. VDF можно представить как временную задержку, наложенную на выход очередного блока. Именно эта задержка защищает выходные данные от манипуляций злоумышленников, так как транзакции будут завершены до того, как кто-либо сможет завершить вычисление VDF. Проверяемая функция задержки является криптографическим доказательством того, что прошло реальное время. Но понятие времени в самой функции не коррелируется со временем реального мира. В этой функции, это скорее количество последовательных вычислений, которые нужно сделать компьютеру, чтобы доказать функцию.
Решение этой функции требует сделать серию последовательных вычислений. Слово «последовательные» тут подразумевает многократное использование хеша от числа. Это означает, что доказывающий не может просто покупать больше машин, чтобы работать быстрее, в отличие от сети Биткоина и PoW. Для вычисления VDF требуется реальное время. Доказывающий должен решить задачу x T раз и также должен предоставить доказательство того, что это было выполнено правильно.
Эволюция функций с временной задержкой
Криптографы Ривест, Шамир и Вагнер в 1996 году ввели использование временных блокировок (time locks) для шифрования данных, которые могут быть дешифрованы только в заранее определенное время в будущем. Это был первый чувствительный ко времени криптографический примитив, учитывающий параллельную мощность возможных злоумышленников. Другие примитивы с задержкой времени появились в разных контекстах: Беллар и Голдвассер предложили временные капсулы для депонирования ключей. Боне и Наор ввели привязанные по времени обязательства с помощью процедуры определенного времени выполнения. Совсем недавно понятие медленной хеш-функции было введено как инструмент, обеспечивающий доверие к генерации общедоступных случайных чисел.
В настоящее время существует три варианта конструкции, удовлетворяющие требованиям VDF. У каждого есть свои потенциальные недостатки. Впервые понятие VDF появилось в исследовании группы криптографов из Стэнфордского и Нью-Йоркского университетов. Однако оценка этого VDF требует довольно большого объема параллельной обработки, в результате чего авторы называют его «слабым VDF».
Позже Петрзак и Весоловски независимо друг от друга пришли к чрезвычайно похожим конструкциям, основанным на повторном возведении в квадрат в группах неизвестного порядка. Схема Весоловски предполагает существование групп, которые удовлетворяют так называемому предположению адаптивного корня, которое недостаточно хорошо изучено в математической литературе. В этой области есть много других открытых проблем, включая создание квантово-устойчивых VDF и потенциальную возможность для ASIC разрушить гарантии безопасности конструкций VDF на практике.
Как работает VDF
Теперь будет немного сложно, но важно следить за значениями =)
VDF — это тройная функция, которая включает в себя настройку, оценку и проверку.
Настройка (Setup (λ, t) → pp = (ek, vk) — это рандомизированный алгоритм, который принимает в качестве входных данных параметр безопасности λ и сложность t, а возвращает ключ оценки ek и ключ проверки vk. Также тут нужно учитывать общедоступные параметры, такие как пространство ввода X и пространство вывода Y. Для безопасности сложность t ограничена субэкспоненциальным размером в λ.
Оценка (Eval (ek, x), заданная входными данными X и ключом оценки ek, дает результат Y и доказательство π. Eval может использовать случайные биты для генерации доказательства π, но не для вычисления y.
Проверка (Verify (vk, x, y, π) учитывает ключ проверки и доказательство Да/Нет.
Алгоритм Verify должен выполняться за полиномиальное время от log t и λ. Verify намного быстрее, чем Eval. Учитывая желаемый параметр задержки t, общедоступные параметры размещаются в блокчейне, затем для блока b значение маяка определяется как r, где (r, π) = Eval (ek, b). Таким образом любой может проверить правильность, запустив Verify (vk, b, r, π).
Кроме этого VDF должна удовлетворять значения корректности, надежности и последовательности.
Корректность и надежность. Каждый вывод Eval должен быть одобрен Verify. Выход Y для входа X уникален, потому что Eval вычисляет детерминированную функцию на X. Доказательство не обязательно должно быть уникальным, но оно обязательно должно быть корректным.
Последовательность. Свойство безопасности, необходимое для VDF, называется σ-последовательностью. Она отвечает за то, чтобы ни один злоумышленник не мог вычислить выход для вычисления за параллельное время σ (t) <t, даже при наличии «многих» параллельных процессоров и после большого количества предварительных вычислений.
В чем польза VDF
Маяки случайностей. VDF полезны для построения маяков случайности в таких процессах, как предсказание цен на акции или, например, в блокчейнах с Proof-of-Work. В основе безопасности блокчейнов с подтверждением работы лежит убеждение, что эти решения имеют высокую вычислительную минимальную энтропию. Однако, подобно потенциальному манипулированию ценами на активы со стороны трейдеров, могущественные майнеры потенциально могут манипулировать результатами, отказываясь размещать блоки. Когда используется VDF с достаточно большой задержкой, майнеры не смогут определить результат маяка из данного блока до того, как он станет устаревшим.
Ресурсоэффективные блокчейны. Блокчейн Биткоина на Proof-of-Work довольно энергозатратен. Поэтому были разработаны более энергоэффективные, например, Proof-of-Stake, Proof-of-Space и Proof-of-Storage. Однако ресурсоэффективный майнинг страдает от симуляционных атак. Интуитивно понятно, поскольку майнинг не требует больших вычислительных затрат, майнеры могут легко попытаться создать множество отдельных форков. Один из методов противодействия симуляционным атакам — использовать маяк случайности для выбора новых мастернод через равные промежутки времени, при этом вероятность стать мастернодой зависит от качества доказательств. Ряд существующих блокчейнов уже создает маяки из таких инструментов, как проверяемые случайные функции, проверяемый обмен секретами или детерминированные пороговые сигнатуры. Но безопасность этих маяков требует честного большинства, не вступившего в сговор. С помощью лотереи на основе VDF, как описано выше, это потенциально может быть улучшено до участия любой честной стороны.
Proof-of-replication (Доказательство репликации). Еще одно многообещающее применение VDF — это доказательства репликации, особый тип доказательства хранения данных, который требует, чтобы доказывающая сторона выделяла уникальное хранилище, даже если данные доступны из другого источника. Это может быть использовано для доказательства того, что хранится несколько реплик одного и того же файла. Целью доказательства репликации является проверка того, что данный сервер хранит уникальную копию некоторых данных, которые могут быть общедоступными. Эквивалентная концепция доказательства репликации была впервые представлена Серджио Демианом Лернером в 2014 году под названием «доказательство репликации».
Определение ложных форков. Все известные системы Proof-of-Stake уязвимы для долгосрочных форков из-за постфактум неправильного поведения заинтересованных сторон. В любой момент времени текущие заинтересованные стороны в системе получают право голоса, пропорционально их доле в системе. Предполагается, что большинство участников будут честны, потому что стороны заинтересованы в том, чтобы система работала правильно. Но они могут вступить в сговор, чтобы создать длинную альтернативную историю системы. Этого можно избежать с помощью внешнего механизма меток времени, который может доказать пользователям, что подлинная история системы намного старше. VDF могут предоставить вычислительное свидетельство того, что данная версия системы старше (и, следовательно, подлинная), доказывая, что длительное вычисление VDF было выполнено на подлинной истории сразу после точки расхождения с мошеннической историей.
Некоторые примеры использования VDF
VDF играют ключевую роль в конструкции блокчейнов Ethereum Foundation, Protocol Labs, Chia, Filecoin, Tezos, NEAR, ThunderCore и других. По информации CoinDesk, есть еще 11 блокчейн-компаний, которые проводят исследования технологии VDF, и каждая имеет свои собственные уникальные разработки.
Ethereum Foundation выделит $15 млн. на разработку «функции проверяемой задержки» (VDF). VDF предназначена для использования ожидаемой системе под названием Serenity. Виталик Бутерин в своем блоге написал пост про VDF, где он обозначил, что У VDF есть следующие преимущества:
- по сравнению с RANDAO и подобными схемами ими нельзя манипулировать,
- по сравнению с пороговыми сигнатурами BLS и аналогичными VRF они не зависят от какой-либо конкретной части узлов, находящихся в сети,
- не требуют сложной процедуры настройки.
В Solana заявляют, что разработали уникальный протокол «Proof of History». Он использует VDF для установления единой неоспоримой правды о времени, когда произошло конкретное событие.Proof of History (PoH) работает до консенсуса. Устраняя нагрузку на сеть, связанную с установлением времени в рамках консенсуса, Solana достигла скорости транзакций более 190 000 в секунду на пиковой нагрузке в тестовой сети.
Сеть Chia объявили открытый конкурс по разработке более защищенного протокола VDF с призовым фондом на $100 000. Они используют протокол проверки временем с функцией VDF. Алгоритм консенсуса Chia основан на VDF в течение периодов времени, называемых суб-слотами, которые периодически корректируются, чтобы в сумме составлять около 10 минут. Периодически запускаются испытания, которые представляют своего рода мини-лотерею для нод.
Использованы материалы:
пост Виталика Бутерина про VDF
Introduction to Verifiable Delay Functions (VDFs)
Автор: Надя Осмокеску
Cyber Academy — образовательная платформа для блокчейн-разработчиков. Присоединяйтесь к нам
Поддержите нас на Gitcoin ✨
Анонсы | Website | Twitter | Телеграм-чат | GitHub | Facebook | Linkedin
