A bheil e comasach àireamhan air thuaiream a ghineadh mura h-eil earbsa againn ann an càch a chèile? Pàirt 2

Hi Habr!

В a ’chiad phàirt San artaigil seo, bhruidhinn sinn air carson a dh’ fhaodadh gum biodh e riatanach àireamhan air thuaiream a ghineadh airson com-pàirtichean aig nach eil earbsa ann an càch a chèile, dè na riatanasan a thathas a ’cur air adhart airson gineadairean àireamhan air thuaiream mar sin, agus bheachdaich sinn air dà dhòigh air an cur an gnìomh.

Anns a’ phàirt seo den artaigil, bheir sinn sùil nas mionaidiche air dòigh-obrach eile a bhios a’ cleachdadh ainmean stairsnich.

Beagan de cryptography

Gus tuigse fhaighinn air mar a tha ainmean stairsneach ag obair, feumaidh tu beagan criptography bunaiteach a thuigsinn. Cleachdaidh sinn dà bhun-bheachd: scalars, no dìreach àireamhan, a chomharraicheas sinn le litrichean beaga (x, y) agus puingean air an lùb elliptic, a chomharraicheas sinn le prìomh litrichean.

Gus bun-bheachdan ainmean stairsnich a thuigsinn, chan fheum thu tuigsinn mar a tha lùban elliptic ag obair, ach a-mhàin beagan rudan bunaiteach:

1. Faodar puingean air lùb elliptic a chur ris agus iomadachadh le scalar (comharraichidh sinn iomadachadh le scalar mar xG, ged a tha an comharradh Gx cuideachd air a chleachdadh gu tric anns an litreachas). Tha toradh cur-ris agus iomadachadh le sgalar na phuing air lùb elliptic.

2. Gun eòlas ach air a’ phuing G agus a toradh le sgalag xG chan urrainnear a thomhas x.

Cleachdaidh sinn cuideachd bun-bheachd polynomial p (x) ceumannan k-1. Gu sònraichte, cleachdaidh sinn an t-seilbh a leanas de polynomials: ma tha fios againn air an luach p (x) airson sam bith k eadar-dhealaichte x (agus chan eil tuilleadh fiosrachaidh againn mu dheidhinn p (x)), is urrainn dhuinn obrachadh a-mach p (x) do dhuine sam bith eile x.

Gu inntinneach, airson polynomial sam bith p (x) agus beagan puing air an lùb Geòlach air a’ bhrìgh p(x) G airson sam bith k ciall eadar-dhealaichte x, is urrainn dhuinn cuideachd àireamhachadh p(x) G airson sam bith x.

Is e fiosrachadh gu leòr a tha seo gus faighinn a-steach don fhiosrachadh mu mar a bhios ainmean stairsneach ag obair agus mar a chleachdas iad iad gus àireamhan air thuaiream a ghineadh.

Gineadair àireamh air thuaiream air ainmean-sgrìobhte stairsnich

Canaidh sinn sin n tha com-pàirtichean ag iarraidh àireamh air thuaiream a ghineadh, agus tha sinn airson gun gabh duine sam bith pàirt k bha gu leòr dhiubh ann airson àireamh a ghineadh, ach gus am bi an luchd-ionnsaigh a bhios a’ cumail smachd k- Cha b’ urrainn dha1 no nas lugha de chom-pàirtichean ro-innse no buaidh a thoirt air an àireamh a chaidh a chruthachadh.

Seach gu bheil leithid de polynomial ann p (x) ceumannan k-1 dè tha fios aig a 'chiad chom-pàirtiche p (1), tha fios aig an dàrna fear p(2), Agus mar sin air adhart (n-tha fios p(n)). Tha sinn cuideachd a’ gabhail ris sin airson puing ro-shuidhichte G tha fios aig a h-uile duine p(x) G airson a h-uile luach x. Canaidh sinn p(i) "pàirt phrìobhaideach" ian com-pàirtiche (oir a-mhàin itha fios aig a' chom-pàirtiche oirre), agus p(i) G “pàirt phoblach” i-th com-pàirtiche (seach gu bheil a h-uile com-pàirtiche eòlach oirre). Mar a chuimhnicheas tu, eòlas p(i) G chan eil gu leòr airson a thoirt air ais p(i).

