Agar biz bir-birimizga ishonmasak, tasodifiy raqamlarni yaratish mumkinmi? 1-qism

Hey Xabr!

Ushbu maqolada men bir-biriga ishonmaydigan ishtirokchilar tomonidan psevdo-tasodifiy raqamlarni yaratish haqida gapiraman. Quyida ko'rib turganimizdek, "deyarli" yaxshi generatorni amalga oshirish juda oddiy, ammo juda yaxshi generatorni amalga oshirish qiyin.

Зачем вообще нужно генерировать случайные числа участникам, не доверяющим друг другу? Одна из областей применения — это децентрализованные приложения. Например, приложение, которое принимает ставку от участника и либо удваивает сумму с вероятностью 49%, либо забирает с 51%, будет работать только если оно может непредвзято получить случайное число. Если злоумышленник может повлиять на результат работы генератора случайных чисел, и даже незначительно увеличить свой шанс получить выплату в приложении, он легко опустошит его.

Taqsimlangan tasodifiy sonlarni yaratish protokolini loyihalashda biz uning uchta xususiyatga ega bo'lishini xohlaymiz:

1. U xolis bo'lishi kerak. Boshqacha qilib aytganda, hech bir ishtirokchi tasodifiy sonlar generatorining natijasiga hech qanday tarzda ta'sir qilmasligi kerak.

2. Он должен быть непредсказуемым. Другими словами, ни один участник не должен иметь возможность предугадать, какое число будет сгенерировано (или вывести какие-либо его свойства) до того, как оно будет сгенерировано.

3. Protokol hayotiy bo'lishi kerak, ya'ni ishtirokchilarning ma'lum bir foizi tarmoqdan uzilishi yoki protokolni ataylab to'xtatishga urinishiga chidamli bo'lishi kerak.

Ushbu maqolada biz ikkita yondashuvni ko'rib chiqamiz: RANDAO + VDF va o'chirish kodlari yondashuvi. Keyingi qismda biz chegara imzolariga asoslangan yondashuvni batafsil ko'rib chiqamiz.

Но для начала давайте разберем простой и часто используемый алгоритм, который жизнеспособен, непредсказуем, но предвзят.

RANDAO

RANDAO juda oddiy va shuning uchun tasodifiylikni yaratish uchun juda tez-tez ishlatiladigan yondashuv. Tarmoqning barcha ishtirokchilari avval mahalliy ravishda psevdor tasodifiy raqamni tanlaydilar, keyin har bir ishtirokchi tanlangan raqamning xeshini yuboradi. Keyinchalik, ishtirokchilar navbatma-navbat tanlagan raqamlarini ochib, aniqlangan raqamlar ustida XOR operatsiyasini bajaradilar va bu operatsiya natijasi protokol natijasiga aylanadi.

Raqamlarni oshkor qilishdan oldin xeshlarni nashr qilish bosqichi kerak, shunda tajovuzkor boshqa ishtirokchilarning raqamlarini ko'rgandan keyin o'z raqamini tanlay olmaydi. Bu unga tasodifiy sonlar generatorining chiqishini deyarli bir qo'l bilan aniqlash imkonini beradi.

Protokol davomida ishtirokchilar ikki marta umumiy qarorga kelishlari kerak (konsensus deb ataladigan narsa): tanlangan raqamlarni qachon ochishni boshlash va shuning uchun xeshlarni qabul qilishni to'xtatish va tanlangan raqamlarni qabul qilishni va natijada tasodifiy hisoblashni qachon to'xtatish kerak. raqam. Bir-biriga ishonmaydigan ishtirokchilar o'rtasida bunday qarorlarni qabul qilish o'z-o'zidan oson ish emas va biz keyingi maqolalarda bunga qaytamiz; ushbu maqolada biz bunday konsensus algoritmi biz uchun mavjud deb taxmin qilamiz.

