האם אפשר ליצור מספרים אקראיים אם אנחנו לא סומכים אחד על השני? חלק 1

היי הבר!

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

מדוע יהיה צורך לייצר מספרים אקראיים בקרב משתתפים שאינם סומכים זה על זה? תחום יישומים אחד הוא יישומים מבוזרים. לדוגמה, אפליקציה שמקבלת הימור ממשתף ומכפילה את הסכום בהסתברות של 49% או לוקחת משם בהסתברות של 51% תעבוד רק אם היא יכולה לקבל ללא משוא פנים מספר אקראי. אם תוקף יכול להשפיע על התוצאה של מחולל המספרים האקראיים, ואפילו להגדיל מעט את הסיכוי שלו לקבל תשלום באפליקציה, הוא יהרוס אותה בקלות.

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

1. הוא חייב להיות חסר פניות. במילים אחרות, אף משתתף לא אמור להשפיע בשום אופן על התוצאה של מחולל המספרים האקראיים.

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

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

במאמר זה נסתכל על שתי גישות: RANDAO + VDF וגישת קודי המחיקה. בחלק הבא נבחן בפירוט את הגישה המבוססת על חתימות סף.

אבל ראשית, בואו נסתכל על אלגוריתם פשוט ונפוץ שהוא בר קיימא, בלתי צפוי, אבל מוטה.

RANDAO

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

השלב של פרסום ה-hashs לפני חשיפת המספרים הוא הכרחי כדי שהתוקף לא יוכל לבחור את המספר שלו לאחר שראה את המספרים של המשתתפים האחרים. זה יאפשר לו לקבוע למעשה לבד את הפלט של מחולל המספרים האקראיים.

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

איזה מהמאפיינים שתיארנו למעלה יש ל-RANDAO? זה בלתי צפוי, יש לו אותה חיוניות כמו פרוטוקול הקונצנזוס הבסיסי, אבל הוא מוטה. באופן ספציפי, תוקף יכול לצפות ברשת, ולאחר שמשתתפים אחרים חושפים את המספרים שלהם, הוא יכול לחשב את ה-XOR שלהם, ולהחליט אם לחשוף את המספר שלו או לא כדי להשפיע על התוצאה. למרות שזה מונע מהתוקף לקבוע לבד את הפלט של מחולל המספרים האקראיים, זה עדיין נותן לו 1 ביט של השפעה. ואם תוקפים שולטים במספר משתתפים, אז מספר הביטים שהם שולטים יהיה שווה למספר המשתתפים בשליטתם.

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

RANDAO+VDF

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

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

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

פיתוח VDFs טוב הוא קשה ביותר. היו כמה פריצות דרך לאחרונה, למשל. זה и זֶה, מה שהפך את VDF למעשי יותר בפועל, ו-Ethereum 2.0 מתכנן להשתמש ב-RANDAO עם VDF כמקור מספר אקראי בטווח הארוך. מלבד העובדה שגישה זו אינה ניתנת לחיזוי וללא פניות, יש לה יתרון נוסף בכך שהיא בת קיימא אם לפחות שני משתתפים זמינים ברשת (בהנחה שפרוטוקול הקונצנזוס בו נעשה שימוש הוא בר קיימא כאשר מתמודדים עם מספר כה קטן של משתתפים).

האתגר הגדול ביותר של גישה זו הוא הגדרת ה-VDF כך שאפילו משתתף עם חומרה מיוחדת ויקרה מאוד לא יוכל לחשב את ה-VDF לפני תום שלב הגילוי. באופן אידיאלי, לאלגוריתם צריך להיות אפילו מרווח בטיחות משמעותי, נניח פי 10. האיור שלהלן מציג התקפה של שחקן שיש לו ASIC מיוחד המאפשר לו להפעיל VDF מהר יותר מהזמן שהוקצב לחשיפת אישור ה-RANDAO. משתתף כזה עדיין יכול לחשב את התוצאה הסופית באמצעות או לא באמצעות המספר שלו, ולאחר מכן, על סמך החישוב, לבחור אם להציג אותו או לא.

עבור משפחת VDF שהוזכרה לעיל, הביצועים של ASIC ייעודי יכולים להיות גבוהים פי 100+ מחומרה רגילה. אז אם שלב הפריסה נמשך 10 שניות, אז ה-VDF המחושב ב-ASIC כזה חייב לקחת יותר מ-100 שניות כדי לקבל מרווח בטיחות של פי 10, ולפיכך אותו VDF המחושב על חומרת סחורה חייב לקחת 100x 100 שניות = ~3 שעות.

קרן Ethereum מתכננת לפתור בעיה זו על ידי יצירת ASIC זמינים לציבור וחינמיים משלה. ברגע שזה קורה, כל שאר הפרוטוקולים יכולים גם לנצל את הטכנולוגיה הזו, אבל עד אז גישת RANDAO+VDF לא תהיה ברת קיימא עבור פרוטוקולים שאינם יכולים להשקיע בפיתוח ASIC משלהם.

מאמרים רבים, סרטונים ומידע אחר על VDF נאסף על אתר זה.

אנו משתמשים בקודי מחיקה

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

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

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

2. המשתתפים משתמשים בסוג של קונצנזוס כדי להגיע להסכמה על סטים מקודדים מ-67 משתתפים ספציפיים.

3. ברגע שהושג הסכמה, כל משתתף לוקח את השיתופים המקודדים בכל אחת מ-67 הקבוצות המוצפנות במפתח הציבורי שלהם, מפענח את כל השיתופים הללו ומפרסם את כל השיתופים המפוענחים הללו.

