آیا در صورت عدم اعتماد به یکدیگر امکان تولید اعداد تصادفی وجود دارد؟ قسمت 2

هی هابر!

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

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

کمی رمزنگاری

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

برای درک اصول اولیه امضاهای آستانه، به جز چند مورد اساسی، نیازی به درک نحوه عملکرد منحنی های بیضوی ندارید:

1. نقاط روی یک منحنی بیضوی را می توان با یک اسکالر اضافه و ضرب کرد (ضرب در یک اسکالر را به عنوان نشان می دهیم xG، اگرچه نماد Gx همچنین اغلب در ادبیات استفاده می شود). حاصل جمع و ضرب با اسکالر نقطه ای از منحنی بیضوی است.

2. دانستن تنها نکته G و محصول آن با اسکالر xG قابل محاسبه نیست x.

از مفهوم چند جمله ای نیز استفاده خواهیم کرد p(x) درجه k-1. به طور خاص، از ویژگی زیر چند جمله ای ها استفاده خواهیم کرد: اگر مقدار را بدانیم 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 چیزی که اولین شرکت کننده می داند پ (1)، دومی می داند p(2) و غیره (n-th می داند p(n)). ما همچنین فرض می کنیم که برای برخی از نقاط از پیش تعیین شده G همه میدانند p(x)G برای همه ارزش ها x. تماس خواهیم گرفت p(i) "جزء خصوصی" iشرکت‌کننده‌ام (زیرا فقط iشرکت‌کننده‌ام او را می‌شناسد)، و p(i)G "مولفه عمومی" iشرکت کننده -ام (زیرا همه شرکت کنندگان او را می شناسند). همانطور که به یاد دارید، دانش p(i)G برای بازیابی کافی نیست p(i).

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

چگونه می توانیم از چنین چند جمله ای برای تولید یک عدد تصادفی استفاده کنیم؟ برای شروع، به رشته ای نیاز داریم که قبلاً به عنوان ورودی ژنراتور استفاده نشده باشد. در مورد بلاک چین، هش آخرین بلاک است h کاندیدای خوبی برای چنین خطی است. اجازه دهید شرکت کنندگان بخواهند با استفاده از یک عدد تصادفی ایجاد کنند h مانند دانه شرکت کنندگان ابتدا تبدیل می شوند h به نقطه ای از منحنی با استفاده از هر تابع از پیش تعریف شده:

H = scalarToPoint(h)

سپس هر شرکت کننده i محاسبه و منتشر می کند سلام = p(i)H، چه کاری می توانند بکنند چون می دانند p(i) و H. افشای Hمن به سایر شرکت‌کنندگان اجازه نمی‌دهم مؤلفه خصوصی را بازیابی کنند iشرکت‌کننده، و بنابراین یک مجموعه از اجزای خصوصی را می‌توان از بلوکی به بلوک دیگر استفاده کرد. بنابراین، الگوریتم تولید چند جمله ای گران قیمت که در زیر توضیح داده شده است، فقط باید یک بار اجرا شود.

وقتی که k شرکت کنندگان کالبد شکافی شدند سلام = p(i)H، همه می توانند محاسبه کنند Hx = p(x)H برای همه x با تشکر از خاصیت چندجمله ای ها که در بخش آخر بحث کردیم. در این لحظه، همه شرکت کنندگان محاسبه می کنند 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)، رمزگذاری شده با کلید عمومی Xj. بنابراین تنها i-ی и j-ی شرکت کننده می داند pi (j). شرکت کننده i نیز علنی اعلام می کند pi(j)G برای همه j از 1 به k شامل

2. همه شرکت کنندگان از برخی اجماع برای انتخاب استفاده می کنند k شرکت‌کنندگانی که از چندجمله‌ای آنها استفاده خواهد شد. از آنجایی که ممکن است برخی از شرکت‌کنندگان آفلاین باشند، نمی‌توانیم تا همه منتظر بمانیم n شرکت کنندگان چند جمله ای ها را منتشر خواهند کرد. نتیجه این مرحله یک مجموعه است 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 برای همه i в Z.

