Je, inawezekana kutengeneza nambari nasibu ikiwa hatuaminiani? Sehemu 2

Habari Habr!

В sehemu ya kwanza Katika nakala hii, tulijadili kwa nini inaweza kuwa muhimu kutoa nambari nasibu kwa washiriki ambao hawaaminiani, ni mahitaji gani yanayowekwa kwa jenereta za nambari bila mpangilio, na tukazingatia njia mbili za utekelezaji wao.

Katika sehemu hii ya makala, tutaangalia kwa karibu mbinu nyingine inayotumia saini za kizingiti.

Kidogo cha cryptography

Ili kuelewa jinsi saini za kizingiti zinavyofanya kazi, unahitaji kuelewa kriptografia ya msingi kidogo. Tutatumia dhana mbili: scalar, au nambari tu, ambazo tutaashiria kwa herufi ndogo (x, y) na pointi kwenye mviringo wa mviringo, ambayo tutaashiria kwa herufi kubwa.

Ili kuelewa misingi ya saini za kizingiti, huhitaji kuelewa jinsi miindo ya duaradufu inavyofanya kazi, isipokuwa mambo machache ya msingi:

1. Pointi kwenye kiwiko cha duaradufu zinaweza kuongezwa na kuzidishwa na kola (tutaashiria kuzidisha kwa kola kama xG, ingawa nukuu Gx pia hutumiwa mara nyingi katika fasihi). Matokeo ya kuongeza na kuzidisha kwa scalar ni hatua kwenye mviringo wa mviringo.

2. Kujua point tu G na bidhaa yake na scalar xG haiwezi kuhesabiwa x.

Pia tutatumia dhana ya polynomial p(x) digrii k-1. Hasa, tutatumia mali ifuatayo ya polynomials: ikiwa tunajua thamani p(x) kwa yoyote k tofauti x (na hatuna habari zaidi kuhusu p(x)), tunaweza kuhesabu p(x) kwa mtu mwingine yeyote x.

Inafurahisha kwamba kwa polynomial yoyote p(x) na hatua fulani kwenye curve Gkujua maana p(x)G kwa yoyote k maana tofauti x, tunaweza pia kuhesabu p(x)G kwa yoyote x.

Haya ni maelezo ya kutosha kuchimba katika maelezo ya jinsi sahihi za kizingiti zinavyofanya kazi na jinsi ya kuzitumia kuzalisha nambari nasibu.

Jenereta ya nambari bila mpangilio kwenye saini za kizingiti

Hebu tuseme hivyo n washiriki wanataka kutoa nambari nasibu, na tunataka mtu yeyote ashiriki k kulikuwa na kutosha wao kuzalisha idadi, lakini ili washambuliaji ambao kudhibiti k-1 au wachache washiriki hawakuweza kutabiri au kuathiri idadi iliyozalishwa.

Tuseme kuna polynomial kama hiyo p(x) digrii k-1 kile mshiriki wa kwanza anajua p (1), wa pili anajua p(2), Nakadhalika (n-inajua p(n)) Sisi pia kudhani kwamba kwa baadhi ya uhakika predetermined G kila mtu anajua p(x)G kwa maadili yote x. Tutapiga simu p(i) "sehemu ya kibinafsi" imshiriki (kwa sababu tu imshiriki anamjua), na p(i)G "sehemu ya umma" i-mshiriki (kwa sababu washiriki wote wanamjua). Kama unavyokumbuka, maarifa p(i)G haitoshi kurejesha p (i).

Kuunda polynomial kama hiyo ili tu i-Mshiriki wa kwanza na hakuna mtu mwingine aliyejua sehemu yake ya kibinafsi - hii ni sehemu ngumu zaidi na ya kuvutia ya itifaki, na tutachambua hapa chini. Kwa sasa, hebu tuchukulie kwamba tuna polynomial kama hiyo na washiriki wote wanajua vipengele vyao vya kibinafsi.

