ZK-STARK

ZK-STARK (Zero-Knowledge Scalable Transparent Argument of Knowledge — «краткий прозрачный аргумент знания с нулевым разглашением») — криптографический протокол, который использует публичные вероятностно проверяемые доказательства с нулевым разглашением. Эта технология позволяет пользователям обмениваться проверенной информацией без её разглашения или выполнять вычисления с третьей стороной без раскрытия вычислений. ZK-STARK — прозрачный протокол, то есть не требующий предварительной настройки и раскрытия информации третьей стороне, такие протоколы ещё называют протоколами Артура-Мерлина.

История

Реализация ZK-STARK была предложена в 2018 году профессором Израильского технологического института Эли Бен-Сассоном совместно с Иддо Бентовым, Иином Хорешом и Михаилом Рябцевым. До создания этой технологии для реализации системы с нулевым разглашением повсеместно использовалась технология zk-SNARKs, например, на основе неинтерактивного доказательства с нулевым разглашением (ZK-SNARK) сейчас работает криптовалюта Zcash. Технология ZK-STARK позволяет сильно ускорить процесс обмена информацией и устраняет необходимость предварительной доверительной настройки, что в предыдущих протоколах ставило под угрозу конфеденциальность всей системы. Сейчас новая технология разрабатывается ведущими специалистами компании StarkWare, сооснователем которой является Эли Бен-Сассон.

Особенности

Протоколы с нулевым разглашением решают проблемы безопасности и приватности, так называемая CIP (англ. computational integrity and privacy) проблема. Система должна обеспечивать корректную работу и правильный ответ, не нарушая приватность пользователя. Протокол ZK-STARK был предложен, как более быстрая и дешёвая версия уже существующих протоколов с нулевым разглашением. Это первая реализованная система с нулевым разглашением, которая является «прозрачной» (от англ. transparency), постквантовой, краткой (от англ. succinct), масштабируемой (от англ. scalable) и универсальной. Прозрачность системы означает, что нет необходимости доверять третьей стороне секретные данные, и это одно из основных достижений ZK-STARK. Благодаря используемой постквантовой криптографии такая система устойчива к атакам квантовых компьютеров. Краткость системы гарантирует быстрый процесс верификации и небольшой размер доказательств. Под масштабируемостью понимается возможность работы системы на больших данных, то есть эффективное время работы доказывающей стороны для любого доказываемого утверждения. Универсальность означает применимость системы для NP-полных задач и NEXP-полных задач.

Принцип работы

Нулевое разглашение

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

1. Полнота: если утверждение верно, то доказывающая сторона убедит в этом проверяющую с любой наперёд заданной точностью.
2. Корректность: если утверждение неверно, то любой, даже «нечестный», доказывающий не сможет убедить проверяющего за исключением пренебрежимо малой вероятности.
3. Нулевое разглашение: если утверждение верно, то любой, даже «нечестный», проверяющий не узнаёт ничего кроме самого факта, что утверждение верно.

Аргумент знания

Аргумент знания — это тип доказательства с нулевым разглашением, в котором доказывается утверждение: «Доказывающий обладает некоторой секретной информацией, которая удовлетворяет некоторой публичной функции». Предположим, что у нас есть публичная функция $f$, приватная переменная $x$ и публичный результат $y$. Тогда доказывающая сторона хочет доказать, что она знает такой $x$, что $f(x)=y$, без раскрытия $x$. Стоит отметить, что «аргумент знания» отличается от «доказательства знания»(от англ. Proof of Knowledge), потому что «доказательство знания» — это статистически доказанное утверждение, а «аргумент знания» — вычислительно доказанное утверждение. То есть «доказательство знания» является более сильной конструкцией: доказывающая сторона может обмануть проверяющую «аргументом знания», но не «доказательством знания».

Краткость и масштабируемость

