الگوریتمِ قرعه‌کشیِ شفاف و قابلِ راستی‌آزمایی؛ چطور قرعه‌ای بسازیم که هر کسی بتواند دوباره اجرا کند

چرا «عددِ تصادفی» مسئله نیست؛ «اعتماد به تولیدکنندهٔ عدد» مسئله است

یک قرعهٔ معمولی سه ورودی دارد: فهرستِ شرکت‌کنندگان، یک عددِ تصادفی، و قاعده‌ای که از این دو برنده را می‌سازد. ابزارهای رایج فقط روی کیفیتِ عددِ تصادفی تأکید می‌کنند، در حالی که هر سه ورودی برای بیننده نامرئی‌اند: کسی نمی‌داند فهرست در لحظهٔ اجرا دقیقاً چه بود، عدد را چه کسی و کِی ساخت، و آیا قاعده همان بود که گفته شد. عددِ تصادفیِ بی‌نقص در چنین قرعه‌ای هیچ چیزی را ثابت نمی‌کند، چون اجراکننده می‌تواند آن‌قدر عدد بسازد تا نتیجهٔ دلخواهش بیاید و فقط آخری را نشان بدهد.

قرعهٔ قابلِ راستی‌آزمایی مسئله را جابه‌جا می‌کند: به‌جای اینکه بخواهد کسی به تصادفی‌بودنِ عدد اعتماد کند، کاری می‌کند که هیچ طرفی به‌تنهایی نتواند عدد را انتخاب کند و هر کسی بتواند محاسبه را تکرار کند. برای این کار چهار قطعه لازم است که به ترتیب می‌آیند و ترتیبشان تمامِ قوتِ روش است.

قطعهٔ اول: قفلِ فهرست و اثرانگشت

فهرستِ متقاضیان پس از پایانِ مهلتِ اعتراض به یک فایلِ متنیِ قانونی‌شده (canonical) تبدیل می‌شود: هر متقاضی یک سطر با فیلدهای ثابت (شناسه، امتیاز، گروهِ سهمیه)، مرتب‌شده با یک کلیدِ قطعی مثلِ شناسه، کدگذاریِ UTF-8 بدونِ BOM، جداکنندهٔ ثابت، پایانِ سطرِ LF، و بدونِ فاصلهٔ اضافه. قانونی‌شدن برای این است که هر کسی از همان داده به بایت‌های دقیقاً یکسان برسد؛ وگرنه اثرانگشتِ دو نفر با یک فهرست فرق می‌کند و بحث از قرعه به کدگذاری کشیده می‌شود. سپس SHA-256 این فایل محاسبه و به‌همراهِ زمانِ ثبت منتشر می‌شود. از این لحظه فهرست تغییر نمی‌کند.

function canonicalList(rows):
  rows = sortBy(rows, r => r.id)                # ترتیبِ قطعی
  lines = rows.map(r => join([r.id, r.score, r.quota], "\t"))
  text = join(lines, "\n") + "\n"             # LF، بدونِ BOM
  return utf8Bytes(text)

listBytes = canonicalList(applicants)
listHash  = hex(sha256(listBytes))
publish(listHash, now())                      # گامِ ۲: اثرانگشت با زمان

اگر سازمان فهرست را با کدِ مستعار منتشر می‌کند، نگاشتِ کدِ مستعار به شناسهٔ پرسنلی جدا و پیش از قفل به خودِ افراد اعلام می‌شود؛ خودِ فهرستِ قفل‌شده فقط کدِ مستعار دارد. این به الگوریتم ربطی ندارد ولی به انتشارِ نتیجه بدونِ نامِ کارکنان ربط دارد.

قطعهٔ دوم: تعهدِ پیش از اجرا (پاکتِ دربسته)

سامانه یک مقدارِ تصادفیِ بلند می‌سازد (دستِ‌کم ۳۲ بایت از یک مولدِ رمزنگاشتی، نه Math.random) و آن را پنهان نگه می‌دارد؛ فقط SHA-256 آن را با زمانِ ثبت منتشر می‌کند. این «تعهد» (commitment) است: سامانه به عددی متعهد شده که کسی نمی‌داند، و بعداً نمی‌تواند عددِ دیگری را جای آن بگذارد، چون اثرانگشتش نمی‌خواند. طولِ زیاد برای این است که کسی نتواند با آزمون و خطا مقدارِ پنهان را از اثرانگشتش حدس بزند.

secret     = randomBytes(32)                  # CSPRNG؛ پنهان می‌ماند
commitment = hex(sha256(secret))
publish(commitment, now())                    # گامِ ۳: پاکتِ دربسته