Tunawezaje kutumia polynomial kama hii kutoa nambari nasibu? Kuanza, tunahitaji kamba ambayo haijawahi kutumika kama pembejeo kwa jenereta. Katika kesi ya blockchain, heshi ya block ya mwisho h ni mgombea mzuri kwa safu kama hiyo. Waruhusu washiriki kutaka kuunda nambari nasibu kwa kutumia h kama mbegu. Washiriki hubadilisha kwanza h kwa uhakika kwenye curve kwa kutumia kazi yoyote iliyoainishwa awali:

H = scalarToPoint(h)

Kisha kila mshiriki i huhesabu na kuchapisha Hi = p(i)H, wanaweza kufanya nini kwa sababu wanajua p (i) na H. Ufichuzi Hsiruhusu washiriki wengine kurejesha sehemu ya kibinafsi imshiriki, na kwa hivyo seti moja ya vifaa vya kibinafsi inaweza kutumika kutoka kizuizi hadi kizuizi. Kwa hivyo, algorithm ya gharama kubwa ya kizazi cha polynomial iliyoelezwa hapa chini inahitaji tu kutekelezwa mara moja.

Wakati k washiriki walikuwa autopsy Hi = p(i)H, kila mtu anaweza kuhesabu Hx = p(x)H kwa wote x shukrani kwa mali ya polynomials ambayo tulijadili katika sehemu iliyopita. Kwa wakati huu, washiriki wote wanahesabu H0 = p(0)H, na hii ndio nambari inayotokana na nasibu. Tafadhali kumbuka kuwa hakuna mtu anayejua p(0), na kwa hivyo njia pekee ya kuhesabu p(0)H - hii ni tafsiri p(x)H, ambayo inawezekana tu wakati k maadili p(i)H inayojulikana. Kufungua kiasi chochote kidogo p(i)H haitoi habari yoyote kuhusu p(0)H.

Jenereta iliyo hapo juu ina sifa zote tunazotaka: washambuliaji wanaodhibiti pekee k-Washiriki 1 au chini hawana habari au ushawishi kwenye hitimisho, wakati wowote k washiriki wanaweza kukokotoa nambari inayotokana, na kikundi chochote cha k washiriki daima watakuja kwa matokeo sawa kwa mbegu sawa.

Kuna shida moja ambayo tuliepuka kwa uangalifu hapo juu. Kwa tafsiri kufanya kazi, ni muhimu kwamba thamani Hi ambayo ilichapishwa na kila mshiriki i kweli ilikuwa sawa p(i)H. Kwa kuwa hakuna mtu isipokuwa i- mshiriki hajui p (i), hakuna mtu isipokuwa i-mshiriki hawezi kuthibitisha hilo Hi kweli imehesabiwa kwa usahihi, na bila uthibitisho wowote wa usahihi wa kriptografia Hi mshambulizi anaweza kuchapisha thamani yoyote kama Hi, na kuathiri kiholela utoaji wa jenereta ya nambari nasibu:

Thamani tofauti za H_1 zilizotumwa na mshiriki wa kwanza husababisha matokeo tofauti ya H_0

Kuna angalau njia mbili za kuthibitisha usahihi Hi, tutazingatia baada ya kuchambua kizazi cha polynomial.

Kizazi cha polynomial

Katika sehemu ya mwisho tulidhani kwamba tuna polynomial kama hiyo p(x) digrii k-1 kwamba mshiriki i anajua p(i), na hakuna mtu mwingine aliye na taarifa yoyote kuhusu thamani hii. Katika sehemu inayofuata tutahitaji hiyo pia kwa nukta fulani iliyoamuliwa mapema G kila mtu alijua p(x)G kwa wote x.

Katika sehemu hii tutachukulia kwamba kila mshiriki ndani ya nchi ana ufunguo fulani wa faragha Xi, ili kila mtu ajue ufunguo unaolingana wa umma Xi.

Itifaki moja inayowezekana ya kizazi cha polynomial ni kama ifuatavyo.

1. Kila mshiriki i ndani inaunda polynomial kiholela pi(x) digrii k-1. Kisha wanatuma kila mshiriki j thamani pi(j), iliyosimbwa kwa ufunguo wa umma Xj. Hivyo tu i-y и j-y mshiriki anajua pmimi (j). Mshiriki i pia hutangaza hadharani pi(j)G kwa wote j kutoka 1 kwa k pamoja.