RANDAO biz yuqorida tavsiflangan xususiyatlardan qaysilariga ega? Bu oldindan aytib bo'lmaydigan, asosiy konsensus protokoli bilan bir xil hayotiylikka ega, ammo u noxolisdir. Xususan, tajovuzkor tarmoqni kuzatishi mumkin va boshqa ishtirokchilar ularning raqamlarini oshkor qilgandan so'ng, u XORni hisoblab chiqishi va natijaga ta'sir qilish uchun o'z raqamini oshkor qilish yoki ochmaslik haqida qaror qabul qilishi mumkin. Bu tajovuzkorga tasodifiy sonlar generatorining chiqishini yakka o'zi aniqlashiga to'sqinlik qilsa-da, u baribir unga 1 bit ta'sir ko'rsatadi. Va agar tajovuzkorlar bir nechta ishtirokchilarni nazorat qilsalar, ular nazorat qiladigan bitlar soni ularning nazorati ostidagi ishtirokchilar soniga teng bo'ladi.

Ishtirokchilardan raqamlarni tartibda ochishni talab qilish orqali hujumchilarning ta'sirini sezilarli darajada kamaytirish mumkin. Shunda tajovuzkor faqat oxirgi marta ochilgan taqdirdagina natijaga ta'sir qilishi mumkin bo'ladi. Ta'sir sezilarli darajada kamroq bo'lsa-da, algoritm hali ham noaniq.

RANDAO+VDF

RANDAO ni xolis qilishning bir usuli: barcha raqamlar aniqlangandan so'ng va XOR hisoblangandan so'ng, uning natijasi funktsiyaning kiritilishiga kiritiladi, bu hisoblash uchun juda uzoq vaqt talab etadi, lekin to'g'riligini tekshirishga imkon beradi. juda tez hisoblash.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Bu funksiya Verifable Delay Function yoki VDF deb ataladi. Agar yakuniy natijani hisoblash raqamni oshkor qilish bosqichidan ko'proq vaqt talab qilsa, tajovuzkor o'z raqamini ko'rsatish yoki yashirish samarasini oldindan aytib bera olmaydi va shuning uchun u natijaga ta'sir qilish imkoniyatini yo'qotadi.

