SNARK (טיעוני ידע תמציתיים לא אינטראקטיביים) הוא יישומי מציאת קריפטוגרפיים פרימיטיביים חשובים למדרגיות בלוקצ'יין (למשל, אוסף L2) ופרטיות. SNARKs מאפשרים למישהו להוכיח למאמת לא בוטח V (למשל, blockchain Ethereum) שהם יודעים כמה נתונים (למשל, אצווה של עסקאות חוקיות). דרך נאיבית להוכיח זאת תהיה לשלוח את הנתונים V, שיכול לאחר מכן לבדוק ישירות את תקפותו. SNARK משיג את אותו הדבר, אבל עם עלויות טובות יותר V. בפרט, הוכחת SNARK צריכה להיות קצרה יותר מזו הנאיבית הכוללת את הנתונים עצמם. (לפרטים נוספים, עיין בטיוטה של ספר הלימוד שלי, הוכחות, טיעונים ואפס ידע. למבוא ל- SNARKs, ראה שרה מייקלג'ון הצגה בקריפטו a16z סדרת מחקר קיץ.)
עלויות האימות עבור SNARKs יכולות להשתנות, אך הן מובנות היטב ולעתים קרובות די טובות. לדוגמה, PlonK הוכחות עולות בערך 290,000 גז לאמת על Ethereum, בעוד שההוכחות של StarkWare עולות כ-5 מיליון גז. SNARKs פוטנציאליים ישימים במסגרות מגוונות גם מחוץ ל- blockchains - למשל, מה שמאפשר שימוש במהירות אך לא מהימנה שרתים ו חומרה.
אבל מכיוון שאימות SNARK הוא בדרך כלל זול, הגורמים העיקריים ליישום הם העלויות של מוכיח SNARK P. בפוסט זה, אני מסביר כיצד להעריך עלויות אלו כדי לקבוע מתי סביר להשתמש ב- SNARKs וכיצד SNARKs עשויים להשתפר בעתיד. ראוי לציין כי מדובר בחלל שזז במהירות, וכמה מהפרויקטים שנדונו בפוסט זה משפרים באופן אקטיבי את הביצועים שלהם.
אבל קודם כל: איך נפרסים SNARKs
בפריסת SNARK מפתח בדרך כלל כותב תוכנית מחשב ψ שלוקח כקלט את הנתונים w שהמוכיח טוען שהוא יודע (w מסמל עד), ובודק את זה w תקף. לדוגמה, באוסף, התוכנית תבדוק שכל העסקאות נכנסות w חתומים דיגיטלית, אינם גורמים ליתרת חשבון כלשהי לרדת מתחת לאפס, וכן הלאה. התכנית ψ לאחר מכן מוזן דרך א חזית SNARK שמרכיב אותו לפורמט נוח יותר ליישום של טכנולוגיית SNARK. פורמט ידידותי ל-SNARK זה נקרא an ייצוג ביניים (IR).
בדרך כלל, ה-IR הוא סוג של מופע של סיפוק מעגלים ששווה ערך לו ψ. זה אומר שהמעגל C לוקח כקלט את הנתונים w, כמו גם כמה תשומות נוספות הנקראות בדרך כלל "ייעוץ לא דטרמיניסטי", והרצות ψ on w. תשומות העצות משמשות כדי לעזור C לָרוּץ ψ, תוך שמירה C קָטָן. למשל, בכל פעם ψ מחלק שני מספרים x ו y, המנה q והשאר r ניתן לספק כייעוץ ל C, ו C יכול פשוט לבדוק את זה x = qy + r. בדיקה זו היא זולה יותר מאשר ביצוע C להפעיל אלגוריתם חלוקה לחישוב q ו r מאפס.
לבסוף, מוחל SNARK לשביעות רצון המעגל C. זה נקרא אחורי SNARK. עבור קומץ בעיות מאוד מובנות כגון כפל מטריצה, פיתולים, ו מספר בעיות גרפים, קיימים SNARKs ידועים שנמנעים מהפרדיגמת החזית/עורפית הזו ובכך משיגים הוכחה מהירה בהרבה. אבל המוקד של הפוסט הזה הוא על SNARKs למטרות כלליות.
כפי שנראה, עלויות ההוכחה של הקצה האחורי של SNARK גדלות C's גודל. שְׁמִירָה C קטן יכול להיות מאתגר, מכיוון שמעגלים הם פורמט מוגבל ביותר שבו ניתן לבטא חישוב. הם מורכבים מ שערים, מחובר על ידי חוטים. כל שער g ניזון בכמה ערכים ומחיל א מאוד פונקציה פשוטה לערכים אלה. לאחר מכן התוצאה מוזנת לשערי "בהמשך" דרך החוטים היוצאים מהם g.
מדרגיות SNARK: כמה זמן זה באמת לוקח?
שאלת המפתח היא, כמה זמן עוד לוקח מבחן SNARK, יחסית לביצוע פשוט מחדש ψ על הנתונים? התשובה היא מוכיח תקורה של ה-SNARK, יחסית ל בדיקת עדים ישירה. הביטוי האחרון מתייחס לכך, בהוכחה הנאיבית שבה P שולח w ל V, V בדיקות wתוקף של על ידי ביצוע ψ על זה.
זה מועיל לחלק את המוכיח תקורה ל"חזית תקורה" ו-"גב תקורה". אם מעריכים את המעגל C שער אחר שער הוא F יקר יותר מאשר ריצה ψ, אז אנחנו אומרים שהתקורה הקדמית היא F. אם מיישמים את המוכיח האחורי על C is B יקר יותר מהערכה C שער אחר שער, אז אנחנו אומרים שהחלק האחורי הוא B. התקורה הכוללת של המוכיח היא מוצר, F·B. תקורה כפולה זו יכולה להיות משמעותית גם אם F ו B הם צנועים בנפרד.
בפועל, F ו B שניהם יכולים להיות בערך 1000 או יותר. פירוש הדבר שתקרת ההוכחה הכוללת ביחס לבדיקת עדים ישירה יכולה להיות מיליון עד 1 מיליון או יותר. תוכנית שפועלת רק לשנייה אחת במחשב נייד יכולה בקלות להוביל למבחן SNARK שדורש עשרות או מאות ימים של זמן חישוב (חד-פתיל). למרבה המזל, עבודה זו ניתנת להקבלה בדרך כלל בהיקפים שונים (בהתאם ל- SNARK).
לסיכום, אם אתה רוצה להשתמש ב-SNARK באפליקציה היום, אז אחד משלושה דברים צריך להיות נכון:
- בדיקת עדים ישירה נמשכת הרבה פחות משנייה אחת במחשב נייד.
- בדיקת עדים ישירה מתאימה במיוחד לייצוג במעגל, כך שהתקורה הקדמית קטנה.
- אתה מוכן להמתין ימים עד שהמוכיח SNARK יסתיים, ו/או לשלם עבור משאבי מחשוב מקבילים עצומים.
Tשאר הפוסט הזה מסביר מאיפה מגיעות תקורה חזיתית ועורפית, וכיצד אני מעריך אותן עבור SNARKs שונים. לאחר מכן נפנה לסיכויים לשיפור.
הפרדת חזיתות וקצה אחוריים
הפרדה מוחלטת של חזיתות מקצה אחוריים יכולה להיות מאתגרת מכיוון שקצה אחוריים שונים תומכים בסוגים שונים של מעגלים. לפיכך, חזיתות יכולות להיות שונות בהתאם לקצה האחורי איתו הם מצפים להתממשק.
קצה אחורי של SNARK תומכים בדרך כלל במה שנקרא מעגלים אריתמטיים, כלומר הכניסות למעגלים הן אלמנטים של שדה סופי כלשהו, ושהשערים של המעגל מבצעים חיבור וכפל של שני רכיבי שדה. מעגלים אלה תואמים בערך לתוכניות מחשב בקו ישר (ללא ענפים, הצהרות מותנות וכן הלאה) שהן אלגבריות בטבען - כלומר, סוג הנתונים הפרימיטיבי שלהן הוא אלמנטים של שדה.
רוב הענפים האחוריים למעשה תומכים בהכללה של מעגלים אריתמטיים הנקראים לעתים קרובות מקרים של Rank-1 Constraint Satisfaction (R1CS). למעט החריג הבולט של גרוט16 וקודמיו, SNARKs אלה יכולים להתבצע כדי לתמוך גם ב-IRs אחרים. לדוגמה, StarkWare משתמשת במשהו שנקרא ייצוג ביניים אלגברי (AIR), אשר דומה גם לרעיון הנקרא חשבון פלונקיש זה יכול להיות נתמך על ידי PlonK ו-backends אחרים. היכולת של חלק מהחלקים האחוריים לתמוך ב-IRs כלליים יותר יכולה להפחית את התקורה של ממשקים קדמיים שמייצרים את אותם IRs.
הקצה האחורי משתנים גם במונחים של השדות הסופיים שבהם הם תומכים באופן טבעי. אדון בזה עוד בסעיף הבא.
גישות שונות לחזיתות
כמה תוכנות מחשב (מיוחדות מאוד) מתאימות באופן טבעי למעגלים אריתמטיים. דוגמה אחת היא תוכנת המחשב המבצעת כפל נאיבי של מטריצות על פני שדה כלשהו. אבל רוב תוכנות המחשב אינן קו ישר או אלגבריות. לרוב הם כרוכים בהצהרות מותנות, פעולות כגון חלוקת מספרים שלמים או חשבון נקודה צפה שאינן מתאימות באופן טבעי לאריתמטיקה של שדה סופי ועוד. במקרים אלה, התקורה הקדמית תהיה משמעותית.
אחת מגישות החזית הפופולריות היא לייצר מעגלים שבעצם מבצעים שלב אחר שלב מעבד פשוט, הנקרא גם מכונה וירטואלית (VM). מעצבי Frontend מציינים קבוצה של "פעולות פרימיטיביות" בדומה להוראות הרכבה עבור מעבדי מחשב אמיתיים. מפתחים שרוצים להשתמש ב-frontend יכתבו "תוכנות בדיקת עדים" ישירות בשפת ה-Assembly או אחרת בשפה ברמה גבוהה יותר כגון Solidity, והתוכנות שלהם יקומפלו אוטומטית לקוד assembly.
לדוגמה, של StarkWare בקהיר היא שפת הרכבה מוגבלת מאוד שבה הוראות הרכבה מאפשרות בערך חיבור וכפל על פני שדה סופי, קריאות פונקציות וקריאה וכתיבה לזיכרון בלתי ניתן לשינוי (כלומר, כתיבה פעם אחת). ה-VM של קהיר הוא ארכיטקטורת פון נוימן, כלומר המעגלים המיוצרים על ידי החזית לוקחים למעשה תוכנית קהיר כקלט ציבורי ו"מריצים" את התוכנית על העד. שפת קהיר היא Turing Complete - למרות ערכת ההוראות המצומצמת שלה, היא יכולה לדמות ארכיטקטורות סטנדרטיות יותר, אם כי זה עשוי להיות יקר. החזית של קהיר הופכת תוכניות קהיר לביצוע T הוראות פרימיטיביות למה שנקרא "תואר-2 אוויר עם T שורות ובערך 50 עמודות." מה בדיוק זה אומר לא חשוב לפוסט הזה, אבל מבחינת מוכיחי SNARK, זה מתאים למעגלים עם בין 50 ל-100 שערים לכל אחד מהשערים T שלבים של מעבד קהיר.
RISC אפס נוקט בגישה דומה לקהיר, אבל כשהמכונה הוירטואלית היא מה שנקרא אדריכלות RISC-V, ארכיטקטורת קוד פתוח עם מערכת אקולוגית תוכנה עשירה שהולכת וגדלה בפופולריות. כמערכת הוראות פשוטה מאוד, תכנון חזית SNARK יעיל שתומך בו עשוי להיות נסבל יחסית (לפחות ביחס לארכיטקטורות מסובכות כגון x86 או ARM). החל ממאי, RISC Zero הופך תוכניות מבצע T הוראות RISC-V פרימיטיביות לתוך תואר 5 AIRs עם 3T שורות ו 160 עמודות. זה מתאים למעגלים עם לפחות 500 שערים לכל שלב של מעבד RISC-V. שיפורים נוספים צפויים בעתיד הקרוב.
הפרויקטים השונים של zkEVM (למשל, zkSync 2.0, Scroll, zkEVM של Polygon) לוקחים את המכונה הוירטואלית להיות (דוה) ה-Ethereum Virtual Machine. התהליך של הפיכת כל הוראת EVM ל"גאדג'ט" שווה ערך (כלומר, מעגל אופטימלי המיישם את ההוראה) מעורב באופן משמעותי יותר מאשר בארכיטקטורות קהיר ו-RISC-V הפשוטות יותר. מסיבה זו ומסיבות אחרות, חלק מהפרויקטים של zkEVM לא מיישמים ישירות את ערכת ההוראות של EVM אלא קומפילציה של תוכניות Solidity ברמה גבוהה לשפות assembly אחרות לפני שהופכים אותן למעגלים. תוצאות ביצועים מפרויקטים אלה ממתינים.
פרויקטים של "אמולטור CPU" כמו RISC-V וקהיר מייצרים מעגל אחד שיכול להתמודד עם כל התוכניות בשפת ה-assembly המשויכת. גישות חלופיות הן "דמויות ASIC", המייצרות מעגלים שונים עבור תוכניות שונות. גישה דמוית ASIC זו יכולה להניב מעגלים קטנים יותר עבור תוכניות מסוימות, במיוחד כאשר הוראת ההרכבה שהתוכנית מבצעת בכל שלב זמן אינה תלויה בקלט של התוכנית. לדוגמה, זה יכול להימנע לחלוטין מתקורה של חזית קצה עבור תוכניות קו ישר כגון כפל מטריצה נאיבי. אבל גם גישת ה-ASIC נראית מוגבלת מאוד; עד כמה שידוע לי, לא ידוע איך להשתמש בו כדי לתמוך בלולאות ללא גבולות איטרציה קבועים מראש.
המרכיב האחרון של תקורה חזיתית נובע מהעובדה שכל SNARKs משתמשים במעגלים הפועלים על פני שדות סופיים. המעבד במחשב הנייד שלך יכול להכפיל או להוסיף שני מספרים שלמים עם הוראת מכונה אחת. אם קצה קצה מוציא מעגל על שדה בעל מאפיין גדול מספיק, הוא יכול למעשה לדמות את הכפל או החיבור הזה באמצעות פעולת השדה המתאימה. עם זאת, יישום פעולת השטח במעבד אמיתי ידרוש בדרך כלל הוראות מכונה רבות (אם כי לחלק מהמעבדים המודרניים יש תמיכה מקורית עבור שדות מסוימים).
חלק מהחלקים האחוריים של SNARK מאפשרים אפשרויות שדה גמישות יותר מאחרים. לדוגמה, אם הקצה האחורי עושה שימוש בקבוצה קריפטוגרפית G, השדה של המעגל צריך להתאים למספר האלמנטים שבו G, מה שיכול להיות מגביל. בנוסף, לא כל השדות תומכים באלגוריתמים מעשיים של FFT.
יש רק SNARK אחד מיושם, להישבר, שתומך באופן טבעי בחישובים על פני שדות שרירותיים (גדולים מספיק). יחד עם שלה צאצאים, יש לו את ביצועי הוכחת הבטון המהירים ביותר המוכרים אפילו בתחומים שבהם תומכים SNARKs אחרים, אבל ההוכחות שלו כרגע גדולות מדי עבור יישומי בלוקצ'יין רבים. עבודה אחרונה מבקש לשפר את גודל ההוכחה, אך המוכיח איטי יותר מבחינה אסימפטוטית ויש נראה מחסומים למעשיות.
חלק מהפרויקטים בחרו לעבוד על שדות עם אריתמטיקה מהירה במיוחד. לדוגמה, פלונקי2 ואחרים משתמשים בשדה של מאפיין 264 - 232 + 1 מכיוון שניתן ליישם חשבון בתחום זה מהר יותר פי כמה מאשר בשדות פחות מובנים. עם זאת, שימוש במאפיין כה קטן עלול להוביל לאתגרים בייצוג יעיל של אריתמטיקה של מספרים שלמים באמצעות פעולות שדה (למשל, הכפלת שני מספרים שלמים ללא סימן של 32 סיביות עשויה להניב תוצאה גדולה יותר ממאפיין השדה).
אבל לא משנה מה, כדי שכל SNARKs הפופולריים היום ישיגו 128 סיביות של אבטחה (ללא גידול משמעותי בעלויות האימות), הם צריכים לעבוד על שדה בגודל גדול מ-2128. עד כמה שאני יכול לדעת, זה אומר שכל פעולת שדה תדרוש לפחות כעשרה מכפלות של מכונה של 64 סיביות, והרבה יותר תוספות ופעולות סיביות. לפיכך, יש להביא בחשבון לפחות סדר גודל תקורה חזיתית בשל הצורך במעגלים הפועלים על פני שדות סופיים.
לסיכום, חזיתות קיימות המשתמשות בהפשטה של מכונות וירטואליות מייצרות מעגלים עם שערים של פי 100 עד פי 1000 לכל שלב של המכונה הוירטואלית, ואולי יותר עבור מכונות וירטואליות מסובכות יותר. נוסף על כך, אריתמטיקה של שדה סופי איטית לפחות פי 10 מהוראות אנלוגיות במעבדים מודרניים (למעט חריגים אפשריים אם למעבד יש תמיכה מובנית בשדות מסוימים). "גישת ASIC frontend" עשויה לצמצם חלק מתקורות אלו, אך היא מוגבלת כיום בסוגי התוכניות שבהן היא יכולה לתמוך.
מהם צווארי הבקבוק האחוריים?
SNARKs עבור סיפוק מעגלים מתוכננים בדרך כלל על ידי שילוב של פרוטוקול מאובטח תיאורטי של מידע הנקרא "פולינום IOP" עם פרוטוקול קריפטוגרפי הנקרא "ערכת מחויבות פולינומית." ברוב המקרים, צוואר הבקבוק הבטון עבור המוכיח הוא ערכת המחויבות הפולינומית. בפרט, ל-SNARKs אלה יש את המוכיח התחייבות קריפטוגרפית לפולינום אחד או יותר שהדרגה שלהם היא (לפחות) |C|, מספר השערים במעגל C.
בתורו, צוואר הבקבוק של הבטון בתוך ערכת המחויבות הפולינומית יהיה תלוי בסכימה שבה נעשה שימוש ובגודל המעגל. אבל זו תמיד תהיה אחת משלוש הפעולות הבאות: מחשוב FFTs, אקספוננציציות בקבוצה קריפטוגרפית, או מרקל-האשינג. מרקל-האשינג הוא בדרך כלל צוואר בקבוק רק אם המעגל קטן, אז לא נדון בו יותר.
התחייבויות פולינומיות המבוססות על יומן דיסקרטי
בהתחייבויות פולינומיות המבוססות על קשיות בעיית הלוגריתם הבדיד בקבוצת קריפטוגרפית G (KZG, תבליטים, בִּצִית, ו Hyrax-commit), על המוכיח לחשב א מחויבות וקטורית של פדרסן למקדמים של הפולינום. זה כרוך בריבוי-אקספונציה, בגודל השווה לדרגת הפולינום. ב-SNARK, תואר זה הוא בדרך כלל הגודל |C| של המעגל C.
נעשה בצורה נאיבית, ריבוי אקספוננציה של גודל |C| דורש בערך 1.5·|C|·היכנס |G| ≈ 400·|C| פעולות קבוצתיות, היכן |G| מציין את מספר האלמנטים בקבוצה G. עם זאת, קיימת גישה, הנקראת אלגוריתם של פיפנגר, שיכולה להפחית זאת בגורם של בערך יומן |C|. עבור מעגלים גדולים (נניח, |C| ≥ 225), יומן זה |C| הפקטור יכול להיות 25 או יותר, כלומר, עבור מעגלים גדולים, אנו מצפים שהמחויבות הווקטורית של פדרסן יכולה להיות ניתנת לחישוב עם קצת יותר מ-10·|C| פעולות קבוצתיות. כל פעולה קבוצתית בתורה נוטה להיות (כמגרש כדורים גס מאוד) איטית בערך פי 10 מפעולת שטח סופית. SNARKs המשתמשים בהתחייבויות פולינומיות אלה יקרות לא פחות P בערך 100·|C| פעולות שטח.
לרוע המזל, למכשירי SNARK קיימים יש תקורה נוספת על מקדם פי 100 לעיל. לדוגמה:
- Spartanהמוכיח של, המשתמש בהתחייבות הפולינומית של Hyrax, צריך לעשות |C|½ ריבוי אקספוננציציות רבות בכל גודל |C|½, החלשת המהירות מהאלגוריתם של פיפנגר בפקטור של בערך שניים.
- In גרוט16, P חייב לעבוד על קבוצה ידידותית להתאמה, שפעולותיה בדרך כלל איטיות לפחות פי 2 מקבוצות שאינן ידידותיות להתאמה. P חייבים גם לבצע 3 ריבוי-אקספונציאנציות במקום 1. ביחד, זה גורם להאטה נוספת של פקטור-6 לפחות ביחס ל-100·|C| הערכה לעיל.
- מרלין ו PlonK דורשים גם זיווגים, והמוכיחים שלהם להתחייב ליותר מ-3 פולינומים במידה ניכרת.
- לכל SNARK שמשתמש תבליטים (לְמָשָׁל, Halo2, שזה בערך PlonK אבל עם התחייבויות פולינומיות מסוג Bulletproofs ולא KZG), המוכיח צריך לחשב לוגריתמית ריבוי אקספוננציציות רבות במהלך שלב ה"פתיחה" של סכימת המחויבות, וזה מוחק במידה רבה כל מהירות של Pippenger.
לסיכום, נראה כי ל-SNARKs ידועים המשתמשים בהתחייבויות וקטוריות של Pedersen יש תקורה עורפית של לפחות פי 200 ועד פי 1000 או יותר.
התחייבויות פולינומיות אחרות
עבור SNARKs המשתמשים בהתחייבויות פולינומיות אחרות (כגון FREE ו Ligero-commit), צוואר הבקבוק הוא שהמוכיח צריך לבצע FFTs גדולים. לדוגמה, במטוסי תואר 2 AIR המיוצרים על ידי קהיר (עם 51 עמודות ו T שורות, אחת לכל שלב של ה-CPU של קהיר), המוכיח הפרוס של StarkWare עושה לפחות 2 FFTs לכל עמודה, באורך בין 16 ·T ו 32 ·T. הקבועים 16 ו 32 תלויים בפרמטרים פנימיים של FRI כפי שנקבעו על ידי StarkWare וניתן לצמצם - אך במחיר של עלויות אימות מוגברות.
באופן אופטימי, FFT באורך 32·T לוקח בערך 64·T·log(32T) הכפלות שדות. זה אומר שגם עבור ערכים קטנים יחסית של T (לְמָשָׁל, T ≥ 220), מספר פעולות השדה בכל עמודה הוא לפחות 64·25·T= 1600·T. אז נראה כי התקורה האחורית היא לפחות באלפים. יתר על כן, יתכן ש-FFTs גדולים נמצאים אפילו יותר בצוואר בקבוק על ידי רוחב הפס של הזיכרון מאשר על ידי פעולות שטח.
בהקשרים מסוימים, ניתן להפחית את התקורה האחורית של SNARKs שמבצעים FFTs גדולים באמצעות טכניקה הנקראת aggregation proof. עבור רולאפים, זה אומר את זה P (שירות האוסף) מפרק אצווה גדולה של עסקאות, למשל, ל-10 קבוצות קטנות יותר. לכל אצווה קטנה i, P מייצר הוכחת SNARK πi על תוקף האצווה. אבל P אינו מפרסם את ההוכחות הללו לאתריום, מכיוון שהדבר יוביל לעלייה של כמעט פי 10 בעלויות הגז. במקום זאת, ה-SNARK מוחל שוב, הפעם כדי לייצר הוכחה π קובעים זאת P יודע π1 ...,π10. כלומר העד ש P טוען לדעת הוא עשר ההוכחות π1,…,π10, ובדיקת עדים ישירה מיישמת את הליך אימות SNARK על כל אחת מההוכחות. ההוכחה היחידה הזו π פורסם ב-Ethereum.
בהתחייבויות פולינומיות כגון FRI ו- Ligero-commit, יש מתח חזק ביניהן P זמן ו V עלויות, כאשר פרמטרים פנימיים משמשים כפתור שיכול להחליף אחד לשני. מאז π1 ,…,π10 לא מתפרסמים ב-Ethereum, ניתן לכוון את הכפתור כך שההוכחות הללו הם גדולים, והייצור שלהם מהיר יותר. רק ביישום הסופי של SNARK, לצבור π1 ,…,π10 להוכחה אחת π, האם יש להגדיר את סכימת ההתחייבויות כדי להבטיח הוכחה קטנה.
StarkWare מתכננת לפרוס צבירה הוכחה באופן מיידי. זה גם המוקד של פרויקטים כגון פלונקי2.
מהם צווארי הבקבוק הנוספים להרחבה של SNARK?
פוסט זה התמקד בהוכחה זמן, אבל עלויות בדיקה אחרות יכולות להיות גם צווארי בקבוק של מדרגיות. לדוגמה, עבור חלקים אחוריים רבים של SNARK, המוכיח צריך לאחסן מספר רכיבי שדה עבור כל שער C, ועלות השטח הזו יכולה להיות עצומה. למשל, תוכנית ψ ריצה בשנייה אחת על מחשב נייד יכולה לבצע אולי מיליארד פעולות פרימיטיביות במעבד מודרני. כפי שראינו, באופן כללי יש לצפות C לדרוש יותר מ-100 שערים לכל פעולה כזו. המשמעות היא 100 מיליארד שערים, אשר, בהתאם ל-SNARK, יכולים להיות עשרות או מאות טרה-בייט של שטח עבור P.
דוגמה נוספת: SNARKs פופולריים רבים (למשל, PlonK, מרלין, גרוט16) דורשים "טקס התקנה מהימן" מסובך כדי ליצור "מפתח הוכחה" מובנה, אשר חייב להיות מאוחסן על ידי המוכיח. עד כמה שידוע לי, ה הטקס הגדול ביותר מסוג זה יצר מפתח הוכחה המסוגל לתמוך במעגלים עם כ-228≈250 מיליון שערים. המפתח המוכיח הוא בגודל של כמה עשרות גיגה-בייט.
בהקשרים שבהם צבירת הוכחות אפשרית, ניתן לצמצם באופן משמעותי את צווארי הבקבוק הללו.
מבט קדימה: סיכויים ל-SNARKs ניתנים להרחבה יותר
גם תקורה חזיתית וגם תקורה עורפית יכולות להיות שלושה סדרי גודל או יותר. האם אנו יכולים לצפות שאלו ירדו באופן משמעותי בעתיד הקרוב?
אני חושב שנעשה זאת - לנקודה מסוימת. ראשית, הרכיבים האחוריים המהירים ביותר כיום (למשל, Spartan ו להישבר, ו-SNARKs אחרים המשלבים את פרוטוקול בדיקת סכום עם מחויבויות פולינומיות) יש הוכחות גדולות - בדרך כלל שורש ריבועי בגודל המעגל - כך שאנשים לא באמת משתמשים בהן. אני מצפה שגודל ההוכחה וזמן המאמת יופחתו באופן משמעותי בעתיד הקרוב באמצעות קומפוזיציה עומק אחת עם SNARKs עם הוכחה קטנה. בדומה לצבירה של הוכחות, זה אומר שמוכיח יפיק תחילה הוכחה SNARK π עם "הוכחה מהירה, הוכחה גדולה" SNARK, אבל לא לשלוח π ל V. במקום זאת, P ישתמש ב-SNARK בעל הוכחה קטנה כדי לייצר הוכחה π" שזה יודע π, ולשלוח π" ל V. זה יכול לגלח סדר גודל מהתקורה האחורית של SNARKs הפופולריים היום.
שנית, האצת חומרה יכולה לעזור. כלל כללי גס מאוד הוא שמעבדי GPU יכולים לקנות מהירות של פי 10 על מעבדים, ו-ASIC מהירות של פי 10 על פני GPU. עם זאת, יש לי שלוש חששות בחזית זו. ראשית, FFTs גדולים עלולים להיות צווארי בקבוק על ידי רוחב הפס של הזיכרון במקום פעולות שטח, כך ש-SNARKs שמבצעים FFTs כאלה עשויים לראות מהירות מוגבלת מחומרה מיוחדת. שנית, בעוד שפוסט זה התמקד בצוואר הבקבוק של המחויבות הפולינומית, SNARKs רבים דורשים מהמוכיח לבצע פעולות אחרות שהן רק מעט פחות יקרות. אז לשבור את צוואר הבקבוק של המחויבות הפולינומית (למשל, האצת ריבוי-אקספונציונציות ב-SNARK מבוססי יומן דיסקרטיים) עשויה להשאיר פעולת צוואר בקבוק חדשה שאינה טובה בהרבה מזו הישנה. (לדוגמה, ל-SNARKs הכוללים Groth16, Marlin ו-PlonK יש גם את ה-FFTs המוכיח את עצמו, בנוסף לריבוי אקספוננציציות.) לבסוף, השדות והעקומות האליפטיות המובילות ל-SNARKs היעילים ביותר עשויים להמשיך ולהתפתח במשך זמן מה, וזה עשוי ליצור אתגרים עבור האצת מוכח מבוסס ASIC.
בחזית הקצה, אנו עשויים לגלות יותר ויותר שגישת "אמולטור ה-CPU" של פרויקטים כמו קהיר, RISC Zero, zkEVMs ואחרים למעשה מתרחבת די טוב (במונחים של ביצועים) עם המורכבות של ערכות הוראות המעבד. אכן, זו בדיוק התקווה של פרויקטים שונים של zkEVM. המשמעות עשויה להיות שבעוד שהתקורה הקדמית נשארת בשלושה סדרי גודל או יותר, החזיתות מצליחות לתמוך ב-VM שתואמות יותר ויותר ארכיטקטורות CPU אמיתיות. דאגה מתנגדת היא שהחזיתות עלולות להסתבך וקשות לביקורת, מכיוון שגאדג'טים מקודדים ביד המיישמים הוראות מסובכות יותר ויותר מתרבות. שיטות אימות פורמליות ימלאו ככל הנראה תפקיד חשוב בטיפול בחשש זה.
לבסוף, לפחות ביישומי בלוקצ'יין, אנו עשויים לגלות שרוב החוזים החכמים המופיעים בטבע משתמשים בעיקר בהוראות פשוטות וידידותיות ל-SNARK. זה עשוי לאפשר בפועל תקורה חזיתית נמוכה תוך שמירה על הכלליות וחוויית מפתח משופרת שמגיעה עם תמיכה בשפות תכנות ברמה גבוהה כמו Solidity וערכות הוראות עשירות כולל אלה של EVM.
***
ג'סטין תאלר is פרופסור חבר באוניברסיטת ג'ורג'טאון. לפני שהצטרף לג'ורג'טאון, הוא בילה שנתיים כמדען מחקר ב-Yahoo Labs בניו יורק, לפניהן היה עמית מחקר ב- מכון סימונס לתורת המחשוב באוניברסיטת ברקלי.
***
תודות: אני אסיר תודה אלנה בורגר על הצעת הנושא של פוסט זה, וכן ארסו ארון, ג'וזף בונו, ו סם ראגסדייל להערות מעניינות. תודה מיוחדת גם לעורך שלי, טים סאליבן.
***
הדעות המובעות כאן הן אלה של אנשי AH Capital Management, LLC ("a16z") המצוטטות ואינן הדעות של a16z או החברות הקשורות לה. מידע מסוים הכלול כאן התקבל ממקורות צד שלישי, כולל מחברות פורטפוליו של קרנות המנוהלות על ידי a16z. למרות שנלקחה ממקורות האמינים כאמינים, a16z לא אימתה מידע כזה באופן עצמאי ואינה מציגה מצגים לגבי הדיוק המתמשך של המידע או התאמתו למצב נתון. בנוסף, תוכן זה עשוי לכלול פרסומות של צד שלישי; a16z לא סקרה פרסומות כאלה ואינה תומכת בתוכן פרסומי כלשהו הכלול בהן.
תוכן זה מסופק למטרות מידע בלבד, ואין להסתמך עליו כייעוץ משפטי, עסקי, השקעות או מס. עליך להתייעץ עם היועצים שלך באשר לעניינים אלה. הפניות לניירות ערך או לנכסים דיגיטליים כלשהם נועדו למטרות המחשה בלבד, ואינן מהוות המלצת השקעה או הצעה לספק שירותי ייעוץ השקעות. יתר על כן, תוכן זה אינו מכוון ואינו מיועד לשימוש על ידי משקיעים או משקיעים פוטנציאליים כלשהם, ואין להסתמך עליו בשום פנים ואופן בעת קבלת החלטה להשקיע בקרן כלשהי המנוהלת על ידי a16z. (הצעה להשקעה בקרן a16z תתבצע רק על ידי מזכר ההנפקה הפרטית, הסכם המנוי ותיעוד רלוונטי אחר של כל קרן כזו ויש לקרוא אותה במלואה). המתוארים אינם מייצגים את כל ההשקעות בכלי רכב המנוהלים על ידי a16z, ואין כל ודאות שההשקעות יהיו רווחיות או שלהשקעות אחרות שיבוצעו בעתיד יהיו מאפיינים או תוצאות דומות. רשימה של השקעות שבוצעו על ידי קרנות המנוהלות על ידי אנדריסן הורוביץ (למעט השקעות שעבורן המנפיק לא נתן אישור ל-a16z לחשוף בפומבי וכן השקעות בלתי מוקדמות בנכסים דיגיטליים הנסחרים בבורסה) זמינה בכתובת https://a16z.com/investments /.
תרשימים וגרפים המסופקים בתוכן הם למטרות מידע בלבד ואין להסתמך עליהם בעת קבלת החלטת השקעה כלשהי. ביצועי העבר אינם מעידים על תוצאות עתידיות. התוכן מדבר רק לתאריך המצוין. כל תחזיות, אומדנים, תחזיות, יעדים, סיכויים ו/או דעות המובעות בחומרים אלו כפופים לשינויים ללא הודעה מוקדמת ועשויים להיות שונים או מנוגדים לדעות שהובעו על ידי אחרים. אנא ראה https://a16z.com/disclosures למידע חשוב נוסף.
