Aleo: Доказательство с Нулевым Разглашением, или как Криптографы могут доказать все что угодно
Посмотреть оригинальное видео вы можете на Youtube канале Aleo, ссылка на него: https://www.youtube.com/watch?v=55t-UANj7k4&ab_channel=Aleo
Материал, на который ссылались в видео: https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
Мой Дискорд: useless_dorozhkina#1394
Привет! Меня зовут Эррол, и я глава отдела образования Aleo. В этом видео я хотел бы продемонстрировать, как криптографы могут доказать, что они знают что угодно с помощью Системы Ограничений Первого Ранга. Это тип доказательной системы, примерами которой являются Marlin и Graph 16.
Доказательные системы очень сложны и содержат множество действующих частей. Поэтому в данном видео мы можем упомянуть только несколько основных идей. Но в будущем мы с с удовольствием сделаем много других видео, в которых объясним другие основные идеи, входящие в доказательные системы.
Мы считаем, что это очень важно, так как в эти технологии вкладываются огромные суммы, и, если вы собираетесь заниматься этим, имеет смысл также попытаться понять технологию немного лучше. Не только для того, чтобы сильнее верить, что все функционирует так, как положено, и что не может быть никакой ошибки, но также и для того, чтобы иметь возможность использовать технологию более эффективно. Если вы понимаете, как все работает, будет легче придумывать новые способы использовать технологию с пользой и делиться этой пользой со всеми.
Данный разбор прежде всего основан на очень популярном блоге, написанном Виталиком Бутериным, где он рассказывал о системе R1CS на конкретном примере. И мы также используем этот пример. Так что большей частью это видео основано на посте. Для вас было бы очень познавательно читать эту статью одновременно с этим видео, если у вас есть время.
Давайте введем уравнение, знание которого мы хотим доказать. У нас есть x³ + x + 5 = 35. Мы собираемся доказать, что мы знаем решение этого уравнения, что мы знаем значение x, которое, если подставить его в выражение, даст верный результат.
Конкретно это уравнение взялось из ниоткуда. Это просто глупое уравнение, пример-игрушка. Главное это то, что у вас будет возможность превратить любую компьютерную программу в набор подобных уравнений, такой метод называется арифметизация. Сейчас у нас нет времени на это, но, если вы подумайте над этим, то это начинает иметь смысл. В компьютерах нули и единицы двигаются сквозь логические вентили И-НЕ, так не являются ли большие целые числа, проходящие через сложение и умножение, подобным явлением?
Первая вещь, которую нам необходимо сделать в данном процессе, называется “уплощение”. Нам нужно разобрать это уравнение на его основные действия. Говоря об основных действиях, мы имеем ввиду только сложение или только вычитание за один раз.
Например, первый элемент x³. Возведение в куб — это то же самое, что и умножение, но мы не может возвести в третью степень за одно действие. Нам придется разбить это на шаги.
Первым действием будет умножение x на x. В результате мы получим x². Но я буду называть этот квадрат int (от англ. intermidiate), потому что, если кто-то хочет подделать решение, они могут подставить неверное значение.
Следующим действием будет intermidiate 2, который представляет собой x в квадрате, умноженный на x.
Далее у нас получается int3, где мы берем x в кубе и добавляем к нему x.
И, наконец, мы добавляем ко всему этому 5.
В основном, у нас есть только два типа операций, которые мы можем выполнять:
Первая это у = x, то есть одна переменная просто равняется значению другой. Вторая y = x (op) z, где (op) — это какая-либо операция, и, на самом деле, в основном это будет только сложение или умножение. И вы можете видеть, что наши первые ограничения int и int2 относятся ко второму типу, y равен x, умноженному на z. Вторая же пара ограничений int3 и out имеют форму y равен x плюс z.
Следующий шаг — это создать систему ограничений. Для каждого из ограничений, которые мы задали выше, мы сделаем набор из трех векторов.
Я напишу в скобочках a1, b1 и c1. Все они являются векторами.
В нашем примере мы имеем четыре набора по три вектора, потому что мы задали четыре ограничения.
Так как много входов каждый из этих векторов имеет? Что ж, это зависит от нашей схемы, в частности, как много разных значений мы ожидаем увидеть в своей схеме.
Например, здесь у нас будет одно для каждой постоянной переменной. У нас будет int, int2, int3 и переменная, которую мы называем output (выходной). Итак, шесть элементов означают, что наши векторы имеют шесть входов.
На данном этапе, давайте сосредоточимся только на наборе векторов первого ограничения, чтобы мы смогли проделать следующие шаги. Мы соединим три набора векторов, приведенных выше, с другим вектором. И мы сделаем это с помощью скалярного произведения.
Коротко о скалярном произведении: если я возьму вектор а и подвину его сюда, и произведу скалярное умножение с вектором решений, то то, как вы это должны читать будет выглядеть следующим образом.
Сначала мы перемножим первые два входа, то есть 1 умножим на а11, затем мы добавим х, умноженный на а12, и мы пройдем так весь путь вниз, прибавляя эти четыре следующие произведения.
И после того, как мы сложим все эти значения, мы получим одну единственную переменную.
Теперь, когда вы увидели, как производить скалярное произведение векторов, мы можем показать вам полное уравнение.
И так, у нас есть вектор решений, умноженный на вектор а, и помните, это только одна переменная, и мы умножим это на вектор решений, скалярно умноженный на вектор b. И теперь наше утверждение состоит в том, что получившееся выражение будет равняться вектору решений, скалярно умноженному на вектор с.
Я сказал, что мы возьмем только первое ограничение, то есть int = x * x. С учетом этого, какие же переменные мы получаем внутри этих a, b и c векторов? На самом деле, это совсем не сложно решить. Помните, мы сказали, что структура этого ограничения имеет формат y = x (op) z, где операцией является умножение. Но здесь я повторно использую условное обозначение, потому что я говорю об этих иксах так, как будто они являются разными вещами. Но я просто хочу, чтобы вы думали о вещи слева операции, а здесь у нас просто x. Итак, это значит, что в нашем скалярном произведении, мы хотим подставить единицу в одной линии с x, а все остальное сделать нулями, потому что больше ничего слева нет.
Справа от операции у нас также стоит только единица на одной линии с x, и больше ничего. Теперь для того, чтобы приравнять ограничение слева к выражению решения справа, у нас есть одна копия int. У нас нет int2 или int3, или чего-либо еще. Мы просто хотим, чтобы единица стояла на одной линии с int.
Теперь, если мы возьмем второе ограничение, int2 = int * x, структура будет довольно похожей. Слева от операции у нас одна копия int, так что мы подставляем единицу на линию с int. А справа у нас снова x. Теперь на равной стороне у нас есть одна копия int.
Теперь мы сделаем то же самое для третьего ограничения.
Теперь что насчет того, что я называю “вектором решений”. Я немного намекаю на то, что это на самом деле, и это должно быть решением. Это должно быть вектором, который удовлетворяет каждому из этих ограничений.
Например, мы можем подставить какие-нибудь значения прямо сейчас так, чтобы удовлетворять четвертому выходному ограничению. И если вы подставите значения способом, представленным выше, вы сможете произвести скалярное произведение
и сложить значения так, как я упоминал ранее,
и мы увидим, что эта реализация вектора удовлетворяет этому ограничению.
Но что насчет других трех ограничений? Давайте посмотрим, как этот вектор удовлетворяет третьему ограничению. Мы снова скалярно умножим, и подставим в уравнение.
Но теперь (1 +2) * (1), которое равняется 3, мы говорим, что будет равняться 1.
Что ж, на самом деле, очевидно, что это неверно. Поэтому данная реализация вектора решений не будет правильной и не пройдет все проверки. Существует лишь несколько действительных векторов решений. Это кубическое уравнение, поэтому мы можем ожидать максимум три возможных решения.
Это должны быть единственные векторы, которые удовлетворяют всем ограничениям одновременно, и это то, знание чего мы будем доказывать. Понимаете, когда вы делаете Доказательство с Нулевым Разглашением, вы утверждаете, что знаете значения всех переменных, которые удовлетворяют всем ограничениям. Вы знали какую-то секретную информацию и запускали это вычисление. В общем случае, вы не сможете угадать, какими будут эти значения. Если бы вы могли, вы бы могли сломать эти системы.
Ниже представлены настоящие значения в векторе решений. Вы конечно могли бы получить их самостоятельно, потому что это довольно-таки легкий пример, но в более сложных вещах это заняло бы больше времени.
Давайте немного отдалимся. У нас было четыре ограничения.
И для каждого из этих ограничений у нас есть три a, b и c вектора.
Все, что мы выделили голубым, создает публичное разглашение начального уравнения. Наши четыре ограничения представляют собой вычисление, которое мы проводим. И значение 35 также будет публичным данным, потому что вы утверждаете, что данное уравнение равняется 35.
Другие элементы в этом векторе решений — это то, что мы собираемся спрятать.
Это будет то, что называется “частной информацией”, это и есть Нулевое Разглашение.
На самом деле, вы бы также могли спрятать и значение 35.
Но, если бы вы сделали это, и спрятали бы значение всего вектора решений,
вы бы просто утверждали, что вы знаете какое-то значение выражения x³ + x + 5, что это равняется чему-то. И теперь получается, что вы можете подставить любые значения в это вычисление. Это совсем не практично.
Сила Доказательств с Нулевым Разглашением идет от комбинирования общедоступной и приватной информации. Говоря, что вы знаете какое-то значение, когда вы проводите с ним вычисления, вы не получаете какое-то случайное значение на выходе. Вы определенно получаете значение 35. И вся общедоступная информация здесь будет использована, чтобы создать проверяющий ключ. Доказывающие также будут брать спрятанную дату, спрятанный вектор решений, и будут использовать его, чтобы создать свой доказывающий ключ.
Итак, все должны знать проверяющий ключ для того, чтобы иметь возможность проверить доказательство. Но только доказывающий должен знать доказывающий ключ, потому что он содержит в себе секретную информацию.
На данный момент мы знаем, как сплюснуть наше уравнение до фундаментальных шагов, как превратить эти шаги в систему ограничений, и теперь нам нужно узнать, это как нам зафиксировать эти данные таким образом, чтобы позволить нам доказать их некоторые свойства.
Для этого теперь мы обратимся к интерполяционному многочлену Лагранжа. Мы делаем это для того, чтобы зафиксировать значения переменных. Мы хотим зафиксировать такие значения так, чтобы дальше мы не могли менять их, и мы могли бы утверждать, что именно эти значения мы зафиксировали. Но мы также и не хотим, чтобы эти зафиксированные переменные что-либо раскрывали об информации, которую мы фиксировали.
Итак, для интерполяционного многочлена Лагранжа, я хочу взять 2D плоскость, и сейчас нам интересны только значения между 1 и 4. Давайте представим, что мы хотели зафиксировать 4 значения переменных 1, 3, 5 и 1.
Мы можем также думать об этом так, как как если бы мы фиксировали какую-то функцию, которая имеет значение 1 в точке х = 1, равняется 3 в точке х = 2, равняется 5 в точке х = 3 и снова равняется 1 в точке х = 4.
Мы сделаем это с помощью так называемых многочленов Лагранжа. Многочлен Лагранжа в точке 1 — это функция, которая принимает значение 1, когда х = 1, и принимает значение 0 во всех остальных точках области, которая нас интересует. На данный момент эта область состоит из 1, 2, 3 и 4.
Особенность этого полинома состоит в том, что это уникальный многочлен третьей степени, который удовлетворяет данным условиям. Так как область, в которой мы заинтересованы, содержит в себе четыре точки, многочлены Лагранжа здесь имеют третью степень.
Наш второй многочлен Лагранжа принимает значение 1 в точке х = 2, а в остальных точках х = 1, 3 или 4 принимает значение 0.
Справа здесь я обозначу L2(x) — это будет наше краткое обозначение второго многочлена Лагранжа. И над ним мы видим коэффициентную форму записи.
Теперь, если я хочу зафиксировать вектор, который принимает значение 3 в точке х = 2, все, что мне нужно сделать, так это взять три копии данного полинома Лагранжа., то есть умножить 3 на L2(x).
Все то же самое и для третьего полинома Лагранжа. Мне нужно будет взять пять его копий.
И, наконец, для четвертого полинома нам нужна будет только одна копия.
Теперь, если мы сложим все эти многочлены Лагранжа, мы получим уникальный многочлен третьей степени, который проходит через все значения, которыми мы интересуемся в нашей области.
Это была небольшая интерлюдия о том, как работает интерполяция Лагранжа.
Теперь мы знаем, что мы можем зафиксировать векторы чисел. И как же мы применим это к ограничениям, которые у нас уже имеются?
Что ж, у нас есть четыре ограничения по три вектора.
Я хочу взять только первые векторы из каждого триплета.
То есть вектор а в каждом случае, и поставить их вместе следующим образом.
Теперь я хочу сфокусироваться только на первых входах каждого из этих векторов. Мы вынесем их, сохраняя позиции, чтобы указать, что мы собираемся зафиксировать их.
И снова проведем интерполяцию Лагранжа.
Рассмотрим первый полином Лагранжа. В точке х = 1 нам нужно значение 0, поэтому нам не нужно никаких копий L1(x).
То же самое с L2(x) и L3(x). Нам не нужны их копии.
Но нам нужно будет взять пять копий L4(x).
Итак 5 * L4(x) будет интерполяцией этого вектора. Это и будет наша фиксация.
Теперь мы можем применить эту фиксацию ко всем входам векторов.
Мы сделали первый ряд, теперь мы можем сделать следующие пять, используя тот же алгоритм. И я поместил этот полином Лагранжа сверху, чтобы напомнить вам, как мы к этому пришли.
Мы можем записать форму Лагранжа или форму коэффициентов, но, в первую очередь, мы хотим записать выражение настолько компактно, как, насколько это возможно.
но, в первую очередь, мы хотим записать выражение настолько компактно, как Ai (x), чтобы нам было удобнее.
Я хочу напомнить нам, как мы сюда добрались. Эти четыре вектора получились из их собственных ограничений, а эти векторы ограничений были представлением шагов,
в то время, как шаги были просто действиями начального вычисления.
Повторим все, что мы сделали. У нас было наше начальное вычисление, которое мы сплюснули до его основных действий. Затем мы превратили эти действия в векторы ограничений,
где мы заполнили эти векторы на основе значений в возможном векторе решений.
Затем мы выстроили эти векторы таким образом, что у нас получились векторы a, b и c.
После того, как векторы были так организованы, мы хотели зафиксировать каждую линию, провести интерполяцию Лагранжа в каждой линии, чтобы зафиксировать значения.
И мы увидели, что, проведя такое с векторами а, мы получаем Ai (x).
Теперь мы хотели провести то же самое с векторами b и c, получая еще двенадцать многочленов ограничений.
После того, как мы получили все многочлены ограничений, мы хотим подставить их в уравнение с вектором решений и скалярным произведением.
Я хочу немного видоизменить это уравнение, переставить все слева от знака “равно”.
Я сделал это, потому что мы хотим, чтобы что-то равнялось нулю. Точнее говоря, это что-то будет равняться нулю для всех х в области, которую мы рассматриваем.
И помните, как раньше у нас были только отдельные ограничения в таком же формате? Но теперь, когда мы зафиксировали значения, каждое из ограничений показывается здесь как A, B и C многочлены. Если мы подставим в эти многочлены единицу,
мы получим вектор первого ограничения int = x * x.
Таким же образом, если бы мы подставили двойку, мы бы получили вектор второго ограничения int2 = int * x.
И то же самое было бы с третьим и четвертым векторами ограничений.
Видите, как теперь мы совместили всю нашу информацию, чтобы одновременно проверять все ограничения за раз.
Теперь вернемся к нашему равенству решения,
но теперь вместо отдельных ограничений у нас есть фиксации ограничений, которые являются общими многочленами Ai (x), Bi (x) и Ci (x).
Небольшое напоминание о том, как работает скалярное произведение. Теперь мы суммируем все ограничения вместе.
В результате мы получаем еще одно уравнение, просто A (х), которое каким-то образом сжимает все ограничения вектора решений в один единственный проверяемый вход.
Мы можем проделать то же и с другими ограничениями и получить выражение:
однако, стоит уточнить, что это выражение равняется нулю только при х, лежащих от 1 до 4.
Важное утверждение! Мы говорим, что это является истиной тогда и только тогда, когда:
Z (x) — это так называемый “исчезающий многочлен”. Он равняется нулю во всех точках интересующей нас области, то есть он равен нулю в точках 1, 2, 3 и 4. Его выражение записывается следующим образом:
Вы можете заметить, что, если вы подставите любые значения из нашей области, Z (x) будет равняться нулю. И, на самом деле, здесь представлен еще более важный алгебраический факт: все многочлены, которые равняются нулю в одной и той же области обязаны делиться на исчезающий многочлен.
H, которая стоит рядом с Z (x) в выражении выше, может быть произвольной. Мы утверждаем, что уравнение все равно будет удовлетворяться, потому что мы знаем, если все, что стоит слева от знака “=”, равняется нулю в наших четырех точках области, математика говорит нам, что оно обязано делиться на исчезающий многочлен.
На самом деле, это особый момент, который мы будем проверять. Мы хотим доказать, что все, что стоит слева в выражении, действительно делится на исчезающий многочлен Z (x). Если это не так, вы не получите многочлен после деления, вместо этого вы получите рациональную функцию. А это значит, что у вас не получится завершить доказательство. Это и есть основная идея, которую, в конце концов, мы хотим проверить.
Я понимаю, это было достаточно тяжело. И, на самом деле, мы даже не рассказали все, что хотелось бы, об R1CS системах.
Все, что мы показали вам, было довольно поверхностно, и это и есть та причина, по которой мы очень хотели бы делать больше видео в будущем, углубляясь в детали, чтобы вы смогли все понять. Но все же, мы надеемся, что вы что-то узнали о том, как работают R1CS системы, и также узнали несколько основных идей.
Если у вас остались какие-либо вопросы, или вы хотите продолжить обсуждение, вы можете посетить наш Дискорд, там проводятся беседы. Не стесняйтесь спрашивать все, что хотите!
Особенно мы хотели бы узнать, есть ли у вас какие-либо рекомендации, как мы могли бы изменить стиль своих видео, или о чем еще мы могли бы рассказать, что могло бы улучшить ваше понимание.
