هل من الممكن توليد أرقام عشوائية إذا كنا لا نثق ببعضنا البعض؟ الجزء 2

يا هبر!

В الجزء الأول في هذه المقالة، ناقشنا لماذا قد يكون من الضروري إنشاء أرقام عشوائية للمشاركين الذين لا يثقون ببعضهم البعض، وما هي المتطلبات المطروحة لمولدات الأرقام العشوائية هذه، ونظرنا في طريقتين لتنفيذها.

في هذا الجزء من المقالة، سنلقي نظرة فاحصة على نهج آخر يستخدم توقيعات العتبة.

قليلا من التشفير

من أجل فهم كيفية عمل توقيعات العتبة، تحتاج إلى فهم القليل من التشفير الأساسي. سوف نستخدم مفهومين: العددية، أو ببساطة الأرقام، والتي سنشير إليها بأحرف صغيرة (س ، ص) والنقاط الموجودة على المنحنى الإهليلجي والتي سنشير إليها بالأحرف الكبيرة.

لفهم أساسيات توقيعات العتبة، لا تحتاج إلى فهم كيفية عمل المنحنيات الإهليلجية، بخلاف بعض الأشياء الأساسية:

1. يمكن إضافة النقاط على المنحنى الإهليلجي وضربها في عددية (سنشير إلى الضرب في عددية كما يلي: xG، على الرغم من التدوين Gx وكثيرا ما تستخدم أيضا في الأدب). نتيجة الجمع والضرب في العدد هو نقطة على منحنى إهليلجي.

2. معرفة النقطة فقط G ومنتجها مع العددية xG لا يمكن حسابها x.

سوف نستخدم أيضًا مفهوم كثير الحدود ص (خ) درجة k-1. على وجه الخصوص، سوف نستخدم الخاصية التالية لكثيرات الحدود: إذا كنا نعرف القيمة ص (خ) لأي k مختلف x (وليس لدينا مزيد من المعلومات حول ص (خ))، يمكننا الحساب ص (خ) لأي شخص آخر x.

ومن المثير للاهتمام أنه لأي متعدد الحدود ص (خ) ونقطة ما على المنحنى Gمعرفة المعنى ع(خ)ز لأي k معان مختلفة x، يمكننا أيضًا الحساب ع(خ)ز لأي x.

هذه معلومات كافية للبحث في تفاصيل كيفية عمل توقيعات العتبة وكيفية استخدامها لإنشاء أرقام عشوائية.

مولد أرقام عشوائية على التوقيعات العتبة

دعنا نقول ذلك n يريد المشاركون إنشاء رقم عشوائي، ونريد أن يشارك أي شخص k كان هناك ما يكفي منهم لتوليد عدد، ولكن حتى يتمكن المهاجمون من السيطرة k-1 أو أقل من المشاركين لم يتمكنوا من التنبؤ أو التأثير على العدد الناتج.

لنفترض أن هناك مثل هذا كثير الحدود ص (خ) درجة k-1 ما يعرفه المشارك الأول ص (1)، والثاني يعرف ص (2)، وما إلى ذلك وهلم جرا (n-يعرف ص (ن)). نحن نفترض أيضًا ذلك بالنسبة لبعض النقاط المحددة مسبقًا G الجميع يعرف ع(خ)ز لجميع القيم x. سنطالب باي) "المكون الخاص" iالمشارك الرابع (لأن فقط iالمشارك الرابع يعرفها)، و خنزير "المكون العام" i-المشاركه الرابعه (لأن جميع المشاركين يعرفونها). كما تتذكر المعرفة خنزير لا يكفي لاستعادة باي).

إنشاء مثل هذا كثير الحدود بحيث فقط i-المشارك الثالث ولا أحد يعرف مكونه الخاص هو الجزء الأكثر تعقيدًا وإثارة للاهتمام في البروتوكول، وسنقوم بتحليله أدناه. في الوقت الحالي، لنفترض أن لدينا كثيرة الحدود وأن جميع المشاركين يعرفون مكوناتهم الخاصة.

