Перешлите оригинальное название 'Парадигма нулевого разглашения: Часть 1 - Что такое zk-VM?'

1. Доказательства с нулевым разглашением: учебник

Что такое доказательства с нулевым разглашением (ZKP)?

Если у вас нет предварительных знаний о доказательствах с нулевым разглашением (ZKP), это видео от Wired объясняет концепцию на пяти уровнях сложности в интерактивной манере с простыми для понимания примерами и демонстрациями. Очень рекомендую.

Проще говоря, ZKP позволяют одной стороне (доказывающей) доказать другой стороне (верификатору), что она что-то знает, не раскрывая, что это за вещь или какую-либо дополнительную информацию. В частности, ZKP доказывают знание фрагмента данных или знание результата вычислений, не раскрывая данные или входные данные. Процесс создания доказательства с нулевым разглашением включает в себя серию математических моделей для преобразования результатов вычислений в фрагмент бессмысленной информации, которая доказывает успешное выполнение кода, который позже может быть проверен.

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

zkSNARKs: Краткий неинтерактивный аргумент знаний с нулевым разглашением

• Полагается на первоначальный процесс настройки (доверенный или ненадежный) для определения параметров для проверки
• Требуется по крайней мере одно взаимодействие между проверяющим и проверяющим
• Размеры пробных оттисков невелики и легко проверяются
• Проверки на основе NARK используются такими накопителями, как zkSync, Scroll и Linea

zkSTARKs: масштабируемый прозрачный аргумент знаний с нулевым разглашением

• Надежная настройка не требуется
• Обеспечение высокой прозрачности за счет использования публично проверяемой случайности для создания не требующих доверия проверяемых систем, т.е. генерации доказуемо случайных параметров для доказательства и верификации
• Высокая масштабируемость, так как они могут быстро генерировать и проверять доказательства (не всегда), даже если размер базового следящего сервера (данных) велик
• Не требует взаимодействия между проверяющим и проверяющим
• За это приходится расплачиваться тем, что STARK генерирует более крупные доказательства, которые может быть сложнее проверить, чем SNARK
• Доказательства сложнее проверить, чем некоторые доказательства zkSNARK, но не так сложно, как некоторые другие
• STARK используются Starknet, а также zkVM, такими как Lita, Risc Zero и Succinct Labs

(Примечание: мост Succinct использует SNARK, но SP1 является протоколом на основе STARK)

Стоит отметить, что все STARK являются SNARK, но не все SNARK являются STARK.

Для лучшего общего понимания SNARK и STARK мы рекомендуем прочитать эту серию статей @krzhang/privacy-in-cryptocurrencies-zero-knowledge-and-zk-snarks-1-2-68ce1838fd9c">, написанную Янь Чжаном и Йи Сунем из Axiom, а также эту коллекцию статей на github Ventali Tan.

2. Что такое zkVM?

Виртуальная машина (ВМ) — это программа, которая запускает программы. В контексте, zkVM — это виртуальный компьютер, который реализован как система для генерации доказательств с нулевым разглашением, или универсальная схема, или инструмент, для генерации ZKP для любой программы или вычисления.

zkVM избавляет от необходимости изучать сложную математику и криптографию для проектирования и кодирования ZK и позволяет любому разработчику выполнять программы, написанные на предпочитаемых им языках, и генерировать ZKP, что значительно упрощает интеграцию и взаимодействие с нулевым разглашением. Вообще говоря, большинство ссылок на zkVM неявно включают в себя цепочки инструментов компилятора и системы доказательства, добавленные к виртуальной машине, выполняющей программы, а не только к самой виртуальной машине. Ниже мы кратко изложим основные компоненты zkVM и их функции:

Основные компоненты zkVM

Проектирование и реализация каждого компонента определяется выбором доказательства (SNARK или STARK) и архитектурой набора инструкций (ISA) zkVM. Традиционно, ISA определяет, на что способен процессор (типы данных, регистры, память и т.д.) и последовательность действий, выполняемых процессором при выполнении программы. В контексте ISA определяет машинный код, который интерпретируется и исполняется виртуальной машиной. Выбор ISA может привести к радикальным различиям в доступности и удобстве использования zkVM, а также в скорости и эффективности процессов генерации доказательств, и лежит в основе построения любой zkVM.

Ниже приведено несколько примеров zkVM и их компонентов для справки.

zkVM и их компоненты

Сейчас мы сосредоточимся на взаимодействиях между каждым компонентом на высоком уровне, чтобы обеспечить основу для понимания алгебраических и криптографических процессов, а также компромиссов при проектировании zkVM в следующей статье.

3. Абстрактный поток процессов zkVM