# ... شاهدان سهمشان را اعلام می‌کنند (قطعهٔ سوم) ...

reveal(secret)                                # گامِ ۵: پاکت باز می‌شود
assert hex(sha256(secret)) == commitment      # هر کسی بررسی می‌کند

قطعهٔ سوم: بذر از سهمِ شاهدان؛ ترتیبِ افشا

پس از انتشارِ تعهد، شاهدانِ دوره (نمایندهٔ کارکنان، بازرسی، حراست، یا هر کسی که سازمان تعیین کرده) هر کدام یک رشتهٔ دلخواه علنی اعلام می‌کنند. لازم نیست تصادفی باشد؛ مهم این است که پس از تعهدِ سامانه و پیش از افشای آن اعلام شده باشد. بذرِ نهایی اثرانگشتِ ترکیبِ مقدارِ افشاشدهٔ سامانه و سهمِ شاهدان به همان ترتیبِ اعلام است.

ترتیب چرا مهم است: اگر سامانه پیش از تعهد سهمِ شاهدان را می‌دانست، می‌توانست مقدارش را طوری انتخاب کند که بذرِ نهایی نتیجهٔ دلخواه بدهد. اگر شاهدی مقدارِ پنهانِ سامانه را می‌دانست، همین کار را می‌توانست بکند. با این ترتیب، سامانه در لحظهٔ تعهد نمی‌داند شاهدان چه خواهند گفت و شاهدان در لحظهٔ اعلام نمی‌دانند سامانه چه پنهان کرده. نتیجه: کافی است یک طرف صادق باشد تا بذر برای همه غیرِ قابلِ پیش‌بینی بماند. اگر همهٔ طرف‌ها با هم تبانی کنند، روش شکست می‌خورد؛ این یکی از حدودِ روش است که پایین‌تر آمده.

shares = [w1, w2, w3]                         # به ترتیبِ اعلام؛ رشته‌های علنی

# ترکیبِ بدونِ ابهام: طولِ هر جزء پیش از خودش می‌آید تا
# "ab"+"c" و "a"+"bc" یک بذر نسازند.
function lengthPrefixed(parts):
  return concat(parts.map(p => concat(u32be(len(p)), utf8Bytes(p))))

seed = sha256(lengthPrefixed([hex(secret), ...shares]))   # گامِ ۶

قطعهٔ چهارم: انتخابِ قطعی؛ بلیت‌ها، فهرستِ ذخیره، و باقی‌ماندهٔ بی‌سوگیری

با بذرِ ثابت، همهٔ «تصادف» تمام شده؛ از اینجا به بعد هر چیزی محاسبهٔ قطعی است و باید طوری نوشته شود که با همان ورودی همیشه همان خروجی را بدهد. امتیازِ هر متقاضی به تعدادی بلیت تبدیل می‌شود (مثلاً یک بلیت به ازای هر واحدِ امتیاز، با یک کفِ حداقلی تا کسی صفر بلیت نگیرد)؛ بلیت‌ها به ترتیبِ فهرستِ قانونی شماره می‌خورند. برای هر گامِ انتخاب، اثرانگشتِ «بذر به‌علاوهٔ شمارهٔ گام» گرفته می‌شود، به عددِ صحیح تبدیل و بر تعدادِ بلیت‌های باقی‌مانده باقی‌مانده گرفته می‌شود؛ صاحبِ آن بلیت انتخاب می‌شود و همهٔ بلیت‌هایش کنار می‌رود. این روند تا پرشدنِ ظرفیت ادامه دارد و بعد از آن هم ادامه دارد تا فهرستِ ذخیره را به ترتیب بسازد؛ برای همین جایگزینیِ بعدی به قرعهٔ تازه نیاز ندارد.

یک ریزه‌کاری که صفحهٔ سازوکار هم پنهانش نمی‌کند: باقی‌مانده‌گرفتنِ یک عددِ ۶۴ بیتی بر n، وقتی n مقسوم‌علیهِ ۲ به توانِ ۶۴ نیست، به بلیت‌های ابتدایی بختِ ناچیزی بیشتر می‌دهد (سوگیریِ باقی‌مانده). برای حذفش، عددهایی که در بازهٔ لبه‌ای می‌افتند دور انداخته و گامِ بعدی برداشته می‌شود؛ چون هر گام از بذر و شمارهٔ گام ساخته می‌شود، دورانداختن هم قطعی و قابلِ بازتولید است.

