Принцип матрешки. От Арифметизации до FRI
Приветствуем на третьей, заключительной части цикла о Starknet. В этой статье мы разберем как работает блокчейн Старка с технической стороны.
Целью протокола STARK является лаконичная(S) и прозрачная(T) проверка вычислений. Первый шаг в STARK называется арифметизацией — то есть проверка того, что многочлен имеет низкую степень.
STARK пытается свести проблему целостности вычислений к задаче тестирования низкой степени. Сначала идет арифметизация - проверка того, что проверяемый многочлен имеет низкую степень, потому что если используемый нами набор полиномиальных ограничений имеет высокую степень, это отрицательно влияет на длину доказательства и время, необходимое для его генерации. Первый шаг арифметизации состоит из двух компонентов:
1) Трассировка выполнения. Это таблица, представляющая этапы базового вычисления, где каждая строка представляет собой один шаг.
2) Набор полиномиальных ограничений. То есть ограничение области вычислений, чтобы исключить слишком низкие и слишком высокие значения. Полиномиальные ограничения выполняются только тогда, когда трассировка представляет допустимое вычисление.
Тип трассировки выполнения, который мы хотим сгенерировать, должен обладать особым свойством краткой тестируемости — каждая строка может быть проверена, опираясь только на строки, которые близки к ней в трассировке, и одна и та же процедура проверки применяется к каждой паре строк. К примеру, мы можем взять чек из супермаркета, добавив дополнительный столбец с текущим итогом(текущий итог в данном случае будет представлять результат сложения каждой строки между собой, начиная с нуля). Потому что такое дополнение позволяет нам проверять каждую строку по отдельности, учитывая предыдущую строку.
Например, взяв 2-ую и 3-ю строку мы можем убедиться что общий итог верный, так как 2.2+3.1=5.3 . Подобное ограничение применяется к каждой паре строк. Это то, что мы подразумеваем под краткими ограничениями.
Второй шаг арифметизации.
Цель STARKnet - дать возможность верификатору задавать проверяющему небольшое количество вопросов и решать, принимать или отклонять доказательство с максимально возможно высоким уровнем точности. В идеале, верификатор хотел бы попросить проверяющего предоставить значения в нескольких случайных местах в трассировке выполнения и проверить, выполняются ли полиномиальные ограничения для этих мест. Но можно сделать неправильную трассировку выполнения, которая имеет ошибку в одном месте, и тогда верификатор вряд ли сможет обнаружить проблему.
С подобными проблемами может справиться код исправления ошибок. То есть преобразование набора строк, так, чтобы они стали длиннее и попарно сильно отличались друг от друга. На практике такие коды представлены кодами Рида-Соломона(RS)
RS - код Рида-Соломона - это добавление дополнительных избыточных элементов для предотвращения потери данных, так как с помощью этих избыточных элементов мы можем вычислить потерявшиеся части данных.
Что же нам это дает? Прувер предоставляет еще дополнительное доказательство g. Если есть две функции, которые вычисляются на одном и том же множестве S и их степень меньше d, а S>100d, тогда, если они не являются одной и той же функцией, то вероятность, того, что они совпадут равна < 0,01. Эти функции которые имеют d степень, не могут отличаться более чем на d, у них не может быть больше d значений по которым они сходятся, если это не одинаковые функции. То есть, мы ограничиваем поле вычислений, чтобы максимально возможное значение было конечным числом(представьте часы, если мы к 10 прибавим 3 часа, то получим 1 час , потому что значения в этом поле не могут быть больше 12) , строим график функции и смотрим в каких точках вторая функция будет сходится с первой.
Если у вас есть фрагмент данных, и вы кодируете их в виде линии, то вы можете выделить четыре точки на линии. Любых двух из этих четырех точек достаточно, чтобы восстановить исходную прямую и, следовательно, также дать вам две другие точки. Более того, если вы внесете хотя бы малейшее изменение в данные, то это гарантирует по крайней мере три из этих четырех точек. Вы также можете закодировать данные в виде полинома с 1 000 000 степенями и выбрать 2 000 000 точек полинома; любые 1 000 001 из этих точек восстановят исходные данные и, следовательно, другие точки, и любое отклонение в исходных данных изменит по меньшей мере 1 000 000 точек.
Но STARK на этом уровне не вычисляет все полиномы целиком, а смотрит близко ли они расположены, так как в данном случае, если полиномы не равны друг другу, то они будут очень сильно отличатся с большой долей вероятности.
Такую методику можно обобщить как состоящую из двух частей:
1) Использования небольшого количества запросов
2) Выполнения верификатором небольшого вычисления для каждого запроса
Небольшое количество запросов достигается с помощью кодов исправления ошибок.
Работу верификатора можно обозначить как:
- Запрос композиционного полинома в случайных местах(многочлен для вычисления проверочных символов)
- Проверку низкой степени на основе этих запросов.
Проверка низкой степени в STARKnet выполняется с помощью протокола (FRI). Чтобы понять что такое FRI погрузимся в тему систем доказательств.
Немного углубимся в Proof systems
Как мы можем кому-то доверять? На ум сразу же приходит посредник или нотариус. Но откуда нам знать, не замешаны ли все они в какой-то мутной теме? Давайте отбросим кожаных мешков и доверимся технологиям. Начнем сразу с козырей, блокчейн - отличный вариант достижения вычислительной целостности. Однако, в блокчейнах, где распространено воспроизведение вычислений, проверяющих каждую транзакцию повторно возникают проблемы в виде конфиденциальности и масштабируемости. Очевидно, если проверять каждую транзакцию о конфиденциальности не может идти и речи. Тоже самое с масштабируемостью. Требуя от системы прозрачности, не получится ее масштабировать простым переходом на большую мощность.
Эти проблемы помогут решить proof systems (Системы доказательств) с нулевым знанием.
Proof System состоит из пяти основных элементов:
1. Формальный язык: Язык, на котором формулируются утверждения.
2. Аксиомы: Необходимые предпосылки или исходные утверждения.
3. Правила вывода: Методы, используемые для формирования заключений из аксиом.
4. Вывод доказательства: Процесс доказывания истинности утверждений.
5. Надежность и полнота: Гарантии, что система доказательств работает корректно.
В интерактивном доказательстве верификатор обменивается сообщениями с проверяющим, принимая решение на основании этого обмена. Особенностью IP является использование zero-knowledge, позволяющего убедить верификатора в правильности утверждения, не раскрывая при этом само утверждение. То есть чтобы убедить верификатор в правильности утверждения prover задает несколько случайных вопросов. Это повторяется до тех пор, пока верификатор не убедится в правильности утверждений prover'a. За счет такого рода случайности prover может доказать свое утверждение не раскрывая информацию об этом утверждении. (zero-knowledge)
Probabilistically Checkable Proofs (PCP)
Это доказательства, которые могут быть проверены с помощью рандомизированного алгоритма, читающего ограниченное количество битов доказательства. Особенностью PCP является роль "случайного оракула", который предоставляет верификатору доступ к случайным частям доказательства. Затем требуется, чтобы алгоритм принимал правильные доказательства и отклонял неправильные доказательства с очень высокой вероятностью. "Случайный оракул” дает PCP возможность запрашивать расшифровку доказательства случайным образом. Таким образом, проверяющий не может предсказать запросы заранее. В случае PCP, когда мы говорим, что у нас есть доступ к “случайному оракулу”, это означает, что у нас есть доступ к расшифровке доказательства и источнику случайности, так что верификатор может получить доступ к случайным частям расшифровки доказательства. Получается, обмануть такую систему не так-то просто, из-за того, что prover не может знать заранее какие из частей доказательства запросит верификатор, поэтому подтвердить ложное утверждение имея на руках несколько фрагментов правдивого утверждения очень сложно.
PCPP - это система PCP, в которой верификатор имеет разрешение от oracle к своим входным данным в дополнение к доказательствам проверяющих. PCPP требуется для отклонения только пары входных данных (x, y), в которых второй элемент (y) далек от соответствия первому элементу (т.е. y находится далеко от L(x)).
Interactive Oracle Proof (IOP)
IOP сочетает в себе Interactive Proof (IP) и Probabilistically Checkable Proofs (PCP), считаясь одной из самых надежных систем доказательств. В IOP, верификатор имеет доступ к сообщениям проверяющего через oracle и может запрашивать их вероятностно. Верификатор не обязан читать сообщение полностью, но может вероятностно запросить его. В раунде взаимодействия: верификатор отправляет сообщение пруверу; затем прувер отвечает сообщением верификатору, которое верификатор может запросить в этом и всех последующих раундах (имея доступ от oracle к нему). После всех раундов взаимодействия верификатор либо принимает, либо отклоняет.
IPCP, в отличие от IOP, так же сочетает в себе IP и PCP, скорее является частным случаем IOP, верификатор имеет доступ oracle к первому сообщению проверки, но должен полностью прочитать последующие сообщения проверки
Интерактивные доказательства близости oracle (IOPP)
IOPP обобщают как IP, так и PCP, предлагая множество раундов взаимодействия, где верификатор может запросить рандомные части сообщений проверяющего. Это уменьшает общую длину доказательства и сложность проверки, не уменьшая при этом надежность системы. К чему все это?
- Основным нововведением и основным источником повышения производительности Starknet является расширенное использование модели IOP, включая протокол Fast Reed-Solomon (RS) IOP of Proximity (IOPP) (FRI).
- Основой FRI является Algebraic Sketch. Если дана функция f и случайное начальное значение b и функция f определена в области D , тогда Algebraic Sketch будет f/2. Это похоже на быстрое преобразование Фурье, где из одной функции получается несколько (в данном случае один) меньших(меньшего) размера.
- Первым делом верификатор дает проверу случайное начальное значение b и запросит Algebraic Sketch с f и b, далее для получившегося f верификатор опять запрашивает b и так продолжается до тех пор, пока такое понижение степени не становится постоянным.
- Второй шаг FRI - Это запрос в рандомных этих функций f и проверка того, равны ли получившиеся Algebraic Sketch предыдущему f/2
- Если все же случается так, что происходит обман и f имеет высокую степень, то FRI должен с очень высокой вероятностью отвергнет это. Но возникновение таких случаев очень маловероятно, из-за прошлых операций STARK.
- Если все прошло гладко, то мы получаем подтверждение транзакции.
Таким образом все эти системы "защиты" работают для того, чтобы обеспечить большую конфиденциальность и масштабируемость.
Здесь я объяснил свое понимание STARK. Если вы обладаете большей информацией и квалификацией по математике Старкнет, пишите комментарии, с радостью бы полностью разобрался в этой теме.
1) StarkWare Sessions 23 | FRIs and other tasty treats | Prof. Swastik Kopparty https://www.youtube.com/watch?v=moBpLN2EOCg
2) STARKS I - Arithmetization Eli Ben Sasson Technion Cyber Computer Security https://www.youtube.com/watch?v=9VuZvdxFZQo
3) STARKs II - Low Degree Testing Eli Ben Sasson Technion Cyber and Computer Security Summer School https://www.youtube.com/watch?v=L7tZeO8ihcQ
4) STARK Math Ramp Up https://docs.google.com/document/d/e/2PACX-1vTXu1-bLgcb3RPH9ch4S5UqXermcmjC2d4BLykF1RvXgsFoPFFKjxHQyg_C3RmZjYQ5reSr6_HupFz4/pub (Это огромный набор статей для тех кто хочет углубиться в STARKnet самостоятельно)