An féidir uimhreacha randamacha a ghiniúint mura bhfuil muinín againn as a chéile? Cuid 1

Hey Habr!

San Airteagal seo labhróidh mé faoi ghiniúint uimhreacha bréagacha randamacha ag rannpháirtithe nach bhfuil muinín acu as a chéile. Mar a fheicfimid thíos, tá sé simplí go leor gineadóir maith “beagnach” a chur i bhfeidhm, ach tá sé deacair ceann an-mhaith.

Cén fáth a mbeadh sé riachtanach uimhreacha randamacha a ghiniúint i measc rannpháirtithe nach bhfuil muinín acu as a chéile? Réimse iarratais amháin is ea iarratais dhíláraithe. Mar shampla, ní oibreoidh iarratas a ghlacann le geall ó rannpháirtí agus a dhúblaíonn an méid le dóchúlacht 49% nó a thógann amach le dóchúlacht 51% ach amháin más féidir leis uimhir randamach a fháil go neamhchlaonta. Más féidir le hionsaitheoir tionchar a imirt ar thoradh an ghineadóra uimhreacha randamacha, agus fiú méadú beag ar an seans go bhfaighidh sé íocaíocht amach san iarratas, scriosfaidh sé go héasca é.

Nuair a dhearaimid prótacal giniúna uimhreacha randamacha dáilte, ba mhaith linn go mbeadh trí airí aige:

1. Caithfidh sé a bheith neamhchlaonta. I bhfocail eile, níor cheart go mbeadh tionchar ar bith ag rannpháirtí ar thoradh an ghineadóra uimhreacha randamacha.

2. Caithfidh sé a bheith dothuartha. I bhfocail eile, níor cheart go mbeadh rannpháirtí ar bith in ann a thuar cén uimhir a ghinfear (nó aon cheann dá airíonna) a bhaint amach sula nginfear é.

3. Caithfidh an prótacal a bheith inmharthana, is é sin, frithsheasmhach ar an bhfíric go ndéanann céatadán áirithe de na rannpháirtithe a dhícheangal ón líonra nó iarracht a dhéanamh d'aon ghnó an prótacal a stopadh.

San Airteagal seo féachfaimid ar dhá chur chuige: RANDAO + VDF agus cur chuige na gcód scriosta. Sa chéad chuid eile, scrúdóimid go mion an cur chuige bunaithe ar shínithe tairsí.

Ach ar dtús, déanaimis féachaint ar algartam simplí agus a úsáidtear go coitianta atá inmharthana, dothuartha, ach claonta.

RANDAO

Is cur chuige an-simplí é RANDAO agus mar sin de a úsáidtear go coitianta chun randamacht a ghiniúint. Roghnaíonn gach rannpháirtí líonra go háitiúil uimhir bhréige ar dtús, ansin seolann gach rannpháirtí hash den uimhir roghnaithe. Ansin, glacann na rannpháirtithe sealanna ag nochtadh a gcuid uimhreacha roghnaithe agus ag déanamh oibríocht XOR ar na huimhreacha a nochtar, agus déantar toradh na hoibríochta seo mar thoradh ar an bprótacal.

Is gá an chéim a bhaineann le foilsiú na hashes roimh na huimhreacha a nochtadh ionas nach féidir leis an ionsaitheoir a uimhir a roghnú tar éis dó líon na rannpháirtithe eile a fheiceáil. Ligfeadh sé seo dó aschur an ghineadóra uimhreacha randamacha a chinneadh beagnach ina aonar.

Le linn an phrótacail, ní mór do rannpháirtithe teacht ar chinneadh coitianta (comhdhearcadh mar a thugtar air) faoi dhó: cathain is féidir tús a chur le nochtadh na n-uimhreacha roghnaithe, agus mar sin stop a chur le hashes a ghlacadh, agus cathain a stopfaidh glacadh leis na huimhreacha roghnaithe agus an randamach mar thoradh air a ríomh. uimhir. Ní tasc éasca ann féin é cinntí den sórt sin a dhéanamh idir rannpháirtithe nach bhfuil muinín acu as a chéile, agus fillfimid air in ailt amach anseo; san Airteagal seo glacfaimid leis go bhfuil algartam comhthola den sórt sin ar fáil dúinn.