function draw(seed, list, capacity):
  pool = []                                   # [ownerId] به ازای هر بلیت، به ترتیبِ فهرست
  for r in list: pool.append(repeat(r.id, ticketsOf(r.score)))
  order = []; step = 0
  while pool not empty:
    step += 1
    x = u64be(sha256(concat(seed, u32be(step)))[0:8])
    n = len(pool)
    limit = (2^64 // n) * n                   # بازهٔ بی‌سوگیری
    if x >= limit: continue                   # دورانداختن؛ گامِ بعد
    winner = pool[x % n]
    order.append(winner)
    pool = pool.filter(id => id != winner)    # همهٔ بلیت‌های برنده کنار می‌رود
  return order[0:capacity], order[capacity:]  # برندگان، ذخیره به ترتیب

بازتولید در مرورگر: چه چیزی بررسی می‌شود، چه چیزی نه

پروندهٔ راستی‌آزمایی یک فایلِ متنی با پنج بخش است: فهرستِ قفل‌شده، اثرانگشتِ منتشرشدهٔ آن با زمان، اثرانگشتِ تعهد با زمان، مقدارِ افشاشده و سهمِ شاهدان به ترتیب، و فهرستِ نهاییِ برندگان و ذخیره. مرورگر بدونِ هیچ کتابخانه‌ای SHA-256 دارد (Web Crypto، تابعِ digest)؛ پس بازتولید یک صفحهٔ HTML ساده است که این چهار بررسی را انجام می‌دهد و هیچ چیزی به سرور نمی‌فرستد.

1. اثرانگشتِ فهرستِ داخلِ پرونده با اثرانگشتِ منتشرشدهٔ پیش از قرعه یکی است. یعنی فهرست پس از قفل عوض نشده.
2. اثرانگشتِ مقدارِ افشاشده با تعهدِ منتشرشده یکی است. یعنی سامانه پس از شنیدنِ شاهدان عددش را عوض نکرده.
3. بذرِ ساخته‌شده از مقدارِ افشاشده و سهمِ شاهدان با بذرِ ادعاشده یکی است.
4. اجرای الگوریتم روی همان فهرست و همان بذر، دقیقاً همان برندگان و همان ترتیبِ ذخیره را می‌دهد.

async function sha256hex(bytes):
  digest = await crypto.subtle.digest("SHA-256", bytes)
  return hex(new Uint8Array(digest))

check1 = (await sha256hex(file.listBytes)) == file.publishedListHash
check2 = (await sha256hex(file.secret))    == file.publishedCommitment
seed   = await sha256(lengthPrefixed([hex(file.secret), ...file.shares]))
check3 = hex(seed) == file.claimedSeed
[winners, reserve] = draw(seed, parse(file.listBytes), file.capacity)
check4 = equal(winners, file.winners) && equal(reserve, file.reserve)

چیزی که بررسی نمی‌شود: اینکه زمانِ ثبتِ اثرانگشت‌ها واقعاً پیش از اعلامِ شاهدان بوده. بازتولید فقط سازگاریِ ریاضی را می‌سنجد؛ ترتیبِ زمانی را کانالِ انتشار تضمین می‌کند و باید کانالی باشد که سامانه نتواند بعداً بازنویسی‌اش کند: ایمیل به شاهدان در لحظهٔ ثبت، نامهٔ اتوماسیون با شمارهٔ ثبت، چاپ و امضا، یا ثبت در سرویسی خارج از کنترلِ سامانه. نقشِ ناظر با دسترسیِ فقط‌خواندنی دقیقاً برای همین است که کسی بیرون از سامانه زمانِ ثبت را دیده باشد.

حدودِ روش: چه چیزی را اثبات نمی‌کند

پرسش‌های فنیِ پرتکرار

چرا Math.random کافی نیست، حتی اگر واقعاً تصادفی باشد؟

چون قابلِ بازتولید نیست و چون یک طرف آن را می‌سازد. مسئله کیفیتِ آماریِ عدد نیست؛ این است که بیننده نمی‌تواند تشخیص بدهد عددِ نشان‌داده‌شده اولین عدد بوده یا صدمین. تعهدِ پیش از اجرا این را می‌بندد و بذرِ چندطرفه انتخابِ انفرادی را غیرِ ممکن می‌کند. مولدِ رمزنگاشتی فقط برای مقدارِ پنهانِ سامانه لازم است تا از اثرانگشتش حدس‌زدنی نباشد.

چرا به‌جای شاهدان از یک منبعِ تصادفیِ عمومی (مثلاً چراغِ تصادفیِ یک نهاد) استفاده نمی‌کنید؟

می‌شود و می‌توان آن را به‌عنوانِ یک شاهدِ اضافه به همان ترکیب افزود: مقدارِ منتشرشدهٔ آن منبع در زمانِ مشخص، یکی از سهم‌ها می‌شود. جایگزینِ شاهدانِ انسانی نمی‌شود، چون کارمندی که به واحدِ رفاه اعتماد ندارد، به یک سرویسِ بیرونی که نمی‌شناسد هم اعتماد نمی‌کند؛ نمایندهٔ خودش را می‌شناسد.

چرا SHA-256 و نه HMAC یا یک تابعِ اختصاصی؟

چون هر ابزارِ استانداردی در دنیا همین را می‌سازد و بازرسِ غیرِ برنامه‌نویس هم می‌تواند با ابزارِ داخلِ سیستم‌عامل اثرانگشتِ فایل را بگیرد. HMAC کلید می‌خواهد و کلید یعنی یک طرفِ دیگر که باید به آن اعتماد کرد. تابعِ اختصاصی هم دقیقاً همان چیزی است که نباید باشد: اثرانگشتِ ما نباید ساختگی و مخصوصِ خودمان باشد.

چرا بلیت و باقی‌مانده، به‌جای بُرِ وزن‌دارِ Fisher–Yates؟

Fisher–Yates برای بُرِ یکنواخت است و نسخهٔ وزن‌دارِ استانداردی ندارد که برای غیرِ برنامه‌نویس توضیح‌دادنی باشد. کشیدنِ پی‌درپیِ وزن‌دار بدونِ جای‌گذاری (هر بار یک بلیت، حذفِ همهٔ بلیت‌های برنده) دو مزیت دارد: با یک جمله قابلِ توضیح است («امتیازِ بیشتر، بلیتِ بیشتر») و ترتیبِ ذخیره را در همان اجرا می‌سازد. روش‌های دیگرِ نمونه‌گیریِ وزن‌دار هم قابلِ راستی‌آزمایی‌اند، به شرطِ قطعی‌بودن و انتشار؛ انتخابِ ما به‌خاطرِ توضیح‌پذیری است نه برتریِ ریاضی.

اگر دو متقاضی شناسهٔ یکسان یا امتیازِ اعشاری داشته باشند؟

شناسهٔ تکراری خطای ورودی است و قانونی‌کردن باید آن را رد کند، نه اینکه بی‌صدا بپذیرد. امتیازِ اعشاری با یک ضریبِ ثابت و منتشرشده به عددِ صحیحِ بلیت تبدیل می‌شود (مثلاً هر دهمِ امتیاز یک بلیت) یا آیین‌نامه از اول امتیازِ صحیح تعریف می‌کند. هر دو تصمیم باید در سندِ الگوریتم نوشته شده باشد، وگرنه دو پیاده‌سازیِ درست به دو نتیجهٔ متفاوت می‌رسند و بررسیِ ۴ بی‌جهت رد می‌شود.

برنامه‌نویسِ سازمان برای پیاده‌سازیِ مستقل چه چیزهایی لازم دارد؟

همین مقاله، سندِ منتشرشدهٔ الگوریتم با جزئیاتِ قانونی‌کردن (جداکننده، ترتیب، کدگذاری)، ضریبِ تبدیلِ امتیاز به بلیت، شکلِ دقیقِ ترکیبِ بذر، و یک پروندهٔ نمونه با نتیجهٔ معلوم برای آزمون. اگر پیاده‌سازیِ مستقل روی پروندهٔ نمونه به همان نتیجه رسید، روی پرونده‌های واقعی هم می‌رسد. سازمانی که این پیاده‌سازی را دارد، دیگر حتی به صفحهٔ راستی‌آزماییِ ما هم نیاز ندارد، و این عمدی است. چک‌لیستِ بازرسی پرسش‌های ۷ تا ۱۰ را برای همین نوشته و قرعه کشی بدونِ این چهار قطعه در آن پاسخِ منفی می‌گیرد. برای اتصالِ فهرستِ ورودی به دادهٔ پرسنلی، هم‌گام‌سازی با سیستمِ پرسنلی مقالهٔ جداگانه‌ای دارد؛ کیفیتِ فهرستِ ورودی از الگوریتم بیرون است ولی از مسئولیتِ آی‌تی نه. هیچ نرم افزار یا نرم‌افزارِ اختصاصی‌ای برای بازتولید لازم نیست؛ مرورگر کافی است.