Давая определение аргументу знания, мы предположили, что обладаем функцией $f$. Обычно речь идёт про большую сложность вычисления $f(x)$, тогда краткость алгоритма означает, что процесс верификации проверяющей стороной аргумента знания происходит намного быстрее, чем вычисление $f(x)$. Примером функции с большой сложностью вычислений, которые не подлежат распараллеливанию, может быть MiMC. Для ZK-STARK справедливо, что при любом выборе функции $f(x)$ процесс проверки требует экспоненциально меньше времени, чем полное вычисление $f(x)$. Для вычислений, требующих $t$ шагов, необходимо приблизительно $O(t\log(t))$ шагов для создания доказательства. Для верификации необходимо $~O(\log ^{2}(t))$ шагов, что даже для больших значений $t$ намного быстрее полного вычисления. Поэтому систему, использующую STARK, называют дважды масштабируемой (от англ. doubly scalable). Стоит отметить, что если мы не оговариваем отдельно нулевое разглашение протокола, то проверяющая сторона может попросить доказывающую сторону просто вычислить значение $f(x,y)$. Технология ZK-STARK позволяет без разглашения секретной информации доказывающей стороной добиться того же результата, что и при использовании протоколов с разглашением, и вдобавок с значимо меньшими затратами по времени.

Прозрачность

Протоколы с нулевым разглашением были изначально разработаны как интерактивные протоколы, когда в процессе верификации доказывающая и проверяющая стороны обмениваются рядом сообщений. Проверяющий последовательно ставит задачи перед доказывающим, а доказывающий отвечает на каждую поставленную перед ним задачу, и в конце проверяющий объявляет свой вердикт: «верно» или «не верно». Далее были разработаны неинтерактивные доказательства с нулевым разглашением, которые позволяли отправить доказывающему лишь одно сообщение проверяющему. Это достигается с помощью начальной доверительной настройки между сторонами, для ZK-SNARKs используется CRS. Основным достижением ZK-STARK является именно то, что это прозрачная система, то есть нет необходимости в начальной доверительной настройке, которую можно рассматривать как уязвимость протокола. Это достигается благодаря использованию в ZK-STARK симметричной криптографии и хэш-функций, устойчивых к коллизиям.

Интерактивные доказательства с оракулом

ZK-STARK система использует новую технологию интерактивного доказательства с оракулом или IOP (Interactive Oracle Proofs). Системы, основанные на интерактивных доказательствах с оракулом, являются объединением систем с интерактивными доказательствами и вероятностно проверяемыми доказательствами. Интерактивное доказательство означает обмен чередой сообщений между доказывающей и проверяющей стороной в процессе проверки. Вероятностно проверяемые доказательства можно проверить, прочитав лишь константное число битов этого доказательства, при этом алгоритм проверки доказательства использует лишь логарифмическое число случайных битов. Такие системы опираются на использование дерева Меркла для хранения доказательства и вычислений. Допустим, доказывающая сторона хочет доказать проверяющему, что обладает некоторыми данными, которые удовлетворяют какой-то функции. Тогда она представляет эти данные в виде дерева Меркла и отправляет хеш корня дерева проверяющей стороне. Проверяющая сторона тогда выбирает случайным образом какое-то количество точек и просит для этих точек прислать ветви дерева Меркла. Доказывающая сторона вычисляет и отправляет необходимые данные. Проверяющий проверяет, что эти полученные ветви соответствуют изначально полученному корню дерева и что в этих точках значения удовлетворяют некоторой проверочной функции. Этот трёхшаговый алгоритм может быть переделан в неинтерактивное доказательство, где доказывающая сторона отправляет лишь одно сообщение, которое может быть проверено любым участником. Для этого используется эвристика Фиата-Шамира. Проверяющая сторона строит дерево Меркла для данных, вычисляет корневой хеш. В качестве меры случайности для выбора точек, необходимых для проверки, доказывающая сторона берёт энтропию корня дерева. Тогда доказывающая сторона предоставляет в качестве доказательства корень и выбранные ветви. При таком подходе все вычисления производятся доказывающей стороной. Вычисление корня дерева Меркла и выбор ветвей на его основе избавляет от необходимости в интерактивном протоколе.

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

Быстрый алгоритм верификации