Cé acu ceann de na hairíonna a bhfuil cur síos déanta againn orthu thuas atá ag RANDAO? Tá sé dothuartha, tá an bheocht chéanna aige agus atá ag an mbunphrótacal comhthola, ach tá sé claonta. Go sonrach, is féidir le hionsaitheoir an líonra a bhreathnú, agus tar éis do rannpháirtithe eile a n-uimhreacha a nochtadh, is féidir leis a XOR a ríomh, agus cinneadh a dhéanamh an nochtfaidh sé a uimhir chun tionchar a imirt ar an toradh. Cé go gcuireann sé seo cosc ​​ar an ionsaitheoir aschur an ghineadóra uimhreacha randamacha a chinneadh ina aonar, tugann sé 1 giotán tionchair dó fós. Agus má rialaíonn ionsaitheoirí roinnt rannpháirtithe, ansin beidh líon na ngiotán a rialaíonn siad cothrom le líon na rannpháirtithe atá faoina smacht.

Is féidir tionchar na n-ionsaitheoirí a laghdú go mór trína cheangal ar rannpháirtithe na huimhreacha a nochtadh in ord. Ansin ní bheidh an t-ionsaitheoir in ann tionchar a imirt ar an toradh ach amháin má osclaítear é faoi dheireadh. Cé go bhfuil an tionchar i bhfad níos lú, tá an algartam fós claonta.

RANDAO+VDF

Bealach amháin chun RANDAO a dhéanamh neamhchlaonta is ea é seo: tar éis na huimhreacha go léir a nochtadh agus an XOR a ríomh, cuirtear a thoradh isteach in ionchur feidhme, a thógann am an-fhada é a ríomh, ach ligeann duit cruinneas na huimhreacha a sheiceáil. ríomh go han-tapa.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Tugtar Feidhm Moill Infhíoraithe ar an bhfeidhm seo, nó VDF. Má thógann sé níos faide ná an chéim nochta uimhreacha a ríomh an toradh deiridh, ní bheidh an t-ionsaitheoir in ann an éifeacht a bhaineann le huimhir a thaispeáint nó a cheilt a thuar, agus dá bhrí sin caillfidh sé an deis tionchar a imirt ar an toradh.

Tá sé thar a bheith deacair VDFanna maithe a fhorbairt. Tharla go leor dul chun cinn le déanaí, e.g. seo и seo, rud a rinne VDF níos praiticiúla go praiticiúil, agus tá sé beartaithe ag Ethereum 2.0 RANDAO a úsáid le VDF mar fhoinse uimhir randamach san fhadtéarma. Seachas go bhfuil an cur chuige seo dothuartha agus neamhchlaonta, tá an buntáiste breise aige go bhfuil sé inmharthana má bhíonn ar a laghad dhá rannpháirtí ar fáil ar an líonra (ag glacadh leis go bhfuil an prótacal comhthola a úsáidtear inmharthana nuair a dhéileáiltear le líon chomh beag rannpháirtithe).

Is é an dúshlán is mó a bhaineann leis an gcur chuige seo ná an VDF a bhunú ionas nach mbeidh fiú rannpháirtí a bhfuil crua-earraí speisialaithe an-chostasach aige in ann an VDF a ríomh roimh dheireadh na céime fionnachtana. Go hidéalach, ba cheart go mbeadh corrlach sábháilteachta suntasach ag an algartam fiú, abair 10x. Léiríonn an figiúr thíos ionsaí ag aisteoir a bhfuil ASIC speisialaithe aige a ligeann dó VDF a reáchtáil níos tapúla ná an t-am a leithdháileadh chun dearbhú RANDAO a nochtadh. Is féidir le rannpháirtí den sórt sin an toradh deiridh a ríomh go fóill ag baint úsáide as nó gan úsáid a bhaint as a uimhir, agus ansin, bunaithe ar an ríomh, roghnaigh cibé acu é a thaispeáint nó nach ea.

