Ĉu eblas generi hazardajn nombrojn se ni ne fidas unu la alian? Parto 1

Hej Habr!

En ĉi tiu artikolo mi parolos pri la generacio de pseŭdo-hazardaj nombroj de partoprenantoj, kiuj ne fidas unu la alian. Kiel ni vidos sube, efektivigi "preskaŭ" bonan generatoron estas sufiĉe simpla, sed tre bona estas malfacila.

Kial estus necese generi hazardajn nombrojn inter partoprenantoj, kiuj ne fidas unu la alian? Unu aplika areo estas malcentralizitaj aplikoj. Ekzemple, aplikaĵo kiu akceptas veton de partoprenanto kaj aŭ duobligas la kvanton kun 49% probableco aŭ forprenas kun 51% probableco nur funkcios se ĝi povas senpartie ricevi hazardan nombron. Se atakanto povas influi la rezulton de la hazarda nombro-generatoro, kaj eĉ iomete pliigi sian ŝancon ricevi pagon en la aplikaĵo, li facile ruinigos ĝin.

Kiam ni desegnas distribuitan hazardan nombrogeneracian protokolon, ni volas, ke ĝi havu tri trajtojn:

1. Li devas esti nepartia. Alivorte, neniu partoprenanto devus iel influi la rezulton de la hazarda nombrogeneratoro.

2. Li devas esti neantaŭvidebla. Alivorte, neniu partoprenanto devus povi antaŭdiri kian nombron estos generita (aŭ konkludi iun ajn el ĝiaj trajtoj) antaŭ ol ĝi estas generita.

3. La protokolo devas esti realigebla, tio estas, imuna al la fakto, ke certa procento de partoprenantoj malkonektas de la reto aŭ intence provas ĉesigi la protokolon.

En ĉi tiu artikolo ni rigardos du alirojn: RANDAO + VDF kaj la aliro de forviŝkodoj. En la sekva parto, ni ekzamenos detale la aliron bazitan sur sojlaj subskriboj.

Sed unue, ni rigardu simplan kaj ofte uzatan algoritmon, kiu estas realigebla, neantaŭvidebla, sed partia.

RANDAO

RANDAO estas tre simpla kaj tial sufiĉe ofte uzata aliro al generado de hazardo. Ĉiuj retpartoprenantoj unue loke elektas pseŭdohazardan nombron, poste ĉiu partoprenanto sendas hash de la elektita nombro. Poste, la partoprenantoj laŭvice malkaŝas siajn elektitajn nombrojn kaj faras XOR-operacion sur la malkaŝitaj nombroj, kaj la rezulto de ĉi tiu operacio fariĝas la rezulto de la protokolo.

La paŝo publikigi la haŝojn antaŭ malkaŝi la nombrojn estas necesa por ke la atakanto ne povas elekti sian numeron post kiam li vidis la nombrojn de la aliaj partoprenantoj. Tio permesus al li praktike sole determini la produktadon de la hazarda nombrogeneratoro.

Dum la kurso de la protokolo, partoprenantoj devas veni al komuna decido (t.n. konsento) dufoje: kiam komenci malkaŝi la elektitajn nombrojn, kaj tial ĉesi akcepti haŝojn, kaj kiam ĉesi akcepti la elektitajn nombrojn kaj kalkuli la rezultan hazardan. nombro. Fari tiajn decidojn inter partoprenantoj, kiuj ne fidas unu la alian, ne estas facila tasko en si mem, kaj ni revenos al ĝi en estontaj artikoloj; en ĉi tiu artikolo ni supozos, ke tia konsenta algoritmo estas disponebla por ni.

Kiun el la ecoj, kiujn ni priskribis supre, havas RANDAO? Ĝi estas neantaŭvidebla, havas la saman viglecon kiel la subesta konsenta protokolo, sed ĝi estas partia. Specife, atakanto povas observi la reton, kaj post kiam aliaj partoprenantoj rivelas siajn numerojn, li povas kalkuli ilian XOR, kaj decidi ĉu aŭ ne riveli sian numeron por influi la rezulton. Dum ĉi tio malhelpas la atakanton sole determini la produktadon de la hazarda nombrogeneratoro, ĝi ankoraŭ donas al li 1 pecon da influo. Kaj se atakantoj kontrolas plurajn partoprenantojn, tiam la nombro da bitoj kiujn ili regas egalos al la nombro da partoprenantoj sub ilia kontrolo.

