Er hægt að búa til handahófskenndar tölur ef við treystum ekki hvort öðru? 1. hluti

Hæ Habr!

Í þessari grein mun ég tala um myndun gervi-handahófsnúmera af þátttakendum sem treysta ekki hver öðrum. Eins og við munum sjá hér að neðan er frekar einfalt að útfæra „næstum“ góðan rafall, en mjög góður er erfitt.

Hvers vegna er nauðsynlegt að búa til handahófskenndar tölur meðal þátttakenda sem treysta ekki hver öðrum? Eitt umsóknarsvæði er dreifð forrit. Til dæmis, forrit sem samþykkir veðmál frá þátttakanda og annað hvort tvöfaldar upphæðina með 49% líkum eða tekur burt með 51% líkum mun aðeins virka ef það getur óhlutdrægt fengið tilviljunarkennda tölu. Ef árásarmaður getur haft áhrif á niðurstöðu slembitöluframleiðandans, og jafnvel aukið örlítið möguleika sína á að fá útborgun í forritinu, mun hann auðveldlega eyðileggja það.

Þegar við hönnum dreifða samskiptareglur fyrir slembitölumyndun viljum við að hún hafi þrjá eiginleika:

1. Hann hlýtur að vera hlutlaus. Með öðrum orðum, enginn þátttakandi ætti á nokkurn hátt að hafa áhrif á niðurstöðu slembitöluframleiðandans.

2. Hann hlýtur að vera óútreiknanlegur. Með öðrum orðum, enginn þátttakandi ætti að geta spáð fyrir um hvaða tala verður mynduð (eða ályktað um eiginleika hennar) áður en hún er mynduð.

3. Samskiptareglurnar verða að vera hagkvæmar, það er að segja að þær séu ónæmar fyrir því að ákveðið hlutfall þátttakenda aftengist netinu eða reyni vísvitandi að stöðva samskiptaregluna.

Í þessari grein munum við skoða tvær aðferðir: RANDAO + VDF og eyðingarkóða nálgunina. Í næsta hluta munum við skoða ítarlega nálgunina sem byggir á þröskulds undirskriftum.

En fyrst skulum við líta á einfalt og almennt notað reiknirit sem er hagkvæmt, ófyrirsjáanlegt, en hlutdrægt.

RANDAO

RANDAO er mjög einföld og því frekar algeng nálgun til að búa til handahófi. Allir þátttakendur netkerfisins velja fyrst gervi-slembinúmer á staðnum, síðan sendir hver þátttakandi kjötkássa af völdu númeri. Næst skiptast þátttakendur á að sýna þær tölur sem þeir hafa valið og framkvæma XOR-aðgerð á þeim tölum sem birtar eru og niðurstaða þessarar aðgerðar verður niðurstaða samskiptareglunnar.

Skrefið að birta kjötkássa áður en númerin eru birt er nauðsynlegt svo að árásarmaðurinn geti ekki valið númerið sitt eftir að hann hefur séð númer annarra þátttakenda. Þetta myndi gera honum kleift að ákvarða úttak slembitölugjafa nánast einn í eigin höndum.

Meðan á bókuninni stendur þurfa þátttakendur að taka sameiginlega ákvörðun (svokallaða samstöðu) tvisvar: hvenær á að byrja að birta valdar tölur og hætta því að samþykkja kjötkássa og hvenær á að hætta að samþykkja valda tölur og reikna út af handahófi. númer. Að taka slíkar ákvarðanir á milli þátttakenda sem treysta ekki hver öðrum er ekki auðvelt verkefni í sjálfu sér og við munum koma aftur að því í næstu greinum; í þessari grein munum við gera ráð fyrir að slíkt samstöðualgrím standi okkur til boða.

Hvaða eiginleika sem við lýstum hér að ofan hefur RANDAO? Hún er óútreiknanleg, hefur sama lífskraft og undirliggjandi samstöðubókun, en hún er hlutdræg. Nánar tiltekið getur árásarmaður fylgst með netkerfinu og eftir að aðrir þátttakendur birta tölurnar sínar getur hann reiknað út XOR þeirra og ákveðið hvort hann skuli gefa upp númerið sitt eða ekki til að hafa áhrif á niðurstöðuna. Þó að þetta komi í veg fyrir að árásarmaðurinn geti sjálfur ákvarðað úttak handahófsnúmeraframleiðandans, gefur það honum samt 1 bita áhrif. Og ef árásarmenn stjórna nokkrum þátttakendum, þá mun fjöldi bita sem þeir stjórna vera jafn fjölda þátttakenda undir þeirra stjórn.