Maidir leis an teaghlach VDF a luaitear thuas, is féidir le feidhmíocht ASIC tiomnaithe a bheith 100+ huaire níos airde ná na crua-earraí traidisiúnta. Mar sin má mhaireann an chéim imscartha 10 soicind, ansin caithfidh an VDF a ríomhtar ar ASIC den sórt sin níos mó ná 100 soicind a ghlacadh chun corrlach sábháilteachta 10x a bheith aige, agus mar sin ní mór don VDF céanna a ríomhtar ar chrua-earraí tráchtearraí 100x 100 soicind = ~ 3 uair a ghlacadh.

Tá sé beartaithe ag Fondúireacht Ethereum an fhadhb seo a réiteach trína ASICanna saor in aisce atá ar fáil go poiblí a chruthú. Nuair a tharlaíonn sé seo, is féidir le gach prótacal eile leas a bhaint as an teicneolaíocht seo, ach go dtí sin ní bheidh an cur chuige RANDAO+VDF chomh inmharthana do phrótacail nach féidir leo infheistíocht a dhéanamh i bhforbairt a gcuid ASICanna féin.

Bailíodh go leor alt, físeáin agus faisnéis eile faoi VDF ar an suíomh seo.

Bainimid úsáid as cóid scriosta

San alt seo, féachfaimid ar phrótacal giniúna uimhreacha randamacha a úsáideann cóid a scriosadh. Féadfaidh sé suas le ⅓ ionsaitheoirí a fhulaingt agus iad fós inmharthana, agus ceadaíonn sé suas le ⅔ ionsaitheoirí a bheith ann sula bhféadfaidh siad an toradh a thuar nó tionchar a imirt.

Is é seo a leanas príomh-smaoineamh an phrótacail. Ar mhaithe le simplíocht, déanaimis glacadh leis go bhfuil díreach 100 rannpháirtí ann. Glacaimid leis freisin go bhfuil eochair phríobháideach éigin ag gach rannpháirtí go háitiúil, agus go bhfuil eochracha poiblí na rannpháirtithe uile ar eolas ag na rannpháirtithe go léir:

1. Tagann gach rannpháirtí go háitiúil suas le teaghrán fada, briseann sé ina 67 cuid, cruthaíonn sé cóid scriosta chun 100 sciar a fháil ionas gur leor aon 67 chun an teaghrán a aisghabháil, sannann sé gach ceann de na 100 scair do cheann de na rannpháirtithe, agus criptíonn sé iad le eochair phoiblí an rannpháirtí céanna. Foilsítear na scaireanna ionchódaithe go léir ansin.

2. Úsáideann rannpháirtithe comhdhearcadh de chineál éigin chun teacht ar chomhaontú maidir le tacair chódaithe ó 67 rannpháirtí ar leith.

3. Nuair a bhíonn comhaontú bainte amach, glacann gach rannpháirtí na scaireanna ionchódaithe i ngach ceann de na 67 tacair atá criptithe lena n-eochair phoiblí, díchriptíonn sé gach scair den sórt sin, agus foilsíonn sé gach scair dhíchriptithe dá leithéid.

4. Nuair a bheidh céim (67) críochnaithe ag 3 rannpháirtí, is féidir gach sraith comhaontaithe a dhíchódú agus a athchruthú go hiomlán mar gheall ar airíonna cóid scriosta, agus is féidir an uimhir dheireanach a fháil mar XOR de na sraitheanna tosaigh ar thosaigh na rannpháirtithe leo (1) .

Is féidir a thaispeáint go bhfuil an prótacal seo neamhchlaonta agus dothuartha. Cinntear an uimhir randamach mar thoradh air tar éis comhaontú a bhaint amach, ach ní fios d'aon duine go dtí go ndéanann ⅔ de na rannpháirtithe na codanna criptithe a dhíchódú lena n-eochair phoiblí. Mar sin, déantar an uimhir randamach a chinneadh sula bhfoilsítear faisnéis leordhóthanach chun í a athchruthú.

