Puncte:1

zkSnark: Conversia R1CS în QAP

drapel et

Citesc pagina lui Vitalin Buterin despre R1CS & QAP - https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

Am înțeles până în partea în care ajunge

$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}$

Acum, când convertește R1CS în QAP, scrie

Adică, dacă evaluăm polinoamele la x=1, atunci obținem primul nostru set de vectori, dacă evaluăm polinoamele la x=2, atunci obținem al doilea set de vectori și așa mai departe.

Seturile originale de vectori A, B și C nu au fost deloc create de niciun x=1, x=2 etc. Au avut maparea

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

adică au fost calculate folosind $x = 3$ (care este rădăcina polinomului $x^3 + x + 5 = 35$)

Deci nu înțeleg cum le echivalează pe acestea cu eșantionarea la x=1, x=2 etc.

Poate cineva să explice?

Puncte:1
drapel cn

În primul rând, este important să înțelegem câte informații este un polinom de grad $d$ ar putea conține. Se caracterizează prin $d+1$ imagini (gândiți-vă la polinoamele Lagrange pentru a înțelege de ce).

Deci, acum trebuie să ne concentrăm pe o propoziție specifică din linkul pe care l-ați scris: „Se trece de la patru grupuri de trei vectori de lungime șase la șase grupuri de trei polinoame de grad 3, unde evaluarea polinoamelor la fiecare coordonată x reprezintă una dintre constrângeri.”

Implică faptul că fiecare grup corespunde imaginilor polinoamelor pentru o anumită valoare. (Deoarece decidem arbitrar să o interpretăm astfel) Se pare că convenția este de a considera că $i^\text{th}$ grupul ne oferă imaginile pentru intrare $i$.

De exemplu, dacă aș calcula primul polinom $P_{1,1}$ a primului vector. voi calcula $P_{1,1}$ de grad cel mult $3$ astfel încât $P_{1,1}(1)= x_1, P_{1,1}(2) = x_2, P_{1,1}(3) = x_3, P_{1,1}(4)=x_4$, cu $x_i$ prima coordonată a primului vector al $i^{\text{th}}$ grup.

Aceste ecuații determină un singur polinom (nu sunt sigur că pot face explicații mai bune decât cea din linkul dvs.), dar dacă doriți să aveți mai multe cunoștințe despre acest lucru, puteți citi: https://en.wikipedia.org/wiki/Lagrange_polynomial

În general, putem face același lucru pentru a calcula $j^{\text{th}}$ polinom $P_{j,k}$ al $k^{\text{th}}$ vector, privind $k^{\text{th}}$ coordonatele lui $j^{\text{th}}$ vectori ai grupurilor.

drapel et
Știu ce puncte (n+1) definesc și polinom de n grad. Interpolarea lui Lagrange este folosită pentru a găsi un polinom de n grade atunci când cunoașteți n+1 puncte pe polinom. Cu toate acestea, aici știm deja polinomul - $x^3 + x -30$ - așa că nu pot să-mi dau seama de ce exact folosim interpolarea lui Lagrange?
drapel et
Știu $L_i(x)= \prod_{j=0}^n \frac {x-x_j} {x_i - x_j}$ și $P_n(x) = \sum_{i=0}^n L_i(x) y_i$. Cu toate acestea, nu pot corela-l cu simbolurile pe care le utilizați - $P_{j,k}(1)$ și $P_{j,k}(2)$ - ce este (1) și (2) aici - este it P(x=1) & P(x=2) & Ce este $P_{j,k}$?
Ievgeni avatar
drapel cn
coordonata $j^{\text{th}}$ a vectorului $k^{\text{th}}$
drapel et
Interpolarea lui Lagrange este folosită pentru a găsi un polinom de n grade atunci când cunoașteți n+1 puncte pe polinom. Cu toate acestea, aici știm deja polinomul - x3+xâ30 - așa că nu pot să-mi dau seama de ce folosim exact interpolarea lui Lagrange?
Ievgeni avatar
drapel cn
Vorbesc despre polinoame în această propoziție ""Mergem de la patru grupuri de trei vectori de lungime șase la șase grupuri de polinoame de trei gradul 3".

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.