איך זה הוגן

מאיפה מגיעה האקראיות

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

מקורות: MDN: Crypto.getRandomValues() · W3C: Web Cryptography API

הטיית מודולו, ואיך נמנעים ממנה

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

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

ערבוב ובחירת זוכים בלי העדפה

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

מקור: Durstenfeld, Algorithm 235: Random permutation (1964)

הגרלות שאפשר לחשב מחדש

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

מקור: NIST FIPS 180-4: Secure Hash Standard (SHA-256)

התחייבות מראש: הגרלה שקופה

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

איך אנחנו בודקים את זה

• מבחני חי בריבוע על מאות אלפי הגרלות, לכל גודל טווח, גם עם המחולל האמיתי וגם עם זרע קבוע.
• מבחן שמראה שחלוקה פשוטה עם שארית נכשלת באותו מבחן, כך שהבדיקה באמת רגישה להטיה.
• כל 24 הסדרים של 4 פריטים יוצאים באותה תדירות בערבוב, וכל 9 השיבוצים האפשריים של 4 משתתפים בגמד וענק.
• SHA-256 נבדק מול המימוש של Node.js על קלטים אקראיים, והגרלה שהתחייבה מראש נבדקת מקצה לקצה, כולל ניסיונות זיוף.

ומה עם האנימציות?

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

שאלות נפוצות