Cad a tharlaíonn má sheol duine de na rannpháirtithe scaireanna ionchódaithe chuig na rannpháirtithe eile i gcéim (1) nach iad an cód scriosta ceart do theaghrán éigin? Gan athruithe breise, ní bheidh rannpháirtithe éagsúla in ann an teaghrán a aisghabháil ar chor ar bith, nó déanfaidh siad teaghráin éagsúla a aisghabháil, rud a fhágann go bhfaighidh rannpháirtithe éagsúla uimhir randamach difriúil. Chun é seo a chosc, is féidir leat an méid seo a leanas a dhéanamh: ríomhann gach rannpháirtí, chomh maith leis na scaireanna ionchódaithe, Crann Merkla gach scair den sórt sin, agus seolann gach rannpháirtí an sciar ionchódaithe féin agus fréamh an chrainn merkle, agus cruthúnas ar chuimsiú na scaire sa chrann meirgí. Sa chomhdhearcadh i gcéim (2), ní hamháin go n-aontaíonn na rannpháirtithe ar shraith tacair, ach ar shraith fréamhacha sonracha de chrainn den sórt sin (má imigh rannpháirtí éigin ón bprótacal, agus chuir sé fréamhacha crann merkle éagsúla chuig rannpháirtithe éagsúla, agus taispeántar dhá fhréamh den sórt sin le linn comhthola, níl a the row san áireamh sa tacar torthaí). Mar thoradh ar an gcomhdhearcadh, beidh 67 líne ionchódaithe againn agus fréamhacha comhfhreagracha an chrainn merkle ionas go mbeidh ar a laghad 67 rannpháirtí ann (ní gá gurb iad na cinn chéanna a mhol na línte comhfhreagracha), a bhfuil gach ceann de na 67 líne acu. teachtaireacht le sciar den chód scriosta, agus cruthúnas gur tháinig deireadh leis an sciar den chrann comhfhreagrach.

I gcéim (4) déanann an rannpháirtí 67 bhuille do shreang áirithe a dhéanamh amach agus iarracht a dhéanamh an téad bhunaidh a athchruthú uathu, tá ceann de na roghanna indéanta:

1. Déantar an teaghrán a athchóiriú, agus má dhéantar é a scriosadh arís agus arís eile, agus an crann Merkle á ríomh do na scaireanna a ríomhtar go háitiúil, comhthráthach an fhréamh leis an gceann ar thángthas ar chomhdhearcadh.

2. Athchóirítear an tsraith, ach ní hionann an fhréamh a ríomhtar go háitiúil agus an fhréamh ar thángthas ar chomhdhearcadh.

3. Níl an tsraith ar ais.

Is furasta a thaispeáint má tharla rogha (1) do rannpháirtí amháin ar a laghad thuas, gur tharla rogha (1) do gach rannpháirtí, agus vice versa, má tharla rogha (2) nó (3) do rannpháirtí amháin ar a laghad, ansin. do gach rannpháirtí tarlóidh rogha (2) nó (3). Mar sin, do gach sraith sa tsraith, beidh na rannpháirtithe go léir a ghnóthú go rathúil é, nó beidh gach rannpháirtí theipeann é a ghnóthú. Is ionann an uimhir randamach mar thoradh air sin agus XOR de na sraitheanna amháin a raibh na rannpháirtithe in ann a ghnóthú.

Sínithe tairsí

Cur chuige eile maidir le randamacht is ea úsáid a bhaint as rud ar a dtugtar sínithe tairsí BLS. Tá na ráthaíochtaí céanna go díreach ag gineadóir uimhreacha randamacha atá bunaithe ar shínithe tairsí agus atá ag an algartam cód scriosta a bhfuil cur síos déanta air thuas, ach tá líon asymptotic i bhfad níos ísle de theachtaireachtaí a sheoltar thar an líonra do gach uimhir ghinte.

