Що вам потрібно:
- фон інформатики
- основи Ethereum
- основи числення (оптимізація обмежень)
Що ви отримаєте:
- основи нульових знань SNARK
- основи дерев Меркле
- як Ethereum може масштабуватися до тисяч транзакцій в секунду завдяки SNARKs
SNARK дозволяють Провертеру довести верифікатору, що він / він має рішення W до проблеми F зі спільними / відомими входами X, не розкриваючи W.
Пошук рішення проблеми може зажадати величезної кількості обчислювальної потужності та пам'яті.
Отже, Верифікатор може бути в основному на 100% впевненим, що Провертор працював належним чином (і знайшов рішення), ні переробляючи цю роботу самостійно, щоб перевірити рішення, ні знаючи рішення взагалі. Це магія!
Процес складається з 3 кроків:
- НАСТРОЙКА - Задача F (яку потрібно виразити як квадратичну арифметичну програму, див. Нижче) підготовлена для SNARK. Цей процес має дуже високу пам’ять та обчислювальну роботу в залежності від складності проблеми (→ Кількість входів та обмежень → Розмір матриці задачі задоволення обмежень). Гравець, який виконує інсталяцію (може бути сам верифікатор), повинен довіряти всім сторонам, оскільки вихідні дані інсталяції використовуються на наступних етапах. Налаштування зазвичай виконується за допомогою libsnark, бібліотека C ++, яка є найбільш популярною реалізацією для zkSNARK.
- ДОКАЗ - Prover, який має рішення W для проблеми F із загальними входами X (можливо, він / він витратив величезну кількість процесора та пам'яті, щоб знайти його!), Використовує libsnark і вихід Setup етап для створення доказу 𝚷. Цей процес, безумовно, вимагає великої пам’яті та інтенсивних обчислень (залежно від складності проблеми, як зазначено вище). Розмір результату (тобто доказ 𝚷) натомість стислий і постійний незалежно від складності проблеми. Проверер повинен довіряти тому, хто виконав етап налаштування, оскільки він / він використовує його вихідні дані ...
- ПЕРЕВІРКА - Верифікатор - надання в якості вихідних даних фази налаштування, спільних входів X та доказу 𝚷 - перевіряє доказ. Якщо перевірка пройшла успішно, Доказчику вдалося довести перевірителю, що він / вона знайшов рішення W проблеми F ... не розкриваючи W! Приємна частина полягає в тому, що не тільки Доказ є стислим і завжди має однакову довжину .., процес перевірки є швидким, а пам’ять / обчислення зовсім не інтенсивними. На відміну від двох попередніх етапів ... перевірку можна легко зробити за допомогою смартфона за мілісекунди!
Хороший підсумок (джерело):
Як це може статися? Ну, це магія Мерліна! Якщо ви хочете зрозуміти математику, Почніть звідси.
Як я можу перетворити своє програмне забезпечення на програму квадратичної арифметики?
Як уже згадувалося вище, завдання F етапу установки має бути квадратичною арифметичною програмою. Правила гри жорсткі:
- Вхідні дані вашого програмного забезпечення повинні мати цифри. Перетворіть свої речі (масиви, рядки тощо) у числа. Це дріб’язково.
- "Квадратично обмежена система рівнянь" означає:
де x - n-мірний вектор ваших входів, m - кількість обмежень (тобто кількість рівнянь вашої системи), C - n-by-n коефіцієнти Матриця, а q - n-мірний вектор коефіцієнтів. Якщо вам не подобаються матриця та вектори, ось випадок n = 3 та m = 2 (3 входи, 2 обмеження):
- Реалізація являє собою арифметичну схему, що означає, що результат є Проблема вирішена (система розв’язана, тобто всі поліноми дорівнюють 0) або Проблема не вирішена (усі інші випадки). Іншими словами: «ці входи є / не є одним із рішень цієї проблеми».
- Коефіцієнти C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 є обмеженнями системи. В основному це визначає ваше програмне забезпечення. Змініть їх… і ви отримаєте інше програмне забезпечення! Повернення до того, як працюють SNARK: C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 - це вхідні дані фази налаштування. Вихід з етапу налаштування (необхідний для підтвердження та перевірки) тому суворо пов’язаний із тими C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 і працює лише для цієї Проблеми. Якщо ви їх змінили, ви визначаєте інше програмне забезпечення / проблему, і вам потрібно повторно запустити етап налаштування! x₁, x₂,…, x𝗇 - це змінні (тобто те, що ви повинні здогадатися, щоб отримати системне рішення). Отже, коли ми говоримо “Шановний Провер, чи могли б Ви знайти секретне рішення W для проблеми F із загальними / загальнодоступними входами X”, ми маємо на увазі, наприклад, “Шановний Провер, чи можете Ви знайти значення x₁, x₂,…, x𝗇, які вирішують систему наприклад, x₇ = 2393, x₅₂₆ = 5647? " Ви можете робити те, що хочете, з усіма x𝗇, крім x₇ та x₇, які обмежені спільними / загальнодоступними входами.
Це важке життя, але ви можете вижити ... Якщо вам потрібні петлі, ви можете розгорнути їх, повторюючи ту саму операцію багато разів. Або якщо вам потрібен, наприклад, x₁⁴ x₂⁵, ви визначаєте новий вхід x₃ = x₁⁴ x₂⁵ і використовуєте x₃ у своїх обмеженнях. Вся справа в додаванні змінних та обмежень ... Навіть для досить простих програмних засобів легко досягти сотень мільйонів або мільярдів введених даних та обмежень!
Хочете знати більше? Прочитайте тут. А також перевірте це основне code_to_r1cs.py з ethereum / дослідження.
Що таке дерево Меркле?
Хеш-функція - це правило, яке відображає вхід довільного розміру на вихід фіксованого розміру. Ми могли б винайти досить марну хеш-функцію "Об'єднати перші дві з останніми двома буквами", яка перетворює "Вуді Аллена" на "Woen", а "Пола Маккартні" на "Paey".
Дерево Меркла - це структура даних, де кожен із батьків є хешем двох своїх синів. Угорі ви знайдете Корінь, який є хешем двох синів рівня 1. Внизу кожен лист є хешем зовнішнього входу.
Використовуючи наш словник “Вуді Аллен” → хеш-функція “Woen”:
Коли лист змінюється, модифікація поширюється до кореня. Якщо змінюється ANTHONY, змінюються також ANNY (лист), CENY та CECO (корінь). Що б лист не змінився, змінюється і Корінь.
Для перерахунку кореня вам не потрібно все дерево. У нашому прикладі, якщо ANTHONY зміниться, і ви знаєте як JACO, так і CECILY, ви можете легко перерахувати Root, навіть якщо повністю ігноруєте JAMES, MARCO, JAES та MACO. Для величезних дерев це економить багато часу!
І що?
Дерева Меркле чудово підходять для перевірки цілісності даних. Зазвичай: ви знаєте, який дійсний Root, і перевіряєте, чи отримані дані збігаються з цим Root. Наприклад: довірена сторона, яка не може дати вам повний набір даних імен людей на Землі (ні часу, ні смуги пропускання, ні, можливо, вона / він взагалі не має даних) дає вам лише Корінь (наприклад, “CECO”). Післямови: ви отримуєте мільйони імен із посиланням на номер листів тисячами ненадійних сторін. Ну, оскільки у вас правильний Root, ви можете перевірити, на кого можна покластися, хто передає вам фальшиві дані ...
Дерева меркле теж є частиною вашого життя! Коли ви завантажуєте торрент-файл розміром 3 ГБ, ваш файл поділяється на мільйони невеликих шматків. Хеш кожного шматка зберігається в листі. Оскільки ви знаєте, який дійсний корінь дерева, кожного разу, коли ви отримуєте фрагмент файлу кимось, ви можете перевірити, чи він правильний. Якщо це не так, ви можете попросити той самий шматок у когось іншого.
Ви можете зробити це, навіть якщо ви ще не завантажили все дерево / всі листя: якщо ви знаєте, що Root - це CECO, і ви довіряєте JACO ... отримавши шматок ANTHONY, ви можете перевірити це, навіть якщо не завантажили ще шматки MARCO та JAMES.
Чому дерева Merkle корисні в технології розподіленої книги - це просто: ви використовуєте консенсус-протоколи (повільні, дорогі) лише для досягнення консенсусу на корені. Тоді ненадійні вузли мережі можуть ефективно і безпосередньо обмінюватися даними ... і можуть спати цілим і здоровим завдяки перевірці цілісності з Root.
Коли Бог попросив Ethereum вибрати 2 наддержави серед безпеки, масштабованості та децентралізації ... Ethereum пожертвував масштабованістю. Насправді не існує чіткого обмеження "транзакцій в секунду": обмеження стосується кількості газу в кожному блоці - це, спрощуючи, кількість операцій, які я можу зробити в кожному блоці. Ця межа становить 8 мільйонів газу. Це може означати багато «крихітних» транзакцій (відсутність даних, що додаються до транзакцій, жодних операцій, що виконуються з цими даними), або мало великих транзакцій. Це залежить від вузлів Ethereum, які подають транзакції, і до майнерів Ethereum, які включають в блок транзакції, які платять більше.
Видобувається блок кожен ~ 15 секунд. Це означає ~ 32 мільйони газу на хвилину, що, безумовно, недостатньо, якщо ми хочемо, щоб дані Ефіріуму стали основними.
До речі: зупиніться на тих нудних порівняннях між Ethereum та Visa. Централізована система буде завжди бути швидшим за Ethereum ... за задумом! Вони роблять різні речі, і вони потрібні вам у різних ситуаціях. Якщо вам не потрібна децентралізація та середовище без довіри ... звичайно, вам слід вибрати Visa. Коротко: той факт, що ваш блендер крутиться швидше, ніж пральна машина, не означає, що ви будете чистити штани в блендері!
Давайте складемо загадку! Уявіть, що ви можете «стиснути» багато крихітних транзакцій в одну велику транзакцію завдяки SNARK. Якщо газ, витрачений на цю велику транзакцію, менше суми газу, витраченого на крихітні транзакції, це означає, що ви економите газ.
А економія газу означає:
- Користувачі витрачають менше коштів на транзакції загалом → Це було б поштовхом для всієї екосистеми
- Можливість помістити більше речей у блок → Ефіріум крутиться швидше, ніж ваш блендер!
Як це працює?
Є користувачі, ретранслятор (або більше ретрансляторів), який агрегує транзакції та смарт-контракт.
- Користувачі, які бажають пограти в цю гру, надсилають свій ефір (або токени) на публічний аудит смарт-контракту. Для кожного нового гравця створюється новий аркуш у дереві Меркле. Аркуш включає інформацію про власника ефіру (його / його адресу, яка також є відкритим ключем), кількість ефіру та відсутність (лічильник транзакцій цього рахунку, що дорівнює 0 при додаванні листка)
- Коли А хоче надіслати Ефір В (їм обом потрібно мати лист / рахунок у смарт-контракті), А пакує транзакцію, яка включає адресу відрахунок, до рахунок, нунцій з рахунку, кількість ефіру, що передається, і підпис транзакції (очевидно, підписаний приватним ключем рахунку “від”). Потім він / він передає упаковану транзакцію ретранслятору.
- Релейер об'єднує всі транзакції, отримані за певний часовий проміжок (наприклад, за одну годину), оновлює дерево Merkle новими сумами залишків і створює доказ SNARK, який доводить, що всі підписи та корінь нового дерева Merkle є дійсними. Ретранслятор, нарешті, відправляє новий стан і доказ до смарт-контракту.
- Смарт-контракт підтверджує систему Proof на мережі. Якщо він дійсний, він зберігає корінь дерева Меркле з Нового стану у внутрішній пам'яті контракту.
В основному, корінь дерева Меркле відображає весь стан усіх рахунків. І ви не можете змінити його (= вкрасти гроші), якщо не зможете довести дійсність підписів, транзакції яких ведуть до нового стану, узагальненого новим кореневим кодом, який ви подаєте.
У двох словах: користувачі мають надзвичайно швидкі та майже безкоштовні транзакції, як на Coinbase, без необхідності довіряти ретранслятору, який нічого не може зробити, на відміну від Coinbase, без вашого підпису.
Це бічний ланцюг, що не зберігається, стан якого узагальнено коренем дерева Меркла.
Давайте пов’яжемо те, що ми дізналися вище про SNARK, з тим, що ми щойно обговорювали щодо масштабування. Для цього існують різні способи. Я порівняю 2 рецепти: рецепт Віталіка версія та barryWhiteHat's версія.
НАЛАШТУВАННЯ робить…
Хлопець, який починає проект, який також створює смарт-контракт. Чим більше це піддається аудиту, тим краще. Ви повинні довіряти їй / йому ... це a надійне налаштування!
Розумний контракт економить ...
2 коріння Меркле (байти32 значення): перше дерево містить адреси рахунків (публічні підписи), залишки та нонси другого рахунку
ДОКАЗАННЯ виконує…
Релеєр
Релеєр відправляє на смарт-контракт ...
- 2 коріння Меркле Нової держави (звертається до дерева та балансів + дерева нонсів)
- перелік операцій, без підписів. «Кожна транзакція коштує 68 газ за байт. Отже, для звичайного переказу ми можемо очікувати граничних витрат 68 * 3 (від) + 68 * 3 (до) + 68 * 1 (плата) + 68 * 4 + 4 * 2 (сума) + 68 * 2 (nonce), або 892 газу ”
Відомі вхідні дані процесу ПРОВАННЯ…
- 2 коріння Меркле старої держави
- 2 нові державні коріння Меркла
- список транзакцій
Процес доказування доводить, що ...
при
- 2 коріння Меркле старого штату (вже зберігаються в контракті)
- 2 нові державні коріння Меркле (надіслані в аггр. транзакції)
- список транзакцій (надсилається в групі транзакцій)
… Ретранслятор має діючі підписи для переходу із стану із 2 старими коріннями у стан із 2 новими коренями за допомогою цих транзакцій.
ПЕРЕВІРКА здійснюється…
Розумний контракт (закодований у твердість, випер, як вам подобається!)
Відомі входи процесу перевірки - це ...
Той самий процес ПРОВІНГУ - відомі вхідні дані, очевидно ...!
Межі масштабованості
Кожна агрегована операція використовує 650 тис. Газу для перевірки SNARK (фіксована вартість) плюс ~ 900 газ гранична вартість за транзакцію (Варто відправити дані!). Отже, використовуючи весь блок, релеєр може агрегувати щонайбільше:
що означає ~ 544 tx за секунду
barryWhiteHat's версія
НАЛАШТУВАННЯ робить…
Хлопець, який починає проект.
Розумний контракт економить ...
1 Корінь Меркла з поточним станом. Кожен аркуш - це хешований стан рахунку.
Хочете, щоб створювати рахунок?
state = AccountState (pubkey, баланс, nonce)
state.index = self._tree.append (state.hash ())
ДОКАЗАННЯ виконує…
Релеєр
Релеєр відправляє на смарт-контракт ...
- доказ 𝚷
- новий державний корінь Меркле
- доказ 𝚷
Відомі вхідні дані процесу ПРОВАННЯ…
- старий державний корінь Меркле
- новий державний корінь Меркле
Процес доказування доводить, що ...
при
- корінь Старого Меркла (вже зберігається в контракті)
- новий корінь Меркле (сенті в аггр. транзакції)
… Ретранслятор має список транзакцій з дійсними підписами для переміщення із стану зі старим коренем у стан із новим коренем
ПЕРЕВІРКА здійснюється…
Розумний контракт (закодований у твердість, випер, як вам подобається!)
Відомі входи процесу перевірки - це ...
Той самий процес ПРОВІНГУ - відомі вхідні дані, очевидно ...!
Межі масштабованості
Ретранслятор не надсилає дані транзакцій до смарт-контракту (що коштує дорого), тому фактично обмеженням є кількість газу для перевірки підтвердження SNARK.
Згадуючи Говарда Ву робота про запуск фази PROVING SNARK на розподілених системах, barryWhiteHat оптимістично заявляє, що можна підтвердити 16666 транзакцій у величезному SNARK (1 мільярд обмежень!).
barryWhiteHat також думає, можна перевірити proof ланцюг з 500 тис. газу, це означає, що ти можеш поставити 16 SNARK (8 млн. / 500 тис.) на блок, що є ~ 1.07 ЗНАКИ в секунду ... що означає ~ 17,832 XNUMX тх в секунду (16,666 * 1.07).
До нескінченності і далі
- Все, що блищить, - це не золото / 1. Обсяг обчислювальної потужності та пам’яті, які вам потрібні у фазі доказування, може бути буквально шокуючим. Особливо у версії barryWhiteHat, де частина складності переміщується поза мережею. пише Баррі "На ноутбуці з 7 Гб оперативної пам'яті і 20 Гб місця для обміну він намагається об'єднати 20 транзакцій в секунду". Добре, якщо мета - 17,832 XNUMX tx за секунду ... LOL. Це створює нетривіальні завдання паралельного обчислення. Але якщо середня вартість угоди в доларах за транзакцію набагато дешевша за звичайну опцію no-SNARKs ... гра вартує свічки.
- Все, що блищить - це не золото / 2. Існує відповідна проблема доступності даних! Оскільки в контракті зберігається лише корінь дерева, ви повинні бути впевнені, що завжди доступна ціла версія дерева (або, те саме, вся історія транзакцій). Якщо дані недоступні, ретранслятор, навіть з дійсними підписаними транзакціями, не може нічого зробити, оскільки він / він не може довести старий стан → транзакції → новий штат.
- Щоб ретранслятор був недовірливим, а ефіри в контракті мали однакову вартість ефірів зовні (проблема ліквідності) ... користувачі повинні мати можливість знімати гроші зі смарт-контракту, коли захочуть, не покладаючись на (конкретного) ретранслятора. Як? Це не входить в обсяг цього 101 допису, але ви можете прочитати про це в доданих посиланнях.
- Хочете зрозуміти більше про те, як з поточним станом (адреси, залишки та заборони) можна обробляти дерево Меркла? Додавання листка, оновлення листка тощо? Перевіряти ця бібліотека (тестовий файл тут), який використовує цю основу Модулі. Дякую HarryR!
- Хочете налаштувати своє особисте середовище Ethereum-SNARKs? Почнемо з ланцюжка з C ++ (Налаштування, перевірка, перевірка) тут. Потім ви можете перейти до Ethereum (не забувайте, лише перевірка здійснюється в мережі!) За допомогою Zokrates (репо, документація для початку).
- Як щодо використання акумуляторів RSA замість дерев Merkle? Google “Rsa акумулятори ethereum” починати…
Насолоджуйтесь!
Twitter @marco_derossi
- 7
- рахунки
- ВСІ
- серед
- наявність
- Основи
- Мільярд
- випадків
- зміна
- Перевірки
- coinbase
- обчислення
- Консенсус
- контракт
- витрати
- Поточний
- Поточний стан
- DApps
- дані
- набір даних
- децентралізація
- Розмір
- Розподілена книга
- розподілена технологія логотипу
- Навколишнє середовище
- Ефір
- Ефіріума
- EU
- EV
- підроблений
- в кінці кінців
- Перший
- Безкоштовна
- функція
- гра
- ГАЗ
- GitHub
- дає
- золото
- добре
- великий
- керівництво
- мішанина
- тут
- Високий
- історія
- Як
- hr
- HTTPS
- величезний
- Сотні
- ia
- індекс
- інформація
- IP
- IT
- робота
- ключ
- портативний комп'ютер
- великий
- вести
- Гросбух
- рівень
- LG
- бібліотека
- ліквідності
- список
- Mainstream
- карти
- середа
- мільйона
- шахтарі
- гроші
- місяців
- Найбільш популярний
- рухатися
- Імена
- мережу
- вузли
- номера
- операції
- порядок
- Інше
- власник
- Платити
- Люди
- гравець
- популярний
- влада
- приватний
- Private Key
- програма
- проект
- доказ
- доводить
- громадськість
- публічний ключ
- Короткий огляд
- RSA
- Правила
- біг
- сейф
- економія
- масштабованість
- шкала
- Масштабування
- наука
- безпеку
- комплект
- Поділитись
- загальні
- Короткий
- простий
- Розмір
- сон
- розумний
- розумний контракт
- смартфон
- So
- Софтвер
- солідність
- Рішення
- ВИРІШИТИ
- Простір
- Витрати
- старт
- почалася
- стан
- Штати
- успішний
- система
- Systems
- Технологія
- тест
- час
- Жетони
- топ
- потік
- угода
- Transactions
- Довіряйте
- Updates
- користувачі
- значення
- перевірка
- visa
- W
- ВООЗ
- слова
- Work
- працює
- вартість
- X