Onko mahdollista tuottaa satunnaisia ​​lukuja, jos emme luota toisiimme? Osa 1

Hei Habr!

Tässä artikkelissa puhun pseudosatunnaislukujen luomisesta osallistujien toimesta, jotka eivät luota toisiinsa. Kuten alla näemme, "melkein" hyvän generaattorin toteuttaminen on melko yksinkertaista, mutta erittäin hyvä on vaikeaa.

Miksi olisi tarpeen luoda satunnaisia ​​lukuja osallistujien kesken, jotka eivät luota toisiinsa? Yksi sovellusalue on hajautetut sovellukset. Esimerkiksi sovellus, joka hyväksyy vedon osallistujalta ja joko tuplaa summan 49 %:n todennäköisyydellä tai ottaa pois 51 %:n todennäköisyydellä, toimii vain, jos se voi saada puolueettomasti satunnaisluvun. Jos hyökkääjä voi vaikuttaa satunnaislukugeneraattorin lopputulokseen ja jopa hieman lisätä mahdollisuuttaan saada voitto sovelluksessa, hän tuhoaa sen helposti.

Kun suunnittelemme hajautetun satunnaislukujen generointiprotokollan, haluamme, että sillä on kolme ominaisuutta:

1. Hänen täytyy olla puolueeton. Toisin sanoen kenenkään osallistujan ei pitäisi millään tavalla vaikuttaa satunnaislukugeneraattorin tulokseen.

2. Hänen täytyy olla arvaamaton. Toisin sanoen, yhdenkään osallistujan ei pitäisi pystyä ennustamaan, mikä luku luodaan (tai päätellä sen ominaisuuksista) ennen sen luomista.

3. Protokollan on oltava käyttökelpoinen, toisin sanoen vastustuskykyinen sille, että tietty prosenttiosuus osallistujista katkaisee yhteyden verkosta tai yrittää tarkoituksella pysäyttää protokollan.

Tässä artikkelissa tarkastellaan kahta lähestymistapaa: RANDAO + VDF ja poistokoodien lähestymistapa. Seuraavassa osassa tarkastelemme yksityiskohtaisesti kynnysallekirjoituksiin perustuvaa lähestymistapaa.

Mutta ensin tarkastellaan yksinkertaista ja yleisesti käytettyä algoritmia, joka on toteuttamiskelpoinen, arvaamaton, mutta puolueellinen.

RANDAO

RANDAO on hyvin yksinkertainen ja siksi melko yleisesti käytetty tapa luoda satunnaisuutta. Kaikki verkon osallistujat valitsevat ensin paikallisesti näennäissatunnaisen luvun, jonka jälkeen kukin osallistuja lähettää valitun numeron tiivisteen. Seuraavaksi osallistujat vuorotellen paljastavat valitsemansa numerot ja suorittavat XOR-operaation paljastetuille numeroille, ja tämän toiminnon tuloksesta tulee protokollan tulos.

Hajautusarvojen julkaiseminen ennen numeroiden paljastamista on välttämätön, jotta hyökkääjä ei voi valita numeroaan nähtyään muiden osallistujien numerot. Näin hän voisi käytännössä yksin määrittää satunnaislukugeneraattorin lähdön.

Protokollan aikana osallistujien tulee tehdä yhteinen päätös (ns. konsensus) kahdesti: milloin aloittaa valittujen lukujen paljastaminen ja lopettaa siten tiivisteiden hyväksyminen ja milloin lopettaa valittujen lukujen hyväksyminen ja tuloksena olevan satunnaisen laskeminen. määrä. Tällaisten päätösten tekeminen toisiinsa luottamattomien osallistujien kesken ei ole sinänsä helppo tehtävä, ja palaamme siihen tulevissa artikkeleissa; tässä artikkelissa oletetaan, että tällainen konsensusalgoritmi on käytettävissämme.

Mitä yllä kuvailemistamme ominaisuuksista RANDAOlla on? Se on arvaamaton, sillä on sama elinvoimaisuus kuin taustalla oleva konsensusprotokolla, mutta se on puolueellinen. Tarkemmin sanottuna hyökkääjä voi tarkkailla verkkoa, ja kun muut osallistujat ovat paljastaneet numeronsa, hän voi laskea niiden XOR:n ja päättää, paljastaako hänen numeronsa lopputulokseen vaikuttamiseksi. Vaikka tämä estää hyökkääjää yksin määrittämästä satunnaislukugeneraattorin lähtöä, se antaa hänelle silti 1 bitin vaikutusvaltaa. Ja jos hyökkääjät hallitsevat useita osallistujia, heidän hallitsemiensa bittien määrä on yhtä suuri kuin heidän hallinnassaan olevien osallistujien määrä.

