עץ מרקל

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

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

שימושים

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

תרשים לדוגמה של עץ מרקל בגובה ${\displaystyle H=3}$

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

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

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

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

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

1. החותם בוחר שלם ${\displaystyle H\geq 2}$ המייצג את גובה העץ כך שיתאים לחתימה על לכל היותר ${\displaystyle 2^{H}}$ מסמכים. זאת בניגוד לסכמות חתימה דיגיטלית אחרות כמו DSA שתאורטית אינן מוגבלות במספר המסמכים עליהם אפשר לחתום.
2. החותם מכין ${\displaystyle 2^{H}}$ זוגות של מפתחות; מפתח חתימה/מפתח אימות ${\displaystyle (X_{i},Y_{i})}$ בהתאמה כאשר ${\displaystyle 0\leq i<2^{H}}$. הכנת המפתחות מתבצעת על ידי בחירת מחרוזת אקראית ${\displaystyle X_{i}}$ ואז חישוב הפונקציה החד כיוונית שלה ${\displaystyle Y_{i}}$ המשמשת כמפתח ציבורי.
3. מכין את עלי העץ שערכם הוא הגיבוב של המפתחות הציבוריים. אם נתונה פונקציית גיבוב מוסכמת ${\displaystyle g}$ ערכו של כל עלה יהיה ${\displaystyle g(Y_{i})}$ כאשר ${\displaystyle 0\leq i<2^{H}}$.
4. קודקודי העץ הפנימיים מחושבים לפי הכלל הבא: צומת אב מכיל את ערך הגיבוב של שרשור ערכי שני הצמתים (או עלים) הבנים, השמאלי והימני. אם נסמן צומת ב-${\displaystyle \nu _{h}[i]}$ כאשר ${\displaystyle h\in \{0,...,H\}}$ מייצג את גובה הצומת ו-${\displaystyle i}$ הוא ערך בין 0 ל-${\displaystyle 2^{H-h}}$ המייצג את מספר העלה או הצומת בגובה ${\displaystyle h}$, אז ערכו של כל צומת בניסוח רשמי הוא:

${\displaystyle \nu _{h}[i]=g(\nu _{h-1}[2i]\ \|\ \nu _{h-1}[2i+1]),\ \ 1\leq h\leq H,0\leq i<2^{H-h}}$.

כאשר הסימן ${\displaystyle \|}$ מייצג שרשור.

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

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

סדר הבנייה של הצמתים בעץ מרקל עם האלגוריתם המתואר, עבור עץ בגובה ${\displaystyle H=3}$.

קלט: גובה העץ ${\displaystyle H}$

פלט: שורש עץ הגיבוב ${\displaystyle R}$, דהיינו המפתח הציבורי.

1. עבור ${\displaystyle i=0}$ עד ${\displaystyle 2^{H}-1}$ בצע:

א. חשב את העלה ה-${\displaystyle i}$. הצב: ${\displaystyle {\text{Node}}1={\text{CreateLeaf}}(i)}$.

ב. כל עוד גובהו של ${\displaystyle {\text{Node1}}}$ שווה לגובה הצומת בראש המחסנית ${\displaystyle {\text{Stack}}}$.

1. בצע שליפה: ${\displaystyle {\text{Node}}2={\text{Stack}}.{\text{Pop}}()}$.

2. חשב את צומת האב: ${\displaystyle {\text{Node}}1=g({\text{Node}}2\ \|\ {\text{Node}}1)}$.

ג. בצע דחיפה: ${\displaystyle {\text{Stack}}.{\text{Push}}({\text{Node}}1)}$.

2. שלוף את השורש: ${\displaystyle R={\text{Stack}}.{\text{Pop}}()}$.

3. החזר את ${\displaystyle R}$.

האלגוריתם נעזר בתת-שגרה הנקראת ${\displaystyle {\text{CreateLeaf}}}$ שמייצרת עם הפונקציה החד-כיוונית את זוג המפתחות הבא (מפתח פרטי/מפתח ציבורי) וכן מבצעת גיבוב של המפתח הציבורי אותו היא מחזירה כעלה ${\displaystyle {\text{Node1}}}$. בתרשים משמאל מתואר סדר בניית הצמתים של האלגוריתם. בכל שלב של האלגוריתם נמצאים במחסנית לכל היותר ${\displaystyle H}$ צמתים והוא מבצע ${\displaystyle 2^{H}}$ קריאות לתת-שגרה ${\displaystyle {\text{CreateLeaf}}}$ בנוסף ל-${\displaystyle 2^{H}-1}$ הפעלות של פונקציית הגיבוב.

תהליך החתימה

