מספרים אקראיים ורשתות מבוזרות: יישומים מעשיים

מבוא

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

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

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

יצירת מספרים אקראיים

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

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

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

אקראי בבלוקצ'יין

קודם כל, אדבר על בלוקצ'יין עם תמיכה בחוזים חכמים; הם אלה שיכולים לנצל באופן מלא את ההזדמנויות שמספקות אקראיות איכותית, שאין להכחישה. יתר על כן, למען הקיצור, אקרא לטכנולוגיה הזו "משואות אקראיות הניתנות לאימות פומבית" או PVRB. מכיוון ש- blockchains הן רשתות שבהן ניתן לאמת מידע על ידי כל משתתף, החלק המרכזי של השם הוא "Publicly Verifiable", כלומר. כל אחד יכול להשתמש בחישובים כדי להשיג הוכחה לכך שלמספר המתקבל שפורסם ב- blockchain יש את המאפיינים הבאים:

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

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

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

אלגוריתמים של קונצנזוס

PVRB ממלא תפקיד עצום בארגון קונצנזוס רשת. עסקאות בבלוקצ'יין מוגנות בחתימה אלקטרונית, כך ש"התקפה על עסקה" היא תמיד הכללה/החרגה של עסקה בבלוק (או מספר בלוקים). והמשימה העיקרית של אלגוריתם הקונצנזוס היא להסכים על סדר העסקאות הללו ועל סדר החסימות הכוללות את העסקאות הללו. כמו כן, מאפיין הכרחי לבלוקצ'יין אמיתי הוא סופיות - היכולת של הרשת להסכים שהשרשרת עד הבלוק הסופי היא סופית, ולעולם לא תישלל עקב הופעת מזלג חדש. בדרך כלל, על מנת להסכים כי בלוק תקף ובעיקר, סופי, יש צורך לאסוף חתימות מרוב יצרני הבלוקים (להלן BP - בלוק-יצרני), מה שדורש לפחות מסירת שרשרת הבלוקים לכל BP, ​​וחלוקת חתימות בין כל BPs. ככל שמספר ה-BPs גדל, מספר ההודעות הנחוצות ברשת גדל באופן אקספוננציאלי, לכן, אלגוריתמי קונצנזוס הדורשים סופיות, המשמשים למשל בקונצנזוס Hyperledger pBFT, אינם פועלים במהירות הנדרשת, החל מכמה עשרות BPs, הדורשים מספר עצום של קשרים.

אם יש PVRB בלתי מעורער וישר ברשת, אז, אפילו בקירוב הפשוט ביותר, אפשר לבחור את אחד מיצרני הבלוק על פיו ולמנות אותו כ"מנהיג" במהלך סבב אחד של הפרוטוקול. אם יש לנו N יצרני בלוקים, מתוכם M: M > 1/2 N ישרים, אל תצנזרו עסקאות ואל תזרקו את השרשרת לבצע התקפת "הוצאות כפולות", ואז שימוש ב-PVRB בלתי מעורער בחלוקה אחידה יאפשר לבחור מנהיג ישר עם הסתברות M / N (M / N > 1/2). אם לכל מנהיג יוקצה מרווח זמן משלו שבמהלכו הוא יכול לייצר בלוק ולאמת את השרשרת, והמרווחים הללו שווים בזמן, אזי שרשרת הבלוק של BP כנים תהיה ארוכה יותר מהשרשרת שנוצרה על ידי BPs זדוניים, ומהקונצנזוס האלגוריתם מסתמך על אורך השרשרת. פשוט יבטל את ה"רע". עיקרון זה של הקצאת פרוסות זמן שוות לכל BP יושם לראשונה ב-Graphene (קודמתה של EOS), ומאפשר סגירה של רוב הבלוקים בחתימה אחת, מה שמפחית מאוד את עומס הרשת ומאפשר לקונצנזוס זה לעבוד במהירות רבה. בהתמדה. עם זאת, רשת EOS צריכה כעת להשתמש בלוקים מיוחדים (Last Irreversible Block), אשר מאושרים על ידי החתימות של 2/3 BP. בלוקים אלה משמשים להבטיח סופיות (חוסר האפשרות של מזלג שרשרת שמתחיל לפני הבלוק האחרון הבלתי הפיך האחרון).

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

הנציג הבולט ביותר של אלגוריתמים כאלה: ouroboros מצוות Cardano, שנאמר שניתן להוכיח מתמטית נגד קנוניה של BP.

ב-Ouroboros, PVRB משמש להגדרת מה שנקרא "BP ​​Schedule" - לוח זמנים לפיו לכל BP מוקצה משבצת זמן משלו לפרסום בלוק. היתרון הגדול בשימוש ב-PVRB הוא ה"שוויון" המלא של BPs (לפי גודל המאזנים שלהם). שלמות ה-PVRB מבטיחה ש-BP זדוניים לא יכולים לשלוט בתזמון של משבצות זמן, ולכן לא יכולים לתפעל את השרשרת על ידי הכנה וניתוח של מזלגות של השרשרת מראש, וכדי לבחור מזלג מספיק להסתמך על אורך השרשרת. שרשרת, מבלי להשתמש בדרכים מסובכות לחישוב "התועלת" של BP ו"משקל" הבלוקים שלה.

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

