Hai Habr!
В A cikin wannan labarin, mun tattauna dalilin da ya sa zai zama dole don samar da lambobin bazuwar ga mahalarta waɗanda ba su amince da juna ba, menene buƙatun da aka gabatar don irin waɗannan masu samar da lambar bazuwar, kuma mun yi la'akari da hanyoyi biyu don aiwatar da su.
A cikin wannan ɓangaren labarin, za mu yi nazari sosai kan wata hanyar da ke amfani da sa hannun bakin kofa.
Kadan na cryptography
Don fahimtar yadda sa hannun bakin kofa ke aiki, muna buƙatar fahimtar ɗan ƙaramin tushe na asali. Za mu yi amfani da ra'ayoyi guda biyu: scalars, ko kawai lambobi, waɗanda za mu yi nuni da ƙananan haruffa (x, y) da kuma maki akan madaidaicin ellipse, wanda zamu yi nuni da babban haruffa.
Don fahimtar mahimman abubuwan sa hannu na bakin kofa, ba kwa buƙatar fahimtar yadda masu lanƙwasa ellipse ke aiki, ban da wasu abubuwa na asali:
Za'a iya ƙara maki akan lanƙwan elliptik kuma a ninka su ta hanyar sikeli (za mu nuna ninkawa ta hanyar sikeli kamar yadda. xG, kodayake abin lura Gx (kuma ana yawan amfani dashi a cikin adabi). Sakamakon ƙari da ninkawa ta hanyar sikeli shine aya akan lanƙwan ellipse.
Sanin batu kawai G da samfurinsa tare da scalar xG ba za a iya lissafta ba x.
Za mu kuma yi amfani da manufar polynomial p(x) digiri k-1. Musamman, za mu yi amfani da dukiya mai zuwa na polynomials: idan mun san darajar p(x) ga kowa k daban-daban x (kuma ba mu da ƙarin bayani game da p(x)), za mu iya lissafta p(x) ga wani x.
Yana da ban sha'awa cewa ga kowane polynomial p(x) da kuma wani batu a kan lankwasa G, sanin ma'anar p (x) G ga kowa k ma'anoni daban-daban x, Hakanan zaka iya lissafta p (x) G ga kowa x.
Wannan bayanin ya isa ya tona cikin cikakkun bayanai na yadda sa hannun bakin kofa ke aiki da yadda ake amfani da su don samar da lambobi bazuwar.
janareta na bazuwar lamba bisa sa hannun bakin kofa
Bari mu ɗauka cewa n mahalarta suna son samar da lambar bazuwar, kuma muna son kowa ya shiga k daga cikinsu akwai isassu don samar da lamba, amma ga maharan da ke iko kMahalarta 1 ko ƙasa da haka ba za su iya yin hasashen ko tasiri lambar da aka ƙirƙira ba.
Bari mu ɗauka cewa akwai irin wannan polynomial p(x) digiri k-1, abin da mahalarta na farko ya sani p(1), na biyu ya sani p(2), da sauransu (n- ya sani p(n)). Bari mu kuma ɗauka cewa don wani ƙayyadadden batu G kowa ya sani p (x) G ga dukkan dabi'u xZa mu kira p(i) "bangaren sirri" i- Mahalarta ta (saboda kawai i- Mahalarta ta san ta), kuma p (i) G "bangaren jama'a" iMahalarta th (saboda duk mahalarta sun san shi). Kamar yadda kuke tunawa, ilimi p (i) G bai isa ya dawo ba p(i).
Ƙirƙirar irin wannan polynomial don haka kawai i-Mahalarta ta uku kuma babu wanda ya san abubuwan sirrinsu - wannan shine mafi rikitarwa kuma sashi mai ban sha'awa na yarjejeniya, kuma zamu tattauna ta a ƙasa. A yanzu, bari mu ɗauka muna da irin wannan nau'in nau'i-nau'i, kuma duk mahalarta sun san abubuwan sirrinsu.
Ta yaya za mu yi amfani da irin wannan polynomial don samar da lambar bazuwar? Da farko, muna buƙatar zaren da ba a yi amfani da shi azaman shigar da janareta a baya ba. A cikin yanayin blockchain, zanta na sabon toshe h - shi ne mai kyau dan takara ga irin wannan kirtani. Bari mahalarta su so su samar da lambar bazuwar ta amfani da su h a matsayin iri. Mahalarta sun fara tuba h zuwa wani batu akan lanƙwasa ta amfani da kowane aikin da aka riga aka ƙayyade:
H = scalarToPoint(h)
Sai kowane mahaluki i lissafta da bugawa Hi = p(i)H, abin da za su iya yi saboda sun sani p(i) da H. Bayyanawa Hban ƙyale sauran mahalarta su dawo da abubuwan sirri ba i- Mahalarta th, sabili da haka ana iya amfani da nau'ikan nau'ikan abubuwan sirri guda ɗaya daga toshe zuwa toshe. Don haka, ƙayyadaddun ƙayyadaddun ƙayyadaddun ƙayyadaddun ƙira da aka kwatanta a ƙasa yana buƙatar aiwatar da sau ɗaya kawai.
Lokacin k an fallasa mahalarta taron Hi = p(i)H, kowa zai iya gane shi Hx = ba p (x) H domin duka x godiya ga dukiyar polynomials da muka tattauna a cikin sashin da ya gabata. A wannan gaba, duk mahalarta suna lissafin H0 = p(0)H, kuma wannan shine sakamakon bazuwar lamba. Lura cewa babu wanda ya sani p(0), sabili da haka hanya daya tilo ta kirga p (0) H- wannan interpolation ne p (x) H, wanda zai yiwu ne kawai lokacin da k dabi'u p (i) H sani. Bude kowane ƙaramin adadi p (i) H ba ya bayar da wani bayani game da p(0)H.
Janareta na sama yana da duk kaddarorin da muke so: maharan suna sarrafa kawai k-Mahalarta 1 ko ƙasa da haka ba su da wani bayani da tasiri akan ƙarshe, yayin da kowane k mahalarta zasu iya lissafin sakamakon lambar, da kowane ɓangaren k mahalarta koyaushe za su zo ga sakamako iri ɗaya don iri ɗaya.
Akwai matsala daya da muka kauce a hankali a sama. Don interpolation don aiki, yana da mahimmanci cewa ƙimar Hkuma wanda kowane ɗan takara ya buga i daidai yake da gaske p (i) H. Tunda babu kowa i- Mahalarci bai sani ba p(i), ba kowa sai i-Mahalarcin ba zai iya tabbatar da hakan ba Hi a haƙiƙa an ƙididdige shi daidai, kuma ba tare da wata hujja ta sirri ba Hi mai hari na iya buga kowace ƙima kamar Hi, kuma suna yin tasiri ga fitowar janareta na lambar bazuwar:
Daban-daban dabi'u na H_1 wanda mahalarta na farko ya aiko suna haifar da sakamako daban-daban na H_0
Akwai aƙalla hanyoyi biyu don tabbatar da daidaito Hi, za mu yi la'akari da su bayan mun yi nazarin ƙarni na polynomial.
Yawancin tsararraki
A cikin sashe na ƙarshe mun ɗauka cewa muna da irin wannan polynomial p(x) digiri k-1 me takara i sani p(i), kuma babu wanda ke da wani bayani game da wannan darajar. A cikin sashe na gaba, za mu kuma buƙaci hakan don wani ƙayyadadden batu G kowa ya sani p (x) G domin duka x.
A cikin wannan sashe, za mu ɗauka cewa kowane ɗan takara yana da wasu maɓalli na sirri na gida xi, kamar yadda kowa ya san maɓalli na jama'a daidai Xi.
Ɗaya mai yuwuwar ƙa'idar tsarar ɗabi'a ita ce kamar haka:
Kowane ɗan takara i a cikin gida yana haifar da yawan sabani pi(x) na digiri k-1. Sai su aika zuwa ga kowane ɗan takara j ma'ana pi(j), rufaffiyar tare da maɓallin jama'a Xj. Don haka kawai i-ый и j-ый dan takara ya sani pina (j). Mahalarta i kuma yana sanar da jama'a pi (j) G domin duka j daga 1 to k hada.
Duk mahalarta suna amfani da wasu yarjejeniya don zaɓar k mahalarta wadanda za a yi amfani da yawan adadinsu. Tun da wasu mahalarta suna iya yin layi, ba za mu iya jira har sai duka n Mahalarta za su buga polynomials. Sakamakon wannan mataki shine saiti Z wanda ya kunshi akalla k polynomials halitta a mataki (1).
Mahalarta sun tabbata cewa dabi'un da aka sani a gare su pi (j) daidai da sanar da jama'a pi (j) G. Bayan wannan mataki Z kawai nau'i-nau'i masu yawa waɗanda aka aika ta sirri pi (j) daidai da sanar da jama'a pi (j) G.
Kowane ɗan takara j yana kimanta abubuwan sirrinsa p(j) a matsayin jimla pi (j) ga kowa da kowa i в ZKowane ɗan takara kuma yana ƙididdige duk ƙimar p (x) G a matsayin jimla pi (x) G ga duk i в Z.
lura da cewa p(x) - wannan hakika babban digiri ne k-1, saboda jimlar mutum ce pi(x), kowanne daga cikinsu yana da nau'ikan digiri k-1. Sa'an nan, lura cewa yayin da kowane ɗan takara j sani p(j), ba su da wani bayani game da su p(x) to x ≠ jLallai, don ƙididdige wannan ƙimar, suna buƙatar sanin komai pi(x), da kuma yayin da mahalarta j bai san aƙalla ɗaya daga cikin zaɓaɓɓun polynomials ba, ba su da isasshen bayani game da su p(x).
Wannan shi ne gaba dayan tsarin samar da abubuwa da yawa da ake buƙata a sashin da ya gabata. Matakai na 1, 2, da 4 na sama suna da aiwatarwa madaidaiciya. Duk da haka, mataki na 3 ba shi da mahimmanci.
Musamman, muna buƙatar mu iya tabbatar da cewa rufaffen pi (j) yi daidai da waɗanda aka buga pi (j) G. Idan ba za mu iya tabbatar da shi ba, maharin i zai iya aika sharar maimakon pi (j) mahalarta j, kuma mahalarta j ba zai iya samun ainihin ma'anar ba pi (j), kuma ba zai iya lissafin abubuwan sirrinsa ba.
Akwai ƙa'idar cryptographic wanda ke ba ku damar ƙirƙirar ƙarin saƙo hujjai(j), kamar kowane ɗan takara, yana da ɗan ƙima e, da kuma hujja (j) и pi(j)G, na iya tabbatar da hakan a cikin gida e - yana da gaske pi (j), rufaffiyar tare da maɓallin mahalarta j. Abin takaici, girman irin waɗannan shaidun yana da girma da yawa, kuma an ba da cewa yana buƙatar buga shi O(nk) ba za a iya amfani da irin waɗannan shaidun don wannan dalili ba.
Maimakon tabbatar da hakan pi (j) соответствует pi(j) G za mu iya keɓance babban lokaci mai yawa a cikin ka'idar tsara tsarar jama'a, yayin da duk mahalarta ke bincika rufaffen da aka karɓa. pi (j), kuma idan saƙon da aka ɓoye bai dace da na jama'a ba pi(j)G, suna buga bayanan sirrin cewa saƙon da aka ɓoye ba daidai ba ne. Tabbatar da cewa sakon ba соответствует pi(G) Ya fi sauƙi fiye da tabbatar da cewa ya dace. Yana da kyau a lura cewa wannan yana buƙatar kowane ɗan takara ya bayyana a kan layi aƙalla sau ɗaya a cikin lokacin da aka ware don ƙirƙirar irin waɗannan hujjoji, kuma ya dogara da tsammanin cewa idan suka buga irin wannan hujja, zai isa ga duk sauran mahalarta a cikin lokaci guda.
Idan ɗan takara bai bayyana akan layi ba a wannan lokacin kuma yana da aƙalla sashi mara inganci, to waccan ɗan takarar ba zai iya shiga cikin ƙarin ƙirƙira lamba ba. Ƙa'idar, duk da haka, za ta ci gaba da aiki idan akwai aƙalla sashi mara aiki. k mahalarta waɗanda ko dai kawai sun sami daidaitattun abubuwan da aka gyara ko kuma sun sami damar barin shaidar rashin kuskure a cikin lokacin da aka ware.
Tabbatattun daidaito na H_i
Kashi na ƙarshe da ya rage don tattaunawa shine yadda za a tabbatar da daidaiton da aka buga Hi, wato haka Hi = p(i)H, ba tare da budewa ba p(i).
Bari mu tuna cewa dabi'u H, G, p(i) G jama'a kuma kowa ya sani. Karɓi aiki p(i) sani p (i) G и G ana kiranta da hankali logarithm, ko ganduje, kuma muna son tabbatar da cewa:
dlog (p(i)G, G) = dlog(Hi, H)
ba tare da bayyanawa ba p(i)Ana yin gine-gine don irin waɗannan hujjoji, alal misali.
Tare da wannan zane, kowane ɗan takara, tare da Hi aika da tabbacin daidai bisa ga ginin.
Da zarar an sami lambar bazuwar, sau da yawa tana buƙatar mahalarta su yi amfani da ita banda waɗanda suka ƙirƙira ta. Dole ne waɗannan mahalarta su aika duk bayanan da ake bukata tare da lambar. Hi da hujjoji masu rakiyar.
Mai karatu mai tambaya zai iya tambaya: tunda lambar bazuwar ta ƙarshe ita ce H0, kuma p(0) G - Wannan bayanin jama'a ne, me yasa muke buƙatar hujja ga kowane mutum? Hni, me zai hana a aika da hujja maimakon haka
ganga(p(0)G, G) = dlog(H0, H)
Matsalar ita ce ba za ku iya ƙirƙirar irin wannan hujja ta amfani da ka'idar Schnorr ba saboda babu wanda ya san darajar. p(0), wajibi ne don ƙirƙirar hujja, kuma haka ma, duk janareta na lambar bazuwar ya dogara ne akan gaskiyar cewa babu wanda ya san wannan darajar. Saboda haka, wajibi ne a sami dukkan dabi'u Hi da kuma shaidarsu guda ɗaya don tabbatar da daidaito H0.
Koyaya, idan akwai wasu aiki akan maki akan maɓallan elliptic waɗanda ke da kamanceceniya ta ma'ana da ninkawa, tabbacin daidaito. H0 zai zama maras muhimmanci, kawai za mu tabbatar da hakan
H0 × G = p(0)G × H
Idan zaɓaɓɓen lanƙwan yana goyan bayan , wannan hujja tana aiki. A wannan yanayin H0 ba kawai fitowar janareta na lamba ba ne wanda kowane ɗan takara da ya sani zai iya tantance shi G, H и p (0) G.H0 kuma shine sa hannun saƙon da aka yi amfani da shi azaman iri, yana tabbatar da hakan k и n mahalarta sun sanya hannu kan wannan sakon. Don haka, idan iri - Wannan shine hash na toshe a cikin ka'idar blockchain, to H0 - wannan duka sa hannu ne da yawa akan toshe kuma lambar bazuwar mai kyau ce.
A ƙarshe
Wannan labarin wani bangare ne na jerin bulogi na fasaha. NEAR ƙa'idar blockchain ce da dandamali don haɓaka aikace-aikacen da ba a daidaita su tare da mai da hankali kan sauƙin haɓakawa da sauƙin amfani ga masu amfani da ƙarshe.
Lambar ka'ida tana buɗe, an rubuta aiwatar da mu a cikin Rust, ana iya samun shi .
Kuna iya ganin yadda ci gaban NEAR yayi kama da gwaji a cikin IDE na kan layi .
Kuna iya bin duk labarai cikin Rashanci a da kuma cikin , kuma a cikin Ingilishi a cikin hukuma .
Sai anjima!
source: www.habr.com
