کریپتو با ویتالیک؛ zk-SNARK چگونه کار می‌کند؟

ویتالیک بوترین یکی از مهم‌ترین دانشمندان حوزه بلاکچین در سطح جهان است. او با وجود سن کم، سابقه زیادی در این حوزه دارد و نوشته‌های او در بلاگ شخصی‌اش را به نوعی می‌توان تاریخچه زنده تحولات مهم بلاکچین دانست. از این رو در مجموعه میهن بلاکچین بر آن شدیم تا با ترجمه این مطالب به زبان فارسی، زمینه آشنایی مخاطب فارسی با این وقایع را ممکن سازیم. مطلب پیش رو که در مورد نحوه عمل الگوریتم‌های بی‌نیاز به دانش (zero-knowledge proof) است در تاریخ ۱ فوریه سال ۲۰۱۷ در سایت شخصی بوترین منتشر شد.

این سومین قسمت از مجموعه مقالاتی است که به منظور شرح فناوری به کار رفته در zk-SNARKها نوشته شده است. مطالعه دو قسمت پیشین برای درک بهتر این قسمت الزامی است. می‌توانید دو قسمت قبلی را از لینک‌های زیر مطالعه کنید:

همچنین می‌توانید مقاله کریستین رایتوایسنر (Christian Reitweiessner) را برای آشنایی با این مفاهیم مطالعه کنید.

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

مبانی این مطلب بر پایه پروتکل پینوکیو که توسط پارنو (Parno)، گنتری (Gentry)، هاول (Howell) و رایکووا (Raykova) در سال ۲۰۱۳ تدوین شد و اغلب با نام اختصاری PGHR13 شناخته می‌شود، استوار است. با توجه به تفاوت‌هایی جزیی در شیوه عمل، ممکن است چیزی که در دنیای واقعی در الگوریتم‌های zk-SNARK می‌بینید کمی متفاوت از چیزی باشد که شرح داده خواهد شد اما اصول و مبانی آن یکسان است.

پیش از شروع، بیایید فرض بنیادین رمزنگاری را که امنیت مکانیزمی که قرار است استفاده کنیم، بر آن استوار است را شرح دهیم: فرض دانش توان (knowledge of exponent).

در واقع اگر یک جفت نقطه P و Q را داشته باشید که P . k = Q، و به نقطه C برسید، آن گاه غیرممکن است که به C . k برسید مگر آن که C را به نحوی که خود اطلاع دارید از P استخراج کرده باشید. شاید این مساله به شکل بدیهی واضح به نظر برسد اما این فرض را نمی‌توان از هیچ یک از دیگر فروض (برای مثال، سختی لگاریتم گسسته) که به شکل عادی از آن‌ها در هنگام اثبات امنیت پروتکل‌های مبتنی بر منحنی‌های بیضوی استفاده می‌کنیم به دست آورد. بنابراین می‌توان اذعان کرد که الگوریتم‌های zk-SNARK بر پایه‌ای لرزان‌تر از امنیت رمزنگاری مبتنی بر منحنی‌های بیضوی بنا شده است – هر چند از دید اکثر رمزنگاران برای استفاده به اندازه کافی امن هست.

حال بیایید بررسی کنیم چگونه می‌توان از این مساله استفاده کرد. فرض کنید که نقطه‌ای با مختصات (P , Q) از آسمان بر زمین می‌افتد به نحوی که معادله P . k = Q برقرار است و هیچ‌کس از مقدار k خبر ندارد. حال تصور کنید که من زوجی با مختصات (R , S) ارائه کرده‌ام که در آن R . k = S است. حال فرض بنیادینی که آن را پذیرفتیم این را بیان می‌دارد که تنها راهی که برای من وجود دارد که بتوانم چنین نقطه‌ای را ارائه دهم این بوده است که P و Q را گرفته و آن‌ها را در ضریبی به نام r ضرب کنم که فقط شخصا از مقدار آن مطلع هستم. همچنین توجه داشته باشید که به مدد جادوی زوج‌سازی منحنی بیضوی، بررسی تساوی R = k . S نیازی به دانستن مقدار k ندارد بلکه صرفا برقرار بودن تساوی e ( R , Q ) = e ( P , S ) را چک می‌کنید.

بیایید کار هیجان‌انگیزتری انجام دهیم؛ فرض کنیم ده زوج نقطه داریم که از آسمان نازل شده‌اند: ( P 1 , Q 1 ) , ( P 2 , Q 2 ) . . . ( P 10 , Q 10 ).

