قرعه‌کشی منصفانه و قابل راستی‌آزمایی

در یک صندوق خانوادگی، ترتیب نوبت‌ها مهم است: نوبت اول زودتر پول را می‌گیرد، نوبت آخر دیرتر. برای همین قرعه باید طوری باشد که همه بپذیرند. خیلی از صندوق‌ها با قرعه‌ای از داخل کیسه کار می‌کنند و اگر کسی بپرسد «مطمئنید دستکاری نشد؟» جوابی جز اعتماد ندارند. باماوام راهی گذاشته که بعد از قرعه می‌شود درستی آن را با محاسبه ثابت کرد.

توضیح ساده

روش ما «تعهد و آشکارسازی» (commit–reveal) نام دارد. مثلاً تصور کنید قبل از قرعه، عددی را روی کاغذ می‌نویسید، کاغذ را در پاکت می‌گذارید و پاکت را جلوی همه مهر می‌کنید. بعد قرعه انجام می‌شود و پاکت باز می‌شود. همه می‌بینند عدد همان بوده و نمی‌شد بعد از قرعه عوضش کرد. در باماوام «پاکت مهرشده» همان اثرانگشت رمزنگاری‌شده است.

مراحل از دید اعضا:

1. ثابت کردن نوبت‌های اضطراری (اختیاری). مدیر می‌تواند با موافقت خانواده نوبتی را برای کسی که نیاز فوری دارد با ذکر دلیل ثابت کند. این نوبت‌ها برای همه نمایش داده می‌شود و در قرعه شرکت نمی‌کند.
2. زمان‌بندی قرعه. سامانه یک عدد تصادفی ۳۲ بایتی (seed) می‌سازد و فقط اثرانگشت SHA-256 آن، یعنی commit، را به همه نشان می‌دهد. خود عدد تا پایان قرعه مخفی می‌ماند.
3. قرعه. هنگام قرعه، ترکیبی از seed و فهرست دقیق سهم‌ها پایهٔ یک ترتیب تصادفی می‌شود. در صفحه، ماه‌ها یکی‌یکی آشکار می‌شوند و به هر عضو پیامک ماهش می‌رسد.
4. آشکار شدن. seed منتشر می‌شود. هر عضو می‌تواند در صفحهٔ راستی‌آزمایی ببیند که اثرانگشت همان seed بوده و ترتیب از همان محاسبه می‌آید.

حدود این روش

بهتر است صادقانه بدانید روش چه چیزی را ثابت می‌کند و چه چیزی را نه:

• ثابت می‌کند که بعد از انتشار commit، نتیجه را نمی‌شود بدون خراب شدن راستی‌آزمایی عوض کرد، و ترتیب فقط از ورودی‌های منتشرشده می‌آید.
• ثابت نمی‌کند که seed واقعاً تصادفی ساخته شده است؛ در نسخهٔ فعلی خود سامانه آن را می‌سازد و اعضا در ساخت آن سهمی ندارند.
• هر تغییر در فهرست اعضا یا نوبت‌های ثابت‌شده در سابقهٔ تغییرات ثبت می‌شود و برای همه دیدنی است.

الگوریتم دقیق

برای کسانی که می‌خواهند خودشان نتیجه را بسنجند. همهٔ رشته‌ها UTF-8 و همهٔ هش‌ها SHA-256 است. همین الگوریتم هم در سرور (PHP) اجرا می‌شود و هم در صفحهٔ راستی‌آزمایی داخل مرورگر شما؛ هر دو با مجموعه‌ای از نتیجه‌های مرجع آزموده شده‌اند و باید دقیقاً یک ترتیب بدهند.

ورودی‌ها

• سهم (ticket): هر سهم یک ردیف دارد. شناسهٔ آن عضو.شمارهٔ‌سهم است، مثلاً 3.2 یعنی دومین سهم عضو شمارهٔ ۳. عضوی که چند سهم دارد، به همان تعداد ردیف دارد. هر ردیف یک برچسب (نام عضو) و یک عدد pin دارد: شمارهٔ ماهی که برایش ثابت شده، یا 0 اگر ثابت نشده است.
• seed: ۳۲ بایت تصادفی (۶۴ نویسهٔ هگزادسیمال) که سامانه در لحظهٔ زمان‌بندی قرعه می‌سازد و تا پایان قرعه مخفی نگه می‌دارد.
• commit: hex(SHA-256(seed)) که پیش از قرعه برای همه منتشر می‌شود. (هش روی ۳۲ بایت خود seed است، نه روی متن هگزادسیمال.)
• ماه‌ها (slots): شمارهٔ ماه‌های صندوق، 1 تا تعداد ماه‌ها.

مراحل

