Автор: Лямбда Класс
Составитель: Бай Дин, Фауст, Никцяо.
Оригинал статьи на английском языке опубликован 17 февраля 2024 г.
Доказательства с нулевым разглашением (ZK Proofs) — это мощные криптографические примитивы, которые позволяют одной стороне (доказывающему) убедить другую сторону (проверяющую) в том, что данное утверждение истинно и действительно, не раскрывая никакой личной информации. В последние годы ZK привлек широкое внимание в области проверяемых частных вычислений, предоставления доказательств достоверности компьютерных программ и блокчейна и оказал значительное положительное влияние на развитие мира.
Хотя ZK является новой технологией, ее основные идеи и концепции восходят к 1980-м годам. После объединения с такими блокчейнами, как Биткойн и Эфириум, развитие технологии ZK значительно ускорилось, поскольку блокчейн может выполнять проверку достоверности через SNARK и STARK, что значительно повышает масштабируемость, что делает ZK в регионе Блокчейн горячей темой.
По словам основателя Starkware Эли Бен-Сассона, в последние годы мы стали свидетелями «кембрийского взрыва» систем криптографической защиты, каждая из которых имеет уникальные преимущества и недостатки, а также компромиссы в своей конструкции. Развитие аппаратного обеспечения, улучшение алгоритмов, новые аргументы и периферийные инструменты — все это стимулировало повышение производительности систем ZK и рождение новых систем. Многие системы доказательств были внедрены в практическое применение, и люди все еще расширяют границы ЗК.
Это также заставляет людей глубоко задуматься над вопросом: существует ли универсальная система доказательства ZK, подходящая для всех приложений? Мы считаем, что это маловероятно по трем причинам:
разнообразие приложений;
Различные типы ограничений (включая память, время проверки, время доказательства);
Потребность в надежности (если одна система доказательств будет скомпрометирована хакером, мы все равно можем переключиться на другую систему в качестве страховки).
На основании вышеизложенных причин ЗК доказывает, что система должна быть разнообразной. Но даже если существует много типов систем доказательств, должна быть одна существенная общая черта: доказательства ZK могут быть быстро проверены и имеют уровень проверки, который можно легко адаптировать к новым системам доказательств для решения базовых уровней (таких как Ethereum), связанных с трудности.
В области ZK часто упоминается zk-SNARK. Это форма реализации доказательств с нулевым разглашением с использованием сложных математических инструментов, таких как билинейные пары и арифметические схемы, для достижения эффективных доказательств с нулевым разглашением. Особенностью zk-SNARK является то, что процесс доказательства является простым и неинтерактивным, между доказывающим и проверяющим требуется только один обмен данными без многократного взаимодействия. Кроме того, zk-SNARK имеет очень небольшой размер доказательства и высокую эффективность проверки, что делает его пригодным для использования в средах с ограниченными ресурсами.
И zk-STARK — еще одна распространенная форма, предназначенная для преодоления некоторых ограничений zk-SNARK. zk-STARK не полагается на доверенные настройки и использует более прозрачную систему математического построения, такую как полиномиальное обязательство и операции с конечными полями, хеш-коллизии и т. д., для генерации и проверки доказательств. zk-STARK более масштабируем, чем zk-SNARK, подходит для крупномасштабных вычислений, а создание доказательства происходит быстрее, но размер самого доказательства обычно больше.
Можно сказать, что zk-SNARK и zk-STARK являются широко используемыми формами в доказательствах с нулевым разглашением, но они различаются с точки зрения прозрачности, масштабируемости, размера доказательства и т. д.
В целом система доказательства ZK обычно состоит из двух частей: PIOP (полиномиальный интерактивный оракул) и PCS (схема полиномиальных обязательств). К распространенным решениям PIOP относятся PLONKish, GKR и т. д., а к распространенным решениям PCS относятся FRI, KZG, IPA и т. д. Например, версия Halo2 для Zcash использует реализацию Plonkish+IPA. Что касается zk-STARK, ее действительно можно рассматривать. как решение на базе ФРИ Специальный зк-СНАРК.
Если вдаваться в подробности, то в разных типах систем доказательства используются разные схемы полиномиального обязательства (PCS), арифметические схемы, интерактивные доказательства оракула (IOP) или вероятностные проверяемые доказательства (PCP).
Кроме того, разные системы доказательств ЗК зачастую различаются по следующим показателям:
Криптографические предположения: устойчивые к коллизиям хэш-функции, задача дискретного логарифма на эллиптических кривых, экспоненциальное знание.
Прозрачные настройки и доверенные настройки
Время, потраченное на создание доказательств: линейное или суперлинейное
Затраты времени на проверку доказательства: постоянное время, логарифмическое время, сублинейное, линейное.
Подтвердить размер
Простота рекурсии
арифметическая схема
Одномерные и многомерные полиномы
Ниже мы кратко коснемся истоков технологии ZK, рассмотрим ее основные строительные блоки и обрисуем взлеты и падения различных систем защиты от ZK. В то же время в этой статье не дается подробный анализ самой системы доказательств, а основное внимание уделяется тем, кто оказал глубокое влияние на эту область. Ведь развитие любой отрасли возможно только благодаря великим идеям пионеров. и их реализация.
Историческое развитие зк-СНАРК
Происхождение: 1980-е и 1990-е годы.
Как мы уже упоминали, доказательство с нулевым разглашением не является новой концепцией. Его определение, основы, важные теоремы и даже соответствующие важные протоколы появились еще в середине 1980-х годов. Впервые оно появилось у Гольдвассера и Микали (основателя Algorand) и Ракоффа. статья «Сложность знаний интерактивных систем доказательства».
Ключевые идеи и протоколы, которые мы используем сегодня для создания технологии ZK-SNARK, были разработаны в 1990-х годах. Например, протокол Sumcheck упрощает объявление суммы многомерных полиномиальных оценок для случайно выбранных точек на эллиптической кривой. закладывает важную основу для технологии ZK.
Таким образом, зарождение идеи ZK фактически предшествовало появлению Биткойна. Однако в то время существовало общее отсутствие подходящих вариантов использования ZK, и люди не могли обеспечить мощные вычислительные мощности, необходимые для соответствия системе доказательства ZK. Ведь интернет и аппаратное оборудование были в прошлом веке, а в 1990-е годы не были развиты.
Соглашение ПКР (2007 г.)
GKR (Гольдвассер-Калаи-Ротблюм) — это интерактивный протокол. Время работы прувера линейно зависит от количества логических элементов в схеме, а время работы верификатора сублинейно связано с размером схемы. В протоколе GKR доказывающему и проверяющему необходимо согласовать результаты арифметической схемы с двумя входами, работающей в конечном поле. Схема имеет глубину d, причем d-й уровень является входным слоем, а 0-й уровень — входным. выходной слой. Протокол начинается с утверждения о выходе схемы, которое рекурсией сводится к утверждению на предыдущем уровне. Наконец, мы можем преобразовать утверждения о выходе в утверждения о входных параметрах схемы, что можно легко проверить. Можно сказать, что протокол GKR сильно упрощен на основе ранее упомянутого протокола Sumcheck.
Схема полиномиальных обязательств KZG (2010 г.)
В 2010 году три эксперта в области ZK — Кейт из немецкого исследовательского института MPI-SWS, Заверуча из канадской криптографической компании Certicom Research и Голдберг из Университета Ватерлоо — совместно опубликовали статью «Обязательства постоянного размера для полиномов и их приложения». ". В этой статье предлагается схема полиномиального обязательства с использованием билинейных парных групп, названных KZG.
Обещание состоит из одного элемента группы, и отправитель может эффективно выявить любую правильную оценку полинома, а с помощью методов пакетной обработки можно выявить оценку нескольких полиномов. KZG обещает стать одним из основных строительных блоков некоторых известных систем доказательства ZK (например, halo2, используемой командой Ethereum PES), а также играет ключевую роль в EIP-4844 Ethereum. Чтобы более интуитивно понять концепцию технологии пакетной обработки, вы можете обратиться к статье о мосте Mina-Ethereum. Мост Mina-Ethereum.
Ссылка: https://blog.lambdaclass.com/mina-to-ethereum-bridge/
Практическая система ЗК-СНАРК на основе эллиптических кривых (2013 г.)
Первая практическая конструкция ZK-SNARK появилась в 2013 году, требуя этапа предварительной обработки для генерации ключей доказательства и проверки, она была специфичной для программы или схемы и не поддавалась обобщению. Размер этих ключей может быть очень большим и зависит от самих секретных параметров. Если эта конфиденциальность будет нарушена, злоумышленник может подделать доказательство; В этой практической системе ZK-SNARK преобразование кода в доказуемую форму требует компиляции кода в математический набор полиномиальных ограничений.
Первоначально описанный выше процесс приходилось выполнять вручную, что занимало много времени и приводило к ошибкам. Более поздние технологические изменения в этом направлении в основном пытались решить следующие основные проблемы:
Предоставьте более эффективные доказательства
Уменьшите количество предварительной обработки
Обеспечивает общие, а не специфичные для схемы настройки.
Избегайте доверенных настроек
Разрабатывать методы описания схем с использованием языков высокого уровня, а не писать полиномиальные ограничения вручную.
Соглашение Пиноккио (2013)
Протокол Пиноккио — это первая практически используемая система zk-SNARK, основанная на программе квадратичной арифметики (QAP) с начальным размером доказательства 288 байт. Набор инструментов Пиноккио предоставляет компилятор, который компилирует C в арифметические схемы, которые в дальнейшем можно преобразовать в QAP. Протокол Пиноккио требует, чтобы верификатор генерировал ключи, которые не являются универсальными, а зависят от схемы. Это доказывает, что асимптотическая временная сложность генерации системы и настройки ключей линейно зависит от размера вычислений, а время проверки линейно зависит от размера общедоступных входов и выходов.
Грот16(2016)
Грот представляет новый алгоритм ZK с более высокой производительностью при обработке R1CS. R1CS — это система ограничений ранга 1, система ограничений первого порядка, которая представляет собой полиномиальную форму ограничений в zk-SNARK. Доказательство Горта является наименьшим по размеру данных (содержит всего три элемента группы) и его можно быстро проверить, требуя всего трех операций сопряжения и шага предварительной обработки для структурирования ссылочной строки. Но главный недостаток Горта в том, что каждая программа, которую необходимо доказать, требует разных доверенных настроек, что весьма неудобно в практических приложениях.
Позже Groth16 был использован в ZCash, относительно известном блокчейн-проекте конфиденциальности (в нем участвовал основатель Starkware Эли).
Bulletproofs и IPA (2016)
Одним из основных недостатков схемы полиномиальных обязательств KZG, упомянутой ранее, является то, что она требует надежной настройки. Бутл и др. предложили эффективную систему доказательства с нулевым разглашением, которая анализирует открытие обязательств Педерсена, которые удовлетворяют внутренним отношениям продукта. Внутренний продукт доказывает, что доказательство с линейной сложностью требует много времени. Число взаимодействий между доказывающим и проверяющим логарифмическое, но время проверки линейное. Кроме того, Бутл и др. также разработали схему полиномиального обязательства, которая не требует доверенной настройки. Эти идеи позже были переняты, среди прочего, Halo2 и Kimchi.
Соник, Марлин и Плонк (2019)
Sonic, Plonk и Marlin решают проблему требования настроек доверия для каждой программы в алгоритме Groth16, вводя универсальную и обновляемую структурированную ссылочную строку, которая позволяет устанавливать настройки доверия только один раз. Среди них Marlin предлагает систему доказательств, основанную на R1CS, которая стала основной технологией Aleo.
А Plonk представил новую арифметическую схему (позже названную Plonkish) и использование гранд-продукта для проверки ограничений репликации. Plonkish также позволяет использовать специализированные логические элементы схемы для конкретных операций, так называемые «пользовательские элементы». Многие известные блокчейн-проекты использовали индивидуальные версии Plonk, включая Aztec, zkSync, Polygon zkEVM, Mina, команду Ethereum PSE, Scroll и т. д.
Спартанец (2019)
Spartan обеспечивает IOP для схем, описанных с помощью R1CS, используя возможности протоколов проверки многомерного полинома и суммирования. Используя подходящую схему полиномиального обязательства, он реализует прозрачную систему zk-SNARK и генерирует доказательства с линейной временной сложностью.
Поиск(2020)
Габизон и Уильямсон предложили plookup в своей статье 2020 года, используя grand-product для доказательства того, что значение содержится в заранее вычисленной таблице истинности, показывая, как ввести параметр plookup в алгоритм Plonk.
Однако у этих аргументов поиска есть общая проблема. Доказывающему приходится тратить огромные средства на построение полной таблицы истинности, поэтому предыдущие работы по поиску были посвящены снижению стоимости доказательства.
Позже Хабёк представил в статье LogUp, который использует логарифмические производные для преобразования проверок больших продуктов в суммы обратных величин. LogUp имеет решающее значение для повышения производительности Polygon zkEVM, поскольку они требуют разделения всей таблицы истинности на несколько модулей STARK. Эти модули должны быть правильно связаны, и поиск по перекрестным таблицам обеспечивает это. С тех пор внедрение LogUp-GKR улучшило производительность LogUp через протокол GKR.
Caulk — это первое решение, в котором время доказательства имеет сублинейную зависимость от размера таблицы истинности. Его сложность времени предварительной обработки равна O(NlogN), а сложность пространства хранения — O(N), где N — значение истинности. Размер таблицы. Затем последовали другие решения, такие как Baloo, flookup, cq и caulk+. Кроме того, Лассо предлагает несколько улучшений, позволяющих избежать использования таблиц истинности, когда они имеют определенную структуру.
ГиперПлонк (2022)
HyperPlonk был предложен в статье «HyperPlonk: Plonk с проверкой линейного времени и настраиваемыми воротами высокой степени». HyperPlonk основан на идеях Plonk и использует полиномы от многих переменных. Он не использует деление для проверки соблюдения ограничений, а опирается на протокол проверки суммирования. В то же время он также поддерживает ограничения более высокого порядка, не влияя на время генерации доказательства.
Благодаря использованию полиномов от многих переменных нет необходимости выполнять быстрое преобразование Фурье (БПФ), что доказывает, что время генерации линейно масштабируется в зависимости от размера схемы. HyperPlonk также представляет новый IOP перестановки, подходящий для небольших полей, и использует протокол проверки суммы, который снижает рабочую нагрузку на проверяющее устройство, размер доказательства и время проверки.
Система доказательства ZK с использованием хэш-функций, защищенных от коллизий
В то же время, когда в 2013 году был предложен «Пиноккио», существовало несколько предложений по созданию схем/арифметических схем, которые могли бы доказать правильность выполнения инструкций виртуальной машиной. Хотя разработка арифметических схем для виртуальных машин более сложна или менее эффективна, чем написание специальных схем для некоторых программ, у нее есть важное преимущество: какой бы сложной ни была программа, вам нужно только доказать, что она корректно выполняется на виртуальной машине.
Некоторые идеи TinyRAM позже были усовершенствованы при разработке виртуальной машины Cairo, за которой, среди прочего, последовали zk-evm и общий zkvm. Использование устойчивых к коллизиям хэш-функций в системах доказательства устраняет необходимость в надежных настройках или операциях с эллиптическими кривыми, но за счет увеличения времени доказательства.
TinyRAM (2013)
В «SNARKs for C» они разработали систему доказательств на основе PCP, позволяющую доказать правильность результатов выполнения программ, написанных на языке C. Программа скомпилирована в TinyRAM, упрощенную виртуальную машину. Виртуальная машина имеет адресуемую оперативную память на уровне байтов, размер схемы растет квазилинейно с масштабом вычислений и может эффективно обрабатывать такие операции, как циклы, поток управления и доступ к памяти.
Среди них PCP относится к вероятностно проверяемому доказательству, то есть вероятностно проверяемому доказательству. Верификатору достаточно прочитать случайно выбранную часть доказательства, чтобы проверить достоверность доказательства с высокой степенью уверенности. В отличие от традиционных систем доказательств, в которых проверяющему необходимо проверить все доказательство, PCP требует лишь ограниченной случайности для достижения эффективной проверки.
Свет (2017)
Лигеро представил систему доказательств, которая позволяет получить доказательства размера O(√￣n), где n — размер схемы. Он упорядочивает полиномиальные коэффициенты в матричной форме. Brakedown основан на Ligero и вводит концепцию независимых от предметной области схем полиномиальных обязательств.
STARKs (2018)
STARK (масштабируемые прозрачные аргументы знаний) были предложены Эли Бен-Сассоном и др. в 2018 году. Они достигают сложности доказательства 𝑂(log²𝑛), имеют высокую скорость проверки, не требуют доверенной настройки и предположительно являются постквантовыми. Они используются Starkware/Starknet с виртуальной машиной Cairo. Его ключевые инновации включают алгебраическое промежуточное представление (AIR) и протокол Fast Reed-Solomon Interactive Oracle Proximity Proof (FRI). Кроме того, STARK также используются многими известными блокчейн-проектами (такими как Polygon Miden, RiscZero, Winterfell, Neptune, ZeroSync, zkSync и т. д.).
новое направление развития
Использование различных систем доказательства в практических приложениях демонстрирует преимущества разных методов и способствует развитию ЗК. Например, арифметическая схема Plonkish обеспечивает простой способ включения пользовательских логических элементов и аргументов поиска. FRI показала отличную производительность в качестве PCS, что привело к рождению Plonky. В то же время использование проверок grand-products в AIR (привнесение предварительно обработанной рандомизированной информации AIR) повышает ее производительность и упрощает параметры доступа к памяти. zk-STARK становится все более популярным благодаря повышению эффективности генерации и появлению все большего количества хеш-функций, совместимых с ZK.
Новая схема полиномиальных обязательств (2023 г.)
С появлением эффективных SNARK, основанных на многомерных полиномах (таких как Spartan или HyperPlonk), растет интерес к новым схемам обязательств, подходящим для таких полиномов. Binius, Zeromorph и Basefold предлагают новые способы обработки полилинейных полиномов. Преимущество Binius заключается в отсутствии накладных расходов при представлении типов данных (в то время как многие другие системы доказательства используют как минимум 32-битные элементы поля для представления отдельных битов) и работе в двоичной области. В этой схеме обязательств используется торможение, которое не зависит от домена. Basefold обобщает FRI за пределы Рида-Соломона, позволяя использовать независимые от предметной области схемы полиномиальных обязательств (PCS).
Независимость области — это свойство полиномиальной схемы обязательств, что означает, что в полиномиальной схеме обязательств процесс принятия не зависит от конкретных свойств какой-либо конкретной области. Это означает, что обязательства могут быть приняты к полиномам любой алгебраической структуры, например, конечным полям, эллиптическим кривым или даже целочисленным кольцам.
Настраиваемая удерживающая система (2023 г.)
CCS обобщает R1CS, сохраняя при этом арифметизацию R1CS, Plonkish и AIR без дополнительных затрат. Использование CCS в сочетании со Spartan IOP приводит к созданию SuperSpartan, который поддерживает многомерные ограничения, при этом доказывающее устройство не несет криптографических затрат, пропорциональных порядку ограничений. В частности, SuperSpartan предоставляет SNARK для AIR, защищенный от линейного времени.
Подвести итог
В данной статье рассматривается развитие технологии ЗК с середины 1980-х годов. Достижения в области информатики, математики и аппаратного обеспечения в сочетании с внедрением блокчейна привели к появлению новых, более эффективных систем доказательства ZK, открывая путь ко многим приложениям, потенциально меняющим общество.
Исследователи и инженеры предложили улучшения системы ZK в зависимости от потребностей, уделив особое внимание таким аспектам, как размер доказательства, использование памяти, прозрачность, антиквантовая безопасность, время доказательства и время проверки. Хотя в ZK всегда существовало две основные категории основных решений реализации (SNARK и STARK), границы между ними постепенно размыты, и преимущества различных систем доказательства объединяются, например, сочетание различных арифметических схем с новой схемой полиномиального обязательства.
Мы можем ожидать, что новые системы проверки ZK будут продолжать появляться, а их производительность будет улучшаться. Для приложений, использующих эти системы доказательства, если они не смогут следить за итеративным развитием новейших технологий и постоянно реконструировать и применять новейшие алгоритмы, нынешняя лидирующая позиция будет лишь временной.
