Preambula
Šī ir ceturtā daļa rakstu sērijā, kurā tiek pētīta zk-SNARK — tehnoloģija, kas ļauj pierādīt zināšanu pareizību, neatklājot slepenu informāciju. Iepriekšējās daļās mēs apguvām dažus sarežģītus jēdzienus, piemēram, kvadrātaritmētiskā programma un eliptiskās līknes pārī (kopējiet 3. daļas saiti šajā treknrakstā).
Kvadrātiskās aritmētikas programma ļauj attēlot skaitļošanas problēmas, izmantojot polinomus, un eliptiskās līknes pārī ir noderīgs kodēšanas rīks datu pareizības pārbaudei. Apvienojot tos ar kādu citu algoritmu, mēs varam ļaut pārbaudītājam pierādīt, ka viņš zina konkrētas QAP risinājumu, neko citu neatklājot. Tas nodrošina uzticību, neatklājot sensitīvus datus.
Šajā rakstā galvenā uzmanība tiks pievērsta Pinokio protokolam QAP, kas ļauj pierādīt, ka mainīgais atbilst noteiktiem nosacījumiem, neatklājot informāciju par mainīgā vērtību.
Šo pierādījumu ir viegli izveidot, un to var autentificēt, nepārbaudot katru skaitļošanas posmu, nodrošinot datu privātumu un drošību blokķēdes lietojumprogrammās un citās jomās, kurās nepieciešama droša autentifikācija, neatklājot privātu informāciju.
Pinokio protokola izveide bez nulles
Vispirms ilustrējam, kā Pinokio protokols darbojas šādi:
Ļaujiet G ir grupa ar galveno secību p. Ļaujiet E : Fp → G ir homomorfisks kodējums. Sekojoši:
ģeneratoram g
Put
Iepriekš minētā izteiksme ir eliptiskas līknes “bilineāra karte”. Pieņemsim, ka pārbaudītājs P pazīst liecinieku, kā parādīts tālāk
oriģinālajai aritmētiskajai shēmai. Vienkāršojot, viņa zinās kādu tādu polinomu
Šobrīd mums tas joprojām šķitīs mazliet mulsinoši, vai ne! Neuztraucieties, uzmanīgi izlasiet katru rindiņu un izpētiet formulas, es paskaidrošu šī protokola galveno ideju tieši zemāk!
V(verifikators) vēlas pārbaudīt P (Prover) nejaušajā punktā (nejaušajā punktā) z ∈ Fp pret iepriekš minētā polinoma vērtībām. P tiek pieprasīta vērtība
un h(z) kāda nejauša z ∈ Fp. P homomorfiski kodēs) šīs vērtības un nosūtīs tās uz V. Pateicoties homomorfās un bilineārās kartes īpašībām, V var pārbaudīt, vai homomorfiski kodētā vērtība atbilst iepriekš norādītajam vienādojumam (20).
Ja tā rīkojas, verificētājs var būt pārliecināts, ka liecinieks patiešām pazīst liecinieku, nezinot par šo liecinieku. Tālāk ir sniegta sīkāka informācija par tikko aprakstīto galveno ideju.
Protokola pirmais solis ir izveidot kopējo atsauces virkni (Common Reference String — CRS), kas satur z reizinātāju homomorfiskus kodējumus.
DRS kalpos diviem mērķiem:
Pirmkārt, pārbaudītājs var ģenerēt homomorfiskus kodējumus savam pierādījumam, izmantojot DRS grupas elementu lineāras kombinācijas (lineāras kombinācijas), nezinot z.
Otrkārt, iestatot DRS, V nav nepieciešams manuāli ģenerēt z un nosūtīt šifrētu ziņojumu no z uz P. Tas ļauj šim pierādījumam būt pilnīgi neinteraktīvam, jo pēc DRS izveides P var izveidot. pārliecinoši pierādījumi.
Mēs varam uzskatīt DRS kā divas publisko grupu elementu kopas:
Novērtēšanas atslēga, kas satur grupas elementus, kas nepieciešami, lai izveidotu pierādījumu, un verifikācijas atslēga, kurā ir verifikācijai nepieciešamie elementi.
Kopējā atsauces virkne:
Nejauši izvēlieties α, βu, βv, βw, γ, z ∈ F ∗ p.
Ieviesiet tālāk norādīto DRS, pēc tam noņemiet visus grupas elementus, kas izmantoti tās izveidē (toksiskie atkritumi).
Provera vēstījums:
Pieņemsim, ka Prover ir šāds polinoms:
Vispirms Prover aprēķina h(x). Pēc tam pārbaudītāja pierādījumos ietilpst:
Pārbaude:
Saņemot pārbaudītāja pierādījumu, verificētājs vispirms pārbauda, vai termini u(z), v(z), w(z), h(z) ir konstruēti kā lineāras kombinācijas, terminu aprēķins DRS — vai nav, veic šādas 4 pārbaudes. :
Pēc tam pārbaudiet, vai katrs termins u(z), v(z), w(z) ir ģenerēts, izmantojot tos pašus lineāros koeficientus:
To var pārbaudīt, pārbaudot šādu vienādojumu:
Visbeidzot, mēs pārbaudām galveno nosacījumu, kas raksturo polinoma dalāmības kritēriju:
Mēs esam veiksmīgi izveidojuši beznulles Pinokio protokolu, ja ir spēkā visas pārbaudes no (21) līdz (26).
Tālāk mēs pāriesim uz bezzināšanu Pinokio protokola analīzi.
Zināšanu Pinokio protokola analīze bez nulles
Pirmkārt, mums ir jāapgūst zināšanas par eksponentu pieņēmumu
Pieņemsim, ka Alisei ir dots grupas elementu pāris (x, αx)
Mēs šādu pāri saucam par α-atdalītu. Tad Alisei nav iespējams ģenerēt citu ar α atdalītu pāri (y, αy), izņemot to, ka to ģenerē šādi:
Ņemot vērā n ar α atdalītus pārus, ja Alise atgriež citu ar α atdalītu pāri, tai ar lielu varbūtību ir jābūt lineārai kombinācijai no sākotnējiem α atdalītiem pāriem.
Atgriežoties pie mūsu protokola, galvenais nosacījums, kas V ir jāpārbauda, ir polinoma dalāmības nosacījums:
Tomēr papildus šim vienādojumam ir jābūt arī citiem vienādojumiem, kas pārbaudītājam jāpārbauda.
Tas ir tāpēc, ka pārbaudītājs var ģenerēt vērtības, kas atbilst šim vienādojumam, bet netiek ģenerētas no faktiskā liecinieka s aritmētiskajai ķēdei. Lai to nodrošinātu, verificētājam ir nepieciešams veids, kā pārbaudīt, vai Prover izmantotie polinomi patiešām ir DRS pamatā esošo polinomu lineāra kombinācija.
Pieņēmums “Knowledge-of-Exponent” ir noderīgs, jo, ja grupas elementu pāris, ko Prover sūta, un dotais pāris ir atdalīti α−, proverpāris ir jāģenerē kā lineāra kombinācija no atdalītajiem α− pāriem.
Tāpēc verificētājs var izmantot sasaistes funkciju, lai efektīvi pārbaudītu, vai šie divi pāri ir atdalīti α–, lai nodrošinātu, ka pārbaude tiek ģenerēta, izmantojot patiesi apmierinošu aritmētiskās ķēdes attēlojumu. Konkrētāk, diviem pāriem (x, αx),(y, αy) ir taisnība:
Verifikators to var izmantot, lai veiktu tālāk norādītās pārbaudes.
Izmantojot šo ideju, verificētājam ir jāpārbauda trīs lietas:
Tālāk mēs varam pierādīt, ka Pinokio protokols atbilst divām īpašībām: pilnīgums un pareizība (šis pierādījums ir diezgan sarežģīts, lai labāk izprastu, varat lasīt tālāk par avota dokumentiem.)
Nulles zināšanu Pinokio protokola modifikācija
Būtībā, ja verificētājs V ģenerē savu pierādījumu s' = (s'₁, s'₂, …, s'ₙ), viņš var aprēķināt E(u'(z)), E (v'(z)), E (w'(z)), E(h'(z)) saskaņā ar pārbaudītāja protokolu.
Ja šīs vērtības atšķiras no E(u(z)), E(v(z)), E(w(z)), E(h(z)), ko pārbaudītājs aprēķina s, tad pārbaudītājs secina ka pierādītāja pierādījums nav s' (SNARK skaidrojums VI daļa: Pinokio protokols)
Lai novērstu šo “nulles zināšanu” pārkāpumu, pārbaudītājs P pievieno nejaušu nobīdi polinomiem u, v un w (Pinokio: gandrīz praktiski pārbaudāms aprēķins).
Izlases nobīde būs t(x) reizinājums, lai viss paliktu tāds pats mod t(x). Nejauši δ₁, δ₂, δ₃, kas pieder Fp, nejauši atlasīti:
Pēc tam P tos novērtēs z punktā, izmantojot DRS, un savā pierādījumā iesniegs nobīdītos terminus (nobīdītos terminus) atbilstošo nemainīto terminu vietā.
Nulles zināšanu Pinokio protokola modifikācija ir pabeigta. Šobrīd visi jūtas apmulsuši =)))))).
Bet tas arī viss, vēlreiz paldies, ka izlasījāt tik tālu. Ja jums patika šis raksts, neaizmirstiet sekot un atstāt aplausus.
Tā beidzas mana rakstu sērija par “Zk-SNARK atklāšanu”. Ceru, ka atstājat savu ieguldījumu, lai es varētu pilnveidoties un būt motivēts rakstīt nākamos rakstus.
Raksta avots: Team Tech/Research AlphaTrue
Atsauces avots:
Chen, T., Lu, H., Kunpittaya, T., & Luo, A. (2022). Pārskats par zk-snarks. arXiv preprint arXiv:2202.06877. https://arxiv.org/pdf/2202.06877.pdf