Puncte:1

zkSnarks: Asigurarea că o variabilă are o singură valoare în toate operațiunile în care este utilizată

drapel et

Citesc această explicație despre zkSnarks scrisă de Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf

În secțiunea 4.5, pdf-ul explică cum să reprezinte următoarele operații

$a$ X $b = r1$
$r1$ X $c = r2$

la fel de $l(x)r(x) - o(x)$ Unde $l(x)$ este polinomul operandului din stânga, $r(x)$ este polinomul operand corect & $o(x)$ este polinomul de ieșire.

Aici dacă vezi asta $a$ este folosit o singură dată în LHS al primului set de operații - este folosit doar în primul (adică $a$ X $b = r1$) - nu apare în al 2-lea.

În 4.6, trece la cum să facă același lucru când $a$ se repetă. adică

$a$ X $b = r1$
$a$ X $c = r2$

Aici $a$ este prezent în ambele operațiuni

Așa spune el

Cu toate acestea, deoarece protocolul nostru permite demonstratorului să stabilească orice coeficienți la un polinom, el nu este restricționat să stabilească diferite valori ale $a$ pentru diferite operații (adică reprezentate de niște x)

Această libertate rupe consecvența și permite demonstratorului să demonstreze execuția unui alt program care nu este interesat de verificator. Prin urmare, trebuie să ne asigurăm că orice variabilă poate avea o singură valoare în fiecare operație în care este utilizată.

Mai departe în 4.6.1 spune el

În consecință, dacă un verificator trebuie să impună demonstratorului să stabilească aceeași valoare în toate operațiunile, atunci ar trebui să fie posibilă modificarea doar proporției și nu coeficienții individuali.

Nu pot înțelege acest lucru - coeficienții de $l(x)$ provin din toate operațiunile (găsești $l(x)$ folosind ceva de genul Interpolației polinomiale a lui Lagrange la ambele operații). Deci, cum poate demonstratorul să folosească diferiți coeficienți pentru diferite operații. Poate unii să explice cu un exemplu?

Puncte:1
drapel gb

Să presupunem că doriți să utilizați $a$ în două constrângeri așa cum ai scris. Vrei să presupui că $l(x_1) = a$ și $l(x_2) = a$, Unde $x_1$ și $x_2$ sunt indicii celor două constrângeri. Dar $l(x)$ este creat de probator și cu siguranță ar fi putut alege un $l(x)$ care evaluează la doi diferit valori la $x_1$ și $x_2$. Apoi, practic, aveți două variabile independente în loc să utilizați $a$ de două ori. Acest lucru este vizualizat în partea de sus a paginii 36 în PDF-ul legat.

Până în acel moment, fiecare constrângere este verificată independent. Prin asta, vreau să spun că $l(x_i)*r(x_i) - o(x_i) = 0$ la fiecare indice $x_i$, care se verifică prin asigurarea $(x-x_i)$ este o rădăcină a polinomului. Acum, avem nevoie de o modalitate de a verifica egalitatea variabilelor între două constrângeri diferite.Cu alte cuvinte, pentru a stabili cumva lucruri de genul $l(x_1) = l(x_2)$ între diferiți indici.

Modul în care se face acest lucru este prin limitarea în continuare a modului în care probatorul poate construi polinoamele (de ex. $l(x)$), astfel încât ei nu pot doar interpola orice valori le plac. O modalitate de a face acest lucru este să îi dai demonstratorului polinoame diferite $l_a(x)$ care evaluează la 1 oricând $a$ este folosit și 0 peste tot. De exemplu, un polinom unde $l_a(x_1) = l_a(x_2) = 1$, și este zero peste tot. Apoi pot pur și simplu înmulți acest lucru cu $a$ pentru a seta aceeași valoare a $a$ în toate locațiile este folosit. Pentru a forța probatorul să folosească acest lucru, îl criptăm din nou și îi oferim $\alpha$ versiune schimbata: $$g^{l_a(x)}, g^{\alpha l_a(x)}$$ (cum s-a făcut de multe ori anterior). Dovatorul poate apoi ridica fiecare dintre acestea la puterea de $a$ pentru a seta acea valoare în toate locurile.

Dacă avem o altă astfel de pereche pentru o altă variabilă $d$: $$g^{l_d(x)}, g^{\alpha l_d(x)}$$ Apoi probatorul le poate seta pe ambele $a$ și $d$ și apoi înmulțiți împreună polinoamele criptate (ceea ce corespunde cu adunarea polinoamelor din exponenți).

La fel se face și pentru $R(x)$ și $O(x)$.

Mai există o captură, abordată în secțiunea 4.9.3, care permite demonstratorului să adauge lucruri suplimentare la polinoamele lor prin înmulțirea cu alta $g^1$ și $g^{\alpha}$. Acest lucru este rezolvat prin introducerea unei alte schimbări secrete prin $\gamma$.

meshcollider avatar
drapel gb
> „așa este chiar și în cazul anterior. chiar și în cazul anterior, probatorul ar putea alege orice vrea” - da, și de aceea trebuie să limităm încet ceea ce doveditorul este capabil să aleagă pe parcursul PDF-ului, deci prin când terminăm, suntem convinși că nu au putut să fi înșelat.
drapel et
Există un exemplu despre modul în care probatorul ar putea exploata ceva în cazul în care probatorul nu este restricționat?
meshcollider avatar
drapel gb
Absolut. Să presupunem că încercați să demonstrați ceva care se rezumă la unele constrângeri, inclusiv faptul că $b = a + 1$ și $c = a - 1$. Fără asigurarea că valoarea lui $a$ utilizată în ambele aceste constrângeri este aceeași, $b$ și $c$ pot primi în mod independent valori arbitrare, iar verificarea va trece în continuare. Să presupunem că un demonstrator rău intenționat folosește o valoare $b = 8$ și $c = 0$. Evident, nu există un $a$ pentru care ambele pot fi adevărate. Dar folosind $a = 7$ în prima constrângere și $a = 1$ în a doua, ambele constrângeri se vor verifica independent.
drapel et
Când dovezitorul rău intenționat formează $l(x)$, $o(x)$ și $r(x)$ cu valori diferite decât cea care este de fapt cea corectă, atunci cum va funcționa Interpolarea Lagrange? Nu se va împiedica probatorul în acel moment?
meshcollider avatar
drapel gb
Interpolarea Lagrange funcționează pentru orice valoare doriți. De exemplu, dacă se presupune că $l(x)$ este egal cu $a$ la $l(x_1)$ și $l(x_2)$, nimic nu împiedică demonstratorul să interpoleze $l(x_1) = a$ și $ l(x_2) = b$, obținând un alt $l(x)$ decât cel pe care l-ați obține dacă le-ați seta sincer ambele $a$ la aceeași valoare. Tot ce faci este să găsești un polinom care trece prin punctele $(x_1, a)$, $(x_2, b)$ în loc de $(x_1, a)$, $(x_2, a)$
drapel et
Am creat o cameră de chat pentru asta - https://chat.stackexchange.com/rooms/134216/temp-zksnark - Mi-am pus întrebarea acolo - poți te rog să te uiți la ea

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.