توضیح‌نامه‌ی ۰۳

یک اثبات چگونه ساخته و بررسی می‌شود؟

توضیح‌نامه‌ی پیشین به این پرسش پاسخ داد که اثبات دانش‌صفر چیست و چه تضمینی می‌دهد. این یکی به پرسشی می‌پردازد که مردم بلافاصله بعد از آن می‌پرسند:

«خب، اما گوشی من چگونه آن اثبات کوچک را تولید می‌کند، و بلاک‌چین چگونه تصمیم می‌گیرد که معتبر است — بی‌آن‌که هرگز گذرنامه‌ی مرا ببیند؟»

برای دنبال‌کردن این متن نیازی به ریاضیات سنگین نیست. ابتدا با یک قیاس شهود می‌سازیم، سپس مسیر واقعی را روی گوشی و روی زنجیره دنبال می‌کنیم.

ایده‌ی اصلی: اثبات دانستن یک راز، بدون فاش‌کردن آن

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

شما وارد می‌شوید و یکی از دو تونل چپ یا راست را برمی‌گزینید. دوستتان دمِ ورودی منتظر است و نمی‌بیند از کدام سو رفتید. او فریاد می‌زند «از سمت چپ بیرون بیا!». اگر واقعن رمز را بدانید می‌توانید در را باز کنید و هر بار از همان سمتی که خواست بیرون بیایید. اگر بلوف می‌زدید، در هر دور تنها ۵۰٪ شانس دارید. این کار را ۴۰ بار تکرار کنید و احتمال جعل به حدود یک در تریلیون می‌رسد. دوستتان متقاعد می‌شود که رمز را می‌دانید — اما هرگز نمی‌فهمد رمز چیست.

اثبات دانش‌صفر نسخه‌ی ریاضی همان غار است. «راز» همان داده‌های گذرنامه و کلید خصوصی شماست. به‌جای رفتن به چپ یا راست، ریاضیات شما را وادار می‌کند به چالش‌هایی غیرقابل‌پیش‌بینی پاسخ دهید که تنها در صورتی می‌توانید درست پاسخشان دهید که رازتان واقعن همه‌ی قواعد را برآورده کند.

گام ۱ — قواعد را به محاسبات عددی تبدیل کنید (مدار)

پیش از آن‌که هر اثباتی وجود داشته باشد، قواعدی که می‌خواهید ثابت کنید به یک دستگاه عظیم از معادلات حسابی تبدیل می‌شوند. هر قاعده به مجموعه‌ای از معادلات بدل می‌شود:

• «گذرنامه‌ی من با گواهی رسمی یک دولت امضا شده است» → معادلاتی که ریاضیات امضای RSA / ECDSA را بررسی می‌کنند.
• «تابعیت من IR است» → معادلاتی که بایت‌های مشخصی از داده را بررسی می‌کنند.
• «من پیش‌تر رای نداده‌ام» → معادلاتی که یک nullifier یکتا محاسبه می‌کنند.

کل این مجموعه معادلات همان مدار (circuit) است. یک مدار گذرنامه صدها هزار معادله دارد. ویژگی کلیدی این است: معادلات چنان نوشته شده‌اند که تنها زمانی همه با هم برابر صفر می‌شوند که داده‌ی واقعی و معتبر را وارد کرده باشید.

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

گام ۲ — پرکردن جاهای خالی (شاهد)

گوشی شما داده‌ی خصوصی واقعی‌تان (بایت‌های اسکن NFC، کلید مخفی) را می‌گیرد و هر مقدار میانی در آن صدها هزار معادله را محاسبه می‌کند — هر ضرب، هر گام درهم‌سازی (hash)، هر بیت.

این مجموعه‌ی کامل از مقادیر پرشده، شاهد (witness) نام دارد. این همان پاسخ کامل سودوکوست. چون شامل رازهای شماست، شاهد هرگز گوشی را ترک نمی‌کند.

گام ۳ — فشرده‌سازی شاهد در یک اثبات کوچک

این‌جا بخش هوشمندانه است. گوشی باید راستی‌آزما را قانع کند که شاهدی معتبر در اختیار دارد — بی‌آن‌که شاهد را بفرستد.

ترفند، چندجمله‌ای‌ها (polynomials) هستند. همه‌ی معادلات در شمار کمی منحنی ریاضی (چندجمله‌ای) بسته‌بندی می‌شوند. یک قضیه‌ی عمیق این کار را ممکن می‌کند:

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

پس فرایند اثبات چنین است:

1. گوشی کل شاهد را در چند چندجمله‌ای رمزگذاری می‌کند.
2. به آن‌ها تعهد (commitment) می‌دهد — چند اثرانگشت رمزنگارانه (نقاطی روی یک منحنی بیضوی) تولید می‌کند. تعهد مانند مهروموم‌کردن یک مقدار در پاکت است: بعدن نمی‌توانید تغییرش دهید، اما محتوای آن را هم فاش نمی‌کند.
3. برای آزمودن چندجمله‌ای‌ها به یک نقطه‌ی چالش تصادفی نیاز است. هیچ راستی‌آزمای زنده‌ای حاضر نیست، پس گوشی چالش «تصادفی» را با درهم‌سازی تعهدهای خودش می‌سازد. این همان ترفند فیات–شامیر (Fiat–Shamir) است: درهم‌سازیِ داده‌ی غیرقابل‌پیش‌بینی همچون پرتاب سکه‌ای دستکاری‌ناپذیر عمل می‌کند که اثبات‌کننده نمی‌تواند آن را تقلب کند.
4. گوشی چندجمله‌ای‌ها را در آن نقطه‌ی چالش ارزیابی می‌کند و پاسخ‌ها را به همراه یک «اثبات گشایش» کوچک بسته‌بندی می‌کند.

نتیجه یک بسته‌ی کوچک است — از چند صد بایت تا چند کیلوبایت — مهم نیست محاسبه‌ی اصلی چقدر غول‌پیکر بوده باشد. همان بسته، اثبات است.

دو سامانه‌ای که جمهور به کار می‌برد این کار را اندکی متفاوت انجام می‌دهند:

کد بومی‌ای که بار سنگین را برمی‌دارد rapidsnark (برای Groth16) یا Barretenberg / Swoirenberg (برای UltraPlonk) است. این همان گامی است که چند ثانیه روی گوشی طول می‌کشد — چون هزاران ضرب روی منحنی بیضوی انجام می‌دهد.

گام ۴ — واقعن چه چیزی فرستاده می‌شود

از گوشی تنها این‌ها بیرون می‌آید:

• بسته‌ی اثبات (اعداد مبهم)، و
• سیگنال‌های عمومی (public signals) — همان شمار اندک مقادیری که اثبات درباره‌ی آن‌هاست: nullifier شما، کد کشور، چند درهم‌سازی، شناسه‌ی طرح رای. هرگز داده‌ی شخصی خام شما گوشی را ترک نمی‌کند.

بایت‌های گذرنامه، کلید مخفی و کل شاهد همگی روی دستگاه می‌مانند.

اثبات چگونه بررسی می‌شود

راستی‌آزما، قرارداد هوشمند روی بلاک‌چین است (برای رای‌گیری INID، همان IDCardVoting.sol). این قرارداد محاسبه‌ی شما را دوباره اجرا نمی‌کند — کل نکته همین است. اجرای دوباره به‌طرز ناممکنی پرهزینه می‌بود و داده‌ی شما را هم در اختیار ندارد. در عوض دو کار می‌کند.

۱. بازسازی سیگنال‌های عمومی موردانتظار

قرارداد مستقلن تعیین می‌کند که سیگنال‌های عمومی باید چه باشند. مقادیری را که ادعا کردید (تابعیت، nullifier و …) به‌علاوه‌ی مقادیری که خودش از پیش می‌داند (قواعد طرح، تاریخ کنونی، ریشه‌ی درخت مرکل روی زنجیره) برمی‌دارد و در همان خانه‌های ثابتی می‌چیند که اثبات باید با آن‌ها بخواند. چرایی این‌که ادعای مقدار جعلی در این‌جا به شما کمکی نمی‌کند در راستی‌آزمایی روی زنجیره آمده است.

