ZK-эволюция и рекурсивные снарки ✨ Александр Власов
Александр Власов обстоятельно и подробно рассказал про развитие рекурсивных снарков и практическую сторону их применения во время нашего последнего митапа. Мы собрали основные тезисы его выступления в краткий конспект. Приятного чтения!
Введение: начнем с терминологии
SNARK — Succinct Non-interactive Argument of Knowledge. Демонстрирует что доказывающий знает некий набор переменных X, что для публично известного набора переменных Y и функции f: f(X)==Y. Функция f обычно называется циркуитом. X — витнессом. Y — публичными входами. При этом доказательство довольно компактно — занимает намного меньше места, чем информация, права владения которой доказываются.
zk-SNARK — zero-knowledge SNARK, в результате проверки доказательства невозможно сделать вывод об элементах X, кроме самого их существования.
Чаще всего никто так не формулирует. Все сводится к тому, на самом деле, что для некоторого циркуита (циркуит — тут способ описать некоторую функцию в терминах естественных для пруфсистем) существует удовлетворяющий его набор переменных, называемых витнессом, для некоторого набора публичных входов.
Свойство zk в данном случае является только дополнительным и сводится к тому, что в результате того, что доказывающий создал доказательство целиком, а проверяющий его проверил и получил результат (узнал истинное или ложное утверждение), проверяющий не сможет узнать ничего о наборе внутренних данных, кроме того факта, что они существуют. И что эти данные удовлетворяют функцию, которую мы хотим доказать.
Далее zk-свойство опускается. Оно интересно для некоторых приложений, которые работают с усиленной приватностью, но оно не обязательно для других целей, о которых мы будем говорить. С практической точки зрения, люди чаще хотят доказать корректность вычислений, а знание всех внутренних переменных, удовлетворяющих функцию, для публичного входа — то же самое, что возможность заявить о корректном проведении вычислений для входных значений и доказать этот факт со средним размером доказательства или временем проверки доказательства. Но в целом zk свойство добавить не очень сложно.
Петр Королев: хочу уточнить про то, как можно опустить zk. Например, есть уравнение и заявление о том, что известен корень уравнения. Это утверждение легко проверить — достаточно подставить корень уравнения и посмотреть, верно ли оно. Снарк позволяет доказать верность, не разглашая эти корни уравнений.
Александр Власов: без свойств zk будет происходить разглашение некоторых данных о переменных проверяющим. Если есть zk-аспект, то проверяющий не получает ничего. Это свойство относится к внутренней структуре пруфсистем. Набор внутренних переменных кодируется полиномом. Но во время доказательства полином отрывается в одной случайной точке. В этом случае нельзя узнать какое-то конкретное значение одной из внутренних переменных, но возможно узнать некоторую функцию от нее. В теории можно интерполировать полином по его значениям и получить их все. Zk-снарк позволяет заранее знать, в каком количестве точек откроется полином. Но это добавляет лишь некоторое количество лишних данных к внутренним переменным.
Первые шаги в разработке снарков
Тут стоит отдать должное работам 2013 и 2016 годов. Это наиболее известные первые протоколы: Piпосchio (от него пошли снарки в их практическом аспекте, использован в первой версии zCash) и Groth16 (самый эффективный снарк с точки зрения скорости создания доказательств, эволюция для zCash, используется в TornadoCash и некоторых других проектах). Рекурсия, в данном контексте, это возможность проверить доказательство некоего циркуиута в другом циркуите. Ключевым тут является то, что проверка проходит до конца. Результатом будет утверждение истинности или ложности о том, что был ли проверяющим предоставлен набор входных данных. Шаг рекурсии тут аттестирует целиком и полностью корректность внутреннего доказательства на предыдущем шаге.
В тот момент подход был именно в полном доказательстве, но возможны другие подходы, как мы увидим позже.
Первые сложности в разработке снарков
Первые протоколы требовали использование эллиптической кривой Е над неким полем Fq, для которой определена операция раiring, но сам циркуит определялся над простым полем Fr, модуль которого равен размеру подгруппы Е. В этом была техническая загвоздка, не фундаментальная, но тем не менее, она была значимой с точки зрения практической реализации.
Поскольку Fq и Fr не совпадают, то симуляция арифметики внутри Fq над Fr (или наоборот), была бы достаточно дорогой. Невозможно использовать операции в духе сложения или умножения внутри циркуита. Поэтому пришлось бы раскладывать элементы неродного поля на биты и после этого «развлекаться» обычной евклидовой арифметикой, что имело бы сложность порядка размера поля Fq. Это давало огромные размеры циркуитов и было сверхнеэффективно. Fq l= Fr, и используя только одну кривую попытка выразить операции над Fq в Fr требовали огромных накладных расходов порядка O(log2(|Fq|))
Первое решение возникших сложностей
Использовать две кривые: создаем доказательство, используя одну кривую, а проверяем доказательство, используя циркуит на другой кривой. При этом, наши кривые обладают такими классными свойствами, что размер базового поля одной равен размеру той подгруппы, где циркуит для другой. Одна определена над Fq и имеет подгруппу Fr, другая определена над Fr и имеет подгруппу Fq. На тот момент уже были известны такие кривые. Это знаменитые циклы кривых MNT4/6.
Операции спаривания (paring) появились как атаки на дискретные логарифмы эллиптической кривой. Операция спаривания может быть сведена к дискретному логарифму но в простом поле. К сожалению для pairing-friendly кривых проблема дискретного логарифма становится «проще». Если рairing определен как е(G1, G2) -> Gt, и G1 и G2 — это группы точек на эллиптической кривой, то Gt — это группа элементов в расширении поля Fq.
Для цикла MNT4/6 размер Gt в худшем случае Fq_4 (для другой кривой Fr_6, но IFrl ^- IFql); что в конечном итоге потребовало Fg “= 700 бит, но при этом вычислительная сложность прувера растет как О(IFq/²) как сложность умножения в простом поле.
Константы абсолютного времени доказательства были не очень хорошими, потому что операции в поле 700 бит в 10 раз медленнее, чем операции в поле 256 бит. Принципиальная операция во время создания доказательства — это умножение, а сложность умножения — квадратична от длины. На тот момент вариант поля в 700 бит воспринимался как данность.
Альтернативные подходы
Альтернативные подходы появились относительно недавно. Вместо того, чтобы использовать рекурсии в варианте полной проверки близлежащего утверждения, сейчас подход изменился. Берется условно верное доказательство, с ним проводятся некоторые действия, чтобы свести процедуру последующей проверки доказательства к более простому и также отложить проверку доказательства на потом.
Пришло решение найти кривые с нужными свойствами, но с большей степенью расширения для Gt пока не найдены. Перейти от рекурсии в смысле полной проверки доказательства к агрегации — внутри циркуита произвести некоторые действия с агрегируемым доказательством и передать «наружу» частичный результат, в предположении что если некая проверка над частичным результатом прошла успешна, то и исходное агрегируемое доказательство верно. Но эта процедура имеет линейную сложность и не может быть использована в блокчейнах.
Эта технология, видимо будет использоваться в следующей версии zCash. И это идеально им подходит: высокая эффективность и невысокая сложность генерации прувов для пользовательских устройств.
Halo — используется 2 не pairing-friendly кривые образующие цикл. Эффективная арифметика над «родным» полем. Поскольку производятся только частичные действия с агрегируемым доказательством, то сложность такого циркуита уменьшается и становится возможным и «достаточно» эффективным производить манипуляции над Fq внутри.
Второй этап альтернативных подходов
На следующем этапе пришла идея отказаться от эллиптических кривых и использовать другие прув-системы и/или схемы polynomial commitments (строительный блок современных прув-систем) чтобы все операции были только над одним полем Fr: Fractal и RedShift. Таким образом исчезает необходимость использовать два поля. Теперь поле только одно — то, в котором определен циркуит. Предусматривалось, что тут будет полная проверка на шаге рекурсии.
Оба используют polynomial commitment основанный на FRI протоколе. Оба подхода изначально подразумевают полную проверку доказательства, а не агрегацию. Идеальное решение? К сожалению нет.
Сложность для FRI-based протоколов
Внутренняя процедура доказательства требует использования набора векторных аккумуляторов (примитивов позволяющих для некоего упорядоченного набора элементов продемонстрировать значение элемента по его индексу), обычно реализуемых как Merkle-деревья. Здесь нас начинает интересовать аспект не-циркуита или не-алгебраических хешей. В среднем все работало достаточно быстро и эффективно.
Использование не-алгебраических хэш-функций для Merkle-деревьев в конечном итоге приводит к тому, что 70–90% времени вычисления доказательства тратится на FFT, и остаток на вычисление хэш-функций, но вычисление такого хэша является достаточно не эффективным внутри циркуита.
Наивная идея использовать алгебраические хеши вместо этого привела к тому, что время создания такого прува значительно выросло. Для алгебраических хэш-функций ситуация наоборот — 90% времени на вычисление хэш-функций и 10% на FFT, что ведет к увеличению общего времени работы, но в то же время возможна эффективная реализация внутри циркуита. Встал выбор: согласиться со сложностью циркуита или согласиться со временем доказательства.
Важность «эффективной реализации» внутри циркуита влияет на предел эффективности рекурсии. Допустим, вы хотите рекурсивно проверить циркуит размера N, но реализация рекурсии требует циркуита размера М. Соответственно, если процедура реализации некоей сторонней логики требует нескольких циклов рекурсии, то конечная сложность построения доказательства будет зависеть не от сложности изначальных циркуитов, а от сложности шага рекурсии. Например, рекурсия в случае Fractal требует примерно 2–21 констрейнтов в случае алгебраических хэшей (и в десятки раз больше в случае не алгебраических), но будет неэффективно применять ее для zCash протокола, где много усилий требуется для минимизации сложности доказательств, создаваемых конечными участниками (порядка 2¹⁶ в последней версии). Нужно учитывать при этом особенности разных проектов. Вместо того, чтобы в циркуите иметь несколько веток, выполняющихся параллельно, можно каждую часть подутверждения вынести в отдельный циркуит только для этих целей и потом каким-то образом эти утверждения пересечь. В этом случае будет эффективной, как раз, циркуит рекурсии. Возможно, каждое из подутверждений, которые хочется доказать, является небольшим. Такимо бразом их просто доказать на мобильных устройствах, например. Но рекурсивный шаг приведет за собой циркуит огромного размера. Доказательство представляет собой древовидную модель и в случае сложных емких утверждений, рекурсия для доказательства будет проходить от основания дерева до его верхушки. Таким образом можно одно огромное утверждение свести до проверки одного доказательства. В этом случае, сложность создания полного набора доказательств начинает зависеть не от размера подутверждений, а стоимостью промежуточного шага рекурсии.
Решение для FRI-based протоколов
Этим летом вышел новый алгебраический хеш, основанный на лук-ап таблицах. Конечным результатом создания этого хеша была возможность для некоторого набора параметров реализовать хеш. К счастью новые работы в области алгебраических хэшей позволяют достичь достаточно высокой скорости их вычисления для целей генерации доказательства за разумное время. при той же сложности реализации внутри циркуита.
Поскольку выбор поля Fr для FRI-based протоколов достаточно произволен, то возможно подобрать такое поле, что вычисление хэша Reinforced Concrete (RC) будет всего лишь в 4 раза медленнее чем вычисление blake2s (чемпион по скорости хеширования на 64-битных процессорах), что является приемлемой цифрой для практического использования.
Использование подхода, похожего на конструкцию из статьи Halo Infinite (вышла зимой 2020 года) позволяет использовать агрегацию вместо полной проверки, дополнительно уменьшая сложность циркуита шага рекурсии. Таким образом значительно снизилась стоимость рекурсии. Теперь рекурсия крайне эффективна для снарков.
Cyber Academy — образовательная платформа для блокчейн-разработчиков. Присоединяйтесь к нам
Поддержите нас на Gitcoin ✨
Анонсы | Website | Twitter | Телеграм-чат | GitHub | Facebook | Linkedin
