Служба VDF на основе STARK

Введение

Мы рады сообщить, что VeeDo — наша служба проверки функции задержки на основе STARK (VDF) — теперь работает в основной сети . Этот пост задуман как введение в VeeDo. Он начинается с набросков строительных блоков VeeDo. Затем мы описываем наше первое приложение для VeeDo, PoC для маяка случайности, и сравниваем наше решение с существующими решениями случайности. Наконец, мы обсудим некоторые будущие приложения и бизнес-модели, которые мы рассматриваем для VeeDo.

Криптографические строительные блоки VeeDo

Верифицируемые функции задержки (VDF) были впервые предложены в работе Boneh et al. Как следует из их названия, VDF — это функции, которые используют вычисления для обеспечения задержки, временной задержки.

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

VDF, который использует VeeDo, представляет собой функцию f , которая:

1. Медленно вычислять
2. Быстрое инвертирование (т. е. вычисление f ^ (-1) выполняется быстро)
3. Можно предоставить доказательство π для вычислительной целостности f таким образом, чтобы обойти необходимость повторения медленного вычисления функции f .

Для достижения вышеуказанных свойств VDF VeeDo комбинирует функцию задержки f с другим криптографическим примитивом — протоколом STARK.

Функция задержки

Функция задержки f получает на вход пару: элемент поля s в качестве начального значения и количество итераций n . Он запускает один цикл для n итераций, начиная с этого семени. (Число итераций, n , значительно превышающее миллион, является параметром, который можно настроить для достижения желаемой задержки). Каждая итерация цикла также проста: найти корень полинома низкой степени (кубического) по модулю простого числа p , которое является «большим», в VeeDo PoC, 126-битное простое число. Шаг поиска корня примерно в 42 раза сложнее, чем обратное направление вычисления кубического многочлена.

Протокол STARK

Верифицируемое свойство VDF , т. е. его полилогарифмическая сложность проверки, достигается протоколом STARK. После того, как вычисление f (s, n) выполнено, три элемента <s, n, f (s, n)> отправляются в STARK Prover. Затем доказывающий доказывает, что вычисления верны. И вычисление f на s , и генерация доказательства выполняются вне цепочки. < s, n , f (s, n)> вместе с доказательством затем отправляются в Verifier, смарт-контракт, работающий в сети. Эффективный STARK Verifier работает за время, полилогарифмическое относительно n (длина вычисления f ).

Обратите внимание, что для небольших задержек может быть достаточно наивного метода проверки вычисления n итераций f ^ (-1). Роль доказательства STARK здесь заключается в том, чтобы экспоненциально сжать наивный процесс проверки (от n до poly-log(n)), когда необходимы большие задержки.

Наш анализ указывает на еще одно важное свойство VeeDo VDF: это аппаратная устойчивость . При вычислении VDF GPU и FPGA не имеют преимущества перед стандартным 64-битным CPU с точки зрения задержки. Более того, у нас есть детальное понимание пределов улучшения, которые можно ожидать от специального ASIC для этого вычисления. Подробный анализ этих аспектов будет включен в официальный документ, который мы опубликуем на VeeDo.

Первое: случайность

Фон

Первое приложение, которое мы собираемся решить с помощью VeeDo, — это ненадежная и беспристрастная случайность в Ethereum. В настоящее время наиболее широко используемым источником случайности Ethereum является хэш блока. Его используют более 3500 смарт-контрактов. Случайность блочного хэша проста в использовании, доступна (генерируется каждый блок) и недорога. Эти самые свойства также облегчают манипулирование случайностью хеш-блоков, и исследователи естественным образом продемонстрировали это (см., например, Bunz et al.). Двумя другими источниками случайности являются служба случайности Chainlink на основе оракула и случайный маяк Keep Network (на основе BLS Threshold Relay). Чтобы оставаться беспристрастными, эти решения либо требуют честного большинства, либо предполагают отсутствие сговора между оператором и провайдером оракула. Таким образом, их доверие требует криптоэкономических механизмов и нетривиальных предположений о доверии.

VeeDo: ненадежный, беспристрастный маяк случайности

Использование VDF в качестве маяка случайности было первоначально предложено Джастином Дрейком и является ведущим предложением по случайности цепочки маяков в Eth 2.0. Основная идея состоит в том, чтобы использовать источник с высокой энтропией в качестве начального числа s для VDF (например, хэш блока), а затем запустить VDF для n итераций и использовать его выходные данные f (s, n) в качестве несмещенной случайности. Предполагая, что никто не знает, как предсказать f (s, n) по s менее чем за t секунд, мы можем попросить игроков сделать всевозможные ходы и ставки до того, как истечет t секунд, и использовать результат f(s,n) как случайность событий, которые произошли до истечения t секунд. Другими словами, непредвзятость случайности VDF не основана на криптоэкономических или доверительных предположениях; скорее, он основан на предположениях о максимальной скорости последовательных вычислений.

PoC Описание