A 'cruthachadh a leithid polynomial mar sin a-mhàin i-Bha a 'chiad chom-pàirtiche agus cha robh fios aig duine sam bith eile air a' phàirt phrìobhaideach aige - is e seo am pàirt as iom-fhillte agus inntinneach den phròtacal, agus nì sinn sgrùdadh air gu h-ìosal. Airson a-nis, gabhamaid ris gu bheil an leithid de polynomial againn agus gu bheil fios aig a h-uile com-pàirtiche air na pàirtean prìobhaideach aca.

Ciamar as urrainn dhuinn a leithid de polynomial a chleachdadh gus àireamh air thuaiream a ghineadh? An toiseach, feumaidh sinn sreang nach deach a chleachdadh roimhe mar chur-a-steach don ghineadair. Ann an cùis blockchain, hash a’ bhloc mu dheireadh h tha e na thagraiche math airson a leithid de loidhne. Leig le com-pàirtichean a bhith ag iarraidh àireamh air thuaiream a chruthachadh a 'cleachdadh h mar shìol. Bidh com-pàirtichean ag atharrachadh an toiseach h gu puing air an lùb a’ cleachdadh gnìomh ro-mhìnichte sam bith:

H = sgalarToPoint(h)

An uairsin gach com-pàirtiche i àireamhachadh agus fhoillseachadh Hi = p(i)H, dè as urrainn dhaibh a dhèanamh oir tha fios aca p(i) agus H. Foillseachadh Hchan eil i a’ leigeil le com-pàirtichean eile am pàirt phrìobhaideach a thoirt air ais ith com-pàirtiche, agus mar sin faodar aon sheata de phàirtean prìobhaideach a chleachdadh bho bhloc gu bloc. Mar sin, chan fheum an algairim gineadh polynomial daor a tha air a mhìneachadh gu h-ìosal a chuir gu bàs ach aon turas.

Cuin k chaidh com-pàirtichean a dhèanamh fèin-ghluasadach Hi = p(i)H, faodaidh a h-uile duine àireamhachadh Hx = p(x)h dha na h-uile x taing dha seilbh polynomials air an do bhruidhinn sinn san roinn mu dheireadh. Aig an àm seo, bidh a h-uile com-pàirtiche a 'cunntadh H0 = p(0)H, agus seo an àireamh air thuaiream a thig às. Thoir an aire nach eil fios aig duine p(0), agus mar sin an aon dòigh air àireamhachadh p(0)H - is e seo eadar-theangachadh p(x)h, a tha comasach a-mhàin nuair a k luachan p(i) H aithnichte. A 'fosgladh meud sam bith nas lugha p(i) H chan eil e a’ toirt seachad fiosrachadh sam bith mu dheidhinn p(0)h.

Tha na feartan uile a tha sinn ag iarraidh aig a’ ghineadair gu h-àrd: luchd-ionnsaigh a’ cumail smachd a-mhàin k-Chan eil fiosrachadh no buaidh aig 1 com-pàirtiche no nas lugha air a’ cho-dhùnadh, fhad ‘s a tha gin k faodaidh com-pàirtichean obrachadh a-mach an àireamh a thig às, agus fo-sheata sam bith de k bidh com-pàirtichean an-còmhnaidh a’ tighinn chun an aon toradh airson an aon sìol.