1. فهرست استاندارد (canonical). برای هر سهم یک خط id|label|pin ساخته می‌شود (اگر برچسب | یا خط جدید داشته باشد، با فاصله عوض می‌شود). خط‌ها به همان ترتیبی که منتشر شده‌اند (اول بر اساس شمارهٔ عضو، بعد شمارهٔ سهم) با کاراکتر \n به هم می‌چسبند و رشته‌ای به نام canon می‌سازند. فهرست مرتب نمی‌شود و بعد از آخرین خط هم \n نیست.
2. مقدار نهایی. final = SHA-256(seed ‖ canon ‖ commit)؛ که seed ۳۲ بایت خام است، canon به‌صورت UTF-8 و commit همان ۶۴ نویسهٔ هگزادسیمال به‌صورت ASCII. ‖ یعنی چسباندن بایت‌ها. نتیجه ۳۲ بایت است. چون canon در آن است، تغییر دادن یک نام یا یک نوبت ثابت‌شده نتیجه را کاملاً عوض می‌کند.
3. جریان عدد تصادفی (DRBG). بلوک شمارهٔ i برابر HMAC-SHA256(کلید = final, پیام = i به‌صورت عدد ۴ بایتی big-endian) است، برای i = 0, 1, 2, …. هر بلوک ۳۲ بایتی به هشت کلمهٔ ۴ بایتی big-endian تقسیم می‌شود و کلمه‌ها به ترتیب، از بلوک ۰ شروع می‌شوند و بدون وقفه خوانده می‌شوند.
4. انتخاب یکنواخت با نمونه‌برداری ردکننده. برای عدد در بازهٔ [0, n): limit = ⌊2³² / n⌋ × n. کلمهٔ بعدی w را بخوانید؛ اگر w ≥ limit بود دور بریزید و کلمهٔ بعدی را بخوانید؛ وگرنه نتیجه w mod n است. به این ترتیب هیچ عددی شانس بیشتری ندارد.
5. سهم‌های ثابت‌شده. هر سهم با pin > 0 مستقیم در ماهِ pin می‌نشیند و در قرعه شرکت نمی‌کند. بقیهٔ سهم‌ها (با pin = 0) به همان ترتیب فهرست در لیست free می‌روند.
6. درهم‌ریزی Fisher–Yates روی free. برای i از طول−۱ تا 1: j = below(i + 1) را بگیرید و عناصر i و j را جابه‌جا کنید.
7. پخش نوبت‌ها. ماه‌هایی که ثابت نشده‌اند را به ترتیب صعودی بنویسید؛ عنصر اول free نوبت اولین ماهِ آزاد می‌شود، عنصر دوم نوبت دومین ماهِ آزاد، و همین‌طور تا آخر.

نمونهٔ کد

کد زیر با پایتون همین مراحل را اجرا می‌کند و روی دستگاه خودتان قابل اجراست. ورودی: seed (هگزادسیمال)، فهرست سهم‌ها به‌صورت {"id", "label", "pin"} و فهرست ماه‌ها. خروجی: نگاشت ماه به شناسهٔ سهم.

```python import hashlib, hmac, struct

def draw(seed_hex, tickets, cycles): seed = bytes.fromhex(seed_hex) commit = hashlib.sha256(seed).hexdigest() canon = "\n".join( "%s|%s|%d" % (t["id"], t["label"].replace("\n", " ").replace("|", " "), t.get("pin", 0)) for t in tickets ) final = hashlib.sha256(seed + canon.encode("utf-8") + commit.encode("ascii")).digest()

pos = 0 # position in the word stream: 8 words per 32-byte block

def next_word(): nonlocal pos block = hmac.new(final, struct.pack(">I", pos // 8), hashlib.sha256).digest() w = struct.unpack(">I", block[(pos % 8) * 4:(pos % 8) * 4 + 4])[0] pos += 1 return w

def below(n): limit = (2 ** 32 // n) * n while True: w = next_word() if w < limit: return w % n

result, taken, free = {}, set(), [] for t in tickets: if t.get("pin", 0) > 0: result[t["pin"]] = t["id"] taken.add(t["pin"]) else: free.append(t["id"]) for i in range(len(free) - 1, 0, -1): j = below(i + 1) free[i], free[j] = free[j], free[i] open_cycles = [c for c in sorted(cycles) if c not in taken] for c, tid in zip(open_cycles, free): result[c] = tid return dict(sorted(result.items())) ```

بعد از قرعه، seed، commit، فهرست سهم‌ها (همان ردیف‌های id، label و pin) و فهرست ماه‌ها در صفحهٔ نتیجه منتشر می‌شود. اگر خروجی کد شما با ترتیب نمایش‌داده‌شده یکی بود و SHA-256(seed) با commit پیش از قرعه برابر بود، قرعه درست انجام شده است.

قرعهٔ آزاد و آزمایشی

ابزار قرعه‌کشی آنلاین همین روش را برای هر فهرستی از نام‌ها به کار می‌برد. قرعهٔ آزمایشی هم در صندوق رایگان است و آشکارا «آزمایشی» نشان داده می‌شود.

دربارهٔ انتخاب نوبت‌ها به‌طور کلی، راهنمای قرعه‌کشی منصفانه برای صندوق خانوادگی را بخوانید.