NejauÅ”i skaitļi un decentralizēti tÄ«kli: praktiski pielietojumi

Ievads

"NejauÅ”o skaitļu Ä£enerÄ“Å”ana ir pārāk svarÄ«ga, lai to atstātu nejauŔības ziņā."
Roberts Kavue, 1970. gads

Å is raksts ir veltÄ«ts risinājumu praktiskai pielietoÅ”anai, izmantojot kolektÄ«vo nejauÅ”o skaitļu Ä£enerÄ“Å”anu neuzticamā vidē. ÄŖsāk sakot, kā un kāpēc nejauŔība tiek izmantota blokķēdēs, un nedaudz par to, kā atŔķirt ā€œlaboā€ nejauŔību no ā€œsliktāā€. Patiesi nejauÅ”a skaitļa Ä£enerÄ“Å”ana ir ārkārtÄ«gi sarežģīta problēma pat vienā datorā, un to jau sen ir pētÄ«juÅ”i kriptogrāfi. Nu, decentralizētos tÄ«klos nejauÅ”u skaitļu Ä£enerÄ“Å”ana ir vēl sarežģītāka un svarÄ«gāka.

TieÅ”i tÄ«klos, kuros dalÄ«bnieki neuzticas viens otram, spēja Ä£enerēt neapstrÄ«damu nejauÅ”u skaitli ļauj efektÄ«vi atrisināt daudzas kritiskas problēmas un bÅ«tiski uzlabot esoŔās shēmas. Turklāt azartspēles un loterijas Å”eit nav galvenais mērÄ·is, kā sākumā var Ŕķist nepieredzējuÅ”am lasÄ«tājam.

NejauÅ”o skaitļu Ä£enerÄ“Å”ana

Datori paÅ”i nevar Ä£enerēt nejauÅ”us skaitļus; lai to izdarÄ«tu, tiem nepiecieÅ”ama ārēja palÄ«dzÄ«ba. Dators var iegÅ«t kādu nejauÅ”u vērtÄ«bu, piemēram, no peles kustÄ«bām, izmantotās atmiņas apjoma, klaiņojoŔām strāvām uz procesora tapām un daudziem citiem avotiem, ko sauc par entropijas avotiem. Å Ä«s vērtÄ«bas paÅ”as nav pilnÄ«gi nejauÅ”as, jo tās atrodas noteiktā diapazonā vai tām ir paredzams izmaiņu modelis. Lai pārvērstu Ŕādus skaitļus patiesi nejauÅ”os skaitļos noteiktā diapazonā, tiem tiek piemērotas kriptotransformācijas, lai no entropijas avota nevienmērÄ«gi sadalÄ«tajām vērtÄ«bām iegÅ«tu vienmērÄ«gi sadalÄ«tas pseidogadÄ«juma vērtÄ«bas. IegÅ«tās vērtÄ«bas sauc par pseidogadÄ«juma, jo tās nav patiesi nejauÅ”as, bet ir deterministiski atvasinātas no entropijas. JebkurÅ” labs kriptogrāfijas algoritms, Å”ifrējot datus, rada Å”ifrētus tekstus, kuriem vajadzētu bÅ«t statistiski neatŔķiramiem no nejauÅ”as secÄ«bas, tāpēc nejauŔības iegÅ«Å”anai var izmantot entropijas avotu, kas nodroÅ”ina tikai labu vērtÄ«bu atkārtojamÄ«bu un neprognozējamÄ«bu pat nelielos diapazonos. pārējais darbs ir bitu izkliedÄ“Å”ana un sajaukÅ”ana IegÅ«to vērtÄ«bu pārņems Å”ifrÄ“Å”anas algoritms.

Lai pabeigtu Ä«su izglÄ«tojoÅ”u programmu, piebildÄ«Å”u, ka nejauÅ”u skaitļu Ä£enerÄ“Å”ana pat vienā ierÄ«cē ir viens no mÅ«su datu droŔības nodroÅ”ināŔanas pÄ«lāriem.Ä¢enerētie pseidogadÄ«juma skaitļi tiek izmantoti, veidojot droÅ”us savienojumus dažādos tÄ«klos, lai Ä£enerētu. kriptogrāfiskās atslēgas slodzes lÄ«dzsvaroÅ”anai, integritātes uzraudzÄ«bai un daudzām citām lietojumprogrammām. Daudzu protokolu droŔība ir atkarÄ«ga no spējas Ä£enerēt uzticamu, ārēji neparedzamu nejauŔību, saglabāt to un neatklāt lÄ«dz nākamajam protokola solim, pretējā gadÄ«jumā tiks apdraudēta droŔība. Uzbrukums pseidogadÄ«juma vērtÄ«bu Ä£eneratoram ir ārkārtÄ«gi bÄ«stams un nekavējoties apdraud visu programmatÅ«ru, kas izmanto nejauŔības Ä£enerÄ“Å”anu.

Jums tas viss būtu jāzina, ja esat apguvis kriptogrāfijas pamatkursu, tāpēc turpināsim par decentralizētiem tīkliem.

NejauÅ”i blokķēdēs

Vispirms es runāŔu par blokķēdēm ar viedo lÄ«gumu atbalstu, tie ir tie, kas var pilnÄ«bā izmantot iespējas, ko sniedz kvalitatÄ«va, nenoliedzama nejauŔība. Turklāt Ä«suma labad es Å”o tehnoloÄ£iju saukÅ”u "Publiski pārbaudāmas nejauÅ”as bākasā€ vai PVRB. Tā kā blokķēdes ir tÄ«kli, kuros informāciju var pārbaudÄ«t jebkurÅ” dalÄ«bnieks, galvenā nosaukuma daļa ir ā€œPubliski verificējamaā€, t.i. Ikviens var izmantot aprēķinus, lai iegÅ«tu pierādÄ«jumu, ka iegÅ«tajam skaitlim, kas ievietots blokķēdē, ir Ŕādas Ä«paŔības:

  • Rezultātam ir jābÅ«t pierādāmi vienmērÄ«gam sadalÄ«jumam, t.i., tam jābÅ«t balstÄ«tam uz pierādāmi spēcÄ«gu kriptogrāfiju.
  • Nav iespējams kontrolēt nevienu rezultāta bitu. Tā rezultātā iznākumu nevar paredzēt iepriekÅ”.
  • JÅ«s nevarat sabotēt Ä£enerÄ“Å”anas protokolu, nepiedaloties protokolā vai pārslogojot tÄ«klu ar uzbrukuma ziņojumiem
  • Visam iepriekÅ”minētajam jābÅ«t izturÄ«gam pret pieļaujamā skaita negodprātÄ«gu protokola dalÄ«bnieku (piemēram, 1/3 dalÄ«bnieku) saskaņoÅ”anu.

Jebkāda iespēja slepenai nelielai dalÄ«bnieku grupai izveidot pat kontrolētu pāra/nepāra nejauŔību ir droŔības robs. Jebkura grupas spēja apturēt nejauŔības izdoÅ”anu ir droŔības robs. Kopumā problēmu ir daudz, un Å”is uzdevums nav viegls...

Å Ä·iet, ka vissvarÄ«gākais PVRB lietojums ir dažādas spēles, loterijas un vispār jebkura veida azartspēles blokķēdē. PatieŔām, tas ir svarÄ«gs virziens, taču nejauŔībai blokķēdēs ir vēl svarÄ«gāki pielietojumi. ApskatÄ«sim tos.

Vienprātības algoritmi

PVRB spēlē milzÄ«gu lomu tÄ«kla vienprātÄ«bas organizÄ“Å”anā. DarÄ«jumus blokķēdēs aizsargā elektroniskais paraksts, tāpēc ā€œuzbrukums darÄ«jumamā€ vienmēr ir darÄ«juma iekļauÅ”ana/izslēgÅ”ana blokā (vai vairākos blokos). Un konsensa algoritma galvenais uzdevums ir vienoties par Å”o darÄ«jumu secÄ«bu un to bloku secÄ«bu, kas ietver Å”os darÄ«jumus. Tāpat Ä«stu blokķēžu nepiecieÅ”amais Ä«paÅ”ums ir galÄ«gums ā€“ tÄ«kla spēja vienoties, ka ķēde lÄ«dz pabeigtajam blokam ir galÄ«ga un nekad netiks izslēgta jaunas dakÅ”as parādÄ«Å”anās dēļ. Parasti, lai vienotos, ka bloks ir derÄ«gs un, galvenais, galÄ«gs, ir jāsavāc paraksti no lielākās daļas bloku ražotāju (turpmāk tekstā BP - bloku ražotāji), kas prasa vismaz bloku ķēdes piegādi. visiem BP un ā€‹ā€‹parakstu sadali starp visiem BP . Pieaugot BP skaitam, nepiecieÅ”amo ziņojumu skaits tÄ«klā pieaug eksponenciāli, lÄ«dz ar to konsensa algoritmi, kuriem nepiecieÅ”ama galÄ«gums, kas izmantoti, piemēram, Hyperledger pBFT konsensā, nedarbojas vajadzÄ«gajā ātrumā, sākot no vairākiem desmitiem BP, kas prasa liels savienojumu skaits.

Ja tÄ«klā ir nenoliedzams un godÄ«gs PVRB, tad, pat visvienkārŔākajā tuvinājumā, pēc tā var izvēlēties kādu no bloku ražotājiem un vienas protokola kārtas laikā iecelt viņu par ā€œlÄ«deriā€. Ja mums ir N bloku ražotāji, no kuriem M: M > 1/2 N ir godÄ«gi, necenzē darÄ«jumus un neliek ķēdi veikt ā€œdubulto tēriņuā€ uzbrukumu, tad vienmērÄ«gi sadalÄ«ta neapstrÄ«dēta PVRB izmantoÅ”ana ļaus ar varbÅ«tÄ«bu izvēlēties godÄ«gu vadÄ«tāju M / N (M / N > 1/2). Ja katram vadÄ«tājam tiek pieŔķirts savs laika intervāls, kurā viņŔ var izveidot bloku un apstiprināt ķēdi, un Å”ie intervāli ir vienādi laikā, tad godÄ«go BP bloku ķēde bÅ«s garāka nekā ķēde, ko veido ļaunprātÄ«gi BP, un vienprātÄ«ba algoritms balstās uz ķēdes garumu. ā€œsliktoā€ vienkārÅ”i atmetÄ«s. Å is princips, saskaņā ar kuru katram BP tiek pieŔķirtas vienādas laika daļas, pirmo reizi tika izmantots programmā Graphene (EOS priekÅ”tecis), un tas ļauj aizvērt lielāko daļu bloku ar vienu parakstu, kas ievērojami samazina tÄ«kla slodzi un ļauj Å”ai vienprātÄ«bai darboties ārkārtÄ«gi ātri un stabili. Taču EOS tÄ«klā tagad ir jāizmanto Ä«paÅ”i bloki (Last Irreversible Block), ko apliecina 2/3 BP paraksti. Å ie bloki kalpo galÄ«guma nodroÅ”ināŔanai (ķēdes dakÅ”as neiespējamÄ«ba, kas sākas pirms pēdējā pēdējā neatgriezeniskā bloka).

Tāpat reālajās implementācijās protokola shēma ir sarežģītāka - balsoÅ”ana par piedāvātajiem blokiem tiek veikta vairākos posmos, lai uzturētu tÄ«klu, ja trÅ«kst bloku un problēmas ar tÄ«klu, taču, pat ņemot vērā to, konsensa algoritmi, izmantojot PVRB, prasa ievērojami mazāk ziņojumu starp BP, kas ļauj tos padarÄ«t ātrākus par tradicionālo PVFT vai tā dažādajām modifikācijām.

Visizcilākie Ŕādu algoritmu pārstāvji: Ouroboros no Cardano komandas, kas esot matemātiski pierādāma pret BP vienoŔanos.

Vietnē Ouroboros PVRB tiek izmantots, lai definētu tā saukto ā€œBP grafikuā€ - grafiku, saskaņā ar kuru katram BP tiek pieŔķirts savs laika posms bloka publicÄ“Å”anai. PVRB izmantoÅ”anas lielā priekÅ”rocÄ«ba ir pilnÄ«ga BP ā€œvienlÄ«dzÄ«baā€ (atbilstoÅ”i to bilanču izmēram). PVRB integritāte nodroÅ”ina to, ka ļaunprātÄ«gie BP nevar kontrolēt laika niÅ”u plānoÅ”anu un tāpēc nevar manipulēt ar ķēdi, iepriekÅ” sagatavojot un analizējot ķēdes dakÅ”as, un, lai izvēlētos dakÅ”iņu, pietiek ar to, ka vienkārÅ”i paļaujas uz laika posmu garumu. ķēdē, neizmantojot sarežģītus veidus, kā aprēķināt BP ā€œlietderÄ«buā€ un tā bloku ā€œsvaruā€.

Kopumā visos gadÄ«jumos, kad decentralizētā tÄ«klā jāizvēlas nejauÅ”s dalÄ«bnieks, PVRB gandrÄ«z vienmēr ir labākā izvēle, nevis deterministiska opcija, kuras pamatā ir, piemēram, bloka hash. Bez PVRB iespēja ietekmēt dalÄ«bnieka izvēli noved pie uzbrukumiem, kuros uzbrucējs var izvēlēties no vairākiem nākotnes lÄ«gumiem, lai izvēlētos nākamo korumpēto dalÄ«bnieku vai vairākus uzreiz, lai nodroÅ”inātu lielāku daļu lēmuma pieņemÅ”anā. PVRB izmantoÅ”ana diskreditē Ŕāda veida uzbrukumus.

MērogoÅ”ana un slodzes lÄ«dzsvaroÅ”ana

PVRB var bÅ«t arÄ« liels ieguvums tādos uzdevumos kā slodzes samazināŔana un maksājumu mērogoÅ”ana. Sākumā ir jēga iepazÄ«ties ar rakstus Rivesta ā€œElektroniskās loterijas biļetes kā mikromaksājumiā€. Vispārējā ideja ir tāda, ka tā vietā, lai veiktu 100 1c maksājumus no maksātāja saņēmējam, jÅ«s varat spēlēt godÄ«gu loteriju ar laimestu 1 $ = 100 c, kur maksātājs bankai pieŔķir vienu no 1 savām ā€œloterijas biļetēmā€ par katru. 100c maksājums. Viena no Ŕīm biļetēm laimē burciņu 1 USD vērtÄ«bā, un tieÅ”i Å”o biļeti saņēmējs var ierakstÄ«t blokķēdē. VissvarÄ«gākais ir tas, ka atlikuŔās 99 biļetes tiek pārsÅ«tÄ«tas starp saņēmēju un maksātāju bez jebkādas ārējas lÄ«dzdalÄ«bas, pa privāto kanālu un jebkurā vēlamajā ātrumā. Labu protokola aprakstu, kas balstÄ«ts uz Å”o shēmu Emercoin tÄ«klā, var izlasÄ«t Å”eit.

Å ai shēmai ir dažas problēmas, piemēram, saņēmējs var pārtraukt apkalpot maksātāju uzreiz pēc laimētās biļetes saņemÅ”anas, taču daudzām Ä«paŔām lietojumprogrammām, piemēram, minÅ«tes norēķiniem vai pakalpojumu elektroniskai abonÄ“Å”anai, tās var atstāt novārtā. Galvenā prasÄ«ba, protams, ir loterijas godÄ«gums, un tās Ä«stenoÅ”anai ir absolÅ«ti nepiecieÅ”ams PVRB.

NejauÅ”a dalÄ«bnieka izvēle ir ārkārtÄ«gi svarÄ«ga arÄ« sadalÄ«Å”anas protokoliem, kuru mērÄ·is ir horizontāli mērogot bloku ķēdi, ļaujot dažādiem BP apstrādāt tikai to darÄ«jumu apjomu. Tas ir ārkārtÄ«gi sarežģīts uzdevums, jo Ä«paÅ”i droŔības ziņā, apvienojot skaidas. GodÄ«ga nejauÅ”a BP atlase, lai noteiktu atbildÄ«gos par konkrētu Ŕķembu, kā tas ir konsensa algoritmos, arÄ« ir PVRB uzdevums. Centralizētās sistēmās shards pieŔķir balansētājs; tas vienkārÅ”i aprēķina jaucējkodu no pieprasÄ«juma un nosÅ«ta to vajadzÄ«gajam izpildÄ«tājam. Blokķēdēs spēja ietekmēt Å”o uzdevumu var izraisÄ«t uzbrukumu vienprātÄ«bai. Piemēram, transakciju saturu var kontrolēt uzbrucējs, viņŔ var kontrolēt, kuri darÄ«jumi nonāk viņa kontrolētajā shardā un manipulēt ar tajā esoÅ”o bloku ķēdi. Varat izlasÄ«t diskusiju par problēmu, kas saistÄ«ta ar nejauÅ”u skaitļu izmantoÅ”anu, lai sadalÄ«tu uzdevumus Ethereum Å”eit
Sharding ir viena no vērienīgākajām un nopietnākajām problēmām blokķēdes jomā, tās risinājums ļaus veidot decentralizētus tīklus ar fantastisku veiktspēju un apjomu. PVRB ir tikai viens no svarīgākajiem blokiem, lai to atrisinātu.

Spēles, ekonomiskie protokoli, arbitrāža

NejauÅ”o skaitļu lomu spēļu industrijā ir grÅ«ti pārvērtēt. TieÅ”a izmantoÅ”ana tieÅ”saistes kazino un netieÅ”a izmantoÅ”ana, aprēķinot spēlētāja darbÄ«bas sekas, ir ārkārtÄ«gi sarežģītas problēmas decentralizētiem tÄ«kliem, kur nav iespējams paļauties uz centrālo nejauŔības avotu. Taču nejauÅ”a atlase var arÄ« atrisināt daudzas ekonomiskas problēmas un palÄ«dzēt izveidot vienkārŔākus un efektÄ«vākus protokolus. Pieņemsim, ka mÅ«su protokolā ir strÄ«di par apmaksu par dažiem lētiem pakalpojumiem, un Å”ie strÄ«di notiek diezgan reti. Šādā gadÄ«jumā, ja ir neapstrÄ«dams PVRB, klienti un pārdevēji var vienoties par strÄ«du risināŔanu nejauÅ”i, bet ar noteiktu varbÅ«tÄ«bu. Piemēram, ar 60% varbÅ«tÄ«bu uzvar klients, bet ar 40% varbÅ«tÄ«bu uzvar pārdevējs. Šāda no pirmā viedokļa absurdā pieeja ļauj automātiski atrisināt strÄ«dus ar precÄ«zi prognozējamu uzvaru/zaudējumu daļu, kas der abām pusēm bez jebkādas treŔās puses lÄ«dzdalÄ«bas un liekas laika tērÄ“Å”anas. Turklāt varbÅ«tÄ«bas koeficients var bÅ«t dinamisks un atkarÄ«gs no dažiem globāliem mainÄ«gajiem. Piemēram, ja uzņēmumam klājas labi, ir maz strÄ«du un augsta rentabilitāte, uzņēmums var automātiski novirzÄ«t strÄ«da risināŔanas iespējamÄ«bu uz klientu orientāciju, piemēram, 70/30 vai 80/20 un otrādi, ja strÄ«di prasa daudz naudas un ir krāpnieciski vai neadekvāti, varat novirzÄ«t varbÅ«tÄ«bu citā virzienā.

Liels skaits interesantu decentralizētu protokolu, piemēram, žetonu kurēti reÄ£istri, prognožu tirgi, saistÄ«tu lÄ«knes un daudzi citi, ir ekonomiskas spēles, kurās par labu uzvedÄ«bu tiek atalgota un par sliktu uzvedÄ«bu tiek sodÄ«ts. Tie bieži satur droŔības problēmas, kuru aizsardzÄ«bas lÄ«dzekļi ir pretrunā viens ar otru. Tas, kas ir aizsargāts no ā€œvaļuā€ uzbrukuma ar miljardiem žetonu (ā€œlielā likmeā€), ir neaizsargāts pret uzbrukumiem tÅ«kstoÅ”iem kontu ar nelielu atlikumu (ā€œsybil stakeā€) un pasākumiem, kas veikti pret vienu uzbrukumu, piemēram, pret Lineārās maksas, kas izveidotas, lai padarÄ«tu darbu ar lielu akciju nerentablu, parasti tiek diskreditētas ar citu uzbrukumu. Tā kā mēs runājam par ekonomisku spēli, atbilstoÅ”os statistiskos svarus var aprēķināt iepriekÅ” un vienkārÅ”i aizstāt komisijas ar randomizētām ar atbilstoÅ”u sadalÄ«jumu. Šādas varbÅ«tÄ«bas komisijas tiek ieviestas ārkārtÄ«gi vienkārÅ”i, ja blokķēdei ir uzticams nejauŔības avots un nav nepiecieÅ”ami sarežģīti aprēķini, apgrÅ«tinot dzÄ«vi gan vaļiem, gan sibiliem.
Tajā paŔā laikā ir jāturpina atcerēties, ka kontrole pār vienu bitu Å”ajā nejauŔībā ļauj krāpties, samazinot un palielinot varbÅ«tÄ«bas uz pusi, tāpēc godÄ«gs PVRB ir vissvarÄ«gākā Ŕādu protokolu sastāvdaļa.

Kur atrast pareizo nejauŔību?

Teorētiski godÄ«ga nejauÅ”a atlase decentralizētos tÄ«klos padara gandrÄ«z jebkuru protokolu droÅ”u pret slepenu vienoÅ”anos. Iemesls ir pavisam vienkārÅ”s ā€“ ja tÄ«kls vienojas par vienu 0 vai 1 bitu un mazāk nekā puse dalÄ«bnieku ir negodÄ«gi, tad, veicot pietiekamas iterācijas, tÄ«kls garantēti panāks vienprātÄ«bu par Å”o bitu ar fiksētu varbÅ«tÄ«bu. VienkārÅ”i tāpēc, ka godÄ«gs nejauÅ”s 51% gadÄ«jumu izvēlēsies 100 no 51 dalÄ«bniekiem. Bet tas ir teorētiski, jo... reālos tÄ«klos, lai nodroÅ”inātu tādu droŔības lÄ«meni kā rakstos, ir nepiecieÅ”ami daudzi ziņojumi starp saimniekiem, sarežģīta daudzpakāpju kriptogrāfija, un jebkura protokola komplikācija nekavējoties pievieno jaunus uzbrukuma vektorus.
Tāpēc mēs blokķēdēs vēl neredzam pārbaudÄ«tu izturÄ«gu PVRB, kas bÅ«tu izmantots pietiekami ilgu laiku, lai to pārbaudÄ«tu ar reālām lietojumprogrammām, vairākiem auditiem, ielādēm un, protams, reāliem uzbrukumiem, bez kuriem ir grÅ«ti izsaukt produkts patieŔām droÅ”s.

Tomēr ir vairākas daudzsoloÅ”as pieejas, tās atŔķiras daudzās detaļās, un viena no tām noteikti atrisinās problēmu. Izmantojot mÅ«sdienu skaitļoÅ”anas resursus, kriptogrāfijas teoriju var diezgan gudri pārvērst praktiskos lietojumos. Nākotnē ar prieku parunāsim par PVRB ievieÅ”anām: tagad tās ir vairākas, katrai ir savs svarÄ«gu Ä«paŔību un ievieÅ”anas pazÄ«mju kopums, un aiz katra slēpjas kāda laba ideja. Randomizācijā nav iesaistÄ«tas daudzas komandas, un katras no tām pieredze ir ārkārtÄ«gi svarÄ«ga visiem pārējiem. Ceram, ka mÅ«su informācija ļaus citām komandām kustēties ātrāk, ņemot vērā viņu priekÅ”gājēju pieredzi.

Avots: www.habr.com

Pievieno komentāru