اگر ہم ایک دوسرے پر بھروسہ نہیں کرتے تو کیا بے ترتیب نمبر بنانا ممکن ہے؟ حصہ 2

ارے حبر!

В پہلا حصہ اس آرٹیکل میں، ہم نے اس بات پر تبادلہ خیال کیا کہ ان شرکاء کے لیے بے ترتیب نمبر تیار کرنا کیوں ضروری ہو سکتا ہے جو ایک دوسرے پر بھروسہ نہیں کرتے، ایسے بے ترتیب نمبر جنریٹرز کے لیے کیا تقاضے پیش کیے جاتے ہیں، اور ان کے نفاذ کے لیے دو طریقوں پر غور کیا گیا۔

مضمون کے اس حصے میں، ہم ایک اور نقطہ نظر پر گہری نظر ڈالیں گے جو حد کے دستخطوں کا استعمال کرتا ہے۔

خفیہ نگاری کا تھوڑا سا

یہ سمجھنے کے لیے کہ تھریشولڈ دستخط کیسے کام کرتے ہیں، آپ کو تھوڑی سی بنیادی کرپٹوگرافی کو سمجھنا ہوگا۔ ہم دو تصورات استعمال کریں گے: اسکیلرز، یا محض اعداد، جنہیں ہم چھوٹے حروف سے ظاہر کریں گے (x، y) اور بیضوی وکر پر پوائنٹس، جنہیں ہم بڑے حروف سے ظاہر کریں گے۔

حد کے دستخطوں کی بنیادی باتوں کو سمجھنے کے لیے، آپ کو یہ سمجھنے کی ضرورت نہیں ہے کہ بیضوی منحنی خطوط کیسے کام کرتے ہیں، چند بنیادی چیزوں کے علاوہ:

1. بیضوی وکر پر پوائنٹس کو اسکیلر سے جوڑا اور ضرب کیا جاسکتا ہے (ہم اسکیلر سے ضرب کو اس طرح ظاہر کریں گے xG, اگرچہ اشارے Gx اکثر ادب میں بھی استعمال ہوتا ہے)۔ اسکیلر کے ذریعہ اضافے اور ضرب کا نتیجہ بیضوی وکر پر ایک نقطہ ہے۔

2. صرف نکتہ جاننا G اور اسکیلر کے ساتھ اس کی مصنوعات xG شمار نہیں کیا جا سکتا x.

ہم کثیر الجہتی کا تصور بھی استعمال کریں گے۔ p(x) ڈگری k-1۔ خاص طور پر، ہم polynomials کی درج ذیل خاصیت کا استعمال کریں گے: اگر ہم قدر جانتے ہیں۔ p(x) کسی کے لیے k مختلف x (اور ہمارے پاس اس کے بارے میں مزید معلومات نہیں ہیں۔ p(x))، ہم حساب کر سکتے ہیں۔ p(x) کسی اور کے لیے x.

یہ دلچسپ ہے کہ کسی بھی کثیر الثانی کے لیے p(x) اور وکر پر کچھ نقطہ Gمطلب جاننا p(x)G کسی کے لیے k مختلف معنی x، ہم بھی حساب کر سکتے ہیں p(x)G کسی کے لیے x.

یہ تفصیلات جاننے کے لیے کافی معلومات ہیں کہ تھریشولڈ دستخط کیسے کام کرتے ہیں اور بے ترتیب نمبر بنانے کے لیے ان کا استعمال کیسے کریں۔

حد کے دستخطوں پر بے ترتیب نمبر جنریٹر

چلو یہ کہتے ہیں۔ n شرکاء ایک بے ترتیب نمبر بنانا چاہتے ہیں، اور ہم چاہتے ہیں کہ کوئی بھی حصہ لے k ان میں سے ایک نمبر پیدا کرنے کے لیے کافی تھے، لیکن حملہ آوروں کو جو کنٹرول کرتے ہیں۔ k-1 یا اس سے کم شرکاء پیدا ہونے والی تعداد کی پیش گوئی یا اثر انداز نہیں کر سکے۔

