Русская Википедия:ZK-STARK

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

ZK-STARK (Шаблон:Lang-en2 — «краткий прозрачный аргумент знания с нулевым разглашением») — криптографический протокол, который использует публичные вероятностно проверяемые доказательства с нулевым разглашением. Эта технология позволяет пользователям обмениваться проверенной информацией без её разглашения или выполнять вычисления с третьей стороной без раскрытия вычислений. ZK-STARK — прозрачный протокол, то есть не требующий предварительной настройки и раскрытия информации третьей стороне, такие протоколы ещё называют Шаблон:Нп3[1].

История

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

Особенности

Протоколы с нулевым разглашением решают проблемы безопасности и приватности, так называемая CIP (Шаблон:Lang-en) проблема[6]. Система должна обеспечивать корректную работу и правильный ответ, не нарушая приватность пользователя. Протокол ZK-STARK был предложен, как более быстрая и дешёвая версия уже существующих протоколов с нулевым разглашением. Это первая реализованная система с нулевым разглашением, которая является «прозрачной» (от Шаблон:Lang-en), постквантовой, краткой (от Шаблон:Lang-en), масштабируемой (от Шаблон:Lang-en) и универсальной[7]. Прозрачность системы означает, что нет необходимости доверять третьей стороне секретные данные, и это одно из основных достижений ZK-STARK. Благодаря используемой постквантовой криптографии такая система устойчива к атакам квантовых компьютеров. Краткость системы гарантирует быстрый процесс верификации и небольшой размер доказательств. Под масштабируемостью понимается возможность работы системы на больших данных, то есть эффективное время работы доказывающей стороны для любого доказываемого утверждения. Универсальность означает применимость системы для NP-полных задач и Шаблон:Нп3[6].

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

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

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

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

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

Аргумент знания — это тип доказательства с нулевым разглашением, в котором доказывается утверждение: «Доказывающий обладает некоторой секретной информацией, которая удовлетворяет некоторой публичной функции»[11]. Предположим, что у нас есть публичная функция <math>f</math>, приватная переменная <math>x</math> и публичный результат <math>y</math>. Тогда доказывающая сторона хочет доказать, что она знает такой <math>x</math>, что <math>f(x)=y</math>, без раскрытия <math>x</math>. Стоит отметить, что «аргумент знания» отличается от «доказательства знания»(от Шаблон:Lang-en), потому что «доказательство знания» — это статистически доказанное утверждение, а «аргумент знания» — вычислительно доказанное утверждение. То есть «доказательство знания» является более сильной конструкцией: доказывающая сторона может обмануть проверяющую «аргументом знания», но не «доказательством знания»[11].

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

Давая определение аргументу знания, мы предположили, что обладаем функцией <math>f</math>. Обычно речь идёт про большую сложность вычисления <math>f(x)</math>, тогда краткость алгоритма означает, что процесс верификации проверяющей стороной аргумента знания происходит намного быстрее, чем вычисление <math>f(x)</math>[12]. Примером функции с большой сложностью вычислений, которые не подлежат распараллеливанию, может быть MiMC[13]. Для ZK-STARK справедливо, что при любом выборе функции <math>f(x)</math> процесс проверки требует экспоненциально меньше времени, чем полное вычисление <math>f(x)</math>[14]. Для вычислений, требующих <math>t</math> шагов, необходимо приблизительно <math>O(t \log(t))</math> шагов для создания доказательства. Для верификации необходимо <math>~O(\log^2(t))</math> шагов, что даже для больших значений <math>t</math> намного быстрее полного вычисления. Поэтому систему, использующую STARK, называют дважды масштабируемой (от Шаблон:Lang-en). Стоит отметить, что если мы не оговариваем отдельно нулевое разглашение протокола, то проверяющая сторона может попросить доказывающую сторону просто вычислить значение <math>f(x,y)</math>. Технология ZK-STARK позволяет без разглашения секретной информации доказывающей стороной добиться того же результата, что и при использовании протоколов с разглашением, и вдобавок с значимо меньшими затратами по времени[15].

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

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

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