Hyökkääjien vaikutusta voidaan vähentää huomattavasti vaatimalla osallistujia paljastamaan numerot järjestyksessä. Tällöin hyökkääjä voi vaikuttaa lopputulokseen vain, jos se avataan viimeisenä. Vaikka vaikutus on huomattavasti pienempi, algoritmi on silti puolueellinen.

RANDAO+VDF

Yksi tapa tehdä RANDAOsta puolueeton on tämä: kun kaikki luvut on paljastettu ja XOR on laskettu, sen tulos syötetään funktion syötteeseen, jonka laskeminen kestää hyvin kauan, mutta jonka avulla voit tarkistaa funktion oikeellisuuden. laskelma hyvin nopeasti.

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

Tätä toimintoa kutsutaan Verifiable Delay Function tai VDF. Jos lopputuloksen laskeminen kestää kauemmin kuin numeron paljastamisvaihe, hyökkääjä ei pysty ennustamaan numeronsa näyttämisen tai piilottamisen vaikutusta, ja siksi hän menettää mahdollisuuden vaikuttaa tulokseen.

Hyvien VDF-tiedostojen kehittäminen on erittäin vaikeaa. Viime aikoina on tapahtunut useita läpimurtoja, mm. tämä и Tämä, mikä teki VDF:stä käytännöllisemmän käytännössä, ja Ethereum 2.0 aikoo käyttää RANDAO:ta VDF:n kanssa satunnaislukulähteenä pitkällä aikavälillä. Sen lisäksi, että tämä lähestymistapa on arvaamaton ja puolueeton, sen lisäetu on elinkelpoinen, jos verkossa on saatavilla vähintään kaksi osallistujaa (olettaen, että käytetty konsensusprotokolla on käyttökelpoinen, kun on kyse niin pienestä osallistujamäärästä).

Tämän lähestymistavan suurin haaste on VDF:n asettaminen siten, että edes osallistuja, jolla on erittäin kallis erikoislaitteisto, ei pysty laskemaan VDF:ää ennen etsintävaiheen loppua. Ihannetapauksessa algoritmilla pitäisi olla jopa merkittävä turvamarginaali, vaikkapa 10x. Alla olevassa kuvassa näkyy sellaisen näyttelijän hyökkäys, jolla on erikoistunut ASIC, jonka avulla hän voi suorittaa VDF:n nopeammin kuin RANDAO-vahvistuksen paljastamiseen varattu aika. Tällainen osallistuja voi silti laskea lopputuloksen omalla numerollaan tai ilman, ja sitten laskelman perusteella valita, näyttääkö se vai ei.

Yllä mainitussa VDF-perheessä erillisen ASIC:n suorituskyky voi olla yli 100 kertaa suurempi kuin perinteisen laitteiston. Joten jos käyttöönottovaihe kestää 10 sekuntia, niin tällaisella ASIC:lla lasketun VDF:n täytyy kestää yli 100 sekuntia, jotta sillä on 10-kertainen turvamarginaali, ja näin ollen saman hyödykelaitteistolla lasketun VDF:n on kestettävä 100x 100 sekuntia = ~3 tuntia.

Ethereum-säätiö aikoo ratkaista tämän ongelman luomalla omat julkisesti saatavilla olevat ilmaiset ASIC-kortit. Kun tämä tapahtuu, kaikki muut protokollat ​​voivat myös hyödyntää tätä tekniikkaa, mutta siihen asti RANDAO+VDF-lähestymistapa ei ole yhtä käyttökelpoinen protokollille, jotka eivät voi investoida omien ASIC-piiriensä kehittämiseen.

VDF:stä on kerätty monia artikkeleita, videoita ja muuta tietoa tällä sivustolla.

Käytämme poistokoodeja

Tässä osiossa tarkastelemme satunnaislukujen generointiprotokollaa, joka käyttää koodien poistaminen. Se sietää jopa ⅓ hyökkääjää pysyen elinkelpoisena ja sallii jopa ⅔ hyökkääjien olemassaolon ennen kuin he voivat ennustaa tai vaikuttaa lopputulokseen.

Protokollan pääidea on seuraava. Yksinkertaisuuden vuoksi oletetaan, että osallistujia on tasan 100. Oletetaan myös, että kaikilla osallistujilla on paikallisesti jokin yksityinen avain ja kaikkien osallistujien julkiset avaimet ovat kaikkien osallistujien tiedossa:

1. Jokainen osallistuja keksii paikallisesti pitkän merkkijonon, jakaa sen 67 osaan, luo poistokoodit saadakseen 100 jakoa siten, että mikä tahansa 67 riittää merkkijonon palauttamiseen, määrittää jokaisen 100 osuudesta yhdelle osallistujasta ja salaa ne saman osallistujan julkinen avain. Kaikki koodatut osuudet julkaistaan ​​sitten.

2. Osallistujat käyttävät jonkinlaista konsensusta päästäkseen sopimukseen koodatuista sarjoista tietyn 67 osallistujan kesken.

3. Kun yhteisymmärrykseen on päästy, jokainen osallistuja ottaa koodatut osuudet kustakin 67 joukosta, jotka on salattu heidän julkisella avaimellaan, purkaa kaikki tällaiset osuudet ja julkaisee kaikki tällaiset salatut osuudet.

4. Kun 67 osallistujaa on suorittanut vaiheen (3), kaikki sovitut joukot voidaan dekoodata ja rekonstruoida kokonaan poistokoodien ominaisuuksien vuoksi, ja lopullinen luku voidaan saada XOR-arvona ensimmäisistä riveistä, joilla osallistujat aloittivat kohdassa (1). .

Tämän protokollan voidaan osoittaa olevan puolueeton ja arvaamaton. Tuloksena oleva satunnaisluku määritetään, kun konsensus on saavutettu, mutta se ei ole kenenkään tiedossa ennen kuin ⅔ osallistujista purkaa julkisella avaimellaan salatut osat. Näin ollen satunnaisluku määritetään ennen kuin sen rekonstruoimiseen riittävät tiedot julkaistaan.

Mitä tapahtuu, jos vaiheessa (1) yksi osallistujista lähettää muille osallistujille koodattuja jakoja, jotka eivät ole oikea poistokoodi jollekin merkkijonolle? Ilman lisämuutoksia eri osallistujat eivät joko pysty palauttamaan merkkijonoa ollenkaan tai he palauttavat eri merkkijonoja, mikä johtaa siihen, että eri osallistujat saavat eri satunnaisluvun. Tämän estämiseksi voit tehdä seuraavasti: jokainen osallistuja laskee koodattujen osuuksien lisäksi myös Merklan puu kaikki tällaiset osuudet ja lähettää jokaiselle osallistujalle sekä itse koodatun osuuden että merkkipuun juuren sekä todisteen osuuden sisällyttämisestä merklepuuhun. Vaiheen (2) konsensuksessa osallistujat eivät sitten vain sovi joukosta joukkoja, vaan joukosta tiettyjä tällaisten puiden juuria (jos joku osallistuja poikkesi protokollasta ja lähetti eri merklepuun juuria eri osallistujille, ja kaksi tällaista juuria näytetään konsensuksen aikana, hänen rivi ei sisälly tulosjoukkoon). Konsensuksen tuloksena meillä on 67 koodattua riviä ja vastaavat merklepuun juuret siten, että osallistujia on vähintään 67 (ei välttämättä samoja, jotka ehdottivat vastaavat rivit), joilla jokaisella 67 rivillä on viesti, jossa oli osuus poistokoodista, ja todiste niiden osuuden esiintymisestä vastaavassa puussa haalistuvat.

Kun vaiheessa (4) osallistuja tulkitsee 67 lyöntiä tietylle merkkijonolle ja yrittää rekonstruoida niistä alkuperäisen merkkijonon, yksi vaihtoehdoista on mahdollinen:

1. Merkkijono palautetaan, ja jos se sitten poistokoodataan uudelleen ja Merkle-puu lasketaan paikallisesti lasketuille osuuksille, juuri on sama kuin se, josta päästiin yksimielisyyteen.

2. Rivi palautetaan, mutta paikallisesti laskettu juuri ei vastaa sitä, jossa konsensus saavutettiin.

3. Riviä ei palauteta.

On helppo osoittaa, että jos vaihtoehto (1) tapahtui vähintään yhdelle yllä olevalle osallistujalle, niin vaihtoehto (1) tapahtui kaikille osallistujille ja päinvastoin, jos vaihtoehto (2) tai (3) tapahtui vähintään yhdelle osallistujalle, niin kaikille osallistujille vaihtoehto (2) tai (3) toteutuu. Siten jokaisella joukon rivillä joko kaikki osallistujat onnistuvat palauttamaan sen tai kaikki osallistujat eivät pysty palauttamaan sitä. Tuloksena oleva satunnaisluku on sitten vain niiden rivien XOR, jotka osallistujat pystyivät palauttamaan.

Kynnys allekirjoitukset

