Provat zero-dije shpesh duken misterioze sepse matematika prapa tyre është shumë e avancuar.Shumë njerëz e quajnë me shaka këtë "matematikë hënë", pasi ndihet si diçka magjike ose nga një botë tjetër. Ne duam të heqim këtë konfuzion dhe të ndihmojmë të gjithë të kuptojnë se çfarë bëjnë vërtet dëshmitë e njohurive zero. Në këtë post, ne prezantojmë një bllok të rëndësishëm ndërtimi të përdorur në shumë sisteme dëshmi zero-dije: Pas kësaj, ne shpjegojmë , një nga llojet më të njohura dhe praktike të skemave të angazhimit polinomial. polynomial commitment schemes KZG Më pas përshkruajmë se si Dhe si Së fundi, ne tregojmë se si zk-rollups dhe Proto-Danksharding mund të punojnë së bashku në mënyrë të qetë dhe efikase - diçka që është e mundur veçanërisht sepse . KZG is used inside zk-rollups Ethereum also uses KZG in Proto-Danksharding both systems use polynomial commitment schemes Why are we talking about polynomials? Polinomialet janë mjete të fuqishme matematikore sepse na lejojnë të përfaqësojmë objekte të mëdha ose komplekse në mënyrë efikase. Një shembull i zakonshëm është përfaqësimi i një vektorit n-dimensional të elementeve të fushës v duke përdorur një polinomial të vetëm. Ne e bëjmë këtë duke ndërtuar një polinomial φ(x) që kalon nëpër pikët (i, v_i) për çdo indeks i = 1, 2, ..., n. Për shembull, vektorin 3-dimensional v = [2, 0, 6] mund të kodohet nga polinomi Për shkak se përqendrimi në vlerat jep të dhe Në përgjithësi, duke marrë parasysh çdo pikë n, gjithmonë ekziston një polinom i veçantë i shkallës në maksimum n − 1 që kalon nëpër të gjitha ato. φ(x) = 4x² − 14x + 12 φ(1) = 2 φ(2) = 0 φ(3) = 6 Procesi i ndërtimit të kësaj polinomiale quhet interpolimi polinomial, dhe një nga teknikat më të përdorura është , e cila siguron një formulë të drejtpërdrejtë për ndërtimin e polinomit nga pikat e dhëna. Duke përdorur këtë metodë, ne tani e dimë se si të ndërtojmë një polinom të shkallës në maksimum . Interpolimi i Lagrange n − 1 from exactly n constraints Në pjesën e mëparshme, ne mësuam se nëse ju e dini , ju gjithmonë mund të përcaktoni një polinom unik shkalla e të cilit është më së shumti Tani, ne duam të shkojmë një hap më tej dhe të kuptojmë për të gjetur në të vërtetë atë polinom nga koordinatat e këtyre n pikave. n points n − 1 Si Një metodë e zakonshme dhe e thjeshtë për ta bërë këtë quhet interpolimi i Lagrange. Edhe pse formulat zyrtare mund të duken të komplikuara, ideja themelore është shumë e thjeshtë. Interpolimi i Lagrange na jep një mënyrë të drejtpërdrejtë për të ndërtuar polinomin që kalon nëpër të gjitha pikat e dhëna. Për shembull, supozoni se ne duam të gjejmë një polinom Për ta bërë këtë, na duhen saktësisht 3 pika, dhe polinomi duhet të kënaqë të tre këto kufizime. Duke përdorur koordinatat e këtyre 3 pikave, interpolimi Lagrange do të ndërtojë polinomin e saktë që i përshtatet atyre në mënyrë të përkryer. P φ (1) = 2 φ (2) = 0 φ(3) = 6 Për ta bërë këtë, ne do të ndërtojmë 3 sub-polinomials (një për kufizim) , dhe Në nivelin më të lartë . P₁ P₂ P₃ 2 Këto 3 sub-polinomiale duhet të ndjekin këto sub-kufi: x P₁(x) P₂(x) P₃(x) 1 2 0 0 2 0 0 0 3 0 0 6 1 2 0 0 2 0 0 0 3 0 0 6 Each sub-polynomial evaluates to Në të gjitha aspektet, por vetëm një. 0 Së fundi, ne vendosim: P(x) = P₁(x) + P₂(x) + P₃(x) Let's quickly check, referring to the previous tab, that Respekton të gjitha kufizimet: P P(1) = P₁(1) + P₂(1) + P₃(1) = 2 + 0 + 0 = 2 P(2) = P₁(2) + P₂(2) + P₃(2) = 0 + 0 + 0 = 0 P(3) = P₁(3) + P₂(3) + P₃(3) = 0 + 0 + 6 = 6 Ne vetëm kemi verifikuar se të respektojnë kufizimet e saj 3 Tani, le të ndërtojmë të dhe . P P₁ P₂ P₃ Building P₁ Using the , we can define P₁ as: factorised form P₁(x) = A(x − 2)(x − 3) tashmë i plotëson kufizimet: P₁ P₁(2) = P₁(3) = 0 Tani le të gjejmë Të tilla si: A P₁(1) = 2 Ne kemi ekuacionin e mëposhtëm: P₁(1) = A(1 - 2)(1 - 3) = 2 Që na jep: A = 2 Dhe më në fund: P₁(x) = 2(x − 2)(x − 3) tani i plotëson 3 nënkufizimet e saj. P₁ Ndërtesa P2 Përdorimi i Ne mund të përcaktojmë si në: Formë fabrike P2 P₂(x) = B(x - 1)(x − 3) tashmë i plotëson kufizimet: P2 P₂(1) = P₂(3) = 0 Tani le të gjejmë Të tilla si: B P₂(2) = 0 Ne kemi ekuacionin e mëposhtëm: P₂(2) = B(2 − 1)(2 − 3) = 0 Që na jep: B = 0 Dhe më në fund: P₁(x) = 0(x − 1)(x − 3) = 0 tani i plotëson 3 nënkufizimet e saj. P₂ Ndërtimi i P3. Përdorimi i Ne mund të përcaktojmë si në: Formë fabrike P3 P₃(x) = C(x − 1)(x − 2) tashmë i plotëson kufizimet: P₃ P₃(1) = P₃(2) = 0 Now let's find Të tilla si: C P₃(3) = 6 Ne kemi ekuacionin e mëposhtëm: P₃(3) = C(3 - 1)(3 - 2) = 6 Që na jep: C = 3 Dhe më në fund: P₃(x) = 3(x - 1)(x - 2) now satisfies its 3 sub-constraints. P₃ Building P As previously seen, P(x) = P₁(x) + P₂(x) + P₃(x) Replacing , and by their respective expression, we get: P₁ P₂ P₃ P(x) = (x - 2)(x - 3) + 0 + 3(x - 1)(x - 2) P(x) = (x² - 5x + 6) + 3(x² - 3x + 2) P(x) = x² - 5x + 6 + 3x² - 9x + 6 P(x) = 4x² - 14x + 12 After expansion and simplification, we obtain: P(x) = 4x² - 14x + 12 Checking P Le ta kontrollojmë shpejt këtë does respect the 3 constraints: P P(1) = 4(1²) - 14(1) + 12 = 4 - 14 + 12 = 2 P(2) = 4(2²) - 14(2) + 12 = 16 - 28 + 12 = 0 P(3) = 4(3²) - 14(3) + 12 = 36 - 48 + 12 = 6 What are polynomial commitment schemes, and why are they useful? Polynomial commitment schemes are special tools that let someone commit to an entire polynomial without showing what the polynomial actually is. They work similarly to normal commitment schemes, where a person commits to a message and later reveals it. A good commitment scheme must be , meaning you cannot change the message after committing, and Angazhimet polinomiale ndjekin të njëjtat rregulla, por në vend që të angazhohen për një mesazh, ju angazhoheni për një polinomial të tërë me shumë koeficientë. binding hiding Pjesa e fuqishme e angazhimeve polinomiale është se më vonë mund të provoni vlerën e polinomialit në pika të caktuara pa zbuluar të gjithë polinomialin. has the value në , ata mund ta bëjnë këtë pa ekspozuar pjesën tjetër të polinomit.Ata thjesht japin një provë të shkurtër që tregon është e vërtetë, dhe verifikuesi mund ta verifikojë atë duke përdorur angazhimin e mëparshëm. verifikuesi nuk mëson asgjë tjetër për vetë polinomin. Kjo veçori është jashtëzakonisht e dobishme në provat zero-dije, ku qëllimi është të provojë diçka është e vërtetë pa zbuluar informacione shtesë. ϕ(x) 66 x = 4 “ϕ(4) = 66” Një polinom mund të ketë qindra ose mijëra vlera, por angazhimi mund të jetë vetëm një element i vetëm i grupit të vogël, si 48 bytes. Kjo është jashtëzakonisht e rëndësishme për blockchain, ku ruajtja ose postimi i të dhënave të mëdha është i shtrenjtë. dhe Mund të kurseni shumë hapësirë dhe të zvogëloni kostot. zk-rollups Proto-Danksharding Për ta bërë këtë më të lehtë për të kuptuar, imagjinoni se Alice ka një polinomial të fshehtë, të tilla si φ(x) = 3x2 + 5x + 2. Ajo nuk dëshiron të zbulojë polinomial, por Bob dëshiron provë se φ(4) = 66. Alice angazhohet në polinomial duke përdorur një skemë polinomial angazhimi dhe dërgon Bob angazhimin. Më vonë, ajo zbulon vetëm vlerën 66 dhe siguron një provë të shkurtër duke treguar se kjo vlerë është e saktë për x = 4. Bob kontrollon provën kundër angazhimit dhe bëhet i bindur, pa mësuar ndonjëherë asgjë tjetër për polinomial. Kjo është arsyeja pse angazhimet polinomiale janë mjete të fuqishme në kriptografinë moderne dhe janë th KZG Polynomial Commitment KZG Angazhimi Polinomial 1. Commitment Në një angazhim polinomial, proveri i parë i kthen të dhënat e tyre në një polinomial. Pastaj ata krijojnë një "angazhim" të veçantë kriptografik për këtë polinomial. Ju mund të mendoni për këtë angazhim si mbyllja e polinomialit brenda një kuti të mbyllur: proveri nuk mund ta ndryshojë atë më vonë, dhe verifikuesi nuk mund të shohë se çfarë është brenda. Ky hap garanton dy gjëra - polinomiali nuk mund të ndryshohet ( ) dhe përmbajtja e saj mbetet private ( ). binding hiding 2. Evaluation Next, the prover wants to prove something about the polynomial Kështu që ata marrin një pikë x, e lidhin atë në polinomial, dhe llogarisin përgjigjen. Ata dërgojnë vetëm këtë vlerë y, plus një provë të vogël që tregon se vlera erdhi nga polinomiali i angazhuar. polinomialet aktuale qëndrojnë të fshehura gjatë gjithë kohës. without revealing it y=P(x) 3. Verification Së fundi, verifikuesi kontrollon nëse vlera e really matches the committed polynomial at point Duke përdorur angazhimin dhe provën, verifikuesi kryen një kontroll kriptografik. must be true — even though they never saw the polynomial itself. If the prover tries to lie or cheat, the verification step will catch it. This makes polynomial commitments secure and very useful in technologies like zero-knowledge proofs and Ethereum scaling. y x P(x)=y KZG Polynomial Commitment Scheme KZG skema e angazhimit polinomial KQZ ka . four main steps Step 1 - Trusted Setup A one-time setup done before the system runs. Zgjidhni një gjenerator g të një grupi elips-kurve G (parimet mbështetëse). Zgjidhni shkallën maksimale l të polinomit. Pick a secret random value: τ ∈ Fp Compute and publish: (g, g^τ, g^(τ^2), ...., g^(τ^l)) Only these powers of are public. gᵗ The value τ must remain secret forever. If someone knows τ, they can forge proofs. Step 2 - Commit to a Polynomial Suppose we have the polynomial: ϕ(x) = ∑ᵢ₌₀ˡ ϕᵢ xⁱ We want to compute the commitment: C = g^{ϕ(τ)} Although the committer cannot compute directly since he doesn’t know , he can compute it using the output of the setup g^{ϕ(τ)} τ τ Step 3 - Create a Proof for Evaluation ϕ(a)=b Për të provuar këtë: ϕ(a)=b Llogaritja e koeficientit polinomial: q(x) = ϕ(x) - b / x - a Kjo është e vlefshme vetëm nëse vlerësimi është i saktë Pastaj llogarisni provën: π = g^{q(τ)} This is the KZG evaluation proof. Step 4 - Verification Të dhëna: Përgjegjësia C = g^{φ(τ)} Prova për π = g^{q(τ)} Evaluation claim ϕ(a)=b Verifikatorët kontrollojnë: e(c/g^b,g) = e(π,g^τ/g^a) Here 𝑒 ( ⋅ , ⋅ ) is a . bilinear pairing This equation is equivalent to verifying: q(τ) = ϕ(τ) - b /τ - a If the pairing check holds, the evaluation is accepted as correct. Shpjegim i shkurtër i kontrollit të përafërt Në LHS: = b) c) c) c) c) c) c) c e(C/g^b, g) e(g,g)ϕ RHS: e(π, g^τ/g^a) = e(g,g)q(τ)⋅(τ−a) (π = g^{q(τ)}) Ngjashmëria nënkupton φ(τ)−b = q(τ)(τ−a), identitetin koeficient të vlerësuar në τ, e cila imponon φ(a)=b nëse q(x) është formuar saktë. (q(x) = φ(x) - b / x - a) Shpjegim i shkurtër i kontrollit të përafërt Në LHS: = b) c) c) c) c) c) c) c e(C/g^b, g) e(g,g)ϕ RHS: e(π, g^τ/g^a) = e(g,g)q(τ)⋅(τ−a) (π = g^{q(τ)}) Ekuacioni nënkupton Numri i të dhënave të vlerësuara në e cila detyron Nëse është formuar në mënyrë korrekte.) ) ϕ(τ)−b = q(τ)(τ−a) τ ϕ(a)=b q(x) q(x) = ϕ(x) - b / x - a Use Cases: zk-rollups të Në zk-rollups, ne duhet të provojë se puna e bërë në Layer 2 (L2) është e saktë. Për ta bërë këtë, të gjitha hapat e llogaritjes janë konvertuar në një tabelë të madhe (një matricë 2D). Kjo ndodh gjatë një procesi të quajtur . Each column of this table represents one part of the computation, and each column can be turned into a polynomial. So instead of handling a huge matrix directly, we work with a list of polynomials. The correctness of the computation can then be described using mathematical rules between these polynomials. For example, imagine three columns of the table represent three polynomials: Gjenerata e dëshmitarëve a) në x b) në x c(x)Një rregull mund të thotë se a(x)⋅b(x)−c(x)= 0 Kjo do të thotë "polinomi i parë i shumëzuar me të dytin duhet të jetë i barabartë me të tretën." kolona 1 × kolona 2 duhet të prodhojë kolona 3. Instead of checking this rule for every possible value of x (which would be slow), zk-rollups check it only at a few random points. If the rule is correct at those random points, then with very high probability, the whole computation is correct. Nëse dua të kontrolloj nëse dy lista të gjata përputhen me një rregull, nuk kam nevojë të krahasoj çdo artikull – duke kontrolluar disa artikuj të rastit zakonisht më tregon nëse e gjithë marrëdhënia është e vlefshme. Example: Skemat e angazhimit polinomial – të tilla si KZG – janë të përkryera për këtë. Rrotullimi angazhohet për të gjitha polinomialet që përshkruajnë llogaritjen L2 (diçka si mbyllja e tyre brenda një kutie kriptografike). Më vonë, verifikuesi mund të kërkojë vlerat e këtyre polinomialeve në pika të caktuara të rastësishme. Me ato vlera dhe angazhimet, verifikuesi kontrollon nëse rregullat e saktësisë mbajnë. Ethereum’s Proto-Danksharding (EIP-4844) është një përmirësim i projektuar për ta bërë shumë më të lirë për rollups për të publikuar të dhënat e tyre në Shtresën 1 të Ethereum. Ky lloj transaksioni përfshin një pjesë të madhe të të dhënave të quajtura një (around 128 kB). However, this blob is kontratat inteligjente ose shtresën e ekzekutimit. kontratat inteligjente mund të shohin vetëm një Blloku, jo vetë Blloku. Protokolli falënderues Transaksionet e blobit Blobë not commitment Now the question is: Një opsion është për të marrë blob dhe vetëm . But hashing is limited: if we only store a hash, then later we cannot prove anything about the data inside the blob without revealing the entire blob. This is too restrictive for Ethereum’s future scaling plans. Si duhet të krijojë Ethereum këtë angazhim në blob? hash it Në vend të kësaj, ne mund ta trajtojmë blobin si një polinomial. (më parë, ne shpjeguam se si vektorët ose të dhënat mund të përfaqësohen si polinomiale.) si KZG, Ethereum mund të angazhohet në blob në një mënyrë që jo vetëm që fsheh të dhënat, por gjithashtu lejon verifikimin e pronave të caktuara . polynomial commitment scheme pa shkarkuar të gjithë blob This capability is essential for something called DAS lejon validatorët të kontrollojnë nëse blob është i disponueshëm dhe i saktë Në vend të kësaj, validatorët shkarkojnë vetëm copa të vogla të rastit. falë matematikës prapa angazhimet polinomiale, nëse mostrat e rastit të mjaftueshme janë të sakta, validatorët mund të jenë shumë të sigurt se e gjithë blob është në dispozicion. (edhe pse DAS nuk është përfshirë në versionin e parë të Proto-Danksharding, ajo do të shtohet sa më shpejt që Ethereum vazhdon drejt "Thanksharding të plotë.") (DAS) Disponueshmëria e të dhënave without downloading all 128 kB Disponueshmëria e të dhënave Ethereum ka zgjedhur Hulumtuesit krahasuan disa skema dhe arritën në përfundimin se KZG ofron ekuilibrin më të mirë të efikasitetit, madhësisë së provës dhe thjeshtësisë për hartën e rrugës së Ethereum në afat të shkurtër dhe të mesëm. KZG How zk-rollups and Ethereum’s Proto-Danksharding interact zk-rollups dhe Proto-Danksharding e Ethereum mund të duket si sisteme të ndara, por ata të dy përdorin angazhimet KZG në mënyra që u lejojnë atyre të punojnë së bashku pa probleme. Scroll përdor KZG për të angazhuar në llogaritjet e kryera në Layer 2, ndërsa Ethereum përdor KZG për të angazhuar në blobs të mëdha të të dhënave të postuara në Layer 1. Kur Scroll përfundon përpunimin e një baterie të transaksioneve L2 dhe llogarit një rrënjë të re të shtetit, duhet të publikojë tre gjëra në L1 të Ethereum: T - lista e transaksioneve L2, Si - rrënja e re e shtetit pas këtyre transaksioneve janë aplikuar, π - një provë se rrënja e shtetit të ri është e saktë. Ethereum must verify two things: që rrënja e re e shtetit Si është e vlefshme (që do të thotë se transaksionet janë ekzekutuar saktë), dhe që lista e transaksioneve T është saktësisht ajo që përdoret për të prodhuar atë gjendje rrënjë.Prandaj duhet të ketë një mënyrë për të lidhur listën e transaksioneveT me provën π. Dyqane të Ethereum Si një , që do të thotë se verifikuesi ka vetëm qasje në një në atë blob - le ta quajmë këtë angazhim . Meanwhile, the proof gjithashtu përmban angazhimet KZG për polinomet e ndryshme të përdorura gjatë llogaritjes, duke përfshirë polinomin që përfaqëson listën e transaksioneve. . T Blob të dhënave KZG commitment Cₜ π Cₚ Tani ne kemi dy angazhimet e ndryshme KZG ( Nga blloku dhe Nga kjo dëshmi që të njëjtin polinomial φt (reprezentimi polinomial i listës së transaksioneve). dhe really refer to the same data. Cₜ Cₚ should Cₜ Cₚ Për ta bërë këtë, ne përdorim një teknikë të quajtur a Ideja është e thjeshtë: Prova e ekuivalencës Prova e ekuivalencës Zgjidhni një vlerë të rastësishme = hash(Ct Cp) Kjo e bën z të paparashikueshme dhe unike për këto dy angazhimet. Both commitments are then “opened” at the point z, each producing a value . That is, prove that: a ϕₜ(z) = a under commitment , and Cₜ ϕₜ(z) = a under commitment . Cₚ Nëse të dy angazhimet japin të njëjtën vlerë në të njëjtin pikë të rastit, atëherë me probabilitet jashtëzakonisht të lartë, ato përfaqësojnë të njëjtin polinomial. Shembull: Imagjinoni dy njerëz, secili duke pretenduar se ata kanë të njëjtin polinom sekret. në vend që të zbulojë të gjithë polinomin, secili e vlerëson atë në një pikë të rastësishme-thotë x = 103. : Imagjinoni dy njerëz, secili duke pretenduar se ata kanë të njëjtin polinom të fshehtë. në vend që të zbulojë të gjithë polinomin, secili e vlerëson atë në një pikë të rastësishme-thotë x = 103. Example E njëjta logjikë lejon Ethereum të verifikojë se lista e transaksioneve të përdorura në provë është saktësisht e njëjtë me listën e transaksioneve të publikuara në blob. π Një bonus i mirë është se ky kontroll i ekuivalencës punon edhe nëse dy angazhimet përdorin Për shembull, njëra mund të jetë KZG dhe tjetra FRI. Për sa kohë që të dy angazhimet mbështesin hapjen në një pikë, verifikuesi mund t'i krahasojë ato, duke e bërë këtë qasje shumë fleksibël. Të ndryshme Të ndryshme Erasure Coding With Polynomials Një tjetër koncept i fuqishëm i përdorur si në KZG dhe PeerDAS është Kjo teknikë lejon që të dhënat të rimarrin edhe nëse disa pjesë të saj mungojnë. Duke përdorur polinomet, ne mund të marrim një grup të vogël vlerash origjinale dhe t'i zgjerojmë ato në një grup më të gjatë duke vlerësuar polinomin në pika shtesë. . This is exactly how Ethereum’s data-availability sampling (DAS) works: nodes don’t need every piece of data, only a random sample that lets them reconstruct the original information with high probability. erasure coding if the degree stays the same, the original data can be recovered from subset of enough points Çdo Çdo Pse janë të nevojshme angazhimet polinomiale? Why Polynomial Commitments Are Needed? Using polynomials and erasure codes solves many problems, but creates a new one: How do we prove that a piece of data truly belongs to the committed polynomial? This is where Një angazhim KZG lejon: KZG polynomial commitments duke u angazhuar në një polinomi me një element të vetëm të grupit të vogël proving that a data point is one of the polynomial’s evaluations verifikimi i provës pa shkarkuar polinomin ose duke e rindërtuar atë Kjo pronë është thelbësore për planin e shkallëzimit të Ethereum sepse validatorët duhet të verifikojnë disponueshmërinë e të dhënave në mënyrë efikase pa lexuar megabyte të të dhënave blob. dhe të mbështetet në polinomet për të ndarë të dhënat në të , and Çdo blob trajtohet si një polinomial vlerësimet e të cilit mbushin të dhënat. Kur të dhënat zgjerohen dhe rregullohen në kolona, validatorët marrin vetëm copa të vogla, megjithatë struktura polinomiale siguron që të gjitha copa janë konsistente. Çdo provë konfirmon se një qelizë specifike korrespondon me polinomin e kryer në krye të bllokut. Pjesë Protokolli falënderues columns cells blobs KZG proofs Falë angazhimeve polinomiale, Ethereum mund të shkallëzohet në mënyrë të sigurtë disponueshmëria e të dhënave duke reduktuar në mënyrë drastike ngarkesën në nyjet individuale. dhe të pjekur. Pllakë 4844 Tjetra, ne do të marrim një vështrim më të afërt se si punon PeerDAS, se si angazhimet KZG luajnë një rol kyç në të, dhe se si kodimi i fshirjes lejon rrjetin për të rimarrë të dhënat e humbura. Tjetra, ne do të marrim një vështrim më të afërt se si punon PeerDAS, se si angazhimet KZG luajnë një rol kyç në të, dhe se si kodimi i fshirjes lejon rrjetin për të rimarrë të dhënat e humbura.
