zkSNARKS - incapabil să înțeleagă utilizarea polinomului pentru a verifica o anumită condiție

Din blogul lui Vitalik Buterin - O introducere aproximativă a modului în care sunt posibile zk-SNARK

De la sub-tema „Compararea unui polinom cu el însuși”, am înțeles până aici

Cu alte cuvinte, orice polinom care este egal cu zero într-o mulțime este a (polinom) multiplu al celui mai simplu (de gradul cel mai mic) polinom care este egal cu zero în aceeași mulțime.

Cu toate acestea, nu pot să-mi dau seama cum folosește asta pentru a verifica o anumită condiție.

Aceasta este partea pe care nu o înțeleg

dacă avem un polinom care codifică numerele Fibonacci (deci peste $F(x+2) = F(x) + F(x+1)$ peste $x = $ { $0, 1, ..., 98$}), atunci te pot convinge de asta $F$ îndeplineşte de fapt această condiţie demonstrând că polinomul $P(x) = F(x+2) - F(x+1) - F(x)$ este zero în intervalul respectiv, oferindu-vă coeficientul $H(x) = \frac {F(x+2) - F(x+1) - F(x)}{Z(x)}$ Unde $Z(x) = (x - 0) * (x - 1) ... (x - 98)$

În primul rând, nu înțeleg ce vrea să spună prin „dau-ți coeficientul” - ce anume îi va oferi verificatorului și cum îl va verifica verificatorul?

Dacă un polinom $P(x)$ (Gândiți-vă la ea ca la o funcție care acceptă intrare $x$ și returnează un rezultat al evaluării) evaluează la zero pentru anumite valori de intrare pentru $x$ (un exemplu foarte simplu ar putea fi $x=x_1, x_2, x_3$), apoi, după cum se arată în primul pasaj citat din întrebare, $P(x)$ va fi un multiplu al unui polinom de cel mai mic grad $Z(x)$ care este zero în acele valori de intrare pentru $x$ (aici ar fi $Z(x)=(x-x_1)(x-x_2)(x-x_3)$). Aceasta înseamnă că dacă $P(x)$ este împărțit la $Z(x)$, coeficientul (numiți-l $H(x)$) va fi în continuare un polinom. Proverul calculează $H(x)$ prin efectuarea efectivă a împărţirii şi anume $P(x)/Z(x)$, și asta $H(x)$ este trimis de la Prover la Verificator ca âProofâ. Verificatorul confirmă apoi că produsul din $H(x)$ și $Z(x)$ este într-adevăr egal cu $P(x)$, iar dacă da, verificatorul acceptă dovada. Verificatorul trebuie să confirme și asta $H(x)$ este de fapt un polinom și nu un alt tip de funcție (de exemplu, nu ar trebui să fie o funcție rațională, care este o fracție netrivială cu numărător și numitor polinomial). În practică, acest lucru este confirmat în mod implicit datorită modului în care Prover comunică sau calculează $H(x)$. De exemplu, dacă protocolul cere ca Proverul să trimită peste coeficienții de $H(x)$, atunci este evident că este un polinom. Sau, dacă protocolul cere ca Proverul să calculeze $H(r)$ pentru o valoare secretă $r$ (ceea ce înseamnă că $H(x)$ este evaluat la $x=r$), atunci va exista un „Șir de referință comun” furnizat Prover-ului care include codificări (de exemplu, în exponentul unui generator de grup într-un grup prietenos de asociere) de puteri ale $r$ până la cea mai mare putere (de ex. ${g^{r}, g^{r^2}, g^{r^3}, g^{r^4}, g^{r^5}}$), astfel încât Proverul este forțat să propună doar un polinom $H(x)$ (evaluat la $x=r$) cu grad până la cea mai mare putere (în acest exemplu simplu, 5).