2. Washiriki wote hutumia baadhi ya makubaliano kuchagua k washiriki ambao polynomia zao zitatumika. Kwa kuwa baadhi ya washiriki wanaweza kuwa nje ya mtandao, hatuwezi kusubiri hadi kila mtu n washiriki watachapisha polynomials. Matokeo ya hatua hii ni seti Z inayojumuisha angalau k polynomials iliyoundwa katika hatua (1).

3. Washiriki wanahakikisha kuwa maadili wanayoyajua pi(j) zinalingana na zilizotangazwa hadharani pi(j)G. Baada ya hatua hii Z polynomials pekee ambazo zinapitishwa kwa faragha pi(j) zinalingana na zilizotangazwa hadharani pi(j)G.

4. Kila mshiriki j huhesabu sehemu yake ya kibinafsi p(j) kama jumla pi(j) kwa wote i в Z. Kila mshiriki pia anahesabu thamani zote p(x)G kama jumla pi(x)G kwa wote i в Z.

Tafadhali kumbuka kuwa p(x) - ni polynomial kweli k-1, kwa sababu ni jumla ya mtu binafsi pi(x), ambayo kila moja ni polynomial ya shahada k-1. Kisha, kumbuka kwamba wakati kila mshiriki j anajua p (j), hawana habari nayo p(x) kwa x ≠ j. Hakika, kuhesabu thamani hii, wanahitaji kujua kila kitu pi(x), na kwa muda mrefu kama mshiriki j hajui angalau moja ya polynomials zilizochaguliwa, hawana taarifa za kutosha kuhusu p (x).

Huu ndio mchakato mzima wa uzalishaji wa polinomia ambao ulihitajika katika sehemu ya mwisho. Hatua za 1, 2 na 4 hapo juu zina utekelezaji wa wazi kabisa. Lakini hatua ya 3 sio ndogo sana.

Hasa, tunahitaji kuwa na uwezo wa kuthibitisha kwamba usimbaji fiche pi(j) inalingana kabisa na zile zilizochapishwa pi(j)G. Ikiwa hatuwezi kuthibitisha, mshambuliaji i inaweza kutuma taka badala yake pi(j) kwa mshiriki j, na mshiriki j hutaweza kupata maana halisi pi(j), na haitaweza kukokotoa sehemu yake ya kibinafsi.

Kuna itifaki ya kriptografia ambayo hukuruhusu kuunda ujumbe wa ziada ushahidii(j), ili kwamba mshiriki yeyote, awe na thamani fulani e, na pia ushahidi(j) и pi(j)G, inaweza kuthibitisha hilo ndani ya nchi e - ni kweli pi(j), imesimbwa kwa ufunguo wa mshiriki j. Kwa bahati mbaya, ukubwa wa ushahidi kama huo ni mkubwa sana, na ikizingatiwa kuwa ni muhimu kuchapishwa O(nk) Ushahidi kama huo hauwezi kutumika kwa kusudi hili.

Badala ya kuthibitisha hilo pi(j) inafanana na pi(j)G tunaweza kutenga muda mrefu sana katika itifaki ya kizazi cha polynomial, ambapo washiriki wote hukagua iliyopokelewa kwa njia fiche. pi(j), na ikiwa ujumbe uliosimbwa haulingani na umma pi(j)G, wanachapisha uthibitisho wa siri kwamba ujumbe uliosimbwa waliopokea si sahihi. Thibitisha kuwa ujumbe huo hakuna inafanana na pi(G) rahisi zaidi kuliko kuthibitisha kwamba inafanana. Ikumbukwe kwamba hii inahitaji kila mshiriki kuonekana mtandaoni angalau mara moja katika muda uliopangwa kuunda ushahidi huo, na inategemea dhana kwamba ikiwa watachapisha uthibitisho huo, utawafikia washiriki wengine wote kwa wakati huo huo uliopangwa.

