Tasodifiy raqamlar va markazlashtirilmagan tarmoqlar: amaliy ilovalar

kirish

"Tasodifiy raqamlarni yaratish juda muhim, tasodifan qoldirilmaydi."
Robert Kavu, 1970 yil

Ushbu maqola ishonchsiz muhitda jamoaviy tasodifiy sonlarni yaratishdan foydalangan holda echimlarni amaliy qo'llashga bag'ishlangan. Muxtasar qilib aytganda, blokcheynlarda tasodifiy qanday va nima uchun ishlatiladi va "yaxshi" tasodifni "yomon" dan qanday ajratish haqida bir oz. Haqiqiy tasodifiy sonni yaratish hatto bitta kompyuterda ham juda qiyin masala bo'lib, kriptograflar tomonidan uzoq vaqtdan beri o'rganilgan. Xo'sh, markazlashtirilmagan tarmoqlarda tasodifiy raqamlarni yaratish yanada murakkab va muhimroqdir.

Ishtirokchilar bir-biriga ishonmaydigan tarmoqlarda shubhasiz tasodifiy raqamni yaratish qobiliyati bizga ko'plab muhim muammolarni samarali hal qilish va mavjud sxemalarni sezilarli darajada yaxshilash imkonini beradi. Bundan tashqari, qimor o'yinlari va lotereyalar bu erda birinchi raqamli maqsad emas, chunki bu birinchi navbatda tajribasiz o'quvchiga tuyulishi mumkin.

Tasodifiy raqamlarni yaratish

Kompyuterlar tasodifiy raqamlarni o'zlari ishlab chiqara olmaydi, buning uchun ular tashqi yordamga muhtoj. Kompyuter, masalan, sichqoncha harakati, ishlatiladigan xotira miqdori, protsessor pinlaridagi adashgan oqimlar va entropiya manbalari deb ataladigan boshqa ko'plab manbalardan tasodifiy qiymatlarni olishi mumkin. Ushbu qiymatlarning o'zlari mutlaqo tasodifiy emas, chunki ular ma'lum bir diapazonda yoki oldindan aytib bo'ladigan o'zgarishlar sxemasiga ega. Bunday raqamlarni ma'lum bir diapazonda haqiqiy tasodifiy songa aylantirish uchun ularga kriptotransformatsiyalar qo'llaniladi, bu entropiya manbasining notekis taqsimlangan qiymatlaridan bir xil taqsimlangan psevdo-tasodifiy qiymatlarni hosil qiladi. Olingan qiymatlar psevdor tasodifiy deb nomlanadi, chunki ular haqiqatan ham tasodifiy emas, balki deterministik ravishda entropiyadan kelib chiqadi. Har qanday yaxshi kriptografik algoritm, ma'lumotlarni shifrlashda, tasodifiy ketma-ketlikdan statistik jihatdan ajratilmaydigan bo'lishi kerak bo'lgan shifrlangan matnlarni ishlab chiqaradi, shuning uchun tasodifiylikni yaratish uchun siz entropiya manbasini olishingiz mumkin, bu hatto kichik diapazonlarda ham qiymatlarning faqat yaxshi takrorlanishi va oldindan aytib bo'lmaydiganligini ta'minlaydi. qolgan ish bitlarni tarqatish va aralashtirishdir. Natijada olingan qiymat shifrlash algoritmi tomonidan qabul qilinadi.

Qisqacha ta'lim dasturini yakunlash uchun shuni qo'shimcha qilamanki, hatto bitta qurilmada tasodifiy raqamlarni yaratish bizning ma'lumotlarimiz xavfsizligini ta'minlashning ustunlaridan biridir.Yaratilgan psevdotasodifiy raqamlar turli tarmoqlarda xavfsiz ulanishlarni o'rnatishda, yaratishda foydalaniladi. kriptografik kalitlar, yuklarni muvozanatlash, yaxlitlik monitoringi va boshqa ko'plab ilovalar uchun. Ko'pgina protokollarning xavfsizligi ishonchli, tashqi oldindan aytib bo'lmaydigan tasodifiy yaratish, uni saqlash va protokolning keyingi bosqichiga qadar oshkor qilmaslik qobiliyatiga bog'liq, aks holda xavfsizlik buziladi. Soxta tasodifiy qiymat generatoriga hujum o'ta xavfli bo'lib, tasodifiy ishlab chiqarishdan foydalanadigan barcha dasturlarga darhol tahdid soladi.

Agar siz kriptografiya bo'yicha asosiy kursni olgan bo'lsangiz, bularning barchasini bilishingiz kerak, shuning uchun markazlashtirilmagan tarmoqlar haqida davom etamiz.

Blokcheynlarda tasodifiy

Avvalo, men aqlli kontraktlarni qo'llab-quvvatlaydigan blokcheynlar haqida gapiraman; ular yuqori sifatli, inkor etilmaydigan tasodifiy imkoniyatlardan to'liq foydalana oladiganlardir. Bundan tashqari, qisqalik uchun men ushbu texnologiyani chaqiraman "Omma tomonidan tekshiriladigan tasodifiy mayoqlar” yoki PVRB. Blokcheynlar ma'lumotlar har qanday ishtirokchi tomonidan tekshirilishi mumkin bo'lgan tarmoqlar bo'lgani uchun, nomning asosiy qismi "Omma tomonidan tekshirilishi mumkin", ya'ni. Har kim blokcheynga joylashtirilgan natijada quyidagi xususiyatlarga ega ekanligini isbotlash uchun hisob-kitoblardan foydalanishi mumkin:

• Natija isbotlanadigan yagona taqsimotga ega bo'lishi kerak, ya'ni ishonchli kuchli kriptografiyaga asoslangan bo'lishi kerak.
• Natijaning biron bir qismini nazorat qilish mumkin emas. Natijada, natijani oldindan aytib bo'lmaydi.
• Protokolda qatnashmaslik yoki tarmoqni hujum xabarlari bilan ortiqcha yuklash orqali siz avlod protokolini sabotaj qila olmaysiz.
• Yuqoridagilarning barchasi halol bo'lmagan protokol ishtirokchilarining ruxsat etilgan sonining til biriktirishiga chidamli bo'lishi kerak (masalan, ishtirokchilarning 1/3 qismi).

Ishtirokchilarning kichik guruhining hatto boshqariladigan juft/toq tasodifni yaratish uchun til biriktirishining har qanday imkoniyati xavfsizlik teshigi hisoblanadi. Guruhning tasodifiy emissiyasini to'xtatish uchun har qanday qobiliyati xavfsizlik teshigi hisoblanadi. Umuman olganda, muammolar ko'p va bu vazifa oson emas...

Ko'rinishidan, PVRB uchun eng muhim dastur turli xil o'yinlar, lotereyalar va umuman blokcheyndagi har qanday qimor o'yinlaridir. Darhaqiqat, bu muhim yo'nalish, ammo blokcheynlardagi tasodifiylik yanada muhimroq ilovalarga ega. Keling, ularga qaraylik.

Konsensus algoritmlari

PVRB tarmoq konsensusini tashkil qilishda katta rol o'ynaydi. Blokcheynlardagi tranzaktsiyalar elektron imzo bilan himoyalangan, shuning uchun "tranzaksiyaga hujum" har doim blokdagi (yoki bir nechta bloklarda) tranzaktsiyaning kiritilishi / chiqarib tashlanishi hisoblanadi. Va konsensus algoritmining asosiy vazifasi - bu bitimlar tartibini va ushbu operatsiyalarni o'z ichiga olgan bloklarning tartibini kelishishdir. Shuningdek, haqiqiy blokcheynlar uchun zaruriy xususiyat yakuniylikdir - tarmoqning yakunlangan blokgacha bo'lgan zanjir yakuniy ekanligiga rozi bo'lish qobiliyati va yangi vilkalar paydo bo'lishi sababli hech qachon chiqarib tashlanmaydi. Odatda, blokning haqiqiy va eng muhimi, yakuniy ekanligiga rozi bo'lish uchun blok ishlab chiqaruvchilarning ko'pchiligidan (bundan buyon matnda BP - blok ishlab chiqaruvchilar deb yuritiladi) imzo to'plash kerak, bu hech bo'lmaganda blok zanjirini etkazib berishni talab qiladi. barcha BPlarga va imzolarni barcha BPlar o'rtasida taqsimlash. BP sonining o'sishi bilan tarmoqdagi zarur xabarlar soni eksponent ravishda o'sib boradi, shuning uchun yakuniylikni talab qiluvchi konsensus algoritmlari, masalan, Hyperledger pBFT konsensusida qo'llaniladigan, bir necha o'nlab BP dan boshlab kerakli tezlikda ishlamaydi. juda ko'p ulanishlar.

Agar tarmoqda inkor etib bo'lmaydigan va halol PVRB mavjud bo'lsa, unda, hatto eng oddiy taxminda ham, unga asoslangan blok ishlab chiqaruvchilardan birini tanlash va uni protokolning bir raundida "rahbar" etib tayinlash mumkin. Agar bizda bo'lsa N blok ishlab chiqaruvchilari, shulardan M: M > 1/2 N halol bo'ling, tranzaktsiyalarni tsenzura qilmang va "ikki marta sarflash" hujumini amalga oshirish uchun zanjirni buzmang, keyin bir xil taqsimlangan, shubhasiz PVRB dan foydalanish, ehtimollik bilan halol rahbarni tanlashga imkon beradi. M / N (M / N > 1/2). Agar har bir rahbarga blok ishlab chiqarishi va zanjirni tasdiqlashi mumkin bo'lgan o'z vaqt oralig'i tayinlangan bo'lsa va bu intervallar vaqt bo'yicha teng bo'lsa, halol BP blok zanjiri zararli BPlar tomonidan yaratilgan zanjirdan uzunroq bo'ladi va konsensus. algoritm zanjir uzunligiga tayanadi, shunchaki "yomon"ni tashlab yuboradi. Har bir BP uchun teng vaqt ajratish printsipi birinchi marta Grafenda (EOS ning salafi) qo'llanilgan va ko'pchilik bloklarni bitta imzo bilan yopish imkonini beradi, bu tarmoq yukini sezilarli darajada kamaytiradi va bu konsensusning juda tez ishlashiga imkon beradi va barqaror. Biroq, EOS tarmog'i endi 2/3 BP imzolari bilan tasdiqlangan maxsus bloklardan (Oxirgi qaytarilmas blok) foydalanishi kerak. Ushbu bloklar yakuniylikni ta'minlash uchun xizmat qiladi (oxirgi qaytarilmas blokdan oldin zanjirli vilkaning boshlanishi mumkin emas).

Bundan tashqari, real ilovalarda protokol sxemasi murakkabroq - taklif qilingan bloklar uchun ovoz berish yo'qolgan bloklar va tarmoq bilan bog'liq muammolar bo'lsa, tarmoqni saqlab qolish uchun bir necha bosqichda amalga oshiriladi, ammo buni hisobga olgan holda ham, PVRB-dan foydalangan holda konsensus algoritmlari talab qiladi. BPlar o'rtasida sezilarli darajada kamroq xabarlar, bu ularni an'anaviy PVFT yoki uning turli xil modifikatsiyalariga qaraganda tezroq qilish imkonini beradi.

Bunday algoritmlarning eng ko'zga ko'ringan vakili: Ouroboros Kardano jamoasidan, bu BP bilan til biriktirishga qarshi matematik jihatdan isbotlanishi mumkin.

Ouroborosda PVRB "BP jadvali" deb ataladigan jadvalni aniqlash uchun ishlatiladi - bu jadvalga muvofiq har bir BPga blokni nashr qilish uchun o'z vaqt oralig'i belgilanadi. PVRB dan foydalanishning katta afzalligi - BPlarning to'liq "tengligi" (ularning balanslari hajmiga ko'ra). PVRB ning yaxlitligi zararli BPlarning vaqt oralig'ini rejalashtirishni nazorat qila olmasligini va shuning uchun zanjirning vilkalarini oldindan tayyorlash va tahlil qilish orqali zanjirni boshqara olmasligini ta'minlaydi va vilkalarni tanlash uchun shunchaki vilka uzunligiga tayanish kifoya. zanjir, BP ning "foydaliligi" va uning bloklarining "og'irligi" ni hisoblashning qiyin usullaridan foydalanmasdan.

Umuman olganda, markazlashtirilmagan tarmoqda tasodifiy ishtirokchini tanlash kerak bo'lgan barcha holatlarda, masalan, blokli xeshga asoslangan deterministik variant emas, balki PVRB deyarli har doim eng yaxshi tanlovdir. PVRB bo'lmasa, ishtirokchining tanloviga ta'sir qilish qobiliyati hujumlarga olib keladi, bunda tajovuzkor qarorda ko'proq ulushni ta'minlash uchun keyingi buzuq ishtirokchini yoki bir vaqtning o'zida bir nechta fyucherslardan birini tanlashi mumkin. PVRB dan foydalanish ushbu turdagi hujumlarni obro'sizlantiradi.

Masshtablash va yukni muvozanatlash

PVRB, shuningdek, yukni kamaytirish va to'lovlarni o'lchash kabi vazifalarda katta foyda keltirishi mumkin. Boshlash uchun, o'zingiz bilan tanishish mantiqan maqola Rivesta "Elektron lotereya chiptalari mikroto'lovlar sifatida". Umumiy g'oya shundan iboratki, to'lovchidan oluvchiga 100 ta 1c to'lovni amalga oshirish o'rniga, siz 1$ = 100 c yutuq bilan halol lotereya o'ynashingiz mumkin, bunda to'lovchi bankka o'zining har biri uchun 1 ta "lotereya chiptasi" dan birini beradi. 100c to'lov. Ushbu chiptalardan biri 1 dollarlik bankni yutib oladi va bu chiptani oluvchi blokcheynda yozib olishi mumkin. Eng muhimi, qolgan 99 ta chipta oluvchi va to‘lovchi o‘rtasida hech qanday tashqi ishtirokisiz, shaxsiy kanal orqali va istalgan tezlikda uzatiladi. Emercoin tarmog'ida ushbu sxemaga asoslangan protokolning yaxshi tavsifi o'qilishi mumkin shu yerda.

Ushbu sxemada bir nechta muammolar mavjud, masalan, oluvchi yutuq chiptasini olgandan so'ng darhol to'lovchiga xizmat ko'rsatishni to'xtatishi mumkin, biroq ko'plab maxsus ilovalar uchun, masalan, daqiqada hisob-kitob qilish yoki xizmatlarga elektron obuna bo'lish uchun ularni e'tiborsiz qoldirish mumkin. Asosiy talab, albatta, lotereyaning adolatliligi va uni amalga oshirish uchun PVRB mutlaqo zarur.

Tasodifiy ishtirokchini tanlash sharding protokollari uchun ham juda muhimdir, ularning maqsadi blok zanjirini gorizontal ravishda o'lchashdir, bu turli BPlarga faqat tranzaktsiyalar doirasini qayta ishlashga imkon beradi. Bu juda qiyin vazifa, ayniqsa parchalarni birlashtirishda xavfsizlik nuqtai nazaridan. Konsensus algoritmlarida bo'lgani kabi, ma'lum bir parcha uchun mas'ul shaxslarni tayinlash uchun tasodifiy BPni adolatli tanlash ham PVRBning vazifasidir. Markazlashtirilgan tizimlarda shardlar balanslashtiruvchi tomonidan tayinlanadi, u shunchaki so'rovdan xeshni hisoblab chiqadi va uni kerakli ijrochiga yuboradi. Blokcheynlarda ushbu topshiriqga ta'sir qilish qobiliyati konsensusga hujumga olib kelishi mumkin. Masalan, tranzaktsiyalar mazmuni tajovuzkor tomonidan boshqarilishi mumkin, u qaysi tranzaktsiyalar o'zi boshqaradigan shardga borishini nazorat qilishi va undagi bloklar zanjirini boshqarishi mumkin. Siz Ethereum-da sharding vazifalari uchun tasodifiy raqamlardan foydalanish muammosi muhokamasini o'qishingiz mumkin shu yerda
Sharding blokcheyn sohasidagi eng ulug‘vor va jiddiy muammolardan biri bo‘lib, uning yechimi ajoyib unumdorlik va hajmdagi markazlashtirilmagan tarmoqlarni yaratish imkonini beradi. PVRB uni hal qilish uchun muhim bloklardan biridir.

O'yinlar, iqtisodiy protokollar, arbitraj

O'yin sanoatida tasodifiy raqamlarning rolini ortiqcha baholash qiyin. Onlayn kazinolarda aniq foydalanish va o'yinchi harakatining ta'sirini hisoblashda yashirin foydalanish markazlashtirilmagan tarmoqlar uchun juda qiyin muammolardir, bu erda tasodifiylikning markaziy manbasiga tayanishning hech qanday usuli yo'q. Ammo tasodifiy tanlash ko'plab iqtisodiy muammolarni ham hal qilishi va sodda va samaraliroq protokollarni yaratishga yordam beradi. Aytaylik, bizning protokolimizda ba'zi arzon xizmatlar uchun to'lov bo'yicha nizolar mavjud va bu nizolar juda kam uchraydi. Bunday holda, agar shubhasiz PVRB mavjud bo'lsa, mijozlar va sotuvchilar nizolarni tasodifiy hal qilishga rozi bo'lishlari mumkin, ammo berilgan ehtimollik bilan. Masalan, 60% ehtimol bilan mijoz yutadi, 40% ehtimol bilan sotuvchi yutadi. Birinchi nuqtai nazardan bema'ni bo'lgan bunday yondashuv, nizolarni avtomatik ravishda g'alabalar / yo'qotishlarning aniq prognoz qilinadigan ulushi bilan hal qilish imkonini beradi, bu uchinchi tomon ishtirokisiz va keraksiz vaqtni behuda sarflamasdan har ikki tomon uchun ham mos keladi. Bundan tashqari, ehtimollik nisbati dinamik bo'lishi va ba'zi global o'zgaruvchilarga bog'liq bo'lishi mumkin. Misol uchun, agar kompaniya yaxshi ishlayotgan bo'lsa, nizolar soni kam va yuqori rentabellikka ega bo'lsa, kompaniya nizoni hal qilish ehtimolini avtomatik ravishda mijozga yo'naltirilganlikka o'zgartirishi mumkin, masalan, 70/30 yoki 80/20 va aksincha, agar nizolar ko'p pul talab qilsa va yolg'on yoki etarli bo'lmasa, ehtimollikni boshqa tomonga o'zgartirishingiz mumkin.

Ko'p sonli qiziqarli markazlashtirilmagan protokollar, masalan, tokenlar tomonidan tuzilgan registrlar, bashorat bozorlari, bog'lanish egri chiziqlari va boshqalar yaxshi xulq-atvor mukofotlanadigan va yomon xatti-harakatlar jazolanadigan iqtisodiy o'yinlardir. Ular ko'pincha bir-biriga zid bo'lgan xavfsizlik muammolarini o'z ichiga oladi. Milliardlab tokenlar ("katta ulush") bo'lgan "kitlar" hujumidan himoyalangan narsa kichik balansga ega bo'lgan minglab hisoblar ("sybil ulushi") hujumlariga va bitta hujumga qarshi ko'rilgan choralarga nisbatan zaifdir. Katta ulush bilan ishlashni foydasiz qilish uchun yaratilgan chiziqli to'lovlar odatda boshqa hujum tomonidan obro'sizlanadi. Iqtisodiy o'yin haqida gapirayotganimiz sababli, tegishli statistik og'irliklarni oldindan hisoblash mumkin va komissiyalarni tegishli taqsimot bilan tasodifiy bo'lganlar bilan almashtiring. Bunday ehtimollik komissiyalari, agar blokcheyn ishonchli tasodifiy manbaga ega bo'lsa va hech qanday murakkab hisob-kitoblarni talab qilmasa, kit va sibillarning hayotini qiyinlashtirsa, juda sodda tarzda amalga oshiriladi.
Shu bilan birga, shuni yodda tutish kerakki, bu tasodifiylikdagi bitta bitni boshqarish sizni aldashga, ehtimollarni ikki baravar kamaytirishga va oshirishga imkon beradi, shuning uchun halol PVRB bunday protokollarning eng muhim tarkibiy qismidir.

To'g'ri tasodifni qaerdan topish mumkin?

Nazariy jihatdan, markazlashtirilmagan tarmoqlarda adolatli tasodifiy tanlash deyarli har qanday protokolni til biriktirishdan ishonchli tarzda himoya qiladi. Buning mantiqiy asosi juda oddiy - agar tarmoq bitta 0 yoki 1 bitga rozi bo'lsa va ishtirokchilarning yarmidan kamrog'i insofsiz bo'lsa, unda etarli iteratsiyalar hisobga olingan holda, tarmoq belgilangan ehtimollik bilan ushbu bit bo'yicha konsensusga erishishi kafolatlanadi. Shunchaki, halol tasodifiy 51 ishtirokchidan 100 tasini 51% vaqtni tanlaydi. Ammo bu nazariy jihatdan, chunki ... haqiqiy tarmoqlarda maqolalardagi kabi xavfsizlik darajasini ta'minlash uchun xostlar o'rtasida ko'plab xabarlar, murakkab ko'p o'tishli kriptografiya talab qilinadi va protokolning har qanday murakkabligi darhol yangi hujum vektorlarini qo'shadi.
Shuning uchun biz blokcheynlarda hali isbotlangan chidamli PVRB ni ko'rmayapmiz, ular real ilovalar, ko'plab auditlar, yuklar va, albatta, haqiqiy hujumlar tomonidan sinovdan o'tish uchun etarli vaqt davomida ishlatilgan bo'lar edi, ularsiz uni chaqirish qiyin. mahsulot haqiqatan ham xavfsiz.

Biroq, bir nechta istiqbolli yondashuvlar mavjud, ular juda ko'p tafsilotlarda farqlanadi va ulardan biri muammoni albatta hal qiladi. Zamonaviy hisoblash resurslari yordamida kriptografik nazariyani amaliy dasturlarga juda mohirona tarjima qilish mumkin. Kelajakda biz PVRB ilovalari haqida gapirishdan xursand bo'lamiz: hozir ularning bir nechtasi bor, ularning har biri o'zining muhim xususiyatlari va amalga oshirish xususiyatlariga ega va har birining orqasida yaxshi g'oya bor. Randomizatsiyada qatnashadigan jamoalar ko'p emas va ularning har birining tajribasi boshqalar uchun juda muhimdir. Umid qilamizki, bizning ma'lumotlarimiz o'zidan oldingi jamoalarning tajribasini inobatga olgan holda boshqa jamoalarga tezroq harakat qilish imkonini beradi.

Manba: www.habr.com