Некоторое время назад я переводил книгу о технологии доказательства с нулевым разглашением. Основной контент был переведен в конце прошлого месяца. Перевод занял гораздо больше времени, чем я ожидал. В настоящее время мы обсуждаем с автором некоторые технические ошибки в книге и готовимся к окончательному варианту.
В любом случае, у меня наконец-то появилось время взглянуть на что-то новое. Начнем с алгоритма Nova~
Информация, связанная с алгоритмом Nova
Три части информации могут помочь понять алгоритм Nova:
Бумага Нова:
Потенциальные атаки Nova и соответствующие исправления:
Краткое описание потенциальных атак Nova:
Эта статья представляет собой понимание и обобщение приведенной выше информации. **Некоторые изображения в этой статье взяты из приведенной выше информации и не будут помечены в этой статье по одному. **
Начните с IVC
Алгоритм Nova — это новый алгоритм доказательства с нулевым разглашением для IVC (инкрементно проверяемые вычисления). IVC, то есть одна и та же функция итеративно вычисляет предыдущий результат как следующий вход. Итерационный процесс вычисления F-функции выглядит следующим образом:
z0 — это первоначальные входные данные, а результат, полученный в результате вычисления F-функции, используется в качестве входных данных следующей F-функции.
Расслабьтесь R1CS и ослабьте обязательства R1CS
Как мы все знаем, R1CS — это представление схемных ограничений в технологии доказательства с нулевым разглашением. Расслабленный R1CS можно рассматривать как расширенную форму R1CS. На основе R1CS добавляются скаляр u и вектор ошибок E. Экземпляр ослабленного R1CS представлен (E, u, x).
Ослабленное обязательство R1CS фиксирует векторы E и W на основе ослабленного R1CS. Пример слабого обязательства R1CS представлен как (\bar{E}, u, \bar{W}, x), где x и u — общедоступные переменные.
Расширение от R1CS до расслабленного R1CS для схемы складывания. Обратите внимание, что с точки зрения расслабленного R1CS, R1CS является его частным случаем. Другими словами, R1CS также является «особым» вариантом R1CS.
Схема складывания
Интуитивно говоря, схема свертывания отношения R заключается в «коллапсировании» двух экземпляров, соответствующих отношению R, в новый экземпляр составного отношения R. Slack R1CS/Relax Commitment R1CS может выполнять аналогичные складки. Процесс складывания в обоих случаях одинаков. Схема складывания Slack Commitment R1CS следующая:
Вся схема складывания состоит из 4 шагов. На первом этапе проверяющий P отправляет проверяющему обязательство \bar{T} перекрестного элемента T. На втором этапе проверяющий отправляет проверяющему случайный запрос r. Третий шаг — это сложение обязательств, которые должны выполнить и доказывающий, и проверяющий. На четвертом этапе доказывающая программа работает самостоятельно и складывает векторы E и W двух экземпляров.
Дополненная функция F' (Аргументированная функция)
Схема свертывания: свернутый экземпляр R1CS ослаблен. Итак, какие же расчеты подтверждаются этими расслабленными примерами R1CS? Очевидно, что эти расчеты включают в себя расчеты складывания. Эти вычисления представляют собой не просто функцию F в вычислениях IVC, их еще называют дополненными функциями F'. Расчет расширенной функции F' в основном состоит из двух частей:
1/F функция в IVC
2/ Складной расчет экземпляра R1CS
Идеальный вид
Имея вышеизложенное понимание, вы можете представить себе процесс складывания:
Среди них схема — это схема, соответствующая дополненной функции F'. acc{1,2,3,4,5,6} — это экземпляр R1CS со слабым обязательством. Схема имеет два расчета: 1/Расслабить свертывание экземпляра обязательства R1CS, например, acc1+acc2->acc3. 2/Вычислить функцию F, меняя состояние с состояния1 на состояние2, а затем с состояния2 на состояние3 и т. д.
Обратите внимание, что схема, соответствующая расширенной функции F', сама является экземпляром R1CS, который можно выразить как расслабленный экземпляр R1CS. На картинке это акк4 и акк6. «Суммирование» означает преобразование слабого экземпляра R1CS в слабый зафиксированный экземпляр R1CS.
Внимательно взглянув на вход второй схемы, acc3 — это экземпляр R1CS с ослабленным обязательством после фолдинга, а acc4 — это экземпляр R1CS с ослабленным обязательством, который доказывает, что acc3 — правильный результат фолдинга. Эти два экземпляра войдут в следующую складку и сгенерируют acc5. Вы можете себе представить, что если acc3 и acc4 являются экземплярами R1CS с выполнимыми слабыми обязательствами, это означает, что acc3 состоит из двух экземпляров R1CS с выполнимыми слабыми обязательствами. Такую надежность можно вывести шаг за шагом «вперед», доказывая тем самым, что расчет F-функции в каждой схеме верен. В общем, благодаря выполнимости двух экземпляров R1CS с слабым обязательством, соответствующих определенной схеме, можно доказать правильность всех предыдущих вычислений IVC.
Настоящий вид
Друзья, знакомые с доказательствами с нулевым разглашением, знают, что эллиптические кривые часто используются в схемах полиномиальных обязательств. Соответствующее полиномиальное обязательство в скалярной области представлено базовой областью эллиптической кривой. Схемы R1CS обычно представляются скалярной областью. Посмотрите внимательно: «подведение итогов» на картинке выше подразумевает преобразование домена. То есть, если вы хотите свернуть экземпляр R1CS со слабой фиксацией, соответствующий схеме, вы должны «свернуть» его в другой схеме. В это время необходимо ввести цикл эллиптической кривой. Между двумя или более эллиптическими кривыми скалярная область одной кривой такая же, как базовая область другой кривой. По совпадению, скалярная область этой кривой такая же, как и базовая область предыдущей кривой. Используя такую петлю эллиптической кривой, можно реализовать «идеальный вид»:
Весь процесс складывания разделен на два контура складывания. Верхнюю часть можно назвать сгибом Контура 1, а нижнюю часть можно назвать сгибом Контура 2. Формальное представление взаимосвязи между двумя схемами находится на странице 8 статьи «Потенциальные атаки на Nova и соответствующие исправления». U представляет свернутый экземпляр, а u представляет расслабленный экземпляр, соответствующий экземпляру R1CS. Обратите внимание, что схема 1 сворачивает экземпляр R1CS с неактивным обязательством, соответствующий схеме 2, а схема 2 сворачивает экземпляр R1CS с неактивным обязательством, соответствующий схеме 1. Основная цель схемы 2 — свернуть экземпляр R1CS с слабым обязательством, соответствующий схеме 1, и вычисление функции в ее схеме бессмысленно. Вместо этого функция F реализована в схеме 1. В сочетании с «идеальным внешним видом» мы можем примерно догадаться о выполнимости U{i+2}^2, u{i+2}^1, u{i+2}^2, U{i+2}^1. является важной частью доказательства.
Потому что «контур» разрезается на две части, и соответствующий контур складывается в другой контур. Существует несколько проблем привязки между экземплярами: привязка между экземплярами u и U и привязка экземпляров u, проходящих между двумя цепями. Чтобы решить эти проблемы привязки, в схему вводятся общедоступные переменные x_0/x_1, где x_1 определяет выходной экземпляр U схемы, привязанный к экземпляру u, и выход текущей функции F (чтобы упростить структуру схемы, не отраженную на рисунке). Вы думаете, что если в схему введен результат H_1 экземпляра U, если экземпляр u выполним, то x_0/x_1 одновременно реален и надежен, то есть он «привязан» к U. x_0 устанавливает связь между входом u и U, а x_1 устанавливает связь между выходом u и U.
Например, когда u{i+1}^1 используется в качестве входа второй половины схемы, он проходит через схему 2, а его выход u{i+1}^2.x0 = u{i+1 }^1.x1, поэтому при входе в верхнюю часть схемы, если u{i+1}^2 может быть удовлетворено, то его x_0 должно быть равно результату H1 из U_{i +1}^2. Это проверяется в схеме 1. Таким образом, гарантируется, что правильный экземпляр передается между двумя цепями.
Подтверждение IVC
Чтобы доказать, что IVC рассчитывается правильно на определенной итерации, необходимо логически доказать следующую информацию:
Помимо доказательства того, что четыре экземпляра могут быть удовлетворены, также необходимо доказать связь привязки между двумя x1, как показано на следующем рисунке:
Верна ли эта информация, требует дополнительного доказательства реализации схемы. То есть доказательство расчета ВАХ является доказательством схемы. Вполне возможно, что если это расчет со многими итерациями, то эти итерации изначально необходимо выполнять в схеме одну за другой, но теперь необходимо проверить только четыре экземпляра схемы на выполнимость и связующие отношения. Улучшение производительности огромно.
Коррекция атак и алгоритмов
Глядя на картинку выше, я интуитивно чувствую, что экземпляры верхнего и нижнего контуров «отдельны» и не имеют никакой привязки. Собственно, так и строится атака.
Поддельные U_i^1 и U{i+1}^2, хотя и поддельные, но являются выполнимыми экземплярами. Создайте u{i+1}^1, измените x_0 и x_1, чтобы они соответствовали подделанному экземпляру U. Очевидно, экземпляр u{i+1}^1 не удовлетворен. Хотя это и не удовлетворено, схема схемы 2 все еще может быть удовлетворена, но выходной экземпляр U{i+1}^1 не удовлетворен. Если u{i+1}^2 успешно построено, схема 1 может построить удовлетворительные u{i+2}^1 и U_{i+2}^2 и удовлетворить отношения привязки x1. Таким образом, сначала строится половина окончательного доказательства подделки. Благодаря симметрии можно построить выходной экземпляр нижней половины. «Соединив» результаты двух построений, можно подделать доказательство расчета ВАХ.
Пересмотренная логика проверки выглядит следующим образом:
Глава 6 статьи «Потенциальные атаки на Nova и соответствующие исправления» содержит подробный анализ безопасности. Заинтересованные друзья могут самостоятельно проверить оригинал статьи.
Основная идея Nova — складывать экземпляры схемы по схеме сгиба. Логика довольно запутанная и требует тщательного обдумывания процесса свертывания схемы и связей связывания в схеме.
Одно слово, чтобы описать это: Абсолют~
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
Революционный прогресс в технологии доказательства с нулевым разглашением: углубленное исследование алгоритма Nova
Некоторое время назад я переводил книгу о технологии доказательства с нулевым разглашением. Основной контент был переведен в конце прошлого месяца. Перевод занял гораздо больше времени, чем я ожидал. В настоящее время мы обсуждаем с автором некоторые технические ошибки в книге и готовимся к окончательному варианту.
В любом случае, у меня наконец-то появилось время взглянуть на что-то новое. Начнем с алгоритма Nova~
Информация, связанная с алгоритмом Nova
Три части информации могут помочь понять алгоритм Nova:
Эта статья представляет собой понимание и обобщение приведенной выше информации. **Некоторые изображения в этой статье взяты из приведенной выше информации и не будут помечены в этой статье по одному. **
Начните с IVC
Алгоритм Nova — это новый алгоритм доказательства с нулевым разглашением для IVC (инкрементно проверяемые вычисления). IVC, то есть одна и та же функция итеративно вычисляет предыдущий результат как следующий вход. Итерационный процесс вычисления F-функции выглядит следующим образом:
z0 — это первоначальные входные данные, а результат, полученный в результате вычисления F-функции, используется в качестве входных данных следующей F-функции.
Расслабьтесь R1CS и ослабьте обязательства R1CS
Как мы все знаем, R1CS — это представление схемных ограничений в технологии доказательства с нулевым разглашением. Расслабленный R1CS можно рассматривать как расширенную форму R1CS. На основе R1CS добавляются скаляр u и вектор ошибок E. Экземпляр ослабленного R1CS представлен (E, u, x).
Ослабленное обязательство R1CS фиксирует векторы E и W на основе ослабленного R1CS. Пример слабого обязательства R1CS представлен как (\bar{E}, u, \bar{W}, x), где x и u — общедоступные переменные.
Расширение от R1CS до расслабленного R1CS для схемы складывания. Обратите внимание, что с точки зрения расслабленного R1CS, R1CS является его частным случаем. Другими словами, R1CS также является «особым» вариантом R1CS.
Схема складывания
Интуитивно говоря, схема свертывания отношения R заключается в «коллапсировании» двух экземпляров, соответствующих отношению R, в новый экземпляр составного отношения R. Slack R1CS/Relax Commitment R1CS может выполнять аналогичные складки. Процесс складывания в обоих случаях одинаков. Схема складывания Slack Commitment R1CS следующая:
Вся схема складывания состоит из 4 шагов. На первом этапе проверяющий P отправляет проверяющему обязательство \bar{T} перекрестного элемента T. На втором этапе проверяющий отправляет проверяющему случайный запрос r. Третий шаг — это сложение обязательств, которые должны выполнить и доказывающий, и проверяющий. На четвертом этапе доказывающая программа работает самостоятельно и складывает векторы E и W двух экземпляров.
Дополненная функция F' (Аргументированная функция)
Схема свертывания: свернутый экземпляр R1CS ослаблен. Итак, какие же расчеты подтверждаются этими расслабленными примерами R1CS? Очевидно, что эти расчеты включают в себя расчеты складывания. Эти вычисления представляют собой не просто функцию F в вычислениях IVC, их еще называют дополненными функциями F'. Расчет расширенной функции F' в основном состоит из двух частей:
1/F функция в IVC
2/ Складной расчет экземпляра R1CS
Идеальный вид
Имея вышеизложенное понимание, вы можете представить себе процесс складывания:
Среди них схема — это схема, соответствующая дополненной функции F'. acc{1,2,3,4,5,6} — это экземпляр R1CS со слабым обязательством. Схема имеет два расчета: 1/Расслабить свертывание экземпляра обязательства R1CS, например, acc1+acc2->acc3. 2/Вычислить функцию F, меняя состояние с состояния1 на состояние2, а затем с состояния2 на состояние3 и т. д.
Обратите внимание, что схема, соответствующая расширенной функции F', сама является экземпляром R1CS, который можно выразить как расслабленный экземпляр R1CS. На картинке это акк4 и акк6. «Суммирование» означает преобразование слабого экземпляра R1CS в слабый зафиксированный экземпляр R1CS.
Внимательно взглянув на вход второй схемы, acc3 — это экземпляр R1CS с ослабленным обязательством после фолдинга, а acc4 — это экземпляр R1CS с ослабленным обязательством, который доказывает, что acc3 — правильный результат фолдинга. Эти два экземпляра войдут в следующую складку и сгенерируют acc5. Вы можете себе представить, что если acc3 и acc4 являются экземплярами R1CS с выполнимыми слабыми обязательствами, это означает, что acc3 состоит из двух экземпляров R1CS с выполнимыми слабыми обязательствами. Такую надежность можно вывести шаг за шагом «вперед», доказывая тем самым, что расчет F-функции в каждой схеме верен. В общем, благодаря выполнимости двух экземпляров R1CS с слабым обязательством, соответствующих определенной схеме, можно доказать правильность всех предыдущих вычислений IVC.
Настоящий вид
Друзья, знакомые с доказательствами с нулевым разглашением, знают, что эллиптические кривые часто используются в схемах полиномиальных обязательств. Соответствующее полиномиальное обязательство в скалярной области представлено базовой областью эллиптической кривой. Схемы R1CS обычно представляются скалярной областью. Посмотрите внимательно: «подведение итогов» на картинке выше подразумевает преобразование домена. То есть, если вы хотите свернуть экземпляр R1CS со слабой фиксацией, соответствующий схеме, вы должны «свернуть» его в другой схеме. В это время необходимо ввести цикл эллиптической кривой. Между двумя или более эллиптическими кривыми скалярная область одной кривой такая же, как базовая область другой кривой. По совпадению, скалярная область этой кривой такая же, как и базовая область предыдущей кривой. Используя такую петлю эллиптической кривой, можно реализовать «идеальный вид»:
Весь процесс складывания разделен на два контура складывания. Верхнюю часть можно назвать сгибом Контура 1, а нижнюю часть можно назвать сгибом Контура 2. Формальное представление взаимосвязи между двумя схемами находится на странице 8 статьи «Потенциальные атаки на Nova и соответствующие исправления». U представляет свернутый экземпляр, а u представляет расслабленный экземпляр, соответствующий экземпляру R1CS. Обратите внимание, что схема 1 сворачивает экземпляр R1CS с неактивным обязательством, соответствующий схеме 2, а схема 2 сворачивает экземпляр R1CS с неактивным обязательством, соответствующий схеме 1. Основная цель схемы 2 — свернуть экземпляр R1CS с слабым обязательством, соответствующий схеме 1, и вычисление функции в ее схеме бессмысленно. Вместо этого функция F реализована в схеме 1. В сочетании с «идеальным внешним видом» мы можем примерно догадаться о выполнимости U{i+2}^2, u{i+2}^1, u{i+2}^2, U{i+2}^1. является важной частью доказательства.
Потому что «контур» разрезается на две части, и соответствующий контур складывается в другой контур. Существует несколько проблем привязки между экземплярами: привязка между экземплярами u и U и привязка экземпляров u, проходящих между двумя цепями. Чтобы решить эти проблемы привязки, в схему вводятся общедоступные переменные x_0/x_1, где x_1 определяет выходной экземпляр U схемы, привязанный к экземпляру u, и выход текущей функции F (чтобы упростить структуру схемы, не отраженную на рисунке). Вы думаете, что если в схему введен результат H_1 экземпляра U, если экземпляр u выполним, то x_0/x_1 одновременно реален и надежен, то есть он «привязан» к U. x_0 устанавливает связь между входом u и U, а x_1 устанавливает связь между выходом u и U.
Например, когда u{i+1}^1 используется в качестве входа второй половины схемы, он проходит через схему 2, а его выход u{i+1}^2.x0 = u{i+1 }^1.x1, поэтому при входе в верхнюю часть схемы, если u{i+1}^2 может быть удовлетворено, то его x_0 должно быть равно результату H1 из U_{i +1}^2. Это проверяется в схеме 1. Таким образом, гарантируется, что правильный экземпляр передается между двумя цепями.
Подтверждение IVC
Чтобы доказать, что IVC рассчитывается правильно на определенной итерации, необходимо логически доказать следующую информацию:
Помимо доказательства того, что четыре экземпляра могут быть удовлетворены, также необходимо доказать связь привязки между двумя x1, как показано на следующем рисунке:
Верна ли эта информация, требует дополнительного доказательства реализации схемы. То есть доказательство расчета ВАХ является доказательством схемы. Вполне возможно, что если это расчет со многими итерациями, то эти итерации изначально необходимо выполнять в схеме одну за другой, но теперь необходимо проверить только четыре экземпляра схемы на выполнимость и связующие отношения. Улучшение производительности огромно.
Коррекция атак и алгоритмов
Глядя на картинку выше, я интуитивно чувствую, что экземпляры верхнего и нижнего контуров «отдельны» и не имеют никакой привязки. Собственно, так и строится атака.
Поддельные U_i^1 и U{i+1}^2, хотя и поддельные, но являются выполнимыми экземплярами. Создайте u{i+1}^1, измените x_0 и x_1, чтобы они соответствовали подделанному экземпляру U. Очевидно, экземпляр u{i+1}^1 не удовлетворен. Хотя это и не удовлетворено, схема схемы 2 все еще может быть удовлетворена, но выходной экземпляр U{i+1}^1 не удовлетворен. Если u{i+1}^2 успешно построено, схема 1 может построить удовлетворительные u{i+2}^1 и U_{i+2}^2 и удовлетворить отношения привязки x1. Таким образом, сначала строится половина окончательного доказательства подделки. Благодаря симметрии можно построить выходной экземпляр нижней половины. «Соединив» результаты двух построений, можно подделать доказательство расчета ВАХ.
Пересмотренная логика проверки выглядит следующим образом:
Глава 6 статьи «Потенциальные атаки на Nova и соответствующие исправления» содержит подробный анализ безопасности. Заинтересованные друзья могут самостоятельно проверить оригинал статьи.
Основная идея Nova — складывать экземпляры схемы по схеме сгиба. Логика довольно запутанная и требует тщательного обдумывания процесса свертывания схемы и связей связывания в схеме.
Одно слово, чтобы описать это: Абсолют~