Posible al da ausazko zenbakiak sortzea elkarrengan konfiantzarik ez badugu? 1. zatia

Aupa Habr!

Artikulu honetan elkarrengan fidatzen ez diren parte-hartzaileek sasi-ausazko zenbakien sorrerari buruz hitz egingo dut. Jarraian ikusiko dugunez, sorgailu “ia” ona ezartzea nahiko erraza da, baina oso ona zaila da.

Zergatik beharko litzateke elkarrengan konfiantzarik ez duten parte-hartzaileen artean ausazko zenbakiak sortzea? Aplikazio-eremu bat aplikazio deszentralizatuak dira. Esaterako, parte-hartzaile baten apustua onartzen duen eta zenbatekoa %49ko probabilitatearekin bikoiztu edo %51ko probabilitatearekin kentzen duen aplikazio batek ausazko zenbaki bat alborabiderik gabe jaso badu bakarrik funtzionatuko du. Erasotzaile batek ausazko zenbaki-sorgailuaren emaitzan eragina badu, eta aplikazioan ordainketa bat jasotzeko aukera apur bat areagotzen badu ere, erraz suntsituko du.

Banatutako ausazko zenbakiak sortzeko protokolo bat diseinatzen dugunean, hiru propietate izatea nahi dugu:

1. Aldegabea izan behar du. Beste era batera esanda, parte hartzaileek ez luke inola ere eragin behar ausazko zenbaki-sorgailuaren emaitzan.

2. Ezustekoa izan behar du. Beste era batera esanda, parte-hartzaile batek ezin du aurreikusi zer zenbaki sortuko den (edo bere propietateren bat ondorioztatu) sortu aurretik.

3. Protokoloak bideragarria izan behar du, hau da, parte-hartzaileen ehuneko jakin bat saretik deskonektatu edo nahita protokoloa geldiarazten saiatzeari erresistentea izan behar du.

Artikulu honetan bi ikuspegi aztertuko ditugu: RANDAO + VDF eta ezabatze-kodeen ikuspegia. Hurrengo zatian, zehatz-mehatz aztertuko dugu atalaseen sinaduretan oinarritutako planteamendua.

Baina lehenik eta behin, ikus dezagun bideragarria, ezustekoa, baina alboratzailea den algoritmo sinple eta erabilia.

RANDAO

RANDAO oso sinplea da eta, beraz, nahiko erabilia da ausazkotasuna sortzeko. Sareko parte-hartzaile guztiek lokalean sasi-ausazko zenbaki bat hautatzen dute, ondoren, parte-hartzaile bakoitzak hautatutako zenbakiaren hash bat bidaltzen du. Jarraian, parte-hartzaileek txandaka aukeratutako zenbakiak agerian uzten dituzte eta agerian dauden zenbakien XOR eragiketa bat egiten dute, eta eragiketa horren emaitza protokoloaren emaitza bihurtzen da.

Zenbakiak agertu aurretik hashak argitaratzeko urratsa beharrezkoa da, erasotzaileak bere zenbakia aukeratu ezin dezan beste parte-hartzaileen zenbakiak ikusi ondoren. Horrek aukera emango lioke ia bakarka zehaztea ausazko zenbaki-sorgailuaren irteera.

Protokoloan zehar, parte-hartzaileek erabaki komun bat hartu behar dute (adostasuna deitzen dena) bi aldiz: noiz hasi hautatutako zenbakiak agerian uzten eta, beraz, hash-ak onartzeari utzi, eta noiz utzi hautatutako zenbakiak onartzeari eta ondoriozko aleatorioa kalkulatzeari. zenbakia. Elkarrengan konfiantzarik ez duten parte-hartzaileen artean halako erabakiak hartzea ez da berez lan erraza, eta hurrengo artikuluetan horretara itzuliko gara; artikulu honetan adostasun algoritmo hori eskura dugula suposatuko dugu.

Goian deskribatu ditugun propietateetatik zein ditu RANDAOk? Ezustekoa da, azpian dagoen adostasun protokoloaren bizitasun bera du, baina alboragarria da. Zehazki, erasotzaile batek sarea behatu dezake, eta beste parte-hartzaileek beren zenbakiak agerian utzi ondoren, XOR kalkula dezake, eta bere zenbakia agerian utzi edo ez erabaki dezake emaitzan eragiteko. Horrek erasotzaileari ausazko zenbaki-sorgailuaren irteera bakarka zehaztea eragozten badu ere, eragin bit 1 ematen dio oraindik. Eta erasotzaileek hainbat parte-hartzaile kontrolatzen badituzte, orduan kontrolatzen duten bit kopurua haien kontrolpean dauden parte-hartzaileen berdina izango da.

