מחשוב קוואנטי, וכיצד הוא משפיע על ביטקוין
לאחרונה התקבלו דיווחים על כך שחברת IBM מתכננת להשיק עוד השנה פלטפורמת ענן לחישוב קוואנטי. זוהי הזדמנות לדבר על מהו מחשב קוואנטי וכיצד הוא יכול להשפיע על ביטקוין.
במחשב קלאסי המידע מאוחסן כ"ביטים", שכל אחד מהם יכול להיות 0 או 1. פעולת החישוב מתבצעת ע"י ביצוע עדכונים למידע המאוחסן בביטים, אחד אחר השני. ניתן לבצע גם מספר עדכונים במקביל, אך קצב העדכון מוגבל באופן ישיר ע"י כמות החומרה העומדת לרשותנו.
מערכות קריפטוגרפיות רבות המשמשות להצפנת מידע ואימות זהות, מבוססות על בעיות חישוביות שאותן קל לאמת אך קשה לפצח. ניתן לשלוט בקושי הבעיה ע"י קביעת כמות המידע (בביטים) המעורב בה. באופן פשטני ומקורב ניתן לומר, שקושי האימות עומד ביחס ישר לגודל הבעיה, בעוד קושי הפיצוח גדל באופן מעריכי. כלומר, כל הגדלה בביט אחד מכפילה את הקושי פי 2. הוספת 2 ביטים מגדילה את הקושי פי 4; 3 ביטים מגדילים את הקושי פי 8 וכך הלאה. ניתן לבחור,למשל, גודל של 256 ביט, ואז האימות מתבצע בקלות ודורש 256 פעולות בלבד, אך פיצוח דורש 2 בחזקת 256 פעולות, כלומר 115792089237316195423570985008687907853269984665640564039457584007913129639936, ולכן אינו אפשרי גם אם כל כוח החישוב על כדור הארץ יופעל לאורך זמן הגדול מגיל היקום.
לעומת זאת, מחשב קוואנטי מבוסס על קיוביטים (Qubits, Quantum bits). בזכות תופעה פיזיקלית הקרויה "סופרפוזיציה קוואנטית", כמות קטנה של קיוביטים יכולה לייצג מידע על מספר רב של מצבים, ובכל פעולה להשפיע על כולם. בעזרת 64 קיוביטים, למשל, ניתן לעבוד על צירופים של 18446744073709551616 מצבים שונים. לכן גם בלי כמות עצומה של חומרה, ניתן לבצע חישובים שהם דימיוניים עבור מחשב קלאסי.
עם זאת, טעות נפוצה היא לחשוב שמחשב קוואנטי הוא "כמו מחשב רגיל, רק יותר מהיר". פעולת העדכון הבסיסית שניתן לעשות במחשב קוואנטי עשירה יותר, אך בשביל להנות מכך דרוש אלגוריתם שעושה בכך שימוש ספציפי. לא עבור כל בעיה קיים אלגוריתם כזה, ועבור רוב סוגי החישוב המתבצעים כיום אין במחשב קוואנטי כל יתרון.
כמו כן, בניית מחשב קוואנטי היא בעיה קשה, ובניגוד למחשב קלאסי, הגדלת מספר הקיוביטים שאיתו הוא יכול לעבוד אינו עניין פשוט כמו לבנות כמה מחשבים כאלה ולהריץ אותם במקביל. לכן סביר שנראה גידול הדרגתי בקיבולת של המחשבים הקוואנטיים בשוק, ואיתה גודל הבעיות שאיתן הם מסוגלים להתמודד.
מעבר לכך, קיימים סוגים שונים של מחשבים קוואנטיים המיועדים לפתרון בעיות ספציפיות ושאין להם היכולות של מחשב קוואנטי מלא, ועל כן בכל הודעה על פיתוח מחשב קוואנטי יש לשים לב במה מדובר ומה יכולותיו.
האלגוריתם הקוואנטי הידוע ביותר הוא אלגוריתם שור, המאפשר שיפור מעריכי בביצוע מספר פעולות חישוביות כגון פירוק מספר שלם לגורמים, ומציאת לוגריתם דיסקרטי. בהינתן מחשב קוואנטי גדול מספיק, זה מאפשר לפצח בקלות מערכות קריפטוגרפיות נפוצות כמו RSA ו-ECDSA. אם זה יקרה, כל מערכות ההצפנה בהן יש שימוש בעולם יצטרכו לעבור תכנון מחודש.
ואיך זה משפיע על ביטקוין?
אחד המרכיבים הבסיסיים במערכת הביטקוין הוא חתימות דיגיטליות מסוג ECDSA. חתימות אלה, המלוות כל פעולה, מוודאות שרק הבעלים הלגיטימיים של מטבע, המחזיק את המפתח הפרטי המתאים, יוכל להשתמש בו. מחשב קוואנטי חזק יכול לזייף חתימות אלה בקלות, ולאפשר לתוקף להשתמש במטבעות שאינם שלו.
קיימת בביטקוין מערכת המספקת הגנה מסוימת כנגד תרחיש זה. ברוב היישומים של חתימות דיגיטליות קיימת הבחנה ברורה בין מפתחות פרטיים למפתחות פומביים, שכשמם כן הם – המפתח הפרטי הוא סודי ומאפשר להוכיח את זהותך, והמפתח הפומבי גלוי לכל ומאפשר לבדוק שהוכחת הזהות תקינה. אלגוריתם שור מאפשר להסיק את המפתח הפרטי מתוך ידיעה של המפתח הפומבי (מה שאינו אפשרי עם מחשב קלאסי).
בביטקוין, גם המפתח הפומבי אינו גלוי לכל – המזהה הגלוי, הידוע גם כ"כתובת ביטקוין", הוא למעשה האש (גיבוב) של המפתח הפומבי. במעמד קבלת כספים לכתובת, לא נחשף המפתח הפומבי אלא רק ההאש, שמתוכו קשה לשחזר את המפתח הפומבי, אפילו עם מחשב קוואנטי. רק במעמד הוצאת כספים מהכתובת יש לחשוף את המפתח הפומבי (המפתח הפרטי, כמובן, לעולם אינו נחשף). לכן גם תוקף המצויד במחשב קוואנטי, לא יצליח להוציא כספים מכתובת ממנה לא הוצאו כספים בעבר.
עם זאת, קשה להסתמך על הגנה זו לאורך טווח, שכן ניתן לבצע גם התקפות מתוחכמות בהן התוקף מחכה שבעל הכתובת ישתמש בכספים בה, וימהר לנצל את המפתח הפומבי שנחשף כדי לבצע ניצול כפול לתועלתו.
לכן, כשאפשרות זו תהיה באופק, לא יהיה מנוס אלא לזנוח את חתימות ECDSA ולעבור למנגנון חתימה החסין למחשוב קוואנטי, כגון Lamport Signatures. ניתן לעבור לשימוש במנגנון זה באמצעות Soft fork, ועל כן נוכל לבצע שינוי זה בקלות יחסית אם יהיה בכך צורך.
המרכיב הבסיסי השני הוא כריה. השם הטכני של הפעולה החישובית בה כרוכה כריה היא "מציאת מקור האש חלקי". עבור בעיה זו אלגוריתם שור אינו מועיל. עם זאת, קיים אלגוריתם אחר, אלגוריתם גרובר, הנותן למחשב קוואנטי יתרון ריבועי בפתרונה. כלומר, אם מגדילים את קושי הבעיה פי 4 עבור מחשב קלאסי, עבור מחשב קוואנטי הקושי יגדל רק פי 2. לאור זאת, כנראה שמחשבים קוואנטיים יהיו רלוונטיים עבור כריה רק זמן רב לאחר שהם יאיימו על החתימות הדיגיטליות. התהליך יהיה הדרגתי, ולמשך זמן-מה מחשבים קוואנטיים וקלאסיים ישתתפו בתחרות זה לצד זה. עם זאת, ככל שהמחשבים הקוואנטיים יתפתחו ודרגת הקושי תעלה (ואיתה יחס היעילות בין מחשב קלאסי לקוואנטי), נגיע למצב שבו מחשבים קלאסיים כבר לא יוכלו לשמש עבור כריה. לא סביר שהדבר ייצור בעיה מערכתית עבור ביטקוין – יהיה רק שינוי בחומרה בה נעשה שימוש.
על נושא זה בדיוק הרצה ויטאליק בוטרין, הידוע כיום בעיקר בזכות המצאת אתריום, בביקורו בארץ לפני שלוש וחצי שנים. בסרטון מההרצאה תוכלו לצפות כאן.