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

Hæ Habr!

В fyrsti hluti Í þessari grein ræddum við hvers vegna það gæti verið nauðsynlegt að búa til slembitölur fyrir þátttakendur sem treysta ekki hver öðrum, hvaða kröfur eru settar fram til slíkra slembitölugjafa og litum á tvær aðferðir við útfærslu þeirra.

Í þessum hluta greinarinnar munum við skoða nánar aðra nálgun sem notar þröskuldarundirskriftir.

Smá dulmál

Til þess að skilja hvernig þröskuldarundirskriftir virka þarftu að skilja smá grunn dulmál. Við munum nota tvö hugtök: scalar, eða einfaldlega tölur, sem við munum tákna með lágstöfum (x, y) og punktar á sporöskjulaga ferlinum, sem við munum tákna með hástöfum.

Til að skilja grunnatriði þröskuldaundirskrifta þarftu ekki að skilja hvernig sporöskjulaga ferlar virka, annað en nokkur grundvallaratriði:

1. Hægt er að bæta við punktum á sporöskjulaga feril og margfalda með stigstærð (við munum tákna margföldun með stigstærð sem xG, þó nótur Gx einnig oft notað í bókmenntum). Niðurstaða samlagningar og margföldunar með kvarða er punktur á sporöskjulaga feril.

2. Að vita aðeins tilganginn G og vara þess með mælikvarða xG ekki hægt að reikna út x.

Við munum einnig nota hugtakið margliðu p (x) gráðu k-1. Sérstaklega munum við nota eftirfarandi eiginleika margliða: ef við vitum gildið p (x) fyrir hvaða k mismunandi x (og við höfum engar frekari upplýsingar um p (x)), getum við reiknað út p (x) fyrir hvern annan x.

Það er áhugavert að fyrir hvaða margliðu sem er p (x) og einhver punktur á ferlinum Gað vita merkinguna p(x)G fyrir hvaða k mismunandi merkingar x, við getum líka reiknað út p(x)G fyrir hvaða x.

Þetta eru nægar upplýsingar til að grafast fyrir um hvernig þröskuldarundirskriftir virka og hvernig á að nota þær til að búa til handahófskenndar tölur.

Tilviljunarkennd númeraframleiðandi á þröskuldsundirskriftum

Við skulum segja það n þátttakendur vilja búa til handahófskennda tölu og við viljum að allir taki þátt k það var nóg af þeim til að búa til fjölda, en svo að árásarmennirnir sem stjórna k-1 eða færri þátttakendur gátu ekki spáð fyrir um eða haft áhrif á fjöldann sem myndaðist.

Segjum sem svo að það sé til slík margliða p (x) gráðu k-1 það sem fyrsti þátttakandi veit bls (1), sá seinni veit p(2), og svo framvegis (n-það veit p(n)). Við gerum líka ráð fyrir því að einhverju fyrirfram ákveðnu atriði G allir vita p(x)G fyrir öll gildi x. Við munum hringja p(i) „einkahluti“ iþátttakandi (vegna þess að aðeins iþátttakandi þekkir hana), og p(i)G „opinber hluti“ iþátttakandi (vegna þess að allir þátttakendur þekkja hana). Eins og þú manst, þekking p(i)G ekki nóg til að endurheimta p(i).

Að búa til svona margliðu þannig að aðeins i-Fyrsti þátttakandinn og enginn annar þekkti einkahlutann hans - þetta er flóknasti og áhugaverðasti hluti bókunarinnar og við munum greina hann hér að neðan. Í bili skulum við gera ráð fyrir að við höfum slíka margliðu og allir þátttakendur þekkja einkahlutana sína.

Hvernig getum við notað slíka margliðu til að búa til handahófskennda tölu? Til að byrja með þurfum við einhvern streng sem hefur ekki áður verið notaður sem inntak í rafalinn. Ef um blockchain er að ræða, kjötkássa síðustu blokkarinnar h er góður kandídat fyrir slíka línu. Leyfðu þátttakendum að búa til slembitölu með því að nota h eins og fræ. Þátttakendur breyta fyrst h að punkti á ferlinum með hvaða forskilgreindu falli sem er:

H = scalarToPoint(h)

Síðan hver þátttakandi i reiknar út og gefur út Hæ = p(i)H, hvað geta þeir gert vegna þess að þeir vita p(i) og H. Upplýsingagjöf Hég leyfi ekki öðrum þátttakendum að endurheimta einkahlutann iþátttakanda og því er hægt að nota eitt sett af einkahlutum frá blokk til blokk. Þannig þarf aðeins að keyra dýra margliða kynslóðaralgrímið sem lýst er hér að neðan einu sinni.