Следующая диаграмма представляет собой абстрактную, обобщенную блок-схему процесса zkVM, разделенную и классифицированную по форматам (входы/выходы) программы по мере ее перемещения по компонентам zkVM. Каждый процесс мы подробно рассмотрим в последующих статьях.

Общий поток для zkVM

Последовательность процессов zkVM обычно выглядит следующим образом:

• Стадия компилятора

1. Компилятор сначала компилирует программы, написанные на обычных языках (C, C++, Rust, Solidity), в машинный код. Формат машинного кода диктуется выбором ISA.

• Стадия виртуальной машины

1. Виртуальная машина выполняет машинный код и создает трассировку выполнения, которая представляет собой последовательность шагов базовой программы. Его формат предопределен выбором арифметизации, а также набором полиномиальных ограничений. Распространенные схемы арифметизации включают R1CS, как в Groth16, арифметизацию PLONKish , как в halo2, и AIR, как в plonky2 и plonky3.

• Стадия прувера

1. Доказывающий получает трассировку и представляет ее в виде набора полиномов, связанных набором ограничений, по сути, переводя вычисления в алгебру путем математического отображения фактов.

2. Доказывающий фиксирует эти полиномы, используя схему полиномиальных обязательств (PCS). Схема обязательств — это протокол, который позволяет доказывающему создать отпечаток некоторой информации X, который называется обязательством перед X, а затем доказать факты об X, не раскрывая X, используя обязательство X. PCS — это отпечаток пальца; «Предварительно обработанная» краткая версия ограничений на вычисление. Это позволяет доказывающему доказать факты о вычислении, теперь выраженные в полиномиальном уравнении, используя случайные значения, предложенные верификатором на следующих шагах.

3. Проверяющий запускает Polynomial Interactive Oracle Proof (PIOP), чтобы показать, что зафиксированные полиномы представляют трассировку выполнения, которая удовлетворяет заданным ограничениям. PIOP — это интерактивный протокол доказательства, состоящий из серии раундов, в которых доказыватель посылает обязательства к полиномам, верификатор отвечает случайными значениями поля, а доказыватель предоставляет оценки полинома при этих случайных значениях, сродни «решению» полиномиального уравнения с использованием случайных значений для вероятностного убеждения верификатора.

4. Применение эвристики Фиат-Шамир; проверяющий запускает PIOP в неинтерактивном режиме, где поведение верификатора ограничено отправкой псевдослучайных баллов вызова. В криптографии эвристика Фиата-Шамира преобразует интерактивное доказательство знаний в цифровую подпись для проверки. На этом шаге доказательство шифруется и становится нулевым разглашением.

5. Доказыватель должен убедить верификатора в том, что заявленные полиномиальные оценки верны в отношении полиномиальных обязательств, которые он отправил верификатору. Для этого доказывающий производит «оценочное» или «открывающее» доказательство, которое обеспечивается схемой полиномиальных обязательств (отпечатком пальца).

• Этап верификатора

1. Верификатор проверяет доказательство, следуя протоколу проверки системы доказательства, используя либо ограничения, либо обязательство. Проверяющий либо принимает, либо отклоняет результат в зависимости от достоверности доказательства.

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

Доказательство zkVM доказывает, что для данной программы виртуальной машины и заданного вывода существует некоторый вход, который заставляет данную программу выдавать заданные выходные данные при выполнении на виртуальной машине.

4. Оценка zkVM

По каким критериям мы должны оценивать zkVM? Другими словами, когда мы должны говорить, что одна zkVM лучше другой? По правде говоря, ответ зависит от варианта использования.

Исследование рынка, проведенное компанией Lita, показывает, что для большинства коммерческих сценариев использования наиболее важными свойствами являются скорость, эффективность и лаконичность, в зависимости от приложения. Некоторые приложения чувствительны к цене и требуют оптимизации для обеспечения низкого энергопотребления и низкого использования капитала при проверке; Для них эффективность основного времени, вероятно, является наиболее важным показателем для оптимизации. Другие приложения, особенно связанные с финансами или торговлей, чувствительны к задержкам и требуют оптимизации скорости.

Большинство публикуемых сравнений производительности сосредоточены исключительно на скорости, которая важна, но не является целостным измерением производительности. Есть также несколько важных свойств, которые измеряют надежность zkVM; Большинство из них не соответствуют стандартам, готовым к производству, даже для ведущих игроков рынка.

Мы предлагаем, чтобы zkVM оценивались по следующим критериям, разделенным на два подмножества:

Основные критерии оценки zk-VM

Базовый: измеряет надежность zkVM

• Корректность
• Безопасность
• Предположения о доверии

Производительность: измеряет возможности zkVM

• Эффективность
• Скорость
• Лаконичность

4.1 Базовый уровень: предположения о правильности, безопасности и доверии

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

Без этих свойств zkVM потенциально более чем бесполезна для приложения, так как она может работать не так, как указано, и подвергать пользователей взлому и эксплойтам.