Yaxshi VDF-larni ishlab chiqish juda qiyin. Yaqinda bir nechta yutuqlar bo'ldi, masalan. bu и этот, bu VDFni amalda amaliyroq qildi va Ethereum 2.0 RANDAO dan VDF bilan uzoq muddatda tasodifiy sonlar manbai sifatida foydalanishni rejalashtirmoqda. Ushbu yondashuv oldindan aytib bo'lmaydigan va xolis bo'lishidan tashqari, tarmoqda kamida ikkita ishtirokchi mavjud bo'lsa, hayotiy bo'lishning qo'shimcha afzalligi bor (agar bunday kam sonli ishtirokchilar bilan ishlashda foydalanilgan konsensus protokoli hayotiy bo'lsa).

Ushbu yondashuvning eng katta muammosi VDFni shunday o'rnatishdirki, hatto juda qimmat maxsus uskunaga ega bo'lgan ishtirokchi ham kashfiyot bosqichi tugaguniga qadar VDFni hisoblay olmaydi. Ideal holda, algoritm hatto muhim xavfsizlik chegarasiga ega bo'lishi kerak, masalan, 10x. Quyidagi rasmda RANDAO tasdig'ini ochish uchun ajratilgan vaqtdan ko'ra VDFni tezroq ishlatish imkonini beruvchi ixtisoslashgan ASIC-ga ega bo'lgan aktyorning hujumi ko'rsatilgan. Bunday ishtirokchi hali ham yakuniy natijani o'z raqamidan foydalanib yoki ishlatmasdan hisoblashi mumkin, keyin esa hisob-kitob asosida uni ko'rsatish yoki ko'rsatmaslikni tanlashi mumkin.

Yuqorida aytib o'tilgan VDF oilasi uchun maxsus ASIC ning ishlashi an'anaviy uskunadan 100+ baravar yuqori bo'lishi mumkin. Shunday qilib, agar oshkor qilish bosqichi 10 soniya davom etsa, bunday ASICda hisoblangan VDF 100x xavfsizlik chegarasiga ega bo'lishi uchun 10 soniyadan ko'proq vaqtni olishi kerak va shuning uchun tovar apparatida hisoblangan bir xil VDF 100x 100 soniya = ~3 soat davom etishi kerak.

Ethereum jamg'armasi ushbu muammoni o'zining ochiq, bepul ASIC-larini yaratish orqali hal qilishni rejalashtirmoqda. Bu sodir bo'lgandan so'ng, boshqa barcha protokollar ham ushbu texnologiyadan foydalanishi mumkin, ammo o'sha vaqtgacha RANDAO+VDF yondashuvi o'z ASIC-larini ishlab chiqishga sarmoya kirita olmaydigan protokollar uchun unchalik mos bo'lmaydi.

VDF haqida ko'plab maqolalar, videolar va boshqa ma'lumotlar to'plangan Ushbu sayt.

Biz o'chirish kodlaridan foydalanamiz

Ushbu bo'limda biz foydalanadigan tasodifiy sonlarni yaratish protokolini ko'rib chiqamiz kodlarni o'chirish. U ⅓ tajovuzkorlarga bardosh bera oladi, shu bilan birga hayotiy bo'lib qoladi va ⅔ gacha bo'lgan tajovuzkorlar natijani bashorat qilish yoki ta'sir qilishdan oldin mavjud bo'lishiga imkon beradi.

Protokolning asosiy g'oyasi quyidagicha. Oddiylik uchun, keling, roppa-rosa 100 ishtirokchi bor deb faraz qilaylik. Shuningdek, barcha ishtirokchilar mahalliy miqyosda qandaydir shaxsiy kalitga ega deb faraz qilaylik va barcha ishtirokchilarning ochiq kalitlari barcha ishtirokchilarga ma'lum:

1. Каждый участник локально придумывает длинную строку, разбивает ее на 67 частей, создает стирающие коды для получения 100 долей, таких, что любых 67 достаточно для восстановления строки, назначает каждую из 100 долей одному из участников и шифрует их с помощью открытого ключа того же участника. Затем все закодированные доли публикуются.

2. Участники используют некоторый консенсус, чтобы достичь согласия о закодированных наборах от конкретных 67 участников.

3. Konsensusga erishilgandan so'ng, har bir ishtirokchi o'zining ochiq kaliti bilan shifrlangan 67 to'plamning har birida kodlangan aktsiyalarni oladi, barcha bunday aktsiyalarning shifrini ochadi va shifrlangan barcha aktsiyalarni nashr etadi.

4. 67 ishtirokchi (3) bosqichni bajargandan so'ng, barcha kelishilgan to'plamlar o'chirish kodlarining xususiyatlari tufayli to'liq dekodlanishi va qayta tiklanishi mumkin va yakuniy raqam ishtirokchilar (1) da boshlagan dastlabki qatorlarning XOR sifatida olinishi mumkin. .

Ushbu protokolning xolis va oldindan aytib bo'lmaydiganligini ko'rsatish mumkin. Olingan tasodifiy raqam konsensusga erishilgandan so'ng aniqlanadi, lekin ishtirokchilarning ⅔ qismi ochiq kalit bilan shifrlangan qismlarni dekodlamaguncha hech kimga ma'lum emas. Shunday qilib, tasodifiy raqam uni qayta qurish uchun etarli bo'lgan ma'lumot nashr etilishidan oldin aniqlanadi.

Agar (1) bosqichda ishtirokchilardan biri boshqa ishtirokchilarga ba'zi bir qator uchun to'g'ri o'chirish kodi bo'lmagan kodlangan aktsiyalarni yuborsa nima bo'ladi? Qo'shimcha o'zgartirishlarsiz, turli ishtirokchilar yo satrni umuman tiklay olmaydilar yoki ular turli qatorlarni tiklaydilar, buning natijasida turli ishtirokchilar boshqa tasodifiy raqam oladilar. Buning oldini olish uchun siz quyidagilarni qilishingiz mumkin: har bir ishtirokchi, kodlangan aktsiyalarga qo'shimcha ravishda, shuningdek, hisoblab chiqadi. Merkla daraxti barcha bunday aktsiyalarni oladi va har bir ishtirokchiga kodlangan ulushning o'zini ham, merkle daraxtining ildizini ham yuboradi va ulushning merkle daraxtiga kiritilganligini tasdiqlaydi. (2) bosqichdagi konsensusda ishtirokchilar nafaqat to'plamlar to'plamiga, balki bunday daraxtlarning o'ziga xos ildizlari to'plamiga ham rozi bo'lishadi (agar ba'zi ishtirokchilar protokoldan chetga chiqsa va turli ishtirokchilarga turli xil daraxt ildizlarini yuborsa, va ikkita shunday ildiz konsensus paytida ko'rsatilgan, uning qatori natijalar to'plamiga kiritilmagan). Konsensus natijasida bizda 67 ta kodlangan satr va shunga mos keladigan merkle daraxtining ildizlari bo'ladi, shunda kamida 67 ta ishtirokchi bo'ladi (tegishli qatorlarni taklif qilganlar bir xil bo'lishi shart emas), ular 67 qatorning har biri uchun o'chirish kodining ulushi bo'lgan xabar va tegishli daraxtda ularning ulushi paydo bo'lganligining isboti.

Qachonki (4) bosqichda ishtirokchi ma'lum bir satr uchun 67 zarbani hal qiladi va ulardan asl qatorni qayta tiklashga harakat qilsa, variantlardan biri mumkin:

1. Satr tiklanadi va agar u yana o'chirish-kodlangan bo'lsa va Merkle daraxti mahalliy hisoblangan aktsiyalar uchun hisoblansa, ildiz konsensusga erishilganiga to'g'ri keladi.

2. Qator tiklandi, lekin mahalliy hisoblangan ildiz konsensusga erishilganiga mos kelmaydi.

3. Qator tiklanmaydi.

Ko'rsatish osonki, agar (1) variant yuqoridagi kamida bitta ishtirokchi uchun sodir bo'lgan bo'lsa, u holda (1) variant barcha ishtirokchilar uchun sodir bo'lgan va aksincha, agar (2) yoki (3) variant kamida bitta ishtirokchi uchun sodir bo'lgan bo'lsa, u holda barcha ishtirokchilar uchun (2) yoki (3) variant amalga oshadi. Shunday qilib, to'plamdagi har bir qator uchun yoki barcha ishtirokchilar uni muvaffaqiyatli tiklaydilar yoki barcha ishtirokchilar uni tiklay olmaydilar. Olingan tasodifiy son faqat ishtirokchilar tiklay olgan qatorlarning XOR ko'rsatkichidir.

Imzolar chegarasi

Другой подход к случайности заключается в использовании так называемых пороговых подписей BLS. Генератор случайных чисел, основанный на пороговых подписях, имеет точно такие же гарантии, как и описанный выше алгоритм на основе стирающих кодов, но имеет значительно меньшую асимптотику количества сообщений, пересылаемых по сети на каждое сгенерированное число.

BLS imzolari bir nechta ishtirokchilarga xabar uchun bitta umumiy imzo yaratish imkonini beruvchi dizayndir. Ushbu imzolar ko'pincha bo'sh joy va tarmoqli kengligini tejash uchun bir nechta imzolarni yuborishni talab qilmasdan ishlatiladi. 

Blockchain protokollarida BLS imzolari uchun keng tarqalgan dastur, tasodifiy raqamlarni yaratishdan tashqari, BFT protokollarida blokirovka qilishdir. Aytaylik, 100 ta ishtirokchi blok yaratadi va agar ulardan 67 nafari imzo cheksa, blok yakuniy hisoblanadi. Ularning barchasi BLS imzosining o'z qismlarini topshirishlari va 67 tasi bo'yicha kelishish uchun ba'zi konsensus algoritmidan foydalanishlari va keyin ularni bitta BLS imzosiga birlashtirishlari mumkin. Yakuniy imzoni yaratish uchun har qanday 67 (yoki undan ortiq) qismdan foydalanish mumkin, bu qaysi 67 ta imzo birlashtirilganiga bog'liq bo'ladi va shuning uchun farq qilishi mumkin, garchi 67 ishtirokchining turli xil tanlovlari boshqa imzoni yaratadi, ammo bunday imzo haqiqiy bo'ladi. blok uchun imzo. Keyin qolgan ishtirokchilar tarmoqdagi yukni sezilarli darajada kamaytiradigan tarmoq orqali 67 emas, balki har bir blok uchun faqat bitta imzoni olishlari va tekshirishlari kerak.

Ma'lum bo'lishicha, agar ishtirokchilar foydalanadigan shaxsiy kalitlar ma'lum bir tarzda yaratilgan bo'lsa, unda qaysi 67 ta imzo (yoki undan ko'p, lekin kam emas) jamlangan bo'lishidan qat'i nazar, natijada imzo bir xil bo'ladi. Bu tasodifiylik manbai sifatida ishlatilishi mumkin: ishtirokchilar birinchi navbatda imzo qo'yadigan ba'zi xabarga rozi bo'lishadi (bu RANDAO chiqishi yoki faqat oxirgi blokning xeshi bo'lishi mumkin, u har safar o'zgarib tursa, buning ahamiyati yo'q. va izchil) va buning uchun BLS imzosini yarating. 67 ishtirokchi o'z qismlarini taqdim qilmaguncha avlodning natijasi oldindan aytib bo'lmaydi va shundan keyin chiqish allaqachon oldindan belgilangan va hech qanday ishtirokchining harakatlariga bog'liq bo'lishi mumkin emas.

Tasodifiylikka bunday yondashuv, agar onlayn ishtirokchilarning kamida ⅔ qismi protokolga amal qilsa, yaroqli bo'ladi va ishtirokchilarning kamida ⅓ qismi protokolga rioya qilsa, xolis va oldindan aytib bo'lmaydi. Shuni ta'kidlash kerakki, ishtirokchilarning ⅓ dan ko'prog'ini, lekin ⅔ dan kamini boshqaradigan tajovuzkor protokolni to'xtatishi mumkin, lekin uning chiqishini bashorat qila olmaydi yoki ta'sir qila olmaydi.

Пороговые подписи сами по себе – очень интересная тема. Во второй части статьи мы детально разберем как они работают, и как именно необходимо генерировать ключи участников, чтобы пороговые подписи можно было использовать как генератор случайных чисел.

Xulosa

Ushbu maqola texnik blog maqolalari seriyasining birinchisidir NEAR. NEAR - bu blokcheyn protokoli va markazlashtirilmagan ilovalarni ishlab chiqish uchun platforma bo'lib, ishlab chiqish qulayligi va oxirgi foydalanuvchilar uchun foydalanish qulayligiga urg'u beradi.

Protokol kodi ochiq, bizning dasturimiz Rustda yozilgan, uni topish mumkin shu yerda.

Onlayn IDE-da NEAR uchun ishlanma qanday ko'rinishini ko'rishingiz va tajriba qilishingiz mumkin shu yerda.

Barcha yangiliklarni rus tilida kuzatib borishingiz mumkin telegram guruhi va VKontakte-dagi guruh, va ingliz tilida rasmiy twitter.

Do skoryx vstrech!

Manba: www.habr.com