4. לאחר ש-67 משתתפים סיימו את שלב (3), ניתן לפענח ולבנות מחדש את כל הקבוצות המוסכמות בשל המאפיינים של קודי מחיקה, וניתן לקבל את המספר הסופי כ-XOR של השורות הראשוניות שהמשתתפים התחילו איתן ב-(1) .

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

מה קורה אם בשלב (1) אחד המשתתפים שלח שיתופים מקודדים למשתתפים האחרים שאינם קוד המחיקה הנכון עבור מחרוזת כלשהי? ללא שינויים נוספים, משתתפים שונים לא יוכלו לשחזר את המחרוזת כלל, או שהם ישחזרו מחרוזות שונות, מה שיגרום לכך שמשתתפים שונים יקבלו מספר אקראי שונה. כדי למנוע זאת, אתה יכול לעשות את הפעולות הבאות: כל משתתף, בנוסף למניות המקודדות, גם מחשב עץ מרקלה את כל השיתופים הללו, ושולחת לכל משתתף הן את הנתח המקודד עצמו והן את שורש עץ המרקל, והוכחה להכללת המניות בעץ המרקל. בקונצנזוס בשלב (2), המשתתפים לא רק מסכימים על קבוצה של קבוצות, אלא על קבוצה של שורשים ספציפיים של עצים כאלה (אם חלק מהמשתתפים חרג מהפרוטוקול, ושלח שורשי עצי מרקל שונים למשתתפים שונים, ושני שורשים כאלה מוצגים במהלך קונצנזוס, השורה שלו אינה כלולה בערכת התוצאות). כתוצאה מהקונצנזוס, יהיו לנו 67 שורות מקודדות והשורשים התואמים של עץ המרקל כך שיהיו לפחות 67 משתתפים (לאו דווקא אותם אלו שהציעו את השורות המתאימות), אשר עבור כל אחת מ-67 השורות יש הודעה עם נתח של קוד המחיקה, והוכחה שהתרחשות חלקם בעץ המתאים התפוגגה.

כאשר בשלב (4) המשתתף מפענח 67 פעימות עבור מיתר מסוים ומנסה לשחזר מהם את המיתר המקורי, אחת האפשרויות אפשרית:

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

2. השורה משוחזרת, אך השורש המחושב המקומי אינו תואם את השורש שבו הושגה הסכמה.

3. השורה לא משוחזרת.

קל להראות שאם אפשרות (1) התרחשה עבור לפחות משתתף אחד למעלה, אז אפשרות (1) התרחשה עבור כל המשתתפים, ולהיפך, אם אפשרות (2) או (3) התרחשה עבור משתתף אחד לפחות, אז לכל המשתתפים תתרחש אפשרות (2) או (3). לפיכך, עבור כל שורה בסט, או שכל המשתתפים ישחזרו אותה בהצלחה, או שכל המשתתפים לא יצליחו לשחזר אותה. המספר האקראי המתקבל הוא אז XOR של השורות בלבד שהמשתתפים הצליחו לשחזר.

חתימות סף

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

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

יישום נפוץ עבור חתימות BLS בפרוטוקולי בלוקצ'יין, בנוסף ליצירת מספרים אקראיים, הוא חתימת בלוק בפרוטוקולי BFT. נניח ש-100 משתתפים יוצרים בלוקים, ובלוק נחשב סופי אם 67 מהם חותמים עליו. כולם יכולים להגיש את החלקים שלהם בחתימת BLS ולהשתמש באלגוריתם קונצנזוס כלשהו כדי להסכים על 67 מהם ואז למזג אותם לחתימת BLS אחת. ניתן להשתמש בכל 67 (או יותר) חלקים ליצירת החתימה הסופית, אשר תהיה תלויה באילו 67 חתימות שולבו ולכן עשויות להשתנות, למרות שבחירות שונות של 67 המשתתפים ייצרו חתימה שונה, כל חתימה כזו תהיה תקפה חתימה לבלוק. המשתתפים הנותרים אז צריכים לקבל ולאמת רק חתימה אחת לכל בלוק, במקום 67, דרך הרשת, מה שמפחית משמעותית את העומס על הרשת.

מסתבר שאם המפתחות הפרטיים שבהם משתמשים המשתתפים נוצרים בצורה מסוימת, אז לא משנה אילו 67 חתימות (או יותר, אך לא פחות) יצטברו, החתימה שתתקבל תהיה זהה. זה יכול לשמש כמקור לאקראיות: המשתתפים מסכימים תחילה על הודעה כלשהי שהם יחתמו (זה יכול להיות הפלט של RANDAO או רק ה-hash של הבלוק האחרון, זה לא באמת משנה כל עוד הוא משתנה בכל פעם והוא עקבי) וליצור עבורו חתימת BLS. תוצאת הדור תהיה בלתי צפויה עד ש-67 משתתפים יספקו את חלקיהם, ולאחר מכן התפוקה כבר נקבעה מראש ואינה יכולה להיות תלויה בפעולות של כל משתתף.

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

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

לסיכום

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

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

אתה יכול לראות איך נראה פיתוח עבור NEAR ולהתנסות ב-IDE המקוון כאן.

אתה יכול לעקוב אחר כל החדשות ברוסית בכתובת קבוצת טלגרם ו - קבוצה ב-VKontakte, ובאנגלית ברשמי טוויטר.

נתראה בקרוב!

מקור: www.habr.com