در تمامی موارد P i ⋅ k = Q i است. حال من به شما نقطه ( R , S ) را نشان می‌دهم که در آن R ⋅ k = S است. حال از این اطلاعات چه چیزی دستگیرتان می‌شود؟ می‌دانید که R ترکیبی خطی از P 1 ⋅ i 1 + P 2 ⋅ i 2 + . . . + P 10 ⋅ i 10 است که من ضرایب آن – i 1 , i 2 . . . i 10 – را می‌دانم. بنابراین تنها راه رسیدن به زوجی همانند ( R , S ) این است که ضرایب P 1 , P 2 . . . P 10 را گرفته و با هم جمع کنیم و همین محاسبات را با Q1 , Q 2 . . . Q 10 انجام دهیم.

دقت کنید که برای هر زیرمجموعه مشخصی از نقاط P 1 . . . P 10 که بخواهید ترکیب خطی آن را بررسی کنید، نمی‌توانید نقاط متناظر Q1 . . . Q10 را بدون دانستن k بسازید و اگر k را بدانید می‌توانید زوج ( R , S ) را که در آن R ⋅ k = S است را برای هر Rای که بخواهید تشکیل دهید و نیازی به ساخت ترکیب خطی ندارید. بنابراین این مساله ایجاب می‌کند که هر کس مسئول ساخت این نقاط است، قابل اعتماد بوده و پس از ساخت ده نقطه مدنظر، k را پاک کند. به همین دلیل نیاز به «ساختاری قابل اعتماد» برای این فرایند داریم.

اگر از قسمت‌‌های پیشین به خاطر داشته باشید، راه‌حل یک مساله QAP مجموعه‌ای از چندجمله‌ای‌های ( A , B , C ) است که در معادله A ( x ) ⋅ B ( x ) − C ( x ) = H ( x ) ⋅ Z ( x ) صدق کند. در این معادله:

• A ترکیبی خطی از مجموعه چندجمله‌ای‌های { A 1 . . . A m } است.
• B ترکیبی خطی از { B 1 . . . B m } با ضرایبی مشابه است.
• C ترکیبی خطی از { C 1 . . . C m } با ضرایبی مشابه است.

مجموعه‌های { A 1 . . . A m } , { B 1 . . . B m } و { C 1 . . . C m } و چندجمله‌ای Z بخشی از صورت مساله هستند.

اما در اکثر موارد دنیای واقعی A, B و C بسیار بزرگ هستند؛ برای چیزی با هزاران گیت منطقی همچون یک تابع هش، چندجمله‌ای‌ها (و ضرایب ترکیب‌های خطی مرتبط با آن‌ها) شامل هزاران جمله هستند. بنابراین به جای آن که اثبات‌کننده (prover) ترکیب‌های خطی را به شکل مستقیم ارائه دهد، از حقه‌ای که در بالا نشان دادیم استفاده می‌کنیم تا اثبات‌کننده بدان وسیله نشان دهد که ترکیب خطی درست را ارائه داده است بی آن که واقعا چیزی را عیان کرده باشد.

اما حقه‌ای که به کار بستیم بر روی نقاط منحنی بیضوی – و نه چند جمله‌ای‌ها – اثر می‌کند بنابراین چیزی که واقعا رخ می‌دهد این است که ما مقادیر زیر را به ساختار قابل اعتماد خود می افزاییم:

• G ⋅ A 1 ( t ) , G ⋅ A 1 ( t ) ⋅ k a
• G ⋅ A 2 ( t ) , G ⋅ A 2 ( t ) ⋅ k a
• …
• G ⋅ B 1 ( t ) , G ⋅ B 1 ( t ) ⋅ k b
• G ⋅ B 2 ( t ) , G ⋅ B 2 ( t ) ⋅ k b
• …
• G ⋅ C 1 ( t ) , G ⋅ C 1 ( t ) ⋅ k c
• G ⋅ C 2 ( t ) , G ⋅ C 2 ( t ) ⋅ k c
• …

t را می‌توان «نقطه‌ای مخفی» دانست که در آن چندجمله‌ای مورد ارزیابی قرار می گیرد. G مولد (نقطه‌ای تصادفی بر روی منحنی بیضوی که در پروتکل مشخص شده است) است و t , k a , k b و k c را «زباله‌های سمی» می‌نامیم؛ اعداد و مقادیری که باید به هر نحو ممکن پاک شوند وگرنه با افشای آن‌ها، هر کس که آن را در اختیار داشته باشد می‌تواند اثبات تقلبی تولید کند. بنابراین اکر کسی به شما زوجی از نقاط P و Q را دهد به نحوی که P ⋅ k a = Q باشد (یادآوری: به k a برای بررسی این برابری احتیاجی نداریم و می‌توانیم از بررسی زوج‌ها استفاده کنیم)، آن گاه می‌دانید چیزی که در واقع به شما ارائه داده است ترکیب خطی از A i چندجمله‌ای در نقطه ارزیابی t است.

