Hey Habr!
В San Airteagal seo, phléamar cén fáth go bhféadfadh sé a bheith riachtanach uimhreacha randamacha a ghiniúint do rannpháirtithe nach bhfuil muinín acu as a chéile, cad iad na ceanglais a chuirtear chun cinn maidir le gineadóirí uimhreacha randamacha den sórt sin, agus bhreithnigh muid dhá chur chuige maidir lena gcur i bhfeidhm.
Sa chuid seo den alt, déanfaimid breathnú níos dlúithe ar chur chuige eile a úsáideann sínithe tairsí.
Beagán cripteagrafaíochta
D'fhonn tuiscint a fháil ar conas a oibríonn sínithe tairsí, ní mór duit beagán cripteagrafaíochta bunúsach a thuiscint. Úsáidfimid dhá choincheap: scálaí, nó go simplí uimhreacha, a shonróimid le litreacha beaga (x, y) agus pointí ar an gcuar éilipseach, a léireoimid le ceannlitreacha.
Chun bunghnéithe sínithe tairsí a thuiscint, ní gá duit a thuiscint conas a oibríonn cuair éilipseacha, seachas roinnt rudaí bunúsacha:
-
Is féidir pointí ar chuar éilipseach a shuimiú agus a iolrú faoi scálach (déanfaimid iolrú faoi scálach a shonrú mar xG, cé go bhfuil an nodaireacht Gx freisin a úsáidtear go minic sa litríocht). Is é an toradh a bhíonn ar shuimiú agus ar iolrú faoi scálach ná pointe ar chuar éilipseach.
-
A fhios agam ach an pointe G agus a táirge le scálach xG ní féidir a ríomh x.
Bainfimid úsáid freisin as an gcoincheap iltéarmach p (x) céim k-1. Go háirithe, úsáidfimid an t-airí seo a leanas de chuid iltéarmaí: má tá an luach ar eolas againn p (x) d'aon k éagsúla x (agus níl a thuilleadh eolais againn faoi p (x)), is féidir linn a ríomh p (x) do dhuine ar bith eile x.
Tá sé suimiúil gur le haghaidh aon polynomial p (x) agus pointe éigin ar an gcuar Ga fhios agam an bhrí p(x)G d'aon k bríonna éagsúla x, is féidir linn a ríomh freisin p(x)G d'aon x.
Is leor faisnéise é seo chun sonraí a fháil faoin gcaoi a n-oibríonn sínithe tairsí agus conas iad a úsáid chun uimhreacha randamacha a ghiniúint.
Gineadóir uimhreacha randamacha ar shínithe tairsí
A ligean ar a rá go n is mian le rannpháirtithe uimhir randamach a ghiniúint, agus ba mhaith linn go mbeadh aon duine rannpháirteach k bhí go leor acu a ghiniúint roinnt, ach ionas go mbeidh an attackers a rialú k- Níorbh fhéidir le1 rannpháirtí nó níos lú an líon a ghintear a thuar nó tionchar a imirt.
Cuir go bhfuil a leithéid de polynomial p (x) céim k-1 a bhfuil ar eolas ag an gcéad rannpháirtí p (1), tá a fhios ag an dara ceann lch(2), agus mar sin de (n-th fhios p(n)). Glacaimid leis freisin go bhfuil pointe réamhshocraithe éigin G fhios ag gach duine p(x)G do gach luach x. Cuirfimid glaoch p(i) "comhpháirt phríobháideach" iú rannpháirtí (mar gheall ar amháin itá aithne ag an ú rannpháirtí uirthi), agus p(i)G “comhpháirt phoiblí” i-ú rannpháirtí (toisc go bhfuil aithne ag gach rannpháirtí uirthi). Mar is cuimhin leat, eolas p(i)G ní leor a chur ar ais p(i).
A leithéid de polynomial a chruthú ionas go mbeidh amháin i-Bhí a fhios ag an gcéad rannpháirtí agus gan aon duine eile ar a chomhpháirt phríobháideach - is é seo an chuid is casta agus suimiúil den phrótacal, agus déanfaimid anailís air thíos. Faoi láthair, glacaimis leis go bhfuil a leithéid de ilchineálach againn agus go bhfuil a gcomhpháirteanna príobháideacha ar eolas ag gach rannpháirtí.
Conas is féidir linn iltéarmach den sórt sin a úsáid chun uimhir randamach a ghiniúint? Ar dtús, teastaíonn sreang éigin uainn nár úsáideadh roimhe seo mar ionchur don ghineadóir. I gcás blockchain, hash an bhloc seo caite h is iarrthóir maith do líne den sórt sin. Lig do rannpháirtithe ag iarraidh uimhir randamach a chruthú ag baint úsáide as h cosúil le síol. Tiontaíonn na rannpháirtithe ar dtús h go pointe ar an gcuar ag baint úsáide as aon fheidhm réamhshainithe:
H = scalparToPoint(h)
Ansin gach rannpháirtí i ríomhann agus foilsíonn Dia duit = p(i)H, cad is féidir leo a dhéanamh mar tá a fhios acu p(i) agus H. Nochtadh Hi ní cheadaíonn sé do rannpháirtithe eile an chomhpháirt phríobháideach a athchóiriú iú rannpháirtí, agus mar sin is féidir sraith amháin de chomhpháirteanna príobháideacha a úsáid ó bhloc go bloc. Mar sin, ní gá an t-algartam giniúna iltéarmach costasach a gcuirtear síos air thíos a fheidhmiú ach uair amháin.
Nuair a k rinneadh uathpsis ar rannpháirtithe Dia duit = p(i)H, is féidir le gach duine ríomh Hx = p(x)H do chách x a bhuíochas do mhaoin na iltéarmaí a phléamar sa chuid dheireanach. Ag an nóiméad seo, ríomhann na rannpháirtithe go léir H0 = p(0)H, agus is é seo an uimhir randamach mar thoradh air. Tabhair faoi deara nach bhfuil a fhios ag aon duine lch(0), agus dá bhrí sin an t-aon bhealach a ríomh p(0)H – is idirshuíomh é seo p(x)H, rud nach féidir ach nuair a k luachanna p(i)H ar eolas. Oscailt aon chainníocht níos lú p(i)H ní sholáthraíonn sé aon eolas faoi p(0)H.
Tá na hairíonna go léir a theastaíonn uainn ag an gineadóir thuas: ionsaitheoirí amháin a rialaíonn k-Níl aon fhaisnéis nó tionchar ag 1 rannpháirtí nó níos lú ar an gconclúid, cé go bhfuil aon k is féidir le rannpháirtithe a ríomh ar an líon mar thoradh air, agus aon fho-thacar de k tiocfaidh rannpháirtithe i gcónaí ar an toradh céanna don síol céanna.
Tá fadhb amháin ann a sheachain muid go cúramach thuas. Chun idirshuíomh a bheith ag obair, tá sé tábhachtach go bhfuil an luach Hi a d'fhoilsigh gach rannpháirtí i bhí sé i ndáiríre mar an gcéanna p(i)H. Ós rud é aon duine ach amháin i-ú rannpháirtí níl a fhios p(i), aon duine ach i-ní féidir leis an rannpháirtí é sin a fhíorú Hi iarbhír a ríomh i gceart, agus gan aon chruthúnas cripteagrafach cruinnis Hi Is féidir le ionsaitheoir aon luach a fhoilsiú mar Haigh, agus tionchar treallach a imirt ar aschur an ghineadóra uimhir randamach:
Bíonn H_1 de thoradh difriúil mar thoradh ar luachanna difriúla H_0 a sheol an chéad rannpháirtí
Tá ar a laghad dhá bhealach ann chun cruinneas a chruthú Hi, déanfaimid iad a mheas tar éis dúinn anailís a dhéanamh ar ghiniúint an iltéarmaigh.
Giniúint ilchineálach
Sa chuid dheireanach ghlacamar leis go bhfuil a leithéid de iltéarmach againn p (x) céim k-1 go bhfuil an rannpháirtí i tá a fhios p(i), agus níl aon fhaisnéis ag aon duine eile faoin luach seo. Sa chéad chuid eile beidh sé sin de dhíth orainn freisin le haghaidh pointe réamhshocraithe éigin G bhí a fhios ag gach duine p(x)G do chách x.
Sa chuid seo glacfaimid leis go bhfuil eochair phríobháideach éigin ag gach rannpháirtí go háitiúil xi, ionas go mbeidh an eochair phoiblí chomhfhreagrach ar eolas ag gach duine Xi.
Is é seo a leanas prótacal giniúna iltéarmaigh féideartha amháin:
-
Gach rannpháirtí i go háitiúil cruthaíonn sé iltéarmach treallach pi(x) céim k-1. Ansin cuireann siad chuig gach rannpháirtí j значение pi(j), criptithe le heochair phoiblí Xj. Mar sin amháin i-yy и j-yy rannpháirtí a fhios pi(j). Rannpháirtí i Fógraíonn go poiblí freisin pi(j)G do chách j ó 1 до k san áireamh.
-
Úsáideann na rannpháirtithe go léir comhdhearcadh éigin chun rogha a dhéanamh k rannpháirtithe a n-úsáidfear ilainmneacha. Ós rud é go bhféadfadh roinnt rannpháirtithe a bheith as líne, ní féidir linn fanacht go dtí gach duine n foilseoidh rannpháirtithe ilainmneacha. Is sraith é toradh na céime seo Z comhdhéanta de ar a laghad k polynomials cruthaithe i gcéim (1).
-
Cinntíonn na rannpháirtithe go bhfuil na luachanna ar eolas acu pi(j) comhfhreagróidh siad don fhógra a fógraíodh go poiblí pi(j)G. Tar éis an chéim seo isteach Z iltéarmaí amháin a tharchuirtear go príobháideach ina leith pi(j) comhfhreagróidh siad don fhógra a fógraíodh go poiblí pi(j)G.
-
Gach rannpháirtí j ríomhann a chomhpháirt phríobháideach p(j) mar shuim pi(j) do chách i в Z. Ríomhann gach rannpháirtí gach luach freisin p(x)G mar shuim pi(x)G do chách i в Z.
tabhair faoi deara go p(x) - is polynomial é i ndáiríre k- 1, toisc gurb é suim an duine aonair é pi(x), ar céim iltéarmach gach ceann acu k-1. Ansin, faoi deara go cé go bhfuil gach rannpháirtí j tá a fhios p(j), níl aon eolas acu faoi p (x) le haghaidh x ≠ j. Go deimhin, chun an luach seo a ríomh, ní mór go mbeadh a fhios acu gach rud pi(x), agus chomh fada leis an rannpháirtí j níl a fhios ag ceann amháin ar a laghad de na hilainmneacha roghnaithe, níl dóthain faisnéise acu faoi p(x).
Is é seo an próiseas giniúna iltéarmach ar fad a bhí ag teastáil sa chuid dheireanach. Tá cur i bhfeidhm measartha soiléir ag céimeanna 1, 2 agus 4 thuas. Ach níl céim 3 chomh fánach.
Go sonrach, ní mór dúinn a bheith in ann a chruthú go criptithe pi(j) comhfhreagras i ndáiríre do na cinn foilsithe pi(j)G. Más rud é nach féidir linn a chruthú, an ionsaitheoir i féadfaidh sé truflais a sheoladh ina ionad pi(j) don rannpháirtí j, agus rannpháirtí j ní bheidh siad in ann an bhrí cheart a fháil pi(j), agus ní bheidh sé in ann a chomhpháirt phríobháideach a ríomh.
Tá prótacal cripteagrafach ann a ligeann duit teachtaireacht bhreise a chruthú cruthúnasi(j), ionas go mbeidh luach éigin ag rannpháirtí ar bith e, chomh maith cruthúnais(j) и pi(j)G, in ann é sin a fhíorú go háitiúil e - tá sé i ndáiríre pi(j), criptithe le heochair an rannpháirtí j. Ar an drochuair, tá méid na fianaise den sórt sin thar a bheith mór, agus ós rud é go bhfuil sé riachtanach a fhoilsiú Ó(nk) Ní féidir fianaise den sórt sin a úsáid chun na críche sin.
In ionad é sin a chruthú pi(j) соответствует pi(j)G is féidir linn tréimhse an-fhada ama a leithdháileadh sa phrótacal giniúna iltéarmaigh, ina seiceálann na rannpháirtithe go léir an criptithe faighte pi(j), agus mura gcomhfhreagraíonn an teachtaireacht díchriptithe don phobal pi(j)G, foilsíonn siad cruthúnas cripteagrafach go bhfuil an teachtaireacht chriptithe a fuair siad mícheart. Cruthaigh go bhfuil an teachtaireacht aon соответствует pi(G) i bhfad níos éasca ná a chruthú go bhfuil sé ag teacht leis. Ba chóir a thabhairt faoi deara go n-éilíonn sé seo go gcaithfidh gach rannpháirtí láithriú ar líne uair amháin ar a laghad le linn an ama atá tugtha chun fianaise den sórt sin a chruthú, agus braitheann sé ar an toimhde má fhoilsíonn siad cruthúnas den sórt sin, go sroichfidh sé gach rannpháirtí eile san am leithroinnte céanna.
Mura raibh rannpháirtí le feiceáil ar líne le linn na tréimhse ama seo, agus go raibh ar a laghad comhpháirt mícheart amháin aige, ní bheidh an rannpháirtí áirithe sin in ann páirt a ghlacadh i nginiúint uimhreacha breise. Feidhmeoidh an prótacal, áfach, má tá ar a laghad ann k rannpháirtithe nach bhfuair ach na comhpháirteanna cearta nó a d'éirigh leo cruthúnas míchearta a fhágáil laistigh den am leithroinnte.
Cruthúnas ar chruinneas H_i
Is í an chuid dheireanach atá fós le plé ná conas cruinneas foilsithe a chruthú Hi, eadhon sin Dia duit = p(i)H, gan oscailt p(i).
Lig dúinn cuimhneamh go bhfuil na luachanna H, G, p(i)G poiblí agus ar eolas ag gach duine. Faigh oibríocht p(i) a fhios agam p(i)G и G ar a dtugtar logartamach scoite, nó dlog, agus ba mhaith linn a chruthú go:
dlog(p(i)G, G) = dlog(Hi, H)
gan nochtadh p(i). Tá foirgnimh le haghaidh cruthúnais den sórt sin ann, mar shampla.
Leis an dearadh, gach rannpháirtí, chomh maith le Hi seolann cruthúnas cruinnis de réir an dearadh.
Nuair a ghintear uimhir randamach, is minic a chaithfidh rannpháirtithe seachas iad siúd a chruthaigh í a úsáid. Ní mór do rannpháirtithe den sórt sin, chomh maith leis an uimhir, go léir a sheoladh Hi agus fianaise ghaolmhar.
Féadfaidh léitheoir fiosrach ceist a chur: ós é an uimhir randamach deiridh H0, agus p(0)G - Is faisnéis phoiblí í seo, cén fáth a bhfuil cruthúnas ag teastáil uainn do gach duine Hi, cén fáth nach seol cruthúnas sin ina ionad
dlog(p(0)G, G) = dlog(H0, H)
Is í an fhadhb atá ann nach féidir a leithéid de chruthúnas a chruthú trí úsáid a bhaint as Prótacal Schnorr mar níl a fhios ag aon duine an luach p (0), is gá chun an cruthúnas a chruthú, agus cad atá níos mó, tá an gineadóir uimhir randamach ar fad bunaithe ar an bhfíric nach bhfuil a fhios ag aon duine an luach seo. Dá bhrí sin tá sé riachtanach go mbeadh na luachanna go léir Hi agus a gcuid fianaise aonair chun cruinneas a chruthú H0.
Mar sin féin, dá mbeadh oibríocht éigin ar phointí ar chuair éilipseacha atá cosúil go semantach le hiolrú, ba cheart go mbeadh an cruthúnas cruinnis H0 a bheith fánach, ní dhéanfaimis cinnte de sin
H0 × G = p(0)G × H
Má thacaíonn an cuar roghnaithe , oibríonn an cruthúnas seo. Sa chás seo HNí hamháin gur aschur gineadóir uimhreacha randamacha é 0, ar féidir le rannpháirtí ar bith a bhfuil aithne aige é a fhíorú G, H и p(0)G. HIs síniú é 0 freisin ar an teachtaireacht a úsáideadh mar shíol, ag dearbhú é sin k и n shínigh rannpháirtithe an teachtaireacht seo. Dá bhrí sin, más rud é síol - is hash an bhloic sa phrótacal blockchain, mar sin H0 is ilshíniú ar bhloc agus uimhir randamach an-mhaith é araon.
Mar fhocal scoir
Tá an t-alt seo mar chuid de shraith blag theicniúil . Is prótacal agus ardán blockchain é NEAR chun feidhmchláir dhíláraithe a fhorbairt le béim ar éascaíocht forbartha agus éascaíocht úsáide d’úsáideoirí deiridh.
Tá an cód prótacail oscailte, tá ár gcur chun feidhme scríofa i Rust, is féidir é a fháil .
Is féidir leat a fheiceáil cén chuma atá ar fhorbairt NEAR agus triail a bhaint as san IDE ar líne .
Is féidir leat an nuacht go léir a leanúint i Rúisis ag agus , agus i mBéarla san oifigeach .
Feicfidh mé go luath thú!
Foinse: will.com