מכרות

מה זה עץ Merkle

עצים Merkle הם חלק מהותי של מה עושה blockchains לתקתק. למרות שזה בהחלט תיאורטית אפשר לעשות blockchain ללא עצים Merkle, פשוט על ידי יצירת כותרות בלוק ענק המכילים ישירות כל עסקה, עושה את זה מציב אתגרים מדרגיים גדולים, כי ניתן לשים את היכולת להשתמש חסרי תועלת blockchains מחוץ להישג ידם של כל אבל הכי הרבה מחשבים רבי עוצמה בטווח הארוך.

הודות לעצי Merkle, ניתן לבנות צמתים של Ethereum הפועלים על כל המחשבים והמחשבים הניידים הגדולים, הקטנים, הטלפונים החכמים ואפילו האינטרנט של התקני דברים כגון אלה שיוצרו על ידי Slock. זה. אז איך בדיוק עובדים אלה עצים לעבוד, ומה הערך שהם מספקים, גם עכשיו וגם בעתיד?

ראשון , את היסודות. עץ במרקל, במובן הכללי ביותר, הוא דרך להפיג מספר רב של נתחי נתונים, אשר מסתמך על פיצול הגושים לדליים, כאשר כל דלי מכיל רק כמה גושים, ואז לוקח את החשיש של כל דלי וחוזר על עצמו אותו תהליך, להמשיך לעשות זאת עד המספר הכולל של hashes הנותרים הופך רק אחד: חשיש השורש.

הצורה הנפוצה והפשוטה ביותר של עץ Merkle היא עץ המקלה הבינרי, שבו דלי מורכב תמיד משני חלקים או hashes סמוכים; זה יכול להיות מתואר כדלקמן:

אז מה היתרון של אלגוריתם hashing מוזר זה? למה לא רק לשרשר את כל chunks יחד לתוך נתח גדול אחד ולהשתמש באלגוריתם hashing קבוע על זה? התשובה היא כי הוא מאפשר מנגנון מסודר המכונה הוכחות Merkle:

הוכחה Merkle מורכב גוש, חשיש השורש של העץ, ואת "ענף" המורכב של כל hashes הולך לאורך השביל מ נתח השורש. מישהו קורא את ההוכחה יכול לוודא כי hashing, לפחות עבור אותו סניף, הוא עקבי הולך כל הדרך במעלה העץ, ולכן נתח נתון למעשה הוא במיקום זה בעץ.

היישום פשוט: נניח שיש מסד נתונים גדול, וכי כל התוכן של המאגר מאוחסנים בעץ Merkle שבו שורש עץ Merclle ידוע ומפורסם (לדוגמה, הוא חתום דיגיטלית על ידי מספיק צדדים מהימנים, או שיש הרבה הוכחות לעבודה). לאחר מכן, משתמש המעוניין לבצע בדיקת ערך מפתח במסד הנתונים (לדוגמה."תגיד לי את האובייקט במצב 85273") יכול לבקש הוכחה מרקל, ועם קבלת ההוכחה לוודא שזה נכון, ולכן הערך שהתקבל למעשה הוא במקום 85273 במסד הנתונים עם זה שורש מסוים.

הוא מאפשר מנגנון לאימות קטן כמות נתונים, כמו חשיש, כדי להרחיב גם לאמת גדול מסדי נתונים של גודל פוטנציאלי בלתי מוגבל.

<9>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> בלוק:

היתרון זה מספק את הרעיון כי סטושי תיאר כמו "אימות תשלום פשוט": במקום להוריד

כל עסקה

