תהליך הכרייה של Zcash ופרדוקס יום ההולדת
אלגוריתם הכרייה של זיקאש נקרא Equihash והוא מבוסס על הוכחת העבודה (Proof of Work) ובעיה קלאסית בסטטיסטיקה המוכרת בתור "פרדוקס יום ההולדת". הפרדוקס מתאר מצב שבו שני זרים מוחלטים נפגשים ברחוב ומסתבר שהם נולדו באותו יום. מכיוון שיש 365 ימים בשנה, הסבירות לכך היא 0.27%. לעומת זאת, אם ישנם 20 עד 30 איש באותו חדר, הסיכוי שלשניים מהם יהיה יום הולדת באותו תאריך עולה באופן דרמטי ל-50%!
מדוע זה קורה? חוק בסיסי בתורת ההסתברות קובע שאם יש N אפשרויות להתרחשות של אירוע מסוים, צריך את השורש הריבועי של N עצמים כדי שיהיה סיכוי של 50% להתנגשות ביניהם. במקרה של פרדוקס יום ההולדת, אנחנו זקוקים לשורש הריבועי של 365, כלומר 23 איש.
אופי הבעיה הזו מונע מצב שבו כורים עם חומרה ייעודית (ASIC) יוכלו לקבל יתרון על כורים עם חומרה חלשה יותר. אם תהליך הכרייה עובר אופטימיזציה, כולם יכולים ליהנות ממנה.
הוכחות באפס ידיעה (Zero-Knowledge Proofs)
הוכחה באפס ידיעה הוא קונספט במדעי המחשב שפותח עוד בשנות השמונים. הקונספט מתאר מצב שבו מי שנושא עליו את נטל ההוכחה צריך לשכנע גורם אחר באמיתות הטענה בלי שהוא חושף את מה שהוא יודע.
למעשה, במקום לבדוק האם הטענה היא שקרית, הבדיקה נועדה למנוע מצב שבו מי שמאמת את הטענה ידליף את המידע הלאה. לכן, המטרה היא לחשוף אותו לכמה שפחות מידע.
אפשר לקחת דוגמה פשוטה של הכנסת סיסמה לשם כניסה לאתר: אפילו אם הסיסמה מוצפנת במסד הנתונים, המשתמש עצמו מקליד את הסיסמה הלא מוצפנת והשרת מקבל אותה, מה שעלול לחשוף אותה לפורצים.
להוכחה באפס ידיעה יש שני צדדים – 'מוכיח' (Prover) ו-'מאמת' (Verifier). כדי שההוכחה תעבוד, חייבים להתקיים שלושה תנאים עבור ההצהרה שאותה רוצים להעביר בין הצדדים:
- שלמות – אם ההצהרה נכונה, אז 'מאמת' הגון יכול להיות משוכנע על ידי 'מוכיח' הגון.
- תקפות – אם מי שמוכיח את ההצהרה הוא לא הגון, הוא לא יכול לשכנע את מי שמאמת את הצהרה באמצעות שקר.
- אפס ידיעה – אם ההצהרה נכונה, ל'מאמת' לא יהיה מושג מה ההצהרה אומרת.
אחת הדוגמאות הידועות שמדגימות את הרעיון היא 'המערה של עליבאבא': נניח שקיימת מערה בצורת המספר "0" ולה יש דלת אחורית עם סיסמה. כיצד מי שיודע את הסיסמה לדלת האחורית למערה יכול להוכיח למישהו אחר שהוא יודע אותה, מבלי למסור לו אותה?
אך מה אם היה מדובר במזל? מה אם ה'מוכיח' לא ידע את הסיסמה לדלת האחורית, בחר בנתיב B ובמזל רב ה'מאמת' בחר לבקש שיגיע מנתיב B?
ובכן, מהכניסה הקדמית אפשר לקחת את נתיב A או נתיב B כדי להגיע לדלת האחורית (המערה השמאלית בדוגמה). נניח שה'מוכיח' (המסומן בעיגול עם האות 'P') בוחר בנתיב A ומגיע לדלת הסודית שבצד השני (המערה האמצעית). כשהוא מגיע לדלת הסודית, ה'מאמת' (מסומן באות 'V'), שלא ראה את נתיבו של ה'מוכיח' בתוך המערה, צועק לו "אני רוצה שתגיע מנתיב B!". ה'מוכיח' מגיע מנתיב B ועל פניו נראה שהצליח להוכיח לו.