דוגמה לחתימה על מסמך הרביעי בעץ מרקל בגובה ${\displaystyle H=3}$. החתימה ${\displaystyle \sigma _{s}}$ כוללת את האינדקס ${\displaystyle s=3}$, מפתח האימות הציבורי ${\displaystyle Y_{3}}$, החתימה החד-פעמית ${\displaystyle \sigma ={\text{OTS}}_{X_{3}}(d)}$ עם מפתח החתימה ${\displaystyle X_{3}}$ והצמתים ${\displaystyle A_{3}=(a_{0},a_{1},a_{2})=(\nu _{0}[2],\nu _{1}[0],\nu _{2}[1])}$ שהם הצמתים האחים של הצמתים במסלול מהעלה הרביעי לשורש העץ.

תחילה החותם מכין מהמסמך ${\displaystyle D}$ את התמצית ${\displaystyle d=g(D)}$ (אותה אפשר לקבל באמצעות פונקציית גיבוב כמו SHA-2) ואז מכין את החתימה ${\displaystyle \sigma _{s}}$ עם מפתח החתימה הסודי ${\displaystyle X_{s}}$. כאשר ${\displaystyle 0\leq s\leq 2^{H}-1}$ מייצג את אינדקס החתימה הפנויה בעץ. כזכור העץ מכיל חתימות חד-פעמיות לכן צריך אינדקס כדי להבטיח שלא יהיה שימוש כפול בחתימה. בנוסף, החותם חייב לשלוח יחד עם החתימה גם את מפתח האימות הציבורי המתאים למסמך ${\displaystyle D}$ כי המקבל מחזיק רק בשורש העץ כמפתח אימות.

החותם צריך לכלול בחתימה ${\displaystyle \sigma _{s}}$ את הערכים הבאים:

1. האינדקס ${\displaystyle s}$ המייצג את מספרה הסידורי של החתימה בעץ.
2. החתימה החד-פעמית ${\displaystyle \sigma }$ על תמצית המסמך לפי אלגוריתם החתימה החד-פעמית ${\displaystyle {\text{OTS}}}$ שנעשתה עם מפתח החתימה הפרטי ${\displaystyle X_{s}}$.
3. מפתח האימות הציבורי המתאים ${\displaystyle Y_{s}}$.
4. "מסלול אימות" שהוא הרצף ${\displaystyle A_{s}=(a_{0},...,a_{H-1})}$ הכולל רשימה של ${\displaystyle H}$ צמתים בעץ איתם המאמת ישתמש כדי לשחזר את המסלול מהעלה ${\displaystyle g(Y_{s})}$ לשורש העץ ${\displaystyle R}$ כדי לאמת את מפתח החתימה ${\displaystyle Y_{s}}$. היות שחישוב כל צומת דורש את שני הצמתים הבנים, כל צומת ${\displaystyle a_{j}}$ במסלול האימות הוא למעשה צומת האח של הצומת הנוכחי בגובה ${\displaystyle h}$ לאורך המסלול מהעלה לשורש כך שמתקיים:

${\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}}}$

במילים אחרות, במהלך התנועה במעלה העץ, הפנייה שמאלה או ימינה נקבעת לפי הערך של ${\displaystyle \lfloor s/2^{h}\rfloor }$ במקרה שהוא מספר זוגי הפנייה תהיה ימינה ואם הוא אי-זוגי הפנייה תהיה שמאלה.

תהליך האימות

כאשר המאמת מקבל את החתימה ${\displaystyle \sigma _{s}=(s,\sigma ,Y_{s},A_{s})}$ יחד עם המסמך ${\displaystyle D}$ הוא פועל בשני צעדים:

• תחילה בודק עם פונקציית האימות של ה-OTS עם מפתח האימות ${\displaystyle Y_{s}}$ ש-${\displaystyle \sigma }$ היא חתימה תקפה על התמצית ${\displaystyle d=g(D)}$. פעולה זו היא חלק מאלגוריתם החתימה והיא נפרדת מהעץ.
• אם הצעד הראשון הסתיים בהצלחה, המאמת מוודה את אמינותו של מפתח האימות ${\displaystyle Y_{s}}$ עצמו על ידי בניית המסלול ${\displaystyle p_{0},...,p_{H}}$ מהעלה ${\displaystyle g(Y_{s})}$ לשורש ${\displaystyle R}$. לשם כך הוא משתמש באינדקס ${\displaystyle s}$ ובמסלול האימות ${\displaystyle A_{s}}$ כדלהלן:

${\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}}}$

במהלך בניית המסלול האינדקס ${\displaystyle s}$ משמש להחלטה באיזה סדר לגבב את ערכי שני הצמתים הנוכחיים כדי לקבל את צומת האב. אם ${\displaystyle \lfloor s/2^{h-1}\rfloor }$ הוא מספר זוגי אז למעשה הצומת הנוכחי ימני לכן יש להוסיף את הצומת השני משמאלו ואילו אם הוא אי-זוגי הסדר הפוך.

אם המאמת מצליח לבנות מסלול לשורש העץ כך שראש המסלול שווה ל-${\displaystyle R}$. הרי שהיות ששורש העץ הוא מפתח ציבורי מאומת הוא יכול להיות משוכנע ש-${\displaystyle Y_{s}}$ אותנטי וכי לא שונה באופן זדוני או כתוצאה מטעות כלשהי. במקרה זה תהליך אימות החתימה הושלם בהצלחה. אחרת, המסמך כנראה שונה או השתבש או שהחתימה זויפה.

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

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