קנה מידה ואיזון עומסים

PVRB יכול להועיל גם במשימות כמו הפחתת עומס וקנה מידה של תשלום. מלכתחילה, הגיוני להכיר את עצמך מאמרים Rivesta "כרטיסי הגרלה אלקטרוניים כתשלומי מיקרו". הרעיון הכללי הוא שבמקום לבצע 100 תשלומים של 1c מהמשלם למקבל, אתה יכול לשחק בלוטו כנה עם פרס של 1$ = 100c, כאשר המשלם נותן לבנק אחד מתוך 1 "כרטיסי ההגרלה" שלו לכל אחד. תשלום 100c. אחד מהכרטיסים הללו זוכה בצנצנת של $1, וזה הכרטיס שהנמען יכול לרשום בבלוקצ'יין. הדבר החשוב ביותר הוא ש-99 הכרטיסים הנותרים מועברים בין המקבל והמשלם ללא כל השתתפות חיצונית, בערוץ פרטי ובכל מהירות רצויה. ניתן לקרוא תיאור טוב של הפרוטוקול המבוסס על סכמה זו ברשת Emercoin כאן.

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

הבחירה במשתתף אקראי חשובה ביותר גם לפרוטוקולי ריסוק, שמטרתם להגדיל אופקית את שרשרת הבלוקים, מה שמאפשר ל-BP שונים לעבד רק את היקף העסקאות שלהם. זוהי משימה קשה ביותר, במיוחד מבחינת אבטחה בעת מיזוג רסיסים. בחירה הוגנת של BP אקראית לצורך הקצאת האחראים על רסיס ספציפי, כמו באלגוריתמים של קונצנזוס, היא גם המשימה של PVRB. במערכות מרכזיות, רסיסים מוקצים על ידי מאזן; הוא פשוט מחשב את ה-hash מהבקשה ושולח אותו למבצע הנדרש. בבלוקצ'יין, היכולת להשפיע על משימה זו יכולה להוביל למתקפה על קונצנזוס. למשל, תוכן העסקאות יכול להיות נשלט על ידי תוקף, הוא יכול לשלוט באילו טרנזקציות עוברות לרסיס שהוא שולט בו ולתפעל את שרשרת הבלוקים בו. אתה יכול לקרוא דיון על הבעיה של שימוש במספרים אקראיים עבור פיצול משימות ב-Ethereum כאן
Sharding היא אחת הבעיות השאפתניות והרציניות ביותר בתחום הבלוקצ'יין; הפתרון שלה יאפשר בניית רשתות מבוזרות בעלות ביצועים ונפח פנטסטיים. PVRB הוא רק אחד מהבלוקים החשובים לפתור אותו.

משחקים, פרוטוקולים כלכליים, בוררות

קשה להעריך יתר על המידה את תפקידם של מספרים אקראיים בתעשיית המשחקים. שימוש מפורש בבתי קזינו מקוונים, ושימוש מרומז בעת חישוב ההשפעות של הפעולה של שחקן הם כולן בעיות קשות ביותר עבור רשתות מבוזרות, שבהן אין דרך להסתמך על מקור מרכזי של אקראיות. אבל בחירה אקראית יכולה גם לפתור בעיות כלכליות רבות ולעזור לבנות פרוטוקולים פשוטים ויעילים יותר. נניח שבפרוטוקול שלנו יש מחלוקות לגבי תשלום עבור כמה שירותים זולים, והמחלוקות הללו מתרחשות לעתים רחוקות למדי. במקרה זה, אם יש PVRB בלתי מעורער, לקוחות ומוכרים יכולים להסכים לפתור מחלוקות באופן אקראי, אך בהסתברות נתונה. לדוגמה, בהסתברות של 60% שהלקוח יזכה, ובסבירות של 40% שהמוכר יזכה. גישה זו, שהינה אבסורדית מהבחינה הראשונה, מאפשרת לפתור מחלוקות באופן אוטומטי עם נתח ניצחונות/הפסדים שניתן לצפות אותו בדיוק, המתאים לשני הצדדים ללא כל השתתפות של צד שלישי ובזבוז זמן מיותר. יתר על כן, יחס ההסתברות יכול להיות דינמי ותלוי במשתנים גלובליים מסוימים. לדוגמה, אם חברה מצליחה, יש לה מספר נמוך של מחלוקות ורווחיות גבוהה, החברה יכולה להעביר אוטומטית את ההסתברות לפתרון סכסוך לכיוון ממוקד לקוח, למשל 70/30 או 80/20, ולהיפך, אם סכסוכים לוקחים הרבה כסף והם הונאה או לא מספקים, אתה יכול להעביר את ההסתברות לכיוון השני.

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

איפה מוצאים את האקראי הנכון?

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

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

מקור: www.habr.com