La influo de atakantoj povas esti tre reduktita postulante ke partoprenantoj malkaŝu la nombrojn en ordo. Tiam la atakanto povos influi la rezulton nur se ĝi estas malfermita laste. Dum la influo estas signife malpli, la algoritmo daŭre estas partia.

RANDAO+VDF

Unu maniero fari RANDAO nepartian estas jena: post kiam ĉiuj nombroj estas malkaŝitaj kaj la XOR estas kalkulita, ĝia rezulto estas enigita en la enigaĵon de funkcio, kiu bezonas tre longan tempon por kalkuli, sed permesas vin kontroli la ĝustecon de la funkcio. kalkulo tre rapide.

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

Ĉi tiu funkcio nomiĝas Kontrolebla Malfrua Funkcio aŭ VDF. Se kalkuli la finan rezulton daŭras pli longe ol la numero-malkovrostadio, tiam la atakanto ne povos antaŭdiri la efikon montri aŭ kaŝi sian numeron, kaj tial li perdos la ŝancon influi la rezulton.

Disvolvi bonajn VDF-ojn estas ekstreme malfacila. Okazis pluraj trarompoj lastatempe, ekz. ĉi tio и ĉi tio, kiu faris VDF pli praktika en praktiko, kaj Ethereum 2.0 planas uzi RANDAO kun VDF kiel hazarda nombro fonto longtempe. Krom la fakto, ke ĉi tiu aliro estas neantaŭvidebla kaj senantaŭjuĝa, ĝi havas la kroman avantaĝon esti realigebla se almenaŭ du partoprenantoj estas disponeblaj en la reto (supozante, ke la konsenta protokolo uzata estas realigebla kiam oni traktas tiel malgrandan nombron da partoprenantoj).

La plej granda defio de ĉi tiu aliro estas starigi la VDF tia ke eĉ partoprenanto kun tre multekosta specialigita aparataro ne povos kalkuli la VDF antaŭ la fino de la malkovra fazo. Ideale, la algoritmo eĉ havu signifan sekurecan marĝenon, ekzemple 10x. La malsupra figuro montras atakon de aktoro, kiu havas specialecan ASIC, kiu permesas al li funkciigi VDF pli rapide ol la tempo asignita por malkaŝi la RANDAO-konfirmon. Tia partoprenanto ankoraŭ povas kalkuli la finan rezulton uzante aŭ ne uzante sian numeron, kaj tiam, surbaze de la kalkulo, elekti ĉu montri ĝin aŭ ne.

Por la VDF-familio menciita supre, la agado de dediĉita ASIC povas esti 100+ fojojn pli alta ol konvencia aparataro. Do se la malkaŝa fazo daŭras 10 sekundojn, tiam la VDF komputita sur tia ASIC devas preni pli ol 100 sekundojn por havi 10x sekurecan marĝenon, kaj tiel la sama VDF komputita sur varhardvaro devas preni 100x 100 sekundojn = ~3 horoj.

La Ethereum Foundation planas solvi ĉi tiun problemon kreante siajn proprajn publike disponeblajn senpagajn ASIC-ojn. Post kiam tio okazas, ĉiuj aliaj protokoloj ankaŭ povas utiligi ĉi tiun teknologion, sed ĝis tiam la aliro RANDAO+VDF ne estos tiel realigebla por protokoloj kiuj ne povas investi en evoluigado de siaj propraj ASICoj.

Multaj artikoloj, filmetoj kaj aliaj informoj pri VDF estis kolektitaj ĉi tiu retejo.

Ni uzas forviŝkodojn

En ĉi tiu sekcio, ni rigardos hazardan nombrogeneracian protokolon kiu uzas viŝante kodojn. Ĝi povas toleri ĝis ⅓ atakantojn restante realigebla, kaj permesas ĝis ⅔ atakantojn ekzisti antaŭ ol ili povas antaŭdiri aŭ influi la rezulton.

La ĉefa ideo de la protokolo estas jena. Por simpleco, ni supozu, ke estas ekzakte 100 partoprenantoj. Ni ankaŭ supozu, ke ĉiuj partoprenantoj loke havas iun privatan ŝlosilon, kaj la publikaj ŝlosiloj de ĉiuj partoprenantoj estas konataj de ĉiuj partoprenantoj:

1. Ĉiu partoprenanto loke elpensas longan ŝnuron, rompas ĝin en 67 partojn, kreas forviŝkodojn por akiri 100 akciojn tiel ke iuj 67 sufiĉas por reakiri la ŝnuron, asignas ĉiun el la 100 akcioj al unu el la partoprenantoj, kaj ĉifras ilin per la publika ŝlosilo de la sama partoprenanto. Ĉiuj koditaj akcioj tiam estas publikigitaj.