ZK-STARK система использует новую технологию интерактивного доказательства с оракулом или Шаблон:Lang-en2[16]. Системы, основанные на интерактивных доказательствах с оракулом, являются объединением систем с Шаблон:Нп3 и Шаблон:Нп3[17]. Интерактивное доказательство означает обмен чередой сообщений между доказывающей и проверяющей стороной в процессе проверки. Вероятностно проверяемые доказательства можно проверить, прочитав лишь константное число битов этого доказательства, при этом алгоритм проверки доказательства использует лишь логарифмическое число случайных битов[18]. Такие системы опираются на использование дерева Меркла для хранения доказательства и вычислений. Допустим, доказывающая сторона хочет доказать проверяющему, что обладает некоторыми данными, которые удовлетворяют какой-то функции. Тогда она представляет эти данные в виде дерева Меркла и отправляет хеш корня дерева проверяющей стороне. Проверяющая сторона тогда выбирает случайным образом какое-то количество точек и просит для этих точек прислать ветви дерева Меркла. Доказывающая сторона вычисляет и отправляет необходимые данные. Проверяющий проверяет, что эти полученные ветви соответствуют изначально полученному корню дерева и что в этих точках значения удовлетворяют некоторой проверочной функции. Этот трёхшаговый алгоритм может быть переделан в неинтерактивное доказательство, где доказывающая сторона отправляет лишь одно сообщение, которое может быть проверено любым участником. Для этого используется Шаблон:Нп3. Проверяющая сторона строит дерево Меркла для данных, вычисляет корневой хеш. В качестве меры случайности для выбора точек, необходимых для проверки, доказывающая сторона берёт энтропию корня дерева. Тогда доказывающая сторона предоставляет в качестве доказательства корень и выбранные ветви. При таком подходе все вычисления производятся доказывающей стороной. Вычисление корня дерева Меркла и выбор ветвей на его основе избавляет от необходимости в интерактивном протоколе[19].

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

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

Для ускорения процесса верификации в ZK-STARK используется новый алгоритм быстрой верификации для интерактивных вероятностных доказательств с оракулом или же FRI (Шаблон:Lang-en2), который основан на идее использования IOP и кода Рида-Соломона[17]. Чтобы объяснить работу алгоритма, необходимо перейти к полиномному представлению. Допустим, проверяющему необходимо проверить принадлежат ли <math>N</math> точек некоторому полиному <math>f(x)</math> степени <math>D</math> меньшей <math>N</math>. Алгоритм FRI позволяет получить статистическое доказательство по предоставленным данным того, что большинство точек принадлежат полиному <math>f(x)</math>. Идея состоит в том, чтобы представить исходную функцию как функцию двух переменных <math>f(x) = g(x,y) = g(x, x^k)</math>. Тогда полином от двух переменных <math>g(x,y)</math> имеет меньшую степень <math>D_1 < \frac{D}{k}</math>. Доказывающая сторона должна вычислить полином <math>g(x,y)</math> над множеством <math>[1,2,...N]\times[x^k: 1\leq x \leq N]</math>, что может быть представлено в виде матрицы <math>N\times N</math>. Тогда на диагонали этой матрицы будут лежать в точности значения <math>g(x, x^k) = f(x)</math>. Проверяющая сторона выбирает какое-то количество строк и столбцов и просит доказывающую сторону предоставить какое-то фиксированное количество точек из каждой строки и каждого столбца, причём в каждом случае хотя бы одна точка принадлежит диагонали. Доказывающая сторона предоставляет эти точки вместе с вычисленными ветвями дерева Меркла, чтобы доказать, что данные являются частью исходных данных в соответствии с протоколом IOP. Проверяющая сторона, получив данные, сверяет предоставленные ветви с полученным в начале корнем дерева Меркла. Затем проверяющая сторона проверяет, что:

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

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

Применение

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

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

Авторы алгоритма считают полезным использовать его в том числе для решения проблемы Шаблон:Lang-en2, то есть для проверки наличия ДНК человека в уже существующих базах данных. Например, для проверки полицией наличия ДНК кандидатов в президенты в криминалистических базах[24]. Таким образом, сгенерированное полицией доказательство не требует раскрытия информации о базах, хранящих ДНК, и о ДНК кандидатов третьим лицам, при этом доказательство публично верифицируемо. Такая проверка проходит быстрее полной сверки образца ДНК со всеми образцами базы данных. Результат проверки: «нет совпадений», «частичное совпадение», «полное совпадение» публикуется и является общедоступным[25].

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

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

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

Примечания

Шаблон:Примечания

Ссылки

Шаблон:Криптография

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Публикация
  2. ↑ Шаблон:Публикация
  3. ↑ Шаблон:Cite web
  4. ↑ Шаблон:Cite web
  5. ↑ Шаблон:Cite web
  6. ↑ 6,0 6,1 Шаблон:Публикация
  7. ↑ Шаблон:Cite web
  8. ↑ Шаблон:Публикация
  9. ↑ 9,0 9,1 9,2 Шаблон:Cite web
  10. ↑ Шаблон:Source
  11. ↑ 11,0 11,1 Шаблон:Cite web
  12. ↑ Шаблон:Публикация
  13. ↑ Шаблон:Публикация
  14. ↑ Шаблон:Публикация
  15. ↑ Шаблон:Cite web
  16. ↑ Шаблон:Публикация
  17. ↑ 17,0 17,1 Шаблон:Публикация
  18. ↑ Шаблон:Cite web
  19. ↑ 19,0 19,1 Шаблон:Cite web
  20. ↑ Шаблон:Публикация
  21. ↑ Шаблон:Публикация
  22. ↑ Шаблон:Cite web
  23. ↑ 23,0 23,1 23,2 Шаблон:Cite web
  24. ↑ Шаблон:Публикация
  25. ↑ Шаблон:Публикация
  26. ↑ Шаблон:Cite web
  27. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:ZK-STARK&oldid=8871674