لطفا توجه داشته باشید که p(x) - این واقعا یک چند جمله ای است k-1، زیرا مجموع فرد است pi(x)، که هر کدام چند جمله ای درجه هستند k-1. سپس، توجه داشته باشید که در حالی که هر شرکت کننده j می داند p(j) آنها هیچ اطلاعاتی در مورد آن ندارند p(x) برای x ≠ j. در واقع، برای محاسبه این مقدار، آنها باید همه چیز را بدانند پی (x)، و تا زمانی که شرکت کننده j حداقل یکی از چند جمله ای های انتخاب شده را نمی شناسد، اطلاعات کافی در مورد آن ندارند p(x).

این کل فرآیند تولید چند جمله ای است که در بخش آخر مورد نیاز بود. مراحل 1، 2 و 4 بالا پیاده سازی نسبتاً واضحی دارند. اما مرحله 3 چندان پیش پا افتاده نیست.

به طور خاص، ما باید بتوانیم رمزگذاری شده را اثبات کنیم pi(j) واقعاً با موارد منتشر شده مطابقت دارد pi(j)G. اگر نتوانیم آن را ثابت کنیم، مهاجم i ممکن است به جای آن زباله بفرستد pi(j) به شرکت کننده j، و شرکت کننده j نمی تواند ارزش واقعی را بدست آورد پی (j)، و قادر به محاسبه جزء خصوصی آن نخواهد بود.

یک پروتکل رمزنگاری وجود دارد که به شما امکان می دهد یک پیام اضافی ایجاد کنید اثباتi(j)، به گونه ای که هر شرکت کننده دارای مقداری ارزش باشد e, همچنین اثبات (j) и pi(j)G، می تواند به صورت محلی آن را تأیید کند e - واقعا همینطوره پی (j)، رمزگذاری شده با کلید شرکت کننده j. متأسفانه حجم چنین شواهدی فوق العاده زیاد است و با توجه به اینکه انتشار آن ضروری است O(nk) چنین شواهدی را نمی توان برای این منظور مورد استفاده قرار داد.

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

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

شواهد صحت H_i

آخرین قسمتی که باید مورد بحث قرار گیرد چگونگی اثبات صحت منتشر شده است Hمن، یعنی آن سلام = p(i)H، بدون باز کردن p(i).

به یاد داشته باشید که ارزش ها H، G، p(i)G عمومی و برای همه شناخته شده است. عملیات را دریافت کنید p(i) دانستن p(i)G и 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)

مشکل این است که چنین اثباتی را نمی توان با استفاده از پروتکل Schnorr ایجاد کرد زیرا هیچ کس ارزش آن را نمی داند پ (0)، برای ایجاد اثبات لازم است، و علاوه بر این، کل مولد اعداد تصادفی بر اساس این واقعیت است که هیچ کس این مقدار را نمی داند. بنابراین لازم است همه ارزش ها را داشته باشیم Hi و شواهد فردی آنها برای اثبات صحت H0.

اما اگر روی نقاط منحنی بیضوی عملیاتی وجود داشته باشد که از نظر معنایی شبیه ضرب باشد، اثبات صحت H0 بی اهمیت خواهد بود، ما به سادگی از آن مطمئن می شویم

H0 G = p(0)G × H

اگر منحنی انتخاب شده پشتیبانی می کند جفت های منحنی بیضوی، این اثبات کار می کند. در این مورد H0 نه تنها خروجی یک تولید کننده اعداد تصادفی است، که می تواند توسط هر شرکت کننده ای که می داند تأیید شود. جی، اچ и p(0)G. اچ0 همچنین امضایی بر روی پیامی است که به عنوان دانه استفاده شده است و تأیید کننده آن است k и n شرکت کنندگان این پیام را امضا کردند. بنابراین، اگر دانه - پس هش بلوک در پروتکل بلاک چین است H0 هم یک امضای چندگانه در یک بلوک است و هم یک عدد تصادفی بسیار خوب.

در نتیجه

این مقاله بخشی از یک سری وبلاگ فنی است نزدیک. NEAR یک پروتکل و پلت فرم بلاک چین برای توسعه برنامه های غیرمتمرکز با تاکید بر سهولت توسعه و سهولت استفاده برای کاربران نهایی است.

کد پروتکل باز است، پیاده سازی ما در Rust نوشته شده است، می توان آن را پیدا کرد اینجا.

می توانید ببینید که توسعه NEAR چگونه است و در IDE آنلاین آزمایش کنید اینجا.

شما می توانید تمام اخبار را به زبان روسی در اینجا دنبال کنید گروه تلگرام و گروه در VKontakte، و به زبان انگلیسی در رسمی توییتر.

به زودی میبینمت!

منبع: www.habr.com