וכל בלוק, "לקוח אור" יכול רק להוריד את השרשרת של כותרות בלוק , נתחי נתונים של 80 סיביות עבור כל בלוק המכילים חמישה דברים בלבד: חשיש של הכותרת הקודמת חותמת זמן

  • ערך קושי של הכרייה
  • הוכחה של
  • חשיש שורש עבור עץ Merkle המכיל את העסקאות עבור אותו בלוק.
  • אם הלקוח האור רוצה לקבוע את הסטטוס של עסקה, זה יכול פשוט לבקש הוכחה Merkle מראה כי עסקה מסוימת היא באחד העצים Merkle אשר השורש הוא כותרת בלוק עבור הרשת הראשי.
  • זה מקבל אותנו די רחוק, אבל לקוחות בייקון בסגנון אור יש מגבלות שלהם. מגבלה אחת היא כי, בעוד הם יכולים להוכיח הכללת עסקאות, הם לא יכולים להוכיח שום דבר על המצב הנוכחי (למשל, החזקת הנכס הדיגיטלי, רישומים שם, מעמד של חוזים פיננסיים, וכו '). כמה bitcoins יש לך עכשיו?

לקוח אור Bitcoin יכול להשתמש בפרוטוקול של שאילתת צמתים מרובים ובטוח כי לפחות אחד מהם יודיע לך על כל הוצאה מסוימת של עסקה מהכתובות שלך, וזה יביא אותך רחוק למדי עבור מקרה שימוש זה, אבל עבור אחרים יישומים מורכבים יותר זה לא מספיק; האופי המדויק של ההשפעה של עסקה יכול להיות תלוי ההשפעה של מספר עסקאות קודמות, אשר תלויים בעצמם עסקאות קודמות, ולכן בסופו של דבר היית צריך לאמת כל עסקה אחת בכל הרשת. כדי לעקוף את זה, Ethereum לוקח את הרעיון עץ Merkle צעד אחד קדימה.

Merkle Proofs in Ethereum

כל כותרת בלוק של Ethereum מכילה לא רק עץ אחד של מרקל, אלא

שלושה

עצים עבור שלושה סוגים של אובייקטים: עסקאות תקבולים (בעיקר, (999)>

  • מצב זה מאפשר פרוטוקול אור מתקדם מאוד המאפשר ללקוחות אור לבצע בקלות ולקבל תשובות ניתנות לאימות לשאילתות רבות: האם עסקה זו נכללה בבלוק מסוים? ספר לי את כל המופעים של אירוע מסוג X (לדוגמה, חוזה גיוס קהל שמגיע למטרה שלו) הנפלטים מכתובת זו ב -30 הימים האחרונים
  • מהו היתרה הנוכחית בחשבוני?

האם חשבון זה קיים?

  • להעמיד פנים להפעיל את העסקה על חוזה זה. מה יהיה הפלט?
  • הראשון מטופל על ידי עץ העסקה; השלישי והרביעי מטופלים על ידי עץ המדינה, והשני על ידי עץ הקבלה. ארבעת הראשונים הם פשוט למדי לחשב; השרת פשוט מוצא את האובייקט, מביא את הסניף Merkle (רשימת hashes הולך מן האובייקט אל שורש העץ) ואת התשובות בחזרה ללקוח אור עם הסניף.
  • החמישי מטופל גם על ידי עץ המדינה, אבל האופן שבו הוא מחושב מורכב יותר. כאן, אנחנו צריכים לבנות מה יכול להיקרא
  • Merkle המדינה הוכחה מעבר
  • . בעיקרו של דבר, זוהי הוכחה אשר להפוך את הטענה: אם אתה מפעיל את העסקה

T

על המדינה עם שורש S , התוצאה תהיה מצב עם שורש S '> עם L ו פלט O ("פלט" קיים כמושג ב Ethereum כי כל עסקה היא קריאה פונקציה, זה לא הכרחי תיאורטית). כדי לחשב את ההוכחה, השרת יוצר באופן מקומי בלוק מזויף, קובע את המצב ל- S, ומעמיד פנים שהוא לקוח קל בעת החלת העסקה. כלומר, אם תהליך החלת העסקה מחייב את הלקוח לקבוע את היתרה בחשבון, הלקוח הקל עושה שאילתת איזון. אם הלקוח האור צריך לבדוק פריט מסוים באחסון של חוזה מסוים, הלקוח האור עושה שאילתה על כך, וכן הלאה. השרת "מגיב" לכל השאלות שלו נכון, אבל עוקב אחר כל הנתונים שהוא שולח בחזרה. השרת שולח ללקוח את הנתונים המשולבים מכל הבקשות האלה כהוכחה. הלקוח מתחייב באותו אופן, אך משתמש בהוכחה המוצגת כמסד הנתונים שלו

; אם התוצאה שלו זהה למה שהשרת טוען, אז הלקוח מקבל את ההוכחה.

פטרישיה עצים

זה היה שהוזכר לעיל כי הפשוטה סוג של עץ Merkle הוא עץ בינרי Merkle; עם זאת, העצים המשמשים Ethereum מורכבים יותר. זהו "Merkle Patricia עץ" כי אתה שומע על התיעוד שלנו. מאמר זה לא ילך מפרט מפורט; כי הוא עשה את הטוב ביותר על ידי מאמר זה ואת זה, אם כי אני אדון את ההיגיון הבסיסי. עצים בינריים Merkle הם מבנים נתונים טובים מאוד לאימות מידע כי הוא בפורמט "רשימה"; למעשה, שורה של גושים אחד אחרי השני. עבור עצי העסקה, הם גם טובים, כי זה לא משנה כמה זמן לוקח עד

לערוך

עץ פעם הוא נוצר, כמו העץ נוצר פעם אחת ואז קפוא תמיד מוצק.

עבור עץ המדינה, עם זאת, המצב מורכב יותר. המדינה ב- Ethereum מורכבת למעשה ממפת מפתח-ערך, כאשר המקשים הם כתובות והערכים הם הצהרות חשבון, המפרטות את האיזון, את הקוד, ואת האחסון עבור כל חשבון (כאשר האחסון עצמו הוא עץ). לדוגמה, מצב ה- genesis של Morden testnet נראה כדלקמן:

{"00000000000000000000000000000000000001": "" "", "00000000000000000000000000000000000000000000000000000000000":: "" "" "" "," 0000000000000000000000000000000000000003 ": { איזון ":" 1 "," 0000000000000000000000000000000000000004 ":" "" "", "102e61f5d8f9bc71d0ad4a084df4e65e05ce0e1c": "160693804425279941962092341162602522202993782792835301376"}} בניגוד להיסטוריית העסקאות, המדינה צריכה להיות המתעדכנים לעתים קרובות: לעתים קרובות משתנים המאזן וחוסר החשבונות, וחשבונות חדשים מוכנסים לעתים קרובות, ומפתחות אחסון מאוחסנים לעתים קרובות ונמחקים.מה הוא הרצוי לכן הוא מבנה נתונים שבו אנו יכולים לחשב במהירות את השורש עץ חדש לאחר הוספה, עדכון לערוך או למחוק פעולה, ללא recomputing את העץ כולו. יש גם שני מאפיינים משניים מבוקשים ביותר: עומק העץ הוא מוגבל, אפילו נתון תוקף כי בכוונה לעצב עסקאות כדי להפוך את העץ עמוק ככל האפשר. אחרת, תוקף יכול לבצע התקפת מניעת שירות על ידי מניפולציה של העץ כדי להיות כה עמוקה שכל עדכון בודד הופך לאיטי ביותר.

שורש העץ תלוי רק בנתונים, לא בסדר שבו מתבצעים עדכונים. ביצוע עדכונים בסדר שונה ואפילו recomputing העץ מאפס לא צריך לשנות את השורש.

עץ Patricia, במונחים פשוטים, הוא אולי הקרוב ביותר שאנחנו יכולים להגיע להשגת כל המאפיינים האלה בו זמנית. ההסבר הפשוט ביותר איך זה עובד הוא כי המפתח שבו ערך מאוחסן הוא מקודד לתוך "נתיב" כי אתה צריך לקחת את העץ. לכל צומת יש 16 ילדים, ולכן הנתיב נקבע על ידי קידוד hex: לדוגמה, המפתח

כלב

  • hex מוצפן הוא
  • 6 4 6 15 6 7

, כך שתתחיל עם השורש , לרדת הילד השישי, אחר כך הרביעי, וכן הלאה עד שתגיע לסוף. בפועל, יש כמה אופטימיזציות נוספות שאנחנו יכולים לעשות כדי להפוך את התהליך הרבה יותר יעיל כאשר העץ הוא דליל, אבל זה העיקרון הבסיסי. שני המאמרים שהוזכרו לעיל מתארים את כל התכונות בפירוט רב יותר.