הצגת המקור של הדף "עץ מרקל"

ב[[קריפטוגרפיה]] ו[[מדעי המחשב]], '''עץ מרקל''' (Merkle tree) הוא עץ [[פונקציית גיבוב|גיבוב]] [[עץ בינארי|בינארי]] שבו כל קודקוד מסומן בערך גיבוב של שני בניו (או ערכי העלים) והוא סוג של [[טבלת גיבוב]] בצורת [[רשימה (מבנה נתונים)|רשימה]] היררכית. כלומר, קיים קשר בין ערכי כל הצמתים החל מהעלים ועד לשורש העץ. עץ מרקל פותח על ידי [[רלף מרקל]] {{אנ|Ralph Merkle}} ב-1979{{הערה|[http://www.merkle.com/papers/Certified1979.pdf A CERTIFIED DIGITAL SIGNATURE],  Merkle, R.C., 1979}}.

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

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

[[קובץ:Merkle tree.png|420px|ממוזער|שמאל|תרשים לדוגמה של עץ מרקל בגובה <math>H=3</math>]]

ביישומים מעשיים אפשר למצוא את עץ מרקל במערכות בהן צריך לוודא שבלוק מידע שהתקבל ב[[תקשורת נתונים|רשת תקשורת]] או אוחזר מ[[אמצעי לאחסון נתונים|אמצעי אחסון]], לא ניזוק או שונה אם בגלל תקלת תקשורת, פגם במדיית האחסון, [[השחתת זיכרון]] או חבלה זדונית. לתכונה זו חשיבות בעיקר במערכות קבצים, [[שיתוף מבוזר]], [[עמית לעמית]], מסדי נתונים ו[[חישוביות מאובטחת]]. דוגמאות מעשיות בהן משתמשים בעץ מרקל שברובן [[קוד פתוח]], כוללות את מערכות הקבצים [[IPFS]]{{הערה|[https://ipfs.io/ipfs/QmR7GSQM93Cx5eAg6a6yRzNde1FQv7uL6X1o4k7zrJa3LX/ipfs.draft3.pdf IPFS - Content Addressed, Versioned, P2P File System]}},{{הערה|[https://blogs.oracle.com/bonwick/entry/zfs_end_to_end_data ZFS End-to-End Data Integrity], Jeff Bonwick's Blog, 2005}}[[ZFS]], [[גנוטלה]], פרוטוקול [[ביטורנט]], פרוטוקול ו[[פלטפורמת מחשוב]] [[Apache Wave]]{{הערה|[http://www.waveprotocol.org/whitepapers/wave-protocol-verification General Verifiable Federation], Google Wave Protocol, 2009}} של [[גוגל (חברה)|גוגל]], [[גיט]]{{הערה|[https://www.kernel.org/pub/software/scm/git/docs/user-manual.html#trust Git User Manual], Trust}}, [[ביטקוין]]{{הערה|[http://link.springer.com/article/10.1007/s10623-015-0148-5 Cryptocash, cryptocurrencies, and cryptocontracts], Neal Koblitz, Alfred J. Menezes, Springer 2015}}, [[DynamoDB]]{{הערה|[http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf 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 }} של [[אמזון]] ועוד.

==עץ אימות של מרקל==
עץ האימות של מרקל{{הערה|[https://www.cdc.informatik.tu-darmstadt.de/~dahmen/papers/BDS08.pdf Merkle tree traversal revisited], Johannes Buchmann, Erik Dahmen, and Michael Schneider}} נועד בתחילה לשיפור חתימת למפורט. הרעיון הוא להשתמש ב[[עץ בינארי]] מושלם שעליו מייצגים חתימות חד-פעמיות. כל עלה משמש לחתימה על מסמך אחד ואילו אימות כל החתימות נעשה על ידי שורש העץ. עץ האימות יכול לעבוד עם כל פונקציית גיבוב וכל סכמת חתימה דיגיטלית חד-פעמית (בקיצור OTS) כמו [[חתימת למפורט]] או [[חתימת למפורט#גרסת וינטרניץ|חתימת וינטרניץ]]. הוכח שעץ מרקל נקרא בטוח תחת CMA (התקפת מסר-נבחר) כל עוד פונקציית הגיבוב שבה משתמשים חסינה מפני התנגשויות ופונקציית החתימה שבבסיסו בטוחה גם היא תחת מודל התקפת מסר-נבחר. 

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

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

# החותם בוחר שלם <math>H\ge 2</math> המייצג את גובה העץ כך שיתאים לחתימה על לכל היותר <math>2^H</math> מסמכים. זאת בניגוד לסכמות חתימה דיגיטלית אחרות כמו [[Digital Signature Algorithm|DSA]] שתאורטית אינן מוגבלות במספר המסמכים עליהם אפשר לחתום. 
# החותם מכין <math>2^H</math> זוגות של מפתחות; מפתח חתימה/מפתח אימות <math>(X_i,Y_i)</math> בהתאמה כאשר <math>0\le i < 2^H</math>. הכנת המפתחות מתבצעת על ידי בחירת מחרוזת אקראית <math>X_i</math> ואז חישוב הפונקציה החד כיוונית שלה <math>Y_i</math>  המשמשת כמפתח ציבורי. 
# מכין את עלי העץ שערכם הוא הגיבוב של המפתחות הציבוריים. אם נתונה פונקציית גיבוב מוסכמת <math>g</math> ערכו של כל עלה יהיה <math>g(Y_i)</math> כאשר <math>0\le i < 2^H</math>. 
# קודקודי העץ הפנימיים מחושבים לפי הכלל הבא: צומת אב מכיל את ערך הגיבוב של [[שרשור (מחרוזות)|שרשור]] ערכי שני הצמתים (או עלים) הבנים, השמאלי והימני. אם נסמן צומת ב-<math>\nu_h[i]</math> כאשר <math>h\in\{0,...,H\}</math> מייצג את גובה הצומת ו-<math>i</math> הוא ערך בין 0 ל-<math>2^{H-h}</math> המייצג את מספר העלה או הצומת בגובה <math>h</math>, אז ערכו של כל צומת בניסוח רשמי הוא:
::<math>\nu_h[i]=g(\nu_{h-1}[2i]\ \| \ \nu_{h-1}[2i+1]), \ \ 1\le h\le H, 0\le i<2^{H-h}</math>.
::כאשר הסימן <math>\|</math> מייצג [[שרשור (מחרוזות)|שרשור]].

כדי לחשב את שורש העץ אין חובה לאחסן את כל העץ בזיכרון. אפשר באמצעות [[הגדרה רקורסיבית|פונקציה רקורסיבית]] לבנות את העץ מלמטה למעלה ולחשב את הערכים לפי הצורך עד הרמה העליונה ביותר שהיא שורש העץ. להלן תיאור [[אלגוריתם]] בסיסי לבניית עץ גיבוב של מרקל. הרעיון הוא לחשב את העלים ובמידת האפשר את אבותיהם באותה נשימה. לשם כך מפעילים [[מחסנית (מבנה נתונים)|מחסנית]] עם פונקציות אתחול ([[init]]), דחיפה (push) ושליפה (pop) הרגילות. 
 
====אלגוריתם עץ גיבוב====
[[קובץ:Merkle order.png|340px|ממוזער|שמאל|סדר הבנייה של הצמתים בעץ מרקל עם האלגוריתם המתואר, עבור עץ בגובה <math>H=3</math>.]]
:'''קלט''': גובה העץ <math>H</math>
:'''פלט''': שורש עץ הגיבוב <math>R</math>, דהיינו המפתח הציבורי.
:1. עבור <math>i=0</math> עד <math>2^{H}-1</math> בצע:
::א. חשב את העלה ה-<math>i</math>. הצב: <math>\text{Node}1=\text{CreateLeaf}(i)</math>.
::ב. כל עוד גובהו של <math>\text{Node1}</math> שווה לגובה הצומת בראש המחסנית <math>\text{Stack}</math>.
:::1. בצע שליפה: <math>\text{Node}2=\text{Stack}.\text{Pop}()</math>.
:::2. חשב את צומת האב: <math>\text{Node}1=g(\text{Node}2\ \| \ \text{Node}1)</math>.
::ג. בצע דחיפה: <math>\text{Stack}.\text{Push}(\text{Node}1)</math>.
:2. שלוף את השורש: <math>R=\text{Stack}.\text{Pop}()</math>.
:3. החזר את <math>R</math>.

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

====תהליך החתימה====
[[קובץ:Auth path.png|420px|ממוזער|שמאל|דוגמה לחתימה על מסמך הרביעי בעץ מרקל בגובה <math>H=3</math>. החתימה <math>\sigma_s</math> כוללת את האינדקס <math>s=3</math>, מפתח האימות הציבורי <math>Y_3</math>, החתימה החד-פעמית <math>\sigma=\text{OTS}_{X_3}(d)</math> עם מפתח החתימה <math>X_3</math> והצמתים <math>A_3=(a_0,a_1,a_2)=(\nu_0[2],\nu_1[0],\nu_2[1])</math> שהם הצמתים האחים של הצמתים במסלול מהעלה הרביעי לשורש העץ.]]
תחילה החותם מכין מהמסמך <math>D</math> את התמצית <math>d=g(D)</math> (אותה אפשר לקבל באמצעות פונקציית גיבוב כמו [[SHA-2]]) ואז מכין את החתימה <math>\sigma_s</math> עם מפתח החתימה הסודי <math>X_s</math>. כאשר <math>0\le s\le 2^H-1</math> מייצג את אינדקס החתימה הפנויה בעץ. כזכור העץ מכיל חתימות חד-פעמיות לכן צריך אינדקס כדי להבטיח שלא יהיה שימוש כפול בחתימה. בנוסף, החותם חייב לשלוח יחד עם החתימה גם את מפתח האימות הציבורי המתאים למסמך <math>D</math> כי המקבל מחזיק רק בשורש העץ כמפתח אימות. 

החותם צריך לכלול בחתימה <math>\sigma_s</math> את הערכים הבאים:
#האינדקס <math>s</math> המייצג את מספרה הסידורי של החתימה בעץ. 
#החתימה החד-פעמית <math>\sigma</math> על תמצית המסמך לפי אלגוריתם החתימה החד-פעמית <math>\text{OTS}</math> שנעשתה עם מפתח החתימה הפרטי <math>X_s</math>.
#מפתח האימות הציבורי המתאים <math>Y_s</math>.
#"מסלול אימות" שהוא הרצף <math>A_s=(a_0,...,a_{H-1})</math> הכולל רשימה של <math>H</math> צמתים בעץ איתם המאמת ישתמש כדי לשחזר את המסלול מהעלה <math>g(Y_s)</math> לשורש העץ <math>R</math> כדי לאמת את מפתח החתימה <math>Y_s</math>. היות שחישוב כל צומת דורש את שני הצמתים הבנים, כל צומת <math>a_j</math> במסלול האימות הוא למעשה צומת האח של הצומת הנוכחי בגובה <math>h</math> לאורך המסלול מהעלה לשורש כך שמתקיים:
:::<math>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}</math>

::במילים אחרות, במהלך התנועה במעלה העץ, הפנייה שמאלה או ימינה נקבעת לפי הערך של <math>\lfloor s/2^h\rfloor</math> במקרה שהוא [[מספר זוגי]] הפנייה תהיה ימינה ואם הוא אי-זוגי הפנייה תהיה שמאלה.

====תהליך האימות====
כאשר המאמת מקבל את החתימה <math>\sigma_s=(s,\sigma,Y_s,A_s)</math> יחד עם המסמך <math>D</math> הוא פועל בשני צעדים:

*תחילה בודק עם פונקציית האימות של ה-OTS עם מפתח האימות <math>Y_s</math> ש-<math>\sigma</math> היא חתימה תקפה על התמצית <math>d=g(D)</math>. פעולה זו היא חלק מאלגוריתם החתימה והיא נפרדת מהעץ.
*אם הצעד הראשון הסתיים בהצלחה, המאמת מוודה את אמינותו של מפתח האימות <math>Y_s</math> עצמו על ידי בניית המסלול <math>p_0,...,p_H</math> מהעלה <math>g(Y_s)</math> לשורש <math>R</math>. לשם כך הוא משתמש באינדקס <math>s</math> ובמסלול האימות <math>A_s</math> כדלהלן:
:<math>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}</math>

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

אם המאמת מצליח לבנות מסלול לשורש העץ כך שראש המסלול שווה ל-<math>R</math>. הרי שהיות ששורש העץ הוא מפתח ציבורי מאומת הוא יכול להיות משוכנע ש-<math>Y_s</math> אותנטי וכי לא שונה באופן זדוני או כתוצאה מטעות כלשהי. במקרה זה תהליך אימות החתימה הושלם בהצלחה. אחרת, המסמך כנראה שונה או השתבש או שהחתימה זויפה.

==שיטות מתקדמות==
עץ מרקל חוסך במקום אחסון בזיכרון אך עדיין אינו יעיל מבחינה מעשית ככלי לחתימה דיגיטלית מאסיבית בגלל כמה סיבות:
# היות שכל חתימה חד-פעמית, חייבים לאחסן את כל החתימות בזיכרון.
# כמות החתימות המרבית מוגבלת למספר העלים בעץ, ליתר דיוק <math>2^H</math> עבור עץ בגובה <math>H</math>. 
# החתימות עצמן גדולות מאוד. אם <math>n</math> הוא פרמטר ביטחון בסיביות, כל חתימה צריכה להכיל <math>n\cdot 2n</math> סיביות או <math>t\cdot n</math> עבור <math>t<n</math> כלשהו במקרה של חתימת וינטרניץ. 
# מלבד החתימה נדרש "מסלול אימות" מה שגורם להתנפחות נוספת של החתימה. אורך מסלול האימות הוא בסדר גודל לוגריתמי כלומר <math>H</math> צמתים עבור עץ בגובה <math>H</math>.
# יש צורך לנהל רישום של החתימות שכבר השתמשו בהן מה שמציב קושי נוסף בניהול ותחזוקת החתימות.

קיימים מספר שיפורים לעץ מרקל. לבעיה הראשונה קיים פתרון פשוט{{הערה|[https://eprint.iacr.org/2006/320.pdf CMSS - An Improved Merkle Signature Scheme]}} והוא להשתמש ב[[מחולל מספרים פסאודו-אקראיים קריפטוגרפי|מחולל פסאודו אקראי]] בקיצור PRNG. פתרון דומה הוצע על ידי מרקל. במקרה זה כל חתימה חד פעמית נדרשת להכנה פעמיים, פעם אחת כאשר בונים את העץ ובפעם השנייה כאשר חותמים על מסמך. התועלת בכך היא שכעת החותם אינו צריך לשמור בזיכרון חתימות כלל אלא רק גרעין התחלתי סודי שממנו הוא יכול לייצר אותם לפי הצורך.

השיטה היא לבחור תחילה גרעין ראשוני <math>\text{Seed}_0</math> באורך <math>n</math> סיביות עבור <math>0\le i <2^H</math>. כדי ליצור חתימה חד-פעמית אחת מייצרים גרעין מקומי <math>\text{Ots}_i</math>, ממנו מכינים באופן איטרטיבי את כל הערכים של החתימה ובד בבד מעדכנים את הגרעין עבור החתימה הבאה, בניסוח רשמי עבור כל חתימה מבצעים פעם אחת:
:<math>(\text{Ots}_i,\text{Seed}_{i+1})\leftarrow \text{PRNG}(\text{Seed}_i)</math>.
ואת החתימה מייצרים באופן איטרטיבי כמידת הצורך:
:<math>(x_i,\text{Ots}_i)\leftarrow \text{PRNG}(\text{Ots}_i)</math> 
בכל סבב הערך של <math>\text{Ots}_i</math> מעודכן בבד בבד עם יצירת <math>x_i</math>. מזה נובע שכאשר רוצים לחשב מפתח מסוים לפי אינדקס, צריך רק את <math>\text{Seed}_i</math> ממנו אפשר להכין את <math>\text{Ots}_i</math>.

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

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

לאור זאת הוצעו מספר שיפורים לאלגוריתם עץ מרקל המתואר לעיל המציעים שיפור הן בזמן ביצוע והן בצריכת זיכרון. ביניהם אלגוריתמים לחיפוש (tree traversal) מהאלגוריתם הקלאסי ועד אלגוריתם חיפוש [[פרקטל|פרקטלי]]{{הערה|[http://link.springer.com/chapter/10.1007/3-540-36563-X_21 Fractal Merkle Tree Representation and Traversal], Markus Jakobsson, Tom Leighton, Silvio Micali, Michael Szydlo, 2003}} שבו מתייחסים לעץ מרקל כאל יער של עצי מרקל (מכאן השם), איתו אפשר להגיע לזמן ביצוע של <math>2\log N/\log\log N</math> וזיכרון בסדר גודל של <math>1.5\log^2 N/\log\log N</math>. אלגוריתם אחר מציע [[סיבוכיות]] של <math>2\ \log_2 N</math> ולמקום בסדר גודל <math>3\ \log_2 N</math>{{הערה|[http://link.springer.com/chapter/10.1007%2F978-3-540-24676-3_32 Merkle Tree Traversal in Log Space and Time], Michael Szydlo, Eurocrypt 2004}}{{הערה|[http://www.fhnw.ch/technik/imvs/publikationen/artikel-2013/a-space-and-time-efficient-implementation-of-the-merkle-tree-traversal-algorithm A space- and time-efficient Implementation of the Merkle Tree Traversal Algorithm], Markus Knecht, Carlo U. Nicola, 2013}}.

==ראו גם==
* [[עץ בינארי]]
* [[חתימה דיגיטלית]]

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{קריפטוגרפיה}}

[[קטגוריה:הצפנה]]
[[קטגוריה:מדעי המחשב]]