Toinen tapa satunnaisuuteen on käyttää niin kutsuttuja BLS-kynnysallekirjoituksia. Kynnysallekirjoituksiin perustuvalla satunnaislukugeneraattorilla on täsmälleen samat takuut kuin yllä kuvatulla poistokoodipohjaisella algoritmilla, mutta sillä on huomattavasti pienempi asymptoottinen määrä viestejä, jotka lähetetään verkon yli kutakin generoitua numeroa kohden.

BLS-allekirjoitukset ovat suunnittelu, jonka avulla useat osallistujat voivat luoda yhden yhteisen allekirjoituksen viestille. Näitä allekirjoituksia käytetään usein säästämään tilaa ja kaistanleveyttä, koska ei vaadita useiden allekirjoitusten lähettämistä. 

Yleinen sovellus BLS-allekirjoituksille lohkoketjuprotokollissa satunnaislukujen generoinnin lisäksi on lohkoallekirjoitus BFT-protokollassa. Oletetaan, että 100 osallistujaa luo lohkoja, ja lohko katsotaan lopulliseksi, jos 67 heistä allekirjoittaa sen. He voivat kaikki lähettää osansa BLS-allekirjoituksesta ja käyttää jotakin konsensusalgoritmia sopiakseen niistä 67:stä ja sitten yhdistää ne yhdeksi BLS-allekirjoitukseksi. Mitä tahansa 67 (tai useampaa) osaa voidaan käyttää lopullisen allekirjoituksen luomiseen, mikä riippuu siitä, mitkä 67 allekirjoitusta yhdistettiin ja voivat siksi vaihdella, vaikka 67 osallistujan erilaiset valinnat luovat erilaisen allekirjoituksen , jokainen tällainen allekirjoitus on kelvollinen. lohkon allekirjoitus. Jäljellä olevien osallistujien tarvitsee sitten vastaanottaa ja vahvistaa vain yksi allekirjoitus lohkoa kohden 67 sijasta verkon yli, mikä vähentää merkittävästi verkon kuormitusta.

Osoittautuu, että jos osallistujien käyttämät yksityiset avaimet luodaan tietyllä tavalla, riippumatta siitä, mitkä 67 allekirjoitusta (tai enemmän, mutta ei vähemmän) yhdistetään, tuloksena oleva allekirjoitus on sama. Tätä voidaan käyttää satunnaisuuden lähteenä: osallistujat sopivat ensin jostain viestistä, jonka he allekirjoittavat (tämä voi olla RANDAO:n tulos tai vain viimeisen lohkon hash, sillä ei ole väliä, kunhan se muuttuu joka kerta ja on johdonmukainen) ja luo sille BLS-allekirjoitus. Sukupolven tulos on arvaamaton, kunnes 67 osallistujaa toimittaa osansa, ja sen jälkeen tulos on jo ennalta määrätty, eikä se voi olla riippuvainen kenenkään osallistujan toimista.

Tämä lähestymistapa satunnaisuuteen on käyttökelpoinen niin kauan kuin vähintään ⅔ verkossa olevista osallistujista noudattaa protokollaa, ja se on puolueeton ja arvaamaton niin kauan kuin vähintään ⅓ osallistujista noudattaa protokollaa. On tärkeää huomata, että hyökkääjä, joka hallitsee enemmän kuin ⅓ mutta vähemmän kuin ⅔ osallistujista, voi pysäyttää protokollan, mutta ei voi ennustaa tai vaikuttaa sen ulostuloon.

Kynnys allekirjoitukset itsessään ovat erittäin mielenkiintoinen aihe. Artikkelin toisessa osassa analysoimme yksityiskohtaisesti, kuinka ne toimivat ja kuinka tarkalleen on tarpeen luoda osallistujaavaimet, jotta kynnysallekirjoituksia voidaan käyttää satunnaislukugeneraattorina.

lopuksi

Tämä artikkeli on ensimmäinen teknisten blogiartikkeleiden sarjassa NEAR. NEAR on lohkoketjuprotokolla ja alusta hajautettujen sovellusten kehittämiseen painottaen kehittämisen helppoutta ja helppokäyttöisyyttä loppukäyttäjille.

Protokollakoodi on avoin, toteutuksemme on kirjoitettu ruosteella, se löytyy täällä.

Voit nähdä miltä NEAR-kehitys näyttää ja kokeilla online-IDE:ssä täällä.

Voit seurata kaikkia uutisia venäjäksi osoitteessa sähkeryhmä ja ryhmä VKontaktessa, ja englanniksi virallisessa viserrys.

Nähdään pian!

Lähde: will.com