Is dearadh iad sínithe BLS a ligeann do rannpháirtithe iolracha síniú coiteann amháin a chruthú le haghaidh teachtaireachta. Is minic a úsáidtear na sínithe seo chun spás agus bandaleithead a shábháil trí gan gá le sínithe iolracha a sheoladh amach. 

Feidhmchlár coitianta ar shínithe BLS i bprótacail blockchain, chomh maith le huimhreacha randamacha a ghiniúint, is ea síniú bloc i bprótacail BFT. Ligean le rá cruthaíonn 100 rannpháirtí bloic, agus meastar bloc a bheith críochnaitheach má shíníonn 67 acu é. Is féidir leo go léir a gcuid codanna den síniú BLS a chur isteach agus roinnt algartam comhdhearcadh a úsáid chun aontú ar 67 acu agus ansin iad a chumasc isteach i síniú BLS amháin. Is féidir aon 67 (nó níos mó) páirteanna a úsáid chun an síniú deiridh a chruthú, a bheidh ag brath ar cé acu a cuireadh le chéile 67 síniú agus dá bhrí sin d’fhéadfadh athrú a bheith ann, cé go gcruthóidh roghanna difriúla ag na 67 rannpháirtí síniú difriúil, beidh aon síniú den sórt sin bailí síniú don bhloc. Ní gá do na rannpháirtithe eile ansin ach síniú amháin a fháil agus a fhíorú in aghaidh an bhloc, in ionad 67, thar an líonra, rud a laghdaíonn go mór an t-ualach ar an líonra.

Tarlaíonn sé, má ghintear na heochracha príobháideacha a úsáideann rannpháirtithe ar bhealach áirithe, ansin is cuma cén 67 síniú (nó níos mó, ach nach lú) a chomhiomlánaítear, beidh an síniú mar an gcéanna mar thoradh air. Is féidir é seo a úsáid mar fhoinse randamachta: aontaíonn rannpháirtithe ar dtús ar theachtaireacht éigin a shíneoidh siad (d'fhéadfadh gur aschur RANDAO nó hash an bhloic dheireanaigh amháin é seo, is cuma i ndáiríre chomh fada agus a athraíonn sé gach uair agus tá sé comhsheasmhach) agus cruthaigh síniú BLS dó. Ní féidir toradh na giniúna a thuar go dtí go soláthraíonn 67 rannpháirtí a gcuid páirteanna, agus ina dhiaidh sin tá an t-aschur réamhchinnte cheana féin agus ní féidir leis brath ar ghníomhaíochtaí aon rannpháirtí.

Tá an cur chuige seo maidir le randamacht inmharthana chomh fada agus a leanann ⅔ ar a laghad de na rannpháirtithe ar líne an prótacal, agus tá sé neamhchlaonta agus neamh-intuartha chomh fada agus a leanann ⅓ de na rannpháirtithe ar a laghad an prótacal. Tá sé tábhachtach a thabhairt faoi deara gur féidir le hionsaitheoir a rialaíonn níos mó ná ⅓ ach níos lú ná ⅔ de na rannpháirtithe an prótacal a stopadh, ach nach féidir leis a aschur a thuar nó tionchar a imirt.

Is ábhar an-suimiúil iad sínithe tairsí féin. Sa dara cuid den alt, déanfaimid anailís mhionsonraithe ar an gcaoi a n-oibríonn siad, agus conas go díreach atá sé riachtanach eochracha rannpháirtithe a ghiniúint ionas gur féidir sínithe tairsí a úsáid mar ghineadóir uimhreacha randamacha.

Mar fhocal scoir

Is é an t-alt seo an chéad cheann i sraith alt teicniúil blag NEAR. 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 anseo.

Is féidir leat a fheiceáil cén chuma atá ar fhorbairt NEAR agus triail a bhaint as san IDE ar líne anseo.

Is féidir leat an nuacht go léir a leanúint i Rúisis ag grúpa teileagraim agus Grúpa Vkontakte, agus i mBéarla san oifigeach twitter.

Feicfidh mé go luath thú!

Foinse: will.com