Деякий час тому я перекладав книгу про технологію з нульовим знанням. Основний вміст було перекладено наприкінці минулого місяця. Переклад зайняв набагато більше часу, ніж я очікував. Зараз ми обговорюємо з автором деякі описки в книзі та готуємо остаточний варіант.
У всякому разі, я нарешті маю час подивитися на щось нове. Почнемо з алгоритму Nova~
Інформація про алгоритм Nova
Три частини інформації можуть допомогти зрозуміти алгоритм Nova:
Нова папір:
Потенційні атаки Nova та відповідні виправлення:
Резюме розуміння потенційних атак Nova:
Ця стаття є розумінням і підсумком наведеної вище інформації. **Деякі зображення в цій статті взяті з наведеної вище інформації та не будуть позначені окремо в цій статті. **
Почати з IVC
Алгоритм Nova — це новий алгоритм із нульовим знанням для IVC (обчислення з поетапною перевіркою). IVC, тобто та сама функція ітеративно обчислює попередній вихід як наступний вхід. Ітеративний процес обчислення функції F виглядає наступним чином:
z0 є початковим введенням, а результат, згенерований обчисленням F-функції, використовується як вхід для наступної F-функції.
Relax R1CS і Slack Commitment 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. Це acc4 і acc6 на зображенні. "summarize" означає перетворення примірника slack R1CS у зафіксований примірник R1CS.
Уважно подивившись на вхідні дані другого контуру, acc3 — це екземпляр R1CS з пом’якшеним зобов’язанням після згортання, а acc4 — це екземпляр R1CS із послабленим зобов’язанням, який доводить, що acc3 — це правильний результат згортання. Ці два екземпляри увійдуть до наступного згортання та згенерують acc5. Ви можете собі уявити, що якщо acc3 і acc4 є виконуваними екземплярами R1CS зобов’язань із затримкою, це означає, що acc3 складено з двох екземплярів R1CS із задовільними зобов’язаннями. Іншими словами, acc1 і acc2 є здійсненними зобов’язаннями R1CS. Цей вид надійності можна вивести «вперед» крок за кроком, таким чином доводячи, що розрахунок функції F у кожній ланцюзі правильний. Загалом, завдяки виконанню двох екземплярів R1CS зобов’язань із затримкою, що відповідають певній схемі, можна підтвердити правильність усіх попередніх розрахунків IVC.
Реальний вигляд
Друзі, які знайомі з доказами з нульовим знанням, знають, що еліптичні криві часто використовуються в поліноміальних схемах зобов’язань. Відповідне поліноміальне зобов'язання на скалярній області представлено базовою областю еліптичної кривої. Схеми R1CS зазвичай представлені скалярною областю. Подивіться уважно, «резюмування» на зображенні вище передбачає перетворення домену. Тобто, якщо ви хочете згорнути екземпляр R1CS зобов’язання, що відповідає схемі, ви повинні «згорнути» його в іншій схемі. У цей час потрібно ввести цикл еліптичної кривої. Між двома або більше еліптичними кривими скалярна область однієї кривої така ж, як базова область іншої кривої. За збігом обставин скалярна область цієї кривої така сама, як базова область попередньої кривої. Використовуючи таку петлю еліптичної кривої, можна реалізувати «ідеальний вигляд»:
Весь процес складання розділений на два цикли складання. Верхню частину можна назвати складкою контуру 1, а нижню частину можна назвати складкою контуру 2. Формальне представлення зв’язку між двома схемами наведено на сторінці 8 статті «Потенційні атаки на Nova та відповідні виправлення». U представляє згорнутий екземпляр, а u представляє розслаблений екземпляр, що відповідає екземпляру R1CS. Зауважте, що Circuit 1 згортає екземпляр R1CS із тимчасовим зобов’язанням, що відповідає Circuit 2, тоді як Circuit 2 згортає екземпляр R1CS із тимчасовим зобов’язанням, що відповідає Circuit 1. Основна мета Circuit 2 полягає в тому, щоб згорнути екземпляр R1CS зобов’язання, що відповідає Circuit1, і обчислення функції в його схемі є безглуздим. Замість цього функція 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, як показано на наступному малюнку:
Для перевірки правильності цієї інформації потрібна додаткова перевірка схеми. Тобто доказ розрахунку IVC є доказом схеми. Цілком можливо, що якщо це обчислення з багатьма ітераціями, ці ітерації спочатку повинні виконуватися в схемі одну за одною, але тепер лише чотири екземпляри схеми повинні бути перевірені на виконуваність і зв’язки. Покращення продуктивності величезне.
Атака та виправлення алгоритму
Дивлячись на картинку вище, у мене є інтуїція. Я відчуваю, що екземпляри верхнього та нижнього контурів «розділені» і не мають зв’язку. Власне, так і побудована атака.
Підроблені 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. Таким чином спочатку створюється половина остаточного доказу підробки. Завдяки симетрії вихідний екземпляр нижньої половини може бути побудований. «З’єднавши» результати двох побудов, можна підробити доказ розрахунку IVC.
Переглянута логіка перевірки така:
Розділ 6 статті «Потенційні атаки на Nova та відповідні виправлення» містить детальний аналіз безпеки. Зацікавлені друзі можуть самостійно перевірити оригінал паперу.
Основна ідея Nova полягає в складанні екземплярів схеми за схемою згортання. Логіка досить заплутана і вимагає ретельного обдумування процесу згортання схеми та зв’язувальних зв’язків у схемі.
Одне слово, щоб описати це: Абсолют ~
Переглянути оригінал
Ця сторінка може містити контент третіх осіб, який надається виключно в інформаційних цілях (не в якості запевнень/гарантій) і не повинен розглядатися як схвалення його поглядів компанією Gate, а також як фінансова або професійна консультація. Див. Застереження для отримання детальної інформації.
Революційний прогрес у технології підтвердження нульового знання: поглиблене дослідження алгоритму Nova
Деякий час тому я перекладав книгу про технологію з нульовим знанням. Основний вміст було перекладено наприкінці минулого місяця. Переклад зайняв набагато більше часу, ніж я очікував. Зараз ми обговорюємо з автором деякі описки в книзі та готуємо остаточний варіант.
У всякому разі, я нарешті маю час подивитися на щось нове. Почнемо з алгоритму Nova~
Інформація про алгоритм Nova
Три частини інформації можуть допомогти зрозуміти алгоритм Nova:
Ця стаття є розумінням і підсумком наведеної вище інформації. **Деякі зображення в цій статті взяті з наведеної вище інформації та не будуть позначені окремо в цій статті. **
Почати з IVC
Алгоритм Nova — це новий алгоритм із нульовим знанням для IVC (обчислення з поетапною перевіркою). IVC, тобто та сама функція ітеративно обчислює попередній вихід як наступний вхід. Ітеративний процес обчислення функції F виглядає наступним чином:
z0 є початковим введенням, а результат, згенерований обчисленням F-функції, використовується як вхід для наступної F-функції.
Relax R1CS і Slack Commitment 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. Це acc4 і acc6 на зображенні. "summarize" означає перетворення примірника slack R1CS у зафіксований примірник R1CS.
Уважно подивившись на вхідні дані другого контуру, acc3 — це екземпляр R1CS з пом’якшеним зобов’язанням після згортання, а acc4 — це екземпляр R1CS із послабленим зобов’язанням, який доводить, що acc3 — це правильний результат згортання. Ці два екземпляри увійдуть до наступного згортання та згенерують acc5. Ви можете собі уявити, що якщо acc3 і acc4 є виконуваними екземплярами R1CS зобов’язань із затримкою, це означає, що acc3 складено з двох екземплярів R1CS із задовільними зобов’язаннями. Іншими словами, acc1 і acc2 є здійсненними зобов’язаннями R1CS. Цей вид надійності можна вивести «вперед» крок за кроком, таким чином доводячи, що розрахунок функції F у кожній ланцюзі правильний. Загалом, завдяки виконанню двох екземплярів R1CS зобов’язань із затримкою, що відповідають певній схемі, можна підтвердити правильність усіх попередніх розрахунків IVC.
Реальний вигляд
Друзі, які знайомі з доказами з нульовим знанням, знають, що еліптичні криві часто використовуються в поліноміальних схемах зобов’язань. Відповідне поліноміальне зобов'язання на скалярній області представлено базовою областю еліптичної кривої. Схеми R1CS зазвичай представлені скалярною областю. Подивіться уважно, «резюмування» на зображенні вище передбачає перетворення домену. Тобто, якщо ви хочете згорнути екземпляр R1CS зобов’язання, що відповідає схемі, ви повинні «згорнути» його в іншій схемі. У цей час потрібно ввести цикл еліптичної кривої. Між двома або більше еліптичними кривими скалярна область однієї кривої така ж, як базова область іншої кривої. За збігом обставин скалярна область цієї кривої така сама, як базова область попередньої кривої. Використовуючи таку петлю еліптичної кривої, можна реалізувати «ідеальний вигляд»:
Весь процес складання розділений на два цикли складання. Верхню частину можна назвати складкою контуру 1, а нижню частину можна назвати складкою контуру 2. Формальне представлення зв’язку між двома схемами наведено на сторінці 8 статті «Потенційні атаки на Nova та відповідні виправлення». U представляє згорнутий екземпляр, а u представляє розслаблений екземпляр, що відповідає екземпляру R1CS. Зауважте, що Circuit 1 згортає екземпляр R1CS із тимчасовим зобов’язанням, що відповідає Circuit 2, тоді як Circuit 2 згортає екземпляр R1CS із тимчасовим зобов’язанням, що відповідає Circuit 1. Основна мета Circuit 2 полягає в тому, щоб згорнути екземпляр R1CS зобов’язання, що відповідає Circuit1, і обчислення функції в його схемі є безглуздим. Замість цього функція 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, як показано на наступному малюнку:
Для перевірки правильності цієї інформації потрібна додаткова перевірка схеми. Тобто доказ розрахунку IVC є доказом схеми. Цілком можливо, що якщо це обчислення з багатьма ітераціями, ці ітерації спочатку повинні виконуватися в схемі одну за одною, але тепер лише чотири екземпляри схеми повинні бути перевірені на виконуваність і зв’язки. Покращення продуктивності величезне.
Атака та виправлення алгоритму
Дивлячись на картинку вище, у мене є інтуїція. Я відчуваю, що екземпляри верхнього та нижнього контурів «розділені» і не мають зв’язку. Власне, так і побудована атака.
Підроблені 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. Таким чином спочатку створюється половина остаточного доказу підробки. Завдяки симетрії вихідний екземпляр нижньої половини може бути побудований. «З’єднавши» результати двох побудов, можна підробити доказ розрахунку IVC.
Переглянута логіка перевірки така:
Розділ 6 статті «Потенційні атаки на Nova та відповідні виправлення» містить детальний аналіз безпеки. Зацікавлені друзі можуть самостійно перевірити оригінал паперу.
Основна ідея Nova полягає в складанні екземплярів схеми за схемою згортання. Логіка досить заплутана і вимагає ретельного обдумування процесу згортання схеми та зв’язувальних зв’язків у схемі.
Одне слово, щоб описати це: Абсолют ~