كيف يمكننا استخدام مثل هذا كثير الحدود لتوليد رقم عشوائي؟ في البداية، نحتاج إلى سلسلة لم يتم استخدامها من قبل كمدخل للمولد. في حالة blockchain، تجزئة الكتلة الأخيرة h هو مرشح جيد لمثل هذا الخط. اسمح للمشاركين بإنشاء رقم عشوائي باستخدام h مثل البذور. يقوم المشاركون بالتحويل أولاً h إلى نقطة على المنحنى باستخدام أي وظيفة محددة مسبقًا:

ح = العدديةToPoint(ح)

ثم كل مشارك i يحسب وينشر مرحبا = ص (ط) ح، ماذا يمكنهم أن يفعلوا لأنهم يعرفون ص (ط) و ح. كشف Hلا أسمح للمشاركين الآخرين باستعادة المكون الخاص iالمشارك الرابع، وبالتالي يمكن استخدام مجموعة واحدة من المكونات الخاصة من كتلة إلى أخرى. وبالتالي، فإن خوارزمية إنشاء كثيرات الحدود المكلفة الموصوفة أدناه تحتاج إلى تنفيذها مرة واحدة فقط.

عندما k تم تشريح جثث المشاركين مرحبا = ص (ط) ح، يمكن للجميع حساب Hس = ع (س) ح للجميع x وذلك بفضل خاصية كثيرات الحدود التي ناقشناها في القسم الأخير. في هذه اللحظة، يقوم جميع المشاركين بالحساب H0 = ص (0) ح، وهذا هو الرقم العشوائي الناتج. يرجى ملاحظة أن لا أحد يعرف ص (0)، وبالتالي فإن الطريقة الوحيدة لحساب ع (0) ح - هذا هو الاستيفاء ع (س) ح، وهو أمر ممكن فقط عندما k القيم ص (ط) ح معروف. فتح أي كمية أقل ص (ط) ح لا يقدم أي معلومات عنه ع(0)ح.

يحتوي المولد أعلاه على جميع الخصائص التي نريدها: المهاجمون يتحكمون فقط k-1- المشاركون أو أقل ليس لديهم أي معلومات أو تأثير على الاستنتاج، بينما أي k يمكن للمشاركين حساب العدد الناتج، وأي مجموعة فرعية من k سيصل المشاركون دائمًا إلى نفس النتيجة لنفس البذرة.

هناك مشكلة واحدة تجنبناها بعناية أعلاه. لكي يعمل الاستيفاء، من المهم أن تكون القيمة Hi الذي نشره كل مشارك i لقد كان هو نفسه حقًا ص (ط) ح. إذ لا أحد إلا i-المشارك لا يعرف باي)، لا أحد باستثناء i-لا يمكن للمشارك التحقق من ذلك Hi تم حسابها بشكل صحيح بالفعل، وبدون أي دليل تشفيري على صحتها Hيمكن للمهاجم نشر أي قيمة كـ مرحبا، والتأثير بشكل تعسفي على إخراج مولد الأرقام العشوائية:

تؤدي القيم المختلفة لـ H_1 التي أرسلها المشارك الأول إلى نتيجة مختلفة لـ H_0

هناك طريقتان على الأقل لإثبات الصحة Hأنا، سننظر فيها بعد أن نحلل توليد كثير الحدود.

جيل متعدد الحدود

في القسم الأخير افترضنا أن لدينا مثل هذا كثير الحدود ص (خ) درجة k-1 أن المشارك i لأنه يعلم باي)، ولا أحد لديه أي معلومات عن هذه القيمة. في القسم التالي، سنحتاج أيضًا إلى ذلك لبعض النقاط المحددة مسبقًا G عرف الجميع ع(خ)ز للجميع x.

سنفترض في هذا القسم أن كل مشارك محليًا لديه بعض المفاتيح الخاصة الحادي عشر, بحيث يعرف الجميع المفتاح العام المقابل Xi.

أحد بروتوكولات توليد متعدد الحدود الممكنة هو كما يلي:

1. كل مشارك i محليا ينشئ كثير الحدود التعسفي بي (خ) درجة ك-1. ثم يرسلون كل مشارك j قيمة pi(j)، مشفر بالمفتاح العام XJ. هكذا فقط i-عشر и j-عشر يعرف المشارك pاي جاي). مشارك i تعلن أيضا علنا بي(ي)ز للجميع j من 1 إلى k شمولية.