Þegar k þátttakendur voru krufnir Hæ = p(i)H, allir geta reiknað út Hx = p(x)H fyrir alla x þökk sé eiginleikum margliða sem við ræddum í síðasta kafla. Á þessari stundu reikna allir þátttakendur H0 = p(0)H, og þetta er slembitalan sem fæst. Athugið að enginn veit p(0), og því eina leiðin til að reikna p(0)H – þetta er innskot p(x)H, sem er aðeins hægt þegar k gildi p(i)H þekkt. Opnun hvaða minna magn sem er p(i)H veitir engar upplýsingar um p(0)H.

Rafallinn hér að ofan hefur alla eiginleika sem við viljum: árásarmenn stjórna eingöngu k-1 þátttakendur eða færri hafa engar upplýsingar eða áhrif á niðurstöðuna á meðan einhver k þátttakendur geta reiknað út fjölda, og hvaða hlutmengi af k þátttakendur munu alltaf komast að sömu niðurstöðu fyrir sama fræ.

Það er eitt vandamál sem við forðumst vandlega hér að ofan. Til að innskot virki er mikilvægt að gildi Hi sem var gefið út af hverjum þátttakanda i það var í rauninni það sama p(i)H. Þar sem enginn nema i-þátttakandi veit það ekki p(i), enginn nema i-þátttakandi getur ekki staðfest það Hi raunverulega reiknað rétt, og án nokkurrar dulmálssönnunar um réttmæti Hég árásarmaður getur birt hvaða gildi sem er Hæ, og hafa geðþótta áhrif á úttak slembitölugjafans:

Mismunandi gildi H_1 send af fyrsta þátttakanda leiða til mismunandi H_0

Það eru að minnsta kosti tvær leiðir til að sanna réttmæti Hi, við munum íhuga þau eftir að við greinum myndun margliðunnar.

Margliða kynslóð

Í síðasta kafla gerðum við ráð fyrir að við höfum slíka margliðu p (x) gráðu k-1 að þátttakandinn i veit p(i), og enginn annar hefur neinar upplýsingar um þetta gildi. Í næsta kafla munum við líka þurfa það fyrir einhvern fyrirfram ákveðinn punkt G allir vissu p(x)G fyrir alla x.

Í þessum hluta munum við gera ráð fyrir að hver þátttakandi á staðnum hafi einhvern einkalykil xi, þannig að allir þekki samsvarandi almenningslykil Xi.

Ein möguleg margliða kynslóðaraðferð er sem hér segir:

1. Hver þátttakandi i staðbundið býr til handahófskennda margliðu pi(x) gráðu k-1. Þeir senda síðan hvern þátttakanda j значение pi(j), dulkóðuð með almennum lykli Xj. Þannig aðeins i-th и j-th þátttakandi veit pi(j). Þátttakandi i tilkynnir einnig opinberlega pi(j)G fyrir alla j frá 1 í k innifalið.

2. Allir þátttakendur nota einhverja samstöðu til að velja k þátttakendur þar sem margliður verða notaðar. Þar sem sumir þátttakendur gætu verið án nettengingar getum við ekki beðið þar til allir n þátttakendur munu birta margliður. Niðurstaðan af þessu skrefi er sett Z sem samanstendur af amk k margliður búnar til í skrefi (1).

3. Þátttakendur ganga úr skugga um að þau gildi sem þeir þekkja pi(j) samsvara opinberlega tilkynnt pi(j)G. Eftir þetta skref inn Z aðeins margliður sem sendar eru einkaskilaboðum pi(j) samsvara opinberlega tilkynnt pi(j)G.

4. Hver þátttakandi j reiknar út einkahluta sinn p(j) sem summa pi(j) fyrir alla i в Z. Hver þátttakandi reiknar einnig út öll gildi p(x)G sem summa pi(x)G fyrir allt i в Z.

takið eftir því p(x) – það er í raun margliða k-1, því það er summa einstaklingsins pi(x), sem hvert um sig er margliður gráðu k-1. Athugaðu síðan að á meðan hver þátttakandi j veit p(j), þeir hafa engar upplýsingar um p (x) í x ≠ j. Reyndar, til að reikna þetta gildi, þurfa þeir að vita allt pí(x), og svo lengi sem þátttakandi j þekkir ekki að minnsta kosti eina af völdum margliðunum, þær hafa ekki nægjanlegar upplýsingar um p(x).

Þetta er allt margliða kynslóðarferlið sem þurfti í síðasta kafla. Skref 1, 2 og 4 hér að ofan hafa nokkuð augljósa útfærslu. En skref 3 er ekki svo léttvægt.

Nánar tiltekið þurfum við að geta sannað það dulkóðað pi(j) samsvara raunverulega þeim sem birtar eru pi(j)G. Ef við getum ekki sannað það, árásarmaðurinn i gæti sent sorp í staðinn pi(j) til þátttakanda j, og þátttakandi j mun ekki geta fengið raunverulegt verðmæti pí(j), og mun ekki geta reiknað út einkahluta sinn.

