اثبات دانش صفر – ۱

shape
shape
shape
shape
shape
shape
shape
shape

اثبات دانش صفر (zero knowledge proof) موضوعی در رمزنگاری است که روش هایی ارائه میدهدکه به واسطه ی آن یک فرد به نام اثبات کننده که دارای اطلاعاتی سری است، میتواند به فرد دیگری به نام تایید کننده، اثبات کند که این اطلاعات سری از یک ویژگی خاص برخوردار است، بدون اینکه نیاز به افشای آن اطلاعات سری داشته باشد. به طور مثال فرض کنید یک کاربر بدون اینکه بخواهد مقدار دارایی اش را افشا کند، بتواند اثبات کند که موجودی اش برای خرید یک محصول کافی است.

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

در ادامه با چند مثال اثبات دانش صفر را کاملا روشن میکنم. فرض کنید نیما و سارا رئیس دو شرکت رقیب هستند که به شرطی حاضرند مشترکا روی یک پروژه سرمایه گذاری کنند که مطمئن باشند سرمایه هر دو یکسان است. اما هیچ کدام از آنها نمیخواهد که در صورت مساوی نبودن سرمایه ها طرف مقابل بداند که سرمایه خودش از دیگری بیشتر بوده یا کمتر زیرا طرف مقابل ممکن است بعدا از این اطلاعات به نحوی به نفع خودش استفاده کند. بنابراین تنها اطلاعاتی که باید سارا درباره سرمایه شرکت نیما به دست بیاورد این است که آیا پول او با پول خودش برابر است یا نه و نباید بتواند درباره اینکه سرمایه او از سرمایه خودش بیشتر یا کمتر است اطلاعاتی کسب کند و بالعکس نیما هم نباید بتواند اطلاعات بیشتری درباره سرمایه شرکت سارا به دست آورد. برای سادگی فرض کنید که سرمایه هر دو شرکت بین مقادیر 10، 20، 30 و 40 میلیارد تومان است.

روشی که برای حل این مساله با کمک اثبات دانش صفر میتوان ارائه داد به صورت زیر است:

4 جعبه وجود دارد که هر کدام متناظر با یکی از مقادیر 10 تا 40 است. این 4 جعبه در یک اتاق در بسته وجود دارند و در آنها قفل میشود و هر کدام از نیما و سارا یک کپی از کلید تمام آنها دارند.

مرحله اول : نیما وارد این اتاق میشود و کلید یکی از جعبه ها را که متناظر با مقدار سرمایه خودش است برمیدارد و بقیه کلید ها را دور می اندازد.

مرحله دوم: نیما بیرون میرود و سارا داخل اتاق می آید و در تک تک جعبه ها را باز میکند و داخل آن جعبه ای که متناظر با سرمایه ی خودش است یک استیکر سبز رنگ با امضای خودش و داخل 3 جعبه ی دیگر یک استیکر قرمز رنگ با امضای خودش میگذارد. سپس در تمام جعبه ها را قفل میکند و از اتاق بیرون میرد.

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

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

همچنین توجه کنید وجود امضای سارا روی استیکر ها سبب میشد نیما نتواند یک استیکر تقلبی را با استیکر سارا جا بزند. به علاوه در مرحله اول باید با یک مکانیزم مطمئن شد که نیما تمام کلید ها را جز یکی دور می اندازد.

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

    راه حل پیشنهادی این است که سارا چشم هایش را ببنندد و نیما توپ ها را به او دهد. حالا سارا توپ ها را پشت سرش بگیرد و یکی از آنها را انتخاب کند و به نیما نشان دهد. سپس آن توپ را مجددا پشت سرش بیاورد و به صورت رندوم یکی از دو حالت زیر را انتخاب کند :

    • دوباره همان توپ را به نیما نشان دهد که در این صورت نیما باید ادعا کند که سارا هر دو بار یک توپ را نشان داده.
    • توپ دیگر را به نیما نشان دهد که در این صورت نیما باید ادعا کند که سارا دو توپ متفاوت را نشان داده.

اگر توپ ها همرنگ باشند نیما نمیتواند بفهمد که سارا همان توپ قبلی را دارد نشان میدهد یا توپ دیگر را و بنابراین نمیتواند ادعای درستی بکند و بالاخره دستش رو خواهد شد. اما اگر نیما شانسی ادعا کند و از قضا ادعایش درست از آب در آید چه؟ برای رفع این مشکل سارا باید چند بار عمل بالا را تکرار کند تا احتمال شانسی بودن درست بودن ادعاهای نیما بسیار کم شود.

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

اما مشکلی که روش های ذکر شده  داردند تعاملی(interactive) بودن است. به طور مثال تصور کنید اثبات کننده یک کاربر است که میخواهد ثابت کند رمز ورود به یک سیستم را میداند و تایید کننده سرور مرکزی است که بدون نیاز به رمز کاربر(اطلاعات محرمانه) باید بتواند تایید کند که آیا کاربر رمز صحیح را میداند یا خیر. اگر قرار باشد تایید کننده سوالات متعددی از کاربر بپرسد تا اطمینان حاصل کند که او رمز را میداند یا نه، کاربر باید برای مدت زمانی آنلاین بماند و حجم زیادی اطلاعات بین او و سرور جابجا شود. برای حل این مشکل اثبات دانش صفر غیرتعاملی پیشنهاد شده است که نیاز به پرسش و پاسخ های متعدد ندارد و تایید کننده با یک پرسش و پاسخ میتواند درستی ادعای اثبات کننده را تایید کند. اما چگونه؟ فرض کنید در مثال توپ های رنگی فقط یکبار آزمایش را انجام دهیم. در این صورت با احتمال 50 درصد نیما دروغ میگوید! این مثال نشان میدهد که مکانیزم اثبات دانش صفر غیرتعاملی بسیار پیچیده تر و متفاوت با اثبات دانش صفر تعاملی است و اصول کاملا متفاوتی دارد.

در پست های بعدی به توضیح مفصل اثبات دانش صفر غیرتعاملی و Zk-snark به عنوان یک روش مشهور که در این دسته جای میگیرد خواهیم پرداخت.

نویسنده : مهسا باستان خواه

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *