מה אתה צריך:
- רקע למדעי המחשב
- היסודות של Ethereum
- יסודות החשבון (אופטימיזציה של אילוצים)
מה תקבל:
- היסודות של SNARK עם ידע אפס
- היסודות של עצי מרקל
- כיצד Ethereum יכולה להתאים לאלפי עסקאות בשנייה בזכות SNARKs
SNARKs מאפשרים ל- Prover להוכיח לאמת כי יש לו / הוא פיתרון W לבעיה F עם תשומות משותפות / ידועות X, מבלי לחשוף את W.
מציאת הפיתרון לבעיה עשויה לדרוש כמות עצומה של כוח חישוב וזיכרון.
אז ה- Verifier יכול בעצם להיות בטוח ב 100% כי ה- Prover עבד כראוי (ומצא פיתרון), בלי שאף אחד לא יבצע שוב את העבודה לבד כדי לבדוק את הפיתרון ולא לדעת בכלל את הפיתרון. זה קסם!
התהליך כולל 3 שלבים:
- להכין - הבעיה F (שצריך לבוא לידי ביטוי כתוכנית חשבון ריבועית, ראה להלן) מוכנה ל- SNARKs. תהליך זה הוא בעל זיכרון גבוה מאוד ואינטנסיבי מחשוב תלוי במורכבות הבעיה (→ מספר הכניסות והאילוצים → ממד המטריצה של בעיית שביעות רצון האילוצים). על כל השחקנים לסמוך על השחקן שעושה את ההתקנה (יכול להיות ה- Verifier עצמו), שכן הפלט של ההתקנה משמש בשלבים הבאים. ההתקנה מתבצעת בדרך כלל באמצעות ליבסנרק, ספריית C ++ שהיא היישום הפופולרי ביותר עבור zkSNARKs.
- הוכחה - הפרובר, שיש לו פיתרון W לבעיה F עם תשומות משותפות X (אולי היא / הוא בילה כמויות אדירות של מעבד וזיכרון כדי למצוא אותו!), משתמש ליבסנרק והתפוקה של ה- התקנה שלב ליצירת הוכחה 𝚷. תהליך זה הוא בהחלט זיכרון גבוה ואינטנסיבי מחשוב (תלוי במורכבות הבעיה, כאמור לעיל). גודל הפלט (כלומר הוכחה 𝚷) במקום תמציתי וקבוע באופן בלתי תלוי ממורכבות הבעיה. הפרובר צריך לסמוך על מי שעשה את שלב ההתקנה, מכיוון שהיא / הוא משתמש בתפוקה ...
- אימות - אימות - נותן כקלט את הפלט משלב ההתקנה, כניסות משותפות X והוכחה 𝚷 - בודק את ההוכחה. אם האימות מצליח, פרובר הצליח להוכיח למאמת שהוא / הוא מצא את הפיתרון W לבעיה F ... בלי לחשוף את W! החלק הנחמד הוא שלא רק ההוכחה תמציתית ותמיד יש אותה אורך .., תהליך האימות מהיר ולא אינטנסיבי בזיכרון / מחשוב. בשונה משני השלבים הקודמים ... ניתן לבצע את האימות בקלות באמצעות סמארטפון באלפיות השנייה!
סיכום טוב (מָקוֹר):
איך זה יכול לקרות? ובכן, זה קסם מרלין! אם אתה רוצה לקבל את המתמטיקה מאחורי זה, התחל מכאן.
כיצד אוכל להפוך את התוכנה שלי לתוכנית חשבון ריבועית?
כאמור לעיל, הבעיה F שלב ההתקנה צריכה להיות תוכנית חשבון ריבועית. כללי המשחק קשים:
- כניסות התוכנה שלך צריכות להיות מספרים. המר את החפצים שלך (מערכים, מחרוזות וכו ') למספרים. זה טריוויאלי.
- "מערכת משוואות מוגבלת באופן מרובע" פירושה:
כאשר x הוא הווקטור n ממדי של הכניסות שלך, m הוא מספר האילוצים (כלומר מספר המשוואות של המערכת שלך), C הוא המקדמים n-by-n מטריקס ו- q הוא וקטור מקדמי n ממדי. אם אינך אוהב מטריצה וקטורים, הנה המקרה n = 3 ו- m = 2 (3 כניסות, 2 אילוצים):
- היישום הוא מעגל חשבון, כלומר התוצאה היא הבעיה נפתרה (המערכת נפתרת, כלומר כל הפולינומים שווים ל- 0) או הבעיה לא נפתרה (כל המקרים האחרים). במילים אחרות: "תשומות אלה אינן אחד הפתרונות לבעיה זו".
- מקדמי C₁, C2393, ..., C𝚖, q₁, q5647, ..., q𝚖 הם האילוצים של המערכת. זה בעצם מה שמגדיר את התוכנה שלך. שנה אותם ... ותקבל תוכנה אחרת! לחזור לאופן העבודה של SNARK: C₁, C₂, ..., C𝚖, q₁, qXNUMX, ..., q𝚖 הם הקלט לשלב ההתקנה. הפלט של שלב ההתקנה (הדרוש לך לצורך הוכחה ואימות) קשור אפוא לאלה C₁, C₂, ..., C𝚖, q₁, q₂, ..., q𝚖 ועובד רק עבור אותה בעיה. אם תשנה אותם אתה מגדיר תוכנה / בעיה אחרת ועליך להפעיל מחדש את שלב ההתקנה! x₁, x₂, ..., x𝗇 הם המשתנים (כלומר, מה שאתה צריך לנחש כדי לקבל פיתרון של מערכת). אז כשאנו אומרים "פרובר היקר, האם תוכל בבקשה למצוא פיתרון סודי W לבעיה F עם תשומות משותפות / ציבוריות X", אנו מתכוונים למשל "פרובר היקר, האם תוכל למצוא את הערכים x₁, x₂, ..., x𝗇 אשר פותרים את המערכת עם, למשל, x₇ = XNUMX, x₅₂₆ = XNUMX? " אתה יכול לעשות מה שאתה רוצה עם כל ה- x𝗇, למעט x₇ ו- x₅₂₆, המוגבלים לתשומות המשותפות / הציבוריות.
אלה חיים קשים, אבל אתה יכול לשרוד ... אם אתה זקוק לולאות אתה יכול לפרש אותם חוזרים על אותה פעולה פעמים רבות. או אם אתה זקוק לדוגמא x₁⁴ x₂⁵, אתה מגדיר קלט חדש x₃ = x₁⁴ x₂⁵ ומשתמש ב- x₃ באילוצים שלך. הכל על הוספת משתנים ואילוצים ... אפילו עבור תוכנות פשוטות למדי קל להגיע למאות מיליונים או מיליארדי תשומות ואילוצים!
רוצים לדעת עוד? לקרוא כאן. וגם לבדוק את הבסיסי הזה code_to_r1cs.py מאתריה / מחקר.
מהו עץ מרקל?
פונקצית hash היא כלל הממפה קלט בגודל שרירותי לפלט בגודל קבוע. נוכל להמציא פונקציית חשיש די חסרת תועלת "לשרשר את השניים הראשונים עם שתי האותיות האחרונות" שהופכת את "וודי אלן" ל"וואן "ו"פול מקרטני" ל"פאי ".
עץ מרקל הוא מבנה נתונים בו כל הורה הוא החשיש של שני בניו. בחלקו העליון מוצאים את השורש, שהוא החשיש של שני הבנים ברמה 1. בתחתית כל עלה הוא החשיש של קלט חיצוני.
בעזרת פונקציית ה- Hash של "וודי אלן" → "וואן":
כאשר עלה משתנה, השינויים מופצים עד השורש. אם ANTHONY משתנה, גם ANNY (עלה), CENY ו- CECO (Root) משתנים. לא משנה מה עלה שישתנה, גם השורש ישתנה.
אינך זקוק לעץ כולו כדי לחשב מחדש את השורש. בדוגמה שלנו, אם ANTHONY משתנה ואתה מכיר גם JACO וגם CECILY, אתה יכול לחשב מחדש מחדש את השורש גם אם אתה מתעלם לחלוטין מ- JAMES, MARCO, JAES ו- MACO. עבור עצים ענקיים זה חוסך זמן רב!
אז מה?
עצי מרקל נהדרים לבדיקות תקינות נתונים. בדרך כלל: אתה יודע מהו השורש התקף, ובודק שהנתונים שהתקבלו תואמים את השורש. לדוגמה: גורם מהימן שלא יכול לתת לך את כל מערך הנתונים של השמות הפרטיים של אנשים בכדור הארץ (אין זמן, אין רוחב פס או אולי אין לו / הוא נתונים כלל) נותן לך רק את השורש (למשל "CECO"). מילות מפתח: אתה מקבל מיליוני שמות פרטיים, בהתייחס למספר העלים, על ידי אלפי גורמים לא אמינים. ובכן, מכיוון שיש לך את השורש הנכון אתה יכול לבדוק על מי אתה יכול לסמוך, מי נותן לך נתונים מזויפים ...
עצי מרקל הם גם חלק מחייך! כשאתה מוריד קובץ טורנט של 3 ג'יגה-בתים, הקובץ שלך מחולק במיליוני נתחים קטנים. החשיש של כל נתח מאוחסן בעלה. מכיוון שאתה יודע שהוא השורש התקף של העץ, בכל פעם שאתה מקבל נתח של הקובץ על ידי מישהו, אתה יכול לבדוק אם הוא נכון. אם זה לא, אתה יכול לשאול את אותו נתח למישהו אחר.
אתה יכול לעשות זאת גם אם עדיין לא הורדת את כל העץ / כל העלים: אם אתה יודע שהשורש הוא CECO ואתה סומך על JACO ... כשאתה מקבל את הנתח ANTHONY אתה יכול לאמת אותו גם אם לא הורדת. ובכל זאת הנתחים מרקו וג'יימס.
מדוע עצי מרקל מועילים בטכנולוגיית ספר-חשבונות מבוזר היא פשוטה: אתה משתמש בפרוטוקולי קונצנזוס (איטי, יקר) רק כדי להגיע להסכמה על השורש. אז הצמתים הבלתי מהימנים של הרשת יכולים לשתף נתונים ביעילות ובישירות ... ויכולים לישון בטוחים וקול בזכות בדיקות יושרה עם ה- Root.
כאשר אלוהים ביקש מ- Ethereum לבחור 2 מעצמות-על בין ביטחון, מדרגיות וביזור ... Ethereum הקריב את המדרגיות. למעשה אין מכסה חזק על "עסקאות בשנייה": המכסה נוגעת לכמות הגז של כל בלוק - כלומר, לפשט, את כמות הפעולות שאני יכול לבצע בכל בלוק. גבול זה הוא 8 מיליון דלק. פירוש הדבר יכול להיות הרבה עסקאות "קטנטנות" (אין נתונים המצורפים לעסקאות, אין פעולות שיש לבצע בנתונים אלה) או מעט עסקאות גדולות. זה תלוי בצמתים של Ethereum, שמגישים עסקאות, וכורים של Ethereum, הכוללים בבלוק את העסקאות שמשלמות יותר.
מכרה בלוק כל ~ 15 שניות. המשמעות היא ~ 32 מיליון דלק לדקה, וזה בהחלט לא מספיק אם אנחנו רוצים שהמטפלים של אתרום ילכו למיינסטרים.
אגב: תפסיק עם ההשוואה המייגעת ההיא בין אתרום לוויזה. מערכת ריכוזית תמיד להיות מהיר יותר מ- Ethereum ... על ידי עיצוב! הם עושים דברים שונים ואתה זקוק להם במצבים שונים. אם אינך זקוק לביזור וסביבה חסרת אמון ... כמובן שעליך לבחור בויזה. בקצרה: העובדה שהבלנדר שלך מסתובב מהר יותר ממכונת הכביסה שלך לא אומר שתנקה את המכנסיים בבלנדר!
בואו נרכיב את הפאזל! תאר לעצמך שאתה יכול "לדחוס" הרבה עסקאות קטנטנות בעסקה אחת גדולה בזכות SNARKs. אם הגז שהוצא על ידי עסקה גדולה זו הוא פחות מסכום הדלק שהוצא בעסקאות הזעירות, זה אומר שאתה חוסך דלק.
וחיסכון בגז פירושו:
- משתמשים שמבלים פחות על עסקאות בסך הכל → זה יהיה דחף לכל המערכת האקולוגית
- היכולת להכניס עוד דברים לחסום → אתרום מסתובב מהר יותר מהבלנדר שלך!
איך זה עובד?
ישנם משתמשים, ממסר (או יותר ממסרים) שמאגד עסקאות וחוזה חכם.
- משתמשים שמוכנים לשחק במשחק הזה שולחים את ה- Ether (או אסימונים) שלהם לחוזה חכם מבוקר. עבור כל שחקן חדש נוצר עלה חדש בעץ מרקל. העלה כולל מידע על הבעלים של האתר (הכתובת שלו, שהיא גם המפתח הציבורי), כמות האתרים וההנפקות (מונה העסקאות של אותו חשבון, שהוא 0 כאשר הוספת העלה)
- כאשר A רוצה לשלוח את אתר ל- B (לשניהם צריך להיות בעל / חשבון בחוזה החכם), A אורז עסקה, הכוללת את הכתובת של החל מ-חשבון, ל חשבון, שליח מהחשבון, כמות של אתר שיועבר וה חֲתִימָה של העסקה (שנחתם עם המפתח הפרטי של החשבון "מן", ברור). לאחר מכן היא / הוא שולח את העסקה המלאה למעביר.
- המשדר מצטבר את כל העסקאות שהתקבלו בחלון זמן נתון (למשל שעה), מעדכן את עץ המרקל בסכומי היתרות החדשות ויוצר הוכחת SNARK שמוכיחה שכל החתימות ושורש עץ המרקל החדשים תקפים. המסר שולח לבסוף את המדינה החדשה ואת ההוכחה לחוזה החכם.
- החוזה החכם מאמת את ההוכחה ברשת. אם הוא תקף, הוא שומר את שורש העץ מרקל של המדינה החדשה בזיכרון הפנימי של החוזה.
בעיקרון, שורש העץ מרקל מתאר את כל מצבם של כל החשבונות. ואתה לא יכול לשנות את זה (= לגנוב כסף) אלא אם כן אתה יכול להוכיח את תקפותן של החתימות שעסקאותיהן מובילות למדינה החדשה המסוכמת על ידי השורש החדש שאתה מגיש.
על קצה המזלג: למשתמשים יש עסקאות סופר מהירות וכמעט חינמיות, כמו ב- Coinbase, מבלי להזדקק לסמוך על הממסר, שלא יכול לעשות דבר, שלא כמו ב- Coinbase, ללא חתימתך.
זו שרשרת צדדית לא משמורת שמדינה מסכמת על ידי שורש עץ מרקל.
בואו נקשר את מה שלמדנו לעיל על SNARKs עם מה שדיברנו זה עתה על קנה המידה. ישנן דרכים שונות לעשות זאת. אשווה 2 מתכונים: ויטליק גרסה ו- barryWhiteHat's גרסה.
ההגדרה נעשית על ידי ...
הבחור שמתחיל את הפרויקט, שיוצר גם את החוזה החכם. ככל שהוא נשמע יותר טוב, עליכם לסמוך עליו / זה… זה א הגדרה מהימנה!
החוזה החכם חוסך ...
2 שורשי מרקל (ערכים של בתים 32): העץ הראשון מכיל כתובות של חשבונות (חתימות פומביות), יתרות החשבונות השניים והיתרים
ההוכחה מתבצעת על ידי ...
ממסר
המסר שולח לחוזה החכם ...
- שני שורשי המרקלה של המדינה החדשה (פונה לעץ ומאזן + עץ nonces)
- רשימת העסקאות, ללא חתימות. "כל עסקה עולה 68 גז לבתים. לפיכך, עבור העברה רגילה, אנו יכולים לצפות שהעלות השולית תהיה 68 * 3 (מ-) + 68 * 3 (ל) + 68 * 1 (בתשלום) + 68 * 4 + 4 * 2 (סכום) + 68 * 2 (nonce), או 892 גז ”
התשומות הידועות של התהליך הן ...
- 2 שורשי המדינה העתיקה של מרקל
- 2 שורשי המדינה החדשה של מרקל
- רשימת עסקאות
תהליך ההוכחה מוכיח ש ...
נתתי
- שני שורשי מרקל של המדינה הישנה (שכבר נשמרו בחוזה)
- 2 שורשי המדינה החדשה של מרקל (נשלחו בעסקת הכניסה הגדולה)
- רשימת העסקאות (נשלחה בעסקה הגדולה)
... למעביר יש חתימות תקפות לעבור ממדינה עם 2 שורשים ישנים למדינה עם 2 שורשים חדשים עם אותן עסקאות.
האימות מתבצע על ידי ...
החוזה החכם (מקודד בסולידיות, וויפר, כמו שאתה רוצה!)
הכניסות הידועות של תהליך האימות הן ...
התהליך של אותו PROVING ידוע בתשומות, ברור ...!
גבולות למדרגיות
כל עסקה מצטברת משתמשת בגז של 650k לצורך אימות SNARK (עלות קבועה) בתוספת ~ 900 דלק של עלות שולית לכל עסקה (עולה משלוח נתונים!). לכן באמצעות החסימה כולה הממסר יכול לצבור לכל היותר:
אשר אומר ~ 544 טקס לשנייה
barryWhiteHat's גרסה
ההגדרה נעשית על ידי ...
הבחור שמתחיל את הפרויקט.
החוזה החכם חוסך ...
1 שורש מרקל עם המדינה הנוכחית. כל עלה הוא המצב המהולל של חשבון.
רוצה לִיצוֹר חשבון?
state = AccountState (pubkey, יתרה, nonce)
state.index = self._tree.append (state.hash ())
ההוכחה מתבצעת על ידי ...
ממסר
המסר שולח לחוזה החכם ...
- הוכחה 𝚷
- שורש המדינה החדשה של מרקל
- הוכחה 𝚷
התשומות הידועות של התהליך הן ...
- שורש מרקל של המדינה הישנה
- שורש המדינה החדשה של מרקל
תהליך ההוכחה מוכיח ש ...
נתתי
- שורש המרקל הישן (שכבר נשמר בחוזה)
- שורש המרקלה החדש (סנטי בעסקה הגדולה)
... למעביר יש רשימת עסקאות עם חתימות תקפות לעבור ממדינה עם שורש ישן למדינה עם שורש חדש
האימות מתבצע על ידי ...
החוזה החכם (מקודד בסולידיות, וויפר, כמו שאתה רוצה!)
הכניסות הידועות של תהליך האימות הן ...
התהליך של אותו PROVING ידוע בתשומות, ברור ...!
גבולות למדרגיות
המעביר אינו שולח נתוני עסקאות לחוזה החכם (וזה יקר), כך שהמגבלה היא למעשה כמות הדלק לאימות הוכחת SNARK.
מזכיר את זה של האוורד וו לעבוד על הפעלת שלב ההוכחה של SNARK במערכות מבוזרות, barryWhiteHat באופטימיות קובע כי ניתן לאשר 16666 עסקאות ב SNARK ענק (מיליארד אילוצים!).
barryWhiteHat גם חושב אפשר לאמת הוכחה 𝚷 על גבי שרשרת עם 500k גז, מה שאומר שאתה יכול לשים 16 SNARKs (8 מיליון / 500k) לכל בלוק, שהוא ~ 1.07 SNARKs לשניות ... מה שאומר ~ 17,832 טקס לשנייה (16,666 * 1.07).
לנצח ומעבר
- כל מה שמנצנץ זה לא זהב / 1. כמות כוח המחשוב והזיכרון הדרושים לך בשלב ההוכחה יכולה להיות ממש מזעזעת. במיוחד בגרסת barryWhiteHat, שבה חלק מהמורכבות מועברת מחוץ לשרשרת. בארי כותב "במחשב נייד עם 7 GB זיכרון RAM ו 20 GB שטח החלפה הוא נאבק לצבור 20 עסקאות בשנייה". ובכן, אם המטרה היא 17,832 טקס לשנייה… LOL. זה מציג אתגרי חישוב מקבילים לא טריוויאליים. אבל אם העלות הממוצעת של $ לכל עסקה היא הרבה יותר זולה מהאפשרות הרגילה ללא SNARKs ... המשחק שווה את הנר.
- כל מה שמנצנץ זה לא זהב / 2. יש סוגיית רלוונטיות לזמינות נתונים! מכיוון שרק שורש העץ נשמר בחוזה, עליכם להיות בטוחים כי גרסה שלמה של העץ (או, זה אותו דבר, כל היסטוריית העסקאות) זמינה תמיד. אם אין נתונים זמינים, המעבר, אפילו עם עסקאות חתומות תקפות, אינו יכול לעשות דבר מכיוון שהיא / הוא לא יכול להוכיח מדינה ישנה → עסקאות → מדינה חדשה.
- על מנת שהממסר יהיה חסר אמון ולאתרס בחוזה יהיה אותו ערך של אתר בחוץ (בעיית נזילות)… המשתמשים צריכים להיות מסוגלים למשוך כסף מהחוזה החכם כשהם רוצים, מבלי להסתמך על ממסר (ספציפי). איך? זה לא נמצא במסגרת פוסט זה 101, אבל אתה יכול לקרוא על זה בקישורים המצורפים.
- רוצה להבין יותר כיצד ניתן לטפל במדינה הנוכחית (כתובות, יתרות וחריגים) באמצעות עץ מרקל? הוספת עלה, עדכון עלה וכו '? לבדוק הספרייה הזו (קובץ מבחן כאן) המשתמש בבסיס זה מודול. תודה HarryR!
- רוצה להגדיר את סביבת Ethereum-SNARK האישית שלך? נתחיל מהשרשרת עם C ++ (התקנה, הוכחה, אימות) כאן. אז אתה יכול לעבור ל- Ethereum (אל תשכח, רק האימות מתבצע ברשת!) עם זוקרטס (הריפו, ה תיעוד שאפשר להתחיל איתו).
- מה דעתך להשתמש במצברי RSA במקום בעצי מרקל? גוגל "אתתרום מצברי rsa" להתחיל…
תהנו!
טויטר @marco_derossi
- 7
- חֶשְׁבּוֹן
- תעשיות
- בין
- זמינות
- יסודות
- B
- מקרים
- שינוי
- בדיקות
- coinbase
- מחשוב
- קונסנסוס
- חוזה
- עלויות
- נוֹכְחִי
- מצב נוכחי
- DAPs
- נתונים
- מערך נתונים
- ביזור
- מֵמַד
- ספר חשבונות מבוזר
- טכנולוגיה מבוזרת
- סביבה
- אתר
- ethereum
- EU
- EV
- מְזוּיָף
- בסופו של דבר
- ראשון
- חופשי
- פונקציה
- מִשְׂחָק
- גז
- GitHub
- נתינה
- זהב
- טוב
- גדול
- מדריך
- שירים
- כאן
- גָבוֹהַ
- היסטוריה
- איך
- hr
- HTTPS
- עצום
- מאות
- ia
- מדד
- מידע
- IP
- IT
- עבודה
- מפתח
- מחשב נייד
- גָדוֹל
- עוֹפֶרֶת
- פנקס
- רמה
- LG
- סִפְרִיָה
- נְזִילוּת
- רשימה
- זרם מרכזי
- מפות
- בינוני
- מִילִיוֹן
- כורים
- כסף
- חודשים
- הכי פופולארי
- המהלך
- שמות
- רשת
- צמתים
- מספרים
- תפעול
- להזמין
- אחר
- בעלים
- תשלום
- אֲנָשִׁים
- שחקן
- פופולרי
- כּוֹחַ
- פְּרָטִי
- מפתח פרטי
- תָכְנִית
- פּרוֹיֶקט
- הוכחה
- מוכיח
- ציבורי
- מפתח ציבורי
- לסכם
- RSA
- כללי
- ריצה
- בטוח
- חסכת
- בקרת מערכות ותקשורת
- סולם
- דרוג
- מדע
- אבטחה
- סט
- שיתוף
- משותף
- קצר
- פָּשׁוּט
- מידה
- לִישׁוֹן
- חכם
- חוזה חכם
- טלפון חכם
- So
- תוכנה
- מוּצָקוּת
- פתרונות
- לפתור
- מֶרחָב
- הוצאה
- התחלה
- החל
- מדינה
- הברית
- מוצלח
- מערכת
- מערכות
- טכנולוגיה
- מבחן
- זמן
- מטבעות
- חלק עליון
- Torrent
- עסקה
- עסקות
- סומך
- עדכונים
- משתמשים
- ערך
- אימות
- F-XNUMX
- W
- מי
- מילים
- תיק עבודות
- עובד
- ראוי
- X