Руководство для начинающих, которое мне бы понравилось несколько месяцев назад, прежде чем копаться в этом материале
Что вам нужно:
- фон информатики
- основы Ethereum
- основы исчисления (оптимизация ограничений)
Что вы получите:
- основы SNARK с нулевым знанием
- основы деревьев Меркле
- как Ethereum может масштабироваться до тысяч транзакций в секунду благодаря SNARKs
SNARKs позволяют Проверяющему доказывать Верификатору, что она / он имеет решение W для проблемы F с общими / известными входами X, не раскрывая W.
Поиск решения проблемы может потребовать огромных вычислительных ресурсов и памяти.
Таким образом, Verifier может быть на 100% уверен, что Prover работал правильно (и нашел решение), ни с тем, чтобы не делать работу самостоятельно, чтобы проверить решение, ни зная решение вообще. Это магия!
Процесс состоит из 3 шагов:
- УСТАНОВКА - Задача F (которая должна быть выражена в виде квадратичной арифметической программы, см. Ниже) подготовлена для SNARK. Этот процесс занимает очень много памяти и требует значительных вычислительных ресурсов в зависимости от сложности задачи (→ Количество входов и ограничений → Размерность матрицы задачи удовлетворения ограничений). Игрок, выполняющий настройку (может быть самим верификатором), должен быть доверен всем сторонам, поскольку выходные данные установки используются на следующих этапах. Настройка обычно выполняется с использованием libsnarkбиблиотека C ++, которая является наиболее популярной реализацией для zkSNARKs.
- ДОКАЗЫВАНИЯ - Проверяющий, у которого есть решение W для проблемы F с общими входами X (возможно, он / она потратил огромное количество ресурсов процессора и памяти, чтобы найти его!), Использует libsnark и выход Установка фаза для создания доказательства 𝚷. Этот процесс определенно требует большого объема памяти и вычислительных ресурсов (в зависимости от сложности проблемы, как указано выше). Размер выходных данных (т. Е. Доказательство instead) вместо этого является кратким и постоянным независимо от сложности задачи. Проверяющий должен доверять тому, кто выполнил фазу установки, поскольку он / она использует ее вывод ...
- ПРОВЕРКА - Верификатор - выдающий в качестве входных данных выходные данные фазы установки, общие входы X и подтверждение 𝚷 - проверяет подтверждение. Если проверка прошла успешно, Проверяющий сумел доказать Верификатору, что он / она нашел решение W проблемы F… не раскрывая W! Приятной особенностью является то, что не только Proof является лаконичным и всегда имеет одинаковую длину ... процесс проверки является быстрым и не требует большого объема памяти / вычислений. В отличие от двух предыдущих этапов ... проверку можно легко выполнить с помощью смартфона за миллисекунды!
Хороший итог (источник):
Как это может случиться? Ну, это магия Мерлина! Если вы хотите получить математику за этим, начать отсюда.
Как я могу преобразовать свое программное обеспечение в квадратичную арифметическую программу?
Как упомянуто выше, проблема F фазы установки должна быть квадратичной арифметической программой. Правила игры жесткие:
- Входные данные вашего программного обеспечения должны быть числами. Преобразуйте ваши вещи (массивы, строки и т. Д.) В числа. Это тривиально.
- «Квадратично ограниченная система уравнений» означает:
где x - это n-мерный вектор ваших входных данных, m - это число ограничений (т. е. число уравнений вашей системы), C - это матрица коэффициентов n-на-n, а q - это n-мерный вектор коэффициентов. Если вам не нравятся матрицы и векторы, вот случай n = 3 и m = 2 (3 входа, 2 ограничения):
- Реализация представляет собой арифметическую схему, которая означает, что результат Задача решена (система решена, т.е. все полиномы равны 0) или Проблема не решена (все остальные случаи). Другими словами: «эти материалы являются / не являются одним из решений этой проблемы».
- Коэффициенты C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 являются ограничениями системы. Это в основном то, что определяет ваше программное обеспечение. Измените их ... и вы получите другое программное обеспечение! Возвращаясь к тому, как работают SNARK: C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 являются входными данными фазы установки. Поэтому выходные данные фазы установки (которые вам нужны для проверки и проверки) строго связаны с этими C to, C₂,…, C𝚖, q₁, q₂,…, q𝚖 и работают только для этой проблемы. Если вы меняете их, вы определяете другое программное обеспечение / проблему, и вам нужно перезапустить этап установки! x₁, x₂,…, x𝗇 - переменные (то есть то, что вы должны угадать, чтобы получить системное решение). Поэтому, когда мы говорим «Уважаемый проверяющий, не могли бы вы найти секретное решение W для проблемы F с общими / общими входами X», мы имеем в виду, например, «Уважаемый проверяющий, можете ли вы найти значения x₁, x₂,…, x𝗇, которые решают систему? например, x₇ = 2393, x₅₂₆ = 5647? » Вы можете делать что хотите со всеми x all, кроме x₇ и x₅₂₆, которые ограничены общими / общими входами.
Это тяжелая жизнь, но вы можете выжить ... Если вам нужны петли, вы можете развернуть их, повторяя одну и ту же операцию много раз. Или, если вам нужно, например, x₁⁴ x₂⁵, вы определяете новый ввод x₃ = x₁⁴ x₂⁵ и используете x₃ в своих ограничениях. Это все о добавлении переменных и ограничений ... Даже для довольно простых программ легко достичь сотен миллионов или миллиардов входов и ограничений!
Хотите узнать больше? Читать здесь, А также проверить это основное code_to_r1cs.py из эфириума / исследования.
Что такое дерево Меркле?
Хеш-функция - это правило, которое отображает вход произвольного размера на выход фиксированного размера. Мы могли бы придумать довольно бесполезную хеш-функцию «Объединить первые две с двумя последними буквами», которая преобразует «Вуди Аллена» в «Вуэн» и «Пол Маккартни» в «Пей».
Дерево Меркле - это структура данных, где каждый родительский элемент является хешем двух его сыновей. Вверху вы найдете Root, который является хешем двух сыновей уровня 1. Внизу каждый лист является хешем внешнего ввода.
Используя нашу фразу «Woody Allen» → «Woen»:
Когда лист меняется, модификация распространяется до корня. Если меняется ANTHONY, меняются также ANNY (лист), CENY и CECO (корень). Какой бы лист не менялся, корень тоже меняется.
Вам не нужно все дерево, чтобы пересчитать корень. В нашем примере, если ANTHONY изменится и вы знаете JACO и CECILY, вы можете легко пересчитать Root, даже если вы полностью игнорируете JAMES, MARCO, JAES и MACO. Для огромных деревьев это экономит много времени!
И что?
Деревья Меркле отлично подходят для проверки целостности данных. Обычно: вы знаете, какой является действительным Root, и вы проверяете, что полученные данные соответствуют этому Root. Например: доверенная сторона, которая не может предоставить вам полный набор данных имен людей на Земле (нет времени, нет пропускной способности или, возможно, она / он вообще не имеет данных), дает вам только Root (например, «ОКЭС»). Послесловие: вы получаете миллионы имен, со ссылкой на номер листа, тысячами ненадежных сторон. Ну, поскольку у вас есть правильный Root, вы можете проверить, на кого можно положиться, кто дает вам поддельные данные ...
Меркле - это тоже часть твоей жизни! Когда вы скачиваете 3-ГБ торрент-файл, ваш файл делится на миллионы маленьких кусочков. Хэш каждого куска хранится в листе. Так как вы знаете, какой является действительным корневым каталогом дерева, каждый раз, когда кто-то получает фрагмент файла, вы можете проверить его правильность. Если это не так, вы можете попросить тот же кусок кому-то еще.
Вы можете сделать это, даже если вы еще не загрузили все дерево / все листья: если вы знаете, что Root - это CECO, и вы доверяете JACO… когда вы получаете чок ANTHONY, вы можете проверить это, даже если вы не загрузили все же куски МАРКО и ДЖЕЙМС.
Почему деревья Merkle полезны в технологии распределенной бухгалтерской книги, просто: вы используете согласованные протоколы (медленные, дорогие) только для достижения консенсуса по корню. Тогда ненадежные узлы сети могут эффективно и напрямую обмениваться данными… и могут спать спокойно и безопасно благодаря проверкам целостности с Root.
Когда Бог попросил Эфириум выбрать 2 сверхдержавы: безопасность, масштабируемость и децентрализация ... Эфириум пожертвовал масштабируемостью. На самом деле не существует строгого ограничения «транзакций в секунду»: ограничение касается количества газа в каждом блоке, что упрощает количество операций, которые я могу выполнять в каждом блоке. Этот лимит составляет 8 миллионов газов. Это может означать много «крошечных» транзакций (нет данных, прикрепленных к транзакциям, нет операций, которые должны выполняться над этими данными) или несколько крупных транзакций. Это зависит от узлов Ethereum, которые отправляют транзакции, и от майнеров Ethereum, которые включают в блок транзакции, которые платят больше.
Блок добыт каждую ~ 15 секунд Это означает ~ 32 миллиона газа в минуту, что, безусловно, недостаточно, если мы хотим, чтобы dapps Эфириума стали массовыми.
Кстати: прекратите эти утомительные сравнения между Ethereum и Visa. Централизованная система будет всегда будь быстрее Эфириума ... по замыслу! Они делают разные вещи, и они нужны вам в разных ситуациях. Если вам не нужна децентрализация и обстановка без доверия… конечно, вам следует выбрать Visa. Коротко: тот факт, что ваш блендер вращается быстрее, чем ваша стиральная машина, не означает, что вы будете чистить брюки в блендере!
Давайте вместе составим пазл! Представьте, что вы можете «сжать» множество крошечных транзакций за одну крупную транзакцию благодаря SNARK. Если газ, потраченный на эту крупную транзакцию, меньше, чем сумма газа, потраченного на крошечные транзакции, это означает, что вы экономите газ.
А экономия газа означает:
- Пользователи тратят меньше на транзакции в целом → Это будет толчком для всей экосистемы
- Возможность поместить больше вещей в блок → Эфириум вращается быстрее, чем ваш блендер!
Как это работает?
Есть пользователи, ретранслятор (или несколько ретрансляторов), который объединяет транзакции и умный контракт.
- Пользователи, желающие поиграть в эту игру, отправляют свои Эфиры (или токены) на публичный аудит смарт-контракта. Для каждого нового игрока создается новый лист в дереве Меркле. Лист содержит информацию о владельце Эфира (его / его адрес, который также является открытым ключом), количестве Эфира и одноразовых номеров (счетчик транзакций этой учетной записи, который равен 0, когда лист добавляется)
- Когда A хочет отправить Ether на B (им обоим необходимо иметь лист / учетную запись в смарт-контракте), A упаковывает транзакцию, которая включает в себя адрес отучетная запись в учетная запись нунций из счета, количество эфира для передачи и подпись транзакции (очевидно, подписанный закрытым ключом учетной записи «from»). Затем он / она отправляет упакованную транзакцию ретранслятору.
- Ретранслятор агрегирует все транзакции, полученные за определенный промежуток времени (например, за один час), обновляет дерево Merkle суммами новых балансов и создает SNARK-доказательство, которое подтверждает, что все подписи и корень нового дерева Merkle действительны. В конце концов, ретранслятор отправляет новое состояние и подтверждение смарт-контракту.
- Интеллектуальный контракт подтверждает Proof on-chain. Если он действителен, он сохраняет корень дерева Merkle состояния New во внутренней памяти контракта.
По сути, корень дерева Merkle отображает все состояние всех учетных записей. И вы не можете изменить его (= украсть деньги), если не можете доказать действительность подписей, транзакции которых приводят к состоянию New, суммируемому новым корневым каталогом, который вы отправляете.
В двух словах: пользователи совершают очень быстрые и почти бесплатные транзакции, как на Coinbase, без необходимости доверять ретранслятору, который ничего не может сделать, в отличие от Coinbase, без вашей подписи.
Это боковая цепь, не связанная с тюремным заключением, состояние которой суммируется с корнем дерева Меркле.
Давайте свяжем то, что мы узнали о SNARKs выше, с тем, что мы только что обсуждали о масштабировании. Есть разные способы сделать это. Я сравню 2 рецепта: Виталика версия и barryWhiteHat's версия.
НАСТРОЙКА выполняется ...
Парень, который запускает проект, который также создает умный контракт. Чем более одитим, тем лучше. Вы должны доверять ей / ему ... это доверенная настройка!
Умный контракт экономит ...
2 Корни Merkle (значения bytes32): первое дерево содержит адреса учетных записей (публичные подписи), остатки и одноразовые счета вторых учетных записей
ПРОВЕРКА выполняется ...
Реле
Эстафета отправляет смарт-контракт ...
- 2 корня Меркле Нового состояния (дерево адресов и балансов + дерево одноразовых номеров)
- список транзакций, без подписей. «Каждая транзакция стоит 68 газов за байт. Следовательно, для обычного перевода мы можем ожидать, что предельные издержки будут 68 * 3 (с) + 68 * 3 (до) + 68 * 1 (комиссия) + 68 * 4 + 4 * 2 (сумма) + 68 * 2 (nonce) или 892 газа »
Доказательство известных входных данных процесса ...
- 2 Старые государственные корни Меркле
- 2 новых государственных корня Меркле
- список транзакций
Доказательство процесса доказывает, что ...
Данный
- 2 старых государственных корня Меркле (уже хранятся в договоре)
- 2 новых состояния корней Меркле (отправлено в аггр. транзакции)
- список транзакций (отправлено в агг. транзакции)
… У ретранслятора есть действительные подписи для перехода из состояния с двумя старыми корнями в состояние с двумя новыми корнями с этими транзакциями.
ПРОВЕРКА выполняется ...
Умный контракт (закодирован в солидности, выпер, сколько угодно!)
Известные входные данные процесса ПРОВЕРКИ…
То же самое доказательство процесса известный вклад, ясно ...!
Ограничения масштабируемости
Каждая агрегированная транзакция использует 650k газа для проверки SNARK (фиксированная цена) плюс ~ 900 газ предельные издержки за транзакцию (стоит отправить данные!). Таким образом, используя весь блок, ретранслятор может агрегировать не более:
что значит ~ 544 ткс в секунду
barryWhiteHat-х версия
НАСТРОЙКА выполняется ...
Парень, который запускает проект.
Умный контракт экономит ...
1 Merkle root с текущим состоянием. Каждый лист - это хешированное состояние аккаунта.
Хотите, чтобы Создайте счет?
state = AccountState (pubkey, balance, nonce)
state.index = self._tree.append (state.hash ())
ПРОВЕРКА выполняется ...
Реле
Эстафета отправляет смарт-контракт ...
- доказательство 𝚷
- Новый государственный корень Меркле
- доказательство 𝚷
Доказательство известных входных данных процесса ...
- Старый государственный корень Меркле
- Новый государственный корень Меркле
Доказательство процесса доказывает, что ...
Данный
- старый корень Merkle (уже хранится в контракте)
- Новый корень Меркле (сенти в аггр. транзакции)
… У ретранслятора есть список транзакций с действительными сигнатурами для перехода из состояния со старым корнем в состояние с новым корнем
ПРОВЕРКА выполняется ...
Умный контракт (закодирован в солидности, выпер, сколько угодно!)
Известные входные данные процесса ПРОВЕРКИ…
То же самое доказательство процесса известный вклад, ясно ...!
Ограничения масштабируемости
Ретранслятор не отправляет данные транзакций в смарт-контракт (который является дорогостоящим), поэтому ограничение - это фактически количество газа для проверки доказательства SNARK.
Упоминание Говарда Ву работает о запуске этапа SNARK PROVING в распределенных системах, barryWhiteHat оптимистически утверждает, что возможно подтвердить 16666 транзакций в огромном SNARK (1 миллиард ограничений!).
barryWhiteHat также считает можно проверить доказательство 𝚷 на цепочке с газом 500 тыс., что означает, что вы можете поставить 16 СНАРКОВ (8 млн. / 500 тыс.) на блок, что ~ 1.07 SNARKs в секунду ... что означает ~ 17,832 XNUMX TX в секунду (16,666 1.07 * XNUMX).
Бесконечность не предел
- Все, что блестит, это не золото / 1. Объем вычислительной мощности и памяти, которые вам нужны на этапе проверки, могут быть буквально шокирующими. Особенно в версии barryWhiteHat, где часть сложности перенесена за пределы цепочки. Барри пишет «На ноутбуке с 7 ГБ оперативной памяти и 20 ГБ пространства подкачки он пытается объединить 20 транзакций в секунду», Хорошо, если цель составляет 17,832 XNUMX тх в секунду ... LOL. Это вводит нетривиальные задачи параллельных вычислений. Но если средняя цена за транзакцию в долларах намного дешевле, чем в обычном варианте без SNARK… игра стоит свеч.
- Все, что блестит, не золото / 2. Есть актуальная проблема с доступностью данных! Поскольку в контракте сохраняется только корень дерева, вы должны быть уверены, что всегда доступна вся версия дерева (или, что то же самое, вся история транзакций). Если данные недоступны, ретранслятор, даже с действительными подписанными транзакциями, не может ничего сделать, потому что он / он не может доказать Старое состояние → Транзакции → Новое состояние.
- Чтобы ретранслятор был ненадежным, а эфиры в контракте имели одинаковую стоимость эфиров извне (проблема ликвидности)… пользователи должны иметь возможность снимать деньги с умного контракта, когда они хотят, не полагаясь на (конкретного) ретранслятора. Как? Это не входит в объем этого поста 101, но вы можете прочитать об этом в прилагаемых ссылках.
- Хотите узнать больше о том, как текущее состояние (адреса, балансы и одноразовые значения) может обрабатываться с помощью дерева Меркля? Добавление листа, обновление листа и т. Д.? Проверять, выписываться эта библиотека (тестовый файл здесь) который использует этот базовый модуль, Спасибо ГарриR!
- Хотите настроить свою личную среду Ethereum-SNARKs? Давайте начнем с цепочки с C ++ (настройка, проверка, проверка) здесь, Затем вы можете перейти в Эфириум (не забывайте, только проверка выполняется в цепочке!) С Zokrates (РЕПО, документация для начала работы с).
- Как насчет использования аккумуляторов RSA вместо деревьев Меркле? Google Rsa аккумуляторы ethereum начать…
Наслаждайтесь!
Twitter @marco_derossi
- 7
- Учетная запись
- Все
- среди
- свободных мест
- Основы
- миллиард
- случаев
- изменение
- Проверки
- coinbase
- вычисление
- Консенсус
- контракт
- Расходы
- Текущий
- Текущее состояние
- DApps
- данным
- набор данных
- Децентрализация
- Размеры
- Распределенная книга
- распределенная бухгалтерская технология
- Окружающая среда
- Ether
- Эфириума
- EU
- EV
- не настоящие
- в заключение
- First
- Бесплатно
- функция
- игра
- ГАЗ
- GitHub
- Отдаете
- Золото
- хорошо
- большой
- инструкция
- хэш
- здесь
- High
- история
- Как
- hr
- HTTPS
- огромный
- Сотни
- ia
- индекс
- информация
- IP
- IT
- работа
- Основные
- портативный компьютер
- большой
- вести
- Ledger
- уровень
- LG
- Библиотека
- Ликвидность
- Список
- Mainstream
- Карты
- средний
- миллиона
- Шахтеры
- деньги
- месяцев
- Самые популярные
- двигаться
- имена
- сеть
- узлы
- номера
- Операционный отдел
- заказ
- Другое
- владелец
- ОПЛАТИТЬ
- Люди
- игрок
- Популярное
- мощностью
- частная
- Секретный ключ
- FitPartner™
- Проект
- доказательство
- доказывает
- что такое варган?
- публичный ключ
- резюме
- RSA
- условиями,
- Бег
- безопасный
- экономия
- Масштабируемость
- Шкала
- масштабирование
- Наука
- безопасность
- набор
- Поделиться
- общие
- Короткое
- просто
- Размер
- спать
- умный
- умный контракт
- смартфон
- So
- Software
- основательность
- Решения
- РЕШАТЬ
- Space
- Расходы
- Начало
- и политические лидеры
- Область
- Области
- успешный
- система
- системы
- Технологии
- тестXNUMX
- время
- Лексемы
- топ
- поток
- сделка
- Сделки
- Доверие
- Updates
- пользователей
- ценностное
- проверка
- визой,
- W
- КТО
- слова
- Работа
- работает
- стоимость
- X