Hægt er að draga mjög úr áhrifum árásarmanna með því að krefjast þess að þátttakendur gefi upp tölurnar í röð. Þá mun árásarmaðurinn aðeins geta haft áhrif á niðurstöðuna ef hann er opnaður síðast. Þó áhrifin séu umtalsvert minni er reikniritið samt hlutdrægt.

RANDAO+VDF

Ein leið til að gera RANDAO óhlutdrægan er þessi: eftir að allar tölur hafa komið í ljós og XOR er reiknað, er niðurstaða þess færð inn í inntak falls, sem tekur mjög langan tíma að reikna út, en gerir þér kleift að athuga réttmæti fallsins. útreikning mjög fljótt.

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

Þessi aðgerð er kölluð Verifiable Delay Function, eða VDF. Ef útreikningur á lokaniðurstöðu tekur lengri tíma en númerabirtingastigið, þá mun árásarmaðurinn ekki geta spáð fyrir um áhrif þess að sýna eða fela númerið sitt og því missir hann tækifærið til að hafa áhrif á niðurstöðuna.

Það er mjög erfitt að þróa góða VDF. Nokkrar byltingar hafa orðið að undanförnu, t.d. þetta и þetta, sem gerði VDF hagnýtari í reynd og Ethereum 2.0 ætlar að nota RANDAO með VDF sem slembitölugjafa til lengri tíma litið. Fyrir utan þá staðreynd að þessi nálgun er ófyrirsjáanleg og óhlutdræg, þá hefur hún þann aukna ávinning að vera hagkvæmur ef að minnsta kosti tveir þátttakendur eru tiltækir á netinu (að því gefnu að samstaðan sem notuð er sé raunhæf þegar um er að ræða svo fáan fjölda þátttakenda).

Stærsta áskorunin við þessa nálgun er að setja upp VDF þannig að jafnvel þátttakandi með mjög dýran sérhæfðan vélbúnað mun ekki geta reiknað út VDF fyrir lok uppgötvunarfasa. Helst ætti reikniritið jafnvel að hafa umtalsverða öryggismörk, segjum 10x. Myndin hér að neðan sýnir árás leikara sem er með sérhæfðan ASIC sem gerir honum kleift að keyra VDF hraðar en sá tími sem úthlutað er til að sýna RANDAO staðfestinguna. Slíkur þátttakandi getur samt reiknað út lokaniðurstöðuna með því að nota númerið sitt eða ekki og síðan, byggt á útreikningnum, valið hvort hann sýnir hana eða ekki.

Fyrir VDF fjölskylduna sem nefnd er hér að ofan getur frammistaða sérstakrar ASIC verið 100+ sinnum hærri en venjulegur vélbúnaður. Þannig að ef dreifingarfasinn varir í 10 sekúndur, þá verður VDF reiknað á slíkum ASIC að taka meira en 100 sekúndur til að hafa 10x öryggisbil og þar með verður sami VDF reiknaður á vörubúnaði að taka 100x 100 sekúndur = ~3 klst.

Ethereum Foundation ætlar að leysa þetta vandamál með því að búa til sína eigin opinbera, ókeypis ASIC. Þegar þetta gerist geta allar aðrar samskiptareglur einnig nýtt sér þessa tækni, en þangað til mun RANDAO+VDF nálgunin ekki vera eins hagkvæm fyrir samskiptareglur sem geta ekki fjárfest í að þróa eigin ASICs.

Mörgum greinum, myndböndum og öðrum upplýsingum um VDF hefur verið safnað á þetta vefsvæði.

Við notum eyðingarkóða

Í þessum hluta munum við skoða samskiptareglur fyrir slembitöluframleiðslu sem notar að eyða kóða. Það þolir allt að ⅓ árásarmenn á meðan það er lífvænlegt og leyfir allt að ⅔ árásarmönnum að vera til áður en þeir geta spáð fyrir um eða haft áhrif á niðurstöðuna.

Meginhugmynd bókunarinnar er sem hér segir. Til einföldunar skulum við gera ráð fyrir að þátttakendur séu nákvæmlega 100. Við skulum líka gera ráð fyrir að allir þátttakendur á staðnum hafi einhvern einkalykil og opinberir lyklar allra þátttakenda eru þekktir fyrir alla þátttakendur:

1. Hver þátttakandi á staðnum kemur með langan streng, skiptir honum í 67 hluta, býr til eyðingarkóða til að fá 100 hluti þannig að allir 67 dugi til að endurheimta strenginn, úthlutar hverjum af 100 hlutunum til eins þátttakenda og dulkóðar þá með almenningslykil sama þátttakanda. Öll kóðuð hlutabréf eru síðan birt.

2. Þátttakendur nota einhvers konar samstöðu til að ná samkomulagi um kóðuð sett frá tilteknum 67 þátttakendum.

3. Þegar samstaða hefur náðst tekur hver þátttakandi dulkóðuðu hlutina í hverju 67 settanna sem eru dulkóðaðir með opinberum lykli sínum, afkóðar alla slíka hluti og birtir alla slíka afkóðaða hluti.

4. Þegar 67 þátttakendur hafa lokið skrefi (3) er hægt að afkóða öll samþykkt sett að fullu og endurbyggja vegna eiginleika eyðingarkóða og lokatöluna er hægt að fá sem XOR af upphafslínunum sem þátttakendur byrjuðu með í (1) .

Sýna má að þessi samskiptaregla sé óhlutdræg og ófyrirsjáanleg. Slembitalan sem myndast er ákvörðuð eftir að samstaða hefur náðst, en er ekki þekkt fyrir neinn fyrr en ⅔ þátttakenda afkóða hlutana sem dulkóðaðir eru með opinbera lyklinum sínum. Þannig er slembitalan ákvörðuð áður en upplýsingar sem nægja til að endurgera hana eru birtar.

Hvað gerist ef í skrefi (1) sendi einn þátttakendanna dulkóðaða hluti til hinna þátttakendanna sem eru ekki réttur eyðingarkóði fyrir einhvern streng? Án frekari breytinga munu mismunandi þátttakendur annað hvort alls ekki geta endurheimt strenginn, eða þeir munu endurheimta mismunandi strengi, sem mun leiða til þess að mismunandi þátttakendur fá aðra slembitölu. Til að koma í veg fyrir þetta geturðu gert eftirfarandi: hver þátttakandi reiknar, auk kóðuðu hlutanna, einnig Merkla tré öllum slíkum hlutum, og sendir hverjum þátttakanda bæði kóðaða hlutinn sjálfan og rót merkletrésins, og sönnun fyrir því að hluturinn sé tekinn inn í merkletréð. Í samstöðunni í skrefi (2) eru þátttakendur ekki bara sammála um mengi setts, heldur um mengi tiltekinna róta slíkra trjáa (ef einhver þátttakandi vék frá samskiptareglunni og sendi mismunandi merkle trjárætur til mismunandi þátttakenda, og tvær slíkar rætur eru sýndar við samstöðu, röðin er ekki með í niðurstöðusettinu). Sem afleiðing af samstöðunni, munum við hafa 67 kóðaðar línur og samsvarandi rætur merkle trésins þannig að það eru að minnsta kosti 67 þátttakendur (ekki endilega þeir sömu og lögðu til samsvarandi línur), sem fyrir hverja af 67 línum hafa skilaboð með hlutdeild í eyðingarkóðanum og sönnun þess að hlutdeild þeirra í samsvarandi tré hafi dofnað.

Þegar þátttakandi í skrefi (4) leysir 67 slög fyrir ákveðinn streng og reynir að endurgera upprunalega strenginn úr þeim, er einn af valkostunum mögulegur:

1. Strenginn er endurheimtur og ef hann er síðan þurrkaður aftur og Merkle tréð er reiknað fyrir staðbundið reiknað hlutfall, fellur rótin saman við þá sem samstaða náðist um.

2. Röðin er endurreist, en staðbundin rót samsvarar ekki þeirri sem samstaða náðist um.

3. Röðin er ekki endurreist.

Það er auðvelt að sýna fram á að ef valkostur (1) átti sér stað fyrir að minnsta kosti einn þátttakanda hér að ofan, þá gerðist valmöguleiki (1) fyrir alla þátttakendur, og öfugt, ef valkostur (2) eða (3) átti sér stað fyrir að minnsta kosti einn þátttakanda, þá fyrir alla þátttakendur mun valkostur (2) eða (3) gerast. Þannig, fyrir hverja röð í settinu, munu annað hvort allir þátttakendur endurheimta hana, eða allir þátttakendur munu ekki endurheimta hana. Slembitalan sem myndast er þá XOR fyrir aðeins þær línur sem þátttakendur gátu endurheimt.