۲. اجرای بررسی جفت‌سازی (pairing)

قرارداد، بسته‌ی اثبات و آن سیگنال‌های عمومی را به یک آزمون کوتاه رمزنگارانه می‌سپارد که بر یک عمل ویژه روی منحنی بیضوی BN254 به نام جفت‌سازی (pairing) بنا شده و با e(·, ·) نشان داده می‌شود.

جفت‌سازی ویژگی‌ای تقریبن جادویی دارد: به شما اجازه می‌دهد یک رابطه‌ی ضربی میان مقادیر پنهان را تایید کنید، در حالی که تنها تعهدهای مهروموم‌شده‌ی آن‌ها را می‌بینید. مانند آن‌که بتوانید تایید کنید «عدد درون پاکت A ضرب در عدد درون پاکت B برابر است با عدد درون پاکت C» — بی‌آن‌که هرگز پاکتی را باز کنید.

برای Groth16 کل اعتبار اثبات شما به بررسی برابری یک معادله خلاصه می‌شود:

e(A, B) = e(α, β) · e(public signals, γ) · e(C, δ)

• A, B, C سه نقطه‌ای‌اند که از اثبات شما می‌آیند.
• α, β, γ, δ ثابت‌هایی‌اند که در قرارداد تعبیه شده‌اند — همان کلید بررسی (verification key)، باقی‌مانده‌ی عمومی مراسم راه‌اندازیِ معتمد.
• جمله‌ی «public signals» مقادیر گام ۱ را در خود جای می‌دهد.

اگر دو طرف برابر درآیند، اثبات معتبر است: شاهد شما وجود داشته و همه‌ی آن صدها هزار معادله را برآورده کرده است. اگر حتی یک معادله در مدار برابر نشده باشد — درباره‌ی تابعیت دروغ گفتید، امضایی جعل کردید، یک nullifier را دوباره به کار بردید — دو طرف برابر نمی‌شوند و قرارداد بازمی‌گردد (revert).

شبکه‌ی Rarimo L2 (مانند اتریوم) حتی precompileهای آماده‌ای دارد — عمل‌های ارزان ویژه در آدرس‌های 0x07 و 0x08 — که مشخصن برای همین جفت‌سازی‌های BN254 ساخته شده‌اند، چون محاسبه‌شان پرهزینه اما ضروری است.

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

همه‌چیز در یک نفس

1. قواعد ← یک دستگاه عظیم از معادلات (مدار).
2. گوشی داده‌ی واقعی و مخفی شما را وارد می‌کند و همه‌ی معادلات را حل می‌کند (شاهد).
3. شاهد از راه تعهدهای چندجمله‌ای + یک چالش تصادفیِ خودساخته در یک اثبات کوچک فشرده می‌شود — رازها هرگز گنجانده نمی‌شوند.
4. گوشی تنها اثبات + سیگنال‌های عمومی را می‌فرستد.
5. قرارداد سیگنال‌های عمومی موردانتظار را بازمی‌سازد و یک معادله‌ی جفت‌سازی را اجرا می‌کند. برابر شد ← معتبر. برابر نشد ← رد.

تضمین عمیق این است: ریاضیات تنها زمانی جور درمی‌آید که شما واقعن داده‌ی معتبر در اختیار داشته باشید — و راستی‌آزما همین واقعیت را می‌آموزد و هیچ چیز دیگری را.

واژه‌نامه

بعدی

در ادامه: راستی‌آزمایی روی زنجیره — این‌که قرارداد هوشمند واقعن با آن بایت‌ها چه می‌کند، چرا سریع و ارزان است، و چرا یک ادعای جعلی در سیگنال‌های عمومی نمی‌تواند از آن بگذرد.