Алекс Пруден

Запуск фази, що винагороджується Тестнет-3 — Прувери

Сьогодні ми раді оголосити про початок винагороджуваної фази для Testnet 3, що наближає нас на один крок до основної мережі Aleo та підтримки приватних децентралізованих програм. Запрошуємо до участі всіх членів нашої спільноти.

Testnet 3 є значним кроком уперед у порівнянні з Testnet 2. По-перше, він представляє новий алгоритм консенсусу AleoBFT, який поєднує в собі алгоритм консенсусу Proof-of-Stake (заснований на DiemBFT) зі схемою компенсації за роботу для пруверів. У найближчі місяці ми опублікуємо докладнішу інформацію про AleoBFT. Але початкова частина програми винагороди буде зосереджена саме на пруверах.

Роль пруверів в AleoBFT

Хто такі прувери? У криптографії з нульовим розголошенням є дві взаємодіючі сторони: що доводить (прувери) , яка генерує криптографічний доказ, і верифікує , яка перевіряє правильність доказу, не знаючи його змісту. Щоб надсилати/отримувати активи або взаємодіяти з програмою, користувач повинен згенерувати доказ з нульовим розголошенням. У деяких випадках ми очікуємо, що деякі користувачі можуть передати процес створення доказів будь-якій сторонній службі перевірки.

Важливо відзначити, що аутсорсингова генерація доказів не є обов'язковою у нашій мережі, як в інших мережах, таких як StarkNet. Однак ми очікуємо, що для підтримки програм на Aleo з'явиться екосистема пруверів. Принадність цієї системи в тому, що вона максимально розширює вибір користувачів з точки зору того, яким сторонам вони довіряють, якщо є.

Для запуску цієї екосистеми мережа Aleo винагороджує пруверів безпосередньо з протоколу. У AleoBFT прувери можуть отримувати частину винагороди від coinbase за створення доказів, подібних до вихідного алгоритму консенсусу PoSW. Однак є дві важливі відмінності порівняно з тим, як це працювало у Testnet 2.

1. Прувери не виробляють блоки, але вони отримують частину винагороди за кожен блок.

2. Винагорода coinbase не залежить від принципу "переможець отримує все". Всі прувери, що надали рішення для даного блоку вище за мінімальну мету складності, отримують пропорційну частину винагороди.

Протокол AleoBFT використовує варіант алгоритму коригування складності ASERT (такий самий, як у Testnet 2) для обчислення двох цільових значень: докази та coinbase. Рішення прувера приймаються, якщо вони вищі за цільове значення доказу. Як тільки сума рішень прувера перевищує цільове значення coinbase, винагорода від coinbase пропорційно розподіляється між пруверами, які надали дійсні рішення. Таким чином, економіка прувера AleoBFT аналогічна майнінгового пулу у традиційній мережі proof-of-work.

Як реальний приклад давайте уявимо трьох пруверів: Алісу, Боба і Чарлі. Припустимо, що цільове значення coinbase - 1024, а цільове значення доказу - 8. Давайте представимо для 15-секундного періоду, коли виробляється один блок, що:

• Аліса обчислює та надсилає 80 доказів PoSW, які відповідають як мінімум цільовому значенню доказу, що дорівнює 8, на загальну суму 640 балів (62,5% від загальної кількості).

• Боб обчислює 32 докази PoSW, які мають як мінімум цільове значення доказу, що дорівнює 8, що дає загальний бал 256 (25% від загальної кількості).

• Чарлі обчислює 16 доказів PoSW, які мають як мінімум цільове значення доказу, що дорівнює 8, що дає загальний бал 128 (12,5% від загальної кількості).

Аліса, Боб та Чарлі отримають пропорційну частину (62,5%, 25% та 12,5% відповідно) винагороди за цей блок.

Розрахунок винагороди за блок

Ми можемо розрахувати винагороду coinbase за такою формулою:

R_coinbase = max(0, H_Y10 — H) * R_anchor * 2^(-1 * (D — B) / B), де

‍R_anchor = награда за якорь.

H_Y10 = висота анкерного блоку у 10-му році.

H = Поточна висота блоку.

D = час, що минув з попереднього блоку.

B = час блокування прив'язки.

Таким чином, початкова пропозиція токенів Aleo буде збільшуватися за рахунок винагород coinbase протягом приблизно десяти років, і вони будуть лінійно зменшуватися по блоках протягом цього періоду часу. Незабаром ми опублікуємо оновлений пост у блозі про токеноміку основної мережі з більш детальною інформацією.

Ця ж крива емісії діє під час Testnet 3, при цьому блок генези створюється 6 листопада 2022 року. Ми не будемо скидати мережу на початку періоду заохочення. Таким чином, винагорода за блок буде розраховуватись протягом періоду заохочення на основі висоти мережі на початку періоду заохочення (див. нижче).

Нагороди у вигляді токенів за заохочувальний період

Як згадувалося в попередньому повідомленні в блозі, ми виділили 25 мільйонів кредитів Aleo для заохочень Testnet 3. Нагородження для пруверів становлять 30% або 7,5 млн кредитів.

Кредити, зароблені в період винагороди, будуть обмінені на кредити Aleo під час запуску основної мережі за курсом 5:1. Тобто кожні п'ять кредитів Aleo, зароблених протягом винагороди, можна обміняти на один кредит Aleo в основній мережі.

Винагороджуваний період триватиме з 00:00 UTC 2 грудня 2022 р. до 23:59 UTC 26 січня 2023 р. або доти, доки мережа не видасть 7,5 млн кредитів, залежно від того, що настане раніше.

Якщо 8-тижневий період закінчився, і було випущено менше 7,5 млн кредитів, команда Aleo залишає за собою право на свій розсуд розподіляти кредити, що залишилися. Якщо ви запускали ноду до дати запуску та НЕ використовуєте надані сценарії, переконайтеся, що ви перезавантажили свою ноду; в іншому випадку ви не зможете заробити нагороду.

Висновок

Команда Aleo стежитиме за активністю прувера протягом періоду заохочення, щоб виявити будь-кого, хто може намагатися обдурити систему. Якщо ви не дотримуватиметеся наших вказівок, ви не отримаєте винагороди, і в цілому команда Aleo залишає за собою право відмовити у винагороді будь-якій особі з будь-якої причини.

Зауважте, що ці кредити, швидше за все, будуть розподілені під час запуску основної мережі. Вони повинні використовуватися як механізм оплати послуг у мережі Aleo. Вони не є інвестиціями або інвестиційними інструментами, і до них не слід ставитись як до таких; їхня цінність полягає просто в їхній корисності для функціональності основної мережі. Запитуючи свої нагороди, ви заявляєте, гарантуєте та визнаєте, що ви:

• не купувати кредити Aleo як інвестиції та не розраховувати на економічну вигоду або прибуток як власник кредитів Aleo;

• жодним чином не покладатися на Aleo або будь-кого з її співробітників або представників;

• не купувати акції або інші частки участі в Aleo через володіння кредитами Aleo;

• не представляти Aleo Credits у хибному світлі як інвестиції чи можливість отримання економічної вигоди чи прибутку.

Як і у випадку з Testnet 2, ціль цієї загальнодоступної Testnet - перевірити технічну архітектуру та безпеку блокчейна в максимально реалістичних умовах. Aleo вже пройшов кілька аудитів безпеки, але ми вважаємо, що більшість того, що змушує працювати децентралізований консенсус, пов'язана з внутрішніми економічними стимулами.

Щоб дізнатися більше про запуск ноди та участь у програмі заохочення Testnet 3, відвідайте наш репозиторій snarkOS на Github. Дякуємо за участь у Aleo Testnet 3 та за допомогу у тестуванні інфраструктури завтрашньої приватної децентралізованої платформи для приватних додатків!

Генерування zk-SNARK (короткого не інтерактивного аргументу знання з нульовим розголошенням), що використовується в Aleo, включає безліч криптографічних обчислень, майже всі з яких відбуваються всередині еліптичної кривої в кінцевому полі.

Еліптичні криві

Ця стаття – короткий виклад цього матеріалу .

Точка еліптичної кривої - це пара таких чисел (x, y) в кінцевому полі (ви можете розглядати кінцеве поле як Zp , цілі числа по модулю від дуже великого простого числа; хоча іноді все складніше), які задовольняють наступному виразу:

для деяких a та b у кінцевому полі.

Ви можете скласти точки еліптичної кривої, але не традиційним методом. Замість

ми виконуємо наступне:

де:

Для цього виразу є два винятки:

1. Коли (x1, y1) = (x2, y2) .

2. Коли x1 = x2 , але y1 ≠ y2 . У такому разі y1 = −y2 , оскільки іншого рішення немає.

В обох цих випадках наведене вище вираз не визначено (нам довелося б ділити на нуль), тому замість нього ми зробимо таке:

1. Сума точки з самою собою - це, як і раніше, точка (x3, y3) лише в одному випадку:

(Тут a - це коефіцієнт, що визначає наведене вище рівняння кривої).

2. В даному випадку результатом додавання є особлива точка, яку ми довільно додаємо до кривої; вона називається точкою на нескінченності та записується як 0 . Ця точка працює як нуль нашої суми, тобто.

кожної пари (x, y) .

Примітивні операції