PoC состоит из компонента вне сети и смарт-контрактов в сети. Компонент вне сети включает в себя тяжелые вычислительные части VDF, а именно вычисление функции задержки и создание доказательства. В цепочке есть два смарт-контракта: смарт-контракт Verifier, который проверяет доказательство, и смарт-контракт Beacon, где мы регистрируем рассчитанную случайность (для проверенных доказательств).

Особенности течения заключаются в следующем:

1. Выбирать блок каждые 820 блоков (примерно раз в 3 часа)
2. Вычислить seed s из хэша блока
3. Вычислите выход VDF f (s, n) — запустите функцию задержки f на s для n итераций
4. Создайте доказательство, подтверждающее правильность вычислений
5. Отправьте подтверждение смарт-контракту Verifier .
6. Отправьте новую случайность в смарт-контракт Beacon

В PoC количество итераций равно 10*2**25–1, что соответствует примерно 3,5-минутной задержке (на мощном ЦП последнего поколения каждая итерация занимает ~634 нс). Ожидается, что новая случайность вместе с доказательством будет принята в сети примерно через 20 минут после того, как выбранный блок был добыт. Это время можно улучшить, но это не входит в объем настоящего PoC. Для более подробного описания технических аспектов загляните в репозиторий github .

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

Будущие приложения

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

Временные блокировки: временные блокировки являются важным строительным блоком криптографии. Они позволяют закрывать информацию на заранее определенный период времени, а затем обнародовать. Обычно временные блокировки реализуются с использованием схемы фиксации . Основным недостатком таких схем является то, что совершающая сторона все равно должна быть в сети в более позднее время, чтобы раскрыть совершенную информацию. Косвенно это также означает, что передающая сторона имеет возможность не раскрывать свое обязательство. Это равносильно бесплатной опции, и если эта опция не оценена должным образом, эффективность рынка снижается. Два интересных варианта использования блокчейнов без разрешения — это децентрализованное голосование и аукционы с закрытыми ставками. VeeDo может помочь: как мы упоминали выше, одно интересное свойство функции задержки VeeDo заключается в том, что обратная (f ^(-1)) намного короче для вычисления. Пользователь, заинтересованный во временной блокировке секрета b (например, заявки или голосования), может быстро вычислить и опубликовать s= f ^(-1)(b, n). Теперь общественность может узнать b , вычислив f (s, n), в результате чего b будет раскрыто с желаемой задержкой.

NextGen PoW: надежный алгоритм PoW остается сложной проблемой в области блокчейна. Проблема усугубляется при попытке запустить блокчейн и его экономику токенов. Существующие решения несовершенны: аирдропы подвержены атакам Сивиллы. ICO ограничены аккредитованными инвесторами. Наконец, первоначальное видение «Один процессор = один голос/токен» оказалось довольно труднодостижимым, поскольку для ускорения любого заданного алгоритма PoW создается специальное оборудование. В результате снижается степень децентрализации майнинговой сети. VeeDo представляет собой альтернативу, которая уравнивает правила игры: владельцы дорогого и специализированного оборудования имеют очень небольшое преимущество (и ограниченное) перед любой женщиной (и обычным мужчиной) с процессором.

Инновационная бизнес-модель

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

• Layer-1 (L-1): Как показывают нам Uniswap и другие, из этих Lego можно построить многое прямо на L-1.
• Уровень-2 (L-2): Исходя из нашего очень ориентированного на блокчейн взгляда на вселенную, можно сказать, что вселенная финтеха (PayPal, Coinbase и т. д.) — это L-2.
• Интерфейс L-1/L-2: Money Legos можно сделать более мощным, если нам удастся эффективно преодолеть разрыв между L-1/L-2 и использовать ресурсы, доступные в L-2 (вычисления и хранение в облаке/ mobile) для усиления взаимодействия на L-1.

VeeDo — наша первая попытка изучить этот интерфейс. «Фронтенд» VeeDo — это смарт-контракт на Ethereum (L-1); его «бэкэнд» вычисляет доказательства STARK в облаке (L-2).

Первый набор проблем связан с доступностью услуг: как обеспечить достаточное время безотказной работы? Как мы можем гарантировать, что сервис в целом достаточно децентрализован? Здесь есть несколько направлений для изучения, включая открытый исходный код, лицензирование и взимание платы за смарт-контракт.

Монетизация с помощью платы за смарт-контракты может представлять проблемы «безбилетника» , особенно при рассмотрении общественных благ, такого надежного источника случайности. Там тоже у нас есть несколько идей в рукаве, которые мы будем изучать в ближайшее время.

Вывод

VeeDo — это VDF на основе STARK от StarkWare, и его PoC теперь доступен в основной сети. Мы видим впереди захватывающий путь со многими приложениями. Первое приложение использует VeeDo для создания надежной случайности. Все это экспериментальный материал, поэтому мы с нетерпением ждем ваших отзывов, обсуждения интересных приложений и т. д. Пожалуйста, напишите нам по адресу [email protected].

~ Кинерет Сигал, Том Брэнд