2. يستخدم جميع المشاركين بعض الإجماع للاختيار k المشاركين الذين سيتم استخدام كثيرات الحدود الخاصة بهم. نظرًا لأن بعض المشاركين قد يكونون غير متصلين بالإنترنت، فلا يمكننا الانتظار حتى يتمكن الجميع من ذلك n سيقوم المشاركون بنشر كثيرات الحدود. نتيجة هذه الخطوة هي مجموعة Z تتكون على الأقل k كثيرات الحدود التي تم إنشاؤها في الخطوة (1).

3. يتأكد المشاركون من أن القيم التي يعرفونها pط (ي) تتوافق مع المعلن عنها علنا بي(ي)ز. بعد هذه الخطوة Z فقط كثيرات الحدود التي تنتقل بشكل خاص pط (ي) تتوافق مع المعلن عنها علنا بي(ي)ز.

4. كل مشارك j يحسب مكونه الخاص ع (ي) كمجموع pط (ي) للجميع i в Z. يقوم كل مشارك أيضًا بحساب جميع القيم ع(خ)ز كمجموع pi(x)G للجميع أنا в Z.

يرجى ملاحظة أن ع (خ) - انها حقا كثيرة الحدود ك-1, لأنه مجموع الفرد pi(x)، كل منها متعدد الحدود من الدرجة k-1. ثم، لاحظ أنه بينما كل مشارك j لأنه يعلم ع (ي)، ليس لديهم معلومات عنه ص (خ) إلى س ≠ ي. في الواقع، لحساب هذه القيمة، يحتاجون إلى معرفة كل شيء بي (س)، وطالما أن المشارك j لا يعرف واحدًا على الأقل من كثيرات الحدود المحددة، وليس لديه معلومات كافية عنها ع (خ).

هذه هي عملية إنشاء كثيرات الحدود بأكملها التي كانت مطلوبة في القسم الأخير. الخطوات 1 و2 و4 أعلاه لها تنفيذ واضح إلى حد ما. ولكن الخطوة 3 ليست تافهة جدا.

على وجه التحديد، نحن بحاجة إلى أن نكون قادرين على إثبات أن التشفير pi(j) تتوافق حقًا مع المنشورات بي(ي)ز. إذا لم نتمكن من إثبات ذلك، فهو المهاجم i قد ترسل القمامة بدلا من ذلك pط (ي) للمشارك j، ومشارك j لن تكون قادرة على الحصول على المعنى الحقيقي بي (ي)، ولن تكون قادرة على حساب المكون الخاص به.

يوجد بروتوكول تشفير يسمح لك بإنشاء رسالة إضافية دليلi(j)، بحيث يكون لأي مشارك بعض القيمة e, إضافة إلى بروفي (ي) и pi(j)G، يمكنه التحقق من ذلك محليًا e - إنها حقا بي (ي)، مشفرة بمفتاح المشارك j. ولسوء الحظ، فإن حجم هذه الأدلة كبير بشكل لا يصدق، ونظرا لأنه من الضروري نشره يا (nk) ولا يمكن استخدام مثل هذه الأدلة لهذا الغرض.

بدلا من إثبات ذلك بي (ي) مباراة pi(j)G يمكننا تخصيص فترة زمنية طويلة جدًا في بروتوكول إنشاء كثير الحدود، حيث يتحقق جميع المشاركين من التشفير المستلم بي (ي)، وإذا كانت الرسالة التي تم فك تشفيرها لا تتوافق مع الجمهور pi(j)G، ينشرون دليلًا مشفرًا على أن الرسالة المشفرة التي تلقوها غير صحيحة. إثبات أن الرسالة لا مباراة خنزير) أسهل بكثير من إثبات أنه يطابق. تجدر الإشارة إلى أن هذا يتطلب من كل مشارك الظهور على الإنترنت مرة واحدة على الأقل خلال الوقت المخصص لإنشاء مثل هذا الدليل، ويعتمد على افتراض أنه إذا نشر مثل هذا الدليل، فسوف يصل إلى جميع المشاركين الآخرين في نفس الوقت المخصص.