Erasotzaileen eragina asko murriztu daiteke parte-hartzaileek zenbakiak ordenan ager ditzatela eskatuz. Orduan, erasotzaileak emaitzan eragin ahal izango du azken irekitzen bada. Eragina nabarmen txikiagoa den arren, algoritmoa alboratuta dago oraindik.

RANDAO+VDF

RANDAO alboragabea izateko modu bat hau da: zenbaki guztiak agerian utzi eta XOR kalkulatu ondoren, bere emaitza funtzio baten sarreran sartzen da, eta horrek oso denbora luzea behar du kalkulatzeko, baina zuzentasuna egiaztatzeko aukera ematen du. kalkulua oso azkar.

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

Funtzio honi Verifiable Delay Function edo VDF deitzen zaio. Azken emaitza kalkulatzeak zenbakiak zabaltzeko fasea baino denbora gehiago hartzen badu, erasotzaileak ezin izango du aurreikusi bere zenbakia erakusteak edo ezkutatzeak izango duen eragina, eta, beraz, emaitzan eragiteko aukera galduko du.

VDF onak garatzea oso zaila da. Azkenaldian hainbat aurrerapen izan dira, adibidez. hau и hau, horrek VDF praktikoagoa bihurtu zuen praktikan, eta Ethereum 2.0-k RANDAO VDFrekin ausazko zenbaki iturri gisa erabiltzeko asmoa du epe luzera. Ikuspegi hau ezustekoa eta alboragabea izateaz gain, sarean gutxienez bi parte-hartzaile eskuragarri egonez gero bideragarria izatearen onura gehigarria du (erabiltzen den adostasun-protokoloa bideragarria dela suposatuz, hain parte-hartzaile kopuru txikiarekin tratatzerakoan).

Planteamendu honen erronkarik handiena VDF ezartzea da, hardware espezializatu oso garestia duen parte-hartzaile batek ere ezingo baitu VDF kalkulatu aurkikuntza fasea amaitu aurretik. Egokiena, algoritmoak segurtasun-marjina esanguratsua izan beharko luke, esate baterako, 10x. Beheko irudian ASIC espezializatua duen aktore baten eraso bat erakusten da, VDF bat exekutatzeko esleitutako denbora baino azkarrago RANDAOren baieztapena erakusteko. Halako partaide batek oraindik kalkula dezake azken emaitza bere zenbakia erabiliz edo ez erabiliz, eta gero, kalkuluaren arabera, erakutsi edo ez aukeratu.

Arestian aipatutako VDF familiarako, ASIC dedikatu baten errendimendua ohiko hardwarea baino 100 aldiz handiagoa izan daiteke. Beraz, hedapen faseak 10 segundo irauten baditu, ASIC batean kalkulatutako VDFak 100 segundo baino gehiago behar ditu 10x segurtasun-marjina izateko, eta, beraz, salgaien hardwarean kalkulatutako VDF berak 100x 100 segundo = ~ 3 ordu behar ditu.

Ethereum Fundazioak arazo hau konpontzeko asmoa du publikoki eskuragarri dauden ASIC doakoak sortuz. Behin hori gertatuz gero, beste protokolo guztiek ere aprobetxa dezakete teknologia hori, baina ordura arte RANDAO+VDF ikuspegia ez da hain bideragarria izango ASICak garatzeko inbertitu ezin duten protokoloetarako.

VDFri buruzko artikulu, bideo eta bestelako informazio asko bildu dira gune hau.

Ezabatzeko kodeak erabiltzen ditugu

Atal honetan, erabiltzen duen ausazko zenbakiak sortzeko protokoloa ikusiko dugu kodeak ezabatuz. Gehienez ⅓ erasotzaile jasan ditzake bideragarria izaten jarraitzen duen bitartean, eta ⅔ erasotzaile egotea ahalbidetzen du emaitza aurreikusteko edo eragin aurretik.

Protokoloaren ideia nagusia honakoa da. Sinpletasunerako, demagun zehazki 100 parte-hartzaile daudela. Demagun, gainera, parte-hartzaile guztiek lokalean gako pribaturen bat dutela, eta parte-hartzaile guztien gako publikoak parte-hartzaile guztiek ezagutzen dituztela:

1. Lokalean parte-hartzaile bakoitzak kate luze bat ateratzen du, 67 zatitan zatitzen du, ezabatze-kodeak sortzen ditu 100 akzio lortzeko, hala nola, 67 nahikoak dira katea berreskuratzeko, 100 akzioetako bakoitza parte-hartzaileetako bati esleitzen dio eta enkriptatzen ditu. parte-hartzaile beraren gako publikoa. Kodetutako akzio guztiak argitaratzen dira.

2. Parte-hartzaileek nolabaiteko adostasuna erabiltzen dute 67 parte-hartzaile espezifikoen multzo kodetuei buruz akordioa lortzeko.

3. Adostasuna lortu ondoren, parte-hartzaile bakoitzak bere gako publikoarekin zifratutako 67 multzoetako kodetutako akzioak hartzen ditu, akzio horiek guztiak deszifratzen ditu eta deszifratutako akzio guztiak argitaratzen ditu.

4. 67 parte-hartzailek (3) urratsa amaitu dutenean, adostutako multzo guztiak guztiz deskodetu eta berreraiki daitezke ezabatze-kodeen propietateei esker, eta azken zenbakia parte-hartzaileek (1) hasitako hasierako errenkadetako XOR gisa lor daiteke. .

Protokolo hau alboragabea eta ezustekoa dela froga daiteke. Lortutako ausazko kopurua adostasuna lortu ondoren zehazten da, baina inork ez du ezagutzen parte-hartzaileen ⅔ak gako publikoarekin zifratutako zatiak deskodetu arte. Horrela, ausazko kopurua zehazten da hura berreraikitzeko nahikoa informazio argitaratu aurretik.

Zer gertatzen da (1) urratsean parte-hartzaileetako batek kate batzuen ezabatze-kode egokia ez diren beste parte-hartzaileei kodetutako akzioak bidaltzen badie? Aldaketa gehigarririk gabe, parte-hartzaile ezberdinek ezin izango dute katea batere berreskuratu, edo kate desberdinak berreskuratuko dituzte, eta, ondorioz, parte-hartzaile ezberdinek ausazko zenbaki bat jasoko dute. Hori ekiditeko, honako hau egin dezakezu: parte-hartzaile bakoitzak, kodetutako partekatzeaz gain, kalkulatzen du Merkla zuhaitza akzio horiek guztiak, eta parte-hartzaile bakoitzari bidaltzen dizkio kodetutako akzioa bera eta merkle zuhaitzaren erroa, eta akzioa merkle zuhaitzean sartzearen froga. (2) urratseko adostasunean, parte-hartzaileak ez dira multzo multzo batean bakarrik adosten, zuhaitz horien sustrai espezifikoen multzoan baizik (parte-hartzaileren batek protokolotik desbideratu eta merkle zuhaitzen sustrai desberdinak bidaltzen badituzte parte-hartzaile ezberdinei, eta halako bi erro erakusten dira adostasunean, bere errenkada ez da emaitza multzoan sartzen). Adostasunaren ondorioz, 67 lerro kodifikatu eta merkle zuhaitzari dagozkion erroak izango ditugu, hala nola, gutxienez 67 parte-hartzaile egon daitezen (ez dira nahitaez dagozkion lerroak proposatu dituzten berberak), zeinak 67 lerroetako bakoitzean dituztenak. ezabatze-kodearen parte-hartzea duen mezu bat eta dagokion zuhaitzean partekatzearen froga bat lausotu da.

(4) urratsean parte-hartzaileak kate jakin baterako 67 kolpe deszifratzen dituenean eta horietatik jatorrizko katea berreraikitzen saiatzen denean, aukeretako bat posible da:

1. Katea leheneratzen da, eta gero berriro ezabatuz kodetzen bada eta Merkle zuhaitza kalkulatzen bada lokalean kalkulatutako akzioetarako, erroa bat dator adostasuna lortu zenarekin.

2. Errenkada leheneratzen da, baina lokalean kalkulatutako erroa ez dator bat adostasuna lortu zenarekin.

3. Errenkada ez da leheneratu.

Erraza da erakustea (1) aukera goiko parte-hartzaile bati gutxienez gertatu bazaio, orduan (1) aukera parte-hartzaile guztiei gertatu zaiela, eta alderantziz, (2) edo (3) aukera gutxienez parte-hartzaile bati gertatu bazaio, orduan parte-hartzaile guztientzat (2) edo (3) aukera gertatuko da. Horrela, multzoko errenkada bakoitzeko, parte-hartzaile guztiek ondo berreskuratuko dute, edo parte-hartzaile guztiek ez dute berreskuratuko. Ondorioz, ausazko zenbakia parte-hartzaileek berreskuratu ahal izan zituzten errenkaden XOR bat da.

