עולם הקריפטו

הוכחה באפס ידיעה (Zero-Knowledge Proof)

הוכחה באפס ידיעה - תמונה ראשית

הוכחה באפס ידיעה (Zero-Knowledge Proof) היא שיטה קריפטוגרפית המשמשת להוכחת ידע על פיסת נתונים, מבלי לחשוף את הנתונים עצמם.

מהי הוכחה באפס ידיעה

הוכחה באפס ידיעה היא דרך להוכיח את תקפותה של הצהרה מבלי לחשוף את ההצהרה עצמה.
המוכיח (Prover) הוא הצד שמנסה להוכיח טענה, בעוד שהמאמת (Verifier) אחראי על תוקף הטענה.

למרות שרק לאחרונה החלו להשתמש ב-ZK בתחום הקריפטו, המושג הופיע לראשונה כבר בשנת 1985 במאמר שנכתב על ידי שפי גולדווסר וסילביו מיקאלי (מייסד אלגורנד) בשם: "מורכבות הידע של מערכות הוכחה אינטראקטיביות" המספק הגדרה של הוכחות אפס ידע בשימוש נרחב כיום.

איך הוכחה באפס ידיעה עובדת

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

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

 להוכחות באפס ידיעה ישנם 3 מאפיינים בסיסיים:

  • שְׁלֵמוּת – אם הצהרה נכונה, מאמת ישר יכול להשתכנע על ידי מוכיח ישר שיש לו ידע לגבי הקלט הנכון.

  • אפס ידיעה – אם ההצהרה נכונה, אז המאמת לא לומד דבר מהמוכיח מלבד העובדה שההצהרה היא אמת.

  • תְקֵפוּת – אם הצהרה שקרית, אז אף מוכיח לא ישר יכול לשכנע באופן חד צדדי מאמת ישר שיש לו ידע לגבי הקלט הנכון (למעט מרווח סבירות זעיר).

אינטראקטיבי ולא אינטראקטיבי

הוכחות באפס ידיעה יכולים להתחלק לשניים: 

  1. אינטראקטיביים – כאשר מוכיח משכנע מאמת ספציפי אבל צריך לחזור על תהליך זה עבור כל מאמת בודד.
  2. לא אינטראקטיביים – כאשר מוכיח מייצר הוכחה שניתן לאמת על ידי כל אחד המשתמש באותה הוכחה.

אינטראקטיבי

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

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


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


מכיוון שההסתברות שהייתם מצליחים באופן אקראי לזהות כל החלפה/אי החלפה היא 50%, ההסתברות להצליח באקראי בכל החלפות/אי החלפות מתקרבת לאפס (תְקֵפוּת). אם אתם וחברכם חוזרים על "הוכחה" זו מספר פעמים (למשל 50 פעמים), חברכם אמור להשתכנע (שְׁלֵמוּת) שהכדורים אכן בצבע שונה.
 
ההוכחה שלעיל היא אפס ידיעה מכיוון שחברכם לעולם לא לומד איזה כדור ירוק ואיזה אדום; ולכן, הוא לא מקבל שום ידע כיצד להבחין בין הכדורים.

לא אינטראקטיבי

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

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

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

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

סוגי הוכחות באפס ידיעה

בקריפטו, ישנם יישומים שונים של הוכחות אפס ידיעה פופולריים:

  1. zk-SNARKs – הם קטנים בגודלם, קלים לאימות ומייצרים הוכחה קריפטוגרפית באמצעות עקומות אליפטיות, הוכחה שיעילה יותר בגז משיטת פונקציית הגיבוב שבה משתמש STARKS (ישנם מקרים [כגון הוכחת מערכי נתונים גדולים] שבהם ZK-STARKs עשויים להיות חסכוניים יותר מאשר ZK-SNARKs).
  2. zk-STARKs – הוכחות מבוססות STARK דורשות אינטראקציה מינימלית בין המוכיח והמאמת, מה שהופך אותן למהירות הרבה יותר מאשר SNARKs.
  3. PLONK – משתמש בהתקנה אוניברסלית מהימנה שניתן להשתמש בה עם כל תוכנה ויכולה לכלול מספר רב של משתתפים. 

יתרונות וחסרונות

Scroll to Top