‏اثبات دانش صفر با ۳۰ خط پایتون

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

به گفتهٔ نویسنده، بلاگ‌پست‌ها و دموهای شیک کمکی نکردن و آخرش رفتن سراغ مقالهٔ اصلی Goldreich، Micali و Wigderson؛ یه صفحه‌ش کافی بود. پروتکل این‌جوریه: اثبات‌کننده یه جایگشت تصادفی روی سه رنگ می‌زنه، رنگ هر گره رو توی یه «جعبهٔ قفل‌شده» می‌ذاره و جعبه‌ها رو بدون کلید می‌فرسته. تأییدکننده یه یال تصادفی انتخاب می‌کنه، کلید دو سرش رو می‌گیره و چک می‌کنه اون دو تا رنگ فرق دارن. همین چهار قدم m² بار تکرار می‌شه.

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

def nonce():
    return random.randrange(100)

def box_coloring(coloring):
    return {node: (color, nonce()) for (node, color) in coloring.items()}

تأییدکننده وقتی جعبه‌ها رو باز می‌کنه، اول چک می‌کنه هشِ (رنگ، nonce) با همون هشی که اول دور گرفته بود جور دربیاد؛ این جلوی عوض کردن رنگ‌ها وسط دور رو می‌گیره:

for (node, (color, nonce)) in revealed.items():
    assert hashed_coloring[node] == hash((color, nonce)), f"Hash mismatch!"

هر دور فقط ۱/|E| اطمینان می‌ده، برای همین تعداد دورها مهمه. مقاله می‌گه احتمال اینکه یه اثبات‌کنندهٔ متقلب همهٔ دورها رو رد کنه حداکثر (1 - m⁻¹)^(m²) هست. برای گرافی با ۱۰۰۰ یال، بعد از ۴۶۰۰ دور شانس تقلب حدود ۱٪ و بعد از ۱۰٬۰۰۰ دور حدود ۰٫۰۰۴۵٪ می‌شه.

نویسنده‌ها یه دموی سرور/کلاینت هم گذاشتن تا واقعاً یه مرز شبکه‌ای بین دو طرف باشه، نه فقط کامنتِ «فقط اثبات‌کننده» توی یه فایل پایتون. همین ایده روی سودوکو هم جواب می‌ده: به جای رنگ‌ها رقم‌ها رو قاطی می‌کنی و به جای یال، سطر و ستون و خونه رو باز می‌کنی. چون رنگ‌آمیزی سه‌رنگ NP-کامله، هر مسئلهٔ NP-کامل دیگه‌ای رو هم می‌شه با یه کاهش چندجمله‌ای به همین قالب برد — هرچند نویسنده می‌گه در عمل حتی برای فاکتورگیری عددهای دورقمی، گراف به هزاران گره می‌رسه.

نکات کلیدی:

• پایهٔ کار پروتکل ۴ مقالهٔ Goldreich، Micali و Wigderson هست؛ هر دور چهار قدم P1/V1/P2/V2 داره.
• کنار رنگِ هر گره یه nonce هش می‌شه تا گره‌های هم‌رنگ هشِ یکسان نگیرن و ساختار رنگ‌آمیزی لو نره.
• هر دور فقط ۱/|E| اطمینان می‌ده؛ احتمال قبول‌شدن یه اثبات‌کنندهٔ متقلب حداکثر (1 - m⁻¹)^(m²) هست.
• برای گراف با ۱۰۰۰ یال، ۴۶۰۰ دور یعنی حدود ۱٪ شانس تقلب و ۱۰٬۰۰۰ دور یعنی حدود ۰٫۰۰۴۵٪.
• نویسنده می‌گه برای کار جدی به جای hash و random سراغ hashlib.sha256 و ماژول secrets برید.