فرض کریں کہ ایک ایسی کثیر الثانی ہے۔ p(x) ڈگری k-1 جو پہلا حصہ لینے والا جانتا ہے۔ p (1)، دوسرا جانتا ہے۔ p(2)، اور اسی طرح (n- وہ جانتا ہے p(n))۔ ہم یہ بھی فرض کرتے ہیں کہ کچھ پہلے سے طے شدہ نقطہ کے لئے G سب جانتے ہیں p(x)G تمام اقدار کے لیے x. ہم کال کریں گے۔ p(i) "نجی جزو" iویں شریک (کیونکہ صرف iحصہ لینے والا اسے جانتا ہے) اور p(i) جی "عوامی جزو" i-ویں شریک (کیونکہ تمام شرکاء اسے جانتے ہیں)۔ جیسا کہ آپ کو یاد ہے، علم p(i) جی بحال کرنے کے لئے کافی نہیں ہے p(i)

اس طرح کا کثیر الجہتی تخلیق کرنا تاکہ صرف i-پہلا حصہ لینے والا اور کوئی بھی اس کے نجی جزو کو نہیں جانتا تھا - یہ پروٹوکول کا سب سے پیچیدہ اور دلچسپ حصہ ہے، اور ہم ذیل میں اس کا تجزیہ کریں گے۔ ابھی کے لیے، آئیے فرض کریں کہ ہمارے پاس ایسا کثیر الثانی ہے اور تمام شرکاء اپنے نجی اجزاء کو جانتے ہیں۔

بے ترتیب نمبر بنانے کے لیے ہم اس طرح کے کثیر الثانی کو کیسے استعمال کر سکتے ہیں؟ شروع کرنے کے لیے، ہمیں کچھ اسٹرنگ کی ضرورت ہے جو پہلے جنریٹر میں ان پٹ کے طور پر استعمال نہیں ہوئی ہے۔ بلاکچین کی صورت میں، آخری بلاک کا ہیش h اس طرح کی لائن کے لئے ایک اچھا امیدوار ہے. شرکاء کو استعمال کرتے ہوئے ایک بے ترتیب نمبر بنانا چاہتے ہیں۔ h بیج کی طرح. شرکاء پہلے تبدیل کرتے ہیں۔ h کسی بھی پہلے سے طے شدہ فنکشن کا استعمال کرتے ہوئے وکر پر ایک نقطہ پر:

H = scalarToPoint(h)

پھر ہر شریک i حساب لگاتا ہے اور شائع کرتا ہے۔ Hi = p(i)H، وہ کیا کر سکتے ہیں کیونکہ وہ جانتے ہیں۔ p(i) اور H. انکشاف Hمیں دوسرے شرکاء کو نجی جزو کو بحال کرنے کی اجازت نہیں دیتا iحصہ لینے والا، اور اس لیے نجی اجزاء کا ایک سیٹ بلاک سے بلاک تک استعمال کیا جا سکتا ہے۔ اس طرح، ذیل میں بیان کردہ مہنگے کثیر الجہتی الگورتھم کو صرف ایک بار عمل میں لانے کی ضرورت ہے۔

جب k شرکاء کا پوسٹ مارٹم کیا گیا۔ Hi = p(i)H، ہر کوئی حساب کر سکتا ہے Hx = p(x)H سب کے لیے x polynomials کی خاصیت کا شکریہ جس پر ہم نے پچھلے حصے میں بات کی تھی۔ اس وقت، تمام شرکاء حساب لگاتے ہیں۔ H0 = p(0)H، اور یہ نتیجہ بے ترتیب نمبر ہے۔ براہ کرم نوٹ کریں کہ کوئی نہیں جانتا ہے۔ p(0)، اور اس لیے حساب کرنے کا واحد طریقہ p(0)H - یہ انٹرپولیشن ہے p(x)H، جو تبھی ممکن ہے جب k اقدار p(i)H جانا جاتا ہے کسی بھی چھوٹی مقدار کو کھولنا p(i)H کے بارے میں کوئی معلومات فراہم نہیں کرتا p(0)H

مذکورہ جنریٹر میں وہ تمام خصوصیات ہیں جو ہم چاہتے ہیں: حملہ آور صرف کنٹرول کرتے ہیں۔ k-1 یا اس سے کم شرکاء کے پاس نتیجہ پر کوئی معلومات یا اثر نہیں ہے، جبکہ کوئی بھی k شرکاء نتیجہ نمبر، اور کسی بھی ذیلی سیٹ کا حساب لگا سکتے ہیں۔ k شرکاء ہمیشہ ایک ہی بیج کے لیے ایک ہی نتیجہ پر آئیں گے۔