تا بدینجا اثبات‌کننده باید موارد زیر را ارائه دهد:

• π a = G ⋅ A ( t ) , π a ′ = G ⋅ A ( t ) ⋅ k a
• π b = G ⋅ B ( t ) , π b ′ = G ⋅ B ( t ) ⋅ k b
• π c = G ⋅ C ( t ) , π c ′ = G ⋅ C ( t ) ⋅ k c

دقت داشته باشید که اثبات‌کننده نیازی نیست که مقادیر t , k a , k b و k c را بداند (و نباید بداند!) تا بتواند آن‌ها را محاسبه کند بلکه اثبات‌کننده تنها باید قادر باشد تا این مقادیر را با استفاده از نقاطی که ما به ساختار قابل اعتماد خود افزودیم به دست آورد.

قدم بعدی اطمینان حاصل کردن از این موضوع است که تمامی سه ترکیب خطی بالا ضرایب یکسان دارندو این کار را می توان با افزودن مجموعه‌ای دیگر از مقادیر به ساختار قابل اعتماد خود انجام داد: G ⋅ ( A i ( t ) + B i ( t ) + C i ( t ) ) ⋅ b که در آن b عددی دیگر است که باید به شمار «زباله‌های سمی» اضافه شود و به محض تکمیل شدن ساختار قابل اعتماد دور انداخته شود. سپس می‌توانیم اثبات‌کننده را مجاب کنیم تا با تشکیل ترکیبی خطی از این مقادیر با ضرایبی یکسان و استفاده از حقه زوج‌سازی بالا، تایید کند که این مقادیر با A+B+C داده شده می‌خواند.

در نهایت باید اثبات کنیم که تساوی A ⋅ B − C = H ⋅ Z برقرار است. از روش بالا بار دیگر برای بررسی این امر استفاده می‌:نیم و خواهیم داشت:

e ( π a , π b ) / e ( π c , G ) ? = e ( π h , G ⋅ Z ( t ) )

که در آن π h = G ⋅ H ( t ) است. اگر ارتباط این معادله و تساوی A ⋅ B − C = H ⋅ Z بر شما آشکار نیست، مطلب مرتبط با زوج‌سازی را برای رفع ابهام مطالعه کنید.

در سطور بالا مشاهده کردیم که چگونه می‌‌توان A، B و C را تبدیل به نقاطی بر روی منحنی بیضوی کرد؛ G مولد است (نقطه‌ای بر روی منحنی بیضوی معادل با عدد یک). می‌توانیم G ⋅ Z ( t ) را به ساختار قابل اعتماد خب بیافزاییم. H کمی بغرنج‌تر است. H یک چندجمله‌ای است و پیش‌بینی اینکه ضرایب آن برای هر راه‌حل QAP چگونه خواهد بود، مشکل است. بنابراین باید اطلاعات بیشتری به ساختار قابل اعتماد خود اضافه کنیم. به خصوص زنجیره زیر:

G , G ⋅ t , G ⋅ t 2 , G ⋅ t 3 , G ⋅ t 4 . . .

در ساختار قابل اعتماد ارز Zcash ، این دنباله تا دو میلیون عدد ادامه می‌یابد. این بدین معنی است که تا توان دو میلیونیوم t را احتیاج خواهید داشت تا مطمئن باشید که همواره قادر خواهید بود که H ( t ) را محاسبه کنید لااقل برای نمونه‌ای از مساله QAP که در ساختار Zcash به دنبال حل آن هستند. با این کار اثبات‌کننده می‌تواند تمامی اطلاعات لازم برای تاییدکننده (verifier) را برای بررسی نهایی تهیه کند.

یک مساله دیگر وجود دارد که باید آن را بررسی نماییم. در اکثر مواقع تنها به دنبال اثبات وجود راه‌حلی برای یک مساله مشخص نیستیم، بلکه می‌خواهیم یا درستی یک راه‌حل مشخص را اثبات نماییم (مثلا اینکه اگر شما کلمه cow را به عنوان ورودی بگیرید و یک میلیون بار با تابع هش SHA3 آن را پشت سر هم هش کنید، جواب نهایی با دنباله 0x73064fe5 آغاز می شود یا نه) و یا اینکه بررسی نماییم اگر برخی پارامترهای مساله را محدود نماییم آیا راه‌حلی برای مساله وجود دارد یا نه. به عنوان مثالی در یک رمزارز فرضی که مقادیر تراکنش‌ها و موجودی حساب‌ها رمزنگاری شده است، می‌خواهیم ثابت کنیم که از وجود کلید رمزگشایی k باخبریم که:

1. decrypt(old_balance, k) >= decrypt(tx_value, k)

