עץ מרקל

בקריפטוגרפיה ומדעי המחשב, עץ מרקל (Merkle tree) הוא עץ גיבוב בינארי שבו כל קודקוד מסומן בערך גיבוב של שני בניו (או ערכי העלים) והוא סוג של טבלת גיבוב בצורת רשימה היררכית. כלומר, קיים קשר בין ערכי כל הצמתים החל מהעלים ועד לשורש העץ. עץ מרקל פותח על ידי רלף מרקל ב-1979^[1].

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

שימושים

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

תרשים לדוגמה של עץ מרקל בגובה

H=3

ביישומים מעשיים אפשר למצוא את עץ מרקל במערכות בהן צריך לוודא שבלוק מידע שהתקבל ברשת תקשורת או אוחזר מאמצעי אחסון, לא ניזוק או שונה אם בגלל תקלת תקשורת, פגם במדיית האחסון, השחתת זיכרון או חבלה זדונית. לתכונה זו חשיבות בעיקר במערכות קבצים, שיתוף מבוזר, עמית לעמית, מסדי נתונים וחישוביות מאובטחת. דוגמאות מעשיות בהן משתמשים בעץ מרקל שברובן קוד פתוח, כוללות את מערכות הקבצים IPFS^[2],^[3]ZFS, גנוטלה, פרוטוקול ביטורנט, פרוטוקול ופלטפורמת מחשוב Apache Wave^[4] של גוגל, גיט^[5], ביטקוין^[6], DynamoDB^[7] של אמזון ועוד.

עץ אימות של מרקל

עץ האימות של מרקל^[8] נועד בתחילה לשיפור חתימת למפורט. הרעיון הוא להשתמש בעץ בינארי מושלם שעליו מייצגים חתימות חד-פעמיות. כל עלה משמש לחתימה על מסמך אחד ואילו אימות כל החתימות נעשה על ידי שורש העץ. עץ האימות יכול לעבוד עם כל פונקציית גיבוב וכל סכמת חתימה דיגיטלית חד-פעמית (בקיצור OTS) כמו חתימת למפורט או חתימת וינטרניץ. הוכח שעץ מרקל נקרא בטוח תחת CMA (התקפת מסר-נבחר) כל עוד פונקציית הגיבוב שבה משתמשים חסינה מפני התנגשויות ופונקציית החתימה שבבסיסו בטוחה גם היא תחת מודל התקפת מסר-נבחר.

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

תיאור עץ מרקל בסיסי:

החותם בוחר שלם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H\ge 2} המייצג את גובה העץ כך שיתאים לחתימה על לכל היותר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^H} מסמכים. זאת בניגוד לסכמות חתימה דיגיטלית אחרות כמו DSA שתאורטית אינן מוגבלות במספר המסמכים עליהם אפשר לחתום.
החותם מכין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^H} זוגות של מפתחות; מפתח חתימה/מפתח אימות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (X_i,Y_i)} בהתאמה כאשר הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle 0\leq i<2^{H}} . הכנת המפתחות מתבצעת על ידי בחירת מחרוזת אקראית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i} ואז חישוב הפונקציה החד כיוונית שלה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y_i} המשמשת כמפתח ציבורי.
מכין את עלי העץ שערכם הוא הגיבוב של המפתחות הציבוריים. אם נתונה פונקציית גיבוב מוסכמת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} ערכו של כל עלה יהיה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(Y_i)} כאשר הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle 0\leq i<2^{H}} .
קודקודי העץ הפנימיים מחושבים לפי הכלל הבא: צומת אב מכיל את ערך הגיבוב של שרשור ערכי שני הצמתים (או עלים) הבנים, השמאלי והימני. אם נסמן צומת ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu_h[i]} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle h\in\{0,...,H\}} מייצג את גובה הצומת ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} הוא ערך בין 0 ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{H-h}} המייצג את מספר העלה או הצומת בגובה $h$ , אז ערכו של כל צומת בניסוח רשמי הוא:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu_h[i]=g(\nu_{h-1}[2i]\ \| \ \nu_{h-1}[2i+1]), \ \ 1\le h\le H, 0\le i<2^{H-h}} .

כאשר הסימן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \|} מייצג שרשור.

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

אלגוריתם עץ גיבוב

סדר הבנייה של הצמתים בעץ מרקל עם האלגוריתם המתואר, עבור עץ בגובה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H=3} .

קלט: גובה העץ הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H}

פלט: שורש עץ הגיבוב

R

, דהיינו המפתח הציבורי.

1. עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=0} עד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{H}-1} בצע:

א. חשב את העלה ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} . הצב: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Node}1=\text{CreateLeaf}(i)} .

ב. כל עוד גובהו של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Node1}} שווה לגובה הצומת בראש המחסנית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Stack}} .

1. בצע שליפה: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Node}2=\text{Stack}.\text{Pop}()} .

2. חשב את צומת האב: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Node}1=g(\text{Node}2\ \| \ \text{Node}1)} .

ג. בצע דחיפה: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Stack}.\text{Push}(\text{Node}1)} .

2. שלוף את השורש: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R=\text{Stack}.\text{Pop}()} .

3. החזר את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} .

האלגוריתם נעזר בתת-שגרה הנקראת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{CreateLeaf}} שמייצרת עם הפונקציה החד-כיוונית את זוג המפתחות הבא (מפתח פרטי/מפתח ציבורי) וכן מבצעת גיבוב של המפתח הציבורי אותו היא מחזירה כעלה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Node1}} . בתרשים משמאל מתואר סדר בניית הצמתים של האלגוריתם. בכל שלב של האלגוריתם נמצאים במחסנית לכל היותר $H$ צמתים והוא מבצע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^H} קריאות לתת-שגרה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{CreateLeaf}} בנוסף ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^H-1} הפעלות של פונקציית הגיבוב.

תהליך החתימה

דוגמה לחתימה על מסמך הרביעי בעץ מרקל בגובה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H=3} . החתימה

\sigma _{s}

כוללת את האינדקס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s=3} , מפתח האימות הציבורי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y_3} , החתימה החד-פעמית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma=\text{OTS}_{X_3}(d)} עם מפתח החתימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_3} והצמתים

A_{3}=(a_{0},a_{1},a_{2})=(\nu _{0}[2],\nu _{1}[0],\nu _{2}[1])

שהם הצמתים האחים של הצמתים במסלול מהעלה הרביעי לשורש העץ.

תחילה החותם מכין מהמסמך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} את התמצית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d=g(D)} (אותה אפשר לקבל באמצעות פונקציית גיבוב כמו SHA-2) ואז מכין את החתימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma_s} עם מפתח החתימה הסודי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_s} . כאשר הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle 0\leq s\leq 2^{H}-1} מייצג את אינדקס החתימה הפנויה בעץ. כזכור העץ מכיל חתימות חד-פעמיות לכן צריך אינדקס כדי להבטיח שלא יהיה שימוש כפול בחתימה. בנוסף, החותם חייב לשלוח יחד עם החתימה גם את מפתח האימות הציבורי המתאים למסמך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} כי המקבל מחזיק רק בשורש העץ כמפתח אימות.

החותם צריך לכלול בחתימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma_s} את הערכים הבאים:

האינדקס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} המייצג את מספרה הסידורי של החתימה בעץ.
החתימה החד-פעמית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma} על תמצית המסמך לפי אלגוריתם החתימה החד-פעמית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{OTS}} שנעשתה עם מפתח החתימה הפרטי $X_{s}$ .
מפתח האימות הציבורי המתאים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y_s} .
"מסלול אימות" שהוא הרצף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_s=(a_0,...,a_{H-1})} הכולל רשימה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} צמתים בעץ איתם המאמת ישתמש כדי לשחזר את המסלול מהעלה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(Y_s)} לשורש העץ הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} כדי לאמת את מפתח החתימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y_s} . היות שחישוב כל צומת דורש את שני הצמתים הבנים, כל צומת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_j} במסלול האימות הוא למעשה צומת האח של הצומת הנוכחי בגובה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle h} לאורך המסלול מהעלה לשורש כך שמתקיים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_h=\begin{cases} \nu_h[s/2^h-1], & \mbox{if }\lfloor s/2^h\rfloor\equiv 1\text{ mod }2 \\ \nu_h[s/2^h+1], & \mbox{if }\lfloor s/2^h\rfloor\equiv 0\text{ mod }2 \end{cases}}

במילים אחרות, במהלך התנועה במעלה העץ, הפנייה שמאלה או ימינה נקבעת לפי הערך של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lfloor s/2^h\rfloor} במקרה שהוא מספר זוגי הפנייה תהיה ימינה ואם הוא אי-זוגי הפנייה תהיה שמאלה.

תהליך האימות

כאשר המאמת מקבל את החתימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma_s=(s,\sigma,Y_s,A_s)} יחד עם המסמך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} הוא פועל בשני צעדים:

תחילה בודק עם פונקציית האימות של ה-OTS עם מפתח האימות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y_s} ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma} היא חתימה תקפה על התמצית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d=g(D)} . פעולה זו היא חלק מאלגוריתם החתימה והיא נפרדת מהעץ.
אם הצעד הראשון הסתיים בהצלחה, המאמת מוודה את אמינותו של מפתח האימות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y_s} עצמו על ידי בניית המסלול הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_0,...,p_H} מהעלה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(Y_s)} לשורש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} . לשם כך הוא משתמש באינדקס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} ובמסלול האימות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_s} כדלהלן:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_h=\begin{cases} g(a_{h-1} \ \| \ p_{h-1}), & \mbox{if }\lfloor s/2^{h-1}\rfloor\equiv 1\text{ mod }2 \\ g(p_{h-1} \ \| \ a_{h-1}), & \mbox{if }\lfloor s/2^{h-1}\rfloor\equiv 0\text{ mod }2 \end{cases}}

במהלך בניית המסלול האינדקס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} משמש להחלטה באיזה סדר לגבב את ערכי שני הצמתים הנוכחיים כדי לקבל את צומת האב. אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lfloor s/2^{h-1}\rfloor} הוא מספר זוגי אז למעשה הצומת הנוכחי ימני לכן יש להוסיף את הצומת השני משמאלו ואילו אם הוא אי-זוגי הסדר הפוך.

אם המאמת מצליח לבנות מסלול לשורש העץ כך שראש המסלול שווה ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} . הרי שהיות ששורש העץ הוא מפתח ציבורי מאומת הוא יכול להיות משוכנע ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y_s} אותנטי וכי לא שונה באופן זדוני או כתוצאה מטעות כלשהי. במקרה זה תהליך אימות החתימה הושלם בהצלחה. אחרת, המסמך כנראה שונה או השתבש או שהחתימה זוייפה.

שיטות מתקדמות

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

היות שכל חתימה חד-פעמית, חייבים לאחסן את כל החתימות בזיכרון.
כמות החתימות המרבית מוגבלת למספר העלים בעץ, ליתר דיוק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^H} עבור עץ בגובה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} .
החתימות עצמן גדולות מאוד. אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} הוא פרמטר ביטחון בסיביות, כל חתימה צריכה להכיל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\cdot 2n} סיביות או הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t\cdot n} עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t<n} כלשהו במקרה של חתימת וינטרניץ.
מלבד החתימה נדרש "מסלול אימות" מה שגורם להתנפחות נוספת של החתימה. אורך מסלול האימות הוא בסדר גודל לוגריתמי כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} צמתים עבור עץ בגובה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} .
יש צורך לנהל רישום של החתימות שכבר השתמשו בהן מה שמציב קושי נוסף בניהול ותחזוקת החתימות.

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

השיטה היא לבחור תחילה גרעין ראשוני הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Seed}_0} באורך $n$ סיביות עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0\le i <2^H} . כדי ליצור חתימה חד-פעמית אחת מייצרים גרעין מקומי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Ots}_i} , ממנו מכינים באופן איטרטיבי את כל הערכים של החתימה ובד בבד מעדכנים את הגרעין עבור החתימה הבאה, בניסוח רשמי עבור כל חתימה מבצעים פעם אחת:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\text{Ots}_i,\text{Seed}_{i+1})\leftarrow \text{PRNG}(\text{Seed}_i)} .

ואת החתימה מייצרים באופן איטרטיבי כמידת הצורך:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x_i,\text{Ots}_i)\leftarrow \text{PRNG}(\text{Ots}_i)}

בכל סבב הערך של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Ots}_i} מעודכן בבד בבד עם יצירת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i} . מזה נובע שכאשר רוצים לחשב מפתח מסוים לפי אינדקס, צריך רק את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Seed}_i} ממנו אפשר להכין את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Ots}_i} .

אם משתמשים במחולל פסאודו-אקראי אין צורך לשלוח את מפתח האימות הציבורי יחד עם החתימה, כי אפשר להכין אותו מהחתימה עצמה. תועלת נוספת שבשימוש במחולל פסאודו אקראי היא שכעת עץ מרקל מספק גם ביטחון לפנים (forward security) כל עוד המחולל בטוח לשימוש. ביטחון לפנים של חתימה דיגיטלית היא תכונה חשובה שמשמעותה היא שכל החתימות שנעשו לפני שמפתח כלשהו נפסל בגלל חשיפה נותרות בטוחות. כאן המחולל יכול לשמש רק להכנת מפתחות חדשים גם בהינתן הגרעין ההתחלתי לא ניתן להשתמש בו כדי לגלות מפתחות קודמים.