i. Правильность

• Виртуальная машина должна выполнить вычисления должным образом
• Система доказательств должна удовлетворять заявленным защитным свойствам

Корректность складывается из трех свойств:

• Обоснованность: Система доказательств правдива, и поэтому все, что она доказывает, истинно. Верификатор отклоняет доказательства ложных утверждений; Он принимает результат вычисления только в том случае, если входные данные действительно дают этот результат.
• Полнота: Система доказательств является полной и может доказать все истинные утверждения. Если проверяющий утверждает, что он может доказать результат вычисления, он должен быть в состоянии предоставить доказательство, которое верификатор принимает.
• Нулевое разглашение: Обладание доказательством раскрывает о входных данных вычислений не больше, чем знание самого результата

Вы можете иметь полноту без здравости; Если система доказательств доказывает все, включая ложность, то очевидно, что она полная, но не обоснованная. И наоборот, вы можете иметь здравость без полноты; Если система доказательств доказывает, что программа существовала, но не может доказать вычисления, то очевидно, что она верна (в конце концов, она никогда не доказывает ложности), но не полна.

ii. Безопасность

• Относится к допускам надежности, полноты и нулевого знания

На практике все три свойства корректности имеют ненулевые допуски. Это означает, что все доказательства являются статистическими вероятностями правильности, а не абсолютной уверенностью. Допуск относится к максимально допустимой вероятности того, что одно свойство не будет выполнено. Нулевые допуски, конечно, являются идеальными, но zkVM не достигают нулевых допусков для всех этих свойств на практике. Идеальная обоснованность и полнота, по-видимому, несовместимы с краткостью, и не существует известных методов достижения совершенного нулевого знания. Распространенный способ измерения безопасности — в битах безопасности, где допуск 1 / (2^n) называется n битами безопасности. Чем больше битов безопасности, тем лучше.

Если zkVM абсолютно корректна, это не обязательно означает, что она надежна. Корректность подразумевает только то, что zkVM удовлетворяет своим защитным свойствам в пределах заявленных допусков. Это не означает, что заявленные допуски достаточно низкие, чтобы быть готовыми к выходу на рынок. Кроме того, если zkVM достаточно безопасна, это не означает, что она правильная; Безопасность относится к заявленным допускам, а не к реально достигнутым допускам. Только в том случае, если zkVM абсолютно правильна и достаточно надежна, можно сказать, что zkVM надежна до заявленных допусков.

iii. Предположения о доверии

• Предположения о честности доказывателя и верификатора для того, чтобы прийти к выводу, что zkVM функционирует надежно

Когда zkVM имеют предположения о доверии, это обычно принимает форму процесса доверенной установки. Процесс настройки системы проверки ZK выполняется один раз, до того, как с помощью системы доказательств будет сгенерировано первое доказательство, чтобы сгенерировать некоторую информацию, называемую «данными настройки». В доверенном процессе настройки один или несколько человек генерируют некоторую случайность, которая включается в данные настройки, и необходимо предположить, что по крайней мере один из этих людей удалил случайность, которую они включили в данные настройки.

На практике существуют две распространенные модели предположения о доверии.

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

Предположение доверия «1 из N» гласит, что из некоторого набора N индивидуумов, по крайней мере, один из этих индивидуумов продемонстрировал целостность в каком-то конкретном взаимодействии с системой, которое обычно используется инструментами и приложениями на основе MPC.

Общепризнано, что при прочих равных условиях zkVM без предположений о доверии более безопасны, чем zkVM, которые требуют предположений о доверии.

4.2 Трилемма zkVM: баланс скорости, эффективности и лаконичности в zkVM

Трилемма zkVM: скорость, эффективность и лаконичность

Скорость, эффективность и лаконичность — все это свойства скользящей шкалы. Все эти факторы влияют на стоимость zkVM для конечного пользователя. То, как они должны быть взвешены при оценке, зависит от приложения. Часто самое быстрое решение не является самым эффективным или лаконичным; Самое лаконичное решение не является самым быстрым или эффективным; и так далее и тому подобное. Давайте сначала определим каждое свойство, прежде чем объяснять их взаимосвязь

i. Скорость

• Как быстро доказатель может сгенерировать доказательства
• Измеряется в настенных часах, то есть во времени, прошедшем от начала до конца вычислений

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

ii. Эффективность

• Ресурсы, потребляемые проверяющим, при этом меньшее значение предпочтительнее
• Может быть аппроксимировано пользовательским временем, которое представляет собой количество компьютерного времени, затраченного программным кодом

Доказывающий потребляет два вида ресурсов: ядро-время и пространство. Таким образом, эффективность может быть подразделена на эффективность основного времени и эффективность использования пространства.