1. decrypt(old_balance, k) – decrypt(tx_value, k) = decrypt(new_balance, k)

مقادیر رمزنگاری شده old_balance (موجودی قبلی)، tx_value (مقدار تراکنش) و new_balance (موجودی جدید) باید به شکل عمومی مشخص شود چرا که آن‌ها مقادیر مشخصی هستند که به دنبال تایید آن‌ها در زمانی مشخص هستیم. تنها کلید رمزگشایی باید مخفی بماند. پروتکل احتیاج به برخی تغییرات جزیی دارد تا بتوان «کلید تایید شخصی‌سازی شده» ایجاد کرد که متناظر با محدودیتی مشخص بر روی ورودی‌ها باشد.

بیایید یک قدم به عقب بازگردیم. الگوریتم تایید که کاری از الی بن ساسون (Eli ben Sasson)، ترومر (Tromer)، ویرزا (Virza) و کیه‌زا (Chiesa) است، به شرح زیر است:

خط اول به ساخت پارامترها می‌پردازد. کارکرد آن را به شکل خلاصه می‌توان به ساخت یک «کلید تایید شخصی‌ئازی شده» برای نمونه خاصی از مساله وقتی برخی آرگومان‌ها مشخص شده‌اند، تقلیل داد. خط دوم بررسی ترکیب خطی A، B و C است. خط سوم چگ گردن یکسان بودن ضرایب ترکیب‌های خطی است و خط چهارم برابری تساوی A ⋅ B − C = H ⋅ Z را بررسی می‌کند.

فرایند تایید شامل چند عمل ضرب منحنی‌های بیضوی (یک عدد به ازای هر متغیر ورودی عمومی) و پنج بررسی زوج‌هاست که یکی از آن‌ها شامل یک ضرب زوجی اضافه است. راه‌حل شامل هشت زوج نقطه بر روی منحنی‌های بیضوی است؛ یک جفت نقطه برای هر یک از A(t)، B(t) و C(t)، یک نقطه π k برای b ⋅ ( A ( t ) + B ( t ) + C ( t ) ) و یک نقطه π h برای H(t). هفت عدد از این نقاط بر روی منحنی F p (با طول ۳۲ بایت برای هر یک؛ چرا که مختصات y را می‌توان با فشرده‌سازی به یک بیت کاهش داد) قرار دارند و در پروتکل Zcash یک نقطه – π b – بر روی خم F p 2 (با طول ۶۴ بایت) قرار دارد. بنابراین اندازه کلی راه‌حل برابر با ۲۸۸ بایت خواهد بود.

دو مرحله مشکل ساخت راه‌حل (از لحاظ محاسباتی) عبارتند از:

• تقسیم ( A ⋅ B − C ) / Z برای به دست آوردن H (هرچند الگوریتم‌هایی مبتنی بر تبدیل فوریه سریع به وجود آمده‌اند که می‌توانند این عمل را به شکلی بهینه‌تر انجام دهند با این حال این کار همچنان از لحاظ محاسباتی مشکل است).
• انجام اعمال ضرب و جمع بر روی منحنی‌های بیضوی برای تشکیل A(t)، B(t)، C(t) و H(t) و نقاط متناظرشان.

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

سوال بسیار مهم دیگر این است که آیا می‌توانیم ساختار قابل اعتماد خود را کمی کمتر نیازمند اعتماد کنیم؟ متاسفانه نمی‌توانیم این کار را به شکل کامل بی‌نیاز از اعتماد انجام دهیم. فرض بنیادینی که در ابتدای مطلب بیان کردیم به تنهایی مانع از این می‌شود که بتوانیم بدون دانستن k، نقاط مستقل ( P i , P i ⋅ k ) را ایجاد کنیم. با این وجود می‌توان امنیت را با استفاده از محاسبات چند جانبه N از N افزایش داد. در این روش، ساختار قابل اعتماد نا به نحوی بین چند عامل بنا می‌شود که مادامی که تنها یکی از عوامل درگیر، «زباله سمی» خود را پاک کند، می‌توان از امنیت محاسبات اطمینان حاصل کرد.

برای اینکه درک این مساله برای‌تان ملموس‌تر شود به این الگوریتم ساده برای دریافت مجموعه G , G ⋅ t , G ⋅ t 2 , G ⋅ t 3 . . . و اضافه کردن رمز خود به آن، به نحوی که برای تقلب نیاز به دانستن رمز خود و رمز/رمزهای پیشین باشید، توجه کنید.

مجموعه خروجی به شکل زیر خواهد بود:

G , ( G ⋅ t ) ⋅ s , ( G ⋅ t 2 ) ⋅ s 2 , ( G ⋅ t 3 ) ⋅ s 3 . . .

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

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

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