הוכחות של ידע אפס נראות לעתים קרובות מסתוריות משום שהמתמטיקה מאחורין מתקדמת מאוד.הרבה אנשים קוראים לזה "מתמטיקה של הירח", משום שזה מרגיש כמו משהו קסום או מעולם אחר. אנחנו רוצים להסיר את הבלבול הזה ולעזור לכולם להבין מה עושות למעשה הוכחות של ידע אפס, ואף על פי שהם עדיין מרגישים קסומים, אנו מאמינים שהקהילה צריכה להבין את הרעיונות הטכניים שמאחורי העבודה שלנו. במאמר זה, אנו מציגים בלוק בניין חשוב המשמש במערכות הוכחה של ידע אפס רבות: לאחר מכן, אנו מסבירים , אחד הסוגים הפופולריים והמעשיים ביותר של תוכניות מחויבות פולינומיות. polynomial commitment schemes KZG לאחר מכן אנו מתארים כיצד וכיצד לבסוף, אנו מראים כיצד zk-rollups ו Proto-Danksharding יכולים לעבוד יחד בצורה חלקה ויעילה - משהו שאפשר במיוחד כי . 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? פולינומיות הן כלים מתמטיים עוצמתיים משום שהם מאפשרים לנו לייצג אובייקטים גדולים או מורכבים ביעילות. דוגמה נפוצה היא לייצג וקטור n-dimensional של אלמנטים שדה v באמצעות פולינומי יחיד. אנו עושים זאת על ידי יצירת φ(x) פולינומי שעובר דרך הנקודות (i, v_i) עבור כל אינדקס i = 1, 2, ..., n. לדוגמה, וקטור 3-dimensional v = [2, 0, 6] ניתן לקודד על ידי הפולינומי. because plugging in the values gives , , ו באופן כללי, בהתחשב בכל n נקודות, תמיד קיים פולינומיה ייחודית של מעלות ב-n − 1 אשר עובר את כולם. φ(x) = 4x² − 14x + 12 φ(1) = 2 φ(2) = 0 φ(3) = 6 תהליך בנייה של פולינומי זה נקרא אינטרפולציה פולינומי, ואחד הטכניקות הנפוצות ביותר הוא , אשר מספק נוסחה ישירה לבניית הפולינומיה מן הנקודות שנקבעו.באמצעות שיטה זו, אנו יודעים כעת כיצד לבנות פולינומיה של מעלות . אינטרפולציה של Lagrange n − 1 from exactly n constraints במאמר הקודם: אם אתם יודעים , אתה תמיד יכול לקבוע פולינומיה אחת ייחודית אשר התואר שלה הוא עכשיו, אנחנו רוצים ללכת צעד נוסף ולהבין כדי למצוא את הפולינומיות האלה מתוך הקואורדינטות של n נקודות. n points n − 1 איך אחת השיטות הנפוצות והפשוטות לעשות זאת נקראת אינטרפולציה של לאגראנג' (Lagrange interpolation).אם כי הנוסחאות הרשמיות עשויות להיראות מסובכות, הרעיון הבסיסי הוא פשוט מאוד. אינטרפולציה של לאגראנג' (Lagrange interpolation) נותנת לנו דרך ישירה לבנות את הפולינומי שהולך דרך כל הנקודות. לדוגמה, נניח שאנחנו רוצים למצוא פולינומיה. כדי לעשות זאת, אנחנו צריכים בדיוק 3 נקודות, והפולינומי חייב לספק את כל שלושת המגבלות האלה. P φ(1) = 2 φ (2) = 0 φ(3) = 6 כדי לעשות זאת, נבנה 3 sub-polynomials (אחד לכל כפייה) , ו ברמה הגבוהה ביותר . P₁ P₂ P₃ 2 3 subpolynomials אלה חייבים לעקוב אחר אלה sub-הגבלות: 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 כל פולינומיה מתבצעת על ידי בכל הנושאים המוגבלים, רק אחד. 0 ובסופו של דבר אנחנו קובעים: P(x) = P₁(x) + P₂(x) + P₃(x) בואו נבחן במהירות, תוך התייחסות לכרטיסיה הקודמת, כי מכבדים את כל המגבלות: 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 רק בדקנו את זה. בואו נתחיל עם שלושת המקומות האלה, בואו נתחיל , and . P P₁ P₂ P₃ Building P₁ Using the , we can define P₁ as: factorised form P₁(x) = A(x − 2)(x − 3) הוא כבר עונה על המגבלות: P₁ P₁(2) = P₁(3) = 0 עכשיו בואו נמצא כמו למשל: A P₁(1) = 2 יש לנו את המשוואה הבאה: P₁(1) = A(1 - 2)(1 - 3) = 2 אשר נותן לנו: A = 2 ולבסוף : P₁(x) = 2(x − 2)(x − 3) כעת הוא עונה על שלושת המגבלות שלו. P₁ בניין P2 באמצעות The אנחנו יכולים להגדיר כמו : צורה מפעלת P2 P₂(x) = B(x - 1)(x − 3) הוא כבר עונה על המגבלות: P2 P₂(1) = P₂(3) = 0 עכשיו בואו נמצא such as: B P₂(2) = 0 יש לנו את המשוואה הבאה: P₂(2) = B(2 − 1)(2 − 3) = 0 אשר נותן לנו: B = 0 ולבסוף : P₁(x) = 0(x − 1)(x − 3) = 0 כעת הוא עונה על שלושת המגבלות שלו. P₂ בניין P3 באמצעות The אנחנו יכולים להגדיר כמו : צורה מפעלת P3 P₃(x) = C(x − 1)(x − 2) already satisfies constraints: P₃ P₃(1) = P₃(2) = 0 עכשיו בואו נמצא כמו למשל: C P₃(3) = 6 יש לנו את המשוואה הבאה: P₃(3) = C(3 - 1)(3 - 2) = 6 אשר נותן לנו: C = 3 ולבסוף : P₃(x) = 3(x - 1)(x - 2) כעת הוא עונה על שלושת המגבלות שלו. 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 בדיקת P בואו נבדוק במהירות את הוא מכבד את שלושת המגבלות: 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? מערכות מחויבות פולינומיות הן כלים מיוחדים המאפשרים למישהו להתחייב למילנומיה שלמה מבלי להראות מה המילנומיה בעצם היא. משמעות הדבר היא שאתה לא יכול לשנות את ההודעה לאחר התחייבות, ו , meaning no one can learn the message from the commitment alone. Polynomial commitments follow the same rules, but instead of committing to one message, you commit to a whole polynomial with many coefficients. binding hiding החלק החזק של התחייבויות פולינומיות הוא שאתה יכול מאוחר יותר להוכיח את הערך של הפולינומי בנקודות ספציפיות מבלי לחשוף את הפולינומיות כולה. יש לו ערך ב , they can do so without exposing the rest of the polynomial. They simply give a short proof that shows is true, and the verifier can check it using the earlier commitment. The verifier learns nothing else about the polynomial itself. This feature is incredibly useful in zero-knowledge proofs, where the goal is to prove something is true without revealing extra information. ϕ(x) 66 x = 4 “ϕ(4) = 66” Another reason polynomial commitments are useful is that the commitment is much smaller than the polynomial. A polynomial may have hundreds or thousands of values, but the commitment can be just a single small group element, like 48 bytes. This is extremely important for blockchains, where storing or posting large data is expensive. By compressing a large polynomial into one tiny commitment, systems like and זה יכול לחסוך הרבה מקום ולהפחית את העלויות. zk-rollups Proto-Danksharding כדי להפוך את זה קל יותר להבין, לדמיין אליס יש פולינומי סודי, כגון φ(x) = 3x2 + 5x + 2. היא לא רוצה לחשוף את הפולינומי, אבל בוב רוצה הוכחה כי φ(4) = 66. אליס מתחייבת לפולינומי באמצעות תוכנית התחייבות פולינומי ומשלחת בוב את ההתחייבות. מאוחר יותר, היא מגלה רק את הערך 66 ומספקת הוכחה קצרה מראה כי הערך הזה נכון עבור x = 4. בוב בודק את ההוכחה נגד ההתחייבות והופך משוכנע, מבלי ללמוד שום דבר אחר על הפולינומי. KZG Polynomial Commitment מחויבות פולינמית KZG 1. Commitment על מנת להבטיח את ההשפעה האפשרית, יש להקפיד על "השפעה" של המשתמשים על המשתמשים המשתמשים במשתמשים המשתמשים במשתמשים המשתמשים במשתמשים המשתמשים במשתמשים המשתמשים במשתמשים המשתמשים במשתמשים המשתמשים במשתמשים. ) and its contents stay private ( ). binding hiding 2. Evaluation לאחר מכן, המבחן רוצה להוכיח משהו על הפולינומי אז הם בוחרים נקודה x, מחוברים אותה לפולינומי, ומחשבים את התשובה. . They send only this value y, plus a small proof that shows the value came from the committed polynomial. The actual polynomial stays hidden the whole time. This allows the prover to show the polynomial behaves correctly at one point without exposing the entire polynomial. מבלי לחשוף את y=P(x) 3. Verification לבסוף, המבדק בודק אם הערך באמת תואם את הפולינומי מחויב בנקודה באמצעות ההתחייבות וההוכחה, המבדק מבצע בדיקה קריפטוגרפית. זה חייב להיות נכון - גם אם הם מעולם לא ראו את הפולינומי עצמו.אם המבחן מנסה לשקר או לרמות, הצעד של אימות יהיה לתפוס את זה. y x P(x)=y KZG Polynomial Commitment Scheme KZG Polynomial Commitment Scheme KZG יש . four main steps Step 1 - Trusted Setup התקנה אחת נעשתה לפני שהמערכת פועלת. בחר גנרטור g של קבוצת הקשת האליפטית G (תמיכה זוגות). בחר את המידה המקסימלית l של הפולינומי. בחר ערך אקראי סודי: τ ∈ 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 כדי להוכיח את זה: ϕ(a)=b לחשב את היקף הפולינומיות: q(x) = ϕ(x) - b / x - a זה נכון רק אם ההערכה נכונה. לאחר מכן לחשב את ההוכחה: π = g^{q(τ)} זוהי ההערכה של KZG. Step 4 - Verification Given: חוזה C = g^{φ(τ)} הוכחה π = g^{q(τ)} טענת הערכה φ(a) = b The verifier checks: e(c/g^b,g) = e(π,g^τ/g^a) כאן e ( ⋅ , ⋅ ) הוא a . בילינינג בילינינג This equation is equivalent to verifying: q(τ) = ϕ(τ) - b /τ - a אם הבדיקה נמשכת, ההערכה מתקבלת כראוי. הסבר קצר על הבדיקה תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: תגית: שוויון פירושו φ(τ)−b = q(τ)(τ−a), זהות הקוונטית המוערכת ב- τ, אשר מחייבת φ(a)=b אם q(x) נוצר כראוי. (q(x) = φ(x) - b / x - a) הסבר קצר על הבדיקה תגיות LHS: = (τ)−b (C = g^{ϕ(τ)}) e(C/g^b, g) e(g,g)ϕ על RHS: = (π = g^{q(τ)}) e(π, g^τ/g^a) e(g,g)q(τ)⋅(τ−a) שוויון פירושו φ(τ)−b = q(τ)(τ−a), זהות הקוונטית המוערכת ב- τ, אשר מחייבת φ(a)=b אם q(x) נוצר כראוי. (q(x) = φ(x) - b / x - a) Use Cases: ZK-Rollups תגיות In zk-rollups, we must prove that the work done on Layer 2 (L2) is correct. To do this, all the steps of the computation are converted into a big table (a 2D matrix). This happens during a process called . 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: הדור העד א ( X ) א ( X ) c(x) חוק עשוי לומר כי a(x)⋅b(x)−c(x)= 0 משמעות הדבר היא "הפולינומי הראשון המופרד על ידי השני חייב להיות שווה לשלישי." עמוד 1 × עמוד 2 חייב לייצר עמוד 3. במקום לבדוק את הכלל הזה עבור כל ערך אפשרי של x (זה יהיה איטי), zk-rollups לבדוק אותו רק בכמה נקודות אקראיות. אם אני רוצה לבדוק אם שני רשימות ארוכות מתאימות לחוק, אני לא צריך להשוות כל פריט – בדיקת כמה פריטים אקראיים בדרך כלל אומרת לי אם הקשר כולו תקף. Example: Polynomial commitment schemes—such as KZG—are perfect for this. The rollup commits to all the polynomials that describe the L2 computation (something like locking them inside a cryptographic box). Later, the verifier can ask for the values of these polynomials at specific random points. With those values and the commitments, the verifier checks whether the correctness rules hold. If they do, the verifier knows the entire computation is valid. עקבו אחרי ethereum ethereum thanks (EIP-4844) is an upgrade designed to make it much cheaper for rollups to publish their data on Ethereum’s Layer 1. It introduces a new kind of transaction called a סוג זה של עסקה כולל חתיכת נתונים גדולה בשם (around 128 kB). However, this blob is חוזה חכם - חוזה חכם - חוזה חכם - חוזה חכם - חוזה חכם - חוזה חכם על הבלוג עצמו, לא על הבלוג עצמו. Proto-Danksharding Blob-carrying עסקה בלוב not commitment עכשיו השאלה היא: אפשרות אחת היא לקחת את הבלוב ורק אבל החישוי מוגבל: אם אנו מאחסנים רק חישוי אחד, אז מאוחר יותר אנחנו לא יכולים להוכיח שום דבר על הנתונים בתוך הבלוב מבלי לחשוף את הבלוב כולו. כיצד Ethereum צריכה ליצור מחויבות זו לבלוב? hash it Instead, we can treat the blob as a polynomial. (Earlier, we explained how vectors or data can be represented as polynomials.) Using a כגון KZG, Ethereum יכול להתחייב לבלוב בצורה שאינה רק מסתירה את הנתונים, אלא גם מאפשרת אימות של תכונות מסוימות . polynomial commitment scheme בלי להוריד את הבלוג כולו היכולת הזאת היא חיונית למשהו שנקרא DAS מאפשר לאמתנים לבדוק אם blob זמין ומדויק . Instead, validators download only tiny random pieces. Thanks to the math behind polynomial commitments, if enough random samples are correct, validators can be highly confident that the whole blob is available. (Although DAS is not included in the very first version of Proto-Danksharding, it will be added soon as Ethereum continues toward “full Danksharding.”) (DAS) אבחון זמינות נתונים without downloading all 128 kB אבחון זמינות נתונים Ethereum בחר as the polynomial commitment scheme for Proto-Danksharding and future sharding upgrades. Researchers compared several schemes, and concluded that KZG provides the best balance of efficiency, proof size, and simplicity for Ethereum’s roadmap in the short and medium term. KZG How zk-rollups and Ethereum’s Proto-Danksharding interact zk-rollups ו Proto-Danksharding של Ethereum עשוי להיראות כמו מערכות נפרדות, אבל הם שניהם משתמשים בהתחייבויות KZG בדרכים המאפשרות להם לעבוד יחד בצורה חלקה. כאשר Scroll מסיימת את העיבוד של סדרה של עסקאות L2 ומחשבת שורש מצב חדש, היא חייבת לפרסם שלושה דברים על L1 של Ethereum: — the list of L2 transactions, T Si - השורש החדש של המצב לאחר העברת העסקאות הללו, π - הוכחה לכך ששורש המצב החדש נכון. Ethereum צריך לאמת שני דברים: שורש המדינה החדש Si הוא תקף (כלומר העסקאות הושלמו כראוי), ו רשימת העסקאות T היא בדיוק אחת המשמשת לייצר את השורש של המצב הזה.לכן, חייב להיות דרך לקשר את רשימת העסקאות T עם הוכחה π. חנויות Ethereum כמו A המשמעות היא כי למשתמש יש גישה רק ל- לבלוב הזה - בואו נקרא התחייבות זו . Meanwhile, the proof מכיל גם התחייבויות KZG לפולינומים שונים המשמשים במהלך החישוב, כולל הפולינומי המייצג את רשימת העסקאות. . T Blob נתונים KZG commitment Cₜ π Cₚ עכשיו יש לנו שתי התחייבויות KZG שונות ( מתוך הבלוג ו מתוך ההוכחה) כי אנחנו צריכים לבדוק את הפולינומיה (polynomial representation of the transaction list). and really refer to the same data. Cₜ Cₚ should Cₜ Cₚ כדי לעשות זאת, אנו משתמשים בטכניקה הנקראת a הרעיון הוא פשוט: הוכחת שוויון הוכחת שוויון Pick a random-like value This makes z unpredictable and unique to these two commitments. z = hash(Cₜ ∥ Cₚ) 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ₚ אם שני ההתחייבויות נותנות את אותה הערך באותו נקודה אקראית, אז עם סיכוי גבוה מאוד, הם מייצגים את אותו פולינומי. לדוגמה: לדמיין שני אנשים, כל אחד טוען כי יש להם את אותו פולניום סודי.במקום לחשוף את הפולניום כולו, כל אחד מעריך אותו בנקודה אקראית-אמרו x = 103.אם שתי הערכות מתאימות, הסיכוי שיש להם שני פולניומים שונים שמסוגלים להסכים באותה נקודה אקראית מדויקת הוא קטן אסטרונומי. במקום לחשוף את הפולינומיה כולה, כל אחד מעריך אותה בנקודה אקראית-אמרו x = 103. Example This same logic lets Ethereum verify that the transaction list used in the proof זה בדיוק אותו הדבר כמו רשימת העסקאות שפורסמה ב-blob. π בונוס נחמד הוא כי בדיקה שווה ערך זה עובד גם אם שני ההתחייבויות להשתמש לדוגמה, אחד יכול להיות KZG והשני FRI. כל עוד שני ההתחייבויות תומכות פתיחה בנקודה מסוימת, המבדק יכול להשוות אותם, מה שהופך גישה זו גמישה מאוד. שונה שונה Erasure Coding With Polynomials מושג חזק נוסף המשמש הן ב- KZG והן ב- PeerDAS הוא טכניקה זו מאפשרת לשחזר נתונים גם אם חלקים מהם חסרים.באמצעות פולינומים, אנו יכולים לקחת קבוצה קטנה של ערכים מקוריים ולהרחיב אותם למספר ארוך יותר על ידי הערכה של הפולינומי בנקודות נוספות. זה בדיוק איך דגימת זמינות הנתונים של Ethereum (DAS) עובד: הצמתים לא צריכים כל חתיכת נתונים, רק דגימה אקראית המאפשרת להם לשחזר את המידע המקורי עם סיכוי גבוה. erasure coding if the degree stays the same, the original data can be recovered from subset of enough points כל כל Why Polynomial Commitments Are Needed? Why Polynomial Commitments Are Needed? שימוש בפולינומים וקודי מחיקה פותר בעיות רבות, אך יוצר בעיה חדשה: How do we prove that a piece of data truly belongs to the committed polynomial? זה המקום שבו קחו בחשבון כי התחייבות KZG מאפשרת: KZG polynomial commitments committing to a polynomial with a single small group element הוכחה כי נקודת נתונים היא אחת ההערכות של הפולינומיה לאמת את ההוכחה מבלי להוריד את הפולינומי או לשחזר אותו תכונה זו חיונית למסלול ההרחבה של Ethereum, שכן המאשרים חייבים לאמת את זמינות הנתונים ביעילות מבלי לקרוא מגה בייט של נתונים. ו משתמשים בפולינומים כדי לחלק את הנתונים , , ו . Each blob is treated as a polynomial whose evaluations fill the data. When data is extended and arranged into columns, validators only receive small pieces, yet the polynomial structure ensures that all pieces are consistent. To verify this consistency without downloading entire blobs, Ethereum uses כל הוכחה מאשרת כי תא ספציפי תואם את הפולינומי המבוצע בכותרת הבלוק. PeerDAS פרוטוקול תודה columns cells blobs KZG proofs הודות למתחייבויות פולינומיות, Ethereum יכולה להגדיל בבטחה את זמינות הנתונים תוך הפחתה דרסטית של העומס על הצמתים הפרטיים. ושותפים EIP-4844 לאחר מכן, נסתכל מקרוב על האופן שבו פועל PeerDAS, כיצד התחייבויות KZG משחקות תפקיד מפתח בה, וכיצד קידוד מחיקה מאפשר לרשת לשחזר נתונים חסרים. לאחר מכן, נסתכל מקרוב על האופן שבו פועל PeerDAS, כיצד התחייבויות KZG משחקות תפקיד מפתח בה, וכיצד קידוד מחיקה מאפשר לרשת לשחזר נתונים חסרים.