Tha aon duilgheadas ann a sheachain sinn gu faiceallach gu h-àrd. Airson interpolation a bhith ag obair, tha e cudromach gu bheil an luach Hi a chaidh fhoillseachadh leis gach com-pàirtiche i bha e dha-rìribh an aon rud p(i) H. Leis nach eil duine ach a-mhàin i-th com-pàirtiche chan eil fios p(i), neach air bith ach i-chan urrainn don chom-pàirtiche sin a dhearbhadh Hi dha-rìribh air a thomhas gu ceart, agus às aonais dearbhadh criptografach air ceartachd HFaodaidh neach-ionnsaigh luach sam bith fhoillseachadh mar Hi, agus gu neo-riaghailteach buaidh a thoirt air toradh gineadair àireamhan air thuaiream:

Bidh luachan eadar-dhealaichte de H_1 a chuir a’ chiad chom-pàirtiche a’ leantainn gu diofar thoradh H_0

Tha co-dhiù dà dhòigh air ceartachd a dhearbhadh Hi, beachdaichidh sinn orra às deidh dhuinn mion-sgrùdadh a dhèanamh air ginealach an polynomial.

Ginealach polynomial

Anns an earrainn mu dheireadh bha sinn a' gabhail ris gu bheil a leithid de dh' ioma-ghnèitheachd againn p (x) ceumannan k-1 gu bheil an com-pàirtiche i tha fios p(i), agus chan eil fiosrachadh sam bith aig duine sam bith eile mun luach seo. Anns an ath earrainn bidh feum againn air sin cuideachd airson puing ro-shuidhichte G bha fios aig a h-uile duine p(x) G dha na h-uile x.

Anns an earrainn seo gabhaidh sinn ris gu bheil iuchair phrìobhaideach aig gach com-pàirtiche gu h-ionadail xi, gus am bi fios aig a h-uile duine air an iuchair phoblach iomchaidh Xi.

Tha aon phròtacal ginealach polynomial comasach mar a leanas:

1. A h-uile com-pàirtiche i gu h-ionadail a’ cruthachadh polynomial neo-riaghailteach pi(x) ceum k-1. Bidh iad an uairsin a’ cur gach com-pàirtiche j ciallachadh pi(j), air a chrioptachadh le iuchair phoblach Xj. Mar sin a-mhàin i-th и j-th tha fios aig a’ chom-pàirtiche pi(j). Com-pàirtiche i cuideachd ag ainmeachadh gu poblach pi(j) G dha na h-uile j от 1 gu k in-ghabhalach.

2. Bidh a h-uile com-pàirtiche a’ cleachdadh beagan co-aontachd airson taghadh k com-pàirtichean a thèid am polynomials a chleachdadh. Leis gum faodadh cuid de chom-pàirtichean a bhith far loidhne, chan urrainn dhuinn feitheamh gus a h-uile duine n foillsichidh com-pàirtichean polynomials. Is e toradh a 'cheum seo seata Z air a dhèanamh suas de co-dhiù k polynomials air an cruthachadh ann an ceum (1).

3. Bidh com-pàirtichean a 'dèanamh cinnteach gu bheil na luachan air a bheil iad eòlach pi(j) a’ freagairt ri a chaidh fhoillseachadh gu poblach pi(j) G. Às deidh a’ cheum seo a-steach Z dìreach polynomials airson an tar-chuir gu prìobhaideach pi(j) a’ freagairt ri a chaidh fhoillseachadh gu poblach pi(j) G.

4. A h-uile com-pàirtiche j ag obrachadh a-mach a phàirt phrìobhaideach p(j) mar suim pi(j) dha na h-uile i в Z. Bidh gach com-pàirtiche cuideachd a’ cunntadh a h-uile luach p(x) G mar suim pi(x)G dha na h-uile i в Z.

