Verifiable computing
قابل تصدیق کمپیوٹنگ (یا تصدیق شدہ کمپیوٹیشن یا تصدیق شدہ کمپیوٹنگ) ایک کمپیوٹر کو قابل تصدیق نتائج کو برقرار رکھتے ہوئے، کسی فنکشن کی کمپیوٹیشن کو دوسرے شاید ناقابل اعتماد کلائنٹس کو آف لوڈ کرنے کے قابل بناتا ہے۔ دوسرے کلائنٹ فنکشن کا جائزہ لیتے ہیں اور اس ثبوت کے ساتھ نتیجہ واپس کرتے ہیں کہ فنکشن کا حساب صحیح طریقے سے کیا گیا تھا۔ اس تصور کا تعارف SETI@home جیسے منصوبوں میں ناقابل اعتماد صارفین کے لیے "آؤٹ سورسنگ" کمپیوٹیشن کے بڑھتے ہوئے عام رجحان اور کلاؤڈ کمپیوٹنگ کی طرح زیادہ طاقتور کمپیوٹیشن سروس میں کمپیوٹیشنل کاموں کو آؤٹ سورس کرنے کی کمزور کلائنٹس کی بڑھتی ہوئی خواہش کے نتیجے میں ہوا۔ یہ تصور بابائی اور دیگر کے کام کرنے سے شروع ہوتا ہے، اور اس کا مطالعہ مختلف اصطلاحات کے تحت کیا گیا ہے، بشمول "چیکنگ کمپیوٹیشنز" (بابائی اور دیگر۔ )، "ڈیلیگیٹنگ کمپیوٹیشنز"، "مصدقہ کمپیوٹیشن"، اور قابل تصدیق کمپیوٹنگ۔ تصدیق شدہ کمپیوٹنگ کی اصطلاح کو خود روزاریو جینارو، کریگ جینٹری، اور برائن پارنو نے باقاعدہ بنایا تھا، اور میکالی کے "مصدقہ کمپیوٹیشن" کی بازگشت کرتا ہے۔ محرک اور جائزہ کمپیوٹیشنل کاموں کو نسبتا کمزور کمپیوٹیشنل ڈیوائس (کلائنٹ) سے زیادہ طاقتور کمپیوٹیشن سروسز (کارکن) کو آؤٹ سورس کرنے کی بڑھتی ہوئی خواہش، اور بے ایمان کارکنوں کا مسئلہ جو اپنے کلائنٹ کے سافٹ ویئر میں ترمیم کرتے ہیں تاکہ اصل کام انجام دیے بغیر قابل فہم نتائج واپس کر سکیں، تصدیق شدہ کمپیوٹیشن کے تصور کو باضابطہ بنانے کی ترغیب دی۔ قابل تصدیق کمپیوٹنگ کا تعلق نہ صرف کلائنٹ کے ان پٹ پر آؤٹ سورس فنکشن کا نتیجہ اور اس کی درستگی کے ثبوت حاصل کرنے سے ہے، بلکہ کلائنٹ شروع سے فنکشن کی کمپیوٹنگ کے مقابلے میں نمایاں طور پر کم کمپیوٹیشنل کوشش کے ساتھ ثبوت کی تصدیق کرنے کے قابل بھی ہے۔ غیر قابل اعتماد کارکنوں کے ذریعہ انجام دیئے گئے افعال کی گنتی کی تصدیق میں کافی توجہ دی گئی ہے جس میں محفوظ کوپروسیسرز، قابل اعتماد پلیٹ فارم ماڈیولز (ٹی پی ایم)، انٹرایکٹو ثبوت، ممکنہ طور پر قابل جانچ ثبوت، موثر دلائل، اور میکیلی کے سی ایس ثبوت شامل ہیں۔ یہ تصدیق یا تو انٹرایکٹو ہیں جن کے لیے کلائنٹ کو درستگی کے ثبوت کی تصدیق کے لیے کارکن کے ساتھ بات چیت کرنے کی ضرورت ہوتی ہے، یا غیر انٹرایکٹو پروٹوکول ہیں جو بے ترتیب اوریکل ماڈل میں ثابت کیے جا سکتے ہیں۔ نقل کے ذریعے تصدیق سب سے بڑا تصدیق شدہ حساب (SETI@home) نقل کے ذریعے تصدیق کا استعمال کرتا ہے۔ SETI@home تصدیق کے عمل میں ایک کلائنٹ مشین اور بہت سی کارکن مشینیں شامل ہوتی ہیں۔ کلائنٹ مشین ایک جیسے ورک یونٹس کو متعدد کمپیوٹرز (کم از کم 2) پر بھیجتی ہے۔ جب مناسب وقت میں کافی نتائج واپس نہیں کیے جاتے ہیں-حادثاتی طور پر مشینیں بند ہونے، مواصلاتی خرابی وغیرہ کی وجہ سے-یا نتائج متفق نہیں ہوتے ہیں-کمپیوٹیشن کی غلطیوں، اصل میں کام کیے بغیر غلط ڈیٹا جمع کرکے دھوکہ دہی وغیرہ کی وجہ سے-تب کلائنٹ مشین دیگر ورکر مشینوں کو زیادہ یکساں ورک یونٹ بھیجتی ہے۔ ایک بار جب نتائج کا کم از کم کورم (اکثر 2) متفق ہو جاتا ہے، تو کلائنٹ فرض کرتا ہے کہ وہ نتائج (اور اس ورک یونٹ کے دیگر یکساں نتائج) درست ہیں۔ کلائنٹ ان تمام مشینوں کو کریڈٹ دیتا ہے جو صحیح نتائج واپس کرتی ہیں۔ قابل تصدیق کمپیوٹیشن جنارو اور دیگر۔ قابل تصدیق کمپیوٹیشن اسکیم کے تصور کو دو کثیر الجہتی ٹائم پارٹیوں کے درمیان ایک پروٹوکول کے طور پر بیان کیا گیا ہے تاکہ فنکشن F: {0,1} n → {0,1} m کی کمپیوٹیشن پر تعاون کیا جا سکے۔ یہ اسکیم تین اہم مراحل پر مشتمل ہے: پری پروسیسنگ۔ یہ مرحلہ کلائنٹ کے ذریعہ ایف سے وابستہ کچھ معاون معلومات کا حساب لگانے کے لیے ایک بار انجام دیا جاتا ہے۔ اس معلومات کا کچھ حصہ کارکن کے ساتھ شیئر کرنے کے لیے عوامی ہے جبکہ باقی نجی ہے اور کلائنٹ کے پاس رکھا جاتا ہے۔ ان پٹ کی تیاری۔ اس مرحلے میں کلائنٹ فنکشن کے ان پٹ کے بارے میں کچھ معاون معلومات کا حساب لگاتا ہے۔ اس معلومات کا کچھ حصہ عوامی ہے جبکہ باقی نجی ہے اور کلائنٹ کے پاس رکھا جاتا ہے۔ عوامی معلومات کارکن کو ان پٹ ڈیٹا پر ایف کا حساب لگانے کے لیے بھیجی جاتی ہے۔ آؤٹ پٹ کمپیوٹیشن اور تصدیق۔ اس مرحلے میں، کارکن فنکشن F اور ان پٹ سے وابستہ عوامی معلومات کا استعمال کرتا ہے، جن کا حساب پچھلے دو مراحل میں کیا جاتا ہے، تاکہ فراہم کردہ ان پٹ پر فنکشن F کے انکوڈ آؤٹ پٹ کا حساب لگایا جا سکے۔ اس کے بعد یہ نتیجہ کلائنٹ کو واپس کر دیا جاتا ہے تاکہ پچھلے مراحل میں شمار کی گئی نجی معلومات کا استعمال کرتے ہوئے کارکن کی طرف سے واپس کیے گئے نتیجہ کو ڈی کوڈ کرکے آؤٹ پٹ کی اصل قیمت کا حساب لگا کر اس کی درستگی کی تصدیق کی جا سکے۔ قابل تصدیق کمپیوٹیشن اسکیم کا متعین تصور کلائنٹ اور کارکن کے درمیان تعامل کو بالکل دو پیغامات میں کم کرتا ہے، جہاں پروٹوکول کے مختلف مراحل کے دوران ہر فریق کی طرف سے دوسرے فریق کو بھیجا جانے والا ایک پیغام ہوتا ہے۔ مکمل طور پر ہومومورفک خفیہ کاری جنارو اور دیگر پر مبنی ایک مثال اسکیم۔ مکمل طور پر ہومومورفک انکرپشن سسٹم کے ساتھ مل کر یاؤ کے گاربلڈ سرکٹ کا استعمال کرتے ہوئے کسی بھی فنکشن F کے لیے قابل تصدیق کمپیوٹیشن اسکیم کی وضاحت کی۔ اس قابل تصدیق کمپیوٹیشن اسکیم وی سی کی تعریف اس طرح کی گئی ہے: وی سی = (کی جین، پروب جین، کمپیوٹ، تصدیق) مندرجہ ذیل چار الگورتھم پر مشتمل ہے: کی جین (ایف، λ) → (پی کے، ایس کے): بے ترتیب کلیدی نسل الگورتھم حفاظتی پیرامیٹر λ کی بنیاد پر دو کلیدیں، عوامی اور نجی پیدا کرتا ہے۔ عوامی کلید ٹارگٹ فنکشن F کو انکوڈ کرتی ہے اور کارکن کو F کا حساب لگانے کے لیے بھیجی جاتی ہے۔ دوسری طرف، خفیہ کلید کلائنٹ کے ذریعے نجی رکھی جاتی ہے۔ ProbGen (SK, x) → (σx, τx): دشواری پیدا کرنے والا الگورتھم خفیہ کلید SK کا استعمال کرتے ہوئے فنکشن ان پٹ x کو دو اقدار، عوامی اور نجی میں انکوڈ کرتا ہے۔ عوامی قیمت σx کارکن کو F (x) کے ساتھ شمار کرنے کے لیے دی جاتی ہے، جبکہ خفیہ قیمت τx کلائنٹ کے ذریعے نجی رکھی جاتی ہے۔ کمپیوٹ (پی کے، σx) → σy: کارکن کلائنٹ کی عوامی کلید پی کے اور انکوڈ شدہ ان پٹ σx کا استعمال کرتے ہوئے فنکشن کی آؤٹ پٹ y = F (x) کی انکوڈ شدہ قیمت σy کا حساب لگاتا ہے۔ تصدیق ایس کے (τx، σy) → y ≤ D: تصدیق الگورتھم کارکن کے انکوڈ شدہ آؤٹ پٹ σy کو خفیہ کلید SK اور خفیہ "ڈیکوڈنگ" τx دونوں کا استعمال کرتے ہوئے فنکشن F کی اصل آؤٹ پٹ میں تبدیل کرتا ہے۔ یہ y = F (x) کو آؤٹ پٹ کرتا ہے اگر σy x پر F کی درست آؤٹ پٹ کی نمائندگی کرتا ہے، یا بصورت دیگر آؤٹ پٹ کرتا ہے۔ قابل تصدیق کمپیوٹیشن اسکیم کا پروٹوکول جس کی وضاحت جنارو اور دیگر نے کی ہے۔ مندرجہ ذیل کام کرتا ہے: فنکشن F کو بولین سرکٹ کے طور پر پیش کیا جانا چاہیے جس پر کلیدی نسل کا الگورتھم لاگو کیا جائے گا۔ کلیدی نسل کا الگورتھم عوامی اور خفیہ چابیاں کا حساب لگانے کے لیے اس بولین سرکٹ پر یاؤ کے گربلنگ کے طریقہ کار کو چلاتا ہے۔ عوامی کلید (پی کے) ان تمام خفیہ متن پر مشتمل ہوتی ہے جو گربلڈ سرکٹ کی نمائندگی کرتے ہیں، اور خفیہ کلید (ایس کے) تمام بے ترتیب تار لیبلز پر مشتمل ہوتی ہے۔ اس کے بعد پیدا شدہ خفیہ کلید کو مسئلہ پیدا کرنے والے الگورتھم میں استعمال کیا جاتا ہے۔ یہ الگورتھم پہلے ہومومورفک خفیہ کاری اسکیم کے لیے عوامی اور خفیہ چابیاں کا ایک نیا جوڑا تیار کرتا ہے، اور پھر ان چابیوں کو ہومومورفک اسکیم کے ساتھ صحیح ان پٹ تاروں کو خفیہ کرنے کے لیے استعمال کرتا ہے، جس کی نمائندگی گاربلڈ سرکٹ کی خفیہ کلید کے طور پر کی جاتی ہے۔ تیار کردہ خفیہ متن ان پٹ (σx) کی عوامی انکوڈنگ کی نمائندگی کرتے ہیں جو کارکن کو دی جاتی ہے، جبکہ خفیہ کلید (τx) کلائنٹ کے ذریعہ نجی رکھی جاتی ہے۔ اس کے بعد، کارکن یاؤ کے پروٹوکول کے حساب کتاب کے مراحل کو مسئلہ پیدا کرنے والے الگورتھم سے پیدا ہونے والے خفیہ متن پر لاگو کرتا ہے۔ یہ حتمی آؤٹ پٹ تار کی اقدار (σy) تک پہنچنے تک گیٹ سائفر ٹیکسٹس کو بار بار ڈکرپٹ کرکے کیا جاتا ہے۔ خفیہ کاری اسکیم کی ہومومورفک خصوصیات کارکن کو صحیح آؤٹ پٹ تار کی خفیہ کاری حاصل کرنے کے قابل بناتی ہیں۔ آخر میں، کارکن آؤٹ پٹ کے خفیہ متن کو کلائنٹ کو واپس کرتا ہے جو انہیں اصل آؤٹ پٹ y = F (x) یا δ کا حساب لگانے کے لیے ڈکرپٹ کرتا ہے۔ قابل تصدیق کمپیوٹیشن اسکیم کی تعریف میں کہا گیا ہے کہ اسکیم درست اور محفوظ دونوں ہونی چاہیے۔ اسکیم کی درستگی اس صورت میں حاصل کی جاتی ہے جب مسئلہ پیدا کرنے والا الگورتھم ایسی اقدار پیدا کرتا ہے جو ایک ایماندار کارکن کو انکوڈ شدہ آؤٹ پٹ اقدار کا حساب لگانے کے قابل بناتی ہیں جو کامیابی سے تصدیق کرے گی اور ان آدانوں پر F کی تشخیص سے مطابقت رکھتی ہیں۔ دوسری طرف، ایک قابل تصدیق کمپیوٹیشن اسکیم محفوظ ہے اگر کوئی بدنیتی پر مبنی کارکن تصدیق کے الگورتھم کو کسی دیئے گئے فنکشن F اور ان پٹ x کے لیے غلط آؤٹ پٹ کو قبول کرنے پر راضی نہیں کر سکتا ہے۔ عملی قابل تصدیق کمپیوٹنگ اگرچہ یہ دکھایا گیا تھا کہ نظریاتی طور پر قابل تصدیق کمپیوٹنگ ممکن ہے (مکمل طور پر ہومومورفک خفیہ کاری کا استعمال کرتے ہوئے یا ممکنہ طور پر قابل جانچ ثبوت کے ذریعے)، زیادہ تر معروف تعمیرات عملی طور پر بہت مہنگی ہیں۔ حال ہی میں، کچھ محققین نے قابل تصدیق حساب کو عملی بنانے پر غور کیا ہے۔ ایسی ہی ایک کوشش یو ٹی آسٹن کے محققین کا کام ہے۔ مصنفین ممکنہ طور پر قابل جانچ ثبوتوں پر مبنی دلیل کے نظام سے شروع کرتے ہیں اور اس کی لاگت کو 1020 کے عنصر سے کم کرتے ہیں۔ انہوں نے کالی مرچ کے نظام میں بھی اپنی تکنیکوں کو نافذ کیا۔ مصنفین نوٹ کرتے ہیں کہ "اب تک ہمارا نتیجہ یہ ہے کہ، محفوظ نظاموں کی تعمیر کے لیے ایک آلے کے طور پر، پی سی پیز اور دلیل کے نظام ایک گمشدہ وجہ نہیں ہیں"۔ مجموعی علاقے، جس میں اب مختلف گروپوں کے ذریعے متعدد نفاذ شامل ہیں، کا سروے کیا گیا ہے۔ 2010 کی دہائی میں، قابل تصدیق کمپیوٹنگ تکنیکوں نے بلاکچین ٹیکنالوجی میں عملی ایپلی کیشنز میں اضافہ دیکھا ہے۔ حوالہ جات محفوظ مواصلات تقسیم شدہ کمپیوٹنگ