Atalasearen sinadurak

Ausazkotasunaren beste ikuspegi bat BLS atalasearen sinadurak deitzen direnak erabiltzea da. Atalasearen sinaduretan oinarritutako ausazko zenbaki-sorgailu batek goian deskribatutako ezabaketa kodean oinarritutako algoritmoaren berme berdinak ditu, baina sarean bidaltzen diren mezu kopuru asintotiko nabarmen txikiagoa du sortutako zenbaki bakoitzeko.

BLS sinadurak hainbat parte-hartzaileri mezu baterako sinadura komun bat sortzeko aukera ematen duen diseinua da. Sinadura hauek espazioa eta banda-zabalera aurrezteko erabiltzen dira askotan sinadura anitz bidaltzea eskatzen ez dutelako. 

BLS sinadurak blockchain protokoloetan ohikoa den aplikazio bat, ausazko zenbakiak sortzeaz gain, BFT protokoloetan blokeatzea da. Demagun 100 parte-hartzailek blokeak sortzen dituztela, eta bloke bat behin betikotzat jotzen da haietako 67k sinatzen badute. Guztiek BLS sinaduraren zatiak bidal ditzakete eta adostasun-algoritmoren bat erabil dezakete horietako 67 adosteko eta gero BLS sinadura bakarrean batzeko. 67 (edo gehiago) edozein zati erabil daitezke azken sinadura sortzeko, zein 67 sinadura konbinatu zirenaren araberakoa izango da eta, beraz, alda daiteke, nahiz eta 67 parte-hartzaileen aukera ezberdinek sinadura ezberdina sortuko duten, sinadura hori baliozkoa izango da. blokearen sinadura. Gainerako parte-hartzaileek bloke bakoitzeko sinadura bakarra jaso eta egiaztatu behar dute, 67 beharrean, sarean, eta horrek sareko karga nabarmen murrizten du.

Ikusten denez, parte-hartzaileek erabiltzen dituzten gako pribatuak modu jakin batean sortzen badira, 67 sinadura (edo gehiago, baina ez gutxiago) batzen badira ere, ondoriozko sinadura berdina izango da. Hau ausazkotasun iturri gisa erabil daiteke: parte-hartzaileek sinatuko duten mezuren bat adosten dute lehenik (hau RANDAOren irteera izan daiteke edo azken blokearen hash besterik ez, ez du axola aldi bakoitzean aldatzen den bitartean. eta koherentea da) eta sortu BLS sinadura bat. Sorkuntzaren emaitza ezustekoa izango da 67 parte-hartzailek beren zatiak eman arte, eta horren ondoren irteera dagoeneko aurrez zehaztuta dago eta ezin da edozein parte-hartzaileren ekintzen araberakoa izan.

Ausazkotasunaren ikuspegi hau bideragarria da sareko parte-hartzaileen gutxienez ⅔ biek protokoloa jarraitzen duten bitartean, eta alboragabea eta ezustekoa da, betiere, parte-hartzaileen ⅔ gutxienez protokoloa jarraitzen duten bitartean. Garrantzitsua da kontuan izan parte-hartzaileen ⅓ baino gehiago baina ⅔ baino gutxiago kontrolatzen dituen erasotzaileak protokoloa geldi dezakeela, baina ezin duela bere irteeran aurreikusi edo eragin.

Atalasearen sinadurak berez oso gai interesgarria dira. Artikuluaren bigarren zatian, zehatz-mehatz aztertuko dugu nola funtzionatzen duten, eta nola zehatz-mehatz beharrezkoa den parte-hartzaileen gakoak sortzea, atalasearen sinadurak ausazko zenbaki-sorgailu gisa erabili ahal izateko.

Ondorioz

Artikulu hau blog teknikoko artikulu batzuen lehenengoa da NEAR. NEAR aplikazio deszentralizatuak garatzeko blockchain protokoloa eta plataforma bat da, azken erabiltzaileentzako garapen erraztasunean eta erabiltzeko erraztasunean azpimarratuz.

Protokolo kodea irekita dago, gure inplementazioa Rust-en idatzita dago, aurki daiteke Hemen.

NEAR-en garapena nolakoa den ikusi eta lineako IDEan esperimentatu dezakezu Hemen.

Albiste guztiak errusieraz jarrai ditzakezu hemen telegrama taldea eta taldea VKontakte-n, eta ingelesez ofizialean Twitter.

Laster arte!

Iturria: www.habr.com