2. Partoprenantoj uzas ian konsenton por atingi interkonsenton pri kodigitaj aroj de specifaj 67 partoprenantoj.

3. Post kiam konsento estas atingita, ĉiu partoprenanto prenas la ĉifritajn akciojn en ĉiu el la 67 aroj ĉifritaj per sia publika ŝlosilo, deĉifras ĉiujn tiajn akciojn, kaj publikigas ĉiujn tiajn deĉifritajn akciojn.

4. Post kiam 67 partoprenantoj kompletigis paŝon (3), ĉiuj interkonsentitaj aroj povas esti tute malkoditaj kaj rekonstruitaj pro la trajtoj de forviŝkodoj, kaj la fina nombro povas esti akirita kiel XOR de la komencaj vicoj per kiuj la partoprenantoj komencis en (1) .

Ĉi tiu protokolo povas montriĝi kiel nepartia kaj neantaŭvidebla. La rezulta hazarda nombro estas determinita post kiam konsento estas atingita, sed ne estas konata al iu ajn ĝis ⅔ de la partoprenantoj deĉifras la partojn ĉifritajn per sia publika ŝlosilo. Tiel, la hazarda nombro estas determinita antaŭ ol informoj sufiĉaj por rekonstrui ĝin estas publikigita.

Kio okazas se en paŝo (1) unu el la partoprenantoj sendis kodigitajn akciojn al la aliaj partoprenantoj kiuj ne estas la ĝusta forviŝkodo por iu ĉeno? Sen aldonaj ŝanĝoj, malsamaj partoprenantoj aŭ tute ne povos reakiri la ŝnuron, aŭ ili reakiros malsamajn ŝnurojn, kio rezultigos, ke malsamaj partoprenantoj ricevos malsaman hazardan nombron. Por malhelpi tion, vi povas fari la jenon: ĉiu partoprenanto, krom la kodigitaj akcioj, ankaŭ kalkulas Merkla arbo ĉiuj tiaj akcioj, kaj sendas al ĉiu partoprenanto kaj la kodigitan parton mem kaj la radikon de la merkle-arbo, kaj pruvon de la inkludo de la parto en la merkle-arbo. En la konsento en paŝo (2), la partoprenantoj tiam ne nur konsentas pri aro da aroj, sed pri aro de specifaj radikoj de tiaj arboj (se iu partoprenanto deviis de la protokolo, kaj sendis malsamajn merkle-arbajn radikojn al malsamaj partoprenantoj, kaj du tiaj radikoj estas montritaj dum konsento, lia la vico ne estas inkluzivita en la rezulta aro). Kiel rezulto de la konsento, ni havos 67 kodigitajn liniojn kaj la respondajn radikojn de la merkle-arbo tiel ke ekzistas almenaŭ 67 partoprenantoj (ne nepre la samaj kiuj proponis la respondajn liniojn), kiuj por ĉiu el la 67 linioj havas mesaĝo kun parto de la forviŝkodo, kaj pruvo la okazo de ilia parto en la responda arbo paliĝis.

Kiam en paŝo (4) la partoprenanto deĉifras 67 taktojn por certa ŝnuro kaj provas rekonstrui la originan ŝnuron el ili, unu el la opcioj eblas:

1. La ŝnuro estas restarigita, kaj se ĝi tiam estas forviŝ-kodita denove, kaj la Merkle-arbo estas kalkulita por la loke kalkulitaj akcioj, la radiko koincidas kun tiu pri kiu konsento estis atingita.

2. La vico estas restarigita, sed la loke kalkulita radiko ne kongruas kun tiu ĉe kiu konsento estis atingita.

3. La vico ne estas restarigita.

Estas facile montri, ke se opcio (1) okazis por almenaŭ unu partoprenanto supre, tiam opcio (1) okazis por ĉiuj partoprenantoj, kaj inverse, se opcio (2) aŭ (3) okazis por almenaŭ unu partoprenanto, tiam por ĉiuj partoprenantoj okazos opcio (2) aŭ (3). Tiel, por ĉiu vico en la aro, aŭ ĉiuj partoprenantoj sukcese reakiros ĝin, aŭ ĉiuj partoprenantoj malsukcesos reakiri ĝin. La rezulta hazarda nombro tiam estas XOR de nur la vicoj kiujn partoprenantoj povis reakiri.