ایک مسئلہ ہے جس سے ہم نے اوپر احتیاط سے گریز کیا۔ انٹرپولیشن کے کام کرنے کے لیے، یہ ضروری ہے کہ قدر Hi جسے ہر شریک نے شائع کیا تھا۔ i یہ واقعی ایک ہی تھا p(i)H چونکہ اس کے سوا کوئی نہیں۔ i- حصہ لینے والا نہیں جانتا p(i) کے علاوہ کوئی نہیں i-شریک اس کی تصدیق نہیں کر سکتا Hi درحقیقت درست طریقے سے، اور درستگی کے کسی خفیہ ثبوت کے بغیر Hمیں ایک حملہ آور کسی بھی قدر کو بطور شائع کر سکتا ہے۔ ہیلو، اور من مانی طور پر بے ترتیب نمبر جنریٹر کے آؤٹ پٹ کو متاثر کرتا ہے۔:

پہلے شریک کی طرف سے بھیجی گئی H_1 کی مختلف اقدار مختلف H_0 کی طرف لے جاتی ہیں۔

درستگی ثابت کرنے کے کم از کم دو طریقے ہیں۔ Hi، ہم کثیر نام کی نسل کا تجزیہ کرنے کے بعد ان پر غور کریں گے۔

کثیر الجہتی نسل

آخری حصے میں ہم نے فرض کیا کہ ہمارے پاس اس طرح کا کثیر الجہتی ہے۔ p(x) ڈگری k-1 کہ شریک i جانتا ہے p(i)، اور کسی کے پاس اس قدر کے بارے میں کوئی معلومات نہیں ہے۔ اگلے حصے میں ہمیں کچھ پہلے سے طے شدہ نکتے کے لیے بھی اس کی ضرورت ہوگی۔ G سب کو معلوم تھا p(x)G سب کے لیے x.

اس سیکشن میں ہم فرض کریں گے کہ ہر شریک کے پاس مقامی طور پر کچھ نجی کلید ہوتی ہے۔ xi، اس طرح کہ ہر کوئی متعلقہ عوامی کلید کو جانتا ہے۔ Xi.

ایک ممکنہ کثیر الثانی نسل پروٹوکول مندرجہ ذیل ہے:

1. ہر شریک i مقامی طور پر ایک صوابدیدی کثیر الجہتی تخلیق کرتا ہے۔ pi(x) ڈگری k-1۔ پھر وہ ہر شریک کو بھیجتے ہیں۔ j قیمت pi(j)، عوامی کلید کے ساتھ خفیہ کردہ ایکس جے اس طرح صرف i-ویں и j-ویں شریک جانتے ہیں pi(j) حصہ لینے والا i عوامی طور پر اعلان بھی کرتا ہے۔ pi(j)G سب کے لیے j سے 1 پر k شامل

2. تمام شرکاء انتخاب کے لیے کچھ اتفاق رائے کا استعمال کرتے ہیں۔ k شرکاء جن کے کثیر نام استعمال کیے جائیں گے۔ چونکہ کچھ شرکاء آف لائن ہو سکتے ہیں، ہم سب تک انتظار نہیں کر سکتے n شرکاء polynomials شائع کریں گے. اس قدم کا نتیجہ ایک سیٹ ہے۔ Z کم از کم پر مشتمل ہے k مرحلہ (1) میں بنائے گئے کثیر نام.

3. شرکاء اس بات کو یقینی بناتے ہیں کہ وہ اقدار جانتے ہیں۔ pi(j) عوامی طور پر اعلان کردہ کے مطابق ہے۔ pi(j)G اس قدم کے بعد Z صرف کثیر الجہتی جن کے لیے نجی طور پر منتقل کیا جاتا ہے۔ pi(j) عوامی طور پر اعلان کردہ کے مطابق ہے۔ pi(j)G

4. ہر شریک j اس کے نجی جزو کا حساب لگاتا ہے۔ p(j) ایک رقم کے طور پر pi(j) سب کے لیے i в Z. ہر شریک تمام اقدار کا حساب بھی لگاتا ہے۔ p(x)G ایک رقم کے طور پر pi(x)G for all i в Z.

براہ کرم نوٹ کریں p(x) - یہ واقعی ایک کثیر الجہتی ہے۔ k-1، کیونکہ یہ فرد کا مجموعہ ہے۔ pi(x)، جن میں سے ہر ایک ڈگری کا کثیر الجہتی ہے۔ k-1۔ اس کے بعد، نوٹ کریں کہ ہر ایک شریک کے دوران j جانتا ہے p(j) ان کے بارے میں کوئی معلومات نہیں ہیں p(x) لیے x ≠ j. درحقیقت، اس قدر کا حساب کرنے کے لیے، انہیں سب کچھ جاننے کی ضرورت ہے۔ pi(x)، اور جب تک شریک j کم از کم منتخب کثیر الثانیات میں سے ایک کو نہیں جانتے، ان کے پاس اس کے بارے میں کافی معلومات نہیں ہیں۔ p(x)۔

