У цій статті детально аналізується алгоритм MSM, алгоритм додавання точок еліптичної кривої, алгоритм множення Монтгомері тощо, а також порівнюється різниця в продуктивності між GPU та FPGA у додаванні точок кривої BLS12_381.
Автор: Стар Лі
Все ширше використовується технологія підтвердження нульових знань, наприклад підтвердження конфіденційності, підтвердження обчислень, підтвердження консенсусу тощо. У пошуках нових і кращих сценаріїв застосування багато людей поступово виявили, що доказ нульового знання доводить, що продуктивність є вузьким місцем. Команда Trapdoor Tech з 2019 року глибоко досліджує технологію з нульовим знанням і досліджує ефективні рішення для прискорення з нульовим знанням. GPU або FPGA є відносно поширеними платформами для прискорення, які зараз є на ринку. Ця стаття починається з обчислення MSM і аналізує переваги та недоліки FPGA та GPU прискореного обчислення з нульовим розпізнаванням.
TL;DR
ЗКП – це технологія з широкими перспективами на майбутнє. Все більше і більше додатків використовують технологію підтвердження нульового знання. Однак існує багато алгоритмів ZKP, і різні проекти використовують різні алгоритми ZKP. У той же час, обчислювальна продуктивність доказу ZKP відносно низька. У цьому документі детально аналізується алгоритм MSM, алгоритм додавання точок еліптичної кривої, алгоритм множення Монтгомері тощо, а також порівнюється різниця в продуктивності між GPU та FPGA у додаванні точок кривої BLS12_381. Загалом, з точки зору ZKP proof computing, короткочасний GPU має очевидні переваги, високу пропускну здатність, високу вартість, програмованість тощо. Умовно кажучи, FPGA має певні переваги в енергоспоживанні. У довгостроковій перспективі можуть бути мікросхеми FPGA, придатні для розрахунків ZKP, або мікросхеми ASIC, налаштовані для ZKP.
Комплекс алгоритмів ЗКП
ZKP — загальний термін для технології Zero Knowledge Proof (Доказ нульового знання). В основному існує дві класифікації: zk-SNARK і zk-STARK. Поточними поширеними алгоритмами zk-SNARK є Groth16, PLONK, PLOOKUP, Marlin і Halo/Halo2. Ітерація алгоритму zk-SNARK відбувається в основному в двох напрямках: 1/чи потрібна довірена установка 2/продуктивність структури схеми. Перевага алгоритму zk-STARK полягає в тому, що довірене налаштування не потрібне, але обчислення перевірки є логарифмічним.
Що стосується застосування алгоритму zk-SNARK/zk-STARK, то алгоритми підтвердження нульового знання, які використовуються різними проектами, відносно розкидані. У застосуванні алгоритму zk-SNARK, оскільки алгоритм PLONK/Halo2 є універсальним (не потребує довіреного налаштування), може бути все більше застосувань.
PLONK підтверджує обсяг обчислень
На прикладі алгоритму PLONK проаналізуйте суму обчислення доказу PLONK.
Розрахункова сума доказової частини PLONK складається з чотирьох частин:
1/ MSM - Багаторазове скалярне множення. MSM часто використовується для обчислення поліноміальних зобов’язань.
2/ Обчислення NTT – поліноміальне перетворення між значенням точки та представленням коефіцієнта.
3/ Обчислення поліномів - додавання, віднімання, множення та ділення поліномів. Поліноміальне оцінювання (uation) тощо.
4/ Circuit Synthesize - синтез схеми. Розрахунок цієї частини пов’язаний із масштабом/складністю схеми.
Взагалі кажучи, кількість обчислень у частині Circuit Synthesize — це більше судження та логіка циклу, а ступінь паралелізму є відносно низьким, що більше підходить для обчислень ЦП. Загалом, прискорення з підтвердженням нульового знання зазвичай стосується прискорення обчислень перших трьох частин. Серед них розрахункова кількість ЧСЧ відносно найбільша, за нею йде НТТ.
Що таке ЧСЧ
MSM (множинне скалярне множення) відноситься до певного ряду точок і скалярів на еліптичній кривій і обчислює точки, що відповідають результатам додавання цих точок.
Наприклад, задано ряд точок на еліптичній кривій:
Дано фіксований набір точок еліптичної кривої з однієї заданої кривої:
[G_1, G_2, G_3, ..., G_n]
і випадкові коефіцієнти:
і випадково відібрані кінцеві елементи поля з заданого скалярного поля:
[s_1, s_2, s_3, ..., s_n]
MSM — це розрахунок для отримання точки еліптичної кривої Q:
Q = \sum_{i=1}^{n}s_i*G_i
Для оптимізації розрахунку MSM у промисловості зазвичай використовується алгоритм Піппенгера. Подивіться уважніше на принципову схему процесу алгоритму Піппенгера:
Процес обчислення алгоритму Піппенгера ділиться на два етапи:
1/ Скалярний розділений на Windows. Якщо Scalar становить 256 біт, а вікно — 8 біт, то всі скаляри поділяються на 256/8=32 Windows. Кожен шар Window використовує «Відра» для тимчасового зберігання проміжних результатів. GW_x – точка накопичення результату на одному шарі. Обчислення GW_x також відносно просте. Воно по черзі обходить кожен скаляр у шарі, використовує значення скалярного шару як індекс і додає відповідний G_x до відповідних сегментів. Насправді принцип відносно простий.Якщо коефіцієнти додавання двох точок однакові, спочатку додайте дві точки, а потім знову додайте скаляр, замість того, щоб двічі додавати дві точки перед додаванням скаляра.
2/ Бали, підраховані кожним вікном, накопичуються шляхом подвійного додавання, щоб отримати остаточний результат.
Алгоритм Піппенгера також має багато алгоритмів оптимізації деформації. У будь-якому випадку основним обчисленням алгоритму MSM є додавання точок на еліптичній кривій. Різні алгоритми оптимізації відповідають різній кількості доданих балів.
Додавання точки еліптичної кривої (Додавання точки)
На цьому сайті ви можете переглянути різноманітні алгоритми додавання точок на еліптичних кривих із «короткою формою Вейєрштрасса».
Припускаючи, що проекційні координати двох точок дорівнюють (x1, y1, z1) і (x2, y2, z2) відповідно, результат додавання точок (x3, y3, z3) можна обчислити за такою формулою обчислення.
Причина детального опису процесу обчислення полягає в тому, щоб показати, що весь процес обчислення складається здебільшого з цілочисельних операцій. Розрядність цілого числа залежить від параметрів еліптичної кривої. Укажіть розрядність деяких поширених еліптичних кривих:
BN256 - 256 біт
BLS12_381 - 381 біт
BLS12_377 - 377 біт
Особлива увага, що ці цілі операції є операціями над полем модуля. Модульне додавання/віднімання за модулем відносно просте, зосередьтеся на принципі та реалізації модульного множення.
模乘（Модульне множення）
Дано два значення над полем модуля: x і y. Обчислення модульного множення відноситься до x*y mod p. Зверніть увагу, що розрядність цих цілих чисел є розрядністю еліптичної кривої. Класичним алгоритмом модульного множення є множення Монтгомері (MontgomeryMulplication). Перш ніж виконувати множення Монтгомері, множене потрібно перетворити на представлення Монтгомері:
Формула для розрахунку множення Монтгомері така:
Існує багато алгоритмів реалізації множення Монтгомері: CIOS (Грубо інтегроване сканування операндів), FIOS (Тонко інтегроване сканування операндів), FIPS (Тонко інтегроване сканування продукту) і так далі. Ця стаття не описує детально різні реалізації алгоритмів, і зацікавлені читачі можуть самостійно дослідити.
Щоб порівняти різницю в продуктивності між FPGA і GPU, виберіть найпростіший метод реалізації алгоритму:
Простіше кажучи, модульний алгоритм множення можна розділити на два обчислення: множення великих чисел і додавання великих чисел. Зрозумівши логіку обчислення MSM, ви можете вибрати продуктивність модульного множення (пропускна здатність), щоб порівняти продуктивність FPGA і GPU.
Спостерігайте і думайте
За такої конструкції FPGA можна оцінити, що весь VU9P може забезпечити пропускну здатність у точках еліптичної кривої BLS12_381. Додавання точок (спосіб add_mix) вимагає приблизно 12 модульних множень. Системний годинник FPGA становить 450M.
За того самого алгоритму модульного множення/додавання модуля, з використанням того самого алгоритму додавання точок, пропускна здатність точки плюс пропускна здатність Nvidia 3090 (з урахуванням факторів передачі даних) перевищує 500 М/с. Звичайно, весь розрахунок включає різноманітні алгоритми, деякі алгоритми можуть бути придатними для FPGA, а деякі алгоритми підходять для GPU. Причиною використання однакового алгоритму порівняння є порівняння основних обчислювальних можливостей FPGA і GPU.
Базуючись на наведених вище результатах, узагальніть порівняння між GPU та FPGA з точки зору перевірки ZKP:
Підведіть підсумки
Все більше і більше додатків використовують технологію підтвердження нульового знання. Однак існує багато алгоритмів ZKP, і різні проекти використовують різні алгоритми ZKP. З нашого практичного інженерного досвіду, FPGA є варіантом, але GPU наразі є економічно ефективним варіантом. FPGA надає перевагу детермінованим обчисленням, які мають переваги затримки та енергоспоживання. Графічний процесор має високу програмованість, має відносно зрілу високопродуктивну обчислювальну структуру, має короткий цикл ітерації розробки та надає перевагу сценаріям пропускної здатності.
Переглянути оригінал
Контент має виключно довідковий характер і не є запрошенням до участі або пропозицією. Інвестиційні, податкові чи юридичні консультації не надаються. Перегляньте Відмову від відповідальності , щоб дізнатися більше про ризики.
Стаття, щоб зрозуміти переваги та недоліки FPGA та GPU, прискорених обчислень з нульовим знанням.
Автор: Стар Лі
Все ширше використовується технологія підтвердження нульових знань, наприклад підтвердження конфіденційності, підтвердження обчислень, підтвердження консенсусу тощо. У пошуках нових і кращих сценаріїв застосування багато людей поступово виявили, що доказ нульового знання доводить, що продуктивність є вузьким місцем. Команда Trapdoor Tech з 2019 року глибоко досліджує технологію з нульовим знанням і досліджує ефективні рішення для прискорення з нульовим знанням. GPU або FPGA є відносно поширеними платформами для прискорення, які зараз є на ринку. Ця стаття починається з обчислення MSM і аналізує переваги та недоліки FPGA та GPU прискореного обчислення з нульовим розпізнаванням.
TL;DR
ЗКП – це технологія з широкими перспективами на майбутнє. Все більше і більше додатків використовують технологію підтвердження нульового знання. Однак існує багато алгоритмів ZKP, і різні проекти використовують різні алгоритми ZKP. У той же час, обчислювальна продуктивність доказу ZKP відносно низька. У цьому документі детально аналізується алгоритм MSM, алгоритм додавання точок еліптичної кривої, алгоритм множення Монтгомері тощо, а також порівнюється різниця в продуктивності між GPU та FPGA у додаванні точок кривої BLS12_381. Загалом, з точки зору ZKP proof computing, короткочасний GPU має очевидні переваги, високу пропускну здатність, високу вартість, програмованість тощо. Умовно кажучи, FPGA має певні переваги в енергоспоживанні. У довгостроковій перспективі можуть бути мікросхеми FPGA, придатні для розрахунків ZKP, або мікросхеми ASIC, налаштовані для ZKP.
Комплекс алгоритмів ЗКП
ZKP — загальний термін для технології Zero Knowledge Proof (Доказ нульового знання). В основному існує дві класифікації: zk-SNARK і zk-STARK. Поточними поширеними алгоритмами zk-SNARK є Groth16, PLONK, PLOOKUP, Marlin і Halo/Halo2. Ітерація алгоритму zk-SNARK відбувається в основному в двох напрямках: 1/чи потрібна довірена установка 2/продуктивність структури схеми. Перевага алгоритму zk-STARK полягає в тому, що довірене налаштування не потрібне, але обчислення перевірки є логарифмічним.
Що стосується застосування алгоритму zk-SNARK/zk-STARK, то алгоритми підтвердження нульового знання, які використовуються різними проектами, відносно розкидані. У застосуванні алгоритму zk-SNARK, оскільки алгоритм PLONK/Halo2 є універсальним (не потребує довіреного налаштування), може бути все більше застосувань.
PLONK підтверджує обсяг обчислень
На прикладі алгоритму PLONK проаналізуйте суму обчислення доказу PLONK.
Розрахункова сума доказової частини PLONK складається з чотирьох частин:
1/ MSM - Багаторазове скалярне множення. MSM часто використовується для обчислення поліноміальних зобов’язань.
2/ Обчислення NTT – поліноміальне перетворення між значенням точки та представленням коефіцієнта.
3/ Обчислення поліномів - додавання, віднімання, множення та ділення поліномів. Поліноміальне оцінювання (uation) тощо.
4/ Circuit Synthesize - синтез схеми. Розрахунок цієї частини пов’язаний із масштабом/складністю схеми.
Взагалі кажучи, кількість обчислень у частині Circuit Synthesize — це більше судження та логіка циклу, а ступінь паралелізму є відносно низьким, що більше підходить для обчислень ЦП. Загалом, прискорення з підтвердженням нульового знання зазвичай стосується прискорення обчислень перших трьох частин. Серед них розрахункова кількість ЧСЧ відносно найбільша, за нею йде НТТ.
Що таке ЧСЧ
MSM (множинне скалярне множення) відноситься до певного ряду точок і скалярів на еліптичній кривій і обчислює точки, що відповідають результатам додавання цих точок.
Наприклад, задано ряд точок на еліптичній кривій:
Дано фіксований набір точок еліптичної кривої з однієї заданої кривої:
[G_1, G_2, G_3, ..., G_n]
і випадкові коефіцієнти:
і випадково відібрані кінцеві елементи поля з заданого скалярного поля:
[s_1, s_2, s_3, ..., s_n]
MSM — це розрахунок для отримання точки еліптичної кривої Q:
Q = \sum_{i=1}^{n}s_i*G_i
Для оптимізації розрахунку MSM у промисловості зазвичай використовується алгоритм Піппенгера. Подивіться уважніше на принципову схему процесу алгоритму Піппенгера:
Процес обчислення алгоритму Піппенгера ділиться на два етапи:
1/ Скалярний розділений на Windows. Якщо Scalar становить 256 біт, а вікно — 8 біт, то всі скаляри поділяються на 256/8=32 Windows. Кожен шар Window використовує «Відра» для тимчасового зберігання проміжних результатів. GW_x – точка накопичення результату на одному шарі. Обчислення GW_x також відносно просте. Воно по черзі обходить кожен скаляр у шарі, використовує значення скалярного шару як індекс і додає відповідний G_x до відповідних сегментів. Насправді принцип відносно простий.Якщо коефіцієнти додавання двох точок однакові, спочатку додайте дві точки, а потім знову додайте скаляр, замість того, щоб двічі додавати дві точки перед додаванням скаляра.
2/ Бали, підраховані кожним вікном, накопичуються шляхом подвійного додавання, щоб отримати остаточний результат.
Алгоритм Піппенгера також має багато алгоритмів оптимізації деформації. У будь-якому випадку основним обчисленням алгоритму MSM є додавання точок на еліптичній кривій. Різні алгоритми оптимізації відповідають різній кількості доданих балів.
Додавання точки еліптичної кривої (Додавання точки)
На цьому сайті ви можете переглянути різноманітні алгоритми додавання точок на еліптичних кривих із «короткою формою Вейєрштрасса».
Припускаючи, що проекційні координати двох точок дорівнюють (x1, y1, z1) і (x2, y2, z2) відповідно, результат додавання точок (x3, y3, z3) можна обчислити за такою формулою обчислення.
Причина детального опису процесу обчислення полягає в тому, щоб показати, що весь процес обчислення складається здебільшого з цілочисельних операцій. Розрядність цілого числа залежить від параметрів еліптичної кривої. Укажіть розрядність деяких поширених еліптичних кривих:
模乘（Модульне множення）
Дано два значення над полем модуля: x і y. Обчислення модульного множення відноситься до x*y mod p. Зверніть увагу, що розрядність цих цілих чисел є розрядністю еліптичної кривої. Класичним алгоритмом модульного множення є множення Монтгомері (MontgomeryMulplication). Перш ніж виконувати множення Монтгомері, множене потрібно перетворити на представлення Монтгомері:
Формула для розрахунку множення Монтгомері така:
Існує багато алгоритмів реалізації множення Монтгомері: CIOS (Грубо інтегроване сканування операндів), FIOS (Тонко інтегроване сканування операндів), FIPS (Тонко інтегроване сканування продукту) і так далі. Ця стаття не описує детально різні реалізації алгоритмів, і зацікавлені читачі можуть самостійно дослідити.
Щоб порівняти різницю в продуктивності між FPGA і GPU, виберіть найпростіший метод реалізації алгоритму:
Простіше кажучи, модульний алгоритм множення можна розділити на два обчислення: множення великих чисел і додавання великих чисел. Зрозумівши логіку обчислення MSM, ви можете вибрати продуктивність модульного множення (пропускна здатність), щоб порівняти продуктивність FPGA і GPU.
Спостерігайте і думайте
За такої конструкції FPGA можна оцінити, що весь VU9P може забезпечити пропускну здатність у точках еліптичної кривої BLS12_381. Додавання точок (спосіб add_mix) вимагає приблизно 12 модульних множень. Системний годинник FPGA становить 450M.
За того самого алгоритму модульного множення/додавання модуля, з використанням того самого алгоритму додавання точок, пропускна здатність точки плюс пропускна здатність Nvidia 3090 (з урахуванням факторів передачі даних) перевищує 500 М/с. Звичайно, весь розрахунок включає різноманітні алгоритми, деякі алгоритми можуть бути придатними для FPGA, а деякі алгоритми підходять для GPU. Причиною використання однакового алгоритму порівняння є порівняння основних обчислювальних можливостей FPGA і GPU.
Базуючись на наведених вище результатах, узагальніть порівняння між GPU та FPGA з точки зору перевірки ZKP:
Підведіть підсумки
Все більше і більше додатків використовують технологію підтвердження нульового знання. Однак існує багато алгоритмів ZKP, і різні проекти використовують різні алгоритми ZKP. З нашого практичного інженерного досвіду, FPGA є варіантом, але GPU наразі є економічно ефективним варіантом. FPGA надає перевагу детермінованим обчисленням, які мають переваги затримки та енергоспоживання. Графічний процесор має високу програмованість, має відносно зрілу високопродуктивну обчислювальну структуру, має короткий цикл ітерації розробки та надає перевагу сценаріям пропускної здатності.