אלגוריתם עץ מרקל הקלאסי צורך זיכרון בסדר גודל של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log^2 N/2} גיבובים וזמן ביצוע של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\log N} קריאות לפונקציית הגיבוב, כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N=2^H} הוא מספר העלים. מבחינה פרקטית דרישות אילו גדולות מדי. "בעיית מסלול האימות" היא מציאת אלגוריתם סדרתי יעיל המפיק מסלול אימות הקצר ביותר מהעלה לשורש בעץ מרקל. מצד אחד הפתרון הנאיבי הוא שמירת כל העץ בזיכרון כך שכל המסלולים זמינים ללא צורך במידע נוסף אך במחיר של שימוש מוגזם בזיכרון. זה אינו מעשי. מצד שני חישוב מסלול אימות בנפרד עבור כל עלה אמנם חוסך בצריכת זיכרון אך במחיר עלייה בסיבוכיות זמן הביצוע. מסתבר שבמהלך בניית מסלולים לכל העלים בעץ נוצרת 'חפיפה', קיימים צמתים רבים המשותפים לכמה מסלולים ולכן טבעי לנצל מידע שנאסף בזמן בניית מסלול לעלה אחד, כדי לקצר את הזמן והמידע הדרוש לבניית מסלול עבור העלה הבא.

לאור זאת הוצעו מספר שיפורים לאלגוריתם עץ מרקל המתואר לעיל המציעים שיפור הן בזמן ביצוע והן בצריכת זיכרון. ביניהם אלגוריתמים לחיפוש (tree traversal) מהאלגוריתם הקלאסי ועד אלגוריתם חיפוש פרקטלי^[10] שבו מתייחסים לעץ מרקל כאל יער של עצי מרקל (מכאן השם), איתו אפשר להגיע לזמן ביצוע של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\log N/\log\log N} וזיכרון בסדר גודל של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1.5\log^2 N/\log\log N} . אלגוריתם אחר מציע סיבוכיות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\ \log_2 N} ולמקום בסדר גודל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3\ \log_2 N} ^[11]^[12].

ראו גם

הערות שוליים

^ A CERTIFIED DIGITAL SIGNATURE, Merkle, R.C., 1979
^ IPFS - Content Addressed, Versioned, P2P File System
^ ZFS End-to-End Data Integrity, Jeff Bonwick's Blog, 2005
^ General Verifiable Federation, Google Wave Protocol, 2009
^ Git User Manual, Trust
^ Cryptocash, cryptocurrencies, and cryptocontracts, Neal Koblitz, Alfred J. Menezes, Springer 2015
^ Dynamo: Amazon’s Highly Available Key-value Store, Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall and Werner Vogels
^ Merkle tree traversal revisited, Johannes Buchmann, Erik Dahmen, and Michael Schneider
^ CMSS - An Improved Merkle Signature Scheme
^ Fractal Merkle Tree Representation and Traversal, Markus Jakobsson, Tom Leighton, Silvio Micali, Michael Szydlo, 2003
^ Merkle Tree Traversal in Log Space and Time, Michael Szydlo, Eurocrypt 2004
^ A space- and time-efficient Implementation of the Merkle Tree Traversal Algorithm, Markus Knecht, Carlo U. Nicola, 2013

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

23340716עץ מרקל

[1] A CERTIFIED DIGITAL SIGNATURE, Merkle, R.C., 1979

[2] IPFS - Content Addressed, Versioned, P2P File System

[3] ZFS End-to-End Data Integrity, Jeff Bonwick's Blog, 2005

[4] General Verifiable Federation, Google Wave Protocol, 2009

[5] Git User Manual, Trust

[6] Cryptocash, cryptocurrencies, and cryptocontracts, Neal Koblitz, Alfred J. Menezes, Springer 2015

[7] Dynamo: Amazon’s Highly Available Key-value Store, Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall and Werner Vogels

[8] Merkle tree traversal revisited, Johannes Buchmann, Erik Dahmen, and Michael Schneider

[9] CMSS - An Improved Merkle Signature Scheme

[10] Fractal Merkle Tree Representation and Traversal, Markus Jakobsson, Tom Leighton, Silvio Micali, Michael Szydlo, 2003

[11] Merkle Tree Traversal in Log Space and Time, Michael Szydlo, Eurocrypt 2004

[12] A space- and time-efficient Implementation of the Merkle Tree Traversal Algorithm, Markus Knecht, Carlo U. Nicola, 2013

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]