پروتکل Zero- knowledge proof روشی است که در آن یک فرد (اثبات کننده - The Prover) میتواند به فرد دیگر (تایید کننده - The Verifier) اثبات کند که یک گزاره درست است بدون آنکه هرگونه اطلاعات بیشتری در مورد آن گزاره آشکار/افشا کند. به عبارت دیگر، اثبات کننده تنها اثبات میکند که یک گزاره درست است بدون آنکه خود گزاره را آشکار کند!
بگذارید یک مثال بزنم:
فرض کنید که رفیقمون، مهراد، کوررنگ هست و نمیتواند بین رنگهای مختلف تمایز قائل شود. بطور مثال، دایره سمت چپ چیزی هست که افراد عادی میبینند اما دایره سمت راستی چیزی هست که افراد کوررنگ میبینند.
حال فرض کنید که ما دو گوی داریم، یکی سفید و دیگری سیاه.
هر چند که شما میدانید که این دو گوی دارای رنگ متفاوتی میباشند اما مهراد فکر میکند که هر دو گوی یکسان میباشند. معمای ما این است که چگونه میتوانید به مهراد ثابت کنید این دو گوی متفاوت هستند بدون آنکه رنگ گویها را افشا کنید؟
راه حل:
هر دو گوی را به مهراد میدهیم تا پشت خود پنهان کند. سپس او یک گوی را به انتخاب خود به ما نشان میدهد و بعد در پشت خود پنهان میکند. سپس مهراد این آزمایش را تکرار میکند و یک گوی را به انتخاب خود به ما نشان میدهد. این گوی میتواند همان گوی قبلی باشد یا گوی متفاوت باشد، این تصمیم به عهده مهراد هست.
قدم بعدی آن است که ما به مهراد بگوییم که آیا گوی یکسانی را در این دو بار آزمایش به ما نشان داده یا آنکه گویهای متفاوتی را انتخاب کرده. طبیعتا برای ما بسیار آسان هست که با نگاه کردن به رنگ گویها بفهمیم که آیا مهراد در هر دو بار آزمایش یک گوی را نمایش داد یا آنکه گوی را تعویض کرد.
اگر ادعای مهراد درست است و گوی ها یکسان هستند در این صورت احتمال اینکه ما این معما را درست حل کنیم ۰.۵ خواهد بود، اما اگر ادعای ما درست باشد در این صورت ما باید بتوانیم با قطعیت (احتمال یک) معما را درست حل کنیم.
بنابراین اگر این معما را هزار بار تکرار کنیم و در هر هزار بار معما را به درستی حل کنیم آنگاه مهراد متقاعد خواهد شد که گویها دارای رنگ متفاوتی میباشند و ما این رنگهای متفاوت را میدانیم بدون آنکه افشا کرده باشیم کدام گوی دارای چه رنگی میباشد.
معمای دوم، غار علیبابا:
فرض کنید ما رمز عبور در داخل غار را میدانیم اما مهراد نسبت به صحت ادعای ما شک دارد. هدف ما این است که به مهراد ثابت کنیم ما رمز عبور را میدانیم بدون آنکه رمز عبور را در اختیار او قرار دهیم.
راه حل:
مهراد در نقطه A میایستد و من به داخل غار میروم. به انتخاب خودم به یک سوی در میروم: سمت C یا سمت D. مهراد بیرون غار است و نمیتواند ببیند که من به کدام سمت در رفتم.
وقتی من در یک سمت در قرار میگیرم، مهراد وارد غار میشود و در نقطه B میایستد.
اکنون مهراد باید از من بخواهد که از یک سوی غار به نزد او بروم: سمت چپ C، یا سمت راست D.
اگر مهراد از من خواسته باشد که از جهتی خارج شوم که نیاز به عبور از در باشد آنوقت من میتوانم از رمز عبور خود استفاده کنم.
من و مهراد با هم توافق میکنیم که این آزمایش را هزار بار تکرار کنیم.
اگر ادعای من درست باشد و من رمز عبور را در اختیار داشته باشم آنگاه قادر خواهم بود که در هر هزار بار از سمتی خارج شوم که مهراد مطالبه کرده. اما اگر من رمز عبور در را نداشته باشم آنگاه شانس من برای خروج از جهتی که مهراد مطالبه میکند تنها ۰.۵ خواهد بود و از آنجا که دفعات تکرار این آزمایش به اندازه کافی زیاد است امکان آنکه من در هر ۱۰۰۰ بار خوششانس باشم و در سمتی باشم که مهراد مطالبه کرده بسیار کم میباشد. بنابر این با این راهحل من میتوانم به مهراد اثبات کنم که رمز عبور را در اختیار دارم بدون آنکه رمز خود را افشا/آشکار کرده باشم.
معمای سوم:
شبکه رادیویی زیر را در نظر بگیرید. هر نود یک دکل مخابراتی میباشد و خط واصل بین دو نود نشاندهنده تداخل رادیویی میباشد که امری نامطلوب است.
خوشبختانه تکنولوژی ما این امکان را به ما میدهد که هر برج مخابراتی را با یکی از سه باند مختلف فرکانس تنظیم کنیم تا از این تداخل امواج اجتناب کنیم.
اکنون معمای ما این میباشد که هر برج مخابراتی را به یکی از سه باند فرکانس نظیر کنیم بطوری که هیچ دو برج مخابراتی همسایه (آنهایی که با یک خط به هم وصل شدند) فرکانس مشترک و یکسان نداشته باشند. ما از سه رنگ مختلف برای نمایش این سه فرکانس مختلف استفاده میکنیم. یک راهحل برای این معما مثال زیر میباشد:
حال فرض کنید وزارت ارتباطات قادر به حل این معما نیست اما حاضر است مبلغ بسیار زیادی به کسی بپردازد که این معما را حل کرده باشد. مشکل این میباشد که من حاضر نیستم تا زمانی که وزارتخانه جایزه را نپرداخته جواب معما را در اختیار آنها قرار بدم و وزارتخانه هم حاضر نیست پاداش تعیین شده را قبل از دریافت راهحل بپردازد. به عبارت دیگر هیچ کدام از طرفین این معما قادر به اعتماد به طرف دیگر نیستند.
راه حل:
پروتکل زیر را در نظر بگیرید.
ابتدا وزیر ارتباطات وارد یک انبار خالی میشود، سطح زمین را با کاغذ میپوشاند و نقشه دکلهای مخابراتی و خطوط واصل که معرف تداخل امواج هستند را بر روی این کاغذ میکشد. سپس وزیر از انبار خارج میشود.
من به همراه سه ماژیک رنگی قرمز، آبی و بنفش وارد انبار میشوم. من نود های معرف دکلها را بر اساس راه حل خودم و با کمک سه ماژیک رنگی نقاشی میکنم. قبل از آنکه از انبار خارج شوم این نودها را با کلاههای سیاه میپوشانم. (به توابع هش فکر کنید.)
وقتی وزیر (به همراه من) دوباره به انبار وارد میشود صحنه زیر را میبیند:
حال من به وزیر جوان اجازه میدهم که من را به چالش بکشد. او باید یک خط واصل و دو نود آن را انتخاب کند. سپس من دو کلاه روی آن دو نود را بر میدارم و رنگ نودها را آشکار میکنم:
اگر رنگ این دو نود یکسان باشد آنگاه وزیر در مییابد که من به او دروغ گفتهام و پرونده را به قوه قضائیه ارجاع میدهد. اما اگر رنگ این دو نود متفاوت باشد آنگاه وزیر این امکان را متصور خواهد شد که من به او دروغ نمیگویم و ممکن است راه حل معما را در اختیار داشته باشم.
اما من همچنان اثبات نکردم که راه حل را در اختیار دارم. ممکن است این اختلاف رنگ تنها از سر شانس و اقبال بوده باشد. بنابراین برای متقاعد کردن وزیر و هیئت همراه من باید این پروتکل را بارها و بارها تکرار کنم. اما از آنجا که من نمیخواهم تکرار این پروتکل راهحل من را آشکار کند در هر بار تکرار، به صورت تصادفی رنگهای سه ماژیک خود را به این سه باند فرکانس اختصاص میدهم.
بنابراین در ادامه کاغذهای قبلی را جدا کرده و کاغذ های جدید به کف انبار میچسبانیم. من اکنون آن سه ماژیک رنگی را دوباره و بصورت تصادفی به سه باند فرکانس اختصاص میدهم و بر اساس راهحل خود رنگآمیزی جدید را انجام میدهم. دوباره کلاه ها را بر سر نودها میگذارم تا راه حل خود را پنهان کنم و به همین ترتیب پروتکل تا انتها تکرار میشود. اگر این پروتکل هزار بار تکرار شود و در هر هزار بار رنگ نودهای متصل به خط واصل انتخاب شده توسط وزیر متفاوت باشد آنگاه وزیر مطمئن خواهد شد که با احتمال بسیار نزدیک به یک من راه حل را در اختیار دارم.
بنابر این پروتکل Zero- knowledge proof میتواند شرایطی را فراهم کند که یک فرد صحت یک گزاره را اثبات کند بدون آنکه اطلاعاتی از محتوای آن درز دهد. اساس این سیستم همانطور که دیده شد بر اساس verify کردن است نه trust بین طرفین.
منابع:
2- https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/