עץ מרקל הוא מבנה נתונים המשמש ביישומים למדעי המחשב. בעובי ביטקוין ובקריפטו-מטבעות אחרים, עצי מרקל משמשים לקידוד נתונים blockchain בצורה יעילה ובטוחה יותר.
הם מכונים גם "עצי חשיש בינאריים".
פירוק עץ מרקל
ב- blockchain של bitcoin, בלוק של עסקאות מופעל באמצעות אלגוריתם כדי ליצור hash, שהוא מחרוזת של מספרים ואותיות שניתן להשתמש בהם כדי לוודא שקבוצת נתונים נתונה זהה לקבוצת העסקאות המקורית, אך לא להשיג את מערך העסקאות המקורי. התוכנה של ביטקוין אינה מריצה את כל גוש נתוני העסקאות - המייצגים עסקאות בשווי של 10 דקות בממוצע - באמצעות פונקציית ה- hash בכל פעם. במקום זאת, כל עסקה מנוהלת, ואז כל זוג עסקאות משורשר ומנוכר יחד, וכן הלאה עד שיש חשיש אחד לכל החסימה. (אם יש מספר אי-זוגי של עסקאות, עסקה אחת מוכפלת וה- hash שלה משורשר לעצמו.)
דמיינו, מבנה זה דומה לעץ. בתרשים להלן "T" מייעד עסקה, "H" חשיש. שימו לב שהתמונה מפושטת מאוד; בלוק ממוצע מכיל מעל 500 עסקאות ולא שמונה.
החשיש בשורה התחתונה מכונה "עלים", חשיש הביניים כ"ענפים ", והחשיש בחלקו העליון כ"שורש". השורש של מרקל של בלוק נתון מאוחסן בכותרת: לדוגמה, שורש ה- Merkle של הבלוק # 482819 הוא e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f71c8. השורש משולב עם מידע אחר (גרסת התוכנה, חשיש החסימה הקודם, חותמת הזמן, יעד הקושי והנושא) ואז רצים דרך פונקציית hash כדי לייצר את ה- hash הייחודי של הבלוק: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b089594 במקרה של block # 48. חשיש זה אינו נכלל למעשה בבלוק הרלוונטי, אלא זה הבא; זה נבדל משורש מרקל.
עץ מרקל שימושי מכיוון שהוא מאפשר למשתמשים לאמת עסקה ספציפית מבלי להוריד את כל ה- blockchain (מעל 130 ג'יגה-בייט בסוף אוגוסט 2017). לדוגמה, נניח שרצית לוודא שעסקה T D כלולה בלוק בתרשים לעיל. אם יש לך את חשיש השורש (H ABCDEFGH), התהליך הוא כמו משחק סודוקו: אתה שואל את הרשת לגבי H D, והוא מחזיר את H C, H AB ו- H EFGH. עץ מרקל מאפשר לך לוודא שהכל אחראי לשלושה חשיש: בהינתן H AB, H C, H EFGH, והשורש H ABCDEFGH, H D (החשיש החסר היחיד) צריך להיות נוכח בנתונים.
עצי מרקל נקראים על שם ראלף מרקל, שהציע אותם במאמר משנת 1987 שכותרתו "חתימה דיגיטלית המבוססת על פונקציית הצפנה קונבנציונאלית." מרקל המציאה גם חשיפה קריפטוגרפית.
