Рейтинг:1

zkSnark: преобразование R1CS в QAP

флаг et

Я читаю страницу Виталина Бутерина на R1CS & QAP - https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

Я понял до той части, где он получает

$A=\begin{pmatrix} 0&1&0&0&0&0 \ 0&0&0&1&0&0 \ 0&1&0&0&1&0 \ 5&0&0&0&0&1 \ \end{pmatrix}$

$B=\begin{pmatrix} 0&1&0&0&0&0 \ 0&1&0&0&0&0 \ 1&0&0&0&0&0 \ 1&0&0&0&0&0 \ \end{pmatrix}$

$C=\begin{pmatrix} 0&0&0&1&0&0 \ 0&0&0&0&1&0 \ 0&0&0&0&0&1 \ 0&0&1&0&0&0 \ \end{pmatrix}$

Теперь, когда он конвертирует R1CS в QAP, он пишет

То есть, если мы оцениваем полиномы при x=1, то получаем наш первый набор векторов, если мы оцениваем полиномы при x=2, то получаем второй набор векторов и так далее.

Исходные наборы векторов A, B и C вообще не были созданы какими-либо x=1, x=2 и т. д. Они имели отображение

$['~one', 'x', '~out', 'sym\_1', 'y', 'sym\_2'] = [ 1, 3, 35, 9, 27, 30]$

т. е. они были рассчитаны с использованием $х = 3$ (который является корнем многочлена $х^3 + х + 5 = 35$)

Поэтому я не понимаю, как он приравнивает их к выборке при x=1, x=2 и т. д.

Может кто-нибудь объяснить?

Рейтинг:1
флаг cn

Во-первых, важно понять, сколько информации содержит полином степени $д$ может содержать. Он характеризуется $д+1$ изображений (подумайте о многочленах Лагранжа, чтобы понять, почему).

Итак, теперь мы должны сосредоточиться на одном конкретном предложении в ссылке, которую вы написали: «Мы переходим от четырех групп из трех векторов длины шесть к шести группам из трех полиномов степени 3, где оценка полиномов в каждой координате x представляет собой одно из ограничений».

Это подразумевает, что каждая группа соответствует образам многочленов для одного конкретного значения. (Поскольку мы произвольно решаем интерпретировать это таким образом). $ я ^ \ текст {й} $ группа дает нам изображения для ввода $я$.

Например, если бы я вычислил первый многочлен $P_{1,1}$ первого вектора. я буду вычислять $P_{1,1}$ степени не более $3$ такой, что $P_{1,1}(1)= x_1, P_{1,1}(2) = x_2, P_{1,1}(3) = x_3, P_{1,1}(4)=x_4$, с $x_i$ первая координата первого вектора $ я ^ {\ текст {й}} $ группа.

Эти уравнения определяют только один многочлен (я не уверен, что смогу объяснить лучше, чем тот, что в вашей ссылке), но если вы хотите узнать об этом больше, вы можете прочитать: https://en.wikipedia.org/wiki/Lagrange_polynomial

В более общем случае мы можем сделать то же самое для вычисления $ j ^ {\ text {th}} $ многочлен $P_{j,k}$ принадлежащий $ к ^ {\ текст {й}} $ вектор, глядя на $ к ^ {\ текст {й}} $ координаты $ j ^ {\ text {th}} $ векторы групп.

флаг et
Я знаю, что (n + 1) точки определяют и полином степени n. Интерполяция Лагранжа используется для нахождения полинома n-й степени, когда известно n+1 точек полинома. Однако здесь мы уже знаем многочлен - $x^3 + x -30$ - поэтому я не могу понять, почему именно мы используем интерполяцию Лагранжа?
флаг et
Я знаю, что $L_i(x)= \prod_{j=0}^n \frac {x-x_j} {x_i - x_j}$ & $P_n(x) = \sum_{i=0}^n L_i(x) у_и$. Однако я не могу сопоставить его с используемыми вами символами - $P_{j,k}(1)$ и $P_{j,k}(2)$ - что здесь (1) и (2) - это это P(x=1) и P(x=2) и что такое $P_{j,k}$?
Ievgeni avatar
флаг cn
координата $j^{\text{th}}$ вектора $k^{\text{th}}$
флаг et
Интерполяция Лагранжа используется для нахождения полинома n-й степени, когда известно n+1 точек полинома. Однако здесь мы уже знаем многочлен — x3+x–30, поэтому я не могу понять, почему именно мы используем интерполяцию Лагранжа?
Ievgeni avatar
флаг cn
Я говорю о полиномах в этом предложении: «Мы переходим от четырех групп из трех векторов длины шесть к шести группам из трех полиномов степени 3».

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.