یہ پورا کثیر الثانی نسل کا عمل ہے جس کی آخری سیکشن میں ضرورت تھی۔ مندرجہ بالا اقدامات 1، 2 اور 4 میں کافی واضح نفاذ ہے۔ لیکن مرحلہ 3 اتنا معمولی نہیں ہے۔

خاص طور پر، ہمیں یہ ثابت کرنے کے قابل ہونے کی ضرورت ہے کہ یہ خفیہ کردہ ہے۔ pi(j) واقعی شائع شدہ سے مطابقت رکھتا ہے۔ pi(j)G اگر ہم ثابت نہ کر سکے تو حملہ آور i اس کے بجائے کوڑا بھیج سکتا ہے۔ pi(j) حصہ لینے والے کو j، اور شریک j حقیقی معنی حاصل نہیں کر سکیں گے۔ pi(j)، اور اس کے نجی جزو کا حساب نہیں لگا سکے گا۔.

ایک کرپٹوگرافک پروٹوکول ہے جو آپ کو ایک اضافی پیغام بنانے کی اجازت دیتا ہے۔ ثبوتi(j)، اس طرح کہ کوئی بھی شریک، کچھ قدر رکھتا ہو۔ e, بھی ثبوت (جے) и pi(j)G، مقامی طور پر اس کی تصدیق کر سکتا ہے۔ e - یہ واقعی ہے pi(j)، شرکت کنندہ کی کلید کے ساتھ خفیہ کردہ j. بدقسمتی سے، اس طرح کے شواہد کا سائز ناقابل یقین حد تک بڑا ہے، اور یہ دیکھتے ہوئے کہ اسے شائع کرنا ضروری ہے۔ O(nk) ایسے شواہد کو اس مقصد کے لیے استعمال نہیں کیا جا سکتا۔

اس کو ثابت کرنے کے بجائے pi(j) سے مساوی pi(j)G ہم پولی نامی جنریشن پروٹوکول میں وقت کی ایک بہت بڑی مدت مختص کر سکتے ہیں، جس کے دوران تمام شرکاء موصول شدہ خفیہ کردہ چیک کرتے ہیں۔ pi(j)، اور اگر ڈکرپٹ شدہ پیغام عوام سے مطابقت نہیں رکھتا ہے۔ pi(j)G، وہ ایک خفیہ ثبوت شائع کرتے ہیں کہ ان کو موصول ہونے والا خفیہ پیغام غلط ہے۔ اس پیغام کو ثابت کریں۔ کوئی سے مساوی pi(G) یہ ثابت کرنے سے کہیں زیادہ آسان ہے کہ یہ مماثل ہے۔ واضح رہے کہ اس کے لیے ہر شریک کو اس طرح کے ثبوت بنانے کے لیے مختص وقت کے دوران کم از کم ایک بار آن لائن حاضر ہونے کی ضرورت ہوتی ہے، اور اس مفروضے پر انحصار کرتا ہے کہ اگر وہ ایسا ثبوت شائع کرتے ہیں، تو یہ اسی مختص وقت میں دیگر تمام شرکاء تک پہنچ جائے گا۔

اگر کوئی شریک اس مدت کے دوران آن لائن ظاہر نہیں ہوا، اور اس کے پاس کم از کم ایک غلط جزو تھا، تو وہ مخصوص شریک مزید تعداد کی تیاری میں حصہ نہیں لے سکے گا۔ پروٹوکول، تاہم، اگر کم از کم ہے تو پھر بھی کام کرے گا۔ k وہ شرکاء جنہوں نے یا تو صرف صحیح اجزاء حاصل کیے یا مقررہ وقت کے اندر غلط ہونے کا ثبوت چھوڑنے میں کامیاب رہے۔

H_i کی درستگی کے ثبوت

آخری حصہ جس پر بحث کرنا باقی ہے وہ یہ ہے کہ شائع کی درستگی کو کیسے ثابت کیا جائے۔ Hمیں، یعنی کہ Hi = p(i)H، کھولے بغیر p(i)