Það er til dulmálssamskiptareglur sem gerir þér kleift að búa til viðbótarskilaboð sönnuni(j), þannig að hver þátttakandi, sem hefur eitthvað gildi e, svo og proofi(j) и pi(j)G, getur staðreynt það e - það er virkilega pí(j), dulkóðuð með lykli þátttakanda j. Því miður er umfang slíkra sönnunargagna ótrúlega stór, og í ljósi þess að það er nauðsynlegt að birta O(nk) Ekki er hægt að nota slík sönnunargögn í þessu skyni.

Í stað þess að sanna það pí(j) соответствует pi(j)G við getum úthlutað mjög löngum tíma í margliða kynslóðarsamskiptareglunni, þar sem allir þátttakendur athuga móttekið dulkóðaða pí(j), og ef afkóðuðu skilaboðin samsvara ekki almenningi pi(j)G, þeir birta dulmálssönnun fyrir því að dulkóðuðu skilaboðin sem þeir fengu séu röng. Sannaðu að skilaboðin ekki соответствует pi(G) miklu auðveldara en að sanna að það passi. Það skal tekið fram að þetta krefst þess að hver þátttakandi birtist á netinu að minnsta kosti einu sinni á þeim tíma sem úthlutað er til að búa til slík sönnunargögn og byggir á þeirri forsendu að ef þeir birta slíka sönnun muni hún ná til allra annarra þátttakenda á sama tíma.

Ef þátttakandi kom ekki fram á netinu á þessu tímabili, og hann var með að minnsta kosti einn rangan þátt, þá mun sá þátttakandi ekki geta tekið þátt í frekari númeragerð. Samskiptareglan mun þó enn virka ef það er amk k þátttakendur sem annaðhvort fengu rétta hluti eða náðu að skilja eftir sönnun um ranglæti innan tiltekins tíma.

Sannanir um réttmæti H_i

Síðasti hlutinn sem á eftir að ræða er hvernig á að sanna réttmæti birtingar Hég, nefnilega það Hæ = p(i)H, án þess að opna p(i).

Við skulum muna að gildin H, G, p(i)G opinbert og öllum kunnugt. Tekið á móti aðgerð p(i) vitandi p(i)G и G kallaður stakur logaritmi, eða hundur, og við viljum sanna að:

dlog(p(i)G, G) = dlog(Hi, H)

án birtingar p(i). Framkvæmdir fyrir slíkar sannanir eru til, til dæmis Schnorr bókun.

Með þessari hönnun, hver þátttakandi, ásamt Hi sendir sönnun um réttmæti samkvæmt hönnun.

Þegar tilviljunarkennd tala er búin til þarf hún oft að vera notuð af öðrum þátttakendum en þeim sem mynduðu hana. Slíkir þátttakendur, ásamt númerinu, verða að senda alla Hi og tengd sönnunargögn.

Forvitinn lesandi gæti spurt: þar sem endanleg slembitala er H0, og p(0)G – Þetta eru opinberar upplýsingar, hvers vegna þurfum við sannanir fyrir hvern einstakling Hég, af hverju ekki að senda sönnun þess í staðinn

dlog(p(0)G, G) = dlog(H0, H)

Vandamálið er að slík sönnun er ekki hægt að búa til með því að nota Schnorr-bókunina vegna þess að enginn veit gildið bls (0), nauðsynlegt til að búa til sönnunina, og það sem meira er, allur slembitölugeneratorinn byggist á því að enginn veit þetta gildi. Þess vegna er nauðsynlegt að hafa öll gildi Hi og einstök sönnunargögn þeirra til að sanna réttmæti H0.

Hins vegar, ef það væri einhver aðgerð á punktum á sporöskjulaga ferlum sem er merkingarlega svipuð margföldun, sönnunin um réttmæti H0 væri léttvægt, við myndum einfaldlega tryggja það

H0 × G = p(0)G × H

Ef valinn ferill styður sporöskjulaga ferilapörun, þessi sönnun virkar. Í þessu tilfelli H0 er ekki aðeins úttak slembitöluframleiðanda, sem allir þátttakendur sem þekkja geta staðfest G, H и p(0)G. H0 er líka undirskrift á skeytinu sem var notað sem fræ, sem staðfestir það k и n þátttakendur skrifuðu undir þetta skeyti. Þannig, ef fræ - er kjötkássa blokkarinnar í blockchain samskiptareglunum, þá H0 er bæði fjölundirskrift á blokk og mjög góð slembitala.

Að lokum

Þessi grein er hluti af tæknilegri bloggseríu 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