Криптографія еліптичних кривих в кінцевому рахунку спирається на дві примітивні операції, складання точок (підсумовування двох різних точок) і подвоєння точок (додавання точки до самої себе), які ми називаємо ECADDі ECDBL.

Якщо ми намагаємось додати точку до самої себе багато разів, ми можемо застосувати алгоритм double-and-add . Як вже пояснювалося в одній з наших статей , ідея проста: якщо ми хочемо обчислити, скажімо, 9P для якоїсь точки P кривою замість виконання 9 докладів ми можемо виконати

P + P = 2P 2P + 2P = 4P 4P + 4P = 8P 4P + P = 9P

— лише 4 операції складання.

Коли нам доводиться складати безліч точок k1P1 + k2P2 + … + knPn , більшість методів припускають, що ці примітиви дані, і зосереджуються на тому, як виконувати скалярні множення kiPi та додавання, мінімізувавши кількість ECADDі ECDBL.

MSM (мульти-скалярне множення)

Завдання мульти-скалярного множення полягає в тому, щоб в даній еліптичній кривій обчислити

для деяких скалярів (цілих чисел по модулю певного простого числа) ki , для деяких точок еліптичної кривої Pi = (xi, yi ) і для когось n (у задачі Aleo воно дорівнює 2²⁶).

Майте на увазі, що операція підсумовування тут та сама, що обговорювалася в попередньому розділі. Аналогічно, kiPi означає " Pi , додане до самого себе ki раз", і сума залишається такою ж, що була наведена вище.

Підраховано, що близько 80% часу генерування доказів zk-SNARK витрачається виконання MSM, тому його оптимізація дуже важлива для продуктивності.

Метод ковзного вікна

Ми можемо розбити MSM на менші суми та скоротити загальну кількість операцій, багаторазово використовуючи метод ковзного вікна . Якщо ми хочемо обчислити кожен твір kiPi , ми можемо розбити його на вікна розміром c

З урахуванням цього, завдання MSM може бути подане у вигляді

Тепер ми можемо змінити порядок додавання

Іншими словами, спочатку ми ділимо скаляри на вікна, а потім поєднуємо всі крапки в кожному вікні. Тепер ми можемо зосередитись на тому, як ефективно обчислити всі Bj :

де підсумовування по u(λ) виконується тільки з точками, коефіцієнт яких дорівнює λ . Наприклад, якщо c = 3 і нам дано 15 точок

ми можемо розділити додавання за коефіцієнтами λ , що приймають значення від 1 до 7. Для λ = 1 : ∑uPu = P4 (бо P4 - єдина точка з коефіцієнтом 1), для λ = 4 : ∑uPu = P1 + P5 і так далі . Таким чином ми просто розставляємо всі крапки із загальним коефіцієнтом λ по λ-вікнах. Отже,

Ми можемо обчислити цей вираз із мінімальною кількістю додавань точок, використовуючи часткові суми.

Кожна така операція містить лише одне складання точок еліптичної кривої. Кінцевий результат може бути обчислений за допомогою додавання часткових сум:

Ми можемо покращити обчислення, змінивши розкладання коефіцієнтів ki . У двійковому поданні вага Хеммінга - це число ненульових бітів; в ідеалі ми хотіли б, щоб ця вага була якнайменша, щоб зменшити кількість сум (Наприклад, 65537, тобто 2¹⁶ + 1 різними способами використовується як публічний ключ для криптосистеми RSA . Алгоритми зведення в квадрат і мультиплікації вимагають лише двох множень ). Середня вага Хеммінга в двійковому поданні дорівнює 1/2; якщо ми введемо двійкове уявлення зі знаком (-1, 0, 1), середня вага знизиться до 1/3 з подальшим зменшенням кількості операцій (у середньому).

BLS 12-377

Крива, яка використовується в Aleo, називається BLS 12-377. Базове поле (кінцеве поле) має порядок q (377-бітне просте число) і має ступінь вкладення 12. І порядок групи G1 еліптичних кривих r і кінцеве поле є 2-адичними числами (це означає, що і q , і r можуть бути записані як (2^α)r + 1, де r - непарне, а α більше 40). Порядки q та r пов'язані ступенем вкладення: r ∣ q¹² − 1 . Рівняння еліптичної кривої:

Додатково ми можемо задати другу групу G2 над квадратичним розширенням поля Fq ; рівняння такої кривої:

де B – параметр. Додаткову інформацію про параметри кривих ви можете знайти тут .

BLS 12–377 біраціонально еквівалентна кривим Монтгомері та скрученим кривим Едвардса . Це дає нам можливість виконувати складання точок та скалярний твір швидше, уникаючи дорогих інверсій поля. У разі кривих Монтгомері можна виконувати скалярні твори за постійний час, що робить цю операцію стійкою до атак за часом .

Реалізації кривої BLS 12-377 та (біраціонально еквівалентної) скрученої кривої Едвардса представлені в даному репозиторії .

BLS 12-377 є однією з кривих, зручних для сполучення; це можна застосовувати для коротких цифрових підписів, які можна ефективно агрегувати, схем поліноміальних зобов'язань та одноразового обміну кількома ключами .

Причина, через яку ми маємо справу з двома рівняннями для кривої BLS і дві групи пов'язані з поєднанням. Сполучення - це білінійне відображення: воно приймає дві точки, кожна з групи простого порядку r . З технічних причин ці групи мають бути різними. Так як початкова крива має тільки одну групу порядку r , нам потрібно зробити розширення поля, щоб мати можливість знайти інші групи порядку r . Ступінь вкладення показує, як нам потрібно розширити поле, щоб знайти інші групи. Як доповнення розширене поле містить у собі всі коріння r ступеня з одиниці .

Примітка для розширення поля

Ступінь вкладення є також і ступенем розширення поля, яке потрібно використовувати. Знайомими прикладами розширення полів є дійсні числа, R (розширення поля раціональних чисел Q , яке є трансцендентальним ) і комплексні числа, C (розширення R ). Останнє не може бути розширено далі, оскільки в C ненаведених багаточленів не існує (ми можемо сказати, що комплексні числа - це замкнене алгебраїчне поле ).

Якщо ми хочемо створити квадратичне розширення Fq , ми можемо його уявити як поліном a0 + a1x , де a0 і a1 — елементи поля Fq . Це додавання є простим, оскільки ми додаємо незалежні та лінійні члени окремо. Для множення із заданими елементами a та b

Щоб уникнути виходу за межі лінійних багаточленів, ми можемо зменшити ступінь, використовуючи багаточлен, що не наводиться, такий як x² + 1 , і встановивши, що x² + 1 = 0 . Якщо ми підставимо це до рівняння вище

що нагадує множення у комплексних числах.

Умови вибору полінома такі:

1. Він повинен мати той самий порядок, що й поле розширення (у разі другий).

2. Він має бути неприведеним у полі, яке ми розширюємо, це означає, що ми не можемо поділити цей багаточлен на поліноми меншою мірою.

Насправді, коли хочемо створити розширення поля Fq12 , ми можемо зробити це, послідовно розширюючи менші поля: використовуючи вежу розширень (таку, як Q → R → C ).

Прискорення за допомогою Карацубі, Тоома-Кука та БПФ

Потенційне застосування БПФ виникає при реалізації примітивів ECADDта ECDBL. Ці операції можуть бути виконані у різних системах координат. Як стверджувалося тут , проективні координати зазвичай набагато швидше, тому що вони дозволяють уникнути інверсії кінцевого поля, яка витрачає набагато більше, ніж множення та додавання.

При використанні проективних координат обчислення виконуються швидше, тому що ми змінюємо поділ на множення. Це означає, що потрібно виконати багато множень, тому нам потрібні ефективні методи для множення цілих чисел, у яких алгоритми Карацуби , Тоома або БПФ можуть стати привабливими, оскільки маємо справу з множенням великих цілих чисел . Оптимальний алгоритм залежатиме від розміру цілих чисел.

Оригінал статті: https://www.entropy1729.com/multiscalar-multiplication/

Короткі не інтерактивні аргументи знання (SNARK) — це потужні криптографічні примітиви, які знаходять своє застосування у децентралізованих фінансах, управлінні та обчисленнях. Існує безліч різних SNARK таких, як Marlin (на якому заснований Aleo), Plonk , STARK , Groth16 і т.д., побудованих на різних інструментах та з різними продуктивністю, розміром доказів, часом перевірки тощо. Проте всі вони ґрунтуються на загальних принципах та властивостях. Серед SNARK найважливішими для приватних програм є SNARK з нульовим розголошенням (скорочено zk-SNARK). Вони дозволяють доводити, що знаємо якісь змінні, звані свідком, w , такі, що вихідне значення функціїF , обчислене у свідку та примірнику (публічних змінних), x , дорівнює F(x, w) = y , не розкриваючи при цьому нічого про w .

Комп'ютерні програми можуть бути перетворені на функції, які приймають вхідні дані (деякі з них, можливо, захочемо приховати), і правильне виконання яких ми доводимо за допомогою SNARK. Наприклад, ми можемо перетворити програму на арифметичну схему, C , і, враховуючи публічні вхідні та вихідні дані, x , і засекречені дані, w , ми можемо довести, що програма була виконана коректно, продемонструвавши здійсненність схеми, C(x, w)= 0 . Оскільки здійснюваність арифметичних схем — це NP-повне завдання , ми можемо звести будь-яке NP-завдання до арифметичної схеми (проте це не єдина альтернатива, і кілька конструкцій спираються на інші техніки).