Core-Time Efficiency: среднее количество времени, в течение которого проверяющий работает на всех ядрах, умноженное на количество ядер, на которых выполняется проверка. Для одноядерного прувера потребление времени ядра и скорость — это одно и то же. Для многоядерного проверщика, работающего в многоядерном режиме в многоядерной системе, потребление времени ядра и скорость — это не одно и то же. Если программа полностью использует 5 ядер или потоков в течение 5 секунд, это будет 25 секунд пользовательского времени и 5 секунд настенного времени.

Эффективность использования пространства: относится к используемой емкости хранилища, такой как оперативная память.

Пользовательское время интересно как показатель энергии, затраченной на выполнение вычислений. В ситуации, когда все ядра полностью загружены почти все время, энергопотребление процессора должно оставаться относительно постоянным. В этой ситуации пользовательское время, затрачиваемое на выполнение кода, связанного с ЦП и преимущественно в пользовательском режиме, должно быть примерно линейно пропорционально количеству ватт-часов (т. е. энергии), затраченных на выполнение этого кода.

Экономия на потреблении энергии или использовании вычислительных ресурсов должна быть интересна с точки зрения любых операций по проверке, которые имеют достаточный масштаб, чтобы их счет за электроэнергию (или счет за облачные вычисления) для доказательства был значительным эксплуатационным расходом. По этим причинам пользовательское время является интересной метрикой. Более низкие затраты на проверку позволяют поставщикам услуг передавать более низкие цены на подтверждение клиентам, чувствительным к затратам.

Оба вида эффективности связаны с энергопотреблением процесса доказательства и количеством капитала, используемого процессом доказательства, что относится к финансовым затратам на доказательство. Чтобы ввести в действие определение эффективности для измерения, определение должно быть сделано относительно одной или нескольких тестовых программ, одного или нескольких тестовых входов для каждой из этих программ и одной или нескольких испытательных систем.

iii. Краткость

• Размер сгенерированных доказательств и сложность их проверки

Краткость представляет собой совокупность трех различных показателей, при этом сложность проверки доказательств дополнительно подразделяется:

• Размер доказательства: физический размер доказательств, обычно измеряемый в килобайтах.
• Время проверки подтверждения: время, необходимое для проверки подтверждений.
• Proof Verification Space: использование памяти во время проверки подтверждения

Верификация, как правило, представляет собой операцию с одним ядром, поэтому скорость и эффективность работы ядра в этом контексте обычно эквивалентны. Как и в случае со скоростью и эффективностью, операционализация определения краткости требует определения наборов тестовых программ, тестовых входных данных и тестовых систем.

Определив каждое свойство производительности, мы продемонстрируем уменьшительное влияние оптимизации одного свойства по сравнению с другими.

• Скорость: Быстрое создание пробных проб приводит к увеличению размеров доказательств, но проверка доказательств выполняется медленно. На создание доказательств расходуется больше ресурсов, что снижает эффективность
• Краткость: Пруверу требуется больше времени для сжатия корректуры. Но проверка доказательств происходит быстро. Чем лаконичнее доказательство, тем выше накладные расходы на вычисления
• Эффективность: Минимизация использования ресурсов снижает скорость создания доказательств и их краткость

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

Хорошим способом взвешивания этих свойств в оценке может быть определение приемлемых уровней для каждого свойства, а затем определение наиболее важных свойств. Наиболее важные свойства должны быть оптимизированы при условии поддержания достаточно хороших уровней для всех остальных свойств.

Ниже мы кратко опишем каждый объект недвижимости и его ключевые аспекты:

Оценочные свойства zkVM

5. Что дальше?

Приведенной выше таблицей мы завершаем первую статью нашей серии. В следующих статьях мы будем опираться на блок-схему, показанную выше, чтобы объяснить общие арифметические и криптографические процессы в zkVM.

Если вы нашли эту статью полезной, посетите наш веб-сайт и gitbook , чтобы узнать больше о том, что мы создаем в Lita.

Кроме того, подпишитесь на нас в X и Discord , чтобы быть в курсе событий, чтобы не пропустить остальную часть серии

Отказ:

1. Эта статья перепечатана из [лита]. Перешлите оригинальное название'Парадигма нулевого разглашения: Часть 1 - Что такое zk-VM?'. Все авторские права принадлежат оригинальному автору [Lita Team]. Если у вас есть возражения против этой перепечатки, пожалуйста, свяжитесь с командой Gate Learn , и они оперативно рассмотрят их.
2. Отказ от ответственности: Взгляды и мнения, выраженные в этой статье, принадлежат исключительно автору и не являются какими-либо инвестиционными рекомендациями.
3. Переводом статьи на другие языки занимается команда Gate Learn. Если не указано иное, копирование, распространение или плагиат переведенных статей запрещены.