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

היי הבר!

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

בחלק זה של המאמר, נסתכל מקרוב על גישה אחרת המשתמשת בחתימות סף.

קצת קריפטוגרפיה

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

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

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

2. יודע רק את הנקודה G והמוצר שלו עם סקלאר xG לא ניתן לחשב x.

נשתמש גם במושג פולינום p (x) степени k-1. בפרט, נשתמש בתכונה הבאה של פולינומים: אם אנחנו יודעים את הערך p (x) לכל k אחר x (ואין לנו מידע נוסף על p (x)), נוכל לחשב p (x) עבור כל אחד אחר x.

זה מעניין עבור כל פולינום p (x) ונקודה כלשהי על העקומה Gלדעת את המשמעות p(x)G לכל k משמעויות שונות x, אנחנו יכולים גם לחשב p(x)G לכל x.

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

מחולל מספרים אקראיים על חתימות סף

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

נניח שיש פולינום כזה p (x) степени k-1 מה שהמשתתף הראשון יודע p (1), השני יודע p(2), וכולי (n-ה יודע P n)). אנו גם מניחים זאת עבור איזו נקודה ידועה מראש G כולם יודעים p(x)G לכל הערכים x. אנחנו נתקשר פאי) "רכיב פרטי" iהמשתתף ה' (כי רק iהמשתתפת ה' מכירה אותה), ו חֲזִיר "מרכיב ציבורי" iמשתתפת -ה (כי כל המשתתפים מכירים אותה). כזכור, ידע חֲזִיר לא מספיק כדי לשחזר פאי).

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

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

H = scalarToPoint(h)

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

כאשר k המשתתפים נותחו היי = p(i)H, כל אחד יכול לחשב Hx = p(x)H עבור כל x הודות לתכונה של פולינומים שעליה דנו בסעיף האחרון. ברגע זה, כל המשתתפים מחשבים H0 = p(0)H, וזה המספר האקראי המתקבל. שימו לב שאף אחד לא יודע p(0), ולכן הדרך היחידה לחישוב p(0)H – זו אינטרפולציה p(x)H, מה שאפשר רק כאשר k ערכים p(i)H ידוע. פתיחה בכל כמות קטנה יותר p(i)H אינו מספק מידע על p(0)H.

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

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

ערכים שונים של H_1 שנשלחו על ידי המשתתף הראשון מובילים לתוצאה שונה של H_0

יש לפחות שתי דרכים להוכיח נכונות Hאני, נשקול אותם לאחר שננתח את יצירת הפולינום.

יצירת פולינום

בסעיף האחרון הנחנו שיש לנו פולינום כזה p (x) степени k-1 שהמשתתף i יודע פאי), ולאף אחד אחר אין מידע על הערך הזה. בסעיף הבא נזדקק לזה גם לאיזו נקודה ידועה מראש G כולם ידעו p(x)G עבור כל x.

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

פרוטוקול יצירת פולינום אפשרי אחד הוא כדלקמן:

1. כל משתתף i יוצר באופן מקומי פולינום שרירותי pi(x) תואר k-1. לאחר מכן הם שולחים כל משתתף j значение pi(j), מוצפן עם מפתח ציבורי Xj. כך בלבד i-ה и j-ה המשתתף יודע pi(j). מִשׁתַתֵף i גם מכריז בפומבי pi(j)G עבור כל j מ 1 до k כולל.

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

3. המשתתפים מוודאים את הערכים שהם מכירים pi(j) תואם להכרז בפומבי pi(j)G. לאחר הצעד הזה פנימה Z רק פולינומים שעבורם משודרים באופן פרטי pi(j) תואם להכרז בפומבי pi(j)G.

4. כל משתתף j מחשב את הרכיב הפרטי שלו p(j) כסכום pi(j) עבור כולם i в Z. כל משתתף גם מחשב את כל הערכים p(x)G כסכום pi(x)G עבור כל i в Z.

שים לב ש p(x) - זה באמת פולינום k-1, כי זה סכום הפרט pi(x), שכל אחד מהם הוא פולינום של תואר k-1. לאחר מכן, שים לב שבזמן שכל משתתף j יודע p(j), אין להם מידע על p (x) עבור x ≠ j. ואכן, כדי לחשב את הערך הזה, הם צריכים לדעת הכל pi(x), וכל עוד המשתתף j אינו מכיר לפחות אחד מהפולינומים שנבחרו, אין להם מספיק מידע לגבי p(x).

זהו כל תהליך יצירת הפולינום שהיה נחוץ בסעיף האחרון. לשלבים 1, 2 ו-4 לעיל יש יישום די ברור. אבל שלב 3 הוא לא כל כך טריוויאלי.

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

קיים פרוטוקול קריפטוגרפי המאפשר ליצור הודעה נוספת הוכחהi(j), כך שלכל משתתף, יש ערך כלשהו e, כמו גם proofi(j) и pi(j)G, יכול לאמת זאת באופן מקומי e - זה באמת pi(j), מוצפן עם המפתח של המשתתף j. למרבה הצער, גודלן של ראיות כאלה הוא גדול להפליא, ובהתחשב בכך שיש צורך לפרסם O (nk) לא ניתן להשתמש בראיות כאלה למטרה זו.

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

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

הוכחות נכונות של H_i

החלק האחרון שנותר לדון בו הוא כיצד להוכיח את נכונות הפרסום Hאני, כלומר זה היי = p(i)H, בלי לפתוח פאי).

בואו נזכור כי הערכים H, G, p(i)G ציבורי וידוע לכולם. קבלו פעולה פאי) ידיעה חֲזִיר и G נקרא לוגריתם בדיד, או דלוג, ואנחנו רוצים להוכיח ש:

dlog(p(i)G, G) = dlog(Hi, H)

ללא חשיפה פאי). מבנים להוכחות כאלה קיימות, למשל פרוטוקול שנור.

עם עיצוב זה, כל משתתף, יחד עם Hi שולח הוכחת נכונות לפי העיצוב.

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

קורא סקרן עשוי לשאול: שכן המספר האקראי הסופי הוא H0, ו p(0)G – זה מידע ציבורי, למה אנחנו צריכים הוכחה לכל אדם Hאני, למה לא לשלוח הוכחה לכך במקום זאת

דלוג(p(0)G, G) = dlog(H0, H)

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

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

H0 × G = p(0)G × H

אם העקומה שנבחרה תומכת זיווג עקומה אליפטית, ההוכחה הזו עובדת. במקרה הזה H0 הוא לא רק פלט של מחולל מספרים אקראיים, אותו ניתן לאמת על ידי כל משתתף שיודע G, H и p(0)G. ח0 הוא גם חתימה על ההודעה ששימשה כ-seed, המאשרת זאת k и n המשתתפים חתמו על הודעה זו. לפיכך, אם זרע - הוא ה-hash של הבלוק בפרוטוקול הבלוקצ'יין, אם כן H0 הוא גם ריבוי חתימה על בלוק וגם מספר אקראי טוב מאוד.

לסיכום

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

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

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

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

נתראה בקרוב!

מקור: www.habr.com