Перед тим, як перейти до деталей, дозвольте пояснити головні властивості SNARK та дати точні визначення кожного слова у його назві. У zk-SNARK беруть участь дві сторони, що доводить і перевіряє, де перший намагається переконати останнього в цьому твердженні, наприклад, у тому, що той, хто доводить, знає такий w , що C(x, w)=0 . SNARK має задовольняти властивостям:

1. Завершеності: якщо доказуючий знає w , він повинен бути здатний переконати чесного перевіряючого у достовірності затвердження.

2. Надійності: якщо твердження хибне, то жоден обманюючий доводить не зможе переконати перевіряючого прийняти його, за винятком випадків із дуже низькою ймовірністю.

3. Нульового розголошення: доказ не розкриває жодної інформації про свідка.

Що стосується назви:

1. Короткість: докази мають бути короткими та швидко перевіряються. Це дозволило б нам делегувати дорогі обчислення ненадійним сторонам та перевіряти їх достовірність без необхідності запускати програму самостійно.

2. Не інтерактивність: ні для генерації, ні для перевірки доказу не потрібна взаємодія між доказуючим та перевіряючим. Ми побачимо, що спочатку конструкція покладалася на інтерактивні докази, але ми зможемо перетворити їх на не інтерактивні, використовуючи трансформацію Фіата-Шаміра .