Для ускорения процесса верификации в ZK-STARK используется новый алгоритм быстрой верификации для интерактивных вероятностных доказательств с оракулом или же FRI (Fast RS IOPP, RS - Reed-Solomon, IOPP - Interactive Oracle Proofs of Proximity), который основан на идее использования IOP и кода Рида-Соломона. Чтобы объяснить работу алгоритма, необходимо перейти к полиномному представлению. Допустим, проверяющему необходимо проверить принадлежат ли $N$ точек некоторому полиному $f(x)$ степени $D$ меньшей $N$. Алгоритм FRI позволяет получить статистическое доказательство по предоставленным данным того, что большинство точек принадлежат полиному $f(x)$. Идея состоит в том, чтобы представить исходную функцию как функцию двух переменных $f(x)=g(x,y)=g(x,x^{k})$. Тогда полином от двух переменных $g(x,y)$ имеет меньшую степень $D_{1}<{\frac {D}{k}}$. Доказывающая сторона должна вычислить полином $g(x,y)$ над множеством $[1,2,...N]\times [x^{k}:1\leq x\leq N]$, что может быть представлено в виде матрицы $N\times N$. Тогда на диагонали этой матрицы будут лежать в точности значения $g(x,x^{k})=f(x)$. Проверяющая сторона выбирает какое-то количество строк и столбцов и просит доказывающую сторону предоставить какое-то фиксированное количество точек из каждой строки и каждого столбца, причём в каждом случае хотя бы одна точка принадлежит диагонали. Доказывающая сторона предоставляет эти точки вместе с вычисленными ветвями дерева Меркла, чтобы доказать, что данные являются частью исходных данных в соответствии с протоколом IOP. Проверяющая сторона, получив данные, сверяет предоставленные ветви с полученным в начале корнем дерева Меркла. Затем проверяющая сторона проверяет, что:

1. большая часть точек столбцов, предоставленных доказывающей стороной, принадлежат полиномам степени меньшей ${\frac {D}{k}}$;
2. большая часть точек строк, предоставленных доказывающей стороной, принадлежат полиномам степени меньшей ${\frac {D}{k}}$;
3. большая часть точек диагонали, предоставленных доказывающей стороной, принадлежит полиномам степени меньшей ${\frac {D}{k}}$.

Это позволяет убедить проверяющего в том, что большинство точек диагонали действительно принадлежат одному полиному степени $D$. Для уменьшения размерности матрицы, генерируемой проверяющим, используется модульная арифметика. Сложность алгоритма (с учётом размера доказательства в виде дерева Меркла) $O(\log ^{2}(D))$ достигается за счёт рекурсивного запуска с уменьшением степени полинома в 2 раза. Также в реальном алгоритме для вычислений используется бинарное поле Галуа, что повышает его эффективность.

Применение

В дальнейшем технология ZK-STARK может быть использована для:

1. Электронного голосования.
2. Тайной верификации, например, для подтверждения личности.
3. Проведения вычислений и проверки результатов вычислений, например для блокчейн транзакций.

Авторы алгоритма считают полезным использовать его в том числе для решения проблемы DNA profile match (DPM), то есть для проверки наличия ДНК человека в уже существующих базах данных. Например, для проверки полицией наличия ДНК кандидатов в президенты в криминалистических базах. Таким образом, сгенерированное полицией доказательство не требует раскрытия информации о базах, хранящих ДНК, и о ДНК кандидатов третьим лицам, при этом доказательство публично верифицируемо. Такая проверка проходит быстрее полной сверки образца ДНК со всеми образцами базы данных. Результат проверки: «нет совпадений», «частичное совпадение», «полное совпадение» публикуется и является общедоступным.

Сейчас две компании Resistance и StarkWare независимо друг от друга разрабатывают решение для работы децентрализованных бирж на основе технологии ZK-STARK. В StarkWare Industries собираются предложить своё решение для функционирования децентрализованных бирж, а в Resistance планируют запустить собственную биржу на основе ZK-STARKs .

Отличия ZK-STARK и ZK-SNARK

• ZK-SNARK использует эллиптическую криптографию, что делает эту технологию уязвимой перед атакой квантовых компьютеров. Тогда как ZK-STARK использует постквантовую криптографию.
• При реализации ZK-SNARK необходимо провести предварительную доверительную настройку с третьей стороной, в ZK-STARK нет такой необходимости благодаря использованию вероятностно проверяемого доказательства. Это позволяет устранить уязвимость, возникавшую из-за необходимости доверять данные третьей стороне.
• В отличие от ZK-SNARK, системы с использованием ZK-STARK легко масштабируются в терминах скорости вычислений и размера памяти на задачи с большим количеством вычислений.
• Размер доказательства для ZK-SNARK составлял 288 байт, для ZK-STARK он увеличился до нескольких сотен килобайт.

Ссылки

• Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. — 2018. — 1 марта.
• Eli Ben-Sasson and Alessandro Chiesa and Nicholas Spooner. Interactive Oracle Proofs. — 2016. — 1 февраля.