1. היות שכל חתימה חד-פעמית, חייבים לאחסן את כל החתימות בזיכרון.
2. כמות החתימות המרבית מוגבלת למספר העלים בעץ, ליתר דיוק ${\displaystyle 2^{H}}$ עבור עץ בגובה ${\displaystyle H}$.
3. החתימות עצמן גדולות מאוד. אם ${\displaystyle n}$ הוא פרמטר ביטחון בסיביות, כל חתימה צריכה להכיל ${\displaystyle n\cdot 2n}$ סיביות או ${\displaystyle t\cdot n}$ עבור ${\displaystyle t<n}$ כלשהו במקרה של חתימת וינטרניץ.
4. מלבד החתימה נדרש "מסלול אימות" מה שגורם להתנפחות נוספת של החתימה. אורך מסלול האימות הוא בסדר גודל לוגריתמי כלומר ${\displaystyle H}$ צמתים עבור עץ בגובה ${\displaystyle H}$.
5. יש צורך לנהל רישום של החתימות שכבר השתמשו בהן מה שמציב קושי נוסף בניהול ותחזוקת החתימות.

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

השיטה היא לבחור תחילה גרעין ראשוני ${\displaystyle {\text{Seed}}_{0}}$ באורך ${\displaystyle n}$ סיביות עבור ${\displaystyle 0\leq i<2^{H}}$. כדי ליצור חתימה חד-פעמית אחת מייצרים גרעין מקומי ${\displaystyle {\text{Ots}}_{i}}$, ממנו מכינים באופן איטרטיבי את כל הערכים של החתימה ובד בבד מעדכנים את הגרעין עבור החתימה הבאה, בניסוח רשמי עבור כל חתימה מבצעים פעם אחת:

${\displaystyle ({\text{Ots}}_{i},{\text{Seed}}_{i+1})\leftarrow {\text{PRNG}}({\text{Seed}}_{i})}$.

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

${\displaystyle (x_{i},{\text{Ots}}_{i})\leftarrow {\text{PRNG}}({\text{Ots}}_{i})}$

בכל סבב הערך של ${\displaystyle {\text{Ots}}_{i}}$ מעודכן בבד בבד עם יצירת ${\displaystyle x_{i}}$. מזה נובע שכאשר רוצים לחשב מפתח מסוים לפי אינדקס, צריך רק את ${\displaystyle {\text{Seed}}_{i}}$ ממנו אפשר להכין את ${\displaystyle {\text{Ots}}_{i}}$.

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

אלגוריתם עץ מרקל הקלאסי צורך זיכרון בסדר גודל של ${\displaystyle \log ^{2}N/2}$ גיבובים וזמן ביצוע של ${\displaystyle 2\log N}$ קריאות לפונקציית הגיבוב, כאשר ${\displaystyle N=2^{H}}$ הוא מספר העלים. מבחינה פרקטית דרישות אילו גדולות מדי. "בעיית מסלול האימות" היא מציאת אלגוריתם סדרתי יעיל המפיק מסלול אימות הקצר ביותר מהעלה לשורש בעץ מרקל. מצד אחד הפתרון הנאיבי הוא שמירת כל העץ בזיכרון כך שכל המסלולים זמינים ללא צורך במידע נוסף אך במחיר של שימוש מוגזם בזיכרון. זה אינו מעשי. מצד שני חישוב מסלול אימות בנפרד עבור כל עלה אמנם חוסך בצריכת זיכרון אך במחיר עלייה בסיבוכיות זמן הביצוע. מסתבר שבמהלך בניית מסלולים לכל העלים בעץ נוצרת 'חפיפה', קיימים צמתים רבים המשותפים לכמה מסלולים ולכן טבעי לנצל מידע שנאסף בזמן בניית מסלול לעלה אחד, כדי לקצר את הזמן והמידע הדרוש לבניית מסלול עבור העלה הבא.

לאור זאת הוצעו מספר שיפורים לאלגוריתם עץ מרקל המתואר לעיל המציעים שיפור הן בזמן ביצוע והן בצריכת זיכרון. ביניהם אלגוריתמים לחיפוש (tree traversal) מהאלגוריתם הקלאסי ועד אלגוריתם חיפוש פרקטלי^[10] שבו מתייחסים לעץ מרקל כאל יער של עצי מרקל (מכאן השם), איתו אפשר להגיע לזמן ביצוע של ${\displaystyle 2\log N/\log \log N}$ וזיכרון בסדר גודל של ${\displaystyle 1.5\log ^{2}N/\log \log N}$. אלגוריתם אחר מציע סיבוכיות של ${\displaystyle 2\ \log _{2}N}$ ולמקום בסדר גודל ${\displaystyle 3\ \log _{2}N}$^[11][12].

ראו גם

• עץ בינארי
• חתימה דיגיטלית

הערות שוליים

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