Þröskuldar undirskriftir

Önnur nálgun á handahófi er að nota það sem kallast BLS þröskuldsmerki. Handahófsnúmeraframleiðandi sem byggir á þröskuldsundirskriftum hefur nákvæmlega sömu tryggingar og reikniritið sem byggir á eyðingarkóða sem lýst er hér að ofan, en hefur verulega lægri einkennalausan fjölda skilaboða sem send eru yfir netið fyrir hverja myndaða tölu.

BLS undirskriftir eru hönnun sem gerir mörgum þátttakendum kleift að búa til eina sameiginlega undirskrift fyrir skilaboð. Þessar undirskriftir eru oft notaðar til að spara pláss og bandbreidd með því að þurfa ekki að senda margar undirskriftir út. 

Algengt forrit fyrir BLS undirskriftir í blockchain samskiptareglum, auk þess að búa til handahófskenndar tölur, er blokkarundirskrift í BFT samskiptareglum. Segjum að 100 þátttakendur búi til blokkir og blokk telst endanleg ef 67 þeirra skrifa undir. Þeir geta allir sent inn hluta sína af BLS undirskriftinni og notað einhverja samstöðu reiknirit til að koma sér saman um 67 þeirra og sameina þá í eina BLS undirskrift. Hægt er að nota hvaða 67 (eða fleiri) hluta sem er til að búa til endanlega undirskriftina, sem fer eftir því hvaða 67 undirskriftir voru sameinaðar og getur því verið breytilegt, þó mismunandi val 67 þátttakenda muni búa til aðra undirskrift, þá mun öll slík undirskrift vera gild undirskrift fyrir blokkina. Þátttakendur sem eftir eru þurfa þá aðeins að fá og sannreyna eina undirskrift á hverri blokk, í stað 67, yfir netið, sem dregur verulega úr álagi á netið.

Það kemur í ljós að ef einkalyklarnir sem þátttakendur nota eru búnir til á ákveðinn hátt, þá er sama hvaða 67 undirskriftir (eða fleiri, en ekki færri) eru samanlagðar, verður undirskriftin sú sama. Þetta er hægt að nota sem uppspretta handahófs: þátttakendur eru fyrst sammála um einhver skilaboð sem þeir munu skrifa undir (þetta gæti verið úttak RANDAO eða bara kjötkássa síðasta blokk, það skiptir ekki máli svo lengi sem það breytist í hvert skipti og er í samræmi) og búðu til BLS undirskrift fyrir það. Niðurstaða kynslóðarinnar verður ófyrirsjáanleg þar til 67 þátttakendur leggja fram hluta sína, og eftir það er framleiðslan þegar fyrirfram ákveðin og getur ekki verið háð aðgerðum nokkurs þátttakanda.

Þessi nálgun á handahófi er raunhæf svo lengi sem að minnsta kosti ⅔ þátttakenda á netinu fylgja bæði siðareglunum og er óhlutdræg og ófyrirsjáanleg svo framarlega sem að minnsta kosti ⅓ þátttakenda fylgja siðareglunum. Það er mikilvægt að hafa í huga að árásarmaður sem stjórnar meira en ⅓ en færri en ⅔ þátttakenda getur stöðvað samskiptaregluna, en getur ekki spáð fyrir um eða haft áhrif á framleiðslu hennar.

Þröskuldarundirskriftir sjálfar eru mjög áhugavert efni. Í seinni hluta greinarinnar munum við greina ítarlega hvernig þeir virka, og hvernig nákvæmlega það er nauðsynlegt að búa til þátttakendalykla svo hægt sé að nota þröskuldaundirskrift sem slembitölugjafa.

Að lokum

Þessi grein er sú fyrsta í röð tæknilegra blogggreina NEAR. NEAR er blockchain siðareglur og vettvangur til að þróa dreifð forrit með áherslu á auðveld þróun og auðvelda notkun fyrir notendur.

Samskiptakóðinn er opinn, útfærslan okkar er skrifuð í Rust, það er hægt að finna hann hér.

Þú getur séð hvernig þróun fyrir NEAR lítur út og gert tilraunir í IDE á netinu hér.

Þú getur fylgst með öllum fréttum á rússnesku á símskeyti hópur og hópur á VKontakte, og á ensku í opinberu kvak.

Sjáumst bráðlega!

Heimild: www.habr.com