Sojlaj subskriboj

Alia aliro al hazardo estas uzi tion, kion oni nomas BLS-sojlaj subskriboj. Hazarda nombrogeneratoro bazita sur sojlosignaturoj havas precize la samajn garantiojn kiel la forviŝkod-bazita algoritmo priskribita supre, sed havas signife pli malaltan asimptotan nombron da mesaĝoj senditaj tra la reto por ĉiu generita nombro.

BLS-signaturoj estas dezajno kiu permesas al pluraj partoprenantoj krei unu komunan subskribon por mesaĝo. Ĉi tiuj subskriboj ofte estas uzataj por ŝpari spacon kaj bendolarĝon ne postulante ke pluraj subskriboj estu senditaj. 

Ofta apliko por BLS-subskriboj en blokĉenaj protokoloj, krom generado de hazardaj nombroj, estas bloksubskribo en BFT-protokoloj. Ni diru, ke 100 partoprenantoj kreas blokojn, kaj bloko estas konsiderata fina se 67 el ili subskribas ĝin. Ili ĉiuj povas sendi siajn partojn de la BLS-signaturo kaj uzi iun konsentan algoritmon por konsenti pri 67 el ili kaj poste kunfandi ilin en unu BLS-signaturon. Ajna 67 (aŭ pli) partoj povas esti uzataj por krei la finan subskribon, kiu dependos de kiuj 67 subskriboj estis kombinitaj kaj tial povas varii, kvankam malsamaj elektoj de la 67 partoprenantoj kreos malsaman subskribon, ĉiu tia subskribo estos valida. subskribo por la bloko. La ceteraj partoprenantoj tiam nur bezonas ricevi kaj kontroli nur unu subskribon per bloko, anstataŭ 67, tra la reto, kio signife reduktas la ŝarĝon en la reto.

Rezultas, ke se la privataj ŝlosiloj, kiujn uzas partoprenantoj, estas generitaj en certa maniero, do ne gravas, kiuj 67 subskriboj (aŭ pli, sed ne malpli) estas kunigitaj, la rezulta subskribo estos la sama. Ĉi tio povas esti uzata kiel fonto de hazardo: partoprenantoj unue konsentas pri iu mesaĝo, kiun ili subskribos (ĉi tio povus esti la eligo de RANDAO aŭ nur la haŝo de la lasta bloko, ĝi ne vere gravas kondiĉe ke ĝi ŝanĝiĝas ĉiufoje. kaj estas konsekvenca) kaj kreu BLS-signaturon por ĝi. La rezulto de la generacio estos neantaŭvidebla ĝis 67 partoprenantoj disponigos siajn partojn, kaj post tio la eligo jam estas antaŭdeterminita kaj ne povas dependi de la agoj de iu ajn partoprenanto.

Ĉi tiu aliro al hazardo estas realigebla kondiĉe ke almenaŭ ⅔ el la partoprenantoj interrete ambaŭ sekvas la protokolon, kaj estas nepartia kaj neantaŭvidebla kondiĉe ke almenaŭ ⅓ el la partoprenantoj sekvas la protokolon. Gravas noti, ke atakanto, kiu regas pli ol ⅓ sed malpli ol ⅔ de la partoprenantoj, povas ĉesigi la protokolon, sed ne povas antaŭdiri aŭ influi ĝian eliron.

Sojlaj subskriboj mem estas tre interesa temo. En la dua parto de la artikolo, ni analizos detale kiel ili funkcias, kaj kiel precize necesas generi partoprenantajn ŝlosilojn, por ke sojlaj subskriboj estu uzataj kiel hazarda nombrogeneratoro.

En konkludo

Ĉi tiu artikolo estas la unua el serio de teknikaj blogartikoloj PROKSIME. NEAR estas blokĉena protokolo kaj platformo por disvolvi malcentralizitajn aplikojn kun emfazo de facileco de disvolviĝo kaj facileco de uzo por finaj uzantoj.

La protokola kodo estas malfermita, nia efektivigo estas skribita en Rust, ĝi troveblas tie.

Vi povas vidi kiel aspektas evoluo por NEAR kaj eksperimenti en la reta IDE tie.

Vi povas sekvi ĉiujn novaĵojn en la rusa ĉe telegrama grupo kaj en grupo ĉe VKontakte, kaj en la angla en la oficiala twitter.

Ĝis baldaŭ!

fonto: www.habr.com