ہمیں یاد ہے کہ اقدار H, G, p (i) G عوامی اور سب کے لیے جانا جاتا ہے۔ آپریشن وصول کریں۔ p(i) جاننا p(i) جی и G مجرد لوگارتھم کہلاتا ہے، یا dlog اور ہم یہ ثابت کرنا چاہتے ہیں:

dlog(p(i)G, G) = dlog(Hi, H)

انکشاف کے بغیر p(i). مثال کے طور پر اس طرح کے ثبوتوں کی تعمیرات موجود ہیں۔ شنور پروٹوکول.

اس ڈیزائن کے ساتھ، ہر شریک، ساتھ ساتھ Hi ڈیزائن کے مطابق درستگی کا ثبوت بھیجتا ہے۔

ایک بار جب کوئی بے ترتیب نمبر تیار ہو جاتا ہے، تو اسے اکثر شرکاء کے علاوہ ان لوگوں کے استعمال کرنے کی ضرورت ہوتی ہے جنہوں نے اسے تیار کیا تھا۔ ایسے شرکاء نمبر کے ساتھ سب کو ضرور بھیجیں۔ Hi اور متعلقہ ثبوت۔

ایک متجسس قاری پوچھ سکتا ہے: چونکہ حتمی بے ترتیب نمبر ہے۔ H0، اور p(0)G - یہ عوامی معلومات ہے، ہمیں ہر فرد کے لیے ثبوت کی ضرورت کیوں ہے۔ Hمیں، اس کے بجائے ثبوت کیوں نہیں بھیجتا

dlog(p(0)G, G) = dlog(H0, H)

مسئلہ یہ ہے کہ شنور پروٹوکول کا استعمال کرتے ہوئے ایسا ثبوت نہیں بنایا جا سکتا کیونکہ کوئی بھی اس کی قدر نہیں جانتا p (0), ثبوت بنانے کے لیے ضروری ہے، اور مزید یہ کہ پورا بے ترتیب نمبر جنریٹر اس حقیقت پر مبنی ہے کہ کوئی بھی اس قدر کو نہیں جانتا۔ اس لیے تمام اقدار کا ہونا ضروری ہے۔ Hi اور درست ثابت کرنے کے لیے ان کے انفرادی ثبوت H0.

تاہم، اگر بیضوی منحنی خطوط پر کچھ آپریشن ہوتے ہیں جو کہ ضرب سے مماثلت رکھتے ہیں، تو درستی کا ثبوت H0 معمولی بات ہوگی، ہم صرف اس بات کو یقینی بنائیں گے۔

H0 × G = p(0)G × H

اگر منتخب وکر سپورٹ کرتا ہے۔ بیضوی وکر کے جوڑے، یہ ثبوت کام کرتا ہے۔ اس معاملے میں H0 نہ صرف ایک بے ترتیب نمبر جنریٹر کا آؤٹ پٹ ہے، جس کی تصدیق کسی بھی شریک کے ذریعہ کی جا سکتی ہے جو جانتا ہے جی، ایچ и p(0)جی ایچ0 پیغام پر ایک دستخط بھی ہے جو بطور بیج استعمال کیا گیا تھا، اس کی تصدیق کرتا ہے۔ k и n شرکاء نے اس پیغام پر دستخط کیے۔ اس طرح، اگر بیج - پھر بلاکچین پروٹوکول میں بلاک کا ہیش ہے۔ H0 بلاک پر ایک کثیر دستخط اور ایک بہت اچھا بے ترتیب نمبر دونوں ہے۔

آخر میں

یہ مضمون تکنیکی بلاگ سیریز کا حصہ ہے۔ قریب. NEAR ایک بلاک چین پروٹوکول اور پلیٹ فارم ہے جس میں وکندریقرت ایپلی کیشنز کو تیار کیا جاتا ہے جس میں ترقی کی آسانی اور اختتامی صارفین کے لیے استعمال میں آسانی پر زور دیا جاتا ہے۔

پروٹوکول کوڈ کھلا ہوا ہے، ہمارا نفاذ Rust میں لکھا ہوا ہے، اسے مل سکتا ہے۔ یہاں.

آپ دیکھ سکتے ہیں کہ NEAR کی ترقی کیسی دکھتی ہے اور آن لائن IDE میں تجربہ کر سکتے ہیں۔ یہاں.

آپ روسی زبان میں تمام خبروں پر عمل کر سکتے ہیں۔ ٹیلیگرام گروپ اور VKontakte پر گروپ، اور سرکاری میں انگریزی میں ٹویٹر.

встреч скорых встреч!

ماخذ: www.habr.com