thoir fa-near sin p(x) - tha e dha-rìribh polynomial k-1, oir is e suim an neach fa leth e pi(x), agus tha gach aon dhiubh na cheum polynomial k-1. An uairsin, thoir fa-near, fhad ‘s a tha gach com-pàirtiche j tha fios p(j), chan eil fiosrachadh sam bith aca mu dheidhinn p (x) airson x ≠ j. Gu dearbh, gus an luach seo obrachadh a-mach, feumaidh fios a bhith aca air a h-uile càil pi(x), agus cho fada ris a’ chom-pàirtiche j chan eil fios aca air co-dhiù aon de na polynomials taghte, chan eil fiosrachadh gu leòr aca mu dheidhinn p(x).

Is e seo am pròiseas ginealach polynomial gu lèir a bha a dhìth anns an earrainn mu dheireadh. Tha buileachadh gu math follaiseach aig Ceumannan 1, 2 agus 4 gu h-àrd. Ach chan eil ceum 3 cho beag.

Gu sònraichte, feumaidh sinn a bhith comasach air dearbhadh gu bheil sin crioptaichte pi(j) dha-rìribh a’ freagairt ris an fheadhainn a chaidh fhoillseachadh pi(j) G. Mura h-urrainn dhuinn a dhearbhadh, an neach-ionnsaigh i faodaidh e sgudal a chuir na àite pi(j) don chom-pàirtiche j, agus com-pàirtiche j cha bhith e comasach dha an fhìor luach fhaighinn pi(j), agus cha bhith e comasach dha a phàirt phrìobhaideach obrachadh a-mach.

Tha protocol criptografach ann a leigeas leat teachdaireachd a bharrachd a chruthachadh dearbhadhi(j), gus am bi com-pàirtiche sam bith, aig a bheil luach air choreigin e, a dh 'fhalbh dearbhadh(j) и pi(j) G, dearbhadh gu h-ionadail sin e - tha e dha-rìribh pi(j), air a chrioptachadh le iuchair a’ chom-pàirtiche j. Gu mì-fhortanach, tha meud an fhianais sin gu math mòr, agus leis gu bheil feum air foillseachadh Ach(nk) Chan urrainnear fianais leithid seo a chleachdadh airson an adhbhair seo.

An àite sin a dhearbhadh pi(j) соответствует pi(j) G is urrainn dhuinn ùine gu math mòr a riarachadh anns a’ phròtacal ginealach polynomial, nuair a bhios a h-uile com-pàirtiche a’ dèanamh sgrùdadh air a’ chrioptachadh a fhuaireadh pi(j), agus mura h-eil an teachdaireachd dì-chrioptaichte a 'freagairt ris a' phoball pi(j) G, bidh iad a’ foillseachadh dearbhadh criptografach gu bheil an teachdaireachd chrioptaichte a fhuair iad ceàrr. Dearbh gu bheil an teachdaireachd chan eil соответствует pi(G) tòrr nas fhasa na bhith a’ dearbhadh gu bheil e co-ionnan. Bu chòir a thoirt fa-near gu bheil seo ag iarraidh air gach com-pàirtiche nochdadh air-loidhne co-dhiù aon turas san ùine a chaidh a shònrachadh airson an leithid de fhianais a chruthachadh, agus tha e an urra ris a’ bharail ma dh’ fhoillsicheas iad dearbhadh mar sin gun ruig e a h-uile com-pàirtiche eile san aon ùine ainmichte.

Mura nochd com-pàirtiche air-loidhne rè na h-ùine seo, agus gu robh co-dhiù aon phàirt ceàrr aige, cha bhith e comasach don chom-pàirtiche sònraichte sin pàirt a ghabhail ann an tuilleadh gineadh àireamhan. Bidh am protocol, ge-tà, fhathast ag obair ma tha co-dhiù ann k com-pàirtichean a tha dìreach air na pàirtean ceart fhaighinn no a fhuair air dearbhadh mearachd fhàgail taobh a-staigh na h-ùine ainmichte.

Dearbhaidhean air ceartachd H_i

Is e am pàirt mu dheireadh a tha fhathast ri dheasbad mar a dhearbhas tu ceartachd foillseachaidh Hi, eadhon sin Hi = p(i)H, gun fhosgladh p(i).