3. Аргумент знання: ми можемо довести, що ми знаємо свідка.

   Налаштування

   SNARK вимагають довірене налаштування. Серед її видів ми можемо виділити:

   — Єдиний довідковий рядок, або прозорі налаштування ( URS ).

   — Структурований рядок посилань, або приватне налаштування ( SRS ).

   У випадку SRS ми можемо натрапити на два випадки:

   • Універсальна (наприклад, MARLIN)

   • Конкретна (Groth 16)

   Насправді приватна настройка виконується як багатостороннє обчислення; конструкція буде безпечною доти, доки існує одна чесна сторона. Проблема з конкретними SRS полягає в тому, що рядок залежить від програми, і для кожної з них необхідно виконати нове налаштування (це небажана властивість).

   Імовірнісні докази та можливості перевіряючого

   Короткість аргументу спирається на імовірнісні докази. Щоб це було можливо, ми спочатку маємо встановити те, що відповідає “повноваженням”, чи можливостям перевіряючого. Є:

   — Інтерактивність: перевіряльнику дозволяється взаємодіяти з доказуючим, надсилаючи виклики та отримуючи відповіді.

   — Безліч доказуючих: є кілька доказувачів, але всі вони ізольовані.

   — Випадковість: перевіряючий може вибирати випадкові елементи чи запити.

   — Можливість надсилання запитів до оракулу : перевіряючий може надсилати запити на повідомлення доказуючого.

   Коли у перевіряючого є доступ до більш ніж одного з цих повноважень, ми отримуємо різні види доказів:

   • Інтерактивність + Випадковість: Інтерактивні докази (ІР).

   — Випадковість + Оракул: Докази (PCP), що ймовірно перевіряються.

   • Інтерактивність + Випадковість + Оракул: Інтерактивні докази з оракулом (IOP).

   Є й інші можливі варіанти, наприклад, MIOP, але ми зосередимося попередніх трьох. На даний момент IOP надає найбільш ефективну конструкцію для SNARK: квазілінійний час перевірки, лінійна довжина розміру доказів, лінійний час доказу та ефективні реалізації. PCP цікаві з теоретичної точки зору, але на практиці не ефективні (вони не призводять до коротких доказів, за винятком лінійних запитів). Нарешті IP надають цікаві будівельні блоки у вигляді підпрограм.

   У IOP доводить і перевіряє обмінюються повідомленнями. Той, хто доводить, надсилає довільні повідомлення (в поліноміальному IOP доказуючий відправляє зобов'язання - див. наступний розділ - поліномам), і перевіряючий відправляє випадкові виклики. Після кількох раундів перевіряючий складає запит із кількох змінних і вирішує, прийняти доказ чи ні.

   Схема зобов'язань

   Продуктивність SNARK залежить від типу використаних зобов'язань; За останні роки було зроблено багато кроків щодо їх поліпшення.

   Ми можемо подавати зобов'язання як сейф. Ми робимо якийсь вибір для ставки, кладемо його в сейф та передаємо іншому. Коли оголошено результат, ми можемо розкрити нашу ставку, відкривши сейф.

   Зобов'язання має задовольняти двом властивостям:

   — Зв'язуюче: ми не можемо зробити два вірних відкриття для того самого зобов'язання. Іншими словами, якщо зобов'язання має якесь значення a , повинно бути неможливо знайти такий b , що cm(a) = cm(b) .

   — Приховуюче: зобов'язання не розкриває нічого про зафіксовані дані.

   Один із способів зафіксувати повідомлення - використовувати стійку до колізій хеш-функцію. Якщо нам дані повідомлення m і випадкове значення r , cm(m, r) = hash(m ∣ r) Враховуючи, що вона стійка до колізій, ми отримуємо властивість зв'язування. Потім ми можемо відкрити зобов'язання та перевірити: Verify( m, r, cm ) → прийняти чи відхилити Однією з переваг зобов'язань є те, що вони схильні бути короткими. Наприклад, якщо ми будемо використовувати SHA-256 , довжина доказу дорівнюватиме 32 байтам.

   Одна важлива група зобов'язань – це поліноміальні схеми. Нижче представлені кілька конструкцій та математика, на якій вони ґрунтуються:

   • Базові еліптичні криві : bulletproofs

   • Білінійні групи: поліноміальні зобов'язання Kate-Zaverucha-Goldberg (KZG) (спарювання, довірене налаштування), DORY (без довірчого налаштування)

   • Групи невизначеного порядку: DARK

   • Тільки хеш-функції: FRI

     Анатомія СНАРК

     SNARK може бути сконструйований шляхом вибору наступних двох елементів:

     • Тип імовірнісного доказу: наприклад, доказ, що вірогідно перевіряється (PCP) або інтерактивний доказ з оракулом (IOP). Особливий вид IOP – це поліноміальний IOP (PIOP).

     • Схеми зобов'язань (криптографія). Наприклад, поліноміальні/функціональні зобов'язання, векторні зобов'язання та лінійне кодування.

       Імовірнісний доказ визначає тип обчислення. Можливі варіанти машинного обчислення (наприклад, vmTinyRam) чи схеми.

     Криптографічний елемент визначає вартість генерації доказу, чи буде постквантово безпечним і тип налаштування (прозора або структурована). Математичні інструменти, з якими нам доведеться працювати для кожного з них:

     • Лінійне кодування: Спарювання еліптичних кривих (ECP) + Грати

     — Векторне зобов'язання: стійкий до колізій хеш-функції (CRH) + ECP

     • Поліноміальні зобов'язання: CRH, ECP, PO групи, UO групи

     Деякі рецепти SNARK:

     Лінійне PCP + Лінійне кодування: Groth16, Groth-Maller 17 PCP/IOP + Векторне зобов'язання: STARK Поліноміальне PCP/IOP + Поліноміальне зобов'язання: MARLIN, SONIC, Plonk, Spartan. Bulletproofs використовують кілька різних комбінацій перерахованих вище елементів і засновані на криптографічних перевірках суми.

     Розмір доказу залежить від типу конструкції. Наприклад, для PIOP з поліноміальними зобов'язаннями KZG доказ займає менше ніж 1 КіБ (два елементи еліптичних кривих), тоді як IOP з FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity) – близько 100 КіБ, більш ніж на два порядки більше! Це так, тому що FRI використовує дерева Меркла ; для перевірки потрібен шлях автентифікації, що вимагає кількох хешів.

     Одна з проблем, з якою ми стикаємося в схемах, полягає в тому, що перевіряючий повинен прочитати її, внаслідок чого час перевірки лінійно залежить від розміру (що зробило доказ не коротким). Щоб уникнути цього, ми можемо попередньо обробити схему та досягти сублінійного часу перевірки.

     Тепер ми зосередимося на поліноміальних зобов'язаннях KZG, які є основою Marlin та Plonk.

     Схема поліноміальних зобов'язань KZG

     Схема поліноміальних зобов'язань має такі алгоритми:

     1. Настройка.

     2. Фіксація.

     3. Відкриття.

     Щоб зафіксувати поліном, ми оцінимо його у заданій, але невідомій точці α .

     Налаштування приймає максимальний ступінь полінома (що залежить від кількості вентилів арифметичної схеми) і виводить загальнодоступні параметри: ключ, що доводить, і перевіряючий ключ. Щоб мати можливість обчислювати багаточлени, ми будемо використовувати еліптичну криву (нам потрібно, щоб вона була зручною для парування, наприклад, BLS 12–377), щоб приховати α та його потужності ( α вибирається під час церемонії налаштування та викидається як токсичне сміття!) . Щоб зробити це, ми вибираємо генератор з групи великого простого порядку d +1, g і обчислюємо

Це дасть нам дуже велику колекцію точок еліптичної кривої (ми збережемо їх у вигляді рядка), яка буде працювати як ключ, що доводить. У разі універсального налаштування кількість елементів збігатиметься з максимальним розміром схеми. Оскільки точки еліптичної кривої займають близько 100 В, якщо ми хочемо мати справу з 10⁸ вентилів, нам потрібно більше 1 Гбайт лише для того, щоб зберігати їх. Для заданої схеми, яка може бути набагато меншою за максимальну, MARLIN обрізає ключ, так що працювати з ним набагато простіше і швидше. Налаштування також залежить від параметра безпеки λ , але в нашому аналізі ми вважатимемо його постійним. Отже, ми маємо setup( λ, N ) → pp(pk, vk).

Доказуючий генерує поліном

і фіксує його , обчислюючи в точці ? Ми не знаємо α , лише скалярні кратні елементи групи ступенів α

Це проблема мульти-скалярного множення ( MSM ). Ми, що поліноміальні зобов'язання відповідає одному груповому елементу еліптичної кривої.

Ми також могли б використовувати дерево Меркла, щоб зафіксувати багаточлен. Проблема дерева Меркла полягає в тому, що розмір дерева залежить від рівня полінома. У випадку KZG зобов'язання - це лише один елемент групи, який не залежить від розміру. Крім того, коли ми хочемо обчислити багаточлен у доказі, нам потрібно відправити всі коефіцієнти у відкритому вигляді (який показує багаточлен), при цьому перевіряльнику доводиться виконувати лінійну роботу над розміром багаточлена. З іншого боку, ми побачимо, що KZG в основному приховує багаточлен (якщо тільки запитів небагато), і перевірка залежить від ступеня многочлена. Крім того, KZG допускає пакетні докази: якщо ми маємо кілька зобов'язань cm1, cm2, …, cmk, ми можемо згенерувати лише одне доказ, показує, що це зобов'язання дійсні.

Як тільки многочлен зафіксований, перевіряючий (в інтерактивній схемі) може відправляти випадкові точки rk доказує, і останній видає многочлен, обчислений rk, P(rk) . Щоб зробити його неінтерактивним, ми використовуємо перетворення Фіата-Шаміра, де випадкові виклики генеруватимуться з криптографічної хеш-функції.

Припустимо, що доводить хоче переконати перевіряючого у цьому, що P(u) = v . Він може перетворити цю рівність на поліном, g(x) = P(x) − v , який має рішення в x = u . Це означає, що g(x) ділиться на x − u , що ми можемо записати як g(x) = P(x)−v = Q(x)(x−u ), де Q є приватним многочленом. Доказуючий може зафіксувати Q(x) , виконавши те саме, що раніше

- Ще один MSM. Доказ π містить елемент групи, який має постійний розмір! Доказ продемонструє, що P(u) = v і P — це дійсно багаточлен ступеня не більше, ніж d , і фіксація P — це cm( P ).

Перевіряючий приймає доказ, якщо (α−u)cm(Q) = cm(P) − vg . Але проблема в тому, що ми не знаємо α . Ось де спаровування приходить на допомогу, і нам знадобляться лише елементи h0 і h1 , щоб мати можливість провести обчислення. Грубо кажучи, спарювання еліптичних кривих – це функція

яка приймає два елементи, P з G1 and Q з G2 і виробляє елемент R з Gt . Всі групи мають однаковий порядок r і відповідають групам зручних для спарювання еліптичних кривих. У разі MARLIN використовується крива BLS 12-377 . Спарювання задовольняє:

де g and g2 - генератори з груп G1 і G2 (і P = pg і Q = qg2 ). Форма рівняння перевірки з точки зору спарювання:

Перевірка проводиться в Gt . Нам потрібно лише дізнатися αg2 із довіреної настройки.

Тепер, як ми можемо бути впевнені, що якщо ми оцінили багаточлени в одній точці і вони збігаються, то дуже ймовірно, що аргумент вірний? Відповідь лежить у лемі Шварца-Зіппеля (ми сформулюємо її для кінцевих полів ): для полінома P ступеня d у кінцевому полі порядку p ймовірність, що поліном дорівнює нулю в точці r , обраної випадковим чином, дорівнює

Враховуючи, що максимальний розмір схеми (який визначає максимальний порядок полінома) дорівнює приблизно 2²⁶ ≈ 10⁸, а розмір поля більше ніж 2²⁵⁶, ця ймовірність дорівнює приблизно 2^(-230) ≈ 10^(-70). Якщо P1 і P2 збігаються в одній точці r ми можемо скласти поліном P(x) = P1(x )− P2(x) (оскільки складення поліномів замкнуте) і P(r) = 0 . Враховуючи, наскільки малоймовірно випадкове потрапляння в нуль, ми можемо бути цілком впевнені, що P(x) є нульовим поліном.

Висновок

zk-SNARK почали привертати увагу завдяки їхньому використанню при розробці повністю приватних додатків. Вони надають короткі докази, що певне обчислення було виконано правильно, не розкриваючи конфіденційної інформації. Існує безліч можливих конструкцій, заснованих на імовірнісних доказах та схемі зобов'язань. Залежно від різних варіантів можливі ефективніші версії, які визначають тип обчислень (машинні чи схемні обчислення). Ми вивчили схему зобов'язань KZG, яка демонструє ідею, що лежить в основі таких систем, як MARLIN та Plonk, та обчислення, які нам необхідно виконати для генерації та перевірки доказів.

Оригінал статті: https://www.entropy1729.com/the-hunting-of-the-zk-snark/

З моменту першого запуску програми амбасадорів Aleo у березні 2022 року ми спостерігаємо, як Discord росте як у кількісному, так і якісному відношенні. Усього ми вітали 157 амбассадорів , розділених на два рівні: 34 у групі маестро (maestro) та 123 у групі учнів (apprentice) . Дискорд виріс на 6000 нових акаунтів . Ми запустили спільноту Aleo у Твіттері, де активно висвітлюємо головних учасників Aleo за тиждень. Тепер ми маємо десять мовних каналів!

Коли ми вперше запустили програму послів, метою було розібратися в нашому співтоваристві, щоб знайти людей, які активно створюють найкращий контент для Aleo. Ми вдячні інженерам, які брали участь у Testnet 2, творцям YouTube, що публікують інформативні відеоролики про технологію Aleo, блогерам, що пишуть про мову програмування Leo, та багатьом іншим, хто зробив свій внесок.

З офіційним запуском Testnet 3 та новими функціями Aleo на горизонті ми вирішили змінити деякі речі у програмі посольств, щоб зробити їх більш прозорими та зручними для наших учасників.

У роботі програми буде дві основні зміни.

Представляємо Aleo Voyagers

З третім раундом послів ми представляємо третю групу Voyagers. Voyagers представлені у проекті як «золоті учні» (golden apprentices). Вони створюють дуже якісний контент, планують та проводять зустрічі Aleo та беруть активну участь у житті спільноти. Амбасадор може стати Voyagers тільки в тому випадку, якщо він спочатку був учнем (apprentices). Так само амбасадор може стати маестро (maestro), тільки якщо він спочатку був Voyagers.

Обновлення системи балів Aleo

Таблиця балів Aleo (нижче) - це те, що ми будемо використовувати для перетворення виконаних завдань від амбасадорів на бали. Зауважте, що бали Aleo не мають власної цінності.

Раніше маестро (maestro) накопичували 50 балів Aleo Points щоразу, коли ми проводили новий раунд відбору амбасадорів. Учні (apprentices) заробляли 25 балів за раунд, якщо виконували щонайменше два завдання.

Ми повністю переглянули те, як ми нараховуємо бали, щоб зробити цей процес децентралізованішим і прозорішим.

Щомісяця, якщо маестро (maestro) виконує свої обов'язки щодо перевірки роботи учнів (apprentices), модерації відповідних мовних каналів та підтримки своїх проектів, пов'язаних з Aleo, він отримує 50 балів Aleo.

Щомісяця учні (apprentices) мають набирати МІНІМУМ чотири бали, щоб зберегти свою роль. Якщо учень не виконує цю вимогу, він буде виключений із програми (при цьому всі накопичені ним бали зберігаються). Діяльність учнів (apprentices) розглядатиметься маестро (maestro) і перевірятиметься на якість. Учні можуть набрати МАКСИМУМ 30 балів за один місяць. Майте на увазі, що чим більше робіт виконується за бали, тим вище буде планка якості кожної роботи, і маестро (maestro) зможуть відхилити роботу, якщо вважають її не якісною. Якість робіт дуже важлива.

Щоб учень (apprentices) набув статусу мандрівника (voyager), він має накопичити 30 балів Aleo протягом двох місяців поспіль. Іншими словами, щомісяця протягом двох місяців поспіль їм потрібно буде набирати по 30 балів Aleo (60 балів протягом двох місяців).

Щоб мандрівник (voyager) зберіг свій статус посла, йому необхідно набирати щонайменше вісім балів на місяць. Якщо кількість балів, яку він збере (x), більше або дорівнює чотирьом, але менше восьми, вони будуть знижені в ролі до учнів (apprentices). Якщо його кількість балів буде меншою за чотири, він буде виключений з програми (при цьому всі раніше накопичені ним бали зберігаються). Його діяльність також буде розглянута маестро (maestro) та перевірена на якість. МАКСИМУМ, який мандрівник (voyager) може набрати протягом місяця, становить 40 балів. Щоб стати маестро (maestro), мандрівники (voyagers) повинні нагромадити 40 балів Aleo за три місяці поспіль. Іншими словами, їм потрібно буде набирати 40 балів Aleo Points щомісяця протягом трьох місяців поспіль.

ВАЖЛИВО ЗВЕРНУТИ УВАГУ, ЩО ТІЛЬКИ АМБАСАДОРИ МОЖУТЬ НАБИРАТИ БАЛИ. Ми будемо проводити нові раунди програми амбасадорів у рамках Testnet 3, але кількість раундів та точні дати поки невідомі.

Ми були так вражені кількістю часу та енергією, які спільнота вклала у Aleo. З цією новою системою нарахування балів ми також запустимо таблицю лідерів Discord. Будь-які питання, будь ласка, ставте в Discord. Ви завжди можете знайти нас там!

Підписуйтесь на Алео у Твіттері: https://twitter.com/aleohq

Спільнота Aleo у Твіттері: https://twitter.com/aleocommunity

Приєднуйтесь до нас у Discord: aleo.org/discord

Ознайомтеся з нашим кодом: https://github.com/AleoHQ/

Якщо, наприклад, ми візьмемо Біткойн і Ethereum, то побачимо, що історія всіх транзакцій є загальнодоступною (це може призвести до витоку конфіденційної інформації про постачальників вашої компанії, ваших знайомих або послуг, якими ви користуєтеся). Ethereum пропонує програмованість, але вимагає, щоб кожен вузол виконував операцію, де найменш потужний пристрій виступає як вузьке місце. ZCash вирішує проблему конфіденційності, але не пропонує можливості програмування, а лише приватні транзакції. ZEXE намагається отримати найкраще з обох світів:

Якщо, наприклад, ми візьмемо Біткойн і Ethereum, то побачимо, що історія всіх транзакцій є загальнодоступною (це може призвести до витоку конфіденційної інформації про постачальників вашої компанії, ваших знайомих або послуг, якими ви користуєтеся). Ethereum пропонує програмованість, але вимагає, щоб кожен вузол виконував операцію, де найменш потужний пристрій виступає як вузьке місце. ZCash вирішує проблему конфіденційності, але не пропонує можливості програмування, а лише приватні транзакції. ZEXE намагається отримати найкраще з обох світів: приватний запуск будь-яких програм, можливість виконання обчислень в автономному режимі та надання доказів цілісності обчислень, які можна швидко перевірити в блокчейні. Для огляду протоколу рекомендуємо наш попередній пост про ZEXE. Нагадаю, що протокол пропонує такі функції:

1. Програмування: ми можемо запускати довільні програми.

2. Швидка перевірка: ми можемо довести достовірність наших обчислень, використовуючи zk-SNARK (короткі неінтерактивні аргументи знання з нульовим розголошенням), які пропонують короткі докази, які можна перевірити в ланцюжку за кілька мілісекунд.

3. Конфіденційність даних та функцій: протокол приховує відповідну вхідну інформацію, а також функції, що викликаються при виконанні переходів у реєстрі.

Протокол ZEXE зазнав кількох покращень з моменту своєї появи, щоб підвищити продуктивність. У цьому пості ми проаналізуємо різницю між вихідним протоколом і недавнім версією VERI-ZEXE . Автори VERI-ZEXE порівняли продуктивність свого протоколу з вихідною версією ZEXE та деякими його ранніми модифікаціями. Жодних порівнянь між поточними покращеними версіями протоколу ZEXE та VERI-ZEXE не проводилося.

Компоненти Ми згадали, що протокол ZEXE використовує примітив zk-SNARK, який дозволяє нам надавати докази цілісності для заданих обчислень, які можуть бути перевірені набагато швидше. Найбільша ціна пов'язана з генерацією доказу, що ґрунтується на операціях з еліптичними кривими. Основи деяких систем SNARK ви можете переглянути в нашому попередньому пості.

Сучасні системи доказів мають два основних компоненти: поліноміальний інтерактивний доказ оракула -PIOP- (який перетворює дане обчислення в поліноміальні рівняння) та поліноміальну схему фіксації -PCS-. Залежно від вибору, який ми робимо, ми отримуємо різні доказові системи, кожна з яких має свої переваги і недоліки. Прикладами PIOP є Marlin, PLONK (Перестановки над базисами Лагранжа для екуменічних неінтерактивних аргументів Знання) та всі їх похідні та Spartan. Серед PCS у нас є KZG (Kate-Zaverucha-Goldberg), FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity), Bulletproofs та DARK (групи невизначеного порядку), і це лише деякі з них.

Щоб мати можливість виконувати докази швидко та ефективно, нам потрібні «дружні до SNARK» криптографічні примітиви та операції. Ми могли б сказати, що функція «зручна для SNARK», якщо її подання у вигляді арифметичної схеми невелике. Наприклад, інтуїтивно зрозумілі та прості побітові операції, такі як AND та XOR, мають складне схемне уявлення. Отже, вартість операцій у разі SNARK повинна враховувати складність арифметичної схеми, яка використовується для представлення операції та її змінних.

Більшість вартості систем SNARK посідає:

• Мультискалярне множення (ЧСЧ). Це операції виду

де ак - Числа і Pk - точки, що належать еліптичної кривої.

• Еліптичні пари кривих. Вони використовуються під час перевірки деяких систем. Вони включають розширення полів та операції між різними групами еліптичних кривих.

• Поліноміальні оцінки над нерідними полями.

• Перетворення Фіата-Шаміра: для створення завдань потрібне використання хеш-функції. Багато криптографічних примітивів, що добре зарекомендували себе, мають складні уявлення у вигляді арифметичних схем, що робить їх оцінку дорогою.

  Дослідницькі зусилля намагаються вирішити усі ці проблеми. Використання GPU або FPGA може прискорити обчислення MSM. Нові хеш-функції та схеми шифрування з більш досконалими арифметичними схемами можуть ще більше знизити складність часто використовуваних криптографічних примітивів (наприклад, Poseidon та Vision and Rescue).

  Вибір VERI-ZEXE Для вирішення цих проблем VERI-ZEXE вносить деякі зміни до системи перевірки та криптографічних примітивів. Ось деякі з основних модифікацій:

  • PLONK як PIOP. За останні роки в PLONK було внесено кілька значних поліпшень, таких як гейти високого ступеня, використання таблиць пошуку і використання полілінійних поліномів (що дозволяє уникнути використання швидкого перетворення Фур'є) (наприклад, turboPLONK, -ultraPLONK і hyperPLONK ).

  • Полегшена схема верифікатора за схемою накопичення. Протокол виводить перевірку сполучення зі схеми SNARK та відкладає перевірку до валідаторів реєстру.Пакетування доказів. Ми можемо генерувати та перевіряти докази партіями, використовуючи властивості деяких PCS, таких як KZG. Вони дозволяють відкривати

N різних зобов'язань одночасно з витратами, які не масштабуються лінійно за кількістю зобов'язань (тобто ви можете відкрити N зобов'язань вартістю менше, ніж вартість N окремих відкриттів).

• Змінна база MSM через довідкову таблицю. MSM виконується шляхом поєднання алгоритму Піппенджера (який розбиває скаляри на блоки) з таблицею пошуку , що знижує вартість додавання еліптичних кривих.

• Поліноміальна оцінка по нерідних полях. Схеми що доводить і перевіряє лежать у різних кінцевих полях. Одним із способів упоратися з цим було використання двох пар еліптичних кривих. VERI-ZEXE використовує модульне додавання та множення з перевіркою діапазону з пошуком, що призводить до більш складної схеми.

• Дружні до SNARK симетричні примітиви. Використання стійких до колізій хеш-функцій, генераторів псевдовипадкових чисел та схем фіксації з більш простим уявленням схеми (що скорочує кількість операцій), що призводить до меншого використання пам'яті та часу. Наприклад, перетворення Фіата-Шамір використовує конструкцію губки перестановки Rescue.

  Використання PLONK та його доповнень разом із більш простими конструкціями криптографічних примітивів призводить до зменшення більш ніж на порядок загальної кількості обмежень, що, у свою чергу, зменшує масштаб МСМ-множень та загальний час доведення.

  Схеми накопичення (AS) та інкрементально верифіковані обчислення (IVC)

  Перевірка доказів потребує обчислення дорогих операцій сполучення. Оригінальний протокол ZEXE використовував інкрементально верифіковані обчислення для доказу задовільності заданих користувачем предикатів за допомогою рекурсії SNARK: при заданому обчисленні на кроці N перевіряючий отримував стан Zn і доказ π(N-1), що підтверджує правильність виконання попереднього. Потім перевіряючий виконає крок N та генерує доказ π(N), який засвідчує, що “новий стан z′ є результатом правильного виконання і що π(N-1) істинно (іншими словами, що (N-1) попередніх кроків були виконані правильно )”. Саме на цьому останньому кроці виникає обчислювальне навантаження: для перевірки доказу нам необхідно вбудувати обчислення верифікатора у схему перевіряючого, що уповільнює генерацію доказів.

  Схема накопичення працює інакше, відкладаючи перевірку остаточного докази валідаторами реєстру. На кожному кроці обчислення прувер отримує поточний стан та накопичення, яке частково верифікується (перевірник перевіряє правильність результатів накопичення, але не обчислює операцію сполучення еліптичних кривих). Для того щоб накопичення не пропускало інформацію про обчислення, групові елементи в накопиченні повинні бути замасковані за допомогою рандомізатора, що виступає в ролі додаткового свідка (секретного входу) для верифікатора накопичення.

  Таблиці пошуку та ефективні модульні операції

  Використання інтерполяційних таблиць для складання еліптичних кривих у алгоритмі Піппенджера разом із ефективними операціями модульної арифметики призводить до скорочення кількості обмежень PLONK у 6 разів.

  Ідея таблиць пошуку для MSM полягає в наступному:

Алгоритм Піппенджера розбиває скаляр a на m вікон довжини c (Наприклад, скаляр - 256-бітове число, і ми вибираємо вікно завдовжки 8 біт). Кожен скаляр може бути записаний як

де кожне значення aij знаходиться у діапазоні 0, 1, . . . 2 c - 1 . Ми можемо обчислити кожної точки Pi всі можливі комбінації значень скалярів 2 Pi , 3 Pi , 4 Pi , . . . , (2 c - 1) Pi.

Тепер ми можемо визначити результат

подивившись на таблицю (яка має простіший опис, ніж операції з чистими еліптичними кривими) і отримати результати j-го дії,

Тепер ми можемо отримати остаточний результат, додавши, нарешті, m-дія,

Подальші покращення від HyperPlonk?

VERI-ZEXE використовує PLONK з таблицями пошуку, що призводить до меншої кількості обмежень та скорочення часу перевірки. Два тижні тому вийшов HyperPLONK, що забезпечує доказ лінійного часу і вентилі високого ступеня. Однією з ключових змін є перехід від одновимірних поліномів (поліномів від однієї змінної, x, таких як

до багатовимірних лінійних поліном (поліном від декількох змінних, де ступінь кожного хk більше одного, наприклад

Ця зміна дозволяє уникнути використання швидкого перетворення Фур'є (FFT) для дуже великих систем (з понад 2²⁰обмежень), який має надлінійну вартість (грубо кажучи, FFT для n-точок вимагає nlog(n) операцій). Попередні дослідження показали, що ця нова версія PLONK має кращу продуктивність для ланцюгів із більш ніж 16000 обмежень порівняно з оптимізованими версіями вихідної пропозиції. Ми розглянемо цю тему наступного посту.

Висновок

Докази ZK є ключем до багатьох нових додатків, таких як децентралізовані фінанси, управління тощо. Протокол ZEXE представив концепцію децентралізованих приватних обчислень, що дозволяє користувачам запускати приватні додатки в публічних реєстрах. Початкова пропозиція була заснована на неуніверсальних системах перевірки, які мають ефективну продуктивність, але потребують нової надійної установки для кожної програми, яку ми хочемо запустити. З того часу було внесено низку серйозних поліпшень до системи перевірки (такі як Marlin та PLONK) та нові «дружні до SNARK» криптографічні примітиви (такі як симетричні шифри та хеш-функції), що призвело до підвищення продуктивності та зниження обчислювальних витрат.

Aleo та Kryha знову об'єднуються

У міру того, як наше з вами життя поступово ставати громадським надбанням, завдяки зростаючій потужності гігантських технологічних компаній, конфіденційність стала важливішою, ніж будь-коли. Aleo - це блокчейн-платформа, розташована в Сан-Франциско, яка використовує технологію нульового розголошення (zk) для створення умов особистого та приватного досвіду користувача. Ми разом з Aleo віримо, що майбутнє онлайн-конфіденційності ґрунтується на технології доказу з нульовим розголошенням, що дозволяє суспільству легко отримувати доступ до складних математичних розрахунків. У цій захоплюючій колаборації Aleo та Kryha зроблять наступний крок у дослідженні конфіденційності та ігор. Для цього ми створюємо перший в історії комплект для розробки ігор із технологією нульового розголошення на Aleo.

Визначення нашої мети (північної зірки)

Ми віримо, що довгострокового успіху буде досягнуто за допомогою чітко поставленої мети, де шлях і пункт призначення однаково важливі. Кінцева мета, яку ми любимо називати нашою північною зіркою, - створити повноцінний набір інструментів для розробки ігор, який дозволить розробникам у всьому світі створювати власні ігри, створені за допомогою доказу з нульовим розголошенням (ZKP) та на основі стандартів з відкритим вихідним кодом. Мета створення цього набору інструментів з відкритим вихідним кодом — сприяти розробці нових ігрових механік за допомогою zk, що призведе до нових ігор або покращених старих ігор із золотої колекції.

Як технологія Aleo допомагає нам досягти цих цілей

Існуючі ігри на основі блокчейна побудовані на тому, що вся інформація про стан гри доступна кожному, хто має доступ до реєстру. Але як грати в гру, де перетинаються конфіденційність та прозорість? Aleo дозволяє створити нову ігрову механіку із збереженням конфіденційності, записуючи приватний стан у мережі. Це робиться шляхом генерації доказів з нульовим розголошенням (ZKP) деяких обчислень поза ланцюгом і запису отриманого ZKP в ланцюгу. Завдяки тому, що Aleo орієнтована на конфіденційності та приватну за умовчанням архітектуру, мережа стає відмінним місцем для розробки ігор, що базуються на блокчейні та належать до цих параметрів. Всі ігрові стани можна легко розмістити в ланцюзі, не хвилюючись, що побачать це інші люди. Наприклад, з такою архітектурою ви можете бути впевнені, що у грі з використанням кубиків ваші ролі приховані від сторонніх очей.

Ігровий набір ZK v1 + перша гра

Щоб переконатися, що ми створюємо компоненти для набору інструментів, які дозволять швидко створювати різні ігри, ми розглянули загальні механіки, які є простими у створенні. З цими компонентами (механікою кубиків, ZK-силові елементи та ін.) ми, використовуючи набором інструментів, створюємо першу в історії гру Liar's Dice. Ця гра швидка, проста для розуміння та використовує загальні механіки, які можна зустріти у багатьох інших іграх. З іншого боку, глибока стратегія, що лежить в основі Liar's Dice, робить гру цікавою та інтригуючою.

Будьте першим, хто дізнається, коли ми запустимося

Набір інструментів для розробки ігор є великим проектом, який вимагає кілька років проектування та розробки. Але щоб створити набір інструментів, що відповідає вимогам спільноти розробників, ми дотримуватимемося принципу «запускай та навчайся». Це означає, що ми випустимо наш продукт, коли він буде готовий, і звернемося до спільноти, щоб перевірити наше творіння. Отут ви і вступаєте: грайте з нами, вивчайте набір інструментів і надсилайте нам свої цінні відгуки.

Нам не терпиться показати вам, що ми задумали. знайте першими про наш запуск, підпишіться на нашу розсилку, або стежте за нами у Twitter. Залишайтеся на зв'язку!

Інформацію про початкову співпрацю між Aleo та Kryha можна знайти у цьому блозі.

Оригінал статті: https://medium.com/@haischel/aleo-and-kryha-are-developing-the-first-ever-zero-knowledge-proof-gaming-kit-ec0761a895d8

Що таке Алео?

Aleo - це новий блокчейн рівня L1, який використовує криптографію, засновану на доказі з нульовим розголошенням, для створення масштабованих та приватних децентралізованих додатків. У нашій архітектурі програми не виконуються в ланцюжку; скоріше, користувачі виконують програму поза мережею і публікують у ланцюжку короткі докази з нульовим розголошенням (zkSNARK), які підтверджують правильність виконання із збереженням конфіденційності. Потім ланцюжок перевіряє ці короткі докази в часі, незалежному від часу роботи програми.

Це добре працюючий план, крім однієї затримки: створення докази правильного виконання програми з нульовим розголошенням може бути сильно дорожче, ніж просто безпосереднє виконання програми. Для багатьох корисних програм (наприклад, платежів) ці накладні витрати можна контролювати навіть під час перевірки на стандартному пристрої, такому як мобільний телефон або ноутбук. Однак для інших, більш ресурсомістких додатків, таких як машинне навчання, ігри або автентифікація, накладні витрати на перевірку, що виконується на стандартних пристроях, можуть бути непомірно високими, що, мабуть, робить ці варіанти використання недосяжними.

Проте дизайн Aleo дозволяє клієнтам вибирати, чи передавати створення доказів сторонній «службі перевірки», яка, у разі важких обчислень, для допомоги у вирішенні zkSNARK може мати більше ресурсів, таких як: багатоядерні процесори, великі обсяги оперативної пам'яті або навіть спеціальне обладнання для випробувань Тоді ця проблема стає проблемою стимулювання розробки найкращих архітектур доведення. Вирішення цієї проблеми — це один із ключових мотивів розробки нового алгоритму консенсусу Aleo, AleoBFT. За великим рахунком AleoBFT є гібридною архітектурою, яка використовує доказ proof-of-stake(PoS) для досягнення миттєвого завершення підтвердження блоку та використовує “coinbase puzzle” типу proof-of-work(PoW), яка винагороджує розробку більш швидких методів для генерації доказів. У цьому пості ми заглибимося в деталі цієї Puzzle.

Coinbase Puzzle Coinbase Puzzle - це завдання типу proof-of-work (PoW), яке призначене для стимулювання розробки більш швидкого програмного та апаратного забезпечення для створення доказів з нульовим розголошенням. Щоб досягти цього, Coinbase Puzzle має дві унікальні особливості:

• Криптографічна: на відміну від традиційного PoW, який ви знайдете у Bitcoin або Ethereum, Coinbase Puzzle вимагає створення ефективних процедур для «корисних» алгоритмів основних підкомпонентів перевірки zkSNARK.

• Економічна: на відміну від традиційного PoW, де кожен блок може містити тільки одне дійсне рішення задачі, а Coinbase Puzzle приймає кілька дійсних рішень на блок, запобігаючи ситуації, коли переможець отримує все (winner-takes-all) та призводячи до ширшого розподілу винагород за доказ.

  Давайте заглибимося в Структуру Puzzle, почавши з криптографічної частини:

  Структура Puzzle Короткий посібник з дизайну zkSNARK: час створення доказу в сучасних zkSNARK визначається часом доказу двох підкомпонентів: поліноміального IOP та поліноміальної схеми розміщення. Наш coinbase puzzle ефективно стимулює прискорення саме цих підкомпонентів. Давайте подивимося, як вона це робить, глянувши на алгоритм протоколу, який складається з двох кроків:

  1. Генерація рішень-кандидатів (доказ) Щоб згенерувати рішення-кандидат, Прувер генерує (з одноразового номера) та множить випадковий поліном, а потім фіксує отриманий поліном твори за допомогою схеми поліноміальних зобов'язань (схема KZG10, у нашому випадку). Отримане в результаті зобов'язання хешується, і якщо цей хеш відповідає цільовій складності, це дійсне рішення, яке можна відправити агрегатору (разом з підтвердженням оцінки для забезпечення ефективного агрегування). Отримана задача складається з 2 групових елементів та 1 елемента поля, адреси та одноразового номера, і її можна перевірити за допомогою D множень полів та пари, де D – ступінь згенерованого полінома.

  2. Агрегування правильних рішень (BFT Leader) Хоча правильне рішення задачі може бути перевірене будь-ким, додавання кожного рішення задачі в ланцюжок призведе до роздмухування стану. Щоб уникнути цього, Coinbase Puzzle дозволяє BFT Leader поєднувати дійсні рішення. Ми не вдаватимемося в подробиці того, як це робиться, але загальний результат полягає в тому, що в сховищі ланцюжка переважає вартість (n + 1) елементів групи, а один елемент поля є суттєвим поліпшенням. Як додаткова перевага перевірка завдання виконується швидше.

     Висновок AleoBFT - це новий механізм консенсусу, який поєднує в собі завершеність proof-of-stake (PoS) з потужним механізмом стимулювання proof-of-work (PoW). У нашому випадку, Coinbase Puzzle стимулює прискорення перевірки zkSNARK. Ця робота корисна, тому що вона переноситься безпосередньо на виконання будь-якої іншої програми в Aleo. За допомогою цього механізму ми сподіваємося стимулювати сильну екосистему, що доводить, (proving ecosystem), яка приносить користь користувачам Aleo за рахунок зниження витрат і зменшення затримки виконання програми.

     І останнє зауваження: цей етап тестової мережі стимулюватиметься. Однак, публікація цього повідомлення в блозі не означає початок програми заохочення. Приєднуйтесь до нашої спільноти в Discord і слідкуйте за нами у Twitter, щоб отримувати останні оновлення про графік заохочень.

     Оригінал статті: https://www.aleo.org/post/launching-testnet-3-2-provers

Функціонал Leo стане головним пунктом призначення для виконання будь-яких дій на блокчейні Aleo: відправлення/отримання токенів, стейкінг, трейдинг, ігри та багато іншого будуть можливі або спочатку через гаманець, або через партнерські dApp. Ми також маємо SDK для безперешкодної інтеграції розробників, які хочуть охопити більше користувачів Aleo. Ми продовжимо додавати функціонал для масштабного впровадження орієнтованих на конфіденційність програм, щоб розширити екосистему Aleo.

Запишіться у наш waitlist, щоб отримати ранній доступ: https://join.leo.app/signup

Команда Ми — команда розробників, які заснували, масштабували та продали безліч підприємств. За сильної підтримки інвесторів та гранту від команди Aleo ми раді розробити найкращий із можливих гаманців, орієнтованих на конфіденційність.

Бачення Майбутнє громадських блокчейнів, що зберігають конфіденційність, ясно. Вони мають потенціал зруйнувати існуючі блокчейни, оскільки вони збирають у собі все хороше, але при цьому дозволяють користувачам мати більше контролю над тим, чим вони діляться. Будь ласка, зв'яжіться з нами, якщо ви зацікавлені у співпраці, є раннім користувачем або вірите в майбутнє, де конфіденційність є пріоритетом за промовчанням.

Waitlist для раннього доступу: https://join.leo.app/signup

Веб-сайт: https://leo.app/

‍Twitter: https://twitter.com/theLeoWallet

‍Discord: https://discord.gg/BNBzZQAd66

Зв'яжіться з нами електронною поштою: Barron@leo.app

Посилання на оригінал: https://www.leo.app/blog/leo-aleo-wallet

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

Ця стаття познайомить вас із п'ятьма головними експертами у сфері доказів із нульовим розголошенням. Ці професіонали зробили видатний внесок у докази з нульовим розголошенням та криптографію загалом за допомогою дослідницьких робіт, семінарів, книг та практичних додатків.

Alessandro Chiesa

Alessandro Chiesa – доцент Каліфорнійського університету в Берклі та співавтор Zerocash, співзасновник Zcash та StarkWare, однієї з фірм, які розробляють рішення для масштабування на основі нульового розголошення. В даний час він є професором криптографії, комп'ютерних наук та теорії складності обчислень. У 2020 році його дослідження цитувалося понад 1200 разів. Він багато досліджував, як покращити технологію нульового розголошення. Одним із прикладів його досліджень є Zexe, приватний та децентралізований обчислювальний протокол, який використовує SNARKs з єдиним налаштуванням. Він також працював над квантово-стійкими, прозорими рекурсивними доказами, які б особливо підходили для блокчейнів.

Eli Ben-Sasson

З того часу, як у 2001 році Eli отримав докторський ступінь у галузі теоретичних комп'ютерних наук в Єврейському університеті, він вивчав криптографічні докази та докази з нульовим розголошенням обчислювальної цілісності. Він був співавтором протоколів STARK, FRI, Zerocash та Zcash Company. Перш ніж піти, щоб заснувати StarkWare, він кілька років був професором комп'ютерних наук в Техніоні. Він також обіймав дослідницькі посади в Інституті перспективних досліджень м. Прінстона, Гарварді і в Массачусетському технологічному інституті.

Shafi Gold-Shafran

Shafi Goldwasser - директор Інституту теорії обчислень Саймонса та професор C. Lester Hogan електротехніки та комп'ютерних наук у Каліфорнійському університеті в Берклі. Вона також є професором електротехніки та комп'ютерних наук у Массачусетському технологічному інституті та професором комп'ютерних наук та прикладної математики в Інституті науки Вейцмана в Ізраїлі. Goldwasser здобула ступінь бакалавра прикладної математики в Університеті Карнегі-Меллон в 1979 році і ступінь магістра і доктора в галузі комп'ютерних наук в Каліфорнійському університеті в Берклі в 1984 році. Вона є одним із авторів “The knowledge complexity of interactive proof-systems”, однією з фундаментальних опублікованих за інтерактивними доказами робіт. Її внесок у область криптографії робить її одним із найбільш цитованих авторів у цій галузі.

Howard Wu

Howard Wu є співзасновником Aleo, блокчейна, який використовує криптографію з нульовим розголошенням для забезпечення конфіденційності та програмованості, та Decrypt Capital, провідної інвестиційної компанії в області блокчейнів для протоколів збереження конфіденційності та підприємств на ранніх стадіях. Howard вперше зацікавився Bitcoin у 2011 році і зробив свій внесок у криптографічні бібліотеки, які використовуються в Ethereum та Zcash. Він є радником з блокчейну в Берклі, першій університетській екосистемі для блокчейну. Він є активним дослідником у галузі теоретичної інформатики та комп'ютерної безпеки, і працює з професором Alessandro Chiesa, співзасновником Zcash, та професором Dawn Song, викладачем Ініціативи з криптовалютів та контрактів (IC3). Howard є кандидатом у магістри електротехніки та комп'ютерних наук і отримав ступінь бакалавра прикладної математики та бакалавра комп'ютерних наук у Каліфорнійському університеті в Берклі.

Dan Boneh

Dan Boneh - американсько-ізраїльський професор прикладної криптографії та комп'ютерної безпеки у Стенфордському університеті. Дослідження Боуна зосереджено застосування криптографії до комп'ютерної безпеки. Його робота включає криптосистеми з новими властивостями, веб-безпеку, безпеку для мобільних пристроїв та криптоаналіз. Він є автором понад ста публікацій у цій галузі та стипендіатом Packard та Alfred P. Sloan. Він є лауреатом премії ACM 2014 року та премії Ґеделя 2013 року. У 2016 році Boneh був обраний членом Національної інженерної академії США за внесок у криптографію та комп'ютерну безпеку.

Ben Fisch

Ben Fisch — доцент кафедри комп'ютерних наук Єльського університету та співзасновник Espresso Systems, блокчейн-компанії, що працює над рішеннями, що налаштовуються, для забезпечення конфіденційності. Він захистив докторську дисертацію у Стенфордському університеті, працюючи з Dan Boneh у дослідницькій групі прикладної криптографії. Дослідження Ben в першу чергу зосереджені на конфіденційності та перевірки в Інтернеті. Він опублікував безліч статей про нульове розголошення, і його цитували понад 1200 разів.

Висновок

Докази з нульовим розголошенням - важлива та захоплююча область досліджень у криптографії. Вони дозволяють сторонам довести, що вони щось знають, не розкриваючи того, що вони знають. Вони корисні в багатьох областях, включаючи голосування, онлайн-рекламу та онлайн-знайомства. Вони також використовуються в блокчейнах для підтвердження дійсності транзакції без розкриття інформації про сторони, що здійснюють транзакцію. Докази з нульовим розголошенням - це складна та технічна область досліджень, але вони мають безліч застосувань та корисні у багатьох реальних ситуаціях. Це захоплююча область досліджень, яка в майбутньому матиме набагато більше застосувань та відкриттів.

Посилання на оригінал: https://www.leo.app/blog/top-zero-knowledge-experts-2022

Системи на основі блокчейна входять до багатьох сфер нашого життя, таких галузей, як DeFi або ігри. Однак багатьом сучасним блокчейнам не вистачає конфіденційності та масштабованості, що обмежує діапазон варіантів використання. Докази з нульовим розголошенням та блокчейни, що підтримуються доказами з нульовим розголошенням, такі як Aleo, обіцяють забезпечити кращу масштабованість та гарантії конфіденційності, а також уможливити застосування нових блокчейн-додатків. Сюди входять нові програми DeFi, складніші ігри web3 чи навіть програми на основі штучного інтелекту. Багато цих додатків вимагають представлення широкого діапазону чисел, включаючи дробові числа. Aleo поставляється з мовою програмування Leo, яка значно спрощує програмування програм із нульовим розголошенням. Однак він підтримує лише числа цілого типу. У цій статті ми аналізуємо структуру чисел з фіксованою точкою zkSNARKS з використанням Leo, що дозволяє нам також виконувати обчислення з використанням дробів для широкого кола додатків.

Проста реалізація чисел із фіксованою комою

При реалізації запису чисел з фіксованою комою ми можемо використовувати цілий тип, що надається мовою Leo. Крім того, ми внутрішньо вказуємо коефіцієнт масштабування, який визначає цифри, що зарезервовані для цілої частини зліва від десяткової точки значення, а також визначає дробову частину праворуч від десяткової точки значення.

Припустимо, ми хочемо уявити значення 1.55 як число з фіксованою комою з точністю до двох знаків після коми. Для цього ми можемо ввести змінну i та присвоїти їй 155, тобто значення 1.55, помножене на коефіцієнт масштабування 100:

let i: u32 = 155;

Тепер ми можемо виконувати математичні операції з цією змінною. Наприклад, щоб додати 0.45 ми додаємо 45 (0.45 * 100) в код програми, що призводить до значення змінної 200. При інтерпретації виведення програми нам потрібно розділити значення на коефіцієнт масштабування 100. Для отримання бажаного запису з десятковою точкою - результат додавання дорівнює 2 у запису з десятковою точкою.

Так само ми можемо виконувати множення. При множенні на 2.50 у десятковому поданні ми множимо на 250 у поданні з фіксованою комою, а потім ділимо результат на коефіцієнт масштабування 100. Наприклад, 22.5=5 у десятковому поданні виглядає як 200250/100=500 у записі з фіксованою точкою . Знову ж таки, при інтерпретації результату нам потрібно розділити число з фіксованою точкою 500 на коефіцієнт масштабування 100, щоб отримати очікуваний результат 5.

Для поділу ми діємо аналогічно до множення, але цього разу множимо на коефіцієнт масштабування, а не ділимо.

Наприклад, 4.5/0.5 = 9 у записі з десятковою комою виглядає як 100*450/50 = 900 у записі з фіксованою комою. Розділивши на коефіцієнт масштабування, ми отримаємо очікуваний результат 9.

Узагальнення та що слід враховувати

Як показано у наведених вище прикладах, коефіцієнт масштабування визначає кількість цифр дробової частини. Ми використовували коефіцієнт масштабування 10 для n дробових цифр. Як правило, більший коефіцієнт масштабування забезпечує більшу точність, однак ми повинні пам'ятати про допустимий діапазон значень типу.

У наведеному вище прикладі використовувався тип u32, загальний діапазон якого становить від 0 до ²³²-1=4294967295. Через бінарної природи типів зазвичай використовують коефіцієнти масштабування S ступенів двійки. Наприклад, під час використання коефіцієнта масштабування ²⁵=32 для дробової частини використовується 5 біт, а цілої частини залишається лише 27 біт. Таким чином, максимальне число для цілої частини дорівнює ²²⁷-1=134 217 727, а роздільна здатність дробової частини дорівнює 2^-5=1/32. Дробова частина може додати 31/32 до максимального цілого числа, тому максимальне значення становить між 0 і ²²⁷-1+31/32=134 217 727,969.

У той самий час максимальна помилка подання обчислюється як (1/S)/2, у цьому прикладі вона дорівнює (1/²⁵)/2=1/64=0,015625. Таким чином, більший коефіцієнт масштабування дозволяє нам мати більш точне уявлення дробових чисел, але зменшує розмір цілої частини і, таким чином, діапазон значень, що подаються.

Як бачимо, існує компроміс між діапазоном значень, які ми можемо зберігати, і точністю представлених чисел.

Особливо при множенні чи розподілі ми можемо зіткнутися з переповненням. Наприклад, припустимо, що ми маємо коефіцієнт масштабування ²⁵=32, і ми хочемо помножити ²¹⁶=65536 на ²⁶=64. Нижче наведений код намагається це зробити.

function main() -> u32 { let s: u32 = 32; let a: u32 = 65536 * s; let b: u32 = 64 * s; let result: u32 = a * b / s; return result; }

Для запису з фіксованою точкою ми повинні помножити обидва числа коефіцієнт масштабування, тобто фактично помножити ²¹⁶²⁵=²²¹ на ²⁶²⁵=²¹¹ . Таким чином, просто подивившись на інструкції, ми очікуємо, що на виході буде ²²⁷.

Однак, на виході ми отримуємо:

[registers] r0: u32 = 0;

Тимчасовий результат c*d дорівнює ²³², що виходить за межі діапазону типу u32. Таким чином, ми фактично отримали числове переповнення та отримали невірний результат.

Отже, що ми можемо зробити з цього приводу? Ми могли б використовувати тип u64 замість типу u32 для всіх типів (змінних та виводу), які можуть зберігати числа до ²⁶⁴-1. Таким чином, ми отримуємо очікуваний результат ²²⁷:

[registers] r0: u64 = 134217728;

Пам'ятайте, що нам потрібно знову поділити на коефіцієнт масштабування, щоб інтерпретувати результат числа з фіксованою точкою: ²²⁷/ ²⁵= ²²², що є результатом вищезгаданого обчислення ²¹⁶, помноженого на ²⁶.

Однак при використанні U64 розмір схеми збільшився з 96 до 192 обмежень, фактично збільшившись вдвічі. Це може призвести до збільшення вартості перевірки, особливо у складних програмах. Таким чином, альтернативою було б зменшення коефіцієнта масштабування та, таким чином, потенційне зниження точності представлення числа.

При використанні ²⁴ як коефіцієнт масштабування замість ²⁵ тільки з типами u32 ми отримуємо наступний результат:

[Registers] r0: u32 = 67108864;

Результат дорівнює ²²⁶. Знову розділіть його на коефіцієнт масштабування ²⁴, і ми отримаємо очікуваний та правильний висновок ²²².

Код зазвичай працює для негативних чисел. Однак нам потрібно використовувати цілі типи зі знаком. Врахуйте, що для знака потрібен додатковий біт, тому для i32 діапазон цілої частини обчислюється як +- ²³¹-1, що відповідає діапазону від -2147483648 до 2147483647.

Приклад коду

Додавання двох чисел a та b у форматі з фіксованою точкою:

function add(a: u32, b: u32) -> u32 { let result: u32 = a + b; return result; }

Розмноження двох чисел a та b у форматі з фіксованою точкою:

function multiply(a: u32, b: u32, s: u32) -> u32 { let result: u32 = a * b / s; return result; }

Розподіл двох чисел a та b у форматі з фіксованою точкою:

function divide(a: u32, b: u32, s: u32) -> u32 { let result: u32 = s * a / b; return result; }

Ви можете знайти весь код проекту Leo тут.

Принципи, про які ми дбаємо, — це безпека, надійність, конфіденційність, простота та захист.

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

Ми раді представити нове обличчя гаманця Leo.

Ми називаємо цей новий логотип “Leo Lock”, він створює замок із двох літер “L” у слові “waLLet”.

Leo Wallet вже почав доходити до розробників, програмістів та ентузіастів конфіденційності. Ми продовжуватимемо розширювати охоплення Leo у міру подальшого розвитку основного блокчейну Aleo.

Ми хочемо створити безпечний простір, де люди могли б процвітати. Наша мета – продовжувати збільшувати користь і будувати майбутнє, в якому ми всі хочемо жити.

Leo - це гаманець з приватністю на першому місці для мережі з приватністю на першому місці.

Запишіться у waitlist раннього доступу тут або приєднуйтесь до нашого Discord.

Посилання на оригінал: https://www.leo.app/blog/say-hello-to-the-new-leo-wallet