אקראיות ציבורית הוא מרכיב חיוני בפרוטוקולי אבטחה רבים בעולם האמיתי. ביישומים מסוימים, כמו הימורים ומשחקים מרובי משתתפים, האקראיות מוסיפה כיף. ביישומים אחרים, אקראיות מספקת דרך הוגנת להקצאת משאבים בלתי ניתנים לחלוקה, החל מכרטיסים ירוקים, דרך הקצאת שופטים של בית המשפט המחוזי לתיקים, וכלה ב-Seding בטורנירי ספורט. הוא משמש גם להקצאה שלילי משאבים, כמו ביקורת מס או בדיקה ביטחונית משנית בשדה התעופה.
באופן מסורתי, סמכנו על רשויות מהימנות כדי ליצור אקראיות עבור הפרוטוקולים האלה, אבל בעולם ה-web3, נצטרך להשתפר. בפוסט זה, נחקור גישות לבניית אקראיות הניתנת לאימות פומבי באמצעות חילקו משואות אקראיות ולאחר מכן לדון בכמה יישומים ברשת. (חלק ב', שעתיד לצאת, יתמקד במיוחד בבחירת מנהיג, תוך מתן הערכה של גישות לבחירת מנהיג חלופי.)
נכסים רצויים
יצירת מספרים אקראיים היא משימה עדינה ידועה לשמצה. לדוגמה, מפתחות קריפטוגרפיים רבים הודלפו בגלל שהם הסתמך על מחולל מספרים אקראיים פגום (עבורו הקיר של Cloudflare של מנורות לבה היה משמש כאמצעי הקלה יצירתי). זה פשוט אקראיות פרטיתעם זאת, כאשר רק צד אחד צריך ליצור ולהשתמש בו.
אקראיות ציבורית, לעומת זאת, היא תהליך רב צדדי, מה שמוסיף במידה ניכרת לקושי. לפרוטוקול טוב להפקת אקראיות ציבורית יהיו מאפייני האבטחה הבאים:
- בלתי משוחד: אף תוקף, או קואליציה של תוקפים, לא אמורים להיות מסוגלים להטות את הפלט.
- אמין: אף תוקף לא אמור להיות מסוגל למנוע מהפרוטוקול לייצר פלט.
- ניתן לאמת: כל אחד יכול לאמת בקלות את פלט הפרוטוקול, ואמור לראות את אותו פלט כמו כולם.
- בלתי צפוי: אם הפרוטוקול מייצר פלט בזמן T1, אף אחד לא אמור להיות מסוגל לחזות שום דבר לגבי הפלט לפני זמן מה T0<T1, באופן אידיאלי עם T0 קרוב מאוד ל T1.
חוסר משוא פנים הוא מאפיין חלש יותר מחוסר משוא פנים מכיוון שכל פרוטוקול שאינו ניתן לחיזוי חייב להיות בלתי משוחד. מדעני מחשב יאמרו חוסר משוא פנים מפחית לחוסר חיזוי, כי אם אתה יכול להטות, אתה יכול לחזות. אבל לפעמים נרצה לנמק אותם בנפרד כי הם עשויים להסתמך על הנחות שונות - למשל, רוב לא ישר עלול לחזות את התוצאה, אבל לא להטות אותה.
בנוסף למאפיינים אלה, הפרוטוקול צריך להיות יעיל להפעלה ולייצר מספר רב של ביטים אקראיים. (בפועל, לעתים קרובות זה מספיק ליישומים לייצר 128 סיביות אקראיות, תוך שימוש בהם כדי ליצור מחולל מספרים פסאודו-אקראיים [PNRG] כדי להוציא יותר סיביות לפי הצורך. עם זאת, אי-חיזוי אמור להחזיק עבור כל סיביות בודדות של הפלט כדי להיות שמיש עבור כאלה יישומים כמו הגרלות או הקצאת משאבים.) הפרוטוקול צריך להיות יעיל גם מבחינת עלויות תקשורת וחישוב.
פרוטוקולים שונים עשויים להשיג תכונות אלה בתנאים שונים. לדוגמה, פרוטוקולים מסוימים עשויים להיות בלתי משוחדים על ידי כל קואליציה של f1 צמתים זדוניים ובלתי צפויים על ידי כל קואליציה של f2<f1 צמתים זדוניים. יש גם דרגות שונות של הטיה. לדוגמה, בפרוטוקולים מסוימים משתתף עשוי להטות את הפלט ב"ביט אחד" - כלומר הם יכולים לבחור בין אחד משני פלטים אפשריים. התקפות אחרות עשויות לאפשר להם לתקן את הפלט לחלוטין. עם זאת, בדרך כלל, אנחנו לא רוצים לסבול שום הטיה (או יכולת חיזוי) בכלל.
האידיאל הקריפטוגרפי: Rמשואות אנדומיות
קריפטוגרפים מתחילים לעתים קרובות בחשיבה על פתרון אידיאלי לבעיות שלהם. במקרה של אקראיות ציבורית, א משואה של אקראיות הוא שירות אידאלי המייצר באופן קבוע פלט אקראי העומד בכל דרישות האבטחה הדרושות.
מגדלור אקראיות אידיאלי כזה, בדומה להפשטות קריפטוגרפיות אחרות - כמו אורקלים אקראיים או מודל הקבוצות הגנרי - לא קיים בעולם האמיתי. אבל זו מטרה שימושית לשאוף אליה ומודל שימושי להגיון לגבי פרוטוקולים המסתמכים על אקראיות ציבורית.
אנו יכולים לשקול כמה קירובים של משואה אקראיות אידיאלית.
- משואות מרכזיות: הגישה הקלה ביותר ליצירת אקראיות טובה היא באמצעות צד שלישי מרוכז עם שירותים כמו משואה אקראיות NIST or random.org, אשר יוצר אקראיות מרעש אטמוספרי ומוסמכת לשימוש בהימורים. הסתמכות זו על צד שלישי מערערת לחלוטין את פילוסופיית הביזור. ואכן, בדוגמה שלמעלה עלינו לסמוך על כך שהארגונים הרלוונטיים מייצרים אקראיות בצורה נכונה, ללא כל הוכחה קריפטוגרפית.
- מציג אקראיות פיזית: הגרלות מסורתיות רבות מסתמכות על תצוגה פומבית, שעשויה לכלול, למשל, מישהו שמושיט יד לתוך מיכל של כדורי פינג פונג עם מספרים שונים עליהם. למרבה הצער, לעתים קרובות ניתן לתמרן אותם בקלות. לדוגמה, כדורים מסוימים ניתן להכניס למקפיא ו ניתן לומר לבורר לבחור את הקרים.
- משואות טבעיות: רעיון נפוץ הוא להשתמש בתופעות טבע אקראיות כמו מזג אוויר או קרינת רקע קוסמית כמגדלור. למרבה הצער, כל המקורות המוצעים אינם מספקים קונצנזוס חזק. משקיפים שונים יראו ערכים מעט שונים, מה שמצריך הצגת מחדש של גורם מהימן כדי לבצע מדידה רשמית, עם כל החסרונות של משואה מרוכזת.
- משואות חצי מרכזיות: גישה טובה יותר תהיה לקבל את האקראיות כותרות בלוק ביטקוין ישירות או מ מחירי הסגירה של המניות, שקל יותר לאימות בפומבי וקשה יותר לכל צד אחד לשלוט בו באופן מוחלט. עם זאת, עדיין קיימות התקפות עדינות על שניהם אקראיות בלוקצ'יין הוכחת עבודה ו אקראיות של מחיר המניה. עם כותרות בלוקצ'יין, למשל, כורים יכולים לבחור למנוע בלוקים שהכותרות שלהם מייצרות ערך מגדלור שהם לא אוהבים. או שהם יכולים לבחור לנתק קשרים כאשר שני בלוקים מתנגשים מתגלים בהתבסס על פלט המשואות המועדף עליהם.
משואות אקראיות מבוזרות (DRBs)
גישה טבעית לבעיות של משואות ריכוזיות היא עיצוב פרוטוקול קריפטוגרפי מבוזר להפקת אקראיות ציבורית. בעיה זו דומה קצת לתכנון פרוטוקולי קונצנזוס מבוזרים, רק קשה יותר. לא רק שכל המשתתפים צריכים להסכים על פלט (האקראיות), אלא שאמור להיות בלתי אפשרי עבור משתתף זדוני בפרוטוקול להטות או לחזות את הפלט.
פרוטוקולים שנועדו לדמות משואת אקראיות נקראים משואות אקראיות מבוזרות (DRBs). (שמות אחרים כוללים "הטלת מטבעות מבוזרת"). הבעיה נחקרה במשך עשרות שנים, עם תוצאות בלתי אפשריות מפורסמות שהוכחו בשנות ה-1980, אבל העניין עלה מחדש בעידן הבלוקצ'יין. ניתן להשתמש ב-DRBs כדי לספק אקראיות על השרשרת, שתהיה מרכיב מפתח ליישומים הוגנים, מאובטחים ושקופים על השרשרת.
הגישה הקלאסית: פרוטוקולי התחייבות-חשיפה
פרוטוקול פשוט מאוד של שני סיבובים מספיק עבור DRB במקרה האופטימי. בסיבוב 1, כל משתתף i יוצר ערך אקראי ri ומפרסם התחייבות קריפטוגרפית ci=לְבַצֵעַ(ri). באפליקציה זו, ההתחייבות יכולה להיות פשוט פונקציית Hash כמו SHA-256. לאחר פרסום ההתחייבות של כל משתתף, הוא ננעל על בחירתו ri, אך ההתחייבויות אינן חושפות מידע על תרומות של משתתפים אחרים. בסיבוב 2, כל משתתף "פותח את המחויבות שלו" בפרסום ri. כל הערכים האקראיים משולבים לאחר מכן, למשל על ידי XOR ביצוע שלהם או (רצוי) גיבוב של שרשרתם.
פרוטוקול זה פשוט ומייצר פלט משואות אקראי כל עוד אחד מהמשתתפים בוחר את שלו ri באופן אקראי. לרוע המזל, הוא סובל מפגם קלאסי: כאשר כל המשתתפים מלבד אחד חשפו את ערכם האקראי, המשתתף האחרון מסוגל לחשב את פלט המשואות המשוער. אם זה לא ימצא חן בעיניהם, הם יכולים לסרב לפרסם את ערכם, ולבטל את הפרוטוקול. התעלמות מתרומת משתתף פגומה לא פותרת את הבעיה, כי זה עדיין נותן לתוקף את הבחירה בין שתי יציאות משואות (אחד מחושב עם תרומתם ואחד בלי).
בלוקצ'יין מציעים תרופה טבעית לבעיה זו: ניתן לדרוש מכל משתתף לשים כמה כספים בנאמנות שנתפסו אם הם לא חושפים את תרומתם האקראית. זו הייתה בדיוק הגישה שנקטה הקלאסי RANDAO מגדלור על Ethereum. החיסרון של גישה זו הוא שהפלט עדיין יכול להיות מוטה, מה שעשוי להיות משתלם כלכלית עבור התוקף אם הכסף בנאמנות קטן מסכום הכסף שרוכב על תוצאת המשואה. אבטחה טובה יותר מפני התקפות הטיה מחייבת לשים יותר מטבעות בנאמנות.
פרוטוקולי התחייבות-חושפים-שחזור
במקום לנסות לאלץ את כל הצדדים לחשוף את תרומתם האקראית, חלק מהפרוטוקולים כוללים מנגנון התאוששות כך שגם אם מיעוט מהמשתתפים נושר, השאר יוכלו להשלים את הפרוטוקול. חשוב שהפרוטוקול יפיק את אותה תוצאה בכל מקרה, כך שצדדים לא יוכלו להטות את התוצאה על ידי בחירה אם לנשור או לא.
אחת הדרכים להשיג זאת היא שכל משתתף יספק לאחרים חלק מהסוד שלו, כך שרובם יוכלו לשחזר אותו, באמצעות, למשל, שיתוף הסוד של שמיר. מאפיין חשוב, לעומת זאת, הוא שהאחרים יכולים לאמת שהסוד שבוצע שותף כראוי, מה שמחייב שימוש בפרימיטיבי חזק יותר הנקרא שיתוף סוד בר אימות (PVSS).
מספר מנגנוני התאוששות אחרים אפשריים, אך לכולם יש את אותה מגבלה. אם יש N משתתפים, ואנחנו רוצים חוסן אם יש קבוצה של עד f צמתים נושרים, אז זה חייב להיות המקרה שכל קבוצה של Nf המשתתפים יכולים לחשב את התוצאה הסופית. אבל זה אומר גם קואליציה זדונית של Nf המשתתפים יכולים לחזות את התוצאה מראש על ידי הדמיה פרטית של מנגנון השחזור. זה יכול לקרות גם במהלך הסיבוב הראשון של הפרוטוקול, שבמהלכו קואליציה כזו יכולה לשנות את בחירות האקראיות שלה ולהטות את התוצאה.
במילים אחרות, זה אומר כל קואליציה של Nf צמתים חייבים לכלול לפחות צומת כנה אחד. לפי אלגברה פשוטה, Nf > f, כך f < N/2, והפרוטוקולים הללו דורשים מטבעם רוב ישר. זהו הבדל משמעותי למודל האבטחה המקורי של commit-reveal, שמצריך רק f<N (לפחות משתתף ישר אחד).
פרוטוקולים אלה דורשים לעתים קרובות גם עלויות תקשורת משמעותיות כדי לשתף את מידע ה-PVSS הנוסף בין כל הצמתים בכל הפעלה של הפרוטוקול. קהילת המחקר עשתה עבודה רבה על בעיה זו בשנים האחרונות, עם הצעות מחקר כוללות RandShare, לְגַרֵד, SecRand, עשב, או אלבטרוס, אבל נראה שאף אחד לא ראה פריסה בעולם האמיתי.
פרוטוקולים אקראיים מבוססי פונקציות הניתנים לאימות
מבין שקבוצה של Nf המשתתפים יכולים לחשב את ערך המשואה האקראי בפרוטוקול הנ"ל מוביל לגישה קצת יותר פשוטה: שתפו מפתח סודי לטווח ארוך בין N הצדדים ובקשו מהם להשתמש בו כדי להעריך א פונקציה אקראית הניתנת לאימות (VRF). המפתח הסודי משותף באמצעות a t-מחוץ-N ערכת סף, כך שכל t המשתתפים יכולים לחשב את ה-VRF (אבל קואליציה קטנה יותר לא יכולה). ל t=Nf, זה מספק את אותה גמישות f צמתים זדוניים כמו פרוטוקולי התחייבות-חושפים-שחזור שנדונו לעיל.
גמישות היו חלוצים בגישה זו כחלק מפרוטוקול הקונצנזוס שלהם באמצעות חתימות סף BLS (המתפקדות כ-VRF). העצמאי לסובב משואת האקראיות משתמשת בעצם באותה גישה, עם קבוצה של משתתפים בסף-BLS-חתימה על מונה בכל סיבוב. ה ליגת האנטרופיה הוא מופע קוד פתוח של דרנד המייצר אקראיות כל 30 שניות באמצעות 16 צמתים משתתפים (נכון לספטמבר 2022), המנוהל על ידי שילוב של חברות וקבוצות מחקר אוניברסיטאות.
החיסרון של גישות אלו הוא שאתחול מפתח הסף מורכב יחסית, וכך גם הגדרה מחדש של המפתח כאשר צמתים מצטרפים או עוזבים. במקרה הנפוץ, עם זאת, הפרוטוקולים יעילים מאוד.
כפי שתואר לעיל, עצם החתימה על ערך מונה אינה מוסיפה אקראיות חדשה לכל סיבוב, כך שאם מספר מספיק של מפתחות המשתתפים נפגע, אז הפרוטוקול יהיה צפוי בכל סיבוב עתידי.
Chainlink VRF משלב גישה זו (באמצעות NSEC5 VRF) עם מקור חיצוני לאקראיות שצוין על ידי צדדים המבקשים אקראיות, בדרך כלל כותרת בלוקצ'יין עדכנית בפועל. נתונים אלה מוזנים לאחר מכן דרך VRF אשר מנוהל על ידי צד אחד או סף לקבוצה.
של אתריום שרשרת ביקון משתמש כרגע ב-VRF מבוססי BLS: המציע של כל סיבוב מוסיף את ערך ה-VRF שלו לתמהיל. זה חוסך סבב של תקשורת בהשוואה לפרדיגמת ה-commit-reveal (בהנחה שמפתח ציבורי BLS לטווח ארוך נרשם פעם אחת), אם כי עיצוב זה יורש כמה סייגים של גישת ה-commit-reveal כולל האפשרות להטות את הפלט של ה-Beacon על ידי מניעת פלט .
פרוטוקולים מבוססי פונקציות השהייה הניתנים לאימות
לבסוף, כיוון חדש ומבטיח הוא שימוש בקריפטוגרפיה מבוססת זמן, במיוחד פונקציות השהיה הניתנות לאימות (VDFs). גישה זו מבטיחה לספק יעילות תקשורת טובה וחוסן עם חוסן N-1 צמתים זדוניים.
אם נחזור לפרוטוקול ה-commit-reveal המקורי, ניתן להחליף התחייבויות מסורתיות התחייבויות מתוזמנות לבטל את בעיית המשתתפים שמסרבים לחשוף את תרומתם האקראית. התחייבויות מתוזמנות יכולות להיפתח ביעילות על ידי המחויב המקורי, או על ידי כל מי שמוכן לחשב פונקציה איטית (בעצם VDF). לפיכך, אם משתתף כלשהו נושר מפרוטוקול של גילוי התחייבות, המחויבות שלו עדיין יכולה להיפתח על ידי אחרים. זה חיוני שהזמן המינימלי לפתיחת ההתחייבות יהיה מספיק ארוך כדי שלא ניתן לעשות את זה במהלך הסיבוב הראשון (שלב ההתחייבות) של הפרוטוקול, אחרת משתתפים זדוניים עלולים לפתוח התחייבויות של אחרים מהר מספיק כדי לשנות את התרומה שלהם ולהטות את התוצאה .
פרוטוקול סיבוב אחד אלגנטי אפילו יותר אפשרי עם VDFs מודרניים: עזוב את ההתחייבות לחלוטין. כל משתתף יכול פשוט לפרסם את תרומתו האקראית ri, והתוצאה הסופית היא שילוב של תרומתו של כל משתתף, המופעל דרך VDF. עיכוב הזמן בחישוב ה-VDF מבטיח שאף אחד לא יוכל לבחור את המחויבות שלו בצורה שתטה את הפלט הסופי. גישה זו הוצעה כ UNICORN מאת Arjen Lenstra ובנג'מין Wesolowski בשנת 2015, ואכן היה יישום מניע מרכזי ב- פיתוח של VDFs.
גישה זו ראתה פריסה מעשית מסוימת. Chia מיישמת גרסה של זה כחלק מפרוטוקול הקונצנזוס שלה, תוך שימוש ב-VDF של ריבוע חוזר בקבוצות כיתה. סטארקוור יישם א משואה מבוססת VDF הוכחת קונספט באמצעות VDFs מבוססי SNARK. Ethereum גם מתכנן כדי להשתמש הגישה הזו, בניית ASIC ייעודי לחישוב VDFs ליצירת אקראיות בשכבת הקונצנזוס.
***
אקראיות ציבורית היא מרכיב חיוני של פרוטוקולים רבים, אך עדיין חסר לנו כל DRB סטנדרטי המספק אבטחה גבוהה. חלל העיצוב גדול ומתאפשרים הכלאות ושילובים רבים של הגישות הנ"ל. לדוגמה, ניתן לשלב פרוטוקול מבוסס VRF עם פרוטוקול מבוסס VDF, המוסיף אנטרופיה חדשה, למשל, כפי שהוצע על ידי ראנדראנר. שרשרת ה-Beacon של Ethereum משתמשת כיום ב-VRF, אם כי היא עשויה להוסיף VDFs בעתיד כדי למנוע את האפשרות של הטיה מהתקפות חסימת חסימות.
זו גם שאלה פתוחה כאשר פרוטוקולים של רוב ישרים מקובלים. עבור קבוצת משתתפים קטנה יחסית ובדוקה - כמו ליגת האנטרופיה - הנחת רוב כנה היא סבירה. מצד שני, לפרוטוקולים שמצריכים רק משתתף ישר בודד יש יתרון מובנה - יותר משתתפים יכולים רק לשפר את האבטחה. משמעות הדבר היא שניתן לפרוס פרוטוקולים אלה עם השתתפות פתוחה ללא הרשאות.
בחלק השני, נדון ביישום הספציפי של בחירה אקראית של מנהיגים בפרוטוקולי קונצנזוס, שיש להם יעדי עיצוב שונים במקצת, וכתוצאה מכך ראו אפילו יותר פרוטוקולים וגישות שהוצעו.
***
ג'וזף בונו הוא שותף מחקר ב-a16z crypto. המחקר שלו מתמקד בקריפטוגרפיה יישומית ואבטחת בלוקצ'יין. הוא לימד קורסי מטבעות קריפטוגרפיים באוניברסיטת מלבורן, NYU, סטנפורד ופרינסטון, וקיבל תואר דוקטור במדעי המחשב מאוניברסיטת קיימברידג' ותואר BS/MS מסטנפורד.
ולריה ניקולאנקו הוא שותף מחקר ב-a16z crypto. המחקר שלה מתמקד בקריפטוגרפיה ואבטחת בלוקצ'יין. היא גם עבדה על נושאים כמו התקפות ארוכות טווח בפרוטוקולי קונצנזוס PoS, סכימות חתימה, אבטחה פוסט-קוונטית ומחשוב מרובה צדדים. היא בעלת תואר דוקטור בקריפטוגרפיה מאוניברסיטת סטנפורד בייעוץ של פרופסור דן בונה, ועבדה על הבלוקצ'יין Diem כחלק מצוות המחקר המרכזי.
***
עורך: טים סאליבן
***
הדעות המובעות כאן הן אלה של אנשי AH Capital Management, LLC ("a16z") המצוטטות ואינן הדעות של a16z או החברות הקשורות לה. מידע מסוים הכלול כאן התקבל ממקורות צד שלישי, כולל מחברות פורטפוליו של קרנות המנוהלות על ידי a16z. למרות שנלקחה ממקורות האמינים כאמינים, a16z לא אימתה מידע כזה באופן עצמאי ואינה מציגה מצגים לגבי הדיוק המתמשך של המידע או התאמתו למצב נתון. בנוסף, תוכן זה עשוי לכלול פרסומות של צד שלישי; a16z לא סקרה פרסומות כאלה ואינה תומכת בתוכן פרסומי כלשהו הכלול בהן.
תוכן זה מסופק למטרות מידע בלבד, ואין להסתמך עליו כייעוץ משפטי, עסקי, השקעות או מס. עליך להתייעץ עם היועצים שלך באשר לעניינים אלה. הפניות לניירות ערך או לנכסים דיגיטליים כלשהם נועדו למטרות המחשה בלבד, ואינן מהוות המלצת השקעה או הצעה לספק שירותי ייעוץ השקעות. יתר על כן, תוכן זה אינו מכוון ואינו מיועד לשימוש על ידי משקיעים או משקיעים פוטנציאליים כלשהם, ואין להסתמך עליו בשום פנים ואופן בעת קבלת החלטה להשקיע בקרן כלשהי המנוהלת על ידי a16z. (הצעה להשקעה בקרן a16z תתבצע רק על ידי מזכר ההנפקה הפרטית, הסכם המנוי ותיעוד רלוונטי אחר של כל קרן כזו ויש לקרוא אותה במלואה). המתוארים אינם מייצגים את כל ההשקעות בכלי רכב המנוהלים על ידי a16z, ואין כל ודאות שההשקעות יהיו רווחיות או שלהשקעות אחרות שיבוצעו בעתיד יהיו מאפיינים או תוצאות דומות. רשימה של השקעות שבוצעו על ידי קרנות המנוהלות על ידי אנדריסן הורוביץ (למעט השקעות שעבורן המנפיק לא נתן אישור ל-a16z לחשוף בפומבי וכן השקעות בלתי מוקדמות בנכסים דיגיטליים הנסחרים בבורסה) זמינה בכתובת https://a16z.com/investments /.
תרשימים וגרפים המסופקים בתוכן הם למטרות מידע בלבד ואין להסתמך עליהם בעת קבלת החלטת השקעה כלשהי. ביצועי העבר אינם מעידים על תוצאות עתידיות. התוכן מדבר רק לתאריך המצוין. כל תחזיות, אומדנים, תחזיות, יעדים, סיכויים ו/או דעות המובעות בחומרים אלו כפופים לשינויים ללא הודעה מוקדמת ועשויים להיות שונים או מנוגדים לדעות שהובעו על ידי אחרים. אנא ראה https://a16z.com/disclosures למידע חשוב נוסף.