Cuimhnich sinn gu bheil na luachan H, G, p(i)G poblach agus aithnichte do na h-uile. Faigh gnìomh p(i) fios p(i) G и G ris an canar logarithm air leth, no dlog, agus tha sinn airson sin a dhearbhadh:

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

gun fhoillseachadh p(i). Tha togalaichean ann airson a leithid de dhearbhadh, mar eisimpleir Pròtacal Schnorr.

Leis an dealbhadh seo, bidh gach com-pàirtiche, còmhla ri Hi a’ cur dearbhadh air ceartachd a rèir an dealbhaidh.

Aon uair ‘s gu bheil àireamh air thuaiream air a chruthachadh, gu tric feumaidh com-pàirtichean a bhith ga chleachdadh ach an fheadhainn a chruthaich e. Feumaidh an leithid de chom-pàirtichean, còmhla ris an àireamh, a h-uile duine a chuir Hi agus fianais co-cheangailte.

Faodaidh leughadair fiosrach faighneachd: oir is e an àireamh air thuaiream mu dheireadh H0, agus p(0)G - Is e fiosrachadh poblach a tha seo, carson a tha feum againn air dearbhadh airson gach neach Hi, carson nach cuir thu dearbhadh sin na àite

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

Is e an duilgheadas a th’ ann nach urrainnear a leithid de dhearbhadh a chruthachadh a’ cleachdadh Pròtacal Schnorr leis nach eil fios aig duine air an luach p (0), riatanach gus an dearbhadh a chruthachadh, agus a bharrachd air an sin, tha an gineadair àireamh air thuaiream gu lèir stèidhichte air nach eil fios aig duine air an luach seo. Mar sin tha e riatanach na luachan uile a bhith agad Hi agus an fhianais fa leth a dhearbhas ceartachd H0.

Ach, nam biodh beagan obrachaidh air puingean air lùban elliptic a tha coltach gu semantach ri iomadachadh, tha an dearbhadh air ceartachd H0 bhiodh e beag, bhiodh sinn dìreach a’ dèanamh cinnteach sin

H0 × G = p(0)G × H

Ma tha an lùb taghte a’ toirt taic paidhir lùban elliptic, tha an dearbhadh seo ag obair. Anns a 'chùis seo HChan e a-mhàin toradh gineadair àireamh air thuaiream a th’ ann an 0, a dh’ fhaodar a dhearbhadh le com-pàirtiche sam bith aig a bheil fios G, H и p(0)G. Tha H0 cuideachd na ainm-sgrìobhte air an teachdaireachd a chaidh a chleachdadh mar shìol, a 'dearbhadh sin k и n chuir na com-pàirtichean ainm ris an teachdaireachd seo. Mar sin, ma tha sìol - an e hash a’ bhloca anns a’ phròtacal blockchain, ma-thà H0 tha an dà chuid ioma-ainm-sgrìobhte air bloc agus àireamh air thuaiream fìor mhath.

Ann an co-dhùnadh

Tha an artaigil seo mar phàirt de shreath blogaichean teicnigeach GUN. Tha NEAR na phròtacal blockchain agus àrd-ùrlar airson a bhith a’ leasachadh thagraidhean dì-mheadhanaichte le cuideam air a bhith furasta an leasachadh agus furasta an cleachdadh airson luchd-cleachdaidh deireannach.

Tha an còd protocol fosgailte, tha ar buileachadh sgrìobhte ann an Rust, gheibhear e an seo.

Chì thu cò ris a tha leasachadh airson NEAR coltach agus feuch an dèan thu deuchainn anns an IDE air-loidhne an seo.

Faodaidh tu na naidheachdan gu lèir ann an Ruisis a leantainn aig buidheann teileagram agus a-staigh Buidheann Vkontakte saor an asgaidh, agus ann am Beurla anns an oifigeach twitter.

Chì mi thu a dh 'aithghearr!

Source: www.habr.com