إذا لم يظهر أحد المشاركين عبر الإنترنت خلال هذه الفترة الزمنية، وكان لديه مكون واحد غير صحيح على الأقل، فلن يتمكن هذا المشارك المعين من المشاركة في إنشاء أرقام أخرى. ومع ذلك، سيظل البروتوكول يعمل إذا كان هناك على الأقل k المشاركون الذين تلقوا للتو المكونات الصحيحة أو تمكنوا من ترك دليل على عدم الصحة خلال الوقت المخصص.

البراهين على صحة H_i

الجزء الأخير الذي لا يزال يتعين مناقشته هو كيفية إثبات صحة ما تم نشره Hأنا، وهي أن مرحبا = ص (ط) ح، بدون فتح باي).

ولنتذكر أن القيم ح، ز، ص (ط) ز عامة ومعروفة لدى الجميع. تلقي العملية باي) معرفة خنزير и G تسمى اللوغاريتم المنفصل أو سجل, ونريد أن نثبت أن:

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

دون الكشف باي). توجد إنشاءات لمثل هذه البراهين، على سبيل المثال بروتوكول شنور.

مع هذا التصميم، كل مشارك، جنبا إلى جنب مع Hi يرسل ما يثبت الصحة حسب التصميم.

بمجرد إنشاء رقم عشوائي، غالبًا ما يلزم استخدامه من قبل مشاركين غير أولئك الذين قاموا بإنشائه. يجب على هؤلاء المشاركين، إلى جانب الرقم، إرسال الكل Hi والأدلة ذات الصلة.

قد يتساءل القارئ الفضولي: بما أن الرقم العشوائي النهائي هو H0 و ع(0)ز – هذه معلومات عامة، لماذا نحتاج إلى إثبات لكل فرد Hأنا، لماذا لا ترسل دليلا على ذلك بدلا من ذلك

سجل (ع (0) ز، ز) = دلوج (H0, H)

المشكلة هي أنه لا يمكن إنشاء مثل هذا الدليل باستخدام بروتوكول شنور لأنه لا أحد يعرف قيمته ص (0)، ضروري لإنشاء الدليل، والأكثر من ذلك، أن مولد الأرقام العشوائية بالكامل يعتمد على حقيقة أنه لا أحد يعرف هذه القيمة. ولذلك فمن الضروري أن يكون كل القيم Hi وأدلتهم الفردية لإثبات صحتها H0.

ومع ذلك، إذا كانت هناك بعض العمليات على النقاط على المنحنيات الإهليلجية التي تشبه الضرب لغويًا، فإن دليل الصحة H0 سيكون تافها، ونحن ببساطة سوف نتأكد من ذلك

H0 × G = ص (0) ز × ح

إذا كان المنحنى المحدد يدعم أزواج منحنى بيضاوي، هذا الدليل يعمل. في هذه الحالة H0 ليس فقط ناتج مولد أرقام عشوائي، والذي يمكن التحقق منه من قبل أي مشارك يعرف جي ، ح и ص(0)ز. ح0 هو أيضًا توقيع على الرسالة التي تم استخدامها كبذرة، مما يؤكد ذلك k и n وقع المشاركون على هذه الرسالة. وهكذا إذا بذرة - هو تجزئة الكتلة في بروتوكول blockchain، إذن H0 هو عبارة عن توقيع متعدد على كتلة ورقم عشوائي جيد جدًا.

في الختام

هذه المقالة جزء من سلسلة مدونة تقنية قريب. NEAR هو بروتوكول ومنصة blockchain لتطوير التطبيقات اللامركزية مع التركيز على سهولة التطوير وسهولة الاستخدام للمستخدمين النهائيين.

رمز البروتوكول مفتوح، وتنفيذنا مكتوب بلغة Rust، ويمكن العثور عليه هنا.

يمكنك أن ترى كيف يبدو التطوير ضمن NEAR، ويمكنك تجربة IDE عبر الإنترنت هنا.

يمكنك متابعة جميع الأخبار باللغة الروسية في المجموعة في برقية و المجموعة على فكونتاكتي، وباللغة الإنجليزية في الرسمية تغريد.

اراك قريبا!

المصدر: www.habr.com