Ikiwa mshiriki hakuonekana mtandaoni katika kipindi hiki cha muda, na alikuwa na angalau sehemu moja isiyo sahihi, basi mshiriki huyo hataweza kushiriki katika uzalishaji zaidi wa nambari. Itifaki, hata hivyo, bado itafanya kazi ikiwa kuna angalau k washiriki ambao wamepokea tu vipengele sahihi au waliweza kuacha uthibitisho wa kutokuwa sahihi ndani ya muda uliopangwa.

Uthibitisho wa usahihi wa H_i

Sehemu ya mwisho ambayo inabaki kujadiliwa ni jinsi ya kudhibitisha usahihi wa kuchapishwa Hmimi, yaani Hi = p(i)H, bila kufungua p (i).

Tukumbuke kwamba maadili H, G, p(i)G hadharani na kujulikana kwa kila mtu. Pokea operesheni p(i) kujua p(i)G и G inayoitwa logarithm tupu, au dlog, na tunataka kuthibitisha kwamba:

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

bila kufichuliwa p(i). Ujenzi kwa uthibitisho kama huo upo, kwa mfano Itifaki ya Schnorr.

Kwa muundo huu, kila mshiriki, pamoja na Hi hutuma uthibitisho wa usahihi kulingana na muundo.

Nambari ya nasibu inapotolewa, mara nyingi inahitaji kutumiwa na washiriki isipokuwa wale walioiunda. Washiriki kama hao, pamoja na nambari, lazima watume wote Hi na ushahidi unaohusiana.

Msomaji mdadisi anaweza kuuliza: kwa kuwa nambari ya nasibu ya mwisho ni H0, na p(0)G - Hii ni habari ya umma, kwa nini tunahitaji ushahidi kwa kila mtu Hi, kwa nini usitume uthibitisho kwamba badala yake

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

Shida ni kwamba uthibitisho kama huo hauwezi kuunda kwa kutumia Itifaki ya Schnorr kwa sababu hakuna anayejua thamani p (0), muhimu ili kuunda uthibitisho, na nini zaidi, jenereta nzima ya nambari ya random inategemea ukweli kwamba hakuna mtu anayejua thamani hii. Kwa hiyo ni muhimu kuwa na maadili yote Hi na ushahidi wao binafsi kuthibitisha usahihi H0.

Walakini, ikiwa kulikuwa na operesheni fulani kwenye alama kwenye mikondo ya duaradufu ambayo inafanana kimaana na kuzidisha, uthibitisho wa usahihi. H0 ingekuwa ndogo, tungehakikisha hivyo

H0 × G = p(0)G × H

Ikiwa curve iliyochaguliwa inasaidia miunganisho ya mviringo wa mviringo, uthibitisho huu unafanya kazi. Kwa kesi hii H0 sio tu matokeo ya jenereta ya nambari nasibu, ambayo inaweza kuthibitishwa na mshiriki yeyote anayejua. G,H и p(0)G. H0 pia ni saini kwenye ujumbe ambao ulitumiwa kama mbegu, kuthibitisha hilo k и n washiriki walitia saini ujumbe huu. Kwa hivyo, ikiwa mbegu - ni heshi ya kizuizi kwenye itifaki ya blockchain, basi H0 ni saini nyingi kwenye kizuizi na nambari nzuri sana ya nasibu.

Kwa kumalizia

Makala haya ni sehemu ya mfululizo wa blogu za kiufundi PEKEE. KARIBU ni itifaki ya blockchain na jukwaa la kuunda programu zilizogatuliwa kwa msisitizo wa urahisi wa maendeleo na urahisi wa matumizi kwa watumiaji wa mwisho.

Nambari ya itifaki imefunguliwa, utekelezaji wetu umeandikwa katika Rust, inaweza kupatikana hapa.

Unaweza kuona jinsi maendeleo ya NEAR yanavyoonekana na ujaribu katika IDE ya mtandaoni hapa.

Unaweza kufuata habari zote kwa Kirusi kikundi cha telegraph na kikundi kwenye VKontakte, na kwa Kiingereza katika rasmi twitter.

